Ironwood Guide The Zcash Orchard protocol and its Ironwood pool 5 The note commitment tree 7 Spend authorisation

6 Nullifiers

This section constructs the nullifier of a note, the nullifier sets that consensus maintains per pool, and the rule that makes the nullifier of each consumed note the element $\rho$ of the note created in the same Action. It proves two properties of the construction: uniqueness, from discrete logarithms on Pallas with $\mathsf{GroupHash}$ modelled as a random oracle; and, for keys generated with $\mathsf{use\_qsk}=\mathsf{false}$ , unlinkability, from these two assumptions, the pseudorandomness of Poseidon and of PRF expansion, and the joint hiding of the viewing keys. It also states what each key tier can compute from nullifiers.

6.1 The nullifier

Requirement R3 of “Requirements on a shielded payment” (§1.4) excludes a second consumption of a note without a public list of consumed notes. Each note therefore determines a nullifier, a tag published when the note is consumed, and a verifier (§1.2) rejects a nullifier already in the nullifier set of its pool (§6.2). The construction must make the nullifier

(a)

deterministic: a function of the note and of the nullifier deriving key $\mathsf{nk}$ of the key that owns it, so that a second consumption publishes the same value; and
(b)

unlinkable: to a party without $\mathsf{nk}$ , the published value reveals nothing about the note’s commitment or address.

Construction 6.1 (Nullifier PRF).

Let $f\colon\mathbb{F}_{p_{\mathsf{Pallas}}}^{3}\to\mathbb{F}_{p_{\mathsf{Pallas}}}% ^{3}$ be the Poseidon permutation of width $t=3$ over the Pallas base field, used as a sponge of rate $2$ and capacity $1$ , with S-box $x\mapsto x^{5}$ , $8$ full and $56$ partial rounds (Crypto Guide, §“Arithmetisation-friendly hashing: Poseidon”, Constructions “The sponge construction” and “The Poseidon permutation”, Example “The Orchard Poseidon instance”). Its round constants and MDS matrix are those of the protocol specification, §“ $\mathsf{PoseidonHash}$ Function”, and are not reproduced. In constant-input-length mode the hash $\mathsf{PoseidonHash}\colon\mathbb{F}_{p_{\mathsf{Pallas}}}\times\mathbb{F}_{p% _{\mathsf{Pallas}}}\to\mathbb{F}_{p_{\mathsf{Pallas}}}$ is

\mathsf{PoseidonHash}(x,y):=\pi_{1}\bigl{(}f(x,y,2^{65})\bigr{)},

where $\pi_{1}$ is the projection onto the first component; the capacity element $2^{65}$ encodes the input length $2$ , so no padding is needed (same citations). The nullifier PRF is

\mathsf{PRF}^{\mathsf{nfOrchard}}\colon\mathbb{F}_{p_{\mathsf{Pallas}}}\times% \mathbb{F}_{p_{\mathsf{Pallas}}}\to\mathbb{F}_{p_{\mathsf{Pallas}}},\qquad% \mathsf{PRF}^{\mathsf{nfOrchard}}_{\mathsf{nk}}(\rho):=\mathsf{PoseidonHash}(% \mathsf{nk},\rho),

keyed by the nullifier deriving key $\mathsf{nk}\in\mathbb{F}_{p_{\mathsf{Pallas}}}$ of “The spending key and the spend-side secrets” (§3.1; protocol specification, §“Pseudo Random Functions”).

Assumption 6.2 (Poseidon is a PRF).

For $\mathsf{nk}$ uniform on $\mathbb{F}_{p_{\mathsf{Pallas}}}$ , no efficient adversary with adaptive oracle access distinguishes $\rho\mapsto\mathsf{PoseidonHash}(\mathsf{nk},\rho)$ from a uniformly random function $\mathbb{F}_{p_{\mathsf{Pallas}}}\to\mathbb{F}_{p_{\mathsf{Pallas}}}$ , except with negligible advantage: this is the game of Definition “Pseudorandom function” (§2.3; Crypto Guide, §“Pseudorandom functions and permutations”) with key, input and output sets $\mathbb{F}_{p_{\mathsf{Pallas}}}$ . It is the security requirement that the protocol specification, §“Pseudo Random Functions”, places on $\mathsf{PoseidonHash}$ keyed by its first argument. Its status is cryptanalytic: it is supported by the analysis of the Poseidon round function (protocol specification, §“ $\mathsf{PoseidonHash}$ Function”, notes) and has no reduction to a standard problem (Crypto Guide, Example “The Orchard Poseidon instance”). Of the results of this section only Proposition 6.10 uses it; Proposition 6.8 uses no property of $\mathsf{PoseidonHash}$ , and the volume proves no unlinkability result for nullifiers without this assumption.

