2 Hierarchical key derivation (ZIP 32)

A hybrid argument (Crypto Guide, §“The hybrid argument”, Lemma “Hybrid lemma”). Game $0$ is the real experiment. Game $1$ answers every oracle query whose input is determined by $S$ (the master query of Construction 2.3, the input of $\mathrm{𝖲𝖾𝖾𝖽𝖥𝖯}$ and the inputs of the other modelled derivations) by fresh uniform strings, independent of $S$. The two games differ only if the adversary itself queries such an input. In Game $1$ its view is independent of $S$ until that happens, so each of its $q$ queries does so with probability at most $2^{-256}$ by hypothesis (ii), and the games differ by at most $q\cdot 2^{-256}$. In Game $1$ the pair $({\mathrm{𝗌𝗄}}_m,{𝖼}_m)$ and $\mathrm{𝖲𝖾𝖾𝖽𝖥𝖯}(S)$ are independent uniform strings.

Then visit the nodes of $T$ that have a child in $T$, each parent before its children. At such a node $v$ the chain code ${𝖼}_v$ is, by the earlier hops, a uniform string that is used only as a $\mathrm{𝖯𝖱𝖥𝖾𝗑𝗉𝖺𝗇𝖽}$ key and is not released, because $v$ is a proper ancestor of a node of $N$. The hop replaces ${\mathrm{𝖯𝖱𝖥𝖾𝗑𝗉𝖺𝗇𝖽}}_{{𝖼}_v}$ by a uniformly random function. The children of $v$ in $T$ have distinct indices, hence distinct inputs $[\mathrm{𝟶}𝚡\mathrm{𝟾𝟷}]\Vert {\mathrm{𝗌𝗄}}_v\Vert {\mathrm{𝖨𝟤𝖫𝖤𝖮𝖲𝖯}}_{32}(i)$, so their $64$-byte outputs become fresh uniform strings (Ironwood Guide, §“Pseudorandom functions and field reductions”, Lemma “Independence of domain-separated expansions”, first conclusion, applied to a uniform key; its statistical-distance clause is not used). The hop costs the PRF advantage of a reduction that samples every other node itself and forwards the queries of $v$ to its oracle. In the last game every released value is a fresh uniform string; the chain codes of proper ancestors, which are not fresh relative to their children, are exactly those the lemma does not release. □

The key ${\mathrm{𝗌𝗄}}_{\mathrm{𝖺𝖼𝖼𝗍}}$ is only computationally close to uniform, so the statistical-distance clause of the Ironwood Guide’s Lemma “Independence of domain-separated expansions” (§“Pseudorandom functions and field reductions”) does not apply; the proof is a reduction. Both $V$ and $W$ are decided efficiently by the challenger. A distinguisher for Lemma 2.5 receives either the real values (${\mathrm{𝗌𝗄}}_{\mathrm{𝖺𝖼𝖼𝗍}}$, the other spending keys and $\mathrm{𝖲𝖾𝖾𝖽𝖥𝖯}(S)$) or independent uniform strings, runs the challenger and $𝒜$ on them, and outputs $1$ exactly on $W\wedge V$; a second distinguisher outputs $1$ exactly on $V$. Write $a:=\mathrm{Pr}[W\wedge V]$ and $v:=\mathrm{Pr}[V]$ for the real values, and $a_u$, $v_u$ for the uniform ones. Then $|a-a_u|\le \delta$ and $|v-v_u|\le \delta$, with $v_u=1-\rho$. With uniform inputs, the extra inputs are independent of the key and distributed as $ℬ$ samples them. Key generation outputs a single uniform draw conditioned on acceptance, so $\mathrm{Pr}[ℬ\text{ wins }G]=a_u/v_u$. Hence

using $a_u\le v_u$ and $v\ge v_u-\delta$. □

Composition of Constructions 2.3 and 2.4 and Definition 2.7, which map the seed to ${\mathrm{𝗌𝗄}}_{\mathrm{𝖺𝖼𝖼𝗍}}$; of Construction 2.10, which maps ${\mathrm{𝗌𝗄}}_{\mathrm{𝖺𝖼𝖼𝗍}}$ and $\mathrm{𝗎𝗌𝖾}\mathrm{\_}\mathrm{𝗊𝗌𝗄}$, together with ${\mathrm{𝖺𝗄}}^{\mathbb{P}}$ when $\mathrm{𝗎𝗌𝖾}\mathrm{\_}\mathrm{𝗊𝗌𝗄}=\mathrm{𝗍𝗋𝗎𝖾}$, to $(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄},{𝗋}_{\mathrm{𝗂𝗏𝗄}})$; and of the Ironwood Guide’s constructions from $(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄},{𝗋}_{\mathrm{𝗂𝗏𝗄}})$ (§“Viewing keys” and §“Diversified addresses”). The keys of the internal scope are a function of $\mathrm{𝖿𝗏𝗄}$ (§2.5), and the composition only adds that function. ZIP 2005, “Changes to the Protocol Specification”, §4.2.3 “Orchard Key Components”, notes, and “Usage with FROST” state the same requirements for recovery. □

