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” | on Pallas (§2.2) | no public field: the fixed bases, and the base of each address (§3.3) |
| §“Sinsemilla: an algebraic hash-based commitment” | (§4.2) | the extracted note commitment of each created note |
| (§3.2) | no public field: the incoming viewing key | |
| §“Binary Merkle trees” | the note commitment tree, hashed by (§5.1) | the anchor of each bundle (§5.2) |
| §“The Pedersen commitment” | (§8.1) | the commitment to the net value of each Action |
| §“Pseudorandom functions and permutations” | (§2.3) | no public field: keys and the randomness of created notes |
| §“Arithmetisation-friendly hashing: Poseidon” | Poseidon, keyed by (§6.1) | the nullifier of each consumed note |
| §“Format-preserving encryption and FF1” | FF1 over AES-256, keyed by (§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 is the group of points of the curve
| Object | This volume | Specification | Lower volumes |
|---|---|---|---|
| Pallas base-field modulus | |||
| Pallas scalar-field modulus, Vesta base-field modulus, order of the Pallas group | |||
| Pallas base field and scalar field | , | , | , |
| Pallas group | |||
| -bit little-endian encoding of an integer | — | ||
| Encoding of a point | — | ||
| Sinsemilla short commitment | — | ||
| Spend validating key, as a point and as its -coordinate | , | , | — |
Scalar multiplication is written , for
Both moduli have bit length , and
Two consequences are used later. First, the integer representative of an
element of either field lies in
For
the map sends
for a multiple of , the map sends a
-byte string to the integer
the map
Hence
The widths used later are (the Merkle layer tag, §5.1), (the note value, §4.2), (the diversifier index, §3.3), (field elements) and (the star encoding below; the key encoding of , §3.2).
Let
Its lifting
The map supplies a field element wherever a later
construction needs one in place of a point: the field element
(§3.1), the extracted note commitment
(§4.2), the node values of the note commitment tree
(§5.1) and the nullifier (§6.1).
It is two-to-one on non-identity points, by Lemma 2.4
and because
For
If
For
Negation is
For
with and read as integer representatives: the -bit
-coordinate fills the low bits and the parity of the top bit. The
partial inverse
the failure value if
the identity if
the failure value if
otherwise the point with
The encoding is canonical:
For byte strings (the domain separator) and (the message), the
point
The map expands by the
function over BLAKE2b-512 into two
-byte strings. BLAKE2b runs with zero personalisation; the string
, 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 , giving
The simplified Shallue–van de Woestijne–Ulas map sends each to a point of a curve -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 -invariant ”).
A domain separator is a fixed ASCII byte string naming a use site; it is the first argument of , so that distinct uses draw distinct generators. A fixed generator is the value of on a public, fixed pair . 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 is modelled as a random oracle on pairs with values in (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 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”, §“ and Hash Functions”, §“Sinsemilla Hash Function”, §“Sinsemilla commitments”, §“ Hash Function” and §“Homomorphic Pedersen commitments (Sapling and Orchard)”.
| Domain separator | Message | Object | Used in |
|---|---|---|---|
| z.cash:Orchard | G | , spend-authorisation base | §3.1, §7.1 |
| z.cash:Orchard | K | , nullifier base | §6.1 |
| z.cash:Orchard-gd | for a diversifier | §3.3 | |
| z.cash:Orchard-gd | if the row above gives | §3.3 | |
| z.cash:SinsemillaQ | z.cash:Orchard-NoteCommit-M | hash base of | §4.2 |
| z.cash:Orchard-NoteCommit-r | blinding base of | §4.2 | |
| z.cash:SinsemillaQ | z.cash:Orchard-CommitIvk-M | hash base of | §2.4 |
| z.cash:Orchard-CommitIvk-r | blinding base of | §2.4 | |
| z.cash:SinsemillaQ | z.cash:Orchard-MerkleCRH | hash base of | §5.1 |
| z.cash:Orchard-cv | v | , value base | §8.1 |
| z.cash:Orchard-cv | r | , randomness base | §8.1 |
| z.cash:SinsemillaS | table entry , | §2.4 |
The pairs of Table 3 are pairwise distinct, and the map from to the input hashed by is injective, because 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 of functions is a pseudorandom function (PRF) if no efficient adversary with adaptive oracle access distinguishes , for a secret uniform key , 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
a -byte string, identified with ; here is unkeyed BLAKE2b with a -byte output, the -byte personalisation and the input . A key given as a -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 names the derived quantity (protocol specification, §“Pseudo Random Functions”).
For uniform on , the function
For uniform on , the statistical distance of
from the uniform distribution on is
at most , and that of from the
uniform distribution on at most
(Math Guide, §“Uniform sampling and the bias of modular
reduction”, Proposition “Bias of modular reduction”, with
Every later use of derives one quantity as
where the lead byte , the key , the remainder of the input
and the reduction
| Key | Remainder | Output | Section | ||
|---|---|---|---|---|---|
| §3.1 | |||||
| §3.1 | |||||
| §3.1 | |||||
| none | §3.2 | ||||
| §4.3 | |||||
| §4.3 | |||||
| §4.3 | |||||
| §4.3 |
Each reduction matches the use of its output. The outputs , , and are reduced by into , the scalar field of the Pallas group, because each multiplies a Pallas point: the scalar the generator (§3.1), and the blinding bases of and (§3.2, §4.2), and the diversified base of the recipient’s address (§10.2). The outputs and are reduced by into , the field of the nullifier’s arithmetic, as the key of the nullifier PRF on and as a summand of its output (§6.1); it is also the native field of the Action circuit (§9.3). The outputs and are used as byte strings, as the key of the permutation that derives diversifiers (§3.3) and as an input of BLAKE2b (§10.3), and are not reduced.
Let be uniform on and used only as a
key. Let an efficient algorithm choose, possibly adaptively, pairwise
distinct inputs
One hybrid replaces 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 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 ; summing over 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 , and for towards an adversary that sees only through outputs; the note plaintext, which contains , is treated in §10.2. It does not hold for the row , whose key encodes the trapdoor , which is also used in ; 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 (this subsection); BLAKE2b-512 without personalisation serves inside (§2.2); personalised BLAKE2b-512 serves the RedPallas hash (§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 , and (§2.4); Poseidon serves the nullifier PRF, constructed with the nullifier (§6.1). The personalisations of , 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
for a byte string , and the accumulator; it writes for the four-byte encoding . The Orchard instance adds the following (protocol specification, §“Sinsemilla Hash Function”).
The chunk bound is the largest integer with
Incomplete addition on
For a byte string and a bit string of length at most ,
let
and
The extracted hash is
For a byte string , a bit string of length at most and a
trapdoor
Then, with complete group addition,
(protocol specification, §“Sinsemilla commitments”). The domain is routed to the hash as and to the blinding base as 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 is deterministic and therefore not hiding; is its blinded counterpart. Proposition 2.24 and Lemma 2.26 state the security of both.
| Instance | Form | Domain | Message bits | Chunks |
|---|---|---|---|---|
| z.cash:Orchard-MerkleCRH | ||||
| z.cash:Orchard-NoteCommit | ||||
| z.cash:Orchard-CommitIvk |
For
a -bit message (protocol specification, §“Sinsemilla commitments”). Its output is exactly when
returns ; it is exactly when the commitment point is
(Lemma 2.3); otherwise it is the
-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 per -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 modelled as a random oracle, not to discrete logarithms alone.
For every classical probabilistic polynomial-time algorithm, given a generator of and for uniform in , the probability of outputting 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 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 ends in this lemma.
Consider an Orchard instance of Table 5 with message length , hash domain (z.cash:Orchard-MerkleCRH for ; for a commitment instance with domain ) and, for a commitment instance, blinding base . Under Assumptions 2.22 and 2.8, no efficient algorithm outputs, except with negligible probability:
messages
are not and satisfy
for a commitment instance, openings and in
are not and satisfy
a message in on which
Each such output yields efficiently a non-trivial discrete-logarithm
relation among , , …,
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
and , and the theorem that a
output of yields a non-trivial
discrete-logarithm relation. These arguments write a non- output on
the pieces
| (1) |
where
non-trivial because
non-trivial because its coefficient on is non-zero. An exceptional
case at step has the form
Three steps are made in place.
(1) Each instance hashes one fixed length per domain, and is
admissible:
The fixed-length hypothesis cannot be dropped. The point hash zero-pads its input to a multiple of bits, so for a message whose length is not a multiple of the messages and 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 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