Ironwood Quantum Recoverability

• Case $\mathsf{sk} \neq \bot$: The spender must prove knowledge of $\mathsf{sk}$, and that $\mathsf{ak}$, $\mathsf{nk}$, and $\mathsf{rivk}$ are derived correctly from $\mathsf{sk}$. This works because the derivations use post-quantum hashes (and $\mathsf{ask} \mapsto \mathsf{ak}$ is deterministic).
  In particular, $\mathsf{ivk}$ is an essentially random function of $\mathsf{sk}$, and so we expect that an adversary has no better attack than to search for values of $\mathsf{sk}$ to find one that reproduces a given $\mathsf{ivk}$. Since $\mathsf{ivk}$ must be an $x$-coordinate of a Pallas curve point (see the note at the end of § 4.2.3 Orchard Key Components), it can take on $(r_{\mathbb{P}}-1)/2$ values. So if there are $T$ targets the success probability for each attempt in a classical search is $2T/(r_{\mathbb{P}}-1)$, which is negligible provided that $T \ll r_{\mathbb{P}}$.

• Case $\mathsf{qk} \neq \bot$: This case is almost the same except that $\mathsf{ivk}$ is now an essentially random function of $(\mathsf{nk}, \mathsf{ak}, \mathsf{qk})$. The success probability in terms of $T$ is also the same as for the $\mathsf{sk} \neq \bot$ case.

The above security argument means that provided we also check the uses of $\mathsf{H^{rcm}}$ and $\mathsf{H}^{\text{ψ}}$ in the post-quantum Recovery Statement, Orchard-protocol note commitments can be considered binding on the note tuple $(\mathsf{rseed}, \mathsf{noterepr})$.

Note that the argument associated with Theorem 5.4.4 in the protocol specification ("$\mathsf{SinsemillaHashToPoint}(\ldots) = \bot$ yields a nontrivial discrete logarithm relation." and "Since by assumption it is hard to find a nontrivial discrete logarithm relation, we can argue that it is safe to use incomplete additions when computing Sinsemilla inside a circuit.") is not applicable when it is necessary to defend against a discrete-logarithm-breaking or quantum adversary. Therefore, the post-quantum Recovery Statement will need to use complete curve additions to implement Sinsemilla.

Security argument for key binding

The security of the Orchard shielded protocol against several attacks depends on cryptographic keys being bound to a recoverable note's $\mathsf{ivk}$. Different Orchard-protocol properties need different components of the key witness pinned:

• Nullifier-binding (used by the Balance argument and by the Spendability argument below — the latter via the $\mathsf{nf}$-pinning lemma): $\mathsf{nk}$ uniquely determined by $\mathsf{ivk}$.
• Spend Authorization: $\mathsf{ak}$ (up to $y$-sign of $\mathsf{ak}^{\mathbb{P}}$) and $\mathsf{qk}$ uniquely determined by $\mathsf{ivk}$. This includes uniquely determining the tag of $\mathsf{qk\_or\_sk}$, i.e. which of the $\mathsf{QK}$ and $\mathsf{SK}$ branches produced the $\mathsf{ivk}$.

The determination of $\mathsf{qk}$ must fix the branch itself, not merely the value of $\mathsf{qk}$ within the $\mathsf{QK}$ branch. Suppose an address generated with $\mathsf{use\_qsk} = \mathsf{true}$ —whose owner authorizes recovery by proving knowledge of $\mathsf{qsk}$ via $\mathsf{SoK^{qsk}}$— shared its $\mathsf{ivk}$ with an $\mathsf{sk}$-branch witness. An adversary holding a suitable $\mathsf{sk}$ could then recover the note through the $\mathsf{sk}$-branch of the Recovery Statement, authorizing the spend with $\mathsf{SoK^{sk}}$ and never demonstrating knowledge of $\mathsf{qsk}$. Against a discrete-logarithm-breaking adversary —for which the accompanying RedDSA signature over $\mathsf{ak}$ gives no protection— this breaks Spend Authorization for such addresses. Ruling out these cross-branch collisions (both $\mathsf{qk}$-values pinned, $\bot$ included) is therefore a requirement of the argument, not incidental strength.

The formal key-binding condition stated below covers all of these uniformly: a key-binding break is a pair of distinct witnesses sharing the same $\mathsf{ivk}$, where each witness carries the full key tuple — $(\mathsf{ak}, \mathsf{nk}, \mathsf{rivk})$ plus whichever of $\mathsf{qk}$ or $\mathsf{sk}$ is in use. If key binding fails, the Balance, Spendability, and Spend Authorization arguments each lose their corresponding pinning step.

Relative to the situation with note commitments where it was reasonable to only obtain quantum recoverability for newly output Ironwood-pool notes, there is a complication. Addresses may be used over the long term and it may not be desirable to switch to new addresses, or to avoid funds being sent to old ones. Fortunately, the Orchard protocol specified each of $\mathsf{ak}$, $\mathsf{nk}$, and $\mathsf{rivk}$ to be derived from $\mathsf{sk}$ via $\mathsf{PRF^{expand}}$, which is assumed collapsing. ($\mathsf{rivk}$ is derived differently for an "internal IVK", but that is also via $\mathsf{PRF^{expand}}$.)

