12 Security

Let $v^{\mathrm{𝗌𝗎𝗆}}:={\sum }_i(v_i^{\mathrm{𝗈𝗅𝖽}}-v_i^{\mathrm{𝗇𝖾𝗐}})-v^{\mathrm{𝖻𝖺𝗅𝖺𝗇𝖼𝖾}}$. Each difference has absolute value at most $2^{64}-1$, and $\mathrm{𝖬𝖠𝖷}\mathrm{\_}\mathrm{𝖬𝖮𝖭𝖤𝖸}=2.1\cdot {10}^{15}$ (protocol specification, §“Constants”), so

The hypothesis makes $v^{\mathrm{𝗌𝗎𝗆}}$ a multiple of $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, and $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}>2^{254}$ (§2.1); the only such multiple of absolute value below $2^{80}$ is $0$. □

Fix a pool and an efficient adversary $𝒜$. The adversary outputs polynomially many bundles, and the union bound reduces the claim to the $j$-th bundle of the pool, for each $j$. Let ${ℬ}_j$ be the algorithm that runs $𝒜$ with the extractors of Assumption 9.11 and outputs that bundle’s net value commitments ${\mathrm{𝖼𝗏}}_1^{\mathrm{𝗇𝖾𝗍}},\mathrm{\dots },{\mathrm{𝖼𝗏}}_n^{\mathrm{𝗇𝖾𝗍}}$, its balancing value, the pairs

read from the witnesses, the digest $\mathrm{𝖲𝗂𝗀𝖧𝖺𝗌𝗁}$ of its transaction and the pool’s binding signature. Algorithm ${ℬ}_j$ is efficient and forwards the queries of $𝒜$ to $𝖧$.

(1) Openings. By condition A4 of Definition 9.2, ${\mathrm{𝖼𝗏}}_i^{\mathrm{𝗇𝖾𝗍}}=[v_i^{\mathrm{𝗈𝗅𝖽}}-v_i^{\mathrm{𝗇𝖾𝗐}}]V^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}+[{\mathrm{𝗋𝖼𝗏}}_i]R^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$, so each output pair is an opening of ${\mathrm{𝖼𝗏}}_i^{\mathrm{𝗇𝖾𝗍}}$ in the sense of “The binding signature” (§8.3), except with the negligible probability that a witness fails the definition.

(2) Signature. The bundle is accepted, so its binding signature is valid on $\mathrm{𝖲𝗂𝗀𝖧𝖺𝗌𝗁}$ under

in the binding-signature instance of RedPallas, with base $R^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$ (step (6) of the verification of §11.6). This key belongs to the pool’s own bundle: each pool’s $\mathrm{𝖻𝗏𝗄}$ sums only that pool’s net value commitments and subtracts only its balancing value (§8.3).

(3) Congruence. Algorithm ${ℬ}_j$ is therefore an efficient party of the consequence of Proposition 8.10: it outputs the net value commitments and the balancing value of a bundle, openings of every commitment, and a binding signature under the resulting $\mathrm{𝖻𝗏𝗄}$ on a message of its choice. The consequence is proved in two steps. The extraction of Proposition 7.12, in the random-oracle model for $𝖧$ (Assumption 7.3), yields $b$ with $\mathrm{𝖻𝗏𝗄}=[b]R^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$; if the openings did not balance modulo $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, part (ii) of Proposition 8.10 would turn the residual $V^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$ component into the discrete logarithm of $V^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$ to the base $R^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$, which Assumptions 2.22 and 2.8 exclude. Hence ${\sum }_i(v_i^{\mathrm{𝗈𝗅𝖽}}-v_i^{\mathrm{𝗇𝖾𝗐}})\equiv v^{\mathrm{𝖻𝖺𝗅𝖺𝗇𝖼𝖾}}(mod{p}_{\mathrm{𝖵𝖾𝗌𝗍𝖺}})$, except with negligible probability.

