Ironwood Guide The Zcash Orchard protocol and its Ironwood pool 2 Notation and primitive instances 4 Notes and note commitments

3 Keys and addresses

This section constructs the key components of the protocol specification, §“Orchard Key Components”, from the instances of §2: the spending key and the spend-side secrets, the viewing keys, and the diversified addresses. It states each assumption that their security needs at its first use and proves, in Proposition 3.18, four one-way separations between key tiers.

3.1 The spending key and the spend-side secrets

Remark 3.1 (Scope of the key derivations).

Every derivation of this section is that of a key generated with $\mathsf{use\_qsk}=\mathsf{false}$ , where $\mathsf{use\_qsk}$ is the Boolean key-generation flag of ZIP 2005. ZIP 2005, §“Changes to the Protocol Specification”, item §4.2.3, specifies, as a change to the specification’s §“Orchard Key Components” and not in that section itself, an alternative source of $\mathsf{ak}^{\mathbb{P}}$ and $\mathsf{r_{ivk}}$ , with $\mathsf{nk}$ derived as here; it yields components $(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})$ of the same types, and $\mathsf{ak}^{\mathbb{P}}$ again of even $y$ -coordinate. The volume does not construct the alternative and names none of its intermediate keys. Assumption 3.13, Propositions 3.18, 3.17, 6.10 and 10.6, Proposition “Confidentiality of the outgoing ciphertext” (§10.3), and the hypotheses on honest key generation of Theorems 12.9 and 12.12 are stated for $\mathsf{use\_qsk}=\mathsf{false}$ only. For such keys every key component is a deterministic function of the spending key $\mathsf{sk}$ .

Definition 3.2 (Spending key and key generation).

The spending key $\mathsf{sk}$ is a uniformly random $256$ -bit string, identified with a $32$ -byte string (protocol specification, §“Constants”). Key generation draws $\mathsf{sk}$ , derives from it the components of this section, and discards $\mathsf{sk}$ and draws a new one when $\mathsf{ask}=0$ (below), when $\mathsf{ivk}\in\{0,\bot\}$ (§3.2), or on the one further condition of the protocol specification, §“Orchard Key Components”, which concerns the internal key of ZIP 32, a key this volume does not construct, and is stated in §3.2. A spending key that key generation does not discard is accepted; it determines every other component of a key generated with $\mathsf{use\_qsk}=\mathsf{false}$ .

Construction 3.3 (Spend-side secrets).

For a spending key $\mathsf{sk}$ , the spend authorising key $\mathsf{ask}$ , the nullifier deriving key $\mathsf{nk}$ and the trapdoor $\mathsf{r_{ivk}}$ of $\mathsf{Commit}^{\mathsf{ivk}}$ are

	$\displaystyle\mathsf{ask}$	$\displaystyle:=\mathrm{ToScalar}\bigl{(}\mathsf{PRFexpand}_{\mathsf{sk}}([% \mathtt{0x06}])\bigr{)}\in\mathbb{F}_{p_{\mathsf{Vesta}}},$
	$\displaystyle\mathsf{nk}$	$\displaystyle:=\mathrm{ToBase}\bigl{(}\mathsf{PRFexpand}_{\mathsf{sk}}([% \mathtt{0x07}])\bigr{)}\in\mathbb{F}_{p_{\mathsf{Pallas}}},$
	$\displaystyle\mathsf{r_{ivk}}$	$\displaystyle:=\mathrm{ToScalar}\bigl{(}\mathsf{PRFexpand}_{\mathsf{sk}}([% \mathtt{0x08}])\bigr{)}\in\mathbb{F}_{p_{\mathsf{Vesta}}}$

(protocol specification, §“Orchard Key Components”). The three lead bytes are rows of Table 3. Key generation discards $\mathsf{sk}$ if $\mathsf{ask}=0$ .

The scalars $\mathsf{ask}$ and $\mathsf{r_{ivk}}$ lie in $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , the scalar field of the Pallas group, because each multiplies a Pallas point: $\mathsf{ask}$ the generator $G^{\mathsf{SpendAuth}}$ below, $\mathsf{r_{ivk}}$ the blinding base of $\mathsf{Commit}^{\mathsf{ivk}}$ (§3.2). The key $\mathsf{nk}$ is an element of the base field $\mathbb{F}_{p_{\mathsf{Pallas}}}$ .

The three inputs of $\mathsf{PRFexpand}_{\mathsf{sk}}$ have distinct lead bytes. By Lemma 2.15, under Assumption 2.12, the triple $(\mathsf{ask},\mathsf{nk},\mathsf{r_{ivk}})$ computed from a uniform $\mathsf{sk}$ , before rejection and before the normalisation below, is therefore computationally indistinguishable from independent uniform elements of $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , $\mathbb{F}_{p_{\mathsf{Pallas}}}$ and $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , up to an additional statistical distance of three reduction distances, each below $2^{-257}$ (§2.3).

Construction 3.4 (Spend validating key and sign normalisation).

Let $G^{\mathsf{SpendAuth}}:=\mathsf{GroupHash}(\texttt{z.cash:Orchard},\texttt{G})$ (Table 2), the generator of the spend-authorisation signature scheme (protocol specification, §“Spend Authorization Signature (Sapling and Orchard)”). For $\mathsf{ask}\neq 0$ :

1.

compute the point $P:=[\mathsf{ask}]\,G^{\mathsf{SpendAuth}}$ ;
2.

if its $y$ -coordinate is odd, that is, if bit $255$ of the star encoding $P^{\star}$ is $1$ , replace $\mathsf{ask}$ by $-\mathsf{ask}$ ;
3.