Definition 6.3 (Nullifier).

Let $K^{\mathsf{Orchard}}:=\mathsf{GroupHash}(\texttt{z.cash:Orchard},\texttt{K})$ , the nullifier base, a fixed generator of Table 2. For $\mathsf{nk},\rho,\psi\in\mathbb{F}_{p_{\mathsf{Pallas}}}$ and a point $\mathsf{cm}\in\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ ,

\mathsf{DeriveNullifier}_{\mathsf{nk}}(\rho,\psi,\mathsf{cm}):=\mathsf{Extract% }_{\mathbb{P}}\bigl{(}[s]\,K^{\mathsf{Orchard}}+\mathsf{cm}\bigr{)}\in\mathbb{% F}_{p_{\mathsf{Pallas}}},

where

s:=\bigl{(}\mathsf{PRF}^{\mathsf{nfOrchard}}_{\mathsf{nk}}(\rho)+\psi\bigr{)}% \bmod p_{\mathsf{Pallas}}\in\{0,\dots,p_{\mathsf{Pallas}}-1\}:

the sum of the two field elements is taken as its representative in $\{0,\dots,p_{\mathsf{Pallas}}-1\}$ , and that integer multiplies $K^{\mathsf{Orchard}}$ . The nullifier of a note $n=(\mathsf{addr},v,\rho,\psi,\mathsf{rcm})$ whose note commitment $\mathsf{cm}$ (Definition 4.4) is not $\bot$ , under the nullifier deriving key $\mathsf{nk}$ of the key that owns $\mathsf{addr}$ , is

\mathsf{nf}:=\mathsf{DeriveNullifier}_{\mathsf{nk}}(\rho,\psi,\mathsf{cm})

(protocol specification, §“Computing $\rho$ values and Nullifiers”).

Remark 6.4 (Reduction modulo $p_{\mathsf{Pallas}}$ ).

The protocol specification attaches two notes to the definition (§“Computing $\rho$ values and Nullifiers”). First, the sum is reduced modulo $p_{\mathsf{Pallas}}$ intentionally, although the scalar field of the Pallas group is $\mathbb{F}_{p_{\mathsf{Vesta}}}$ . Since $p_{\mathsf{Pallas}}<p_{\mathsf{Vesta}}$ (§2.1), the representative in $\{0,\dots,p_{\mathsf{Pallas}}-1\}$ is a scalar without further reduction, by the injective reading $\mathbb{F}_{p_{\mathsf{Pallas}}}\to\mathbb{F}_{p_{\mathsf{Vesta}}}$ of §2.1, and the multiplier of $K^{\mathsf{Orchard}}$ ranges over $p_{\mathsf{Pallas}}$ of the $p_{\mathsf{Vesta}}$ scalars. Second, the inputs $\rho$ and $\psi$ must be those of the note committed to by $\mathsf{cm}$ .

Remark 6.5 (Determinism and masking).

For a fixed $\mathsf{nk}$ the nullifier is a function of the fields $\rho$ and $\psi$ of the note and of its commitment $\mathsf{cm}$ , so a note has exactly one nullifier under the $\mathsf{nk}$ of its owner. That every accepted consumption of the note publishes this value is Lemma 12.5, proved in “Double-spend resistance” (§12.2) from the Action statement, defined in “The Action statement” (§9.2). The point $[s]\,K^{\mathsf{Orchard}}$ is added to $\mathsf{cm}$ before extraction. For notes of one key with pairwise distinct $\rho$ , the key generated with $\mathsf{use\_qsk}=\mathsf{false}$ , the multipliers are jointly pseudorandom to an efficient party that holds the incoming viewing key and $\mathsf{ak}^{\mathbb{P}}$ but not $\mathsf{nk}$ , so the extracted values give it no usable information on the commitments or on the address; Proposition 6.10 states this exactly, under Assumption 6.2 and the further assumptions it names. The element $\rho$ enters as the input of the PRF and $\psi$ as an additive term of the multiplier. Both are fixed when the note is created: $\rho$ by “Nullifier chaining” (§6.3), and $\psi$ by the derivation of §4.3.