Classically, the binding of $\mathsf{Commit^{ivk}}$ —instantiated via Sinsemilla— fails against a discrete-logarithm-breaking adversary, similarly to $\mathsf{NoteCommit}$. We use essentially the same fix as for $\mathsf{NoteCommit}$, with the $\mathsf{rivk}$-derivation hashes playing the role of $\mathsf{H^{rcm}}$. The Recovery Statement checks the derivation of $\mathsf{rivk}$:

The witness carries the branch as a tagged union $\mathsf{qk\_or\_sk} \;{\small ⦂}\; \mathsf{QK}\big(\mathbb{B}^{{\kern-0.1em\tiny\mathbb{Y}}[\ell_{\mathsf{qk}}/8]}\big) \mid \mathsf{SK}\big(\mathbb{B}^{[\ell_{\mathsf{sk}}]}\big)$ —following the formalization's sum type— so exactly one branch is present per witness, by construction. This is equivalent to case-splitting by $\mathsf{use\_qsk}$.

• In the $\mathsf{QK}$ branch, $\mathsf{rivk\_ext} = \mathsf{H^{rivk\_ext}_{qk}}(\mathsf{ak}, \mathsf{nk})$.
• In the $\mathsf{SK}$ branch, $\mathsf{rivk\_ext} = \mathsf{H^{rivk\_legacy}}(\mathsf{sk})$, with $\mathsf{ak}$ and $\mathsf{nk}$ also derived from $\mathsf{sk}$ via $\mathsf{H^{ask}}$ and $\mathsf{H^{nk}}$.

In either case, $\mathsf{rivk}$ is then either $\mathsf{rivk\_ext}$ directly (external IVK) or $\mathsf{H^{rivk\_int}_{rivk\_ext}}(\mathsf{ak}, \mathsf{nk})$ (internal IVK). All of these hashes are modelled as independent random oracles for the key-binding argument.

As in the Recovery Statement, we have:

$\begin{array}{rll} \hspace{1em}\mathsf{BindKeys^{sk}}(\mathsf{sk}, \mathsf{ak}^{\mathbb{P}}, \mathsf{nk}, \mathsf{rivk\_ext}) = \big(&\!\!\!\! \mathsf{ak}^{\mathbb{P}} = [\mathsf{H^{ask}}(\mathsf{sk})]\, \mathcal{G}^{\mathsf{Orchard}} \\ &\!\!\!\! \wedge\; \mathsf{nk} = \mathsf{H^{nk}}(\mathsf{sk}) \\ &\!\!\!\! \wedge\; \mathsf{rivk\_ext} = \mathsf{H^{rivk\_legacy}}(\mathsf{sk}) \,\big) \end{array}$

Let the key-binding condition on a witness $w = (\mathsf{ivk}, \mathsf{ak}^{\mathbb{P}}, \mathsf{nk}, \mathsf{rivk\_ext}, \mathsf{rivk}, \mathsf{qk\_or\_sk})$ be:

$\begin{array}{l} \;\;\; \text{match } \mathsf{qk\_or\_sk} \text{ with } \begin{cases} \mathsf{QK}(\mathsf{qk}) \!\!\!&\Rightarrow \mathsf{rivk\_ext} = \mathsf{H^{rivk\_ext}_{qk}}(\mathsf{ak}, \mathsf{nk}) \\ \mathsf{SK}(\mathsf{sk}) \!\!\!&\Rightarrow \mathsf{BindKeys^{sk}}(\mathsf{sk}, \mathsf{ak}^{\mathbb{P}}, \mathsf{nk}, \mathsf{rivk\_ext}) \vphantom{\Big(} \end{cases} \\ \wedge\; \mathsf{rivk} \in \big\{\, \mathsf{rivk\_ext},\, \mathsf{H^{rivk\_int}_{rivk\_ext}}(\mathsf{ak}, \mathsf{nk}) \,\big\} \\ \wedge\; \mathsf{ivk} = \mathsf{Commit^{ivk}_{rivk}}(\mathsf{ak}, \mathsf{nk}) \\ \wedge\; \mathsf{ivk} \not\in \{0, \bot\} \end{array}$

where $\mathsf{ak} = \mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}^{\mathbb{P}})$.

The predicate intentionally does not constrain the $y$-sign of $\mathsf{ak}^{\mathbb{P}}$. This is consistent with the Orchard protocol's design choice to use $\mathsf{ak}$ as a single $\mathbb{F}_{q_{\mathbb{P}}}$ element (the $x$-coordinate $\mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}^{\mathbb{P}})$), which avoids point-decompression in places that consume $\mathsf{ak}$, in exchange for a factor-of-2 reduction in concrete binding security. Accordingly, the break event below identifies witnesses up to the $y$-sign of $\mathsf{ak}^{\mathbb{P}}$.

The flags $\mathsf{use\_qsk}$ and $\mathsf{is\_internal\_rivk}$ that appear in the protocol diagram do not appear in this witness — nor in the formal Recovery Statement above. Their roles are absorbed into the witness's structural form:

