This section fixes the encodings and the primitive instances on which the later constructions rest, each with its Orchard parameters and domain separators. The underlying constructions belong to the Math Guide and the Crypto Guide and are cited, not re-derived; each named assumption is stated at the first construction whose security needs it. Table 1 maps each primitive of the Crypto Guide that the Orchard protocol uses to its Orchard instance and to the public data of an Action or a bundle that the instance produces; the public data are those of Remark “Division of verification” (§1.2), each constructed in the section named.
| Crypto Guide section | Orchard instance | Public data produced, or role |
|---|---|---|
| §“Hashing to a curve point” | GroupHash on Pallas (§2.2) | no public field: the fixed bases, and the base g d of each address (§3.3) |
| §“Sinsemilla: an algebraic hash-based commitment” | NoteCommit (§4.2) | the extracted note commitment of each created note |
| Commit ivk (§3.2) | no public field: the incoming viewing key | |
| §“Binary Merkle trees” | the note commitment tree, hashed by MerkleCRH (§5.1) | the anchor of each bundle (§5.2) |
| §“The Pedersen commitment” | ValueCommit Orchard (§8.1) | the commitment to the net value of each Action |
| §“Pseudorandom functions and permutations” | PRFexpand (§2.3) | no public field: keys and the randomness of created notes |
| §“Arithmetisation-friendly hashing: Poseidon” | Poseidon, keyed by nk (§6.1) | the nullifier of each consumed note |
| §“Format-preserving encryption and FF1” | FF1 over AES-256, keyed by dk (§3.3) | no public field: the diversifier of each address |
| §“Shielded-note delivery as deployed hybrid encryption” | Diffie–Hellman on Pallas, BLAKE2b-256 and ChaCha20-Poly1305 (§10.2, §10.3) | the note ciphertext of each created note |
| §“RedDSA: re-randomisable Schnorr for Orchard” | RedPallas, in two instances (§7.1) | the spend-authorisation signature and its validating key (§7.2); the binding signature (§8.3) |
| §“SNARKs: succinct non-interactive arguments of knowledge” | Halo 2 on the Pasta curves, one fixed circuit (§9.3) | the Action proof of each bundle |
The Pallas group E (F p Pallas) is the group of points of the curve
| Object | This volume | Specification | Lower volumes |
|---|---|---|---|
| Pallas base-field modulus | p Pallas | q P | p |
| Pallas scalar-field modulus, Vesta base-field modulus, order of the Pallas group | p Vesta | r P | q |
| Pallas base field and scalar field | F p Pallas , F p Vesta | F q P , F r P | F p , F q |
| Pallas group | E (F p Pallas) | P | E p (F p) |
| k -bit little-endian encoding of an integer | LE k | I2LEBSP k | — |
| Encoding of a point P | P ⋆ | repr P (P) | — |
| Sinsemilla short commitment | ShortCommit | SinsemillaShortCommit | — |
| Spend validating key, as a point and as its x -coordinate | ak P , ak | ak P , ak | — |
Scalar multiplication is written [k] P , for
Both moduli have bit length 255 , and
| 2 254 < p Pallas < p Vesta < 2 255 . |
Two consequences are used later. First, the integer representative of an
element of either field lies in
For
the map I2LEOSP k sends
for k a multiple of 8 , the map LEOS2IP k sends a
k / 8 -byte string (s 0, ..., s k / 8 − 1) to the integer
the map
Hence
The widths used later are LE 10 (the Merkle layer tag, §5.1), LE 64 (the note value, §4.2), LE 88 (the diversifier index, §3.3), LE 255 (field elements) and LE 256 (the star encoding below; the key encoding of r ivk , §3.2).
Let
| Extract P (O) := 0, Extract P ((x, y)) := x . |
Its lifting
The map Extract P supplies a field element wherever a later
construction needs one in place of a point: the field element ak
(§3.1), the extracted note commitment cmx
(§4.2), the node values of the note commitment tree
(§5.1) and the nullifier nf (§6.1).
It is two-to-one on non-identity points, by Lemma 2.4
and because
For
If
For
Negation is
For
| O ⋆ := LE 256 (0), (x, y) ⋆ := LE 256 (x + 2 255 (y mod 2)), |
with x and y read as integer representatives: the 255 -bit
x -coordinate fills the low bits and the parity of y the top bit. The
partial inverse
the failure value ⊥ if
the identity O if
the failure value ⊥ if
otherwise the point (x, y) with
The encoding is canonical:
For byte strings D (the domain separator) and M (the message), the
point
Let
| DST := D ‖ - ‖ pallas ∥ _XMD:BLAKE2b_SSWU_RO_ ; |
the map is defined when DST has at most 255 bytes, which holds for every domain separator of Table 3.
The map hash _ to _ field expands (M, DST) by the
function expand _ message _ xmd over BLAKE2b-512 into two
64 -byte strings. BLAKE2b runs with zero personalisation; the string
DST , followed by a byte carrying its length, is part of the
hashed input. Each string is read as a big-endian integer and reduced
modulo p Pallas , giving
The simplified Shallue–van de Woestijne–Ulas map sends each u i to a point Q i of a curve 3 -isogenous to Pallas.
The output is the image of
No cofactor is cleared, since the Pallas group has prime order. The isogenous curve, the isogeny coefficients and the constant of the map are those of the protocol specification, §“Group Hash into Pallas and Vesta”, and are not reproduced. The map is deterministic, public and efficiently computable (Crypto Guide, §“Hashing to a field element”, Construction “Expand-then-reduce”; §“Hashing to a curve point”, Constructions “Simplified Shallue–van de Woestijne–Ulas map” and “The hash-to-curve pipeline”, Remark “The isogeny required by j -invariant 0 ”).
A domain separator is a fixed ASCII byte string naming a use site; it is the first argument of GroupHash , so that distinct uses draw distinct generators. A fixed generator is the value of GroupHash on a public, fixed pair (D, M) . It is nothing-up-my-sleeve: the public pair determines it, and no party chose it (Crypto Guide, §“Hashing to a curve point”, Construction “Nothing-up-my-sleeve generators”). The strings are fixed by the protocol specification.
In security arguments GroupHash is modelled as a random oracle on pairs (D, M) with values in E (F p Pallas) (Crypto Guide, §“The random oracle model”, Definition “Random oracle”, with the group in place of bit strings): distinct pairs receive independent uniform points. In particular the fixed generators of Table 3 are, in the model, independent uniform points. The assumption is a heuristic about the concrete map, supported by its design for indifferentiability from a random oracle (protocol specification, §“Group Hash into Pallas and Vesta”, note); it is not a theorem. Every later binding, collision, uniqueness or unlinkability result that needs it names it.
Table 3 lists every GroupHash input of the Orchard protocol, with the object it defines and the section that uses it. The messages G, K, v and r are one-byte ASCII strings, and the Sinsemilla messages are the ASCII strings shown. The rows are those of the protocol specification, §“Spend Authorization Signature (Sapling and Orchard)”, §“Computing ρ values and Nullifiers”, §“ DiversifyHash Sapling and DiversifyHash Orchard Hash Functions”, §“Sinsemilla Hash Function”, §“Sinsemilla commitments”, §“ MerkleCRH Orchard Hash Function” and §“Homomorphic Pedersen commitments (Sapling and Orchard)”.
| Domain separator D | Message M | Object | Used in |
|---|---|---|---|
| z.cash:Orchard | G | G SpendAuth , spend-authorisation base | §3.1, §7.1 |
| z.cash:Orchard | K | K Orchard , nullifier base | §6.1 |
| z.cash:Orchard-gd | LEBS2OSP 88 (d) | g d for a diversifier d | §3.3 |
| z.cash:Orchard-gd | ε | g d if the row above gives O | §3.3 |
| z.cash:SinsemillaQ | z.cash:Orchard-NoteCommit-M | hash base of NoteCommit | §4.2 |
| z.cash:Orchard-NoteCommit-r | ε | blinding base of NoteCommit | §4.2 |
| z.cash:SinsemillaQ | z.cash:Orchard-CommitIvk-M | hash base of Commit ivk | §2.4 |
| z.cash:Orchard-CommitIvk-r | ε | blinding base of Commit ivk | §2.4 |
| z.cash:SinsemillaQ | z.cash:Orchard-MerkleCRH | hash base of MerkleCRH | §5.1 |
| z.cash:Orchard-cv | v | V Orchard , value base | §8.1 |
| z.cash:Orchard-cv | r | R Orchard , randomness base | §8.1 |
| z.cash:SinsemillaS | I2LEOSP 32 (j) | table entry S (j) , 0 ≤ j < 2 10 | §2.4 |
The pairs of Table 3 are pairwise distinct, and the map from (D, M) to the input hashed by hash _ to _ field is injective, because DST is closed by a byte carrying its length. Under Assumption 2.8 the table’s generators are therefore independent, and a relation found in one context transfers to no other (Crypto Guide, §“Domain separation and personalisation”, Proposition “Domain separation yields independent oracles”). The Crypto Guide’s inventory of Orchard tags and personalisations in the same section is cited, not repeated.
A keyed family (F k) k of functions is a pseudorandom function (PRF) if no efficient adversary with adaptive oracle access distinguishes F k , for a secret uniform key k , from a uniformly random function with the same domain and range, except with negligible advantage (Crypto Guide, §“Pseudorandom functions and permutations”, Definition “Pseudorandom function”).
For a key
| PRFexpand k (t) := BLAKE2b - 512 ( | Zcash_ExpandSeed, | ||
| LEBS2OSP 256 (k) ∥ t), |
a 64 -byte string, identified with { 0, 1 } 512 ; here BLAKE2b - 512 (P, x) is unkeyed BLAKE2b with a 64 -byte output, the 16 -byte personalisation P and the input x . A key given as a 32 -byte string enters as is. The key is thus carried in the message, not in BLAKE2b’s native keyed mode (protocol specification, §“Pseudo Random Functions”), so the Crypto Guide’s PRF argument for native keying (§“PRFs from hash functions: length extension and keyed BLAKE2”) does not cover this construction; Assumption 2.12 states the property directly. The key is written as a subscript; the leading byte of t names the derived quantity (protocol specification, §“Pseudo Random Functions”).
For k uniform on { 0, 1 } 256 , the function
For
| ToBase (x) | := LEOS2IP 512 (x) mod p Pallas ∈ F p Pallas, | ||
| ToScalar (x) | := LEOS2IP 512 (x) mod p Vesta ∈ F p Vesta |
For x uniform on { 0, 1 } 512 , the statistical distance of
ToBase (x) from the uniform distribution on F p Pallas is
at most p Pallas / 2 512 , and that of ToScalar (x) from the
uniform distribution on F p Vesta at most p Vesta / 2 512
(Math Guide, §“Uniform sampling and the bias of modular
reduction”, Proposition “Bias of modular reduction”, with
Every later use of PRFexpand derives one quantity as
| y := f (PRFexpand κ (b ∥ t ′)), |
where the lead byte b , the key κ , the remainder t ′ of the input
and the reduction
| b | Key κ | Remainder t ′ | f | Output | Section |
|---|---|---|---|---|---|
| 0x06 | sk | ε | ToScalar | ask | §3.1 |
| 0x07 | sk | ε | ToBase | nk | §3.1 |
| 0x08 | sk | ε | ToScalar | r ivk | §3.1 |
| 0x82 | LE 256 (r ivk) | I2LEOSP 256 (ak) ∥ I2LEOSP 256 (nk) | none | dk ∥ ovk | §3.2 |
| 0x04 | rseed | I2LEOSP 256 (ρ) | ToScalar | esk | §4.3 |
| 0x05 | rseed | I2LEOSP 256 (ρ) | ToScalar | rcm | §4.3 |
| 0x09 | rseed | I2LEOSP 256 (ρ) | ToBase | ψ | §4.3 |
| 0x0B | rseed | LEBS2OSP 256 (g d ⋆) ∥ LEBS2OSP 256 (pk d ⋆) ∥ I2LEOSP 64 (v) ∥ I2LEOSP 256 (ρ) ∥ I2LEOSP 256 (ψ) | ToScalar | rcm | §4.3 |
Each reduction matches the use of its output. The outputs ask , r ivk , esk and rcm are reduced by ToScalar into F p Vesta , the scalar field of the Pallas group, because each multiplies a Pallas point: the scalar ask the generator G SpendAuth (§3.1), r ivk and rcm the blinding bases of Commit ivk and NoteCommit (§3.2, §4.2), and esk the diversified base of the recipient’s address (§10.2). The outputs nk and ψ are reduced by ToBase into F p Pallas , the field of the nullifier’s arithmetic, nk as the key of the nullifier PRF on F p Pallas and ψ as a summand of its output (§6.1); it is also the native field of the Action circuit (§9.3). The outputs dk and ovk are used as byte strings, dk as the key of the permutation that derives diversifiers (§3.3) and ovk as an input of BLAKE2b (§10.3), and are not reduced.
Let k be uniform on { 0, 1 } 256 and used only as a PRFexpand
key. Let an efficient algorithm choose, possibly adaptively, pairwise
distinct inputs
One hybrid replaces PRFexpand k by a uniformly random function; the distinguishing advantage changes by at most the PRF advantage of the algorithm that runs the given one and forwards its queries to its own oracle (Assumption 2.12; adaptive queries are within the definition, Crypto Guide, §“Pseudorandom functions and permutations”, Remark “Necessity of adaptivity”). A random function, sampled lazily, answers each new input with a fresh uniform value, so its answers on pairwise distinct inputs are independent and uniform, also when each input depends on earlier answers. For the reduced answers, replacing each f i of a fresh uniform string by a fresh uniform field element changes the distribution of the whole interaction by at most the reduction distance of f i ; summing over i bounds the total by the triangle inequality, and the post-processing by the algorithm does not increase it (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”). A key within statistical distance δ of uniform changes the interaction, a function of the key and the algorithm’s coins, by at most δ , by the same theorem. □
The hypothesis of Lemma 2.15 holds for the spending key sk , and for rseed towards an adversary that sees rseed only through PRFexpand outputs; the note plaintext, which contains rseed , is treated in §10.2. It does not hold for the row 0x82 , whose key encodes the trapdoor r ivk , which is also used in Commit ivk ; that row is covered by Assumption 3.13 in §3.2. The lemma is used in §3.1, in Lemma “Rejection in key generation” (§3.2), in Propositions 3.18, 3.17, 4.8, 6.10 and 10.6, in Proposition “Confidentiality of the outgoing ciphertext” (§10.3), in Theorems 12.10 and 12.13, and in Remark “Hypothesis (H) for honest keys” (§11.3).
Each hash is defined at its construction site. BLAKE2b-512 with personalisation Zcash_ExpandSeed serves PRFexpand (this subsection); BLAKE2b-512 without personalisation serves hash _ to _ field inside GroupHash (§2.2); personalised BLAKE2b-512 serves the RedPallas hash H (§7.1); BLAKE2b-256 serves the note-encryption key derivation and the outgoing cipher key (§10.2, §10.3); BLAKE2b serves the transaction and signature digests (§11.3); Sinsemilla serves MerkleCRH , NoteCommit and Commit ivk (§2.4); Poseidon serves the nullifier PRF, constructed with the nullifier (§6.1). The personalisations of PRFexpand , the note-encryption key derivation and the outgoing cipher key are those of the Crypto Guide’s inventory (§“PRFs from hash functions: length extension and keyed BLAKE2”, Remark “Zcash’s use of keyed and personalised BLAKE2”); every personalisation is stated at its construction.
The Crypto Guide, §“Sinsemilla: an algebraic hash-based
commitment”, Construction “Sinsemilla hash”, fixes the chunk width
| S (j) | := GroupHash (z.cash:SinsemillaS, I2LEOSP 32 (j)) (0 ≤ j < 2 k), | ||
| Q (D) | := GroupHash (z.cash:SinsemillaQ, D) |
for a byte string D , and the accumulator; it writes LE 32 (j) for the four-byte encoding I2LEOSP 32 (j) . The Orchard instance adds the following (protocol specification, §“Sinsemilla Hash Function”).
The chunk bound c is the largest integer with
Incomplete addition ∔ on
For a byte string D and a bit string M of length at most k c ,
let
| Acc 0 := Q (D), Acc i := (Acc i − 1 ∔ S (m i)) ∔ Acc i − 1 (1 ≤ i ≤ n), |
and
The extracted hash is
| SinsemillaHash (D, M) := Extract P ⊥ (SinsemillaHashToPoint (D, M)) ∈ F p Pallas ∪ { ⊥ } . |
For a byte string D , a bit string M of length at most k c and a
trapdoor
| M ^ := SinsemillaHashToPoint (D ∥ -M, M), H D := GroupHash (D ∥ -r, ε) . |
Then, with complete group addition,
| SinsemillaCommit r (D, M) | := { M ^ + [r] H D if M ^ ≠ ⊥, ⊥ otherwise, | ||
| ShortCommit r (D, M) | := Extract P ⊥ (SinsemillaCommit r (D, M)) ∈ F p Pallas ∪ { ⊥ } |
(protocol specification, §“Sinsemilla commitments”). The domain D is routed to the hash as D ∥ -M and to the blinding base as D ∥ -r with the empty message. The Crypto Guide constructs the commitment with a generic independent blinding generator (§“Sinsemilla: an algebraic hash-based commitment”, Construction “SinsemillaCommit”); the routing and the ⊥ case are the Orchard additions.
The unblinded SinsemillaHash is deterministic and therefore not hiding; ShortCommit is its blinded counterpart. Proposition 2.24 and Lemma 2.26 state the security of both.
The Orchard protocol uses three Sinsemilla instances, each with one fixed message length per domain, all within c chunks (Table 5): MerkleCRH , a SinsemillaHash instance whose layout is given in §5.1; NoteCommit , a SinsemillaCommit instance whose layout is given in Definition 4.4; and Commit ivk , a ShortCommit instance defined next.
| Instance | Form | Domain | Message bits | Chunks |
|---|---|---|---|---|
| MerkleCRH | SinsemillaHash | z.cash:Orchard-MerkleCRH | 10 + 2 ⋅ 255 = 520 | 52 |
| NoteCommit | SinsemillaCommit | z.cash:Orchard-NoteCommit | 2 ⋅ 256 + 64 + 2 ⋅ 255 = 1086 | 109 |
| Commit ivk | ShortCommit | z.cash:Orchard-CommitIvk | 2 ⋅ 255 = 510 | 51 |
For
| Commit r ivk ivk (x, y) := ShortCommit r ivk (z.cash:Orchard-CommitIvk, LE 255 (x) ∥ LE 255 (y)), |
a 510 -bit message (protocol specification, §“Sinsemilla commitments”). Its output is ⊥ exactly when
| SinsemillaHashToPoint (z.cash:Orchard-CommitIvk-M, ⋅) |
returns ⊥ ; it is 0 exactly when the commitment point is
O (Lemma 2.3); otherwise it is the
x -coordinate of a non-identity point, an element of
Sinsemilla is used for its cost inside an arithmetic circuit with lookups, one table lookup and two incomplete additions over F p Pallas per k -bit chunk (Crypto Guide, §“Sinsemilla: an algebraic hash-based commitment”, Remark “In-circuit cost of Sinsemilla”; Halo 2 Guide, §“The lookup argument” and §“From statement to circuit: arithmetisation in practice”), and its collision resistance reduces to discrete logarithms on Pallas together with GroupHash modelled as a random oracle, not to discrete logarithms alone.
For every classical probabilistic polynomial-time algorithm, given a generator G of E (F p Pallas) and [s] G for s uniform in F p Vesta , the probability of outputting s is negligible (Crypto Guide, §“The discrete logarithm problem”, Definition “Discrete logarithm problem, DLP”, instantiated on Pallas; Math Guide, §“The elliptic-curve discrete logarithm problem”). Concretely, the best known classical attack costs about 2 126 group operations (Crypto Guide, §“Instantiation on elliptic curves; the Pasta curves”, Proposition “The Pasta curves against the criteria”); the level is cited, not recomputed.
In the model of Assumption 2.8 a reduction receiving a
challenge
Every later argument that ends in a non-trivial discrete-logarithm relation among values of GroupHash ends in this lemma.
Consider an Orchard instance of Table 5 with message length l , hash domain D ′ (z.cash:Orchard-MerkleCRH for MerkleCRH ; D ∥ -M for a commitment instance with domain D ) and, for a commitment instance, blinding base H D . Under Assumptions 2.22 and 2.8, no efficient algorithm outputs, except with negligible probability:
messages
| P := SinsemillaHashToPoint (D ′, M) and P ′ := SinsemillaHashToPoint (D ′, M ′) |
are not ⊥ and satisfy
for a commitment instance, openings (M, r) and (M ′, r ′) in
| C := SinsemillaCommit r (D, M) and C ′ := SinsemillaCommit r ′ (D, M ′) |
are not ⊥ and satisfy
a message in { 0, 1 } l on which
Each such output yields efficiently a non-trivial discrete-logarithm
relation among Q (D ′) , S (0) , …,
The proof is by citation, with the Orchard steps made in place. The cited
arguments are, in the Crypto Guide, §“Sinsemilla: an algebraic
hash-based commitment”, Proposition “Collision resistance of Sinsemilla”,
with the paragraph after it on the extracted coordinate and the fixed
length, and Construction “SinsemillaCommit”; and the
Security argument of the protocol specification, §“Sinsemilla Hash
Function”: Lemma “An injectivity property for Sinsemilla”, the theorem
“Collision resistance of SinsemillaHash and SinsemillaHashToPoint” with its
note extending it to added terms with independent bases, which covers
SinsemillaCommit and ShortCommit , and the theorem that a
⊥ output of SinsemillaHashToPoint yields a non-trivial
discrete-logarithm relation. These arguments write a non- ⊥ output on
the pieces
| SinsemillaHashToPoint (D ′, M) = [2 n] Q (D ′) + ∑ j = 0 2 k − 1 [χ j (m)] S (j), | (1) |
where
| ∑ j [χ j (m) − χ j (m ′)] S (j) + [r − r ′] H D = O, |
non-trivial because
| [2 n + 1] Q (D ′) + ∑ j [χ j (m) + χ j (m ′)] S (j) + [r + r ′] H D = O, |
non-trivial because its coefficient on Q (D ′) is non-zero. An exceptional
case at step i has the form
Three steps are made in place.
(1) Each instance hashes one fixed length l per domain, and l is
admissible:
The fixed-length hypothesis cannot be dropped. The point hash SinsemillaHashToPoint zero-pads its input to a multiple of k bits, so for a message M whose length is not a multiple of k the messages M and M ∥ 0 collide with no discrete-logarithm relation. The specification requires collision resistance only between inputs of one fixed length for a given domain (protocol specification, §“Sinsemilla Hash Function”), and every Orchard domain hashes a single length.
Let D be a byte string and
Perfect hiding: if
The lemma is the Crypto Guide’s Construction “SinsemillaCommit”
(§“Sinsemilla: an algebraic hash-based commitment”) for the Orchard
blinding base. (i) Since