(4) Integers. The bundle is accepted, so it has Actions, its balancing value lies in the range $\{-\mathrm{𝖬𝖠𝖷}\mathrm{\_}\mathrm{𝖬𝖮𝖭𝖤𝖸},\mathrm{\dots },\mathrm{𝖬𝖠𝖷}\mathrm{\_}\mathrm{𝖬𝖮𝖭𝖤𝖸}\}$, and the witnessed values lie in $\{0,\mathrm{\dots },2^{64}-1\}$. Lemma 12.3 turns the congruence into an equality of integers.

The argument uses no property of the pool beyond its own bundle and binding signature, and applies to the Ironwood pool as to the Orchard pool. □

Let $w$ and $w^{\prime }$ be the two witnesses, primed components belonging to $w^{\prime }$. Outside the negligible events of the paragraph after Definition “Pools, accepted Actions and witnesses”, both satisfy Definition 9.2 with A1 and A7 unweakened. Every step below is carried out by the efficient algorithm that runs the adversary with the extractors and searches the accepted Actions for such a pair.

(1) The note. By A1, ${\mathrm{𝖼𝗆}}^{\mathrm{𝗈𝗅𝖽}}={\mathrm{𝖭𝗈𝗍𝖾𝖢𝗈𝗆𝗆𝗂𝗍}}_{{\mathrm{𝗋𝖼𝗆}}^{\mathrm{𝗈𝗅𝖽}}}(M^{\mathrm{𝗈𝗅𝖽}})\ne \perp$, and likewise for $w^{\prime }$. The two consumed notes thus have equal extracted commitments other than $\perp$, and by Remark “Binding for notes given by expanded receivers” they are equal, except with negligible probability. Equal notes have equal messages and trapdoors modulo $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, hence ${\mathrm{𝖼𝗆}}^{\mathrm{𝗈𝗅𝖽}}={\mathrm{𝖼𝗆}}^{\prime \mathrm{𝗈𝗅𝖽}}$.

(2) The key. By A7, $\mathrm{𝗉𝗄}_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}=[\mathrm{𝗂𝗏𝗄}]𝗀_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}$ with $\mathrm{𝗂𝗏𝗄}:={\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}_{{𝗋}_{\mathrm{𝗂𝗏𝗄}}}^{\mathrm{𝗂𝗏𝗄}}({\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}({\mathrm{𝖺𝗄}}^{\mathbb{P}}),\mathrm{𝗇𝗄})\ne \perp$, and, the notes being equal, $\mathrm{𝗉𝗄}_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}=[{\mathrm{𝗂𝗏𝗄}}^{\prime }]𝗀_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}$ likewise. Both values of ${\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}^{\mathrm{𝗂𝗏𝗄}}$ are integers below , read as scalars (§2.1), and $𝗀_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}$ is a non-identity point of a group of prime order $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$; hence $\mathrm{𝗂𝗏𝗄}={\mathrm{𝗂𝗏𝗄}}^{\prime }$. By the binding of $\mathrm{𝗂𝗏𝗄}$ to $(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄})$ (Proposition “Binding of $\mathrm{𝗂𝗏𝗄}$ to $(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄})$”, §3.2), under Assumptions 2.22 and 2.8,

except with negligible probability; in particular $\mathrm{𝗇𝗄}={\mathrm{𝗇𝗄}}^{\prime }$.

(3) The nullifier. By A5, ${\mathrm{𝗇𝖿}}^{\mathrm{𝗈𝗅𝖽}}={\mathrm{𝖣𝖾𝗋𝗂𝗏𝖾𝖭𝗎𝗅𝗅𝗂𝖿𝗂𝖾𝗋}}_{\mathrm{𝗇𝗄}}({\rho }^{\mathrm{𝗈𝗅𝖽}},{\psi }^{\mathrm{𝗈𝗅𝖽}},{\mathrm{𝖼𝗆}}^{\mathrm{𝗈𝗅𝖽}})$ (Definition 6.3), a function of its four arguments, which are equal for $w$ and $w^{\prime }$ by (1) and (2). The two Actions therefore publish the same nullifier. No step uses $v^{\mathrm{𝗈𝗅𝖽}}$ or A3. □

