Explicitly Defining and Modifying Ed25519 Validation Rules

Preamble

ZIP

215

Title

Explicitly Defining and Modifying Ed25519 Validation Rules

Owners

Henry de Valence

Status

Final

Category

Consensus

Created

2020-04-27

License

BSD-2-Clause

Terminology

The key words "MUST" and "MUST NOT" in this document is to be interpreted as described in BCP 14¹ when, and only when, they appear in all capitals.

Abstract

Zcash uses Ed25519 signatures as part of Sprout transactions. However, Ed25519 does not clearly define criteria for signature validity, and implementations conformant to RFC 8032² need not agree on whether signatures are valid. This is unacceptable for a consensus-critical application like Zcash. Currently, Zcash inherits criteria for signature validity from an obsolete version of libsodium. Instead, this ZIP settles the situation by explicitly defining the Ed25519 validity criteria and changing them to be compatible with batch validation.

Motivation

The lack of clear validity criteria for Ed25519 signatures poses a maintenance burden. The initial implementation of Zcash consensus in zcashd inherited validity criteria from a then-current version of libsodium (1.0.15). Due to a bug in libsodium, this was different from the intended criteria documented in the Zcash protocol specification³ (before the specification was changed to match libsodium 1.0.15 in specification version 2020.1.2). Also, libsodium never guaranteed stable validity criteria, and changed behavior in a later point release. This forced zcashd to use an older version of the library before eventually patching a newer version to have consistent validity criteria. To be compatible, Zebra had to implement a special library, ed25519-zebra to provide Zcash-flavored Ed25519, attempting to match libsodium 1.0.15 exactly. And the initial attempt to implement ed25519-zebra was also incompatible, because it precisely matched the wrong compile-time configuration of libsodium.

In addition, the validity criteria used by Zcash preclude the use of batch validation of Ed25519 signatures. While signature validation is not the primary bottleneck for Zcash, it would be nice to be able to batch-validate signatures, as is the case for RedJubjub.

Specification

After activation of this ZIP, the $\mathsf{JoinSplitSig}$ validation rules in⁴ are changed to the following:

• $\underline{A}$ and $\underline{R}$ MUST be encodings of points $A$ and $R$ respectively on the complete twisted Edwards curve Ed25519;
• $\underline{S}$ MUST represent an integer $S$ less than $\ell$;
• The group equation $[8][S]B = [8]R + [8][k]A$ MUST be satisfied, where $k$ and $B$ are defined as in RFC 8032 sections §5.1.7 and §5.1 respectively.⁵

The language about $\mathsf{ExcludedPointEncodings}$ in §5.4.5 of the Zcash specification⁶ no longer applies.

It is not required that $\underline{A}$ and $\underline{R}$ are canonical encodings; in other words, the integer encoding the $y$-coordinate of the points may be unreduced modulo $2^{255}-19$.

Note: the alternate validation equation $[S]B = R + [k]A$, allowed by RFC 8032, MUST NOT be used.

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.

Deployment

This is intended to be deployed with the Canopy Network Upgrade⁷, which is scheduled to activate on Mainnet⁸ at block height 1046400.

References

---

1. Information on BCP 14 — "RFC 2119: Key words for use in RFCs to Indicate Requirement Levels" and "RFC 8174: Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words"↩︎

2. RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA)↩︎

3. Zcash Protocol Specification, Version 2020.1.1↩︎

4. Zcash Protocol Specification, Version 2021.2.16. Section 5.4.6: Ed25519↩︎

5. RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA)↩︎

6. Zcash Protocol Specification, Version 2021.2.16. Section 5.4.6: Ed25519↩︎

7. ZIP 251: Deployment of the Canopy Network Upgrade↩︎

8. Zcash Protocol Specification, Version 2021.2.16. Section 3.12: Mainnet and Testnet↩︎