let $\mathsf{ak}^{\mathbb{P}}:=[\mathsf{ask}]\,G^{\mathsf{SpendAuth}}$ for the updated $\mathsf{ask}$ , and $\mathsf{ak}:=\mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}^{\mathbb{P}})\in\mathbb% {F}_{p_{\mathsf{Pallas}}}$ .

The spend validating key is the point $\mathsf{ak}^{\mathbb{P}}$ together with its $x$ -coordinate $\mathsf{ak}$ , a field element (protocol specification, §“Orchard Key Components”).

After step 2 the point $\mathsf{ak}^{\mathbb{P}}$ has even $y$ -coordinate. The point $P$ is not $\mathcal{O}$ , since $\mathsf{ask}\neq 0$ and $G^{\mathsf{SpendAuth}}$ generates a group of prime order, so $P=(x,y)$ with $y\neq 0$ (§2.1, on the star encoding). Replacing $\mathsf{ask}$ by $-\mathsf{ask}$ replaces $P$ by $-P=(x,-y)$ , and the representatives $y$ and $p_{\mathsf{Pallas}}-y$ have opposite parities because $p_{\mathsf{Pallas}}$ is odd.

For an accepted key, $\mathsf{ak}\in\{1,\dots,p_{\mathsf{Pallas}}-1\}$ , and $\mathsf{ak}$ determines $\mathsf{ak}^{\mathbb{P}}$ . Indeed $\mathsf{ak}^{\mathbb{P}}\neq\mathcal{O}$ , so $\mathsf{ak}\neq 0$ by Lemma 2.3. By Lemma 2.4 the points with $x$ -coordinate $\mathsf{ak}$ are $\mathsf{ak}^{\mathbb{P}}$ and $-\mathsf{ak}^{\mathbb{P}}$ , whose $y$ -coordinates have opposite parities; the point $\mathsf{ak}^{\mathbb{P}}$ is the one with even $y$ -coordinate, that is, $\mathsf{ak}^{\mathbb{P}}=\mathsf{abst}_{\mathbb{P}}(\mathrm{LE}_{256}(\mathsf{% ak}))$ , the even- $y$ lift of $\mathsf{ak}$ . Theorem 12.9 cites this normalisation.

3.2 Viewing keys

Definition 3.5 (Full viewing key).

The full viewing key of an accepted key is the triple

\mathsf{fvk}:=(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})\in\{1,\dots,p_{% \mathsf{Pallas}}-1\}\times\mathbb{F}_{p_{\mathsf{Pallas}}}\times\mathbb{F}_{p_% {\mathsf{Vesta}}},

with $\mathsf{ak}$ the field element of §3.1; the point $\mathsf{ak}^{\mathbb{P}}$ is recomputed from $\mathsf{ak}$ by the even- $y$ lift.

Construction 3.6 (Incoming viewing key scalar).

With the key commitment of §2.4 and $D:=\texttt{z.cash:Orchard-CommitIvk}$ ,

\mathsf{ivk}:=\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}}(\mathsf{ak},% \mathsf{nk})=\mathsf{ShortCommit}_{\mathsf{r_{ivk}}}\bigl{(}D,\ \mathrm{LE}_{2% 55}(\mathsf{ak})\,\|\,\mathrm{LE}_{255}(\mathsf{nk})\bigr{)}\in\mathbb{F}_{p_{% \mathsf{Pallas}}}\cup\{\bot\}.

Explicitly, let $\hat{M}$ be the Sinsemilla hash point of the $510$ -bit message $\mathrm{LE}_{255}(\mathsf{ak})\,\|\,\mathrm{LE}_{255}(\mathsf{nk})$ under the domain z.cash:Orchard-CommitIvk-M, and let

H_{D}:=\mathsf{GroupHash}(\texttt{z.cash:Orchard-CommitIvk-r},\varepsilon)

be the blinding base; then $\mathsf{ivk}=\mathsf{Extract}_{\mathbb{P}}(\hat{M}+[\mathsf{r_{ivk}}]\,H_{D})$ if $\hat{M}\neq\bot$ , and $\mathsf{ivk}=\bot$ otherwise. Key generation discards $\mathsf{sk}$ when $\mathsf{ivk}\in\{0,\bot\}$ , so an accepted key has $\mathsf{ivk}\in\{1,\dots,p_{\mathsf{Pallas}}-1\}$ . Because $p_{\mathsf{Pallas}}<p_{\mathsf{Vesta}}$ , this integer is a non-zero element of $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , the scalar that multiplies the diversified base in §3.3.

Let $X_{\mathsf{Pallas}}:=\{\mathsf{Extract}_{\mathbb{P}}(P):P\in\mathcal{E}(% \mathbb{F}_{p_{\mathsf{Pallas}}})\setminus\{\mathcal{O}\}\}\subset\{1,\dots,p_% {\mathsf{Pallas}}-1\}$ . The set $X_{\mathsf{Pallas}}$ has $(p_{\mathsf{Vesta}}-1)/2$ elements (§2.4, Definition “The key commitment”), and an accepted $\mathsf{ivk}$ lies in it. The blinding base $H_{D}$ is not $\mathcal{O}$ : the protocol specification, §“Sinsemilla commitments”, states that the commitment is distributed as a uniform point for a uniform trapdoor, which holds only for a blinding base other than $\mathcal{O}$ .

Lemma 3.7 (Distribution of $\mathsf{ivk}$ ).