6.2 Nullifier sets

Each verifier maintains, for each shielded pool, a nullifier set, part of that pool’s treestate (“Anchors”, §5.2). Every Action publishes one nullifier, that of its consumed note, real or dummy (§4.4), and the nullifiers published by the Actions of valid transactions are inserted into the nullifier set of their pool (protocol specification, §“Nullifiers” and §“Nullifier Sets”). The consensus rule of §“Nullifier Sets” is that a nullifier must not repeat, either within a transaction or across transactions in a valid block chain; a nullifier is compared only with nullifiers of its own pool, so equal values in two pools do not repeat a nullifier (the specification treats the pools’ nullifiers as disjoint).

Both pools use the one derivation of Definition 6.3, with the same PRF and the same nullifier base: the nullifier construction belongs to the Orchard protocol, not to a pool (ZIP 229, Terminology). The Orchard pool and the Ironwood pool keep separate nullifier sets, as they keep separate note commitment trees, anchors and value pool balances (ZIP 229, Rationale, “Separate state”; protocol specification, §“Nullifier Sets”). The nullifier of an Ironwood-pool Action is inserted into, and checked against, the nullifier set of the Ironwood pool only.

Remark 6.6 (Pool locality).

Equal nullifier values in the two pools do not violate the consensus rule, so every uniqueness property derived from it holds within one pool. In particular the uniqueness of the elements $\rho$ proved in “Double-spend resistance” (Corollary 12.7) is uniqueness within a pool, not across the two pools.

6.3 Nullifier chaining

Construction 6.7 (Chaining rule).

In every Action the sender sets the element $\rho$ of the created note to the nullifier that the same Action publishes for its consumed note,

\rho^{\mathsf{new}}:=\mathsf{nf}^{\mathsf{old}}\in\mathbb{F}_{p_{\mathsf{% Pallas}}},

and encodes it as the $32$ -byte string $\mathsf{I2LEOSP}_{256}(\rho^{\mathsf{new}})$ . When the Action consumes no real note, its consumed side is a dummy note (Definition “Dummy notes”, §4.4), and the nullifier of that dummy note is $\rho^{\mathsf{new}}$ (protocol specification, §“Sending Notes (Orchard)”, §“Dummy Notes (Orchard)” and §“Faerie Gold attack and fix”).

Every Action has a consumed side (Definition “Action”, §4.4), so every note that an Action creates is constructed with $\rho$ equal to the nullifier of that Action’s consumed note. The leaves that enter a pool’s note commitment tree are the extracted commitments of notes created by that pool’s Actions (“The Merkle hash and the tree”, §5.1), so the rule covers every note whose extracted commitment enters the tree. The consumed dummy note is not created by an Action: its $\rho$ is $\mathsf{Extract}_{\mathbb{P}}$ of a uniformly random point of the Pallas group (§4.4).

The derivations of §4.3 take the chained $\rho$ as input: with $\underline{\rho}:=\mathsf{I2LEOSP}_{256}(\rho)$ ,

\displaystyle\mathsf{esk}

\displaystyle=\mathrm{ToScalar}\bigl{(}\mathsf{PRFexpand}_{\mathsf{rseed}}([% \mathtt{0x04}]\,\|\,\underline{\rho})\bigr{)},

\displaystyle\psi

\displaystyle=\mathrm{ToBase}\bigl{(}\mathsf{PRFexpand}_{\mathsf{rseed}}([% \mathtt{0x09}]\,\|\,\underline{\rho})\bigr{)},

