The Zcash ArboretumII Crypto Guide
Contents
PDF
Theme

3 Hash functions and the random oracle model

A hash function compresses arbitrary data into a short fixed-length tag. Digital signatures, commitment schemes, message authentication, key derivation, proof-of-work, Merkle trees, and the Fiat–Shamir transform behind Halo 2’s non-interactive arguments all use one, because an ideal hash acts as a deterministic source of fresh randomness keyed by its input. This section defines the three classical security notions and proves their hierarchy (Proposition 3.8), bounds generic collision finding at about the square root of the number of digests (Lemma 3.11), proves the two powers of the random oracle model on which Fiat–Shamir proofs rest (Proposition 3.14), and proves that domain separation keeps a digest computed for one use from serving in another (Proposition 3.17). It then constructs hashing into a finite field and onto an elliptic curve (from which the next section’s commitment generators derive) and the arithmetisation-friendly hash Poseidon that Orchard evaluates inside its circuit, and registers the transparent layer’s SHA-256-derived hashes.

3.1 Syntax

The set of all finite binary strings is {0,1}∗; the strings of length exactly n form {0,1}n; the length of a string x is |x|; and concatenation is written x∥y.

Definition 3.1 (Hash function).

A hash function with output length n∈ℕ is a function

H:{0,1}∗⟶{0,1}n.

Elements of the codomain are called digests, hashes, or tags. The function is compressing on a domain D⊆{0,1}∗ if D contains strings longer than n; when the domain is all of {0,1}∗, the function is overwhelmingly many-to-one.

Practice deploys a single fixed function such as SHA-256, but collision resistance of a fixed function admits no meaningful asymptotic definition. For any fixed compressing H there exist inputs x≠x′ with H(x)=H(x′), by the pigeonhole principle, so a short program that outputs one such hardcoded pair exists, is efficient, and always succeeds; the asymptotic statement “no efficient adversary finds a collision” is therefore false for every fixed compressing function. (No collision for SHA-256 is known, but existence suffices to falsify the universally quantified claim.) The standard remedy indexes the function by a key.

Definition 3.2 (Keyed hash family).

A keyed hash family (or hash function ensemble) is a function

H:𝒦×{0,1}∗⟶{0,1}n,

where 𝒦 is a finite key space. A key s∈𝒦 is sampled publicly at random, fixed, and we write Hs(⋅):=H(s,⋅) for the family member in force.

The key indexes the member of the family that the adversary must attack: a hardcoded collision for one member is of no use against an independently sampled member, so “no efficient adversary finds a collision for a random member” is a meaningful asymptotic statement.

Remark 3.3 (Convention: keyed definitions, unkeyed deployments).

This volume follows the standard convention. Security notions are stated for the keyed family; every concrete construction deployed is unkeyed; and the key is identified, informally, with “the choice of standard”: the sampling of s occurred, once and in public, when the function was designed. No formal theorem connects the two readings; the gap is the one that separates the random oracle model of §3.4 from deployed hashes.

Definition 3.4 (Extendable-output function).

An extendable-output function (XOF) is a primitive producing a digest of caller-chosen length: syntactically a function

H:{0,1}∗×ℕ⟶{0,1}∗,|H⁢(x,ℓ)|=ℓ,

whose outputs are prefix-consistent: for ℓ≤ℓ′, the string H(x,ℓ) is a prefix of H(x,ℓ′), so a longer request extends a shorter one as a stream.

The canonical XOFs are SHAKE128 and SHAKE256 from the SHA-3 family. Hashing into a finite field or onto a curve (§3.6) needs a controlled number of uniform bits for reduction modulo a prime, which an XOF supplies directly.

3.2 Security notions: preimage, second-preimage, and collision resistance

Each of the three classical security notions is a game between a challenger and a PPT adversary 𝒜, in the template of Definition 1.15; the keyed family H is secure in a given sense if every PPT adversary wins the corresponding game with probability negligible in the security parameter λ (Math Guide, §“Polynomial, exponential, and negligible functions”; §1.2). All sizes are functions of λ: the output length n=n(λ), the key length, and a polynomially bounded challenge input length m=m(λ) from which the games sample their random challenge x←${0,1}m.

Definition 3.5 (Preimage resistance).

The game 𝖯𝖱𝖤H𝒜(λ) runs as follows.

  1. 1.

    The challenger samples s←$𝒦 and x←${0,1}m, computes y:=Hs(x), and sends (s,y) to the adversary.

  2. 2.

    The adversary outputs x′∈{0,1}∗.

  3. 3.

    The game outputs 1 iff Hs(x′)=y.

The family H is preimage resistant (or one-way) if for every PPT 𝒜,

AdvHpre⁢(𝒜,λ):=Pr⁡[𝖯𝖱𝖤H𝒜⁢(λ)=1]∈negl⁡(λ).

Any preimage of y wins; the adversary need not recover the original x.

Definition 3.6 (Second-preimage resistance).

