The Zcash ArboretumThe Complete Arboretum PDF

6 Symmetric encryption, AEAD, and key derivation

The adversary of this section owns the channel. Every ciphertext passes through her hands, and she attacks on two fronts at once. As an eavesdropper she tries to distinguish: to tell an encryption of one note plaintext from an encryption of another, or to recognise that two ciphertexts hide the same message. As a forger she tries to modify: a stream cipher’s ciphertext is XOR-malleable, so flipping a ciphertext bit flips the corresponding plaintext bit without any key material at all; she can also shift bytes between a packet’s public header and its encrypted body, replay a ciphertext under a different context, or manufacture a wholly new ciphertext that the receiver accepts. She is patient enough to exploit a single reused pad—two ciphertexts under one pad hand her the XOR of the plaintexts—and mathematically literate enough to exploit a key that is merely high-entropy rather than uniform. This section arms the honest parties against all of it, one guarantee at a time: confidentiality from the one-time pad through the nonce-based stream cipher ChaCha20 and the chosen-plaintext game; integrity from message authentication codes through universal hashing and Carter–Wegman; their composition as authenticated encryption with associated data, culminating in the ChaCha20-Poly1305 scheme that Zcash’s note-encryption layer deploys; and finally key derivation, the manufacture of the uniform key that every theorem in between takes as its hypothesis.

Throughout, an adversary is a probabilistic algorithm 𝒜; the notation y←𝒜⁢(x) denotes running 𝒜 on input x and assigning its output to y, and x←$S denotes sampling x uniformly from the finite set S. Every adversary in the computational definitions is probabilistic polynomial time (PPT) in the security parameter λ, and negl⁡(λ) denotes a negligible function (Math Guide, §“Polynomial, exponential, and negligible functions”; recalled in §1.2).

The one-time pad and EAV security.

The information-theoretic baseline is the one-time pad: to encrypt m∈{0,1}L under a uniformly random key k∈{0,1}L used exactly once, output c=m⊕k. Since m⊕k is uniform whatever m is, the ciphertext distribution is independent of the message, and even an unbounded eavesdropper learns nothing—Shannon’s perfect secrecy. The price is severe on both counts the name advertises: the key must be as long as the message, and it must never be reused, for two ciphertexts under one pad reveal c⊕c′=m⊕m′—the two-time-pad failure, which the adversary of the opening paragraph collects for free. The computational relaxation is EAV security (security against an eavesdropper): an adversary who chooses two equal-length messages m0,m1 and sees a single ciphertext Enck⁢(mb) for a hidden uniform bit b guesses b with advantage at most negl⁡(λ)—the one-ciphertext, no-oracle restriction of the chosen-plaintext game formalised in §6.2. Replacing the truly random pad by the output of a pseudorandom generator stretched from a short seed—the pseudo-one-time pad—achieves EAV security with a fixed-length key, at the cost of resting on a pseudorandomness assumption.

6.1 Stream ciphers and ChaCha20

A stream cipher is the practical instantiation of the pseudo-one-time pad: a keyed, seekable generator producing a keystream that XORs into the plaintext. To encrypt many messages under one key without violating the one-time-pad no-reuse rule, modern stream ciphers take an additional public input called a nonce (number used once) and behave like a pseudorandom function of the nonce, in the sense of Section 5.

Definition 6.1 (Nonce-based stream cipher).

A nonce-based stream cipher is a deterministic function

KS:𝒦×𝒩×ℕ→{0,1}∗

producing, for key k, nonce ν, and length L, a keystream KS⁢(k,ν,L)∈{0,1}L. Encryption of m∈{0,1}L is Enck⁢(ν,m)=m⊕KS⁢(k,ν,|m|) with ciphertext (ν,c); decryption recomputes the keystream and XORs it off. The security goal is that for distinct nonces the keystreams are jointly indistinguishable from independent uniform strings, provided no nonce repeats under a fixed key.

The stream cipher Zcash deploys—inside the AEAD of §6.5, in the note-encryption layer—is ChaCha20, designed by Bernstein and standardised in RFC 8439. Its core is a reversible mixing of four 32-bit words built only from modular addition, XOR, and rotation (an “ARX” design), which avoids data-dependent table lookups and hence the timing side channels that table-based ciphers must engineer around.

Construction 6.2 (ChaCha20).

The ChaCha20 state is a 4×4 matrix of 32-bit words, viewed as a vector (x0,…,x15)∈(ℤ/232⁢ℤ)16; the symbol + denotes addition modulo 232, ⊕ XOR, and x⋘r left rotation by r bits. The quarter-round QR⁢(a,b,c,d) updates four words by

a +=b; d ⊕=a; d ⋘=16;
c +=d; b ⊕=c; b ⋘=12;
a +=b; d ⊕=a; d ⋘=8;
c +=d; b ⊕=c; b ⋘=7.