• $\mathsf{use\_qsk}$ is encoded in the tag of $\mathsf{qk\_or\_sk}$: the witness carries exactly one of the two branches by construction (enforced by the tagged form, not by a $\bot$-exclusion constraint), and the branch-specific constraint applies to whichever is present.
• $\mathsf{is\_internal\_rivk}$ is encoded in $\mathsf{rivk} \in \big\{\mathsf{rivk\_ext},\, \mathsf{H^{rivk\_int}_{rivk\_ext}}(\mathsf{ak}, \mathsf{nk})\big\}$: both $\mathsf{rivk}$ derivations are admitted simultaneously.

This formulation is strictly stronger than a flag-conditioned one: a key-binding break can have $w_1$ and $w_2$ in different branches across either flag (e.g., $w_1$ in the $\mathsf{QK}$ branch and $w_2$ in the $\mathsf{SK}$ branch, or $w_1$ with external $\mathsf{rivk}$ and $w_2$ with internal $\mathsf{rivk}$), provided both produce the same $\mathsf{ivk}$. A flag-based formulation would forbid only same-branch breaks. For the $\mathsf{use\_qsk}$ flag this extra strength is required by Spend Authorization —forbidding the $\mathsf{qk}$-versus-$\mathsf{sk}$ cross-branch collision described above— and not merely incidental; for $\mathsf{is\_internal\_rivk}$ it is additional robustness.

A key-binding break is a pair of witnesses $(w_1, w_2)$ with shared $\mathsf{ivk}$ satisfying the key-binding condition, whose $(\mathsf{ak}, \mathsf{nk}, \mathsf{rivk}, \mathsf{qk\_or\_sk})$ projections differ — i.e., $w_1$ and $w_2$ differ in some component other than the $y$-sign of $\mathsf{ak}^{\mathbb{P}}$.

The random oracles used in the key-binding condition are $\mathsf{H^{rivk\_ext}}$, $\mathsf{H^{rivk\_legacy}}$, $\mathsf{H^{rivk\_int}}$, $\mathsf{H^{ask}}$, and $\mathsf{H^{nk}}$.

Let $\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})$ be the probability, over $\mathcal{A}$'s randomness and at most $q_{\mathsf{kb}}$ queries in total to these random oracles, that $\mathcal{A}$ outputs a key-binding break. Here $q_{\mathsf{kb}}$ counts the derivation inputs of $\mathcal{A}$'s output witnesses among its queries — a convention that is without loss of generality, by the accounting normalization in the proof.

Theorem (key-binding, classical ROM). Let $\mathcal{A}$ be a classical adversary making at most $q_{\mathsf{kb}}$ total queries to the random oracles used in the key-binding condition. Then $\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}}) \leq \frac{q_{\mathsf{kb}}(q_{\mathsf{kb}}-1)}{r_{\mathbb{P}}}$.

Proof sketch.

Algebraic setup. By § 5.4.1.10 “Sinsemilla commitments”,

