matrix-org / matrix-org/matrix-spec
Spec's `NACL` allusions are ambiguous to ZIP-215 vs. strict RFC 8032 `ed25519` signing key algos
Nobody has claimed this yet.
- Dominant language
- HTML
- Stars
- 330
- Forks
- 150
- Avg merge
- 2h 21m
- Merged PRs (30d)
- 3
Description
### Link to problem area
spec revision v1.15, appendix 3 section 2 _Signing Details_, references: "`ed25519` as implemented by NACL"
v1.15 server-server-api further alludes to this in 2.3: "modified to include the NACL keys and to use JSON"
- https://spec.matrix.org/v1.15/appendices/#signing-details
- https://spec.matrix.org/v1.15/server-server-api/#retrieving-server-keys
Synapse, indeed, uses the `NACL` library.
Ruma, however, has a long-standing contract with the sequential (non-batched) `ed25519-dalek` library.
_signatures: Replace ring with ed25519-dalek · ruma/ruma@b6f0cb97157ac576ca9ea1dc059b642c2b891172_ (committed on Jun 17, 2021)
### Issue
The choice is ours: `dalek` vs. `consensus`? Initially I thought `ed25519-dalek` (currently tracks RFC 8032) was more secure, but it's unclear whether we care or wish to allow servers to publish less secure keys. The "consensus" library (tracks ZIP 215) appears to perform better under load/batches but worse sequentially or individually (see table in below section).
Regarding some general concerns, relevant material quoted directly from Zcash's ZIP 215:
> RATIONALE
> This change simplifies the Ed25519 validation logic and reduces future maintenance burden. Because multiplication by the cofactor admits more solutions to the validation equation, not fewer, it is compatible with all existing Ed25519 signatures on the chain.
> It also allows the use of batch validation, which requires multiplication by the cofactor in the validation equation.
> SECURITY and PRIVACY CONSIDERATIONS
> This change has no effect on honestly-generated signatures. Unlike the current validation rules, it makes it possible for a user to generate weak signing keys or to generate signing keys with nonzero torsion component and submit them to the blockchain. However, doing so provides them with no advantage, only compromise to their own security. Moreover, these cases are not a failure mode of any deployed implementation.
### Implementation notes
Benchmarks from gamesguru/rezzy@0869541a2870f81da45e83b6b10485c9b31a6b40, which baselines at 1.05× faster than Ruma.
By moving to batched ZIP-215 verification, I can speed this up by a further factor of 3-5×, while also achieving full parity with Synapse (still comfortably the most widespread implementation).
```text
Workload Dalek ZIP-215 consensus Winner
━━━━━━━━━━━━━━━━━━━ ━━━━━━━━━━━━━━━━━━━ ━━━━━━━━━━━━━━━━━━━ ━━━━━━━━━━━━━━━━━━
Sequential, 1 34.5 µs 45.0 µs Dalek, 1.31×
─────────────────── ─────────────────── ─────────────────── ──────────────────
Sequential, 5,000 35.7 µs/signature 45.4 µs/signature Dalek, 1.27×
─────────────────── ─────────────────── ─────────────────── ──────────────────
Batch, 64 18.1 µs/signature 10.5 µs/signature Consensus, 1.72×
─────────────────── ─────────────────── ─────────────────── ──────────────────
Batch, 5,000 10.5 µs/signature 7.39 µs/signature Consensus, 1.42×
```
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Read spec revision v1.15 appendix 3 section 2, Signing Details, and server-server-api 2.3, Retrieving server keys. Compare the linked Ruma commit with the supplied Dalek and ZIP-215 benchmark. Done means the specification unambiguously defines the required Ed25519 verification behavior and resolves the NACL wording.
Written by the indexing model from the issue text.
Assessment
- Domain
- cryptography, documentation
- Issue type
- Documentation
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100