The game 𝖲𝖤𝖢H𝒜(λ) runs as follows.

  1. 1.

    The challenger samples s←$𝒦 and x←${0,1}m, and sends (s,x) to the adversary.

  2. 2.

    The adversary outputs x′∈{0,1}∗.

  3. 3.

    The game outputs 1 iff x′≠x and Hs(x′)=Hs(x).

The family H is second-preimage resistant if for every PPT 𝒜,

AdvHsec⁢(𝒜,λ):=Pr⁡[𝖲𝖤𝖢H𝒜⁢(λ)=1]∈negl⁡(λ).
Definition 3.7 (Collision resistance).

The game 𝖢𝖮𝖫H𝒜(λ) runs as follows.

  1. 1.

    The challenger samples s←$𝒦 and sends s to the adversary.

  2. 2.

    The adversary outputs a pair (x,x′).

  3. 3.

    The game outputs 1 iff x≠x′ and Hs(x)=Hs(x′).

The family H is collision resistant if for every PPT 𝒜,

AdvHcol⁢(𝒜,λ):=Pr⁡[𝖢𝖮𝖫H𝒜⁢(λ)=1]∈negl⁡(λ).

The three notions are ordered by the following proposition.

Proposition 3.8 (Hierarchy of notions).

Let H be a keyed hash family that is compressing, with challenge input length m>n. Then:

  1. 1.

    collision resistance implies second-preimage resistance, with no loss; and

  2. 2.

    second-preimage resistance implies preimage resistance up to an additive loss of 2n−m, which is negligible—so the implication holds outright—whenever H is sufficiently compressing, m−n=ω(logλ).

Neither implication reverses in general.

Proof.

(1) From an adversary 𝒜 against second-preimage resistance, construct ℬ against collision resistance: on input the key s, the reduction ℬ samples x←${0,1}m itself, runs x′←𝒜(s,x)—the simulated view is exactly that of 𝖲𝖤𝖢, since ℬ samples x from the same distribution as the challenger—and outputs the pair (x,x′). Whenever 𝒜 succeeds, x′≠x and Hs(x′)=Hs(x), which is precisely a collision. Hence AdvHcol(ℬ,λ)≥AdvHsec(𝒜,λ): the reduction is tight, and if the left side is negligible so is the right.

(2) Towards the contrapositive, let 𝒜 be an inverter; we build a second-preimage finder ℬ. On input (s,x), the reduction computes y:=Hs(x), runs x′←𝒜(s,y)—again a perfect simulation of 𝖯𝖱𝖤, since x is uniform and y is its digest—and outputs x′. Whenever 𝒜 succeeds, Hs(x′)=y=Hs(x); it remains to show that x′≠x except with probability at most 2n−m. Fix 𝒜’s coins, so that its output on each digest is a single string x′=𝒜(s,y). An input x can satisfy x=𝒜(s,Hs(x)) only if x is the output assigned to its own digest, so each of the 2n digests contributes at most one such input, and at most 2n inputs in all are “fixed points” of the composed map. Over uniform x←${0,1}m, therefore, Pr[x′=x]≤2n/2m=2n−m; averaging over 𝒜’s coins preserves the bound. Hence

AdvHsec⁢(ℬ,λ)≥AdvHpre⁢(𝒜,λ)−2n−m.

The loss is additive, not multiplicative: nothing bounds Pr[x′≠x] conditioned on success, because 𝒜’s successes might concentrate on small fibres where returning x itself is likely. Sufficient compression, m−n=ω(logλ), makes 2n−m negligible and the implication unconditional.

Non-reversal is witnessed by Example 3.9 below. □

Example 3.9 (Preimage-resistant but not collision-resistant).

Take any one-way family H and define H′s(x):=Hs(x¯), where x¯ deletes the last bit of x. The family H′ inherits one-wayness: a preimage challenge (s,y) for H is distributed exactly as one for H′ at one bit greater challenge length, and an H′-inverter’s output x′′ satisfies Hs(x′′¯)=y, so deleting its last bit gives the reduction a preimage under H. Yet the pair x∥ 0, x∥ 1 is an immediate collision for every x, found without any computation. Hence preimage resistance does not imply collision resistance. The other separations are constructed similarly; the implications of Proposition 3.8 are strictly one-directional.

Figure 4 draws the order and the separation that Example 3.9 gives.

Refer to caption
Figure 4: The implications of Proposition 3.8 for a compressing keyed family H with challenge length m>n. Each solid arrow (green) is an implication, proved by a reduction that turns an adversary against the lower notion into one against the upper: collision resistance yields second-preimage resistance with no loss, and second-preimage resistance yields preimage resistance up to the additive loss 2n−m, negligible when m−n=ω(logλ). The struck edge (amber) is Example 3.9: the family H′, which deletes the last bit of its input before hashing, is one-way whenever H is, yet x∥ 0 and x∥ 1 collide for every x, so preimage resistance does not imply collision resistance.
Remark 3.10 (Which application needs which notion).