Let two distinct accepted Actions of one pool consume the same note. Their consumed notes have the same extracted commitment, so by Lemma 12.5, except with negligible probability, the two Actions publish the same nullifier. Both belong to transactions of the adversary’s block chain, and the nullifier rule of “Nullifier sets” (§6.2), step (4) of the verification of §11.6, rejects a nullifier of the pool that repeats within a transaction or across the transactions of the chain. The event therefore lies in the negligible event of the lemma. The argument uses neither the value nor the membership of the note and holds for every note; the case of a committed note of non-zero value is the one that moves value. The nullifier sets of the two pools are separate (§6.2), so the argument concerns two Actions of one pool only. □

(a) The note that the witness of an accepted Action creates has ${\rho }^{\mathrm{𝗇𝖾𝗐}}={\mathrm{𝗇𝖿}}^{\mathrm{𝗈𝗅𝖽}}$ of that Action: the Action statement fixes ${\rho }^{\mathrm{𝗇𝖾𝗐}}:={\mathrm{𝗇𝖿}}^{\mathrm{𝗈𝗅𝖽}}$ and binds the created note to the published $\mathrm{𝖼𝗆𝗑}$ by A2 (Definition 9.2), so the chaining rule of §6.3 is enforced through Assumption 9.11. Distinct accepted Actions of one pool publish distinct nullifiers, by the nullifier rule (§6.2). Their created notes therefore have distinct $\rho$, and notes with a distinct component are distinct. The created note is the only opening of $\mathrm{𝖼𝗆𝗑}$ that an efficient algorithm finds (Remark “Binding for notes given by expanded receivers”); a recipient that accepts a note from the Action obtains that note (Proposition 10.15(c)) and checks $\rho ={\mathrm{𝗇𝖿}}^{\mathrm{𝗈𝗅𝖽}}$ itself (Proposition 10.15(a)).

(b) Two distinct notes have distinct note commitments, except with negligible probability, by the same remark; Proposition 6.8, which admits every pair of nullifier deriving keys, then excludes equal nullifiers.

Faerie Gold. Let a recipient accept a note $n^{\prime }$ from an accepted Action of a pool, and let ${\mathrm{𝗇𝖿}}^{\prime }$ be its nullifier under the recipient’s $\mathrm{𝗇𝗄}$. By (a) no other accepted Action of the pool creates $n^{\prime }$, so the notes that the recipient accepts from distinct Actions are distinct. An accepted Action of the pool whose witness consumes a note $n\ne n^{\prime }$ publishes, by A5, the nullifier of $n$ under the witnessed key, which differs from ${\mathrm{𝗇𝖿}}^{\prime }$ by (b). The value ${\mathrm{𝗇𝖿}}^{\prime }$ therefore enters the pool’s nullifier set only through an Action that consumes $n^{\prime }$ itself, and the consumption of another note does not make $n^{\prime }$ unspendable.

Pool locality. The argument of (a) uses the nullifier set of one pool. An Orchard-pool Action and an Ironwood-pool Action may publish the same nullifier and create notes with the same $\rho$; a consumption in one pool inserts its nullifier into that pool’s set only, and so blocks no note of the other pool (Remark “Pool locality”, §6.2). □

Let an efficient adversary $𝒜$ win with probability $ϵ$, and write $G:=G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$.