and $\mathsf{rcm}$ is derived from the string $\mathsf{pre\_rcm}$ , which contains $\underline{\rho}$ and the encoding of $\psi$ . Hence $\mathsf{esk}$ and $\psi$ are functions of $\mathsf{rseed}$ and of the nullifier that the note’s own Action publishes, and $\mathsf{rcm}$ is a function of these and of the remaining note fields.

A Faerie Gold attack is one in which a sender creates several notes to one recipient that share a nullifier, so that only one of them can be spent (protocol specification, §“Faerie Gold attack and fix”). What a verifier can rely on, the uniqueness of the elements $\rho$ within a pool and resistance to the Faerie Gold attack, is proved in “Double-spend resistance” (Corollary 12.7) from the nullifier-set rule and the Action statement, defined in “The Action statement” (§9.2). This subsection states the rule that an honest sender follows and draws no conclusion about accepted notes from it.

6.4 Nullifier uniqueness and unlinkability

Proposition 6.8 (Nullifier uniqueness).

Under Assumptions 2.22 and 2.8, no efficient adversary outputs, except with negligible probability, two notes $n=(\mathsf{addr},v,\rho,\psi,\mathsf{rcm})$ and $n^{\prime}=(\mathsf{addr}^{\prime},v^{\prime},\rho^{\prime},\psi^{\prime},% \mathsf{rcm}^{\prime})$ and two nullifier deriving keys $\mathsf{nk},\mathsf{nk}^{\prime}\in\mathbb{F}_{p_{\mathsf{Pallas}}}$ , all of its choice, whose note commitments $\mathsf{cm}$ and $\mathsf{cm}^{\prime}$ are not $\bot$ and satisfy $\mathsf{cm}\neq\mathsf{cm}^{\prime}$ and

\mathsf{DeriveNullifier}_{\mathsf{nk}}(\rho,\psi,\mathsf{cm})=\mathsf{% DeriveNullifier}_{\mathsf{nk}^{\prime}}(\rho^{\prime},\psi^{\prime},\mathsf{cm% }^{\prime}).

The adversary may hold every nullifier deriving key, and $\mathsf{nk}=\mathsf{nk}^{\prime}$ and $\rho=\rho^{\prime}$ are admitted. Since two distinct notes have distinct commitments except with negligible probability (Proposition 4.5(b)), the same holds for two distinct notes in place of two distinct commitments.

Proof.

The adversary supplies both openings, so no knowledge extraction is used. Let its output satisfy the conditions, and write

	$\displaystyle K$	$\displaystyle:=K^{\mathsf{Orchard}},$
	$\displaystyle Q$	$\displaystyle:=Q(\texttt{z.cash:Orchard-NoteCommit-M}),$
	$\displaystyle H_{D}$	$\displaystyle:=\mathsf{GroupHash}(\texttt{z.cash:Orchard-NoteCommit-r},\varepsilon)$

for the nullifier base and for the hash base and the blinding base of $\mathsf{NoteCommit}$ (Definition 4.4). A reduction that runs the adversary computes $s:=(\mathsf{PRF}^{\mathsf{nfOrchard}}_{\mathsf{nk}}(\rho)+\psi)\bmod p_{% \mathsf{Pallas}}$ and $s^{\prime}$ likewise; the pieces $m=(m_{1},\dots,m_{109})$ and $m^{\prime}$ of the messages $M(n)$ and $M(n^{\prime})$ , which have $109$ chunks of $k=10$ bits (Table 4); and $\mathsf{rcm}$ , $\mathsf{rcm}^{\prime}$ . Every coefficient below is therefore known to it, the PRF outputs included, and no property of $\mathsf{PoseidonHash}$ is used.

Equal nullifiers are equal extracted coordinates, so by Lemma 2.4

[s]\,K+\mathsf{cm}=\theta\bigl{(}[s^{\prime}]\,K+\mathsf{cm}^{\prime}\bigr{)}% \qquad\text{for some }\theta\in\{1,-1\}.

Since $\mathsf{cm}\neq\bot$ , its hash point is not $\bot$ , and by the unrolled form (1) of the proof of Proposition 2.24,

\mathsf{cm}=[2^{109}]\,Q+\sum_{j=0}^{2^{k}-1}[\chi_{j}(m)]\,S(j)+[\mathsf{rcm}% ]\,H_{D},\qquad\chi_{j}(m)=\sum_{i=1}^{109}2^{109-i}\,\delta_{m_{i},j},