The state is initialised from the 128-bit constant “expand 32-byte k” (words x0–x3), a 256-bit key (x4–x11), a 32-bit block counter (x12), and a 96-bit nonce (x13–x15). One double round applies QR to the four columns and then to the four diagonals; the 20 rounds of ChaCha20 are ten double rounds. Writing X for the initial state and R⁢(X) for the state after the rounds, the 64-byte keystream block is the feed-forward sum R⁢(X)+X (word-wise, modulo 232), serialised in little-endian order.

Remark 6.3 (Feed-forward and counter mode).

The rounds R form a bijection—each quarter-round is invertible, being a composition of invertible word operations—so without the final addition the block function would be an invertible permutation, and an adversary holding a keystream block could run the rounds backwards. The feed-forward sum R⁢(X)+X destroys invertibility; it is the standard Davies–Meyer-style move for turning a permutation into a one-way mixing function. Incrementing the block counter x12 produces successive 64-byte keystream blocks, so KS⁢(k,ν,L) is the concatenation of the blocks for counters 0,1,2,…; this counter mode is what makes the cipher seekable and parallelisable. The security status is a conjecture, in the same heuristic position as every concrete cipher of Section 5: ChaCha20 is conjectured to be a secure PRF of the pair (nonce, counter), and no attack better than brute force over the 256-bit key is known. Reusing a (k,ν) pair reproduces the same keystream and re-creates the two-time-pad failure; nonce uniqueness is a hard requirement, not a hygiene recommendation.

6.2 Chosen-plaintext security

EAV security models an adversary who sees a single ciphertext. The adversary of this section is stronger: she can influence which messages get encrypted—by triggering payments, injecting plaintext into a session, or simply guessing—and she observes many ciphertexts. The corresponding notion is security against chosen-plaintext attack (CPA), modelled by granting her oracle access to the encryption algorithm, in the game template of Definition 1.15.

Definition 6.4 (CPA security).

For a symmetric encryption scheme Π with key generator Gen, adversary 𝒜, and bit b∈{0,1}, the game 𝖢𝖯𝖠Π𝒜⁢(λ,b) runs as follows.

  1. 1.

    The challenger samples k←Gen⁢(1λ) and gives 𝒜 oracle access to Enck⁢(⋅).

  2. 2.

    At some point 𝒜 submits a challenge pair (m0,m1) of equal-length messages and receives c⋆←Enck⁢(mb).

  3. 3.

    The adversary may continue querying the oracle and finally outputs a bit b′, which is the output of the game.

The scheme Π is CPA-secure if for every PPT 𝒜,

AdvΠcpa⁢(𝒜,λ):=|Pr⁡[𝖢𝖯𝖠Π𝒜⁢(λ,0)=1]−Pr⁡[𝖢𝖯𝖠Π𝒜⁢(λ,1)=1]|∈negl⁡(λ).

The first consequence of giving the adversary an encryption oracle is a structural one: encryption cannot be a function of the message alone.

Proposition 6.5 (Determinism precludes CPA security).

No scheme whose Enc is deterministic and stateless is CPA-secure.

Proof.

The adversary queries the oracle on two distinct messages m0≠m1, recording c0=Enck⁢(m0) and c1=Enck⁢(m1). Decryption correctness forces c0≠c1: a single ciphertext cannot decrypt to both messages. She submits the challenge (m0,m1), receives c⋆=Enck⁢(mb), and outputs 0 if c⋆=c0 and 1 otherwise. Since Enc is deterministic, c⋆=cb, and since c0≠c1 the comparison identifies b: the guess is always correct and the advantage is 1. □

Consequently a CPA-secure scheme must be randomised or nonce-based. A nonce-based stream cipher used with a fresh nonce per encryption—random, or drawn from a counter—attains CPA security under the PRF conjecture for its keystream generator, because each encryption is then effectively a fresh one-time pad. We record the notion here and defer the routine PRF-based proof to the AEAD analysis (Theorem 6.20), where confidentiality and integrity are treated together.

Remark 6.6 (Semantic security).

Goldwasser and Micali’s original notion, semantic security, demands that whatever an efficient adversary can compute about the plaintext from the ciphertext, she could have computed without the ciphertext, from the message length alone. Semantic security is provably equivalent to the indistinguishability notions above; we use indistinguishability throughout because it is far easier to manipulate in reductions. The content is the same: the ciphertext is computationally useless for learning anything about the message beyond its length.

6.3 Message authentication codes

CPA security protects confidentiality and says nothing about integrity, and for the XOR-based stream ciphers above the gap is not hypothetical: flipping a bit of the ciphertext flips the corresponding plaintext bit, so the channel-owning adversary can convert a payment of one amount into a payment of another without ever touching the key. Detecting tampering requires a second primitive, keyed like the cipher but aimed at the forger rather than the eavesdropper: the message authentication code. Here we build this symmetric, shared-key form of authentication, the form that the AEAD needs.

Definition 6.7 (Message authentication code).