$$\mathsf{Commit^{ivk}_{rivk}}(\mathsf{ak}, \mathsf{nk}) = \mathsf{Extract}_{\mathbb{P}}\big(M' + [\mathsf{rivk}]\, \mathcal{S}\big)\textsf{,}$$

where $\mathcal{S}$ is the rivk-randomization base

$$\mathcal{S} := \mathsf{GroupHash}^{\mathbb{P}}(\texttt{“z.cash:Orchard-CommitIvk-r”}, \texttt{“”})\textsf{,}$$

and

$$M' := \mathsf{SinsemillaHashToPoint}\big(\texttt{“z.cash:Orchard-CommitIvk-M”},\; \mathsf{I2LEBSP}_{\ell^{\mathsf{Orchard}}_{\mathsf{base}}}(\mathsf{ak}) \,\Vert\, \mathsf{I2LEBSP}_{\ell^{\mathsf{Orchard}}_{\mathsf{base}}}(\mathsf{nk})\big)\textsf{.}$$

By expanding the Sinsemilla bases used inside $\mathsf{SinsemillaHashToPoint}$ as scalar multiples of $\mathcal{S}$, without loss of generality we have $M' = [h(\mathsf{ak}, \mathsf{nk})]\, \mathcal{S}$ for a Pedersen-like deterministic scalar hash $h$, so

$$\mathsf{Commit^{ivk}_{rivk}}(\mathsf{ak}, \mathsf{nk}) = \mathsf{Extract}_{\mathbb{P}}\big([h(\mathsf{ak}, \mathsf{nk}) + \mathsf{rivk}]\, \mathcal{S}\big)\textsf{.}$$

Domain separation in the protocol's BLAKE2b instantiations ensures $h$ does not query $\mathsf{H^{rivk\_ext}}$, $\mathsf{H^{rivk\_legacy}}$, $\mathsf{H^{rivk\_int}}$, $\mathsf{H^{ask}}$, or $\mathsf{H^{nk}}$: $h$ depends only on fixed Sinsemilla bases and on $(\mathsf{ak}, \mathsf{nk})$.

By the same $y^2 = Y(x)$ argument used in the Spendability proof (using § 5.4.9.7 for the $\mathsf{Extract}_{\mathbb{P}}$-style $x$-coordinate convention), a key-binding break implies

$$h(\mathsf{ak}, \mathsf{nk}) + \mathsf{rivk} \equiv \pm\big(h(\mathsf{ak}', \mathsf{nk}') + \mathsf{rivk}'\big) \pmod{r_{\mathbb{P}}}\textsf{.}$$

Define $\mathsf{G}(w) := h(\mathsf{ak}, \mathsf{nk}) + \mathsf{rivk} \pmod{r_{\mathbb{P}}}$ for a witness $w$, and let $G_i := \mathsf{G}(w_i)$ for $i \in \{1, 2\}$. The break condition is $G_1 \equiv \pm G_2 \pmod{r_{\mathbb{P}}}$.

Final-random-oracle structure. For each witness $w_i$ satisfying the key-binding condition, $\mathsf{rivk}_i$ is the output of a final random oracle $O_i \in \{\mathsf{H^{rivk\_ext}}, \mathsf{H^{rivk\_legacy}}, \mathsf{H^{rivk\_int}}\}$ at a final input $x_i$, determined by the witness's branch and IVK choice:

• qk-branch, external IVK: $O_i = \mathsf{H^{rivk\_ext}}$, $x_i = (\mathsf{qk}_i, \mathsf{ak}_i, \mathsf{nk}_i)$.
• sk-branch, external IVK: $O_i = \mathsf{H^{rivk\_legacy}}$, $x_i = \mathsf{sk}_i$.
• qk-branch, internal IVK: $O_i = \mathsf{H^{rivk\_int}}$, $x_i = (\mathsf{rivk\_ext}_i, \mathsf{ak}_i, \mathsf{nk}_i)$ where $\mathsf{rivk\_ext}_i = \mathsf{H^{rivk\_ext}_{qk_i}}(\mathsf{ak}_i, \mathsf{nk}_i)$.
• sk-branch, internal IVK: $O_i = \mathsf{H^{rivk\_int}}$, $x_i = (\mathsf{rivk\_ext}_i, \mathsf{ak}_i, \mathsf{nk}_i)$ where $\mathsf{rivk\_ext}_i = \mathsf{H^{rivk\_legacy}}(\mathsf{sk}_i)$.

In each case $G_i = h(\mathsf{ak}_i, \mathsf{nk}_i) + O_i(x_i) \pmod{r_{\mathbb{P}}}$, with the deterministic shift $h$ independent of $O_i$'s responses (by non-querying).

The shifted combined oracle. Treat the three rivk-derivation oracles ($\mathsf{H^{rivk\_ext}}$, $\mathsf{H^{rivk\_legacy}}$, $\mathsf{H^{rivk\_int}}$) as a single combined oracle $\mathsf{H}^*$ on the disjoint union of their input domains. Each instance contributes outputs uniform on $\mathbb{F}_{r_{\mathbb{P}}}$, independently of the others, by domain separation. $\mathsf{H^{ask}}$ and $\mathsf{H^{nk}}$ are not part of $\mathsf{H}^*$: they enter only through the shifts below, and their output types differ.

For a combined input $x$, define the shift $s(x) := h(\mathsf{ak}, \mathsf{nk})$, with $(\mathsf{ak}, \mathsf{nk})$ read off the input: directly for $\mathsf{H^{rivk\_ext}}$ and $\mathsf{H^{rivk\_int}}$ inputs, and via $\mathsf{ak} = \mathsf{Extract}_{\mathbb{P}}\big([\mathsf{H^{ask}}(\mathsf{sk})]\, \mathcal{G}^{\mathsf{Orchard}}\big)$, $\mathsf{nk} = \mathsf{H^{nk}}(\mathsf{sk})$ for an $\mathsf{H^{rivk\_legacy}}$ input $\mathsf{sk}$. So $s$ is a function of the input and of the $\mathsf{H^{ask}}$/$\mathsf{H^{nk}}$ oracles only; since $h$ is non-querying, $s$ never depends on the rivk-derivation responses. Define the shifted combined oracle

$$\mathsf{H}^s(x) := s(x) + \mathsf{H}^*(x) \pmod{r_{\mathbb{P}}}\textsf{.}$$

For every witness satisfying the key-binding condition the derivation constraints give $G_i = \mathsf{H}^s(x_i)$, so the break condition is a ±-collision of $\mathsf{H}^s$ at the pair $(x_1, x_2)$.

Distinct final inputs. The final inputs $x_1, x_2$ of a break need not be distinct, but the case $x_1 = x_2$ is fully deterministic. If the witnesses decode differently —one external, one internal— their final inputs lie in disjoint summands of the combined domain, so $x_1 = x_2$ is impossible outright. If both witnesses are externally decoded, equal final inputs force the witnesses to coincide on all fields constrained by the key-binding condition, contradicting distinctness. (Equal $\mathsf{H^{rivk\_ext}}$ inputs determine $(\mathsf{qk}, \mathsf{ak}, \mathsf{nk})$ and thence $\mathsf{rivk\_ext} = \mathsf{rivk}$; equal $\mathsf{H^{rivk\_legacy}}$ inputs determine $\mathsf{sk}$ and thence everything, via $\mathsf{H^{ask}}$ and $\mathsf{H^{nk}}$.) So both witnesses are internally decoded, sharing $(\mathsf{ak}, \mathsf{nk}, \mathsf{rivk\_ext}, \mathsf{rivk})$ and differing only in their branch data. Then $\mathsf{rivk\_ext}_1 = \mathsf{rivk\_ext}_2$ is an equality of $\mathsf{H}^*$ outputs at the two upstream (rivk_ext-derivation) inputs, which the differing branch data make distinct. The shifts at those inputs agree: both equal $h(\mathsf{ak}, \mathsf{nk})$, using the derivation constraints on the $\mathsf{sk}$ side. So this is again a ±-collision of $\mathsf{H}^s$, at distinct inputs. In every case: a key-binding break yields a ±-collision of $\mathsf{H}^s$ at two distinct inputs among the adversary's queries, under the convention that $q_{\mathsf{kb}}$ counts the derivation inputs of the adversary's output witnesses among its queries. This convention is without loss of generality: replace $\mathcal{A}$ by the adversary that runs $\mathcal{A}$, queries the (at most 4) derivation inputs of its output witnesses —each witness's final input and its rivk_ext-derivation input— and returns the output unchanged. This "reasonable adversary" normalization³⁸ leaves the output distribution —and therefore the break probability— unchanged, puts the collision inputs among the queries by construction, and adds at most 4 to $q_{\mathsf{kb}}$.

Note that the external/internal decode is by value ($\mathsf{rivk} \overset{?}{=} \mathsf{rivk\_ext}$), not by how the witness was derived: at a fixpoint $\mathsf{H^{rivk\_int}_{rivk\_ext}}(\mathsf{ak}, \mathsf{nk}) = \mathsf{rivk\_ext}$ an internally-derived witness decodes as external. Both readings give the same $\mathsf{rivk}$, and the accounting partitions pairs by the decode.

Sequential collision bound. The adversary chooses each query adaptively, so we reveal the oracle responses in query order rather than fixing a pair in advance. Before the $j$-th query $x_j$ to $\mathsf{H}^*$, condition on the transcript so far: the $\mathsf{H^{ask}}$/$\mathsf{H^{nk}}$ responses (which fix the shifts $s(\cdot)$) and the $j-1$ recorded $\mathsf{H}^*$ responses. Under every such conditioning the fresh response $\mathsf{H}^*(x_j)$ is uniform on $\mathbb{F}_{r_{\mathbb{P}}}$, and for each recorded input $x_i$ and each sign there is exactly one value of $\mathsf{H}^*(x_j)$ with $\mathsf{H}^s(x_j) \equiv \pm \mathsf{H}^s(x_i) \pmod{r_{\mathbb{P}}}$; so the fresh response completes a shifted ±-collision with probability at most $2(j-1)/r_{\mathbb{P}}$. Because the conditioning is on the transcript itself, this holds however $x_j$ was chosen from the transcript. Summing over the queries,

$$\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}}) \leq \sum_{j=1}^{q_{\mathsf{kb}}} \frac{2(j-1)}{r_{\mathbb{P}}} = \frac{q_{\mathsf{kb}}(q_{\mathsf{kb}}-1)}{r_{\mathbb{P}}}\textsf{.}$$