and likewise for $\mathsf{cm}^{\prime}$ . Substituting gives, with coefficients in $\mathbb{F}_{p_{\mathsf{Vesta}}}$ and $s$ , $s^{\prime}$ read as scalars,

[s-\theta s^{\prime}]\,K+[(1-\theta)\,2^{109}]\,Q+\sum_{j}[\chi_{j}(m)-\theta% \,\chi_{j}(m^{\prime})]\,S(j)+[\mathsf{rcm}-\theta\,\mathsf{rcm}^{\prime}]\,H_% {D}=\mathcal{O}.

(3)

The relation is non-trivial in each case.

•

If $\theta=-1$ , the coefficient of $Q$ is $2^{110}$ , non-zero modulo $p_{\mathsf{Vesta}}$ because $0<2^{110}<2^{253}\leq(p_{\mathsf{Vesta}}-1)/2$ .
•

If $\theta=1$ and $M(n)\neq M(n^{\prime})$ , then $m\neq m^{\prime}$ , and $\chi(m)\neq\chi(m^{\prime})$ modulo $p_{\mathsf{Vesta}}$ by step (1) of the proof of Proposition 2.24 ( $109\leq c=253$ ); some coefficient of an $S(j)$ is non-zero.
•

If $\theta=1$ and $M(n)=M(n^{\prime})$ , then $\mathsf{rcm}\neq\mathsf{rcm}^{\prime}$ , since equal messages and equal trapdoors give $\mathsf{cm}=\mathsf{cm}^{\prime}$ ; the coefficient of $H_{D}$ is non-zero.

The points $K$ , $Q$ , $S(0),\dots,S(2^{k}-1)$ and $H_{D}$ are values of $\mathsf{GroupHash}$ on pairwise distinct inputs (Table 2). The reduction outputs these inputs with the coefficients of (3), a non-trivial relation with known coefficients. By the lemma on relations among fixed generators (§2.4), the reduction behind Proposition 2.24, this happens with negligible probability under Assumptions 2.22 and 2.8. The specification records that its Sinsemilla collision argument extends to additional terms with independent bases for this purpose (protocol specification, §“Sinsemilla Hash Function”, Security argument, note; §“Faerie Gold attack and fix”).

For distinct notes whose commitments are not $\bot$ , equal commitments have negligible probability by Proposition 4.5(b), and distinct commitments are the case above. □

Remark 6.9 (Scope of Proposition 6.8). #

The proposition uses no pseudorandomness of $\mathsf{PoseidonHash}$ , and none could be used: the adversary holds the PRF keys, and the reduction knows every coefficient. It does not require distinct elements $\rho$ , which the specification’s security requirement assumes (§“Computing $\rho$ values and Nullifiers”). Two notes with equal commitments are equal except with negligible probability (Proposition 4.5(b)) and so have equal nullifiers under one $\mathsf{nk}$ . Excluding equal commitments among the notes of a pool is the role of the chaining rule of §6.3, as Corollary 12.7 proves.

Proposition 6.10 (Nullifier unlinkability).

Let a key be generated with $\mathsf{use\_qsk}=\mathsf{false}$ from a uniform spending key, as in §3.1 and §3.2, with nullifier deriving key $\mathsf{nk}$ . An adversary receives the incoming viewing key $(\mathsf{dk},\mathsf{ivk})$ and the point $\mathsf{ak}^{\mathbb{P}}$ of the key, but not $\mathsf{nk}$ . It then submits, adaptively, notes $n_{i}=(\mathsf{addr}_{i},v_{i},\rho_{i},\psi_{i},\mathsf{rcm}_{i})$ , $1\leq i\leq q$ , of its choice, with pairwise distinct $\rho_{i}$ and note commitments $\mathsf{cm}_{i}\neq\bot$ , and after each submission receives an answer:

•

in the real game, $\mathsf{nf}_{i}:=\mathsf{DeriveNullifier}_{\mathsf{nk}}(\rho_{i},\psi_{i},% \mathsf{cm}_{i})$ ;
•