Computation: ${\mathrm{𝖿𝗏𝗄}}_{\mathrm{𝗂𝗇𝗍}}$ is a function of $\mathrm{𝖿𝗏𝗄}$ (Construction 2.14), and each address is a function of $(\mathrm{𝖽𝗄},\mathrm{𝗂𝗏𝗄})$ and $j$ (Ironwood Guide, §“Diversified addresses”, Construction “Diversified address”). No $\mathrm{𝖺𝗌𝗄}$: the Ironwood Guide, §“Key capabilities and scope”, Proposition “Capability separation”, part (a), under its Assumptions “Pseudorandomness of PRF expansion” and “Discrete logarithms on Pallas”, transferred to ${\mathrm{𝗌𝗄}}_{\mathrm{𝖺𝖼𝖼𝗍}}$ by Lemma 2.9. No other account: the spending key of another account lies at a distinct path, and only hardened derivation exists; by Lemma 2.5 the two keys are jointly indistinguishable from independent uniform strings, so an algorithm given every key of this account outputs the other key with probability at most $2^{-256}$ plus the advantage bound of that lemma. □

Acceptance under a key $\mathrm{𝗂𝗏𝗄}$ derives the transmission key again as $[\mathrm{𝗂𝗏𝗄}]{𝗀}_{𝖽}$ from the decrypted diversifier and checks the note commitment of the derived note against $\mathrm{𝖼𝗆𝗑}$ (Ironwood Guide, §“Trial decryption and note acceptance”, Construction “Acceptance of an Ironwood-pool output”, check (iv); for an Orchard-pool output the check of the protocol specification, §“Decryption using an Incoming Viewing Key (Sapling and Orchard)”). The honest output commits to a note $n$ with transmission key $[{\mathrm{𝗂𝗏𝗄}}_{\mathrm{𝗂𝗇𝗍}}]{𝗀}_{𝖽}$. If the note $n^{\prime }$ derived under ${\mathrm{𝗂𝗏𝗄}}_{\mathrm{𝖾𝗑𝗍}}$ differs from $n$, acceptance exhibits two distinct notes with one extracted commitment, which happens with negligible probability (Ironwood Guide, §“Note commitments”, Proposition “Hiding and binding of note commitments”, part (b)). If $n^{\prime }=n$, then $[{\mathrm{𝗂𝗏𝗄}}_{\mathrm{𝖾𝗑𝗍}}]{𝗀}_{𝖽}=[{\mathrm{𝗂𝗏𝗄}}_{\mathrm{𝗂𝗇𝗍}}]{𝗀}_{𝖽}$; since ${𝗀}_{𝖽}\ne 𝒪$ in a group of prime order and both scalars lie in $\{1,\mathrm{\dots },p_{\mathrm{𝖯𝖺𝗅𝗅𝖺𝗌}}-1\}$ with , this forces ${\mathrm{𝗂𝗏𝗄}}_{\mathrm{𝖾𝗑𝗍}}={\mathrm{𝗂𝗏𝗄}}_{\mathrm{𝗂𝗇𝗍}}$ (Ironwood Guide, §“Viewing keys”). By Lemma 2.9 and Assumption 2.16 the pair is replaced by $({\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}_r^{\mathrm{𝗂𝗏𝗄}}(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄}),{\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}_{r^{\prime }}^{\mathrm{𝗂𝗏𝗄}}(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄}))$ with independent uniform $r$ and $r^{\prime }$, at the cost of the distinguishing advantage, since equality is efficiently decidable. By the Ironwood Guide’s Lemma “Distribution of $\mathrm{𝗂𝗏𝗄}$” (§“Viewing keys”), the second value equals any fixed value with probability at most $2/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, independently of the first, so the two are equal with probability at most $2/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$. □

(i) Constructive: Construction 2.14 and the Ironwood Guide’s constructions; for transparent keys, Construction 2.18 from $(𝖼,\mathrm{𝗉𝗄})$.

(ii) and (iii), Orchard: by Lemma 2.9 and Assumption 2.16 the six keys are replaced by the ideal distribution, at the cost of the distinguishing advantage, since success is decided by comparing the output with the key. In the ideal distribution every key not computed from the held one is independent of it: either a uniform $32$-byte string, output with probability $2^{-256}$, or a ${\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}^{\mathrm{𝗂𝗏𝗄}}$ value under an independent trapdoor, output with probability at most $2/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$ (Ironwood Guide, §“Viewing keys”, Lemma “Distribution of $\mathrm{𝗂𝗏𝗄}$”). Transparent: the same argument in the ideal distribution of Assumption 2.19, where an independently generated extended public key has a uniform chain code, output with probability $2^{-256}$. Sapling: cited to ZIP 316, “Deriving Internal Keys”, which asserts them from the one-wayness of $\mathrm{𝖯𝖱𝖥𝖾𝗑𝗉𝖺𝗇𝖽}$ and ${\mathrm{𝖢𝖱𝖧}}^{\mathrm{𝗂𝗏𝗄}}$; not proved here. □

