Skip to content

Latest commit

 

History

History
231 lines (165 loc) · 10.7 KB

zip-0216.rst

File metadata and controls

231 lines (165 loc) · 10.7 KB
Raw
ZIP: 216
Title: Require Canonical Jubjub Point Encodings
Owners: Jack Grigg <jack@electriccoin.co>
        Daira Hopwood <daira@electriccoin.co>
Status: Proposed
Category: Consensus
Created: 2021-02-11
License: MIT
Discussions-To: <https://github.com/zcash/zips/issues/400>

Terminology

The key word "MUST" in this document is to be interpreted as described in RFC 2119. 1

The term "network upgrade" in this document is to be interpreted as described in ZIP 200.2

Abstract

This ZIP fixes an oversight in the implementation of the Sapling consensus rules, by rejecting all non-canonical representations of Jubjub points.

Motivation

The Sapling specification was originally written with the intent that all values, including Jubjub points, are strongly typed with canonical representations.3 This has significant advantages for security analysis, because it allows the protocol to be modelled with just the abstract types.

The intention of the Jubjub implementation (both in the jubjub crate4 and its prior implementations) was to ensure that only canonical point encodings would be accepted by the decoding logic. However, an oversight in the implementation allowed an edge case to slip through: for each point on the curve where the u​-coordinate is zero, there are two encodings that will be accepted:

// Fix the sign of `u` if necessary
let flip_sign = Choice::from((u.to_bytes()[0] ^ sign) & 1);
let u_negated = -u;
let final_u = Fq::conditional_select(&u, &u_negated, flip_sign);

This code accepts either sign bit, because u_negated == u.

There are two points on the Jubjub curve with u​-coordinate zero:

  • (0, 1), which is the identity;
  • (0,  − 1), which is a point of order two.

Each of these has a single non-canonical encoding in which the value of the sign bit is 1.

This creates a consensus issue because (unlike other non-canonical point encodings that are rejected) either of the above encodings can be decoded, and then re-encoded to a different encoding. For example, if a non-canonical encoding appeared in a transaction field, then node implementations that store points internally as abstract curve points, and used those to derive transaction IDs, would derive different IDs than nodes which store transactions as bytes (such as zcashd).

This issue is not known to cause any security vulnerability, beyond the risk of consensus incompatibility. In fact, for some of the fields that would otherwise be affected, the issue does not occur because there are already consensus rules that prohibit small-order points, and this incidentally prohibits non-canonical encodings.

Adjustments to the protocol specification were made in versions 2020.1.8, 2020.1.9, 2020.1.15, and 2021.1.17 to match the zcashd implementation. (The fact that this required 4 specification revisions to get right, conclusively demonstrates the problem.)

Specification

Let abst𝕁, repr𝕁, and q𝕁 be as defined in5.

Define a non-canonical compressed encoding of a Jubjub point to be a sequence of 256 bits, b, such that abst𝕁(b) ≠ ⊥ and repr𝕁(abst𝕁(b)) ≠ b.

Non-normative note: There are two such bit sequences, I2LEOSPℓ𝕁(2255 + 1) and I2LEOSPℓ𝕁(2255 + q𝕁 − 1). The Sapling protocol uses little-endian ordering when converting between bit and byte sequences, so the first of these sequences corresponds to a 0x01 byte, followed by 30 zero bytes, and then a 0x80 byte.

Once this ZIP activates, the following places within the Sapling consensus protocol where Jubjub points occur MUST reject non-canonical Jubjub point encodings.

In Sapling Spend descriptions6:

  • the $\underline{R}$ component (i.e. the first 32 bytes) of the spendAuthSig RedDSA signature.

In transactions7:

  • the $\underline{R}$ component (i.e. the first 32 bytes) of the bindingSigSapling RedDSA signature.

In the plaintext obtained by decrypting the Cout field of a Sapling transmitted note ciphertext8:

  • pk⋆d.

(This affects decryption of Cout in all cases, but is consensus-critical only in the case of a shielded coinbase output. 9)

There are some additional fields in the consensus protocol that encode Jubjub points, but where non-canonical encodings MUST already be rejected as a side-effect of existing consensus rules.