in the ideal game, $\mathsf{Extract}_{\mathbb{P}}([u_{i}]\,K^{\mathsf{Orchard}}+\mathsf{cm}_{i})$ for $u_{i}$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , independent of each other and of all else.

It outputs a bit. Let $\delta:=(p_{\mathsf{Vesta}}-p_{\mathsf{Pallas}})/p_{\mathsf{Vesta}}$ , which is below $2^{-167}$ , the statistical distance between the uniform distribution on $\{0,\dots,p_{\mathsf{Pallas}}-1\}$ , read in $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , and the uniform distribution on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ . Then the difference of the probabilities that it outputs $1$ in the two games is at most

2\bigl{(}\epsilon_{\mathsf{key}}+\epsilon_{\mathsf{expand}}+3\cdot 2^{-257}+% \epsilon_{\mathsf{vk}}\bigr{)}+\epsilon_{\mathsf{Pos}}+q\,\delta,

where $\epsilon_{\mathsf{expand}}$ , $\epsilon_{\mathsf{vk}}$ and $\epsilon_{\mathsf{Pos}}$ are the largest advantages against Assumptions 2.12 (through Lemma 2.15), 3.13 and 6.2 of the algorithms built from the adversary in the proof, and $\epsilon_{\mathsf{key}}$ is the probability that a single draw of key generation from a uniform spending key is rejected plus the probability that $\mathsf{ask}=0$ or $\hat{M}=\bot$ for independent uniform $(\mathsf{ask},\mathsf{nk})$ , with $\hat{M}$ the hash point of $\mathsf{Commit}^{\mathsf{ivk}}$ on $(\mathsf{ak},\mathsf{nk})$ (§3.2). The term $\epsilon_{\mathsf{key}}$ is negligible under Assumptions 2.12, 2.22 and 2.8 (Lemma “Rejection in key generation”, §3.2); the bound is therefore negligible for every efficient adversary, whose number $q$ of queries is polynomial, under these assumptions and Assumptions 3.13 and 6.2. When $K^{\mathsf{Orchard}}\neq\mathcal{O}$ , the point $[u_{i}]\,K^{\mathsf{Orchard}}+\mathsf{cm}_{i}$ is uniform on $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ whatever $\mathsf{cm}_{i}$ is, so the ideal answers are independent of the notes and of each other; in the model of Assumption 2.8, $K^{\mathsf{Orchard}}=\mathcal{O}$ has probability $1/p_{\mathsf{Vesta}}$ .

Proof.

Write $K:=K^{\mathsf{Orchard}}$ . The proof passes from the real game $H_{0}$ through hybrid games $H_{1},\dots,H_{5}$ ; each hop changes the probability of the output $1$ by at most the amount stated (Crypto Guide, §“The hybrid argument”, Lemma “Hybrid lemma”), and each reduction runs the adversary and the rest of the game.

Hybrid $H_{1}$ : idealised key. The key is generated by a single draw from a uniform $\mathsf{sk}$ , without rejection, at the cost of the probability that the draw is rejected (Lemma “Rejection in key generation”, §3.2). Then $(\mathsf{ask},\mathsf{nk},\mathsf{r_{ivk}})$ is replaced by independent uniform elements of $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , $\mathbb{F}_{p_{\mathsf{Pallas}}}$ and $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , from which the other components are derived as in §3.1 and §3.2. By Lemma 2.15, this costs at most $\epsilon_{\mathsf{expand}}$ plus the three reduction distances, each below $2^{-257}$ (§2.3): the three inputs of $\mathsf{PRFexpand}_{\mathsf{sk}}$ have distinct lead bytes, and the game is an efficient function of the triple, which derives $\mathsf{ak}^{\mathbb{P}}$ , $\mathsf{ivk}$ and $\mathsf{dk}$ , runs the adversary and answers each query with the nullifier under $\mathsf{nk}$ .