Let $\mathsf{r_{ivk}}$ be uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ and independent of $(\mathsf{ak},\mathsf{nk})$ , and let $\hat{M}\neq\bot$ . Then $\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}}(\mathsf{ak},\mathsf{nk})$ is $0$ with probability $1/p_{\mathsf{Vesta}}$ and otherwise uniform on $X_{\mathsf{Pallas}}$ , independently of $(\mathsf{ak},\mathsf{nk})$ .

Proof.

By Lemma 2.26(i) the point $\hat{M}+[\mathsf{r_{ivk}}]\,H_{D}$ is uniform on $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ , whatever $\hat{M}$ is. It is $\mathcal{O}$ , of extracted coordinate $0$ , with probability $1/p_{\mathsf{Vesta}}$ ; each $x\in X_{\mathsf{Pallas}}$ is the extracted coordinate of exactly the two points $\pm P$ with $P\neq-P$ (Lemma 2.4), and so has probability $2/p_{\mathsf{Vesta}}$ . □

In particular $\mathsf{ivk}$ is not uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ (protocol specification, §“Orchard Key Components”, note).

The further rejection condition of key generation concerns the internal key of ZIP 32, §“Orchard internal key derivation”. That key has the same $\mathsf{ak}$ and $\mathsf{nk}$ and a trapdoor $t\in\mathbb{F}_{p_{\mathsf{Vesta}}}$ that is an efficiently computable function of $(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})$ , and key generation discards $\mathsf{sk}$ when its incoming viewing key $\mathsf{Commit}^{\mathsf{ivk}}_{t}(\mathsf{ak},\mathsf{nk})$ is $0$ or $\bot$ (protocol specification, §“Orchard Key Components”).

Lemma 3.8 (Rejection in key generation).

Under Assumptions 2.22 and 2.8, a single draw of key generation from independent uniform $(\mathsf{ask},\mathsf{nk},\mathsf{r_{ivk}})$ is rejected with negligible probability. Under Assumptions 2.12, 2.22 and 2.8, the output of key generation is within negligible statistical distance of a single draw from a uniform $\mathsf{sk}$ without rejection.

Proof.

A single draw is rejected only if $\mathsf{ask}=0$ , of probability $1/p_{\mathsf{Vesta}}$ ; or $\hat{M}=\bot$ ; or $\mathsf{ivk}=0$ , of probability $1/p_{\mathsf{Vesta}}$ by Lemma “Distribution of $\mathsf{ivk}$ ”; or $\mathsf{Commit}^{\mathsf{ivk}}_{t}(\mathsf{ak},\mathsf{nk})=0$ . The value $\mathsf{Commit}^{\mathsf{ivk}}_{t}(\mathsf{ak},\mathsf{nk})$ commits to the message of $\mathsf{ivk}$ , so it is $\bot$ exactly when $\hat{M}=\bot$ . The event $\hat{M}=\bot$ has negligible probability under Assumptions 2.22 and 2.8: an algorithm that samples $(\mathsf{ask},\mathsf{nk})$ and outputs the message $\mathrm{LE}_{255}(\mathsf{ak})\,\|\,\mathrm{LE}_{255}(\mathsf{nk})$ finds a $\bot$ input with that probability, which Proposition 2.24(iii) bounds. For $\hat{M}\neq\bot$ , $\mathsf{Commit}^{\mathsf{ivk}}_{t}(\mathsf{ak},\mathsf{nk})=0$ exactly when $\hat{M}+[t]\,H_{D}=\mathcal{O}$ (Lemma 2.3). By (1), with $n=51$ (Table 4), this is a relation among $Q(\texttt{z.cash:Orchard-CommitIvk-M})$ , the $S(j)$ and $H_{D}$ whose coefficient on the first is $2^{51}$ , non-zero modulo $p_{\mathsf{Vesta}}$ . An algorithm that samples $(\mathsf{ask},\mathsf{nk},\mathsf{r_{ivk}})$ , computes $t$ and outputs this relation succeeds with the probability of the event, which the lemma on relations among fixed generators (§2.4) bounds under the same assumptions. The rejection event is efficiently decidable from the three outputs of $\mathsf{PRFexpand}_{\mathsf{sk}}$ , so by Lemma 2.15 a first draw from a uniform $\mathsf{sk}$ is also rejected with negligible probability. Key generation outputs its first draw whenever that draw is accepted; its output is therefore within that negligible probability, in statistical distance, of a single draw without rejection. □

The proofs of this section analyse a single draw and add the statistical distance bounded by this lemma, under Assumptions 2.12, 2.22 and 2.8.

Construction 3.9 (Diversifier key and outgoing viewing key).

Let $K:=\mathrm{LE}_{256}(\mathsf{r_{ivk}})$ and

R:=\mathsf{PRFexpand}_{K}\bigl{(}[\mathtt{0x82}]\,\|\,\mathsf{I2LEOSP}_{256}(% \mathsf{ak})\,\|\,\mathsf{I2LEOSP}_{256}(\mathsf{nk})\bigr{)},

a $64$ -byte string, where $\mathsf{I2LEOSP}_{256}$ encodes the field elements $\mathsf{ak}$ and $\mathsf{nk}$ as $32$ -byte little-endian integers. The diversifier key $\mathsf{dk}$ is the first $32$ bytes of $R$ and the outgoing viewing key $\mathsf{ovk}$ the last $32$ bytes (protocol specification, §“Orchard Key Components”; row $\mathtt{0x82}$ of Table 3). One output of $\mathsf{PRFexpand}$ , keyed by the encoding of $\mathsf{r_{ivk}}$ , yields both.

Definition 3.10 (Incoming and outgoing viewing keys).