(Queries to $\mathsf{H^{ask}}$ or $\mathsf{H^{nk}}$ are not $\mathsf{H}^*$ inputs and cannot complete a collision, so counting them in $q_{\mathsf{kb}}$ is conservative.)

Security argument for Spendability

DeriveNullifier is based on a Pedersen hash. In the current Orchard protocol, the property that it is infeasible to find two distinct Orchard-protocol notes with the same nullifier depends on the collision resistance of that hash, which would not hold against a discrete-logarithm-breaking adversary.

Does this mean it is possible to break Spendability for the given Recovery Statement? As it turns out, no, but the argument is somewhat involved.

Since each function in the Recovery Statement is deterministic, the free variables that the adversary can control are the sources of the derivation digraph within that statement and either $\mathsf{SoK^{sk}}$ or $\mathsf{SoK^{qk}}$. That is, the adversary can control all of

$$(\text{ρ}, \mathsf{g_d}, \mathsf{rseed}, \mathsf{sk}, \mathsf{nk}, \mathsf{ak}, \mathsf{qk}, \mathsf{qsk}, \mathsf{rivk})$$

subject to exactly one of $\mathsf{sk}$ and $\mathsf{qk}$ being present, per the $\mathsf{qk\_or\_sk}$ tagged union. The choice between external and internal IVK is encoded in $\mathsf{rivk}$'s value (either $\mathsf{rivk\_ext}$ or $\mathsf{H^{rivk\_int}_{rivk\_ext}}(\mathsf{ak}, \mathsf{nk})$).