Replace ${\mathrm{𝗌𝗄}}_{\mathrm{𝖺𝖼𝖼𝗍}}$ by a uniform string (Lemma 2.5); the $512$-bit outputs of rows $\mathrm{𝟶}𝚡\mathrm{𝟶𝟼}$, $\mathrm{𝟶}𝚡\mathrm{𝟶𝟽}$ and $\mathrm{𝟶}𝚡\mathrm{𝟶𝟾}$ by independent uniform strings (the Ironwood Guide’s Lemma “Independence of domain-separated expansions” (§“Pseudorandom functions and field reductions”), first conclusion); ${𝗋}_{\mathrm{𝗂𝗏𝗄}}$ by a uniform element of ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$ (the reduction distance); and, on the event $\mathrm{𝖺𝗌𝗄}\ne 0$, the pair $(\mathrm{𝗂𝗏𝗄},{\mathrm{𝗂𝗏𝗄}}_{\mathrm{𝗂𝗇𝗍}})$ by $({\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}_r^{\mathrm{𝗂𝗏𝗄}}(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄}),{\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}_{r^{\prime }}^{\mathrm{𝗂𝗏𝗄}}(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄}))$ with independent uniform $r$ and $r^{\prime }$ (Assumption 2.16). Each replacement changes the probability of invalidity by at most one term of $\delta$, since validity is efficiently decidable. Then, by the union bound (Math Guide, §“The union bound and a birthday calculation”, Theorem “Union bound / Boole’s inequality”), the key is invalid only on one of the following events.

1. (a)

   $\mathrm{𝖺𝗌𝗄}=0$. The sign normalisation preserves $0$, so this happens exactly when a uniform $512$-bit integer is divisible by $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, with probability $\lceil 2^{512}/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}\rceil /2^{512}$ (Math Guide, §“Uniform sampling and the bias of modular reduction”).

2. (b)

   The Sinsemilla hash point $\widehat{M}$ of the message ${\mathrm{LE}}_{255}(\mathrm{𝖺𝗄})\parallel {\mathrm{LE}}_{255}(\mathrm{𝗇𝗄})$ is $\perp$. The message has $510$ bits, $51$ chunks of $10$ bits, so the hash performs $102$ incomplete additions, two per round, ${\mathrm{𝖠𝖼𝖼}}_i:=({\mathrm{𝖠𝖼𝖼}}_{i-1}\dotplus S(m_i))\dotplus {\mathrm{𝖠𝖼𝖼}}_{i-1}$ (protocol specification, §“Sinsemilla Hash Function”; Ironwood Guide, §“Sinsemilla: hash, commitment, and short forms”, Construction “Sinsemilla hash on Pallas”). An incomplete addition $A\dotplus B$ of points is exceptional exactly when $A=𝒪$, $B=𝒪$, $A=B$ or $A=-B$. At the first exceptional addition every accumulator so far equals its formal value, an integer combination of $Q$ and the $S(j)$, so one of four linear relations among the generators holds. Each relation is nontrivial: it either states that the single generator $S(m_i)$ is $𝒪$, or gives $Q$ a coefficient $2^t$ or $2^{t+1}$, non-zero modulo the odd prime $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$. The message depends only on $(\mathrm{𝖺𝗌𝗄},\mathrm{𝗇𝗄})$ and $G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$, which are independent of $Q$ and the $S(j)$, so each relation holds with probability $1/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, and the $102$ additions cost at most $408/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$. Both scopes commit to the same message, so this event is counted once.

3. (c)

   $\mathrm{𝗂𝗏𝗄}=0$ with $\widehat{M}\ne \perp$. The addition of $[r]H_D$ is complete, and $\mathrm{𝗂𝗏𝗄}=0$ exactly when $\widehat{M}+[r]H_D=𝒪$ (Ironwood Guide, §“Fields, groups, and encodings”, Lemma “Extract vanishes only at the identity”), which, since $H_D\ne 𝒪$, holds for a single value of $r$: probability $1/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}\le \lceil 2^{512}/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}\rceil /2^{512}$.

4. (d)

   ${\mathrm{𝗂𝗏𝗄}}_{\mathrm{𝗂𝗇𝗍}}=0$ with $\widehat{M}\ne \perp$: likewise, under the independent $r^{\prime }$, with the same bound.

The sum is $\epsilon$. Negligibility alone is the Ironwood Guide’s Lemma “Rejection in key generation” (§“Viewing keys”). For $n$ accounts, apply the replacements to the $n$ paths jointly and the union bound over the $n$ keys; path nodes that are not account keys are never expanded into components and do not enter the union. □

For each key, the Ironwood Guide’s Lemma “Independence of domain-separated expansions” (§“Pseudorandom functions and field reductions”), applied after the hybrid of Lemma 2.5 has made the keys uniform; this is a reduction, as in Lemma 2.9, not the statistical-distance clause of that lemma. For the three personalisations, the Crypto Guide’s Proposition “Domain separation yields independent oracles” (§“Domain separation and personalisation”): they are pairwise distinct $16$-byte strings, and the two BLAKE2b-256 uses and the BLAKE2b-512 use differ also in the output length, a parameter of BLAKE2b. The proof of Lemma 2.5 uses the same two citations directly. □