# ZIP 2005: Ironwood Quantum Recoverability

Status: Proposed

Owners: Daira-Emma Hopwood, Jack Grigg

Snapshot: a34cfc091434275120ff017c92c3b50d3cef623a

Source date: 2026-10-16T02:56:04+01:00

[Source revision](https://github.com/zcash/zips/commit/a34cfc091434275120ff017c92c3b50d3cef623a)

[Official source](https://zips.z.cash/zip-2005) · [Source file](https://github.com/zcash/zips/blob/a34cfc091434275120ff017c92c3b50d3cef623a/zips/zip-2005.md) · [Discussion](https://github.com/zcash/zips/issues/1135)

## Document parts

[Part 1](https://zips.tools/zip/2005) · [Part 2](https://zips.tools/zip/2005?part=2) · [Part 3](https://zips.tools/zip/2005?part=3) · [Part 4](https://zips.tools/zip/2005?part=4)

Reading part 3 of 4. Follow all parts for the complete proposal.

- 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](https://zips.z.cash/protocol/protocol.pdf#orchardkeycomponents)),
  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](#proposedrecoverystatement), 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](https://zips.z.cash/protocol/protocol.pdf#thmsinsemillaex)
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](#proposedrecoverystatement)
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](#securityargumentforspendability) below
  — the latter via the
  [$\mathsf{nf}$-pinning lemma](#lemma-nf-pinning)):
  $\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](#proposedrecoverystatement), 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](#proposedrecoverystatement), 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](#kb-query-accounting) in the proof.

**Theorem (key-binding, classical ROM).** <a id="thm-key-binding-rom"></a>
[]()
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. <a id="kb-query-accounting"></a>
[]()
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<a id="user-content-fnref-bs2023"></a>
[38](/zip/2005?part=4#user-content-fn-bs2023) 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.)

<a id="security-argument-for-spendability"></a>

### 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](#securityargumentforkeybinding).

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](#kb-query-accounting)).
$\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](#proposedrecoverystatement) 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.** <a id="lemma-ivk-pinning"></a>
[]()
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.** <a id="lemma-nf-pinning"></a>
[]()
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](#thm-key-binding-rom).

**Theorem (distinct-notetuple Spendability, classical ROM).** <a id="thm-spendability"></a>
[]()
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:

<a id="thm-spendability-validity"></a>
[]()**Validity of witnesses**
:   both witnesses satisfy the
[Proposed Recovery Statement](#proposedrecoverystatement).

<a id="thm-spendability-distinct"></a>
[]()**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$.

<a id="thm-spendability-collide"></a>
[]()**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 <a id="user-content-fnref-maurer2002"></a>
[39](/zip/2005?part=4#user-content-fn-maurer2002) (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 <a id="user-content-fnref-bernstein2009"></a>
[40](/zip/2005?part=4#user-content-fn-bernstein2009) (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**](#thm-spendability-validity),
[**Distinct note tuples**](#thm-spendability-distinct), and
[**Colliding nullifiers**](#thm-spendability-collide). 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](#lemma-nf-pinning), 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' <a id="user-content-fnref-protocol-updated-concreteextractorpallas"></a>
[41](/zip/2005?part=4#user-content-fn-protocol-updated-concreteextractorpallas)) 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**](#thm-spendability-distinct),
$\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](#thm-key-binding-rom) 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](#thm-key-binding-rom) above, see the next section.

<a id="adaptation-to-the-quantum-setting"></a>

### Adaptation to the quantum setting

The classical-ROM proofs above (for [key binding](#thm-key-binding-rom)
and [Spendability](#thm-spendability-collide)) 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 <a id="user-content-fnref-unruh2015-2"></a>
[28](/zip/2005?part=4#user-content-fn-unruh2015) <a id="user-content-fnref-unruh2016-2"></a>
[29](/zip/2005?part=4#user-content-fn-unruh2016).
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
<a id="user-content-fnref-unruh2016-3"></a>
[29](/zip/2005?part=4#user-content-fn-unruh2016) proved this for Merkle–Damgård (with a padding
restriction); Czajkowski et al. <a id="user-content-fnref-cbhsu2017"></a>
[42](/zip/2005?part=4#user-content-fn-cbhsu2017) for the **sponge**
construction (the absorb-then-squeeze paradigm used by SHA-3 / Keccak),
with <a id="user-content-fnref-acmt2025-2"></a>
[37](/zip/2005?part=4#user-content-fn-acmt2025) strengthening the sponge result via the related notion
of quantum indifferentiability. Fehr <a id="user-content-fnref-fehr2018"></a>
[43](/zip/2005?part=4#user-content-fn-fehr2018) 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 <a id="user-content-fnref-gm2022-2"></a>
[35](/zip/2005?part=4#user-content-fn-gm2022) 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.

## Citation relationships

Cites: [ZIP 32](https://zips.tools/zip/32), [ZIP 200](https://zips.tools/zip/200), [ZIP 209](https://zips.tools/zip/209), [ZIP 212](https://zips.tools/zip/212), [ZIP 226](https://zips.tools/zip/226), [ZIP 227](https://zips.tools/zip/227), [ZIP 229](https://zips.tools/zip/229), [ZIP 231](https://zips.tools/zip/231), [ZIP 258](https://zips.tools/zip/258), [ZIP 312](https://zips.tools/zip/312), [ZIP 2003](https://zips.tools/zip/2003), [ZIP 2007](https://zips.tools/zip/2007)

Cited by: [ZIP 32](https://zips.tools/zip/32), [ZIP 226](https://zips.tools/zip/226), [ZIP 229](https://zips.tools/zip/229), [ZIP 230](https://zips.tools/zip/230), [ZIP 231](https://zips.tools/zip/231), [ZIP 258](https://zips.tools/zip/258), [ZIP 316](https://zips.tools/zip/316), [ZIP 326](https://zips.tools/zip/326), [ZIP 374](https://zips.tools/zip/374)