In Sapling Spend descriptions:

  • cv
  • rk

In Sapling Output descriptions10:

  • cv
  • ephemeralKey.

These fields cannot by consensus contain small-order points. All of the points with non-canonical encodings are small-order.

Implementations MAY choose to reject non-canonical encodings of the above four fields early in decoding of a transaction. This eliminates the risk that parts of the transaction could be re-serialized from their internal representation to a different byte sequence than in the original transaction, e.g. when calculating transaction IDs.

In addition, Sapling addresses and full viewing keys MUST be considered invalid when imported if they contain non-canonical Jubjub point encodings, or encodings of points that are not in the prime-order subgroup 𝕁(r). These requirements MAY be enforced in advance of NU5 activation.

In Sapling addresses11:

  • the encoding of pkd.

In Sapling full viewing keys12 and extended full viewing keys13:

  • the encoding of ak.

(ak also MUST NOT encode the zero point 𝒪𝕁.)

The above is intended to be a complete list of the places where compressed encodings of Jubjub points occur in the Zcash consensus protocol and in plaintext, address, or key formats.

Rationale

Zcash previously had a similar issue with non-canonical representations of points in Ed25519 public keys and signatures. In that case, given the prevalence of Ed25519 signatures in the wider ecosystem, the decision was made in ZIP 21514 (which activated with the Canopy network upgrade15) to allow non-canonical representations of points.

In Sapling, we are motivated instead to reject these non-canonical points:

  • The chance of the identity occurring anywhere within the Sapling components of transactions from implementations following the standard protocol is cryptographically negligible.
  • This re-enables the aforementioned simpler security analysis of the Sapling protocol.
  • The Jubjub curve has a vastly-smaller scope of usage in the general cryptographic ecosystem than Curve25519 and Ed25519.

The necessary checks are very simple and do not require cryptographic operations, therefore the performance impact will be negligible.

The public inputs of Jubjub points to the Spend circuit (rk and cvold) and Output circuit (cvnew and epk) are not affected because they are represented in affine coordinates as elements of the correct field (𝔽r𝕊 = 𝔽q𝕁), and so no issue of encoding canonicity arises.

Encodings of elliptic curve points on Curve25519, BN-254 𝔾1, BN-254 𝔾2, BLS12-381 𝔾1, and BLS12-381 𝔾2 are not affected.

Encodings of elliptic curve points on the Pallas and Vesta curves in the NU5 proposal 16 are also not affected.

Security and Privacy Considerations

This ZIP eliminates a potential source of consensus divergence between differing full node implementations. At the time of writing (February 2021), no such divergence exists for any production implementation of Zcash, but the alpha-stage zebrad node implementation would be susceptible to this issue.

Deployment

This ZIP is proposed to activate with Network Upgrade 5. Requirements on points encoded in payment addresses and full viewing keys MAY be enforced in advance of NU5 activation.

References

  1. RFC 2119: Key words for use in RFCs to Indicate Requirement Levels↩

  2. ZIP 200: Network Upgrade Mechanism↩

  3. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 5.4.9.3: Jubjub↩

  4. jubjub Rust crate↩

  5. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 5.4.9.3: Jubjub↩

  6. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 4.4: Spend Descriptions↩

  7. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 7.1: Transaction Encoding and Consensus↩

  8. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 4.19.3 Decryption using a Full Viewing Key (Sapling and Orchard)↩

  9. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 7.1: Transaction Encoding and Consensus↩

  10. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 4.5: Output Descriptions↩

  11. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 5.6.3.1: Sapling Payment Addresses↩

  12. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 5.6.3.3: Sapling Full Viewing Keys↩

  13. ZIP 32: Shielded Hierarchical Deterministic Wallets. Sapling extended full viewing keys↩

  14. ZIP 215: Explicitly Defining and Modifying Ed25519 Validation Rules↩

  15. ZIP 251: Deployment of the Canopy Network Upgrade↩

  16. Zcash Protocol Specification, Version 2021.1.24 [NU5 proposal]. Section 5.4.9.6: Pallas and Vesta↩