The incoming viewing key is the pair $(\mathsf{dk},\mathsf{ivk})$ ; the outgoing viewing key is $\mathsf{ovk}$ . The diversifier key $\mathsf{dk}$ derives diversifiers (§3.3). What the holders of $\mathsf{ivk}$ and of $\mathsf{ovk}$ can compute from note ciphertexts is stated in “Trial decryption and note acceptance” (§10.4) and “The outgoing ciphertext” (§10.3).

Proposition 3.11 (Binding of $\mathsf{ivk}$ to $(\mathsf{ak},\mathsf{nk})$ ).

Under Assumptions 2.22 and 2.8, no efficient algorithm outputs, except with negligible probability, triples $(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})\neq(\mathsf{ak}^{\prime},\mathsf{nk% }^{\prime},\mathsf{r_{ivk}}^{\prime})$ with $\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}}(\mathsf{ak},\mathsf{nk})=% \mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}^{\prime}}(\mathsf{ak}^{\prime% },\mathsf{nk}^{\prime})\neq\bot$ .

Proof.

Equal extracted values come from commitment points $C$ , $C^{\prime}$ with $C=\pm C^{\prime}$ (Lemma 2.4). If the messages differ, both cases are excluded by Proposition 2.24(ii), since $\mathrm{LE}_{255}$ is injective on integer representatives. If the messages agree, then $\mathsf{r_{ivk}}\neq\mathsf{r_{ivk}}^{\prime}$ , the case $C=C^{\prime}$ gives $[\mathsf{r_{ivk}}-\mathsf{r_{ivk}}^{\prime}]\,H_{D}=\mathcal{O}$ , impossible for $H_{D}\neq\mathcal{O}$ in a group of prime order, and the case $C=-C^{\prime}$ is excluded by the same proposition. □

Hence $\mathsf{ivk}$ is bound to the pair $(\mathsf{ak},\mathsf{nk})$ , and so is every address of the key (§3.3): its transmission key $\mathsf{pk_{d}}=[\mathsf{ivk}]\,\mathsf{g_{d}}$ with $\mathsf{g_{d}}\neq\mathcal{O}$ determines $\mathsf{ivk}$ , an integer below $p_{\mathsf{Vesta}}$ . The binding is used in Lemma 12.5 (“Double-spend resistance”, §12.2) and Theorem 12.9 (“Authorisation of spends”, §12.3). Binding alone would follow from any collision-resistant hash of $(\mathsf{ak},\mathsf{nk})$ ; the trapdoor $\mathsf{r_{ivk}}$ adds hiding.

Remark 3.12 (Hiding of $\mathsf{ivk}$ and the double use of $\mathsf{r_{ivk}}$ ).

For $\mathsf{r_{ivk}}$ uniform and independent of every other quantity, $\mathsf{ivk}$ is independent of $(\mathsf{ak},\mathsf{nk})$ by Lemma “Distribution of $\mathsf{ivk}$ ”. The derivation of $(\mathsf{dk},\mathsf{ovk})$ is keyed by the same $\mathsf{r_{ivk}}$ , so once $\mathsf{dk}$ or $\mathsf{ovk}$ is known that argument no longer applies, and modelling $\mathsf{PRFexpand}$ only as a PRF does not restore it: the key of row $\mathtt{0x82}$ is also the trapdoor of $\mathsf{Commit}^{\mathsf{ivk}}$ , outside the hypothesis of Lemma 2.15 (§2.3; protocol specification, §“Orchard Key Components”, note on the use of $\mathsf{r_{ivk}}$ as both trapdoor and key). The volume states the joint assumption on Pallas scalar multiplication and $\mathsf{PRFexpand}$ that the specification proposes as Assumption 3.13.

Assumption 3.13 (Joint hiding of the viewing keys).

For keys with $\mathsf{use\_qsk}=\mathsf{false}$ : for every $(\mathsf{ak},\mathsf{nk})\in\{1,\dots,p_{\mathsf{Pallas}}-1\}\times\mathbb{F}_% {p_{\mathsf{Pallas}}}$ , given to the distinguisher, and $\mathsf{r_{ivk}}$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , the triple $(\mathsf{ivk},\mathsf{dk},\mathsf{ovk})$ computed from $(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})$ by the constructions of this subsection is computationally indistinguishable from

\bigl{(}\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}^{\prime}}(\mathsf{ak}% ,\mathsf{nk}),\,u_{1},\,u_{2}\bigr{)},

where $\mathsf{r_{ivk}}^{\prime}$ is uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ and $u_{1}$ , $u_{2}$ are uniform $32$ -byte strings, all independent. It is a precise form of the joint assumption that the protocol specification proposes (§“Orchard Key Components”, note); it is not perfect hiding. Results apply it after Lemma 2.15 (Assumption 2.12) has made $\mathsf{r_{ivk}}$ uniform and independent of $(\mathsf{ask},\mathsf{nk})$ , averaging over the key-generation distribution of $(\mathsf{ak},\mathsf{nk})$ . It is used by Propositions 3.18, 3.17, 6.10 and 10.6, by Proposition “Confidentiality of the outgoing ciphertext” (§10.3) and by Theorem 12.12.

3.3 Diversified addresses

Construction 3.14 (Diversified address).

For an index $j\in\{0,\dots,2^{88}-1\}$ chosen by the key holder:

1.

the diversifier is $d:=\mathsf{FF1\text{-}AES256}_{\mathsf{dk}}(\mathrm{LE}_{88}(j))\in\{0,1\}^{88}$ , the FF1 mode of NIST SP 800-38G over AES-256 with key $\mathsf{dk}$ , radix $2$ , length $88$ and the empty tweak (Crypto Guide, §“Format-preserving encryption and FF1”, Construction “The FF1 mode of NIST SP 800-38G”; protocol specification, §“Pseudo Random Permutations”);
2.