Password storage, which keeps a digest of each password so that a stolen table does not reveal them, requires preimage resistance: an attacker who obtains the table holds digests, and any preimage suffices to authenticate. (Preimage resistance is not the only requirement there: passwords are guessable, so deployments hash each together with a unique random string, its salt, through a deliberately slow function, to resist offline guessing.) A signature scheme that signs H(m), where an adversary may later try to substitute a forged document for the honestly chosen m, needs second-preimage resistance: the message is fixed and honest, and the attacker must collide with it. A scheme in which the signer may be dishonest, preparing two contracts with the same digest, signing the benign one and presenting the malicious one, needs full collision resistance, because the adversary then controls both messages. Commitment schemes, Merkle trees, and the Fiat–Shamir transform all fall into this last category and therefore require collision resistance.

3.3 The birthday bound on generic collision finding

The generic collision attack evaluates the hash on many inputs until two digests coincide; the birthday calculation of the Math Guide bounds its cost.

Lemma 3.11 (Birthday bound for hashing).

Let H:{0,1}∗→{0,1}n and N=2n. Evaluate H on q distinct inputs, in the idealised model where the q digests behave as independent uniform samples from {0,1}n, and let C be the event that two digests coincide. Then

Pr⁡[C]= 1−∏i=0q−1(1−iN),

with the two-sided estimate

1−e−q⁢(q−1)/(2⁢N)≤Pr⁡[C]≤q⁢(q−1)2⁢N≤q22⁢N,

and the lower bound gives Pr[C]≥1/2 once q≥1.18N. A collision therefore appears with constant probability after about N=2n/2 evaluations.

Proof.

The exact product and both estimates are the birthday-bound proposition of the Math Guide (§“The union bound and a birthday calculation”), instantiated with set size N=2n and sample count k=q. Only the half-probability threshold is new. Setting the exponent of the lower bound equal to −ln2 gives q(q−1)=2Nln2, i.e.

q≈2⁢ln⁡2⁢N≈ 1.18⁢N,

the constant being 2⁢ln⁡2=1.1774…; for q≥1.18N the exponential falls below 1/2 and Pr[C]≥1/2. □

Remark 3.12 (Reading the birthday bound).

The square-root law. An n-bit digest yields only n/2 bits of collision security in the sense of Definition 1.32. The conventional 128-bit collision security requires n=256; for this reason SHA-256 (there is no “SHA-128”) is the standard digest size, and the transcript hashes of Fiat–Shamir-style protocols must carry at least 256-bit output.

The attack is practical. The direct attack stores all q≈2n/2 digests and sorts them, using 2n/2 memory, the same obstruction that makes baby-step giant-step impractical (Remark 2.12). Collision finding, however, like the discrete-logarithm walk of Proposition 2.13, admits cycle finding: one iterates x↦H(x) and detects the cycle with Floyd’s or Brent’s algorithm, in the manner of Pollard’s rho, or runs the van Oorschot–Wiener parallel collision search across many machines. These methods achieve the same 2n/2 time in essentially constant memory, so parameter choices must meet the birthday cost in practice, not only in theory.

Preimages cost the square. The best generic attack against preimage and second-preimage resistance is brute force: about 2n evaluations to hit a prescribed digest. Those notions therefore have full n-bit generic security, twice the collision level, because the attacker cannot exploit birthday coincidences among self-chosen pairs.

3.4 The random oracle model

This subsection defines the random oracle precisely and proves the two powers stated informally in Remark 1.27; the random oracle model is that of Definition 1.26, one of the two idealisations under which proofs proceed, and a heuristic with the limits of Remark 1.29.

Definition 3.13 (Random oracle).

A random oracle with output length n is a function 𝒪:{0,1}∗→{0,1}n drawn uniformly at random from the set of all such functions. Equivalently—and this is the form every proof uses—the oracle is realised lazily: a table, initially empty, is maintained; on query x, if x is in the table the stored value is returned, and otherwise a fresh 𝒪(x)←${0,1}n is sampled, recorded, and returned.

Access to the oracle is only by querying: it has no description shorter than its (exponentially long) truth table. A scheme is analysed in the random oracle model (ROM) when every party, honest or adversarial, queries a single shared 𝒪 in place of a concrete hash, and security is proved relative to the random choice of 𝒪; on deployment a concrete hash such as SHA-256 or BLAKE2b instantiates the oracle.

Proposition 3.14 (The two powers of the ROM).

In a ROM security proof, the reduction, which simulates 𝒪 for the adversary, gains two capabilities that no concrete hash affords.

  1. 1.

    Observability (extractability). The reduction sees every input the adversary queries. Since querying is the only way to learn anything about 𝒪(x), if the adversary’s output depends on 𝒪(x) then the reduction holds x.

  2. 2.

    Programmability. On a not-yet-queried input x, the reduction may choose the response 𝒪(x) to be any value it selects, provided the value is distributed uniformly; the simulation remains perfect, and the reduction can thereby plant a challenge—a value it must invert, say—inside an oracle answer.

Proof.

Both capabilities are immediate from the lazy realisation of Definition 3.13, because in the simulation the reduction is the table-keeper. Every query arrives at the reduction before an answer exists, which is observability. And on a fresh input the honest table-keeper would sample the answer uniformly and independently of the adversary’s view so far; a reduction that instead inserts any value with that same distribution produces a view identical to the honest one, while the table keeps repeated queries consistent. That is programmability. □