A message authentication code (MAC) is a pair (Mac,Vrfy) with key space 𝒦: algorithm Mack⁢(m) outputs a tag t, and Vrfyk⁢(m,t)∈{0,1} accepts (1) or rejects (0). Correctness requires Vrfyk⁢(m,Mack⁢(m))=1 for all k,m. When Mac is deterministic, canonical verification recomputes the tag and checks equality.

Definition 6.8 (Existential and strong unforgeability).

For a MAC Π and adversary 𝒜, the game 𝖥𝗈𝗋𝗀𝖾Π𝒜⁢(λ) runs as follows.

  1. 1.

    The challenger samples k←$𝒦 and gives 𝒜 oracle access to Mack⁢(⋅); let Q be the set of messages queried.

  2. 2.

    The adversary outputs a pair (m⋆,t⋆); the game outputs 1 iff Vrfyk⁢(m⋆,t⋆)=1 and m⋆∉Q.

The MAC is existentially unforgeable under chosen-message attack (EUF-CMA) if for every PPT 𝒜,

AdvΠforge⁢(𝒜,λ):=Pr⁡[𝖥𝗈𝗋𝗀𝖾Π𝒜⁢(λ)=1]∈negl⁡(λ).

A strongly unforgeable (sUF-CMA) MAC additionally forbids producing a new valid tag on an already-queried message: the adversary wins on (m⋆,t⋆) as long as the oracle never returned that exact pair. We write AdvΠs⁢-⁢forge⁢(𝒜,λ) for the advantage in this variant.

The MAC Zcash uses, Poly1305, is not a pseudorandom-function MAC but a one-time, universal-hash MAC: it provides information-theoretic security per nonce and is extremely fast, at the cost of a key that authenticates only a single message. The enabling abstraction is a hash family whose differences are unpredictable.

Definition 6.9 (ε-almost-Δ-universal hash family).

Let (𝒢,+) be a finite abelian group. A family of functions {hr:𝒳→𝒢}r∈ℛ is ε-almost-Δ-universal (ε-AΔU) if for all distinct x,x′∈𝒳 and every δ∈𝒢,

Prr←$ℛ⁡[hr⁢(x)−hr⁢(x′)=δ]≤ε.

Taking δ=0 recovers ordinary ε-universality—low collision probability—while the Δ condition controls additive differences, which is what makes the one-time MAC below secure. With 𝒢={0,1}n under XOR this is the classical almost-XOR-universality; Poly1305 takes 𝒢=ℤ/2128⁢ℤ under addition modulo 2128.

The Carter–Wegman paradigm turns any AΔU family into a one-time MAC by masking the hash value with a fresh uniform pad.

Theorem 6.10 (Carter–Wegman one-time MAC).

Let {hr} be ε-AΔU into (𝒢,+). Define a MAC with key (r,s), where r←$ℛ and the pad s←$𝒢, by Macr,s⁢(m)=hr⁢(m)+s. If (r,s) authenticates at most one message, then any adversary—even a computationally unbounded one—who sees one message–tag pair (m,t) forges a valid pair (m⋆,t⋆) with m⋆≠m with probability at most ε.

Proof.

The adversary observes t=hr⁢(m)+s and must output (m⋆,t⋆) with m⋆≠m and t⋆=hr⁢(m⋆)+s. Subtracting the two tag equations eliminates the pad: the forgery succeeds iff

hr⁢(m⋆)−hr⁢(m)=t⋆−t.

Condition on the adversary’s view. The pad s is uniform and independent of r, so given the single observed tag t, every value of hr⁢(m) is equally consistent—each candidate value determines a unique s—and the observation therefore leaks nothing about r: the posterior on r remains uniform on ℛ. The adversary’s difference δ:=t⋆−t and distinct pair (m,m⋆) are thus fixed independently of r, and the AΔU property gives Pr⁡[hr⁢(m⋆)−hr⁢(m)=δ]≤ε. □

The MAC Poly1305 instantiates the paradigm with a polynomial-evaluation hash over the prime field 𝔽p for p=2130−5 (prime-field arithmetic as in the Math Guide, §“The prime field and two inversion routes”).

Construction 6.11 (Poly1305).

Fix the prime p=2130−5 and work in 𝔽p. The key is a pair (r,s): r is a 128-bit value subjected to a fixed bit-clamping (the top four bits of bytes 3,7,11,15 and the bottom two bits of bytes 4,8,12 are forced to zero), and s is a 128-bit pad. To authenticate a message, split it into ℓ blocks c1,…,cℓ of at most 16 bytes; encode each block as an integer in [0,2128) and add 28⁢b, where b is the block’s byte length—this sets a 1 bit just above the block’s bytes, making every coefficient nonzero and the block encoding injective in both content and byte length. Interpreting r and each ci as elements of 𝔽p, the hash is the polynomial evaluation

hr⁢(m)=∑i=1ℓci⁢rℓ−i+1∈𝔽p,

