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 ρ of the note created in the same Action. It
proves two properties of the construction: uniqueness, from discrete
logarithms on Pallas with GroupHash modelled as a random oracle; and, for
keys generated with
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
deterministic: a function of the note and of the nullifier deriving key nk of the key that owns it, so that a second consumption publishes the same value; and
unlinkable: to a party without nk , the published value reveals nothing about the note’s commitment or address.
Requirement (b) forces a key: the extracted commitment cmx of a note is public, as its leaf (§5.1), so an unkeyed function of it, such as a hash of cmx , would be deterministic and, for a collision-resistant hash, distinct for distinct commitments, but any party could evaluate it on every leaf and so link each published nullifier to the leaf of its note; and an unkeyed function of the note’s other fields would let its sender, who knows them, recognise the nullifier when the recipient consumes the note.
Let
| PoseidonHash (x, y) := π 1 (f (x, y, 2 65)), |
where π 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
| PRF nfOrchard : F p Pallas × F p Pallas → F p Pallas, PRF nk nfOrchard (ρ) := PoseidonHash (nk, ρ), |
keyed by the nullifier deriving key
For nk uniform on F p Pallas , no efficient adversary with
adaptive oracle access distinguishes
Let
| K Orchard := GroupHash (z.cash:Orchard, K), |
the nullifier base, a fixed generator of
Table 3. For
| DeriveNullifier nk (ρ, ψ, cm) := Extract P ([s] K Orchard + cm) ∈ F p Pallas, |
where
| s := (PRF nk nfOrchard (ρ) + ψ) mod p Pallas ∈ { 0, ..., p Pallas − 1 } : |
the sum of the two field elements is taken as its representative in
| nf := DeriveNullifier nk (ρ, ψ, cm) |
(protocol specification, §“Computing ρ values and Nullifiers”).
The protocol specification attaches two notes to the definition
(§“Computing ρ values and Nullifiers”). First, the sum is reduced
modulo p Pallas intentionally, although the scalar field of the Pallas
group is F p Vesta . Since
For a fixed nk the nullifier is a function of the fields ρ and
ψ of the note and of its commitment cm , so a note has exactly one
nullifier under the 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 Orchard is
added to cm before extraction. For notes of one key with pairwise
distinct ρ , the key generated with
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.
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 ρ proved in “Double-spend resistance” (Corollary 12.7) is uniqueness within a pool, not across the two pools.
In every Action the sender sets the element ρ of the created note to the nullifier that the same Action publishes for its consumed note,
| ρ new := nf old ∈ F p Pallas, |
and encodes it as the 32 -byte string I2LEOSP 256 (ρ 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 ρ 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 ρ 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 ρ is Extract P of a uniformly random point of the Pallas group (§4.4).
The derivations of §4.3 take the chained ρ as input:
with
| esk | = ToScalar (PRFexpand rseed ([0x04] ∥ ρ ̄)), | ψ | = ToBase (PRFexpand rseed ([0x09] ∥ ρ ̄)), |
and rcm is derived from the string pre _ rcm , which contains ρ ̄ and the encoding of ψ . Hence esk and ψ are functions of rseed and of the nullifier that the note’s own Action publishes, and 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 ρ 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.
Under Assumptions 2.22 and 2.8, no
efficient adversary outputs, except with negligible probability, two notes
| DeriveNullifier nk (ρ, ψ, cm) = DeriveNullifier nk ′ (ρ ′, ψ ′, cm ′) . |
The adversary may hold every nullifier deriving key, and
The adversary supplies both openings, so no knowledge extraction is used. Let its output satisfy the conditions, and write
| K | := K Orchard, | ||
| Q | := Q (z.cash:Orchard-NoteCommit-M), | ||
| H D | := GroupHash (z.cash:Orchard-NoteCommit-r, ε) |
for the nullifier base and for the hash base and the blinding base of
NoteCommit (Definition 4.4). A reduction that runs the
adversary computes
Equal nullifiers are equal extracted coordinates, so by Lemma 2.4
| [s] K + cm = θ ([s ′] K + cm ′) for some θ ∈ { 1, − 1 } . |
Since
| cm = [2 109] Q + ∑ j = 0 2 k − 1 [χ j (m)] S (j) + [rcm] H D, χ j (m) = ∑ i = 1 109 2 109 − i δ m i, j, |
and likewise for cm ′ . Substituting gives, with coefficients in F p Vesta and s , s ′ read as scalars,
| [s − θ s ′] K + [(1 − θ) 2 109] Q + ∑ j [χ j (m) − θ χ j (m ′)] S (j) + [rcm − θ rcm ′] H D = O . | (3) |
The relation is non-trivial in each case.
If
If
If
The points K , Q ,
For distinct notes whose commitments are not ⊥ , equal commitments have negligible probability by Proposition 4.5(b), and distinct commitments are the case above. □
The proposition uses no pseudorandomness of PoseidonHash , and none could be used: the adversary holds the PRF keys, and the reduction knows every coefficient. It does not require distinct elements ρ , which the specification’s security requirement assumes (§“Computing ρ 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 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.
Let a key be generated with
in the real game,
in the ideal game,
It outputs a bit. Let
| 2 (ε key + ε expand + 3 ⋅ 2 − 257 + ε vk) + ε Pos + q δ, |
where ε expand , ε vk and
ε 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 ε key is the probability that a single draw of
key generation from a uniform spending key is rejected plus the probability
that
Write
Hybrid H 1 : idealised key. The key is generated by a single draw from a uniform sk , without rejection, at the cost of the probability that the draw is rejected (Lemma “Rejection in key generation”, §3.2). Then (ask, nk, r ivk) is replaced by independent uniform elements of F p Vesta , F p Pallas and F p Vesta , from which the other components are derived as in §3.1 and §3.2. By Lemma 2.15, this costs at most ε expand plus the three reduction distances, each below 2 − 257 (§2.3): the three inputs of PRFexpand sk have distinct lead bytes, and the game is an efficient function of the triple, which derives ak P , ivk and dk , runs the adversary and answers each query with the nullifier under nk .
Hybrid H 2 : joint hiding. When
Hybrid H 3 : independent viewing keys. The pair (ivk, dk) is
replaced, whatever ask is, by (Extract P (W), u) for a uniform point
W and a uniform 32 -byte string u , independent of all else. When
Hybrid H 4 : random function. The function
PRF nk nfOrchard is replaced by a uniformly
random function
Hybrid H 5 : uniform scalars. For
| 1 2 (p Pallas (1 p Pallas − 1 p Vesta) + p Vesta − p Pallas p Vesta) = p Vesta − p Pallas p Vesta = δ . |
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 δ , and the q steps at most q δ (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
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 PoseidonHash preserves sufficient entropy from nk and ρ , 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 (§“ 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
Proposition 6.10 gives nothing against a holder of 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.13, in “Privacy” (§12.4).