Remark 3.15 (Why Fiat–Shamir needs the ROM).

The Fiat–Shamir transform uses both powers at once. It is the compiler that renders Halo 2’s interactive protocol non-interactive, developed in this volume under “From identification to signature via the Fiat–Shamir transform” and in full generality under “The Fiat–Shamir transform: from interactive to non-interactive”. The transform replaces the verifier’s random challenge e by e=𝒪(transcript so far). Soundness of the resulting non-interactive argument is proved by rewinding: the reduction observes (capability 1) the transcript the prover commits to, then reprograms (capability 2) the oracle to return a fresh independent challenge on that same transcript, extracting two accepting transcripts that share a prefix and, from them, a witness—the forking technique previewed in Remark 1.24. Neither step is available against a concrete hash, whose outputs the reduction can neither observe selectively nor rewrite, so the argument holds only in the ROM.

3.5 Domain separation and personalisation

A deployed protocol uses one hash function for many purposes: it derives keys, commits to notes, tags spent notes, and seeds Fiat–Shamir challenges. Digests are interchangeable bit strings, so an output produced for one purpose can be replayed as another unless domain separation keeps the purposes apart.

Definition 3.16 (Domain separation).

Let H be a hash modelled as a random oracle, and let {τi}i∈I be a set of distinct, prefix-free domain tags (also called labels or personalisation strings), one per intended use: no τi is a prefix of another—as when all tags have equal length, or when each is length-prefixed. The use-i hash is

H(i)⁢(x):=H⁢(τi∥x).
Proposition 3.17 (Domain separation yields independent oracles).

If H is a random oracle and the tags {τi} are prefix-free, then the family {H(i)}i∈I is distributed exactly as a collection of independent random oracles. Consequently a digest obtained from H(i) is—except with the negligible probability of a generic collision—useless against any use j≠i.

Proof.

Prefix-freeness makes the domains τi∥{0,1}∗ pairwise disjoint: a string with prefix τi cannot also have prefix τj unless one tag is a prefix of the other. Inputs queried through different H(i) are therefore never equal. A random oracle assigns independent uniform values to distinct inputs, so restricting H to the disjoint slices yields, per slice, a uniformly random function, independent across slices—precisely a collection of independent random oracles. The replay conclusion follows: the value H(i)(x) reveals nothing about any H(j)(⋅) with j≠i. □

Three idioms implement the technique in deployed practice; Zcash uses all three.

  1. 1.

    Context tagging. An ASCII string naming the use is bound into every call, either prepended, as in Definition 3.16, or in any framing that keeps the tag unambiguously delimited from the data. The Orchard tag inventory is of this kind: the strings z.cash:Orchard-cv, z.cash:Orchard-NoteCommit, and z.cash:Orchard-CommitIvk separate the value commitment, note commitment, and key commitment uses of one group-hash (protocol specification §§ 5.4.8.3–5.4.8.4), and z.cash:Orchard-gd separates diversified key generation (protocol specification § 5.4.1.6). The deployed framing differs from the definition’s: the curve hash of §3.7 appends its domain tag after the message, closed by a byte carrying the tag’s length (protocol specification § 5.4.9.8); the length byte makes the tag self-delimiting, so distinct tags still induce disjoint effective inputs, which is all that the proof of Proposition 3.17 uses. The tags enter that hash in two ways, and the commitment tags in both: -cv and -gd serve directly as its domain tag, while each commitment tag, suffixed -M, is hashed as the message under the fixed domain tag z.cash:SinsemillaQ to derive one of the commitment’s two base points and, suffixed -r, serves directly as the domain tag deriving the other (protocol specification §§ 5.4.1.9 and 5.4.8.4).

  2. 2.

    Native personalisation. BLAKE2b’s parameter block carries a dedicated 16-byte personalisation field that is mixed into the initialisation vector, so distinct personalisations separate the primitive’s effective inputs before a single message byte is processed; this field is the reason Zcash prefers BLAKE2 for its oracles. With BLAKE2b modelled as a random oracle of the pair (personalisation, message), the fixed-length field is a prefix-free tag and Proposition 3.17 makes the resulting domains independent; a concrete BLAKE2b instantiation does not make that independence a fact “by construction”. The deployed personalisations include Zcash_ExpandSeed for key expansion (protocol specification § 5.4.2), Zcash_OrchardKDF for the note-encryption key-derivation function (KDF, the object of §6.6; protocol specification § 5.4.5.6), and Zcash_Orchardock for the outgoing cipher key (protocol specification § 5.4.2)—all exactly 16 bytes.

  3. 3.

    Suffix and framing bits in the SHA-3 family. FIPS 202 reserves domain-separation suffix bits appended to the message before padding: 01 for SHA-3 hashing and 1111 for the SHAKE XOFs. SHA3-256 and SHAKE256 share the same underlying permutation, yet the framed inputs differ, so their effective inputs are disjoint—though their finite digests can still coincide by chance.