computed by Horner’s rule as (⋯⁢((c1⁢r+c2)⁢r+c3)⁢r⁢⋯)⁢r. The tag is

Macr,s⁢(m)=((hr⁢(m)modp)+s)mod2128,

the field hash reduced and added to the pad modulo 2128.

Proposition 6.12 (Poly1305 is almost-Δ-universal).

Restricted to messages of at most L bytes—hence at most ℓmax=⌈L/16⌉ blocks—the reduced Poly1305 hash family {m↦hr⁢(m)modp}, read into ℤ/2128⁢ℤ, is ε-almost-Δ-universal with respect to addition modulo 2128, with

ε≤8⁢ℓmax2106.

The loss over the ideal ℓmax⋅p−1 accounts for the clamping of r—which restricts r to a subset of size 2106—and for the final reduction modulo 2128.

Proof.

Sketch. Fix two distinct messages m,m′ with block encodings (ci) and (cj′), padded to a common length ℓ≤ℓmax by leading zero coefficients without changing their values. The block encoding guarantees that m≠m′ yields distinct coefficient vectors: genuine coefficients are nonzero, so differing block counts set a nonzero coefficient against a zero padding one, while equal block counts leave two blocks differing in content or in final-block byte length, hence in encoding. The difference of hashes is

hr(m)−hr(m′)=∑i=1ℓ(ci−ci′)rℓ−i+1=:P(r)∈𝔽p,

a nonzero polynomial in r of degree at most ℓ. Now count the ways a target difference δ∈ℤ/2128⁢ℤ can be hit. The reduced hash values lie in [0,p), so their integer difference lies in the interval (−p,p), which has length 2⁢p<8⋅2128; each residue class modulo 2128 therefore contains at most ⌈2⁢p/2128⌉=8 candidate integer differences u. For each such u, the equation P⁢(r)=u in 𝔽p has at most ℓ roots—a polynomial of degree ≤ℓ over a field has at most ℓ roots (Math Guide, §“Roots and the factor theorem”)—so at most 8⁢ℓ values of r produce the difference δ. The clamped r is uniform over a set of 2106 values (clamping zeroes 22 of the 128 bits), so it lands on one of those roots with probability at most 8⁢ℓ/2106≤8⁢ℓmax/2106. □

The bound is comfortably small in practice: for messages of 16 384 bytes (ℓmax=1024 blocks) it gives ε≤8⋅1024/2106=2−93, against the ideal ℓmax/p≈2−120—the clamping and reduction losses cost 27 bits of the margin and leave it enormous. Combining Proposition 6.12 with the Carter–Wegman Theorem 6.10: Poly1305 with a fresh, uniformly random pad s per message—uniformity, not mere unpredictability, is what the theorem’s pad-elimination step uses—is a one-time MAC with forgery probability at most 8⁢ℓmax/2106 per verification attempt. In the AEAD below, ChaCha20 itself generates the one-time key (r,s) pseudorandomly from the nonce—uniform once the cipher is idealised as a random function—so the per-nonce one-time guarantee is exactly what is needed.

6.4 Authenticated encryption with associated data

We now combine the two guarantees. The composite goal is authenticated encryption: the adversary should be unable to learn anything about plaintexts (CPA security) and unable to produce any new ciphertext that decrypts to anything other than the distinguished rejection symbol ⊥, a value distinct from every message (ciphertext integrity). Real protocols additionally require ciphertexts to bind to public context—packet headers, version bytes, an ephemeral public key—that travels in the clear but must be authenticated; this is the associated data.

Definition 6.13 (AEAD scheme).

An authenticated encryption with associated data (AEAD) scheme is a pair (Enc,Dec) with key space 𝒦, nonce space 𝒩, and associated-data space 𝒟: algorithm Enck⁢(ν,a,m) returns a ciphertext c, and Deck⁢(ν,a,c) returns a message or ⊥. Correctness: Deck⁢(ν,a,Enck⁢(ν,a,m))=m for all k,ν,a,m. The scheme authenticates but does not encrypt the associated data a.

Definition 6.14 (Ciphertext integrity, INT-CTXT).

For an AEAD scheme Π and adversary 𝒜, the game 𝖢𝗍𝗑𝗍Π𝒜⁢(λ) runs as follows.

  1. 1.

    The challenger samples k←$𝒦 and gives 𝒜 two oracles: an encryption oracle Enck⁢(⋅,⋅,⋅), recording the set Q of returned triples (ν,a,c), and a verification oracle that on (ν,a,c) returns 1 if Deck⁢(ν,a,c)≠⊥ and 0 otherwise. The adversary must never repeat a nonce to the encryption oracle (the nonce-respecting model); verification queries may reuse nonces freely.

  2. 2.

    The game outputs 1 iff some verification query (ν⋆,a⋆,c⋆)∉Q is answered 1.

The scheme Π has ciphertext integrity if for every PPT 𝒜, Pr⁡[𝖢𝗍𝗑𝗍Π𝒜⁢(λ)=1]∈negl⁡(λ).