We analyze $\mathsf{DeriveNullifier}$ as a function of these controllable inputs. Recall that $\mathsf{DeriveNullifier}$ is defined in § 4.16 ‘Computing ρ values and Nullifiers’ as:

$$\mathsf{DeriveNullifier_{nk}}(\text{ρ}, \text{ψ}, \mathsf{cm}) := \mathsf{Extract}_{\mathbb{P}}\Big( \big[(\mathsf{PRF^{nf}_{nk}}(\text{ρ}) + \text{ψ}) \bmod q_{\mathbb{P}}\big]\, \mathcal{K} + \mathsf{cm} \Big)$$

Also recall from [Repairing note commitments] that we have

$$\mathsf{cm} = [\mathsf{H^{rcm}_{rseed}}(\mathsf{noterepr}) + \mathsf{f}(\mathsf{rseed}, \mathsf{noterepr})]\, \mathcal{R}\textsf{.}$$

Let $K_{\kern-.08em\mathcal{R}}$ denote the discrete logarithm of $\mathcal{K}$ with respect to $\mathcal{R}$. This is well-defined and nonzero: $\mathcal{R}$ generates the prime-order Pallas group, so any non-identity Pallas point has a unique nonzero discrete logarithm with respect to it; and $\mathcal{K}$ is non-identity by construction.

Recall that $\text{ψ}$ is determined by $\mathsf{rseed}$ via $\text{ψ} = \mathsf{H}^{\text{ψ}}_{\mathsf{rseed}}(\text{ρ})$. The nullifier corresponding to $(\mathsf{nk}, \text{ρ}, \mathsf{rseed}, \mathsf{noterepr})$ is then

$$\mathsf{Extract}_{\mathbb{P}}\Big( \big[ \big((\mathsf{PRF^{nf}_{nk}}(\text{ρ}) + \text{ψ}) \bmod q_{\mathbb{P}}\big) \cdot K_{\kern-.08em\mathcal{R}} + \mathsf{H^{rcm}_{rseed}}(\mathsf{noterepr}) + \mathsf{f}(\mathsf{rseed}, \mathsf{noterepr}) \big]\, \mathcal{R} \Big)\textsf{.}$$

We model $\mathsf{H^{rcm}}$ as a random oracle with output uniform on $\mathbb{F}_{r_{\mathbb{P}}}$. The functions $\mathsf{f}$, $\mathsf{H}^{\text{ψ}}$, and $\mathsf{PRF^{nf}}$ are deterministic functions of $\mathsf{notetuple} = (\mathsf{rseed}, \mathsf{noterepr})$ that do not query $\mathsf{H^{rcm}}$: $\mathsf{f}(\mathsf{notetuple})$ is the Sinsemilla-base lift; $\mathsf{H}^{\text{ψ}}$ and $\mathsf{PRF^{nf}}$ are conventional hash functions.

The non-querying constraint rules out trivializing instantiations such as $\mathsf{f}({\small •}) = -\mathsf{H^{rcm}}({\small •})$. In the concrete protocol, it reflects that $\mathsf{f}$ depends only on fixed Sinsemilla bases; and that the hashes $\mathsf{H}^{\text{ψ}}$, $\mathsf{PRF^{nf}}$, and $\mathsf{H^{rcm}}$ use distinct domain separators, so can be considered unrelated to each other.

A key-binding break is as defined above in the Security argument for key binding.

Let $\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})$ be the probability, over $\mathcal{A}$'s randomness and at most $q_{\mathsf{kb}}$ queries to the random oracles used in the key-binding argument, that $\mathcal{A}$ outputs a key-binding break (with $q_{\mathsf{kb}}$ counting the derivation inputs of the output witnesses among the queries, as in the accounting normalization). $\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})$ is bounded separately by that argument; the bound below is unconditional, but is only useful to the extent that $\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})$ is small.

We give a reduction-based argument that any classical adversary $\mathcal{A}$ in the Random Oracle Model attempting to find two valid Recovery Statement witnesses with distinct note tuples that have colliding nullifiers, succeeds with probability at most $\frac{q_{\mathsf{rcm}}(q_{\mathsf{rcm}}-1)}{r_{\mathbb{P}}} + \varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})$, where $q_{\mathsf{rcm}}$ is the number of queries $\mathcal{A}$ makes to $\mathsf{H^{rcm}}$, and $q_{\mathsf{kb}}$ is as defined above. The bound depends only on $q_{\mathsf{rcm}}$ and on $\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})$, not on running time.

The components $\mathsf{rseed}, \mathsf{noterepr}$ are fields of $\mathsf{notetuple}$ by definition; and $\text{ρ}$, $\mathsf{g_d}$, $\mathsf{pk_d}$, and $\text{ψ}$ are fields of $\mathsf{noterepr}$, hence of $\mathsf{notetuple}$.