An ad hoc tag that is a prefix of another merges two domains without any visible failure and readmits the replay attack, which is why Definition 3.16 demands prefix-freeness rather than mere distinctness. The Merkle trees of the final section apply the same technique within a single structure, tagging tree layers to prevent a forgery that confuses leaves with internal nodes; see “Layer and domain separation” there.

3.6 Hashing to a field element

Commitments over the Pasta curves, Fiat–Shamir challenges, and key derivations hash a message to a field element: a near-uniform element of 𝔽p rather than a bit string. Reducing n uniform bits modulo a prime p is not uniform on 𝔽p, because 2n is not a multiple of p and some residues receive one more preimage than others; the remedy is to hash to a wide output and reduce.

Construction 3.18 (Expand-then-reduce).

Let p be a prime of L=⌈log2p⌉ bits, and fix a XOF, or a domain-separated hash, 𝖾𝗑𝗉𝖺𝗇𝖽, producing arbitrary-length near-uniform output. To map a message m to 𝔽p, with a domain tag τ and a security slack of k bits (commonly k=128):

  1. 1.

    compute b←𝖾𝗑𝗉𝖺𝗇𝖽(τ∥m,L+k), a string of L+k near-uniform bits;

  2. 2.

    interpret b as an integer B∈{0,…,2L+k−1} and output Bmodp∈𝔽p.

Proposition 3.19 (Near-uniformity of expand-then-reduce).

If 𝖾𝗑𝗉𝖺𝗇𝖽 is a random oracle, the output of Construction 3.18 lies within statistical distance (Definition 1.6) at most

p2L+k+1≤ 2−k

of the uniform distribution on 𝔽p. With k=128, no algorithm whatsoever—efficient or not—distinguishes the output from a uniform field element with advantage better than 2−128.

Proof.

The integer B is uniform on {0,…,K−1} with K=2L+k, and the bias of reducing a uniform B modulo p is exactly the situation of the modular-reduction proposition of the Math Guide (§“Uniform sampling and the bias of modular reduction”): each residue’s probability differs from 1/p by at most 1/K, because the preimage counts ⌊K/p⌋ and ⌈K/p⌉ differ by one, and summing over the p residues gives statistical distance at most p/(2K)=p/2L+k+1—the sharper form proved there. Since p<2L, this is less than 2−(k+1)≤2−k. The final claim is the variational characterisation of statistical distance (Proposition 1.7): no decision procedure exceeds the distance. □

The slack is necessary. With k=0, a single L-bit block reduced modulo p, the bias can be a constant: for p slightly above a power of two, K=2L is slightly less than twice p, the residues beyond the wrap-around point receive only one preimage while the rest receive two, and each residue with one preimage has as little as half its uniform probability.

Deployed standards package the construction. The IETF hash-to-curve specification (RFC 9380) defines 𝗁𝖺𝗌𝗁_𝗍𝗈_𝖿𝗂𝖾𝗅𝖽(m,𝑐𝑜𝑢𝑛𝑡), producing 𝑐𝑜𝑢𝑛𝑡 field elements by calling an expansion routine—𝖾𝗑𝗉𝖺𝗇𝖽_𝗆𝖾𝗌𝗌𝖺𝗀𝖾_𝗑𝗆𝖽 over a fixed-output hash, or 𝖾𝗑𝗉𝖺𝗇𝖽_𝗆𝖾𝗌𝗌𝖺𝗀𝖾_𝗑𝗈𝖿 over a XOF—with a mandatory domain-separation tag, and reducing each chunk of

LRFC=⌈(⌈log2⁡p⌉+k)/8⌉⁢bytes

modulo p, where k is the suite’s target security level in bits. The RFC’s own suites for 255-bit fields—the curve25519 family—set k=128, hence 48-byte chunks. The Zcash suite for Pallas and Vesta takes the larger k=256, reducing each element from a full 64-byte BLAKE2b-512 digest, so the slack of Proposition 3.19 is realised with margin (expansion is BLAKE2b in the XMD pattern under the suite tag {tag}-{curve}_XMD:BLAKE2b_SSWU_RO_, and each of the two 64-byte chunks is reduced modulo p; protocol specification § 5.4.9.8). The same procedure maps identities to field elements and produces the field elements that the next subsection maps to a curve. Halo 2’s deployed Fiat–Shamir transcript uses the same wide-output-then-reduce principle: each challenge is the 64-byte digest of a BLAKE2b state personalised with Halo2-Transcript, reduced modulo the field order; the order in which that state absorbs messages and squeezes challenges is fixed by the Halo 2 protocol and treated in a later volume of the series.

3.7 Hashing to a curve point

Commitment generators with discrete logarithms known to no party are derived by a hash onto an elliptic curve, mapping a message to a point of E(𝔽p). The output must be near-uniform in the relevant subgroup, so that the map can stand in for a random oracle into the group in security arguments, and the map must run in constant time, because its input often depends on secret data.

The direct approach, try-and-increment, hashes the message to a candidate x∈𝔽p (Construction 3.18); tests whether g(x)=x3+ax+b is a quadratic residue, so that a y-coordinate exists; and, if not, increments x and retries. It is correct and roughly uniform, but about half of all x fail the residue test, since the squares are half of 𝔽p× (Math Guide, §“Quadratic residues and the Euler criterion”, whose Legendre symbol (g⁢(x)p) is exactly the test); the number of trials depends on the message, and the running time leaks information about m to side-channel attacks. A constant-time map must succeed on the first try, for every input.