Definition 6.15 (Authenticated encryption).

An AEAD scheme is secure (is an AEAD) if it is both CPA-secure and has ciphertext integrity (Definition 6.14), where the CPA game of Definition 6.4 is run with k←$𝒦 and extended so that the adversary supplies the nonce and associated data of every oracle query and of the challenge, subject to the nonce-respecting restriction—a restriction on the adversary, not a property of the scheme—that no nonce is used twice across oracle queries and challenge. The restriction is necessary: an AEAD may encrypt deterministically given (ν,a,m)—ChaCha20-Poly1305 does—and then querying the oracle at (ν,a,m0) and submitting the challenge (ν,a,m0,m1) would identify the bit by comparing ciphertexts.

The standard route from a CPA-secure cipher and a strongly unforgeable MAC to an AEAD is encrypt-then-MAC: encrypt the message, compute a MAC over the ciphertext together with the associated data and nonce, and append the tag; decryption verifies the tag before decrypting, and any tag failure returns ⊥. The contrasting orders—MAC-then-encrypt and encrypt-and-MAC—do not generically achieve authenticated encryption; encrypt-then-MAC does.

Theorem 6.16 (Encrypt-then-MAC yields authenticated encryption).

Let ΠE=(Enc,Dec) be a CPA-secure encryption scheme and ΠM=(Mac,Vrfy) a strongly unforgeable (sUF-CMA) MAC, with independent keys kE,kM. Define the composite scheme Π′ by

EnckE,kM′⁢(ν,a,m)=(c,t),c←EnckE⁢(ν,m),t←MackM⁢(ν⁢‖a‖⁢c),

with Dec′ returning ⊥ unless VrfykM⁢(ν⁢‖a‖⁢c,t)=1, in which case it returns DeckE⁢(ν,c). Then Π′ is a secure AEAD: it is CPA-secure and has ciphertext integrity.

Proof.

Ciphertext integrity. Suppose a PPT 𝒜 making at most qv verification queries wins the game: some fresh query (ν⋆,a⋆,(c⋆,t⋆))∉Q decrypts successfully, i.e. VrfykM⁢(ν⋆⁢‖a⋆‖⁢c⋆,t⋆)=1. Each encryption-oracle call on (ν,a,m) returned (c,t) and corresponds to one MAC query on the string w=ν⁢‖a‖⁢c returning tag t. Because the framing ν⁢‖a‖⁢c parses uniquely (the component lengths are fixed or prepended), the freshness of (ν⋆,a⋆,c⋆) means the MAC oracle never produced the string–tag pair (w⋆,t⋆) with w⋆:=ν⋆⁢‖a⋆‖⁢c⋆: either w⋆ was never queried, or it was queried and returned a different tag. Either way (w⋆,t⋆) is a fresh valid pair—a strong forgery against ΠM. The reduction ℬ runs 𝒜, answering encryption queries with its own MAC oracle and a self-chosen kE. Verification queries ℬ cannot answer, lacking kM, so it guesses: it samples a uniform index i≤qv in advance, answers each fresh verification query before the i-th with 0 (queries on triples in Q are answered 1, correctly), halts at the i-th fresh query, and outputs that query’s (w⋆,t⋆) as its forgery. On the event that 𝒜 wins and i hits her first successful fresh query—the guess is right with probability 1/qv—every earlier 0 answer was correct, the simulation is perfect, and ℬ wins, so

Pr⁡[𝖢𝗍𝗑𝗍Π′𝒜⁢(λ)=1]≤qv⋅AdvΠMs⁢-⁢forge⁢(ℬ,λ)∈negl⁡(λ),

the factor qv being polynomial.

CPA security. The tag is computed from c (together with kM,ν,a, and the MAC’s own coins) and so carries no information about the challenge bit beyond what c already carries. Formally, the reduction ℬ′ samples kM itself, forwards 𝒜’s oracle and challenge queries to its own ΠE oracle to obtain the c-components, and appends tags it computes with kM. This simulates Π′ perfectly, so AdvΠ′cpa⁢(𝒜,λ)=AdvΠEcpa⁢(ℬ′,λ)∈negl⁡(λ). □

Remark 6.17 (Why the ordering matters).

Encrypt-then-MAC lets the receiver reject forged ciphertexts without decrypting, and this is what blocks chosen-ciphertext and padding-oracle attacks: a rejected ciphertext never reaches the decryption logic, so the decryption logic cannot leak. By contrast, MAC-then-encrypt verifies only after decrypting, exposing the decryption routine to attacker-chosen ciphertexts—the historical source of a long line of padding-oracle breaks. Ciphertext integrity is also exactly the property that upgrades CPA security to chosen-ciphertext (CCA) security, the CPA game of Definition 6.4 with a decryption oracle added that refuses only the challenge ciphertext: an authenticated-encryption scheme is automatically CCA-secure, because that oracle is useless to the adversary—every ciphertext she did not legitimately obtain decrypts to ⊥ except with negligible probability.