$\mathsf{ivk}$-pinning lemma. For any valid Recovery Statement witness $w$ with $\mathsf{notetuple} = (\mathsf{rseed}, \mathsf{noterepr})$, the value $\mathsf{ivk} = \log_{\mathsf{g_d}}(\mathsf{pk_d})$ is well-defined, since $\mathsf{g_d} \neq \mathcal{O}_{\mathbb{P}}$ on the prime-order Pallas curve and $\mathsf{ivk} \in [0, q_{\mathbb{P}}) \subseteq [0, r_{\mathbb{P}})$; $\mathsf{ivk}$ is therefore uniquely determined by $\mathsf{notetuple}$.

$\mathsf{nf}$-pinning lemma. Suppose $\mathcal{A}$'s output $(w_1, w_2)$ does not contain a key-binding break. Then for each $i \in \{1, 2\}$, $\mathsf{nf}_i$ is uniquely determined by $\mathsf{notetuple}_i$: by the conditioning, $(\mathsf{ak}_i, \mathsf{nk}_i, \mathsf{rivk}_i)$ is the only opening of $\mathsf{ivk}_i$ appearing in $\mathcal{A}$'s output, so $\mathsf{nk}_i$ is a function of $\mathsf{ivk}_i$, which is in turn a function of $\mathsf{notetuple}_i$ by the $\mathsf{ivk}$-pinning lemma; $\text{ρ}_i$ is a field of $\mathsf{notetuple}_i$; and the remaining $\mathsf{DeriveNullifier}$ inputs $\text{ψ}_i$ and $\mathsf{cm}_i$ are determined by $\mathsf{notetuple}_i$ through the Recovery Statement's deterministic derivations.

The argument here covers nullifier-binding — it argues that $\mathsf{nf}$ binds the note tuple $(\mathsf{rseed}, \mathsf{noterepr})$ under $\mathsf{H^{rcm}}$ modelled as a random oracle and the key-binding theorem.

Theorem (distinct-notetuple Spendability, classical ROM). Let $\mathcal{A}$ be a classical adversary with oracle access to $\mathsf{H^{rcm}}$ having output uniform on $\mathbb{F}_{r_{\mathbb{P}}}$, making at most $q_{\mathsf{rcm}}$ oracle queries. The Spendability-collision game has $\mathcal{A}$ output two Recovery Statement witnesses $w_1, w_2$ satisfying:

Validity of witnesses : both witnesses satisfy the Proposed Recovery Statement.

Distinct note tuples : the $\mathsf{H^{rcm}}$-input tuples $\mathsf{notetuple}_i := (\mathsf{rseed}_i, \mathsf{noterepr}_i)$ satisfy $\mathsf{notetuple}_1 \neq \mathsf{notetuple}_2$.

Colliding nullifiers : $\mathsf{nf}_1 = \mathsf{nf}_2$.

Then $\mathcal{A}$ wins this game with probability at most

$$\Big({\textstyle{q_{\mathsf{rcm}}} \atop \textstyle{2}}\Big) \cdot \frac{2}{r_{\mathbb{P}}} + \varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}}) = \frac{q_{\mathsf{rcm}}(q_{\mathsf{rcm}}-1)}{r_{\mathbb{P}}} + \varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})\textsf{,}$$

taken over the random oracle's responses and any internal randomness of $\mathcal{A}$.

This bound is essentially tight against classical generic adversaries. Maurer ³⁹ (Section 2, p. 5) establishes a matching upper bound of ${k \choose 2}/N$ on the success probability of any classical algorithm in finding a collision against a random oracle with an $N$-element output space using $k$ queries. Maurer's bound applies to the equality event $F_i = F_j$; our win condition allows $F_i = \pm F_j$ (two winning configurations per pair instead of one). Applying Maurer with $N = r_{\mathbb{P}}$ (the $\mathsf{H^{rcm}}$ output space) gives ${q_{\mathsf{rcm}} \choose 2}/r_{\mathbb{P}}$ for the equality event; doubling for the sign relaxation gives our $\frac{q_{\mathsf{rcm}}(q_{\mathsf{rcm}}-1)}{r_{\mathbb{P}}}$ bound. Classical parallel collision search ⁴⁰ (top of p. 8) achieves the equality-event regime up to a constant factor; the same adversaries achieve a constant fraction of the doubled bound for the $\pm$-equivalence event.

Proof sketch. $\mathcal{A}$ makes at most $q_{\mathsf{rcm}}$ queries to $\mathsf{H^{rcm}}$ before outputting $(w_1, w_2)$ satisfying Validity of witnesses, Distinct note tuples, and Colliding nullifiers. The probability that $(w_1, w_2)$ contains a key-binding break is at most $\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})$; condition on the complement.

Algebraic setup. Under this conditioning, define

$$\mathsf{F}(\mathsf{notetuple}) := \mathsf{H^{rcm}}(\mathsf{notetuple}) + \mathsf{f}(\mathsf{notetuple}) + \big((\mathsf{PRF^{nf}_{nk}}(\text{ρ}) + \text{ψ}) \bmod q_{\mathbb{P}}\big) \cdot K_{\kern-.08em\mathcal{R}} \pmod{r_{\mathbb{P}}}$$