(1) Idealised key. By Lemma “Rejection in key generation” (§3.2), the key is replaced by a single draw from a uniform $\mathrm{𝗌𝗄}$ without rejection, at a cost negligible under Assumptions 2.12, 2.22 and 2.8. By Lemma 2.15 (Assumption 2.12), its triple $(\mathrm{𝖺𝗌𝗄},\mathrm{𝗇𝗄},{𝗋}_{\mathrm{𝗂𝗏𝗄}})$, before the sign normalisation, is then replaced by independent uniform elements of ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$, ${𝔽}_{p_{\mathrm{𝖯𝖺𝗅𝗅𝖺𝗌}}}$ and ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$, at a further negligible cost. Both hops apply because the event that $𝒜$ wins is efficiently decidable from the triple: an algorithm derives the key’s components, runs $𝒜$, answers its signing queries with $\mathrm{𝖺𝗌𝗄}$, runs the extractors on its output and checks the winning condition. After this step $\mathrm{𝗇𝗄}$ and ${𝗋}_{\mathrm{𝗂𝗏𝗄}}$ are independent of $\mathrm{𝖺𝗌𝗄}$, and, when $\mathrm{𝖺𝗌𝗄}\ne 0$, the sign normalisation makes ${\mathrm{𝖺𝗄}}^{\mathbb{P}}$ a uniform non-identity point of even $y$-coordinate (Remark “Hypothesis (H) for honest keys”, §11.3). This independence lets the reduction below simulate the full viewing key from ${\mathrm{𝖺𝗄}}^{\mathbb{P}}$ alone.

(2) Reduction. An algorithm $ℬ$ plays the adversary of Proposition 7.12. It receives $Y=[x]G$ for $x$ uniform on ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$, with access to $𝖧$ and to the signing oracle. If $Y=𝒪$ or $Y$ has odd $y$-coordinate, it stops. Otherwise, an event of probability $(p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}-1)/(2p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}})$, since exactly half of the $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}-1$ non-identity points have even $y$-coordinate (§2.1, on the star encoding), the point $Y$ is distributed as ${\mathrm{𝖺𝗄}}^{\mathbb{P}}$ in step (1) conditioned on $\mathrm{𝖺𝗌𝗄}\ne 0$. Algorithm $ℬ$ sets ${\mathrm{𝖺𝗄}}^{\mathbb{P}}:=Y$ and $\mathrm{𝖺𝗄}:={\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}(Y)$, draws $\mathrm{𝗇𝗄}$ and ${𝗋}_{\mathrm{𝗂𝗏𝗄}}$ uniformly, computes $\mathrm{𝗂𝗏𝗄}$, and gives $𝒜$ the full viewing key $(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄},{𝗋}_{\mathrm{𝗂𝗏𝗄}})$. It answers each query $(\alpha ,m)$ of $𝒜$ with the oracle’s signature under $x+\alpha$, forwards the queries of $𝒜$ to $𝖧$, and simulates every other honest party and random oracle. When $𝒜$ outputs a block chain, $ℬ$ runs the extractors of Assumption 9.11, as stated after Definition “Pools, accepted Actions and witnesses”, and searches for an Action that meets the winning condition, all of whose parts it can check; failing one, it stops. For the Action found, with witness $w$, it determines $\theta \in \{1,-1\}$ with ${\mathrm{𝖺𝗄}}_w^{\mathbb{P}}=[\theta ]Y$, stopping if there is none, and outputs the Action’s triple $(\mathrm{𝗋𝗄},m,\sigma )$ together with the witnessed randomiser ${\alpha }_w$ and $\theta$.

(3) The witnessed key. Except with negligible probability, ${\mathrm{𝖺𝗄}}_w^{\mathbb{P}}\in \{Y,-Y\}$. By A7, in its unweakened form, $\mathrm{𝗉𝗄}_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}=[{\mathrm{𝗂𝗏𝗄}}_w]𝗀_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}$ with ${\mathrm{𝗂𝗏𝗄}}_w:={\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}_{𝗋_{\mathrm{𝗂𝗏𝗄}}^{}{}_w{}^{}}^{\mathrm{𝗂𝗏𝗄}}({\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}({\mathrm{𝖺𝗄}}_w^{\mathbb{P}}),{\mathrm{𝗇𝗄}}_w)\ne \perp$, and the consumed note is a note of the key, so $\mathrm{𝗉𝗄}_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}=[\mathrm{𝗂𝗏𝗄}]𝗀_{𝖽}^{}{}_{}{}^{\mathrm{𝗈𝗅𝖽}}$. As in step (2) of the proof of Lemma 12.5, ${\mathrm{𝗂𝗏𝗄}}_w=\mathrm{𝗂𝗏𝗄}$, and the binding of $\mathrm{𝗂𝗏𝗄}$ to $(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄})$ gives ${\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}({\mathrm{𝖺𝗄}}_w^{\mathbb{P}})=\mathrm{𝖺𝗄}={\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}(Y)$, under Assumptions 2.22 and 2.8. By Lemma 2.4, ${\mathrm{𝖺𝗄}}_w^{\mathbb{P}}\in \{Y,-Y\}$. The statement does not constrain the sign of the witnessed point (Remark “Sign of ${\mathrm{𝖺𝗄}}^{\mathbb{P}}$”, §9.2), and the proof treats both signs. By A6,