6.5 The ChaCha20-Poly1305 AEAD

We now assemble the concrete scheme of RFC 8439, the AEAD by which Zcash encrypts every shielded note ciphertext and outgoing ciphertext (protocol specification, §“Symmetric Encryption”). It is an encrypt-then-MAC composition of the ChaCha20 stream cipher with the Poly1305 one-time MAC, with one economical twist: the cipher derives both the keystream and the one-time MAC key from the single (k,ν) input.

Construction 6.18 (ChaCha20-Poly1305).

Fix a 256-bit key k and a 96-bit nonce ν. Encryption of a message m with associated data a proceeds as follows.

  1. 1.

    One-time MAC key. Run ChaCha20 with key k, nonce ν, and block counter 0; take the first 32 bytes of the keystream block as the Poly1305 one-time key (r,s)—clamp the first 16 bytes to form r; the next 16 are s. Discard the rest of this block.

  2. 2.

    Encrypt. Run ChaCha20 with key k and nonce ν starting at block counter 1, producing the keystream KS1 (the keystream of Remark 6.3 taken from counter 1 onward), and set c=m⊕KS1⁢(k,ν,|m|).

  3. 3.

    Authenticate. Form the Poly1305 input by concatenating: a padded with zeros to a 16-byte boundary, c padded with zeros to a 16-byte boundary, the 8-byte little-endian length of a, and the 8-byte little-endian length of c. Compute the tag t=Poly1305r,s⁢(that input).

The ciphertext is (c,t). Decryption recomputes (r,s) and the tag from (k,ν,a,c), compares it to t in constant time, returns ⊥ on mismatch, and otherwise outputs m=c⊕KS1⁢(k,ν,|c|).

Remark 6.19 (Length encoding prevents splicing).

The trailing 8-byte lengths of a and c are essential. Without them, the zero-padding that aligns a and c to 16-byte boundaries would let an adversary shift bytes between the associated data and the ciphertext, or pad-extend one of them, while leaving the Poly1305 input string unchanged—breaking the binding between a and c even though every authenticated byte is intact. Appending the explicit lengths makes the MAC input an injective encoding of the pair (a,c), the same injectivity that the per-block length encoding supplies within one message in the AΔU analysis (Proposition 6.12).

Theorem 6.20 (Security of ChaCha20-Poly1305).

Model ChaCha20 as a pseudorandom function Fk⁢(ν,j) from (nonce, block counter) pairs to 64-byte blocks. In the nonce-respecting model, ChaCha20-Poly1305 is a secure AEAD. Concretely, consider a PPT adversary making q encryption queries and qv verification queries, each of whose Poly1305 inputs—padded associated data, padded ciphertext, and the length block—comprises at most ℓmax sixteen-byte blocks, ℓmax=⌈|a|/16⌉+⌈|c|/16⌉+1. Her CPA advantage is at most twice the best PRF-distinguishing advantage against F at comparable cost, and she forges—wins the INT-CTXT game—with probability at most

AdvFprf⁢(ℬ,λ)+8⁢qv⁢ℓmax2106,

where ℬ is a PRF distinguisher of comparable cost.

Proof.

Sketch. Replace Fk by a truly random function Φ from (nonce, counter) pairs to 64-byte blocks. Any noticeable change in the adversary’s success probability yields a PRF distinguisher of comparable cost—it simulates the whole game using its function oracle—so each replacement costs one AdvFprf term; the CPA game is played twice (once per challenge bit), whence the factor two there. We analyse the idealised scheme.

Confidentiality. Since the adversary is nonce-respecting, every encryption query uses a fresh ν, and the keystream blocks Φ⁢(ν,1),Φ⁢(ν,2),… are uniform and independent of everything else in her view; the ciphertext c=m⊕KS is a genuine one-time pad and reveals nothing about m beyond its length. The tag is a deterministic function of c,a,ν and the (independent) key (r,s), and adds no information. The idealised CPA advantage is therefore zero.

Integrity. For each nonce ν, the block Φ(ν,0)[0:32] is uniform and independent across distinct nonces; clamping its first half samples r from Poly1305’s prescribed restricted set, while the second half s stays uniform, so the resulting one-time keys are independent across nonces. Because counter 0 is reserved for this key while encryption consumes counters ≥1, each one-time key is also independent of the keystream that produced its ciphertext. Per nonce, the setting is exactly the Carter–Wegman one-time MAC of Theorem 6.10 instantiated with the ε-AΔU Poly1305 hash of Proposition 6.12, ε≤8⁢ℓmax/2106. Consider any single fresh verification query (ν⋆,a⋆,c⋆,t⋆). If ν⋆ was never used for encryption, the pad s for ν⋆ is uniform and entirely unknown, so the tag is correct with probability 2−128. If ν⋆ equals the nonce of some encryption query—nonce reuse is allowed in verification queries, only encryption is nonce-respecting— then the adversary has seen exactly one tag under that (r,s), and freshness of (a⋆,c⋆) makes this a forgery on a new message under a one-time key, succeeding with probability at most ε by Theorem 6.10. The union bound over the qv verification queries (Math Guide, §“The union bound and a birthday calculation”) gives forgery probability at most 8⁢qv⁢ℓmax/2106 in the idealised scheme; adding back the PRF-switching cost yields the stated bound. □