Construction 3.20 (Simplified Shallue–van de Woestijne–Ulas map).

Let E:y2=g(x)=x3+ax+b over 𝔽p with ab≠0, and choose, as RFC 9380 requires, a constant Z∈𝔽p such that Z is a nonsquare, Z≠−1, the polynomial g(X)−Z is irreducible over 𝔽p, and g(b/(Za)) is a square. (The RFC selects Z mechanically, as the candidate of smallest absolute value meeting these conditions—a nothing-up-my-sleeve constant with no hidden design freedom.) The map SWU:𝔽p→E(𝔽p) sends u to a point as follows. Compute the two candidate x-coordinates

x1=−ba⁢(1+1Z2⁢u4+Z⁢u2),x2=Z⁢u2⁢x1,

with the fallback x1=b/(Za) when the denominator Z2u4+Zu2 vanishes (as at u=0). Set x=x1 if g(x1) is a square and x=x2 otherwise; let y be a square root of g(x) (Math Guide, §“Square roots modulo a prime”), its sign fixed by a convention—the deployed map matches the parity of y to that of u—and output (x,y).

The construction contains no trial loop, hence runs in constant time; it remains to prove that one of the two candidates always yields a point.

Proposition 3.21 (Correctness of the branch selection).

Under the parameter conditions of Construction 3.20, the map is well-defined for every u∈𝔽p: the selected value g(x) is a square, so SWU(u) is a genuine point of E(𝔽p).

Proof sketch.

Suppose first that D=Z2u4+Zu2≠0. The argument rests on the algebraic identity

g⁢(x2)=Z3⁢u6⁢g⁢(x1),

a polynomial identity in u: substitute x2=Zu2x1 into g and simplify using the formula for x1 (the computation is omitted). If g(x1)=0, the first candidate yields a point, with y=0. Otherwise apply multiplicativity of the Legendre symbol (Math Guide, §“Quadratic residues and the Euler criterion”):

(g⁢(x2)p)=(Z3⁢u6p)⁢(g⁢(x1)p)=(Zp)⁢((Z⁢u3)2p)⁢(g⁢(x1)p)=(Zp)⁢(g⁢(x1)p),

since Z2u6=(Z⁢u3)2 is a nonzero square, contributing +1 (as D≠0 forces u≠0). Because Z is a nonsquare, (Zp)=−1, so the two symbols are opposite and the branch selection picks the square. If D=0, the prescribed fallback has g(x1)=g(b/(Za)), a square by the last condition on Z. Thus every input produces a valid affine point. □

A single SWU evaluation does not suffice: the map is not surjective onto E(𝔽p), and its output is not uniformly distributed on its image. The standardised pipeline repairs both defects.

Construction 3.22 (The hash-to-curve pipeline).

The RFC 9380 map 𝗁𝖺𝗌𝗁_𝗍𝗈_𝖼𝗎𝗋𝗏𝖾:{0,1}∗→E(𝔽p) composes four steps:

  1. 1.

    hash to the field: 𝗁𝖺𝗌𝗁_𝗍𝗈_𝖿𝗂𝖾𝗅𝖽(m,2) produces two independent near-uniform field elements u0,u1 (§3.6);

  2. 2.

    map each through SWU: Q0=SWU(u0), Q1=SWU(u1);

  3. 3.

    sum on the curve: R=Q0+Q1. Summing two independent SWU images provably repairs the non-uniformity: the sum lies within negligible statistical distance of uniform on E(𝔽p), the theorem on which the pipeline’s random-oracle claim rests;

  4. 4.

    clear the cofactor: multiply R by h=#E(𝔽p)/r to land in the prime-order subgroup of order r in which the protocol operates.

The result is a constant-time hash from messages to group elements which, under the hash model and suite conditions of RFC 9380, can instantiate a random oracle into the group. For the Pasta curves the last step is vacuous—their cofactor is 1 (Definition 2.25).

Remark 3.23 (The isogeny required by j-invariant 0).

For the Pasta curves the SWU step cannot be applied directly. The SWU formula for x1 divides by a, and its numerator carries the factor −b: with a=0 the formula is undefined, while b=0 makes x1 identically zero with g(x1)=0, collapsing the map to the constant point (0,0). The construction therefore requires ab≠0—and Pallas and Vesta have a=0 (the j-invariant-0 shape y2=x3+5 of Definition 2.25; curves with b=0, j=1728, are excluded symmetrically). The obstruction is intrinsic, not notational: the j-invariant is an isomorphism invariant, and a Weierstrass change of variables rescales (a,b) to (u4a,u6b) (Math Guide, §“The j-invariant and the GLV endomorphism”), so no model of these curves attains ab≠0. The standardised remedy evaluates simplified SWU on an isogenous auxiliary curve E′:y2=x3+a′x+b′ with a′b′≠0, then transports the result through an isogeny E′→E: a nonconstant map between curves given by polynomial coordinate formulas and respecting the group law. The deployed implementation applies a degree-3 isogeny, and—because an isogeny is a group homomorphism—sums Q0+Q1 on E′ first and transports the single sum (protocol specification § 5.4.9.8). Figure 5 draws the pipeline in this deployed form.