(4) Forgery. An answer of the signing oracle to a query $(\alpha ,m^{\prime })$ has validating key $Y+[\alpha ]G$ and message $m^{\prime }$. The winning condition excludes a query $(\alpha ,m)$ with $\mathrm{𝗋𝗄}=Y+[\alpha ]G$, so the output triple is not the triple of an oracle answer: it is a forgery in the sense of Proposition 7.12. Algorithm $ℬ$ is efficient, and forges with probability at least

for a negligible $\nu$, the costs of step (1) and of the events excluded in step (3).

(5) Discrete logarithm. By Proposition 7.12(i), an algorithm $𝒟$ runs $ℬ$ twice on shared coins and outputs, with at least the probability that part states for the forging probability of $ℬ$, a scalar ${\mathrm{𝗋𝗌𝗄}}^{\ast }$ with $\mathrm{𝗋𝗄}=[{\mathrm{𝗋𝗌𝗄}}^{\ast }]G$ for the $\mathrm{𝗋𝗄}$ of the first run. It outputs $x^{\prime }:=\theta ({\mathrm{𝗋𝗌𝗄}}^{\ast }-{\alpha }_w)$, with $\theta$ and ${\alpha }_w$ of the first run. By step (3), $[\theta ]Y=[{\mathrm{𝗋𝗌𝗄}}^{\ast }-{\alpha }_w]G$, so $x^{\prime }=x$. For $\theta =1$ this is part (ii) of the proposition with ${\alpha }^{\ast }={\alpha }_w$; for $\theta =-1$ the same relation gives $-x={\mathrm{𝗋𝗌𝗄}}^{\ast }-{\alpha }_w$, so a witnessed point $-{\mathrm{𝖺𝗄}}^{\mathbb{P}}$ is no easier than ${\mathrm{𝖺𝗄}}^{\mathbb{P}}$: either sign yields $\mathrm{𝖺𝗌𝗄}$, the discrete logarithm of the honest ${\mathrm{𝖺𝗄}}^{\mathbb{P}}$. By Assumption 2.22 the probability that $𝒟$ outputs $x$ is negligible, hence so is the forging probability of $ℬ$, and with it $ϵ$; the loss factor $2p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}/(p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}-1)$ is about $2$. □

For $\beta \in \{0,1\}$ let $G_0^{\beta }$ be the experiment with specification $\beta$. Each of the games $G_1^{\beta }$ to $G_7^{\beta }$ below changes the probability that the adversary outputs $1$ by a negligible amount (Crypto Guide, §“The hybrid argument”, Lemma “Hybrid lemma”; each game is reached in polynomially many steps, one key or one Action at a time), and $G_7^0$ and $G_7^1$ are identically distributed. Every reduction runs the experiment with the adversary and samples every value that its hop does not concern. The keys involved are those of (P1), the spending keys of the dummy consumed notes and the keys of the dummy created notes.

Game $G_1$ (proof). The aggregate proof is replaced by the output of the simulator of Assumption 9.14 on the primary inputs, which are public; the witnesses satisfy Definition 9.2 by hypothesis. The cost is the statistical distance of that assumption. From $G_1$ on, a witness enters the game only through the public fields computed from its components.

