The adversary of this section forges by coincidence. She prepares two contracts—one benign, one ruinous—whose digests agree, has the benign one signed, and produces the ruinous one in court; or she takes a digest minted for one purpose, say a key-derivation output, and replays it in another role, say a commitment, exploiting the fact that both are interchangeable bit strings; or she simply walks a pseudo-random path through the digest space until, square-root-of-the-space steps later, two inputs collide. Denying her these coincidences is the business of the hash function: a function compressing arbitrary data into a short fixed-length tag. It underlies 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—so many purposes for one primitive because an ideal hash acts like a deterministic source of fresh randomness keyed by its input. This section builds the primitive from the ground up: its syntax; the three classical security notions and the generic birthday attack that bounds them; the random oracle model; domain separation; hashing into a finite field and onto an elliptic curve; the arithmetisation-friendly hash Poseidon that Orchard evaluates inside its circuit; and finally a register of the transparent layer’s SHA-256-derived hashes.
Notation for strings is fixed once. 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 is a function
Elements of the codomain are called digests, hashes, or tags. The function is compressing on a domain if contains strings longer than ; when the domain is all of , the function is overwhelmingly many-to-one.
A single fixed function such as SHA-256 is what practice deploys, but a foundational wrinkle appears the moment one tries to say what its security means. For any fixed compressing there exist inputs with —the pigeonhole principle guarantees it—and therefore a tiny program that simply outputs one such hardcoded pair also exists. The asymptotic statement “no efficient adversary finds a collision” is consequently false for every fixed compressing function: the hardcoding program is efficient and always succeeds. (Writing that program down is another matter—nobody knows a collision for SHA-256—but existence suffices to falsify the universally quantified claim.) The standard remedy indexes the function by a key.
A keyed hash family (or hash function ensemble) is a function
where is a finite key space. A key is sampled publicly at random, fixed, and we write for the family member in force.
The key is not secret. Its role is to index which member of the family the adversary must attack: a hardcoded collision for one member is useless against a freshly sampled other, so “no efficient adversary finds a collision for a random member” is a meaningful asymptotic statement.
The convention of this volume follows the standard resolution of the mismatch between theory and practice. Security notions are stated for the keyed family, where the definitions are clean; every concrete construction we deploy is unkeyed; and the key is mentally identified with “the choice of standard”—the sampling of happened, once and in public, when the function was designed. No formal theorem bridges the two readings; the gap is the same one the random oracle model of §3.4 inhabits, and we flag it rather than hide it.
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 string is a prefix of , so a longer request extends a shorter one as a stream.
The canonical XOFs are SHAKE128 and SHAKE256 from the SHA-3 family. An XOF is the natural tool wherever a controlled number of uniform bits is needed rather than a fixed digest—above all when hashing into a finite field or onto a curve, where the output must be reduced modulo a prime; §3.6 returns to this.
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 . All sizes are functions of : the output length , the key length, and a polynomially bounded challenge input length from which the games sample their random challenge . Recall that a function is negligible, , if it decays faster than the reciprocal of every polynomial (Math Guide, §“Polynomial, exponential, and negligible functions”; recalled in §1.2). The three notions form a strict hierarchy, and no single definition of a “good” hash exists; which notion an application needs is a per-application question that Remark 3.10 takes up.
The game runs as follows.
The challenger samples and , computes , and sends to the adversary.
The adversary outputs .
The game outputs iff .
The family is preimage resistant (or one-way) if for every PPT ,
Note the winning condition: the adversary, given the key and the digest of a random message, must output any string hashing to . Recovering the original is not required; any preimage wins.
The game runs as follows.
The challenger samples and , and sends to the adversary.
The adversary outputs .
The game outputs iff and .
The family is second-preimage resistant if for every PPT ,
Here the challenger gives the adversary a specific random message; the adversary must produce a different message colliding with it.
The game runs as follows.
The challenger samples and sends to the adversary.
The adversary outputs a pair .
The game outputs iff and .
The family is collision resistant if for every PPT ,
The three games differ in who chooses what. In the preimage game the challenger chooses the message and reveals only its digest; in the second-preimage game the challenger chooses the message and reveals it; in the collision game the adversary chooses both messages and need only make them collide. More adversarial choice means an easier game and hence a stronger security demand on the function; collision resistance, granting the most choice, is the strongest of the three.
Let be a keyed hash family that is compressing, with challenge input length . Then:
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 itself, runs —the simulated view is exactly that of , since samples from the same distribution as the challenger—and outputs the pair . Whenever succeeds, and , which is precisely a collision. Hence : the reduction is tight, and if the left side is negligible so is the right.
(2) Toward the contrapositive, let be an inverter; we build a second-preimage finder . On input , the reduction computes , runs —again a perfect simulation of , since is uniform and is its digest—and outputs . Whenever succeeds, ; what remains is to argue with good probability. Fix ’s coins, so that its output on each digest is a single string . An input can satisfy only if is the output assigned to its own digest, so each of the digests contributes at most one such input, and at most inputs in all are “fixed points” of the composed map. Over uniform , therefore, ; averaging over ’s coins preserves the bound. Hence
The loss is additive, not multiplicative: nothing bounds conditioned on success, because ’s successes might concentrate on small fibres where returning itself is likely. Sufficient compression, , makes negligible and the implication unconditional.
Non-reversal is witnessed by Example 3.9 below. □
Take any one-way family and define , where deletes the last bit of . The family inherits one-wayness: a preimage challenge for is distributed exactly as one for at one bit greater challenge length, and an -inverter’s output satisfies , so deleting its last bit hands the reduction a preimage under . Yet the pair , is an immediate collision for every , 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 genuinely one-directional.
Password storage—keeping a digest of each password so that a stolen table does not reveal them—is the natural home of preimage resistance: the thief holds digests, and any preimage lets her log in. (The notion alone is not the whole story there: passwords are guessable, so deployments hash each together with a unique random string, its salt, through a deliberately slow function, against 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 herself may cheat—preparing two contracts with the same digest, signing the benign one, presenting the malicious one—needs full collision resistance, because there the adversary controls both messages. Commitment schemes, Merkle trees, and the Fiat–Shamir transform all fall into this last category, which is why collision resistance is the headline property of a cryptographic hash.
How hard can collision finding be? The generic attack—evaluate the hash on many inputs and wait for a coincidence—succeeds far sooner than intuition suggests, and its cost is governed by the birthday calculation of the Math Guide.
Let and . Evaluate on distinct inputs, in the idealised model where the digests behave as independent uniform samples from , and let be the event that two digests coincide. Then
with the two-sided estimate
and the lower bound gives once . A collision therefore appears with constant probability after about evaluations.
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 and sample count ; we do not re-derive them. Only the half-probability threshold is new. Setting the exponent of the lower bound equal to gives , i.e.
the constant being ; for the exponential falls below and . □
Three consequences deserve emphasis.
The square-root law. An -bit digest yields only bits of collision security in the sense of Definition 1.32. For the conventional -bit collision security one must take —which is why SHA-256 (and not “SHA-128”, which does not exist) is the workhorse digest size, and why the transcript hashes of Fiat–Shamir-style protocols must carry at least -bit output.
The attack is practical. The naive attack stores all digests and sorts— memory, the same obstruction that made baby-step giant-step unrealistic in Remark 2.12. But collision finding, like the discrete-logarithm walk of Proposition 2.13, admits cycle finding: iterate and detect the cycle with Floyd’s or Brent’s algorithm, in the manner of Pollard’s rho, or run the van Oorschot–Wiener parallel collision search across many machines. These achieve the same time in essentially constant memory, so the birthday attack is a genuine budget item, not a thought experiment.
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 enjoy full -bit generic security—twice the collision level—because the attacker cannot exploit birthday coincidences among self-chosen pairs; the collision game is the only one that pays the square-root discount.
The model section introduced the random oracle model as one of the two idealisations under which proofs proceed (Definition 1.26), stated its two powers informally (Remark 1.27), and fixed its status as a heuristic with known limits (Remark 1.29). With hash syntax now in hand we can define the idealised object precisely and prove the powers.
A random oracle with output length is a function 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 , if is in the table the stored value is returned, and otherwise a fresh is sampled, recorded, and returned.
Three features characterise the object: outputs on distinct inputs are independent and uniform; outputs on repeated inputs are consistent; and access is only by querying—the oracle has no description shorter than its (exponentially long) truth table. A scheme lives in the random oracle model (ROM) when every party, honest or adversarial, interacts with a single shared in place of a concrete hash, and security is proved relative to the random choice of ; on deployment a concrete hash—SHA-256, say, 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 of its liking, 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 paradigmatic consumer of both powers at once is the Fiat–Shamir transform—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 . 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. This is the proof that lives only in the ROM, and the reason the model is indispensable to the cryptography this monograph targets.
One physical hash serves many purposes in a deployed protocol: it derives keys, commits to notes, tags spent notes, seeds Fiat–Shamir challenges. Digests, however, are interchangeable bit strings, and an output produced for one purpose can be replayed as another unless the purposes are cryptographically insulated. Domain separation is the discipline that insulates them.
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 with . □
Three idioms implement the discipline in deployed practice; Zcash uses all three.
Context tagging. Bind an ASCII string naming the use into every call—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 mirrors the definition’s rather than copying it: 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—all the proof of Proposition 3.17 uses. The tags reach that hash by two routes, and the commitment tags by 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—the field for which Zcash favours 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.
The unifying requirement behind all three idioms is that distinct uses induce disjoint effective inputs to the underlying primitive. An ad hoc tag that happens to be a prefix of another silently merges two domains and reopens 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 discipline within a single structure, tagging tree layers to foreclose a forgery that confuses leaves with internal nodes; see “Layer and domain separation” there.
The primitives ahead—commitments over the Pasta curves, Fiat–Shamir challenges, key derivations—repeatedly need to hash a message to a field element: a near-uniform element of rather than a bit string. The obstacle is arithmetic: a hash emits uniform bits, and reducing uniform bits modulo a prime is not uniform on , because is not a multiple of —some residues receive one more preimage than others. The remedy is to hash wide and reduce.
Let be a prime of bits, and fix a XOF, or a domain-separated hash, , producing arbitrary-length near-uniform output. To map a message to , with a domain tag and a security slack of bits (commonly ):
compute , a string of near-uniform bits;
interpret as an integer and output .
The integer is uniform on with , and the bias of reducing a uniform modulo 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 by at most , because the preimage counts and differ by one, and summing over the residues gives statistical distance at most —the sharper form proved there. Since , this is less than . The final claim is the variational characterisation of statistical distance (Proposition 1.7): no decision procedure exceeds the distance. □
The slack is not optional. With —a single -bit block reduced modulo —the bias can be macroscopic: for just above a power of two, is barely twice , the residues beyond the wrap-around point receive only one preimage while the rest receive two, and each deprived residue carries as little as half its uniform mass. The extra bits are exactly what drives this imbalance to negligibility.
Deployed practice packages 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 , hence -byte chunks. The Zcash suite for Pallas and Vesta is more generous: it takes , reducing each element from a full -byte BLAKE2b-512 digest, so the slack of Proposition 3.19 is realised with room to spare (the hash_to_field routine expands with BLAKE2b in the XMD pattern under the suite tag {tag}-{curve}_XMD:BLAKE2b_SSWU_RO_ and reduces two -byte chunks each via from_uniform_bytes; protocol specification § 5.4.9.8). This is the concrete recipe for mapping identities to field elements, and for producing the field elements that the next subsection feeds to a curve. Halo 2’s deployed Fiat–Shamir transcript uses the same wide-output-then-reduce principle: each challenge is the -byte digest of a BLAKE2b state personalised with Halo2-Transcript, reduced by from_uniform_bytes; the order in which that state absorbs messages and squeezes challenges is the Halo 2 Guide’s, §“The complete Halo 2 protocol”.
The volume ahead also needs to hash onto an elliptic curve: given a message, produce a point of that behaves like a uniform group element—the raw material for commitment generators whose discrete logarithms nobody knows. Two requirements pull against each other. The output should 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 is often secret-adjacent.
The naive approach fails the second requirement instructively. Hash the message to a candidate (Construction 3.18); test whether is a quadratic residue, so that a -coordinate exists; if not, increment and retry. This try-and-increment loop is correct and roughly uniform, but the number of trials depends on the message: about half of all fail the residue test, since the squares are half of (Math Guide, §“Quadratic residues and the Euler criterion”, whose Legendre symbol is exactly the test), so the running time leaks information about —an avenue for side-channel attacks. Constant-time hashing to a curve requires a map that succeeds on the first try, for every input.
Let over with , and choose, as RFC 9380 requires, a constant such that is a nonsquare, , the polynomial is irreducible over , and is a square. (The RFC selects mechanically, as the candidate of smallest absolute value meeting these conditions—a nothing-up-my-sleeve constant with no hidden design freedom.) The map sends to a point as follows. Compute the two candidate -coordinates
with the fallback when the denominator vanishes (as at ). Set if is a square and otherwise; let be a square root of (Math Guide, §“Square roots modulo a prime”), its sign fixed by a convention—the deployed map matches the parity of to that of —and output .
The construction contains no trial loop, hence runs in constant time; what needs proof is that one of the two candidates always works.
Under the parameter conditions of Construction 3.20, the map is well-defined for every : the selected value is a square, so is a genuine point of .
Suppose first that . The key algebraic identity is
a polynomial identity in : substitute into and simplify using the formula for (we take the computation as given). If , the first candidate already works, with . Otherwise apply multiplicativity of the Legendre symbol (Math Guide, §“Quadratic residues and the Euler criterion”):
since is a nonzero square, contributing (note that forces ). Because is a nonsquare, , so the two symbols are opposite and the branch selection picks the square. If , the prescribed fallback has , a square by the last condition on . Thus every input produces a valid affine point. □
A single SWU evaluation is not the end of the pipeline: the map is not surjective onto , and its image is not uniformly covered—it reaches only part of the curve, with a lumpy distribution. The standardised pipeline repairs both defects.
The RFC 9380 map composes four steps:
hash to the field: produces two independent near-uniform field elements (§3.6);
map each through SWU: , ;
sum on the curve: . Summing two independent SWU images provably repairs the lumpiness: the sum lies within negligible statistical distance of uniform on , the theorem on which the pipeline’s random-oracle claim rests;
clear the cofactor: multiply by to land in the prime-order subgroup of order where the cryptography occurs.
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 one step needs a detour. The SWU formula for divides by , and its numerator carries the factor : with the formula is undefined, while makes identically zero with , collapsing the map to the constant point . The construction therefore requires —and Pallas and Vesta have (the -invariant- shape of Definition 2.25; curves with , , are excluded symmetrically). The obstruction is intrinsic, not notational: the -invariant is an isomorphism invariant, and a Weierstrass change of variables rescales to (Math Guide, §“The -invariant and the GLV endomorphism”), so no model of these curves attains . The standardised remedy evaluates simplified SWU on an isogenous auxiliary curve with , then transports the result through an isogeny : a nonconstant map between curves given by polynomial coordinate formulas and respecting the group law. The deployed implementation applies a degree- isogeny, and—because an isogeny is a group homomorphism—sums on first and transports the single sum (protocol specification § 5.4.9.8).
The culminating application ties together collision resistance, the random-oracle idealisation, and hashing to a curve.
To generate public generators of a vector commitment (the Pedersen vector commitment of Construction 4.22 in the next section) so that no one knows any discrete-logarithm relation among them, derive each as
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 engineered a backdoor relation in advance. This is exactly how Halo 2 produces the generators of its Pedersen vector and inner-product commitments (the latter Construction 4.38): 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 with not all zero would let a committer open one commitment two ways, destroying the binding property that the next section defines and relies on. The NUMS derivation forecloses 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 , hard under the standing assumptions of Remark 2.32; the reduction, which embeds its challenge in every generator, is Theorem 4.23 of the next section. Hence no efficient party, the scheme designer included, can know such a relation.
The hashes of this section so far are bit-oriented: SHA-2 and BLAKE2 shuffle and XOR - and -bit words. Inside an arithmetic circuit over a large prime field —the setting of proof systems such as Halo 2, whose cost model, developed in the Halo 2 Guide, §“From computation to a grid of constraints”, prices each field multiplication as a constraint—such a hash is prohibitively expensive: every Boolean operation must be re-expressed through field arithmetic and range checks, and the tens of thousands of resulting constraints dominate the circuit. Arithmetisation-friendly hashes invert the design: the round function is a handful of low-degree field operations, native to the circuit, incurring few constraints. Poseidon (Grassi, Khovratovich, Rechberger, Roy, and Schofnegger, 2019) is the instance Orchard employs, and it arrives via a mode of operation worth defining in general.
Fix a permutation on a state of field elements. Split the state into a rate of elements—the only part input is added into and output is read from—and a capacity of elements, never accessed directly: the security reserve. To hash, absorb the message into the rate, elements at a time, applying between blocks; then squeeze output from the rate, applying between reads. Collision and preimage resistance hold up to approximately work, as for a random sponge: the birthday bound of Lemma 3.11 applied to the capacity states the adversary cannot see.
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 to state elements, where is the smallest integer with , so that the power map is a bijection on ; over the Pasta fields , because there rules out ;
mix: multiply the state by a fixed maximum-distance-separable (MDS) matrix —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 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 stand against the known algebraic (Gröbner-basis) attacks.
Inside a circuit, the only non-linear operation in all of Poseidon is , verified by a couple of multiplication gates per S-box; the round-constant additions and the MDS multiplication are linear and almost free. A -to- Poseidon hash costs a few hundred constraints, against tens of thousands for a bit-oriented hash—the difference between a practical circuit and an impractical one.
Orchard fixes (rate , capacity ), , and full plus partial rounds, over the Pallas base field, at the -bit security level—the parametrisation named P128Pow5T3 in the deployed source (protocol specification § 5.4.1.10). It is used in constant-input-length mode as a two-input hash:
the first component of the state after a single permutation of the input padded by the fixed capacity value , which encodes the input length into the capacity so that no message padding is required (the ConstantLength domain sets the initial capacity element to ). Keyed by its first argument, this hash serves as the pseudorandom function
—the PRF vocabulary is owned by “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 the Ironwood Guide, §“The nullifier”; this volume supplies only the PRF. One contrast deserves note: unlike the Pedersen and Sinsemilla hashes constructed in the next section, whose collision resistance reduces to a clean assumption (discrete log), Poseidon’s security rests on cryptanalytic confidence in its round function—the same epistemic footing as SHA-256, not the same as a reduction.
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 needing machinery beyond §3.2 and the birthday bound of §3.3; this register fixes their names, domains, and deployed uses for the volumes above.
The address hash . A pay-to-public-key-hash (P2PKH) address carries the -byte of the -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 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 of the Wallet Guide, §“Partially created transactions (PCZT)”, carries on each transparent input preimage maps keyed by RIPEMD-160, SHA-256, , and digests.
Double SHA-256 (SHA-256d, or ). The composition (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.
The toolbox now holds its first primitive in full: a hash with three calibrated security notions, an idealisation that licenses proofs, a discipline that insulates its many uses, and maps carrying its output into fields, onto curves, and inside circuits. The next section spends this capital immediately: commitments—the sealed envelopes of the protocol—are built from exactly the hashes, generators, and hardness assumptions now on the table.