the diversified base is $\mathsf{g_{d}}:=\mathsf{DiversifyHash}(d)$ , where

$T:=\mathsf{GroupHash}\bigl{(}\texttt{z.cash:Orchard-gd},\ \mathsf{LEBS2OSP}_{8% 8}(d)\bigr{)}$

and

$\mathsf{DiversifyHash}(d):=\begin{cases}T&\text{if }T\neq\mathcal{O},\\ \mathsf{GroupHash}(\texttt{z.cash:Orchard-gd},\varepsilon)&\text{otherwise}% \end{cases}$

(protocol specification, §“ $\mathsf{DiversifyHash}^{\mathsf{Sapling}}$ and $\mathsf{DiversifyHash}^{\mathsf{Orchard}}$ Hash Functions”);
3.

the diversified transmission key is $\mathsf{pk_{d}}:=[\mathsf{ivk}]\,\mathsf{g_{d}}$ , with $\mathsf{ivk}$ read as a scalar (§2.1).

The address is $(d,\mathsf{pk_{d}})\in\{0,1\}^{88}\times(\mathcal{E}(\mathbb{F}_{p_{\mathsf{% Pallas}}})\setminus\{\mathcal{O}\})$ (protocol specification, §“Orchard Key Components”).

The map $\mathsf{LEBS2OSP}_{88}$ packs $d$ into $11$ bytes, eight bits at a time, least significant bit first (§2.1). Every index yields an address. The map $\mathsf{GroupHash}$ returns a point for every input, and $\mathsf{DiversifyHash}$ replaces the identity by the fixed fallback point, which is not the identity: the protocol specification types $\mathsf{DiversifyHash}^{\mathsf{Orchard}}$ into the non-identity points. The fallback case has negligible probability under Assumption 2.8. Hence $\mathsf{g_{d}}\neq\mathcal{O}$ for every $d$ , and $\mathsf{pk_{d}}\neq\mathcal{O}$ because $\mathsf{ivk}$ is a non-zero scalar and the group has prime order. For each key $\mathsf{dk}$ the map $j\mapsto d$ is a permutation of the $88$ -bit strings (Crypto Guide, §“Format-preserving encryption and FF1”, Proposition “FF1 is a keyed bijection on $\mathcal{X}$ ”), so distinct indices give distinct diversifiers: one incoming viewing key $(\mathsf{dk},\mathsf{ivk})$ yields $2^{88}$ distinct addresses, all with transmission keys under the same $\mathsf{ivk}$ . No index is excluded.

Assumption 3.15 (FF1-AES256 as a pseudorandom permutation).

For a uniform $256$ -bit key, $\mathsf{FF1\text{-}AES256}$ with the empty tweak on $\{0,1\}^{88}$ is a pseudorandom permutation: no efficient adversary with oracle access distinguishes it from a uniformly random permutation of $\{0,1\}^{88}$ (Crypto Guide, §“Pseudorandom functions and permutations”, Definition “Pseudorandom permutation”, and §“Format-preserving encryption and FF1”, Definition “Format-preserving encryption”). It is the security requirement of the protocol specification, §“Pseudo Random Permutations”, whose note records that the distinguishing attack of Dunkelman, Kumar, Lambooij and Sanadhya at this domain size and round count is no better than exhaustive search for the $256$ -bit key. It is used so that a diversifier reveals neither its index nor the key that produced it, in Proposition 3.17 (“Unlinkability of diversified addresses”).

Assumption 3.16 (DDH on Pallas).

Let $P$ be a generator of $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ , let $b$ and $c$ be uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ and $a$ uniform on $X_{\mathsf{Pallas}}$ (§3.2), all independent. The triples $([a]P,[b]P,[ab]P)$ and $([a]P,[b]P,[c]P)$ are computationally indistinguishable. With $a$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ instead, this is the DDH assumption of the Crypto Guide (§“Diffie–Hellman: computational and decisional”, Definition “Decisional Diffie–Hellman, DDH”). The volume assumes the form with $a$ uniform on $X_{\mathsf{Pallas}}$ because $\mathsf{ivk}$ is so distributed, and claims no reduction between the two forms; the protocol specification expects the non-uniformity of $\mathsf{ivk}$ to cause no security issue (§“Orchard Key Components”, note). It is used by Propositions 3.17 and 10.6 (“Confidentiality and key privacy of note encryption”).

Proposition 3.17 (Unlinkability of diversified addresses).

Let two keys be generated independently with $\mathsf{use\_qsk}=\mathsf{false}$ . An adversary holds $\mathsf{ak}$ , $\mathsf{nk}$ and $\mathsf{ovk}$ of both keys, and none of $\mathsf{r_{ivk}}$ , $\mathsf{dk}$ and $\mathsf{ivk}$ of either. It chooses indices $j_{0}$ , $j_{1}$ and $j^{\prime}$ with $j^{\prime}\notin\{j_{0},j_{1}\}$ , and receives the address of key $0$ at index $j_{0}$ , the address of key $1$ at index $j_{1}$ , and the address of key $\beta$ at index $j^{\prime}$ , for a uniform hidden bit $\beta$ ; it outputs a bit $\beta^{\prime}$ . Conditioned on the event $E$ that the three diversifiers are pairwise distinct, its advantage $\bigl{|}\mathrm{Pr}[\beta^{\prime}=1\mid\beta=0]-\mathrm{Pr}[\beta^{\prime}=1% \mid\beta=1]\bigr{|}$ is negligible under Assumptions 2.12 (through Lemma 2.15), 3.13, 3.15, 2.8 and 3.16, together with Assumption 2.22 for Lemma “Rejection in key generation”. This is the unlinkability requirement of the protocol specification, §“ $\mathsf{DiversifyHash}^{\mathsf{Sapling}}$ and $\mathsf{DiversifyHash}^{\mathsf{Orchard}}$ Hash Functions”, which stipulates distinct diversifiers.