Game $G_2$ (keys). Each key involved is replaced in turn, as in the preliminary step of the proof of Proposition 10.6 and hybrids $H_1$ to $H_3$ of the proof of Proposition 6.10: by a single draw without rejection (Lemma “Rejection in key generation”, §3.2; Assumptions 2.12, 2.22 and 2.8); its triple $(\mathrm{𝖺𝗌𝗄},\mathrm{𝗇𝗄},{𝗋}_{\mathrm{𝗂𝗏𝗄}})$ by independent uniform elements (Lemma 2.15); and its triple $(\mathrm{𝗂𝗏𝗄},\mathrm{𝖽𝗄},\mathrm{𝗈𝗏𝗄})$ by $({\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}(W),u_1,u_2)$, for a uniform point $W$ and uniform $32$-byte strings $u_1$ and $u_2$ (Assumption 3.13, whose reduction draws $\mathrm{𝖺𝗌𝗄}$ and $\mathrm{𝗇𝗄}$ itself, and the negligible event that $\mathrm{𝖺𝗌𝗄}=0$ or that the hash point of ${\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}^{\mathrm{𝗂𝗏𝗄}}$ is $\perp$). The hops apply because after $G_1$ the trapdoor ${𝗋}_{\mathrm{𝗂𝗏𝗄}}$ enters the game only through $(\mathrm{𝗂𝗏𝗄},\mathrm{𝖽𝗄},\mathrm{𝗈𝗏𝗄})$. From $G_2$ on, the components $\mathrm{𝖺𝗌𝗄}$, $\mathrm{𝗇𝗄}$, $\mathrm{𝗂𝗏𝗄}$, $\mathrm{𝖽𝗄}$ and $\mathrm{𝗈𝗏𝗄}$ of each key are independent, and $\mathrm{𝖽𝗄}$ and $\mathrm{𝗈𝗏𝗄}$ are uniform.

Game $G_3$ (outgoing ciphertexts). Each $C_{\mathrm{𝗈𝗎𝗍}}$ is replaced by the encryption of a fixed $64$-byte string under an independent uniform key, by Proposition “Confidentiality of the outgoing ciphertext” (§10.3). For $\mathrm{𝗈𝗏𝗄}\ne \perp$, the key $\mathrm{𝗈𝖼𝗄}$ is a value of the random oracle ${\mathrm{𝖯𝖱𝖥}}^{\mathrm{𝗈𝖼𝗄}}$ (Assumption 10.4) at an input that begins with the uniform secret $\mathrm{𝗈𝗏𝗄}$, which $q$ queries of the adversary hit with probability at most $q\cdot 2^{-256}$. Distinct Actions give distinct inputs, their $\mathrm{𝖾𝗉𝗄}$ differing except with negligible probability, so each $\mathrm{𝗈𝖼𝗄}$ is uniform and encrypts once, and Assumption 10.5(a) replaces the plaintext. For $\mathrm{𝗈𝗏𝗄}=\perp$, the key is uniform by construction and Assumption 10.5(a) applies directly.

Game $G_4$ (randomised keys). Each randomiser ${\alpha }_i$ is replaced by a uniform scalar, at a cost of at most ${\delta }_{512}+q_h\cdot 2^{-640}$ each, , for $q_h$ queries to $𝖧$ (Lemma “Distance of GenRandom from uniform”, §7.2; Assumption 7.3). Then $y_i:={\mathrm{𝗋𝗌𝗄}}_i=\mathrm{𝖺𝗌𝗄}+{\alpha }_i$ is uniform and independent of $\mathrm{𝖺𝗌𝗄}$ and of every other value, and ${\mathrm{𝗋𝗄}}_i=[y_i]G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$ (Proposition 7.10(i)); the signature ${\sigma }_i$ is computed under $y_i$. From $G_4$ on, no $\mathrm{𝖺𝗌𝗄}$ enters the game.

