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.
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 .
A hash function with output length
| H : { 0, 1 } ∗ ⟶ { 0, 1 } n . |
Elements of the codomain are called digests, hashes, or
tags. The function is compressing on a domain
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
A keyed hash family (or hash function ensemble) is a function
| H : K × { 0, 1 } ∗ ⟶ { 0, 1 } n, |
where K is a finite key space. A key
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.
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.
An extendable-output function (XOF) is a primitive producing a digest of caller-chosen length: syntactically a function
| H : { 0, 1 } ∗ × N ⟶ { 0, 1 } ∗, | H (x, l) | = l, |
whose outputs are prefix-consistent: for
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.
Each of the three classical security notions is a game between a
challenger and a PPT adversary A , 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
The game PRE H A (λ) runs as follows.
The challenger samples
The adversary outputs
The game outputs 1 iff
The family H is preimage resistant (or one-way) if for every PPT A ,
| Adv H pre (A, λ) := Pr [PRE H A (λ) = 1] ∈ negl (λ) . |
Any preimage of y wins; the adversary need not recover the original x .
The game SEC H A (λ) runs as follows.
The challenger samples
The adversary outputs
The game outputs 1 iff
The family H is second-preimage resistant if for every PPT A ,
| Adv H sec (A, λ) := Pr [SEC H A (λ) = 1] ∈ negl (λ) . |
The game COL H A (λ) runs as follows.
The challenger samples
The adversary outputs a pair (x, x ′) .
The game outputs 1 iff
The family H is collision resistant if for every PPT A ,
| Adv H col (A, λ) := Pr [COL H A (λ) = 1] ∈ negl (λ) . |
The three notions are ordered by the following proposition.
Let H be a keyed hash family that is compressing, with challenge
input length
collision resistance implies second-preimage resistance, with no loss; and
second-preimage resistance implies preimage resistance up to an
additive loss of 2 n − m , which is negligible—so the
implication holds outright—whenever H is sufficiently
compressing,
Neither implication reverses in general.
(1) From an adversary A against second-preimage
resistance, construct B against collision resistance: on
input the key s , the reduction B samples
(2) Towards the contrapositive, let A be an inverter; we
build a second-preimage finder B . On input (s, x) ,
the reduction computes
| Adv H sec (B, λ) ≥ Adv H pre (A, λ) − 2 n − m . |
The loss is additive, not multiplicative: nothing bounds
Non-reversal is witnessed by Example 3.9 below. □
Take any one-way family H and define
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.
The generic collision attack evaluates the hash on many inputs until two digests coincide; the birthday calculation of the Math Guide bounds its cost.
Let
| Pr [C] = 1 − ∏ i = 0 q − 1 (1 − i N), |
with the two-sided estimate
| 1 − e − q (q − 1) / (2 N) ≤ Pr [C] ≤ q (q − 1) 2 N ≤ q 2 2 N, |
and the lower bound gives
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
| q ≈ 2 ln 2 N ≈ 1.18 N, |
the constant being
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
The attack is practical. The direct attack stores all
Preimages cost the square. The best generic attack against preimage and second-preimage resistance is brute force: about 2 n 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.
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.
A random oracle with output length n is a function
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 O in place of a concrete hash, and security is proved relative to the random choice of O ; on deployment a concrete hash such as SHA-256 or BLAKE2b instantiates the oracle.
In a ROM security proof, the reduction, which simulates O for the adversary, gains two capabilities that no concrete hash affords.
Observability (extractability). The reduction sees every input the adversary queries. Since querying is the only way to learn anything about O (x) , if the adversary’s output depends on O (x) then the reduction holds x .
Programmability. On a not-yet-queried input x , the reduction may choose the response O (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.
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. □
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
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.
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) . |
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
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
Three idioms implement the technique in deployed practice; Zcash uses all three.
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).
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.
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.
Commitments over the Pasta curves, Fiat–Shamir challenges, and key derivations hash a message to a field element: a near-uniform element of F p rather than a bit string. Reducing n uniform bits modulo a prime p is not uniform on F p , because 2 n 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.
Let p be a prime of
compute
interpret b as an integer
If expand is a random oracle, the output of Construction 3.18 lies within statistical distance (Definition 1.6) at most
| p 2 L + k + 1 ≤ 2 − k |
of the uniform distribution on F p . With
The integer B is uniform on
The slack is necessary. With
Deployed standards package the construction. The IETF hash-to-curve specification (RFC 9380) defines hash _ to _ field (m, count) , producing count field elements by calling an expansion routine— expand _ message _ xmd over a fixed-output hash, or expand _ message _ xof over a XOF—with a mandatory domain-separation tag, and reducing each chunk of
| L RFC = ⌈ (⌈ log 2 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
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 (F 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
Let
| x 1 = − b a (1 + 1 Z 2 u 4 + Z u 2), x 2 = Z u 2 x 1, |
with the fallback
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.
Under the parameter conditions of Construction 3.20,
the map is well-defined for every
Suppose first that
| g (x 2) = Z 3 u 6 g (x 1), |
a polynomial identity in u : substitute
| (g (x 2) p) = (Z 3 u 6 p) (g (x 1) p) = (Z p) ((Z u 3) 2 p) (g (x 1) p) = (Z p) (g (x 1) p), |
since
A single SWU evaluation does not suffice: the map is not surjective onto E (F p) , and its output is not uniformly distributed on its image. The standardised pipeline repairs both defects.
The RFC 9380 map
hash to the field: hash _ to _ field (m, 2) produces
two independent near-uniform field elements
map each through SWU:
sum on the curve:
clear the cofactor: multiply R by
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).
For the Pasta curves the SWU step cannot be applied directly. The
SWU formula for
x 1 divides by a , and its numerator carries the factor
− b : with
To generate public generators
| G i = hash _ to _ curve (τ ∥ 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 G i is hash _ to _ curve ("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 G i 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".
Knowledge of a discrete-logarithm relation
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 F 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.
Fix a permutation
Figure 6 draws the two phases.
The permutation f is a sequence of rounds, each comprising three steps:
add round constants: add a fixed vector in F p t to the state;
S-box: apply
mix: multiply the state by a fixed
maximum-distance-separable (MDS) matrix
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.
Inside a circuit, the only non-linear operation in all of Poseidon is
Orchard fixes
| PoseidonHash (x, y) = f ([x, y, 2 65]) 0, |
the first component of the state after a single permutation of the
input padded by the fixed capacity value
| F nk (ρ) = PoseidonHash (nk, ρ) |
—the PRF notion is defined in “Pseudorandom functions and permutations” later in this volume—deployed as PRF nfOrchard (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.
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,
The address hash
Double SHA-256 (SHA-256d, or hash256 ). The
composition