Proof.

For each $\beta$ the game is modified by a sequence of hops, each changing the adversary’s output distribution by a negligible amount (Crypto Guide, §“The hybrid argument”, Lemma “Hybrid lemma”). Each hop is justified by a reduction that runs the game; the event $E$ is efficiently decidable from the diversifiers and has probability at least $1/2$ in every game below, so conditioning on $E$ at most doubles each cost.

1.

Each key is replaced by a single draw without rejection (Lemma “Rejection in key generation”, §3.2).
2.

For each key in turn, $(\mathsf{ask},\mathsf{nk},\mathsf{r_{ivk}})$ is replaced by independent uniform elements of the three fields (Lemma 2.15); the reduction derives the remaining components and the addresses.
3.

For each key in turn, $(\mathsf{ivk},\mathsf{dk},\mathsf{ovk})$ is replaced by $(\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}^{\prime}}(\mathsf{ak},% \mathsf{nk}),u_{1},u_{2})$ (Assumption 3.13); the reduction is given $(\mathsf{ak},\mathsf{nk})$ , generates the other key itself, and computes the game from the triple. Now $\mathsf{dk}$ and $\mathsf{ovk}$ are uniform and independent of all else, and, except on the negligible events $\mathsf{ivk}\in\{0,\bot\}$ , the scalar $\mathsf{ivk}$ is uniform on $X_{\mathsf{Pallas}}$ and independent of $(\mathsf{ak},\mathsf{nk})$ (Lemmas “Distribution of $\mathsf{ivk}$ ” and “Rejection in key generation”, §3.2).
4.

For $b\in\{0,1\}$ in turn, $\mathsf{FF1\text{-}AES256}_{\mathsf{dk}_{b}}$ is replaced by a uniformly random permutation $\pi_{b}$ of $\{0,1\}^{88}$ (Assumption 3.15); the reduction queries its oracle at the indices it needs. Then $d^{\prime}=\pi_{\beta}(\mathrm{LE}_{88}(j^{\prime}))\neq d_{\beta}$ because $j^{\prime}\neq j_{\beta}$ , and on $E$ the triple $(d_{0},d_{1},d^{\prime})$ is uniform on pairwise distinct triples, for either value of $\beta$ . The event $E$ fails only if $d_{1-\beta}$ equals $d_{\beta}$ or $d^{\prime}$ , of probability $2/2^{88}$ .
5.

On $E$ the inputs $\mathsf{LEBS2OSP}_{88}(d)$ of $\mathsf{GroupHash}$ are distinct, since $\mathsf{LEBS2OSP}_{88}$ is injective, so under Assumption 2.8 the bases $g_{0}$ , $g_{1}$ , $g^{\prime}$ are independent uniform points, each $\mathcal{O}$ , which invokes the fallback, with probability $1/p_{\mathsf{Vesta}}$ only.

In the last game the adversary’s view consists of $\mathsf{ak}$ , $\mathsf{nk}$ , $\mathsf{ovk}$ of both keys and $(d_{0},d_{1},d^{\prime})$ , independent of the rest and identically distributed for $\beta=0,1$ , together with

(g_{0},[\mathsf{ivk}_{0}]\,g_{0}),\qquad(g_{1},[\mathsf{ivk}_{1}]\,g_{1}),% \qquad(g^{\prime},[\mathsf{ivk}_{\beta}]\,g^{\prime}),

where $\mathsf{ivk}_{0}$ , $\mathsf{ivk}_{1}$ are independent and uniform on $X_{\mathsf{Pallas}}$ . The first two pairs are public keys of the per-key-base ElGamal scheme with private keys $\mathsf{ivk}_{0}$ and $\mathsf{ivk}_{1}$ . For $g_{\beta}\neq\mathcal{O}$ the uniform point $g^{\prime}$ equals $[r]\,g_{\beta}$ for a uniform scalar $r$ , so the third pair is $([r]\,g_{\beta},[r]([\mathsf{ivk}_{\beta}]\,g_{\beta}))$ , an encryption of $\mathcal{O}$ under key $\beta$ (Crypto Guide, §“Key privacy”, Construction “ElGamal encryption”). Distinguishing $\beta$ is therefore the game of Definition “Key privacy under chosen-plaintext attack, IK-CPA” of the same subsection, for the message $\mathcal{O}$ . The proof of its Theorem “ElGamal is key-private under DDH” bounds the advantage by two DDH advantages. That proof plants the first exponent of the DDH triple as a private key; with private keys uniform on $X_{\mathsf{Pallas}}$ , the same proof, with the other key’s private key drawn uniformly from $X_{\mathsf{Pallas}}$ (the $x$ -coordinate of a uniform non-identity point), reduces to Assumption 3.16. Its reduction samples $(d_{0},d_{1},d^{\prime})$ itself and programs $\mathsf{GroupHash}$ at their three inputs with the planted bases before running the adversary. The Crypto Guide’s Remark “What key privacy buys upstairs” records this correspondence for diversified addresses. Summing the costs of the hops, the advantage is negligible. □

3.4 Key capabilities and scope