Refer to caption
Figure 5: The hash-to-curve pipeline of Construction 3.22 in the deployed form of Remark 3.23. The message m and the domain tag τ enter 𝗁𝖺𝗌𝗁_𝗍𝗈_𝖿𝗂𝖾𝗅𝖽, which emits the field elements u0 and u1. Simplified SWU (Construction 3.20) maps each to a point of the auxiliary curve E′ (amber rail), on which a′b′≠0, and Q0+Q1 is formed there. The degree-3 isogeny carries the sum to the point R of the Pasta curve E (blue rail), whose a=0 excludes SWU. Cofactor clearing (faded) multiplies by h=1 on the Pasta curves and is skipped.
Construction 3.24 (Nothing-up-my-sleeve generators).

To generate public generators G1,…,Gk of a vector commitment (the Pedersen vector commitment of Construction 4.23 in the next section) so that no one knows any discrete-logarithm relation among them, derive each as

Gi=𝗁𝖺𝗌𝗁⁢_⁢𝗍𝗈⁢_⁢𝖼𝗎𝗋𝗏𝖾⁢(τ∥i)

from a fixed public domain tag τ—often a human-readable protocol name—and the index i. Because the seed is a transparent, auditable string with no hidden parameters, no party could have constructed a backdoor relation in advance. Halo 2 produces the generators of its Pedersen vector and inner-product commitments (the latter Construction 4.39) in exactly this way: every generator Gi is 𝗁𝖺𝗌𝗁_𝗍𝗈_𝖼𝗎𝗋𝗏𝖾("Halo2-Parameters") applied to a five-byte message—a zero byte, then the four-byte little-endian encoding of i—the leading zero keeping the Gi disjoint from the two auxiliary generators the same tag derives from the one-byte messages 1 and 2, and Orchard’s value commitment derives its two bases from the tag z.cash:Orchard-cv with the one-byte messages "v" and "r".

Remark 3.25 (Why NUMS generators are binding-safe).

Knowledge of a discrete-logarithm relation ∑iaiGi=0 with not all ai zero would let a committer open one commitment two ways, violating the binding property that the next section defines and relies on. The NUMS derivation excludes this: the generators are outputs of a function modelled as a random oracle into the group, so they are distributed as independent uniform group elements, and finding a discrete-logarithm relation among independent uniform elements reduces to computing a discrete logarithm on E, hard under the standing assumptions of Remark 2.32; the reduction, which embeds its challenge in every generator, is Theorem 4.24 of the next section. Hence no efficient party, the scheme designer included, can know such a relation.

3.8 Arithmetisation-friendly hashing: Poseidon

SHA-2 and BLAKE2 are bit-oriented: they rearrange and XOR 32- and 64-bit words. In an arithmetic circuit over a large prime field 𝔽p, as in Halo 2, whose cost model (developed in a later volume of the series) prices each field multiplication as a constraint, every Boolean operation of such a hash must be re-expressed through field arithmetic and range checks. An arithmetisation-friendly hash instead builds its round function from a few low-degree field operations, native to the circuit; Orchard employs Poseidon (Grassi, Khovratovich, Rechberger, Roy, and Schofnegger, 2019) through the mode of operation of Construction 3.26.

Construction 3.26 (The sponge construction).

Fix a permutation f:𝔽pt→𝔽pt on a state of t field elements. Split the state into a rate of r elements—the only part input is added into and output is read from—and a capacity of c=t−r elements, never accessed directly, which carries the security margin. To hash, absorb the message into the rate, r elements at a time, applying f between blocks; then squeeze output from the rate, applying f between reads. Collision and preimage resistance hold up to approximately pc work, as for a random sponge: the birthday bound of Lemma 3.11 applied to the pc capacity states the adversary cannot see.

Figure 6 draws the two phases.

Refer to caption
Figure 6: The sponge of Construction 3.26 on a state of t field elements, a rate of r (amber) above a capacity of c=t−r (blue). The absorb phase adds successive r-element blocks of the message m into the rate, with the permutation f between blocks; the squeeze phase reads output from the rate, with f between reads. The capacity is never exposed: no input enters it and no output is read from it, and it changes only inside f. Orchard’s instance has t=3, r=2 and c=1 (Example 3.29).
Construction 3.27 (The Poseidon permutation).

The permutation f is a sequence of rounds, each comprising three steps:

  1. 1.

    add round constants: add a fixed vector in 𝔽pt to the state;

  2. 2.

    S-box: apply x↦xα to state elements, where α≥3 is the smallest integer with gcd(α,p−1)=1, so that the power map is a bijection on 𝔽p; over the Pasta fields α=5, because 3∣p−1 there rules out α=3;

  3. 3.

    mix: multiply the state by a fixed maximum-distance-separable (MDS) matrix M∈𝔽pt×t—one whose every square submatrix is invertible, giving the fastest possible diffusion of any element’s change across the whole state.