Hybrid $H_{2}$ : joint hiding. When $\mathsf{ask}\neq 0$ , the pair $(\mathsf{ivk},\mathsf{dk})$ is replaced by $(\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}^{\prime}}(\mathsf{ak},% \mathsf{nk}),u)$ , for $\mathsf{r_{ivk}}^{\prime}$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ and $u$ a uniform $32$ -byte string, independent of all else. The cost is at most $\epsilon_{\mathsf{vk}}$ . The reduction for Assumption 3.13 draws $\mathsf{ask}$ and $\mathsf{nk}$ itself; for $\mathsf{ask}\neq 0$ the pair $(\mathsf{ak},\mathsf{nk})$ lies in the domain of the assumption (§3.1). It receives a triple for that pair, passes its first two components to the adversary as $\mathsf{ivk}$ and $\mathsf{dk}$ , together with $\mathsf{ak}^{\mathbb{P}}$ , and answers every query with the nullifier under its own $\mathsf{nk}$ . Giving $\mathsf{ak}^{\mathbb{P}}$ costs nothing, because after $H_{1}$ the scalar $\mathsf{ask}$ is independent of $(\mathsf{nk},\mathsf{r_{ivk}})$ and the assumption holds for every fixed $(\mathsf{ak},\mathsf{nk})$ .

Hybrid $H_{3}$ : independent viewing keys. The pair $(\mathsf{ivk},\mathsf{dk})$ is replaced, whatever $\mathsf{ask}$ is, by $(\mathsf{Extract}_{\mathbb{P}}(W),u)$ for a uniform point $W$ and a uniform $32$ -byte string $u$ , independent of all else. When $\mathsf{ask}\neq 0$ and the hash point $\hat{M}$ of the message $\mathrm{LE}_{255}(\mathsf{ak})\,\|\,\mathrm{LE}_{255}(\mathsf{nk})$ is not $\bot$ , the commitment point $\hat{M}+[\mathsf{r_{ivk}}^{\prime}]\,H_{D}$ is uniform on $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ by Lemma 2.26(i), its blinding base $H_{D}$ not being $\mathcal{O}$ (§3.2), so the two games are identically distributed conditioned on that event, which depends on $(\mathsf{ask},\mathsf{nk})$ only. The cost is at most the probability that $\mathsf{ask}=0$ or $\hat{M}=\bot$ , the remaining part of $\epsilon_{\mathsf{key}}$ . In $H_{3}$ the key $\mathsf{nk}$ enters the game only through the answers: $\mathsf{dk}$ , $\mathsf{ivk}$ and $\mathsf{ak}^{\mathbb{P}}$ are independent of it.

Hybrid $H_{4}$ : random function. The function $\mathsf{PRF}^{\mathsf{nfOrchard}}_{\mathsf{nk}}$ is replaced by a uniformly random function $F\colon\mathbb{F}_{p_{\mathsf{Pallas}}}\to\mathbb{F}_{p_{\mathsf{Pallas}}}$ . The cost is at most $\epsilon_{\mathsf{Pos}}$ : the reduction for Assumption 6.2 runs $H_{3}$ with its oracle in place of $\mathsf{PRF}^{\mathsf{nfOrchard}}_{\mathsf{nk}}$ , since $\mathsf{nk}$ , uniform on $\mathbb{F}_{p_{\mathsf{Pallas}}}$ , is used nowhere else. In $H_{4}$ the $i$ -th answer is $\mathsf{Extract}_{\mathbb{P}}([s_{i}]\,K+\mathsf{cm}_{i})$ with $s_{i}:=(F(\rho_{i})+\psi_{i})\bmod p_{\mathsf{Pallas}}$ . The $\rho_{i}$ are pairwise distinct, so, with $F$ sampled lazily, $F(\rho_{i})$ is uniform on $\mathbb{F}_{p_{\mathsf{Pallas}}}$ and independent of everything the adversary has received when it submits $n_{i}$ . Translation by $\psi_{i}$ is a bijection modulo $p_{\mathsf{Pallas}}$ , so $s_{i}$ is uniform on $\{0,\dots,p_{\mathsf{Pallas}}-1\}$ and independent of that view, whatever $\psi_{i}$ is.