Figure 1 gives the derivation graph, each edge labelled by its operation, and each one-way edge also by the assumption that makes it one-way. Proposition 3.18 proves four separations: the full viewing key yields no $\mathsf{ask}$ , the incoming viewing key neither $\mathsf{nk}$ nor $\mathsf{ask}$ , the outgoing viewing key no $\mathsf{ivk}$ , and an address no $\mathsf{ivk}$ .

Refer to caption — Figure 1: Derivation graph of a key generated with $\mathsf{use\_qsk}=\mathsf{false}$ , from the spending key $\mathsf{sk}$ to the address $(d,\mathsf{pk_{d}})$ . Each edge carries its operation, and each one-way edge also carries, in brackets, the assumption under which it is one-way: PRF, Assumption 2.12; DL, Assumption 2.22; JH, Assumption 3.13; RO, Assumption 2.8. Each one-way edge is a PRF call, a scalar multiplication, the joint hiding assumption or $\mathsf{GroupHash}$ as a random oracle; bundling edges invert by projection, $\mathsf{Extract}_{\mathbb{P}}$ by the even- $y$ lift, and the FF1 edge is inverted by the holder of $\mathsf{dk}$ . The edges out of $\mathsf{sk}$ are one-way under Assumption 2.12, since an algorithm recovering $\mathsf{sk}$ from $(\mathsf{ask},\mathsf{nk},\mathsf{r_{ivk}})$ distinguishes $\mathsf{PRFexpand}_{\mathsf{sk}}$ from a random function. Colours give the lowest key tier that computes a node; the index $j$ is uncoloured. The dashed edges into $\mathsf{ak}^{\mathbb{P}}$ and $\mathsf{r_{ivk}}$ mark the alternative source of ZIP 2005, not constructed. Markers (a) to (d) are the four separations that Proposition 3.18 proves; no other separation is claimed.

Proposition 3.18 (Capability separation).

Let a key be generated honestly with $\mathsf{use\_qsk}=\mathsf{false}$ . No efficient algorithm, given the public parameters and only the listed key material of the key, outputs the listed secret, except with negligible probability:

(a)

given the full viewing key $(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})$ , the scalar $\mathsf{ask}$ ;
(b)

given the incoming viewing key $(\mathsf{dk},\mathsf{ivk})$ , the key $\mathsf{nk}$ or the scalar $\mathsf{ask}$ ;
(c)

given $\mathsf{ovk}$ , the scalar $\mathsf{ivk}$ ;
(d)

given an address $(d,\mathsf{pk_{d}})$ of the key, the scalar $\mathsf{ivk}$ .

The hypotheses are: for (a), Assumptions 2.12 (through Lemma 2.15) and 2.22; for (b), those of (a) and, for $\mathsf{nk}$ , Assumption 3.13; for (c), Assumptions 2.12 and 3.13; for (d), Assumptions 2.12, 3.13, 2.8 and 2.22 (“Discrete logarithms on Pallas”). Every part also uses Lemma “Rejection in key generation” (§3.2), under Assumptions 2.12, 2.22 and 2.8. These are the only separations claimed.

Proof.

By Lemma “Rejection in key generation” (§3.2), a single draw from a uniform $\mathsf{sk}$ replaces the key at a negligible cost. By Lemma 2.15, its triple $(\mathsf{ask},\mathsf{nk},\mathsf{r_{ivk}})$ is then replaced by independent uniform elements of $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , $\mathbb{F}_{p_{\mathsf{Pallas}}}$ and $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , at a further negligible cost: in each part the success of an algorithm is efficiently decidable from the three values, by deriving the remaining components, running the algorithm and comparing its output with the secret. The result is called the idealised key.

(a) Let an algorithm $\mathcal{A}$ output $\mathsf{ask}$ from $(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})$ with probability $\epsilon$ for the idealised key. An algorithm $\mathcal{B}$ receives $Y=[s]\,G^{\mathsf{SpendAuth}}$ for $s$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , draws $\mathsf{nk}$ and $\mathsf{r_{ivk}}$ uniformly, and runs $\mathcal{A}$ on $(\mathsf{Extract}_{\mathbb{P}}(Y),\mathsf{nk},\mathsf{r_{ivk}})$ . The input is distributed as for the idealised key, because the sign normalisation replaces $\mathsf{ask}$ by $\pm\mathsf{ask}$ and does not change $\mathsf{ak}$ (Lemma 2.4). A correct output $a$ satisfies $[a]\,G^{\mathsf{SpendAuth}}=\mathsf{ak}^{\mathbb{P}}$ , the even- $y$ lift of $\mathsf{Extract}_{\mathbb{P}}(Y)$ , which is $Y$ or $-Y$ ; $\mathcal{B}$ outputs whichever of $a$ and $-a$ maps to $Y$ . Hence $\mathcal{B}$ computes discrete logarithms to the generator $G^{\mathsf{SpendAuth}}$ with probability $\epsilon$ , and $\epsilon$ is negligible by Assumption 2.22.

(b) An algorithm that computes $\mathsf{ask}$ from $(\mathsf{dk},\mathsf{ivk})$ computes it from $(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})$ by first deriving $(\mathsf{dk},\mathsf{ivk})$ , so (a) applies. Let $\mathcal{A}$ output $\mathsf{nk}$ from $(\mathsf{dk},\mathsf{ivk})$ with probability $\epsilon$ . A distinguisher for Assumption 3.13, given $(\mathsf{ak},\mathsf{nk})$ of the idealised key and a triple $(x,y,z)$ , runs $\mathcal{A}$ on $(y,x)$ and outputs $1$ exactly when $\mathcal{A}$ outputs $\mathsf{nk}$ . On the real triple it outputs $1$ with probability $\epsilon$ . On the ideal triple $\mathcal{A}$ receives $u_{1}$ and $\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}^{\prime}}(\mathsf{ak},\mathsf% {nk})$ , which is independent of $\mathsf{nk}$ unless $\hat{M}=\bot$ , a negligible event (Lemma “Rejection in key generation”); since $\mathsf{nk}$ is uniform on $\mathbb{F}_{p_{\mathsf{Pallas}}}$ , $\mathcal{A}$ then succeeds with probability at most $1/p_{\mathsf{Pallas}}$ plus a negligible term. So $\epsilon$ exceeds the distinguisher’s advantage by a negligible amount at most.