Game $G_5$ (nullifiers). For each key that consumes a note in the bundle, real or dummy, the key $\mathrm{𝗇𝗄}$ enters $G_4$ only through the nullifiers of those notes: $G_1$ removed it from the proof and $G_2$ from the viewing keys. As in hybrids $H_4$ and $H_5$ of the proof of Proposition 6.10, ${\mathrm{𝖯𝖱𝖥}}_{\mathrm{𝗇𝗄}}^{\mathrm{𝗇𝖿𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$ is replaced by a uniformly random function (Assumption 6.2), and each multiplier of $K^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$ by a uniform scalar $u_i\in {𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$, at a statistical cost below $2^{-167}$ each; the elements $\rho$ of the consumed notes of one key are pairwise distinct by the definition of the experiment, and a dummy consumed note has a key of its own. Each nullifier is then ${\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}([u_i]K^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}+{\mathrm{𝖼𝗆}}_i)$, the $x$-coordinate of a uniform point whatever ${\mathrm{𝖼𝗆}}_i$ is, since $K^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}\ne 𝒪$ except with probability $1/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$ (Assumption 2.8).

Game $G_6$ (ephemeral keys and note ciphertexts). For each created note in turn, real or dummy, $\mathrm{𝖾𝗉𝗄}$ is replaced by a uniform non-identity point and $C_{\mathrm{𝖾𝗇𝖼}}$ by the encryption of a fixed $564$-byte string under an independent uniform key, by steps (1) to (4) of the proof of Proposition 10.6 (Assumptions 10.4, 3.16, 10.5, 2.8 and 2.12), which keep $\mathrm{𝖼𝗆𝗑}$. The other public data, the data $z$ of that proposition, depend after $G_2$ to $G_5$ on the recipient’s key only through the addresses of that key given to the adversary and the outputs to them. The reduction of step (2) of that proof embeds the exponent $a$ as the $\mathrm{𝗂𝗏𝗄}$ of the recipient’s key in every such address, computing its transmission key as $[t]([a]P)$ for the diversified base $[t]P$ that it programs, and computes every other output to that key from its own $\mathrm{𝖾𝗌𝗄}$; the proof is otherwise as written.

Game $G_7$ (note commitments). For each created note in turn, $\mathrm{𝖼𝗆𝗑}$ is replaced by the $x$-coordinate of a uniform point. After $G_6$ the seed $\mathrm{𝗋𝗌𝖾𝖾𝖽}$ of the note enters the game only through $\psi$ and $\mathrm{𝗋𝖼𝗆}$, that is through $\mathrm{𝖼𝗆}$: step (1) of $G_6$ replaced $\mathrm{𝖾𝗌𝗄}$, and the ciphertexts no longer depend on the plaintext. The proof of Proposition 4.8 then places $\mathrm{𝖼𝗆}$ within ${ϵ}_{\mathrm{𝖯𝖱𝖥}}+\delta +{ϵ}_{\perp }$ of a uniform point, with and ${ϵ}_{\mathrm{𝖯𝖱𝖥}}$, ${ϵ}_{\perp }$ negligible under Assumptions 2.12, 2.22 and 2.8.

Value commitments and the binding signature. In $G_7^{\beta }$ every field other than the net value commitments and the binding signature is distributed independently of $\beta$: the nullifiers and the extracted commitments are $x$-coordinates of uniform points, each $\mathrm{𝖾𝗉𝗄}$ is a uniform non-identity point, the ciphertexts encrypt fixed strings under fresh keys, each ${\mathrm{𝗋𝗄}}_i$ and ${\sigma }_i$ come from a fresh key $y_i$, the proof is simulated from the primary inputs, and the rest of the transaction is common. The net values $v_i^{\beta }$ of specification $\beta$ enter only

and, through these, the digest, the primary inputs of the simulator and $\mathrm{𝖻𝗏𝗄}$. Let $\lambda$ be the discrete logarithm of $V^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$ to the base $R^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$, which exists because $R^{\mathrm{𝖮𝗋𝖼𝗁𝖺𝗋𝖽}}$ generates the group (§8.1). The map

is a bijection of ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}^n$. It carries the net value commitments of specification $0$ to those of specification $1$, and it preserves ${\sum }_i{\mathrm{𝗋𝖼𝗏}}_i$, because ${\sum }_i{v}_i^0={\sum }_i{v}_i^1$, the common balancing value (step (6) of the construction of §11.5). The ${\mathrm{𝗋𝖼𝗏}}_i$ being uniform and independent, the tuple $({\mathrm{𝖼𝗏}}_1^{\mathrm{𝗇𝖾𝗍}},\mathrm{\dots },{\mathrm{𝖼𝗏}}_n^{\mathrm{𝗇𝖾𝗍}},\mathrm{𝖻𝗌𝗄})$ has the same distribution for both $\beta$, and $G_7^0$ and $G_7^1$ are identically distributed. This step is perfect and needs no reduction; the game is not required to compute $\lambda$.