The cost-saving principle (the HADES strategy) distinguishes two round types: a few full rounds at the start and end apply the S-box to all t elements, while in the many partial rounds between them the S-box touches a single element—the MDS mix still diffusing it across the state. Round counts are chosen to resist the known algebraic (Gröbner-basis) attacks.

Remark 3.28 (Circuit cost).

Inside a circuit, the only non-linear operation in all of Poseidon is x↦x5, verified by a couple of multiplication gates per S-box; the round-constant additions and the MDS multiplication are linear and add almost no cost. A 2-to-1 Poseidon hash costs a few hundred constraints, against tens of thousands for a bit-oriented hash; this difference determines whether such a circuit is practical.

Example 3.29 (The Orchard Poseidon instance).

Orchard fixes t=3 (rate 2, capacity 1), α=5, and 8 full plus 56 partial rounds, over the Pallas base field, at the 128-bit security level (protocol specification § 5.4.1.10). It is used in constant-input-length mode as a two-input hash:

𝖯𝗈𝗌𝖾𝗂𝖽𝗈𝗇𝖧𝖺𝗌𝗁⁢(x,y)=f⁢([x,y, 265])0,

the first component of the state after a single permutation of the input padded by the fixed capacity value 265=2⋅264, which encodes the input length 2 into the capacity so that no message padding is required (an input of any other constant length is encoded the same way, with that length in place of the factor 2). Keyed by its first argument, this hash serves as the pseudorandom function

F𝗇𝗄⁢(ρ)=𝖯𝗈𝗌𝖾𝗂𝖽𝗈𝗇𝖧𝖺𝗌𝗁⁢(𝗇𝗄,ρ)

—the PRF notion is defined in “Pseudorandom functions and permutations” later in this volume—deployed as 𝖯𝖱𝖥𝗇𝖿𝖮𝗋𝖼𝗁𝖺𝗋𝖽 (protocol specification § 5.4.2), from which Orchard constructs the nullifier—a construction developed in a later volume of the series; this volume supplies only the PRF. Unlike the Pedersen and Sinsemilla hashes constructed in the next section, whose collision resistance reduces to a standard assumption (discrete log), Poseidon’s security rests on cryptanalytic confidence in its round function: the same epistemic footing as SHA-256, not a reduction.

3.9 The transparent layer’s hashes

Where the Orchard shielded protocol hashes with BLAKE2b, Sinsemilla, and Poseidon, the transparent layer, inherited from Bitcoin, hashes with SHA-256 and two functions derived from it, none requiring results beyond §3.2 and the birthday bound of §3.3. This register fixes their names, domains, and deployed uses for the volumes above.

  • •

    RIPEMD-160. A 160-bit iterated (Merkle–Damgård, the construction of §5.3) hash, {0,1}∗→{0,1}160, older than Bitcoin and inherited with its address format, whose collision resistance is limited to the 80-bit birthday bound of Lemma 3.11. Zcash uses it only inside 𝗁𝖺𝗌𝗁𝟣𝟨𝟢 below and the script opcodes OP_RIPEMD160 and OP_HASH160.

  • •

    The address hash 𝗁𝖺𝗌𝗁𝟣𝟨𝟢:=RIPEMD160∘SHA256. A pay-to-public-key-hash (P2PKH) address carries the 20-byte 𝗁𝖺𝗌𝗁𝟣𝟨𝟢 of the 33-byte compressed encoding of an ECDSA public key (the scheme is registered in §8.10), and a pay-to-script-hash (P2SH) address the 𝗁𝖺𝗌𝗁𝟣𝟨𝟢 of a redeem script, the spending condition the spender later reveals and satisfies (protocol specification § 5.6.1.1). The P2PKH output script—the condition a spend of the output must satisfy—is OP_DUP OP_HASH160 ⟨h⟩ OP_EQUALVERIFY OP_CHECKSIG, which recomputes the hash from the public key the spender reveals; wallets compute it through the zcash_transparent crate, and a partially created transaction (PCZT), the multi-party construction format treated in a later volume of the series, carries on each transparent input preimage maps keyed by RIPEMD-160, SHA-256, 𝗁𝖺𝗌𝗁𝟣𝟨𝟢, and 𝗁𝖺𝗌𝗁𝟤𝟧𝟨 digests.

  • •

    Double SHA-256 (SHA-256d, or 𝗁𝖺𝗌𝗁𝟤𝟧𝟨). The composition x↦SHA256(SHA256(x)) (protocol specification § 5.4.1.1), whose outer application also closes the length-extension property of plain SHA-256 (§5.3). It hashes block headers; its leading four bytes are the checksum that Base58Check, the string encoding of transparent addresses, appends to the raw address bytes before converting to base 58 (protocol specification § 5.6.1.1) and the payload checksum in every peer-to-peer message header; and it is the legacy transaction identifier: the txid of a version-4-or-earlier transaction is SHA-256d of its serialisation (protocol specification § 7.1.1), whereas a version-5 txid is the BLAKE2b digest tree of ZIP 244.