(c) Let $\mathcal{A}$ output $\mathsf{ivk}$ from $\mathsf{ovk}$ with probability $\epsilon$ . The distinguisher given $(\mathsf{ak},\mathsf{nk})$ and $(x,y,z)$ runs $\mathcal{A}$ on $z$ and outputs $1$ exactly when $\mathcal{A}$ outputs $x$ . On the ideal triple, $z=u_{2}$ is independent of $x=\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}^{\prime}}(\mathsf{ak},% \mathsf{nk})$ , which, for $\hat{M}\neq\bot$ , takes each value with probability at most $2/p_{\mathsf{Vesta}}$ by Lemma “Distribution of $\mathsf{ivk}$ ”. Hence $\epsilon$ is at most the advantage under Assumption 3.13 plus $2/p_{\mathsf{Vesta}}$ and a negligible term.

(d) Let $\mathcal{A}$ output $\mathsf{ivk}$ from the address at an index $j$ , possibly of its choice, with probability $\epsilon$ . The distinguisher given $(\mathsf{ak},\mathsf{nk})$ and $(x,y,z)$ computes $d:=\mathsf{FF1\text{-}AES256}_{y}(\mathrm{LE}_{88}(j))$ , $\mathsf{g_{d}}:=\mathsf{DiversifyHash}(d)$ and $\mathsf{pk_{d}}:=[x]\,\mathsf{g_{d}}$ , runs $\mathcal{A}$ on $(d,\mathsf{pk_{d}})$ , and outputs $1$ exactly when $\mathcal{A}$ outputs $x$ . On the ideal triple, $\mathcal{A}$ succeeds with probability $\epsilon^{\prime}\geq\epsilon-\delta$ , for $\delta$ the advantage under Assumption 3.13; there, outside the negligible event $\hat{M}=\bot$ , the value $\mathsf{ivk}:=x$ is $0$ with probability $1/p_{\mathsf{Vesta}}$ and otherwise uniform on $X_{\mathsf{Pallas}}$ , independently of $(\mathsf{ak},\mathsf{nk})$ and of $u_{1}$ , hence of $d$ . An algorithm $\mathcal{B}$ receives a generator $G$ and $Y=[s]\,G$ for $s$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ . It draws $t$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}\setminus\{0\}$ and $u_{1}$ uniform, computes $d$ from $u_{1}$ and $j$ , programs $\mathsf{GroupHash}$ at $(\texttt{z.cash:Orchard-gd},\mathsf{LEBS2OSP}_{88}(d))$ with the uniform non-identity point $[t]\,G$ (Assumption 2.8), answers other queries with fresh uniform points, and runs $\mathcal{A}$ on $(d,[t]\,Y)=(d,[s]([t]\,G))$ . With probability $(p_{\mathsf{Vesta}}-1)/(2p_{\mathsf{Vesta}})$ the exponent $s$ lies in $X_{\mathsf{Pallas}}$ ; it is then uniform on $X_{\mathsf{Pallas}}$ , and the view of $\mathcal{A}$ is that of the ideal triple conditioned on $\mathsf{ivk}\neq 0$ , up to statistical distance $1/p_{\mathsf{Vesta}}$ for the programmed point. Algorithm $\mathcal{B}$ outputs the output of $\mathcal{A}$ and so computes $s$ with probability at least

\frac{p_{\mathsf{Vesta}}-1}{2p_{\mathsf{Vesta}}}\Bigl{(}\epsilon^{\prime}-% \frac{2}{p_{\mathsf{Vesta}}}\Bigr{)},

a loss factor of $2p_{\mathsf{Vesta}}/(p_{\mathsf{Vesta}}-1)$ , about $2$ , against Assumption 2.22. Hence $\epsilon^{\prime}$ , and with it $\epsilon$ , is negligible. □

Of the objects of this section only an address $(d,\mathsf{pk_{d}})$ , with the base $\mathsf{g_{d}}$ computed from $d$ , is public; $\mathsf{sk}$ , $\mathsf{ask}$ , $\mathsf{ak}^{\mathbb{P}}$ , $\mathsf{ak}$ , $\mathsf{nk}$ , $\mathsf{r_{ivk}}$ , the full viewing key, $\mathsf{dk}$ , $\mathsf{ivk}$ , $\mathsf{ovk}$ and the index $j$ are secret key material. One incoming viewing key yields $2^{88}$ addresses (§3.3), unlinkable in the sense of Proposition 3.17 (“Unlinkability of diversified addresses”).

What a holder of each key can compute from the objects of later sections is stated where those objects are constructed, each with a back-reference to Proposition 3.18: from nullifiers in “Nullifier uniqueness and unlinkability” (§6.4), and from note ciphertexts in “The outgoing ciphertext” (§10.3) and “Trial decryption and note acceptance” (§10.4). This section states no such power.

Keys and addresses are objects of the Orchard protocol, not of a pool: one key hierarchy and one address format serve both the Orchard pool and the Ironwood pool (ZIP 229, Abstract).