The advantage of the adversary is therefore at most the sum of the costs of the hops for $\beta =0$ and $\beta =1$, which is negligible. In $G_7$ a dummy side differs from a real side only through the value in ${\mathrm{𝖼𝗏}}^{\mathrm{𝗇𝖾𝗍}}$, so two sequences that differ in whether a side is a dummy, with equal public leakage, are covered by the same argument. □

Each clause is a result of this section or of an earlier one.

(i) The first part is Assumption 9.11, applied to each bundle as stated after Definition “Pools, accepted Actions and witnesses”, with Remark “$\perp$-weakened conditions” (§9.2) for the unweakened forms of A1, A2, A3 and A7. By A2 the created note opens $\mathrm{𝖼𝗆𝗑}$, and by Remark “Binding for notes given by expanded receivers” it is the only opening that an efficient algorithm finds. For $v^{\mathrm{𝗈𝗅𝖽}}\ne 0$, condition A3, outside its $\perp$ case, makes the fold of A3 on $({\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}({\mathrm{𝖼𝗆}}^{\mathrm{𝗈𝗅𝖽}}),\mathrm{𝗉𝗈𝗌},\mathrm{𝗉𝖺𝗍𝗁})$, with the witnessed encodings $𝖼$, reach the bundle’s anchor $\mathrm{𝑟𝑡}$, and the anchor rule, step (3) of the verification of §11.6, makes $\mathrm{𝑟𝑡}$ the anchor of an earlier block in the pool. By A1, ${\mathrm{𝖼𝗆}}^{\mathrm{𝗈𝗅𝖽}}$ is a point, so Proposition 5.9(iii), which applies to that fold (§9.2), gives, under Assumptions 2.22 and 2.8, that ${\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}({\mathrm{𝖼𝗆}}^{\mathrm{𝗈𝗅𝖽}})$ is the leaf appended at position $\mathrm{𝗉𝗈𝗌}$, in the anchoring block or earlier: the consumed note is a committed note of the pool.

(ii) Theorem 12.6.

(iii) Theorem 12.4, which adds Assumption 7.3.

(iv) The first part is Theorem 12.9. The second is Proposition 11.10, under Assumptions 11.9, 2.22 and 7.3; its hypothesis (H) holds for honestly generated keys up to a negligible change in the probability of every efficiently decidable event, the event of that proposition included, under Assumptions 2.12, 2.22 and 2.8 (Remark “Hypothesis (H) for honest keys”, §11.3).

(v) Theorem 12.12.

Clauses (i) to (iii) use Assumptions 9.11, 2.22, 2.8 and 7.3 only, and no property of key generation; clauses (iv) and (v) use honest key generation with $\mathrm{𝗎𝗌𝖾}\mathrm{\_}\mathrm{𝗊𝗌𝗄}=\mathrm{𝖿𝖺𝗅𝗌𝖾}$. Each assumption of the list is used by some clause, and Assumption 9.10 enters only through the supporting analysis of Assumption 9.11 (“The Action circuit and the Halo 2 proof”, §9.3). □