, where $\mathsf{rseed}, \text{ρ}, \text{ψ}$ are fields of $\mathsf{notetuple}$ and $\mathsf{nk}$ is determined by $\mathsf{notetuple}$ via the key-binding leg of the $\mathsf{nf}$-pinning lemma, and let $F_i := \mathsf{F}(\mathsf{notetuple}_i)$ for $i \in \{1, 2\}$.

$\mathsf{Extract}_{\mathbb{P}}$ (§ 5.4.9.7 'Coordinate Extractor for Pallas' ⁴¹) is the $x$-coordinate of its argument for non-identity points, with the identity mapping to $0$. Since Pallas has the form $y^2 = Y(x)$ and no Pallas point has $x$-coordinate $0$, the collision $\mathsf{nf}_1 = \mathsf{nf}_2$ holds iff $F_1 \equiv \pm F_2 \pmod{r_{\mathbb{P}}}$.

Independence claim per pair. By Distinct note tuples, $\mathsf{notetuple}_1 \neq \mathsf{notetuple}_2$, so the $\mathsf{H^{rcm}}$ outputs at $\mathsf{notetuple}_1, \mathsf{notetuple}_2$ are independent uniform on $\mathbb{F}_{r_{\mathbb{P}}}$. The deterministic shifts ($\mathsf{f}$ and the $\mathsf{PRF^{nf}}$ contribution scaled by $K_{\kern-.08em\mathcal{R}}$) do not query $\mathsf{H^{rcm}}$, so they are independent of its responses. Hence $F_1$ and $F_2$ are independent uniform on $\mathbb{F}_{r_{\mathbb{P}}}$.

Bounding the win probability. The win condition $F_1 \equiv \pm F_2$ is a linear constraint on a pair of independent uniform variables, satisfied with probability at most $2/r_{\mathbb{P}}$ (one per sign). Union-bounding over the at most ${q_{\mathsf{rcm}} \choose 2}$ pairs of distinct $\mathsf{H^{rcm}}$ queries:

$$\Pr[\text{win} \mid \neg\,\text{break}] \leq \frac{q_{\mathsf{rcm}}(q_{\mathsf{rcm}}-1)}{r_{\mathbb{P}}}\textsf{.}$$

Decomposing on whether a key-binding break occurs and applying $\Pr[\text{win}] \leq \Pr[\text{win} \mid \neg\,\text{break}] + \Pr[\text{break}]$:

$$\Pr[\text{win}] \leq \frac{q_{\mathsf{rcm}}(q_{\mathsf{rcm}}-1)}{r_{\mathbb{P}}} + \varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}})\textsf{.}$$

This completes the classical-ROM proof.

The key-binding theorem bounds $\varepsilon_{\mathsf{kb}}(\mathcal{A}, q_{\mathsf{kb}}) \leq \frac{q_{\mathsf{kb}}(q_{\mathsf{kb}}-1)}{r_{\mathbb{P}}}$. Substituting, an adversary $\mathcal{A}$ that makes at most $q_{\mathsf{rcm}}$ queries to $\mathsf{H^{rcm}}$ and at most $q_{\mathsf{kb}}$ queries to the key-binding random oracles wins the Spendability-collision game with probability at most $\frac{q_{\mathsf{rcm}}(q_{\mathsf{rcm}}-1)}{r_{\mathbb{P}}} \;+\; \frac{q_{\mathsf{kb}}(q_{\mathsf{kb}}-1)}{r_{\mathbb{P}}}$.

For the post-quantum lift of this bound and of the key-binding bound above, see the next section.

Adaptation to the quantum setting

The classical-ROM proofs above (for key binding and Spendability) rely on $\mathsf{H^{rcm}}$ and the various $\mathsf{rivk}$-derivation hashes being collision-resistant. The natural quantum analog is called the collapsing property, introduced by Unruh ^{28 29}. It says that even a quantum adversary holding a superposition over several preimages of a fixed output cannot tell —by any subsequent measurement— which preimage it now has. This is the right property for our reductions. Each proof above splits cases based on which oracle query produced the colliding output; that case analysis works the same classically and quantumly only if the underlying hash "collapses" the adversary's superposition to a single classical preimage.

Subsequent work has analyzed whether standard hash-function constructions inherit collapsing from their compression function. Unruh ²⁹ proved this for Merkle–Damgård (with a padding restriction); Czajkowski et al. ⁴² for the sponge construction (the absorb-then-squeeze paradigm used by SHA-3 / Keccak), with ³⁷ strengthening the sponge result via the related notion of quantum indifferentiability. Fehr ⁴³ gave a unified algebraic framework that recovers these results and proves the collapsing property of HAIFA, a Merkle–Damgård variant with a per-iteration salt and counter. Gunsing and Mennink ³⁵ extended this kind of analysis to tree-hash constructions, relevant for the Recovery Protocol's note-commitment tree.

BLAKE2b uses HAIFA, so by Fehr's theorem modelling $\mathsf{H^{rcm}}$ as collapsing reduces to modelling BLAKE2b's compression function as collapsing. The "iv-preimage resistance" side condition Fehr's theorem requires for arbitrary-length inputs is automatically satisfied if the compression function is modelled as a random oracle — which is also the modelling assumption underlying the classical-ROM analyses above.