Hybrid $H_{5}$ : uniform scalars. For $i=1,\dots,q$ in turn, the scalar $s_{i}$ , read in $\mathbb{F}_{p_{\mathsf{Vesta}}}$ (§2.1), is replaced by $u_{i}$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ . The two distributions differ by $1/p_{\mathsf{Pallas}}-1/p_{\mathsf{Vesta}}$ on each of the $p_{\mathsf{Pallas}}$ residues and by $1/p_{\mathsf{Vesta}}$ on each of the other $p_{\mathsf{Vesta}}-p_{\mathsf{Pallas}}$ scalars, so their statistical distance is

\tfrac{1}{2}\Bigl{(}p_{\mathsf{Pallas}}\Bigl{(}\frac{1}{p_{\mathsf{Pallas}}}-% \frac{1}{p_{\mathsf{Vesta}}}\Bigr{)}+\frac{p_{\mathsf{Vesta}}-p_{\mathsf{% Pallas}}}{p_{\mathsf{Vesta}}}\Bigr{)}=\frac{p_{\mathsf{Vesta}}-p_{\mathsf{% Pallas}}}{p_{\mathsf{Vesta}}}=\delta.

The rest of the game is a randomised function of the view before the $i$ -th answer and of the replaced value, which is independent of that view; each step therefore costs at most $\delta$ , and the $q$ steps at most $q\,\delta$ (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”, parts (2) and (4)).

In $H_{5}$ the answers are those of the ideal game, and the key material is that of $H_{3}$ . Neither in $H_{5}$ nor in the ideal game do the answers depend on the key, so the hops of $H_{3}$ , $H_{2}$ and $H_{1}$ , taken in reverse order with the answers of the ideal game, lead from $H_{5}$ to the ideal game at the same costs. Summing the costs of both passes gives the bound. The last statement of the proposition holds because, for $K\neq\mathcal{O}$ , the map $u\mapsto[u]\,K$ is a bijection from $\mathbb{F}_{p_{\mathsf{Vesta}}}$ onto the group of prime order $p_{\mathsf{Vesta}}$ , and translation by $\mathsf{cm}_{i}$ is a bijection of the group; under Assumption 2.8 the point $K$ is uniform. □

Remark 6.11 (Design statement, not proved).

The specification describes the nullifier as combining elliptic-curve cryptography with the Poseidon-based PRF so as to give privacy defence in depth against a weakness in either (protocol specification, §“Faerie Gold attack and fix”). It states that, under the weaker assumption that $\mathsf{PoseidonHash}$ preserves sufficient entropy from $\mathsf{nk}$ and $\rho$ , the construction would remain unlinkable under a decisional Diffie–Hellman assumption on Pallas even if the Poseidon-based PRF were distinguishable from an ideal PRF (§“ $\mathsf{PoseidonHash}$ Function”, note; Crypto Guide, §“Diffie–Hellman: computational and decisional”, Definition “Decisional Diffie–Hellman, DDH”; the form assumed in this volume is Assumption 3.16). The volume records this as the specification’s design statement and derives no result from it; Proposition 6.10 relies on Assumption 6.2 instead.

For keys with $\mathsf{use\_qsk}=\mathsf{false}$ , the key tiers of Proposition 3.18 (“Capability separation”) have the following powers over nullifiers. The full viewing key $(\mathsf{ak},\mathsf{nk},\mathsf{r_{ivk}})$ contains $\mathsf{nk}$ . Its holder computes $\mathsf{DeriveNullifier}_{\mathsf{nk}}(\rho,\psi,\mathsf{cm})$ for every note of the key whose fields it knows, and tests whether that value is in the nullifier set of the note’s pool; that every accepted consumption of the note publishes this value is Lemma 12.5. It does so without spending authority, since the full viewing key yields no $\mathsf{ask}$ (Proposition 3.18(a)). A holder of only the incoming viewing key $(\mathsf{dk},\mathsf{ivk})$ cannot link a nullifier to its note, for notes with pairwise distinct $\rho$ , by Proposition 6.10.

Remark 6.12 (Limits).

Proposition 6.10 gives nothing against a holder of $\mathsf{nk}$ , which includes every holder of the full viewing key: such a holder recomputes, and so links, the nullifier of every note of the key whose fields it knows. It does not concern links through other public data, such as timing or the structure of the transaction; the privacy of an Action, with its preconditions, is Theorem 12.12, in “Privacy” (§12.4).