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 ; the strings of length exactly form ; the length of a string is ; and concatenation is written .
A hash function with output length
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 there
exist inputs
A keyed hash family (or hash function ensemble) is a function
where 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 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
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 , in the template of
Definition 1.15; the keyed family 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 runs as follows.
The challenger samples
The adversary outputs
The game outputs iff
The family is preimage resistant (or one-way) if for every PPT ,
Any preimage of wins; the adversary need not recover the original .
The game runs as follows.
The challenger samples
The adversary outputs
The game outputs iff
The family is second-preimage resistant if for every PPT ,
The game runs as follows.
The challenger samples
The adversary outputs a pair .
The game outputs iff
The family is collision resistant if for every PPT ,
The three notions are ordered by the following proposition.
Let 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 , which is negligible—so the
implication holds outright—whenever is sufficiently
compressing,
Neither implication reverses in general.
(1) From an adversary against second-preimage
resistance, construct against collision resistance: on
input the key , the reduction samples
(2) Towards the contrapositive, let be an inverter; we
build a second-preimage finder . On input ,
the reduction computes
The loss is additive, not multiplicative: nothing bounds
Non-reversal is witnessed by Example 3.9 below. □
Take any one-way family 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 , where an adversary may later try to substitute a forged document for the honestly chosen , 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
with the two-sided estimate
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
the constant being
The square-root law. An -bit digest yields only
bits of collision security in the sense of
Definition 1.32. The conventional -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 evaluations to hit a prescribed digest. Those notions therefore have full -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 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 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.
In a ROM security proof, the reduction, which simulates 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 , if the adversary’s output depends on then the reduction holds .
Programmability. On a not-yet-queried input , the reduction may choose the response 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 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 be a hash modelled as a random oracle, and let be a set of distinct, prefix-free domain tags (also called labels or personalisation strings), one per intended use: no is a prefix of another—as when all tags have equal length, or when each is length-prefixed. The use- hash is
If is a random oracle and the tags are
prefix-free, then the family is distributed
exactly as a collection of independent random oracles.
Consequently a digest obtained from is—except with the
negligible probability of a generic collision—useless against any
use
Prefix-freeness makes the domains
pairwise disjoint: a string with prefix cannot also have
prefix unless one tag is a prefix of the other. Inputs
queried through different are therefore never equal. A
random oracle assigns independent uniform values to distinct inputs,
so restricting 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 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 -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 bytes.
Suffix and framing bits in the SHA-3 family. FIPS 202 reserves domain-separation suffix bits appended to the message before padding: for SHA-3 hashing and 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 rather than a bit string. Reducing uniform bits modulo a prime is not uniform on , because is not a multiple of and some residues receive one more preimage than others; the remedy is to hash to a wide output and reduce.
Let be a prime of
compute
interpret as an integer
The integer is uniform on
The slack is necessary. With
Deployed standards package the construction. The IETF hash-to-curve specification (RFC 9380) defines , 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
modulo , where is the suite’s target security level in
bits. The RFC’s own suites for -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 . 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
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
a polynomial identity in : substitute
since
A single SWU evaluation does not suffice: the map is not surjective onto , and its output is not uniformly distributed on its image. The standardised pipeline repairs both defects.
The RFC 9380 map
hash to the field: produces
two independent near-uniform field elements
map each through SWU:
sum on the curve:
clear the cofactor: multiply 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 (Definition 2.25).
For the Pasta curves the SWU step cannot be applied directly. The
SWU formula for
divides by , and its numerator carries the factor
: with
To generate public generators
from a fixed public domain tag —often a human-readable protocol name—and the index . 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 is applied to a five-byte message—a zero byte, then the four-byte little-endian encoding of —the leading zero keeping the disjoint from the two auxiliary generators the same tag derives from the one-byte messages and , 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 - and -bit words. In an arithmetic circuit over a large prime field , 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 is a sequence of rounds, each comprising three steps:
add round constants: add a fixed vector in 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 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
the first component of the state after a single permutation of the
input padded by the fixed capacity value
—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.
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 -bit iterated (Merkle–Damgård,
the construction of §5.3) hash,
The address hash
Double SHA-256 (SHA-256d, or ). The
composition