Remark 6.21 (Single key, two roles).

The scheme reuses one 256-bit key for both encryption and authentication, seemingly violating the independent-keys hypothesis of Theorem 6.16. Reserving block counter 0 for the Poly1305 key and counters ≥1 for the keystream is exactly what restores independence: once the cipher is idealised as a truly random function—the switch the proof of Theorem 6.20 pays for with a PRF-distinguishing term—outputs at distinct counters are independent, so (r,s) is independent of the keystream and the two-key analysis applies. For the PRF itself the independence is computational, not literal. This is a recurring design pattern—domain separation by a counter or label, the same discipline as §3.5, lets one master key safely play several roles.

Remark 6.22 (Wrong-key rejection and key commitment).

The upper volumes consume this AEAD in a trial-decryption pattern: a receiver detects the notes addressed to it by attempting decryption of every ciphertext under each of its keys, relying on decryption under a wrong key to return ⊥ (protocol specification, §“Symmetric Encryption”). For honestly produced ciphertexts the scheme delivers this. Fix a ciphertext (c,t)=Enck⁢(ν,a,m) and a key k′ independent of k, and idealise the cipher under k and under k′ as independent random functions, as in the proof of Theorem 6.20. The one-time key (r′,s′) that decryption under k′ derives from block (ν,0) is then uniform and independent of (c,t): the pad s′ alone makes the recomputed tag match t with probability exactly 2−128, and even conditioned on one exposed tag under (r′,s′), Theorem 6.10 bounds acceptance by the AΔU slack 8⁢ℓmax/2106 of Proposition 6.12, with ℓmax as in Theorem 6.20. Decryption under an independent key therefore rejects except with probability at most 2−128+8⁢ℓmax/2106 per attempt, plus two PRF-distinguishing terms for the two idealisations.

The guarantee stops at honest senders, and the boundary deserves care. CPA security and INT-CTXT are single-key notions: nothing in Definition 6.15 constrains a ciphertext crafted by a malicious sender who knows several keys. The scheme is in fact not key-committing—the separate notion demanding that no ciphertext verify under two distinct keys—and a sender who chooses keys k1,k2 herself can craft a single (c,t) that decrypts validly, to different plaintexts, under both: with (ri,si) the one-time key each ki derives, the hash hri of Construction 6.11 is linear in the blocks of c, so fixing t, leaving two blocks of c free, and solving over 𝔽p the two linear equations that pin the hash under ri to t−si (retrying until both solutions encode valid blocks) makes both keys accept (c,t)—the multi-key collision of Len, Grubbs, and Ristenpart’s partitioning-oracle attack. The upper volumes’ trial-decryption arguments therefore never rest on the tag alone against adversarial senders: their note-plaintext consistency checks—recomputing the note commitment from the decrypted plaintext and comparing it against the commitment the transaction carries—are what close this gap.

6.6 Key-derivation functions

Theorem 6.20 assumes a uniformly random 256-bit key. In practice keys may come from sources that are high-entropy but not uniform: a Diffie–Hellman shared secret is a structured group encoding, not a uniform bit string, and a hardware noise source may spread its unpredictability unevenly across its bits. (A passphrase is a different, usually low-entropy source, and needs a deliberately costly password KDF rather than the machinery of this subsection.) The adversary is owed nothing here—if the honest parties feed a non-uniform key into a scheme proved secure for uniform keys, the proof simply does not apply, and structure in the key is structure she may exploit. A key-derivation function (KDF) converts an appropriate source secret into one or more pseudorandom keys. The right entropy measure is worst-case, not average-case.

Definition 6.23 (Min-entropy).

The min-entropy of a random variable X is

H∞⁢(X)=−log2⁡maxx⁡Pr⁡[X=x];

equivalently, the best chance of guessing X in one try is 2−H∞⁢(X). Given side information Z, the conditional min-entropy is

H~∞⁢(X∣Z)=−log2⁡𝔼z←Z⁢maxx⁡Pr⁡[X=x∣Z=z],

so that 2−H~∞⁢(X∣Z) is the best chance of guessing X from Z. Recall the statistical distance Δ⁢(X,Y)=12⁢∑u|Pr⁡[X=u]−Pr⁡[Y=u]| of Definition 1.6 (Math Guide, §“Statistical distance”); we say X is ϵ-close to uniform on a set S if Δ⁢(X,US)≤ϵ.

Definition 6.24 (Key-derivation function and its security).

A key-derivation function is a function

KDF:𝒳×ℐ×{0,1}∗×ℕ→{0,1}∗

taking a source secret (a sample of a random variable Σ over 𝒳), a non-secret salt slt∈ℐ, an info or context string ctx, and a desired output length L. The security goal must specify the source model. For an arbitrary source of conditional min-entropy at least γ given the adversary’s side information, an extractor-style guarantee uses a salt sampled uniformly and independently of the source and requires the pair (slt,KDF⁢(Σ,slt,ctx,L)) to be computationally indistinguishable from (slt,UL), even given ctx and that side information. No fixed deterministic unsalted function can provide this guarantee for every high-min-entropy source; an unsalted KDF therefore rests on a narrower premise, such as input keying material that is already computationally pseudorandom, or that is hard to query in a random-oracle model.

The notion a KDF targets is that of a seeded randomness extractor whose output need only look uniform.

Definition 6.25 (Strong computational extractor).

A keyed function Ext:ℐ×𝒳→{0,1}n is a strong (γ,ϵ)-computational extractor if for every source Σ over 𝒳 of conditional min-entropy at least γ given auxiliary information Z, and a uniformly random salt slt←$ℐ, the pair (slt,Extslt⁢(Σ)) is computationally indistinguishable from (slt,Un), even given Z, with distinguishing advantage at most ϵ. “Strong” means the salt is revealed to the distinguisher.

Information theory can realise the notion unconditionally; we state the classical result without proof, since the deployed mechanism below rests on random-oracle modelling instead.

Theorem 6.26 (Leftover hash lemma; stated without proof).

Let {gr:𝒳→{0,1}n} be a 2−n-universal hash family with a uniform public seed R. For any X with H∞⁢(X)≥γ,

Δ⁢((R,gR⁢(X)),(R,Un))≤12⁢2n−γ.

Thus investing γ≥n+2⁢log2⁡(1/ϵ) bits of min-entropy buys n output bits that are ϵ-close to uniform—a strong (γ,ϵ)-extractor in the statistical, not merely computational, sense.

HKDF, in passing.

The standardised general-purpose KDF is Krawczyk’s HKDF (RFC 5869), built from HMAC (§5.3) in an extract-then-expand architecture: a salted HMAC call first distils suitable non-uniform input keying material into a short pseudorandom key (the extractor stage, justified along leftover-hash lines), and a counter-chained sequence of HMAC calls then expands that key, under a context string, up to RFC 5869’s limit of 255 hash-output-length blocks (the expander stage, justified by HMAC’s PRF security). The resulting KDF is a standard choice across many protocol source models and output lengths, though its precise guarantee still depends on assumptions about the source and about HMAC. Zcash does not use it—indeed the shielded protocol uses HMAC nowhere: neither the orchard nor the zcash_note_encryption crate carries an HMAC dependency (HMAC enters the wallet stack through the transparent BIP-32 derivation and BIP-39 mnemonic layers and, transitively, through the optional Tor client, never through a shielded crate)—because its requirements are narrower and a single hash call meets them in the random-oracle analysis.

The Zcash KDF.

Orchard derives the note-encryption key by one personalised BLAKE2b call:

Kenc=KDF⁢(𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍,𝖾𝗉𝗄)=BLAKE2b⁢-⁢256⁢("Zcash_OrchardKDF";𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍∥𝖾𝗉𝗄),

where 𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍 is the Diffie–Hellman shared point of the note-encryption key agreement, 𝖾𝗉𝗄 is the sender’s ephemeral public key, and the quoted string occupies BLAKE2b’s 16-byte personalisation field (the function kdf_orchard hashes the serialised shared point followed by the ephemeral-key bytes with a 32-byte output; protocol specification, §“Orchard Key Derivation”). The analysis models this personalised hash as a random oracle: by the domain-separation principle of §3.5 (Proposition 3.17, via the native-personalisation idiom catalogued there), the personalisation makes it an oracle independent of every other hash use in the protocol, and the derived key is uniform in the adversary’s view unless she queries that oracle at the hidden 𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍—a query whose argument she must first compute from the two public keys, an instance of the computational Diffie–Hellman problem of §2.2. Folding 𝖾𝗉𝗄 into the input binds the derived key to this particular ephemeral, the role the context string plays in HKDF. No salt is used because the claim is this narrower Diffie–Hellman-plus-random-oracle one—the unsalted premise anticipated in Definition 6.24—not extraction from every high-min-entropy source.

Remark 6.27 (The role of the KDF in the larger protocol).

In the Zcash note-encryption layer, a Diffie–Hellman exchange on the Pallas curve produces a shared group element, and the single BLAKE2b call above condenses that element into the symmetric key fed to ChaCha20-Poly1305. The two halves of this section meet exactly here: key derivation manufactures the uniform key that the AEAD security theorem (Theorem 6.20) takes as its hypothesis, and the chain from a non-uniform shared secret to an authenticated ciphertext is complete. Section 7 assembles that chain end to end as hybrid public-key encryption.