Quantum resilience

This is a draft and is incomplete in some respects.

​​​​ZIP: XXX {{ 2005 suggested }}
​​​​Title: Quantum resilience
​​​​Owners: Daira-Emma Hopwood <daira-emma@electriccoin.co>
​​​​        Jack Grigg <jack@electriccoin.co>
​​​​Credits: Sean Bowe
​​​​Status: Draft
​​​​Category: Consensus
​​​​Created: 2025-03-31
​​​​License: MIT
​​​​Pull-Request: <https://github.com/zcash/zips/pull/???>

Terminology

The key words "MUST", "SHOULD", and "MAY" in this document are to be interpreted as described in BCP 14 ^[1] when, and only when, they appear in all capitals.

The term "network upgrade" in this document is to be interpreted as described in
ZIP 200. [^zip-0200]

The character § is used when referring to sections of the Zcash Protocol
Specification. ^[2]

The terms "Mainnet" and "Testnet" are to be interpreted as described in
§ 3.12 ‘Mainnet and Testnet’. ^[3]

We use the convention followed in the protocol specification that an \(\underline{\mathsf{underlined}}\) variable indicates a byte sequence, and a variable suffixed with \(⋆\) indicates a bit-sequence encoding of an elliptic curve point.

Abstract

This ZIP proposes a change to the construction of Orchard notes that is intended to support a smoother transition to future versions of Zcash designed to be secure against discrete-log-breaking adversaries, including adversaries using quantum computers.

Specifically, if it were necessary to disable the Sapling and Orchard shielded protocols in order to ensure balance preservation and prevent a discrete-log-breaking adversary from stealing funds, this change would make it possible to use an alternative protocol to recover existing Orchard funds. This recovery protocol is expected to remain secure against discrete-log-breaking and quantum adversaries.

Sapling funds should be migrated to Orchard in order to take advantage of this change.

Motivation

If quantum computers —or any other attack that allows finding discrete logarithms on the elliptic curves used in Zcash— were to become practical in the near future, it would raise difficult issues for the Zcash community. An adversary able to compute discrete logarithms could cause arbitrary inflation or steal users' funds.

This ZIP proposes a small change to the way Orchard notes are derived. If this change is made in advance of quantum computers becoming viable, then users' Orchard funds could remain safe and recoverable after a post-quantum transition. This would not require any change to the Orchard or proposed OrchardZSA circuits for the time being, and would not require deciding on the particular proof system or note commitment tree hash used in the future protocol.

Recovering Orchard funds after the post-quantum transition would involve checking a more expensive and complicated statement in zero knowledge, but it is expected that this will be entirely practical for future proof systems. The current privacy properties of Orchard would be retained against pre-quantum adversaries, and also against post-quantum adversaries without knowledge of the notes' addresses. ^[4]

To reduce overall protocol complexity and analysis effort, we do not propose a similar change for Sapling. Instead, Sapling funds can be migrated to Orchard in order to make them quantum-resilient. (Another reason not to support quantum resilience for Sapling is that it conflicts with the child key derivation defined in ZIP 32 ^[5].)

This proposal is implementable at low risk and with minimal changes to existing libraries and wallets. It can be folded into other changes necessary to implement ZSAs ^[6] and Memo Bundles ^[7].

Requirements

• Orchard notes constructed according to this proposal should be spendable via a recovery protocol (to be introduced, potentially, in a future upgrade) that is expected to be secure against discrete-log-breaking and quantum adversaries.
• No particular choice of post-quantum proving system or commitment tree hash should be assumed for that alternate protocol.
• The proposed scheme should be fully compatible with FROST multisignatures ^[8], hardware wallets, and the combination of both.
• The proposed scheme should not require regeneration of existing non-multisignature keys or addresses.
• The changes made to the pre-quantum protocol should not cause a significant regression in performance, applicability, or security against any given adversary class, or require significant re-analysis of the protocol.
• The recovery protocol should support usage during a period when quantum attacks may be very difficult, ensuring no loss of security against pre-quantum adversaries — including when FROST multisignatures and/or hardware wallets are used.
• Recovery of funds from hardware wallets that support this protocol should not require exposing spend authorizing keys to theft, and should be possible given only small extensions to their existing functionality (such as exposing an additional key that does not grant spend authority).

Non-requirements

• It is not required to address discrete-log-breaking or quantum attacks on privacy with this proposal, as long as it does not cause any regression in privacy properties.
• It is not required to add support for the alternate spending protocol to consensus rules now.

Specification

This is written as a set of changes to the existing protocol specification and ZIPs. It will need to be merged with other changes for v6 transactions (memo bundles ^[7:1] and ZSAs ^{[6:1] [9]}). We believe that this merge will be straightforward.

Some of the suggested changes to the protocol specification are refactoring to make it easier to consistently specify the rules on allowed note plaintext lead bytes and generation of note components, without duplication between sections. It is suggested to do this refactoring first, independently of the semantic changes for quantum resilience, and then to simplify this ZIP accordingly.

Changes to the protocol specification

§ 3.1 ‘Payment Addresses and Keys’

Add a \(\ast\) to the arrows leading to \(\mathsf{ask}\) and \(\mathsf{rivk}\) in the Orchard key components diagram, with the following note:

\(\ast\) The derivations of \(\mathsf{ask}\) and \(\mathsf{rivk}\) shown in the diagram are not the only possibility. For further detail see § 4.2.3 ‘Orchard Key Components’.

§ 3.2.1 ‘Note Plaintexts and Memo Fields’

{{ replace \(\mathsf{XXX}\) in \(\mathsf{ZIPXXXActivationHeight}\) with the number of this ZIP }}

Replace the paragraph

The field \(\mathsf{leadByte}\) indicates the version of the encoding of a Sapling or Orchard note plaintext. For Sapling it is \(\mathtt{0x01}\) before activation of the Canopy network upgrade and \(\mathtt{0x02}\) afterward, as specified in [ZIP-212]. For Orchard note plaintexts it is always \(\mathtt{0x02}\).

with

The field \(\mathsf{leadByte}\) indicates the version of the encoding of a Sapling or Orchard note plaintext.

Let the constants \(\mathsf{CanopyActivationHeight}\), \(\mathsf{ZIP212GracePeriod}\), and \(\mathsf{ZIPXXXActivationHeight}\) be as defined in § 5.3 ‘Constants’.

Let \(\mathsf{protocol} \;{\small ⦂}\; \{ \mathsf{Sapling}, \mathsf{Orchard} \}\) be the shielded protocol of the note.

Let \(\mathsf{height}\) be the block height of the block containing the transaction having the encrypted note plaintext as an output, and let \(\mathsf{txVersion}\) be the transaction version.

Define \(\mathsf{allowedLeadBytes^{protocol}}(\mathsf{height}, \mathsf{txVersion}) =\)
\(\hspace{2em} \begin{cases} \{ \mathtt{0x01} \},&\!\!\!\text{if } \mathsf{height} < \mathsf{CanopyActivationHeight} \\ \{ \mathtt{0x01}, \mathtt{0x02} \},&\!\!\!\text{if } \mathsf{CanopyActivationHeight} \leq \mathsf{height} < \mathsf{CanopyActivationHeight} + \mathsf{ZIP212GracePeriod} \\ \{ \mathtt{0x02} \},&\!\!\!\text{if } \mathsf{CanopyActivationHeight} + \mathsf{ZIP212GracePeriod} \leq \mathsf{height} < \mathsf{ZIPXXXActivationHeight} \\ \{ \mathtt{0x02} \},&\!\!\!\text{if } \mathsf{ZIPXXXActivationHeight} \leq \mathsf{height} \text{ and } \mathsf{protocol} = \mathsf{Sapling} \\ \{ \mathtt{0x02}, \mathtt{0x03} \},&\!\!\!\text{if } \mathsf{ZIPXXXActivationHeight} \leq \mathsf{height} \text{ and } \mathsf{protocol} = \mathsf{Orchard} \text{ and } \mathsf{txVersion} < 6 \\ \{ \mathtt{0x03} \},&\!\!\!\text{otherwise.} \end{cases}\)

The \(\mathsf{leadByte}\) of a Sapling or Orchard note MUST satisfy \(\mathsf{leadByte} \in \mathsf{allowedLeadBytes^{protocol}}(\mathsf{height}, \mathsf{txVersion})\). Senders SHOULD choose the highest lead byte allowed under this condition.

Non-normative note:   Since Orchard was introduced after the end of the [ZIP-212] grace period, note plaintexts for Orchard notes MUST have \(\mathsf{leadByte} \geq \mathtt{0x02}\).

§ 4.1.2 ‘Pseudo Random Functions’

In the list of places where \(\mathsf{PRF^{expand}}\) is used:

Replace

• [NU5 onward] in § 4.2.3 ‘Orchard Key Components’, with inputs \([6]\), \([7]\), \([8]\), and with first byte \(\mathtt{0x82}\) (the last of these is also specified in [ZIP-32]);
• in the processes of sending (§ 4.7.2 ‘Sending Notes (Sapling)’ and § 4.7.3 ‘Sending Notes (Orchard)’) and of receiving (§ 4.20 ‘In-band secret distribution (Sapling and Orchard)’) notes, with inputs \([4]\) and \([5]\), and for Orchard \([t] || \underline{\text{ρ}}\) with \(t \in \{ 5, 4, 9 \}\);

with

• [NU5 onward] in § 4.2.3 ‘Orchard Key Components’, with inputs \([\mathtt{0x06}]\), \([\mathtt{0x07}]\), \([\mathtt{0x08}]\), with first byte in \(\{ \mathtt{0x0B}, \mathtt{0x0C} \}\) (also specified in {{ reference to this ZIP }}), and with first byte \(\mathtt{0x82}\) (also specified in [ZIP-32]);
• in the processes of sending (§ 4.7.2 ‘Sending Notes (Sapling)’ and § 4.7.3 ‘Sending Notes (Orchard)’) and of receiving (§ 4.20 ‘In-band secret distribution (Sapling and Orchard)’) notes, for Sapling with inputs \([\mathtt{0x04}]\) and \([\mathtt{0x05}]\), and for Orchard with first byte in \(\{ \mathtt{0x05}, \mathtt{0x04}, \mathtt{0x09}, \mathtt{0x0A} \}\) (\(\mathtt{0x0A}\) is also specified in this ZIP);

Add

• in {{ reference to this ZIP }}, with first byte in \(\{ \mathtt{0x0A}, \mathtt{0x0B}, \mathtt{0x0C} \}\).

Also change the remaining decimal constants to hex for consistency.

§ 4.2.3 ‘Orchard Key Components’

Insert after the definition of \(\mathsf{ToScalar^{Orchard}}\):

Define \(\mathsf{H}^{\mathsf{ext\_rivk}}_{\mathsf{qk}}(\mathsf{ak}, \mathsf{nk}) = \mathsf{ToScalar^{Orchard}}(\mathsf{PRF^{expand}_{qk}}([\mathtt{0x0C}] \,||\, \mathsf{I2LEOSP}_{256}(\mathsf{ak})\)
\(\hspace{24.3em} ||\, \mathsf{I2LEOSP}_{256}(\mathsf{nk})))\).

Replace from "From this spending key" up to and including the line
"let \(\mathsf{ak} = \mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}^{\mathbb{P}})\)" in the algorithm with:

Under normal circumstances, the Spend authorizing key \(\mathsf{ask} \;{\small ⦂}\; \mathbb{F}^{*}_{r_{\mathbb{P}}}\) is derived directly from \(\mathsf{sk}\). However, this might not be the case for protocols that require distributed generation of shares of \(\mathsf{ask}\), such as FROST's Distributed Key Generation ^[10] (see {{ reference to the [Usage with FROST] section of this ZIP }} for further discussion). To support this we define an alternative derivation method using an additional "quantum resilience key", \(\mathsf{qk}\).

There can also be advantages to not deriving \(\mathsf{ask}\) directly from \(\mathsf{sk}\) for hardware wallets, in order to separate the authority to make proofs for the recovery protocol from the spend authorization key that is kept on the device (see {{ reference to the [Usage with hardware wallets] section of this ZIP }}). The derivation from \(\mathsf{qk}\) can also be used in that case.

Let \(\mathsf{use\_qk} \;{\small ⦂}\; \mathbb{B}\) be a flag that is set to true when the derivation from \(\mathsf{qk}\) is used, or false if \(\mathsf{ask}\) is derived directly from \(\mathsf{sk}\). (To match versions of this specification prior to {{ fill in version }}, \(\mathsf{use\_qk}\) MUST be set to false.)

\(\mathsf{ask} \;{\small ⦂}\; \mathbb{F}^{*}_{r_{\mathbb{P}}}\), the Spend validating key \(\mathsf{ak} \;{\small ⦂}\; \{ 1\,.\!.q_{\mathbb{P}}-1 \}\), the nullifier deriving key \(\mathsf{nk} \;{\small ⦂}\; \mathbb{F}^{*}_{q_{\mathbb{P}}}\), the optional quantum recovery key \(\mathsf{qk} \;{\small ⦂}\; \mathbb{B}^{{\kern-0.1em\tiny\mathbb{Y}}[\ell_{\mathsf{sk}}/8]} \cup \{\bot\}\), the \(\mathsf{Commit^{ivk}}\) randomness \(\mathsf{rivk} \;{\small ⦂}\; \mathbb{F}^{*}_{r_{\mathbb{P}}}\), the diversifier key \(\mathsf{dk} \;{\small ⦂}\; \mathbb{B}^{{\kern-0.1em\tiny\mathbb{Y}}[\ell_{\mathsf{dk}}/8]}\), the \(\mathsf{KA^{Orchard}}\) private key \(\mathsf{ivk} \;{\small ⦂}\; \{ 1\,.\!.q_{\mathbb{P}}-1 \}\), the outgoing viewing key \(\mathsf{ovk} \;{\small ⦂}\; \mathbb{B}^{{\kern-0.1em\tiny\mathbb{Y}}[\ell_{\mathsf{ovk}}/8]}\), and corresponding “internal” keys MUST be derived as follows:

let \(\mathsf{nk} = \mathsf{ToBase^{Orchard}}(\mathsf{PRF^{expand}_{sk}}([\mathtt{0x07}]))\)
if \(\mathsf{use\_qk}\):
\(\hspace{1.5em}\) generate \(\mathsf{ask} \;{\small ⦂}\; \mathbb{F}^{*}_{r_{\mathbb{P}}}\) and corresponding \(\mathsf{SpendAuthSig^{Orchard}}\) public key \(\mathsf{ak}^{\mathbb{P}} \;{\small ⦂}\; \mathbb{P}^*\)
\(\hspace{2.5em}\) using any suitably secure method that ensures the last bit of \(\mathsf{repr}_{\mathbb{P}}(\mathsf{ak}_{\mathbb{P}})\) is \(0\).
\(\hspace{1.5em}\) let \(\mathsf{ak} = \mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}_{\mathbb{P}})\)
\(\hspace{1.5em}\) let \(\mathsf{qk} = \mathsf{LEOS2BSP}_{256}(\mathsf{truncate}_{32}(\mathsf{PRF^{expand}_{sk}}([\mathtt{0x0B}])))\)
\(\hspace{1.5em}\) let \(\mathsf{rivk} = \mathsf{H}^{\mathsf{ext\_rivk}}_{\mathsf{qk}}(\mathsf{ak}, \mathsf{nk})\)
else:
\(\hspace{1.5em}\) let mutable \(\mathsf{ask} \leftarrow \mathsf{ToScalar^{Orchard}}(\mathsf{PRF^{expand}_{sk}}([\mathtt{0x06}]))\)
\(\hspace{1.5em}\) let \(\mathsf{ak}_{\mathbb{P}} = \mathsf{SpendAuthSig^{Orchard}.DerivePublic}(\mathsf{ask})\)
\(\hspace{1.5em}\) if the last bit (that is, the \(\tilde{y}\) bit) of \(\mathsf{repr}_{\mathbb{P}}(\mathsf{ak}_{\mathbb{P}})\) is \(1\):
\(\hspace{3em}\) set \(\mathsf{ask} \leftarrow -\mathsf{ask}\)
\(\hspace{1.5em}\) let \(\mathsf{ak} = \mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}_{\mathbb{P}})\)
\(\hspace{1.5em}\) let \(\mathsf{qk} = \bot\) (there is no quantum recovery key in this case)
\(\hspace{1.5em}\) let \(\mathsf{rivk} = \mathsf{ToScalar^{Orchard}}(\mathsf{PRF^{expand}_{sk}}([\mathtt{0x08}]))\)

Add the following notes:

• If \(\mathsf{ask}\), \(\mathsf{ak}\), \(\mathsf{nk}\), \(\mathsf{rivk}\), and \(\mathsf{rivk_{internal}}\) are not generated as specified in this section, then it may not be possible to recover the resulting notes as specified in {{ reference to this ZIP }} in the event that attacks using quantum computers become practical. In addition, to recover notes it is necessary to retain, or be able to rederive the following information.

  • When \(\mathsf{use\_qk}\) is false: the secret key \(\mathsf{sk}\). This will be the case when \(\mathsf{sk}\) is generated according to [ZIP-32], and the master seed or any secret key and chain code above \(\mathsf{sk}\) in the derivation hierarchy is retained.
  • When \(\mathsf{use\_qk}\) is true: the combination of the full viewing key \((\mathsf{ak}, \mathsf{nk}, \mathsf{rivk})\), the quantum recovery key \(\mathsf{qk}\), and the ability to make spend authorization signatures with \(\mathsf{ask}\).

  When the latter option is used, see {{ reference to the [Usage with hardware wallets] section of this ZIP }} for recommendations on the storage of, and access to \(\mathsf{qk}\).

§ 4.7.2 ‘Sending Notes (Sapling)’

Replace

Let \(\mathsf{CanopyActivationHeight}\) be as defined in § 5.3 ‘Constants’.

Let \(\mathsf{leadByte}\) be the note plaintext lead byte. This MUST be \(\mathsf{0x01}\) if for the next block, \(\mathsf{height} < \mathsf{CanopyActivationHeight}\), or \(\mathtt{0x02}\) if \(\mathsf{height} \geq \mathsf{CanopyActivationHeight}\).

with

Let \(\mathsf{leadByte}\) be the note plaintext lead byte, chosen according to § 3.2.1 ‘Note Plaintexts and Memo Fields’ with \(\mathsf{protocol} = \mathsf{Sapling}\).

Define \(\mathsf{H^{rcm,Sapling}_{rseed}}(\_) = \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}([\mathtt{0x04}]))\)

Define \(\mathsf{H^{esk,Sapling}_{rseed}}(\_) = \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}([\mathtt{0x05}]))\).

(\(\mathsf{H^{rcm,Sapling}}\) and \(\mathsf{H^{esk,Sapling}}\) intentionally take arguments that are unused.)

Replace the lines deriving \(\mathsf{rcm}\) and \(\mathsf{esk}\) with

Derive \(\mathsf{rcm} = \mathsf{H^{rcm,Sapling}_{rseed}}(\bot)\)

Derive \(\mathsf{esk} = \mathsf{H^{esk,Sapling}_{rseed}}(\bot)\)

§ 4.7.3 ‘Sending Notes (Orchard)’

Replace

Let \(\mathsf{leadByte}\) be the note plaintext lead byte, which MUST be \(\mathtt{0x02}\).

with

Let \(\mathsf{leadByte}\) be the note plaintext lead byte, chosen according to § 3.2.1 ‘Note Plaintexts and Memo Fields’ with \(\mathsf{protocol} = \mathsf{Orchard}\).

Define \(\mathsf{H^{rcm,Orchard}_{rseed}}(\mathsf{leadByte}, \underline{\text{ρ}}, \text{φ}, \mathsf{g}\!⋆_{\mathsf{d}}, \mathsf{pk}\!⋆_{\mathsf{d}}, \mathsf{v}[, \mathsf{AssetBase}\kern0.08em⋆]) = \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}(\mathsf{pre\_rcm}))\)

where \(\mathsf{pre\_rcm} = \begin{cases} [\mathtt{0x05}] \,||\, \underline{\text{ρ}},&\!\!\!\text{if } \mathsf{leadByte} = \mathtt{0x02} \\[0.3ex] [\mathtt{0x0A}] \,||\, \underline{\text{ρ}} \,||\, \mathsf{I2LEOSP}_{256}(\text{φ}) \\[-0.2ex] \hphantom{[\mathtt{0x0A}]} \,||\, \mathsf{LEBS2OSP}_{256}(\mathsf{g}\!⋆_{\mathsf{d}}) \,||\, \mathsf{LEBS2OSP}_{256}(\mathsf{pk}\!⋆_{\mathsf{d}}) \\[0.35ex] \hphantom{[\mathtt{0x0A}]} \,||\, \mathsf{I2LEOSP}_{64}(\mathsf{v}) \,[\,||\, \mathsf{LEBS2OSP}_{256}(\mathsf{AssetBase}\kern0.08em⋆)],&\!\!\!\text{if } \mathsf{leadByte} = \mathtt{0x03} \\ \end{cases}\)

Define \(\mathsf{H^{esk,Orchard}_{rseed}}(\underline{\text{ρ}}) = \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}([\mathtt{0x04}] \,||\, \underline{\text{ρ}}))\).

Define \(\mathsf{H^{\text{φ},Orchard}_{rseed}}(\underline{\text{ρ}}) = \mathsf{ToBase}(\mathsf{PRF^{expand}_{rseed}}([\mathtt{0x09}] \,||\, \underline{\text{ρ}}))\).

Insert before the derivation of \(\mathsf{esk}\):

Let \(\mathsf{g}\!⋆_{\mathsf{d}} = \mathsf{repr}_{\mathbb{P}}(\mathsf{g_d})\), \(\mathsf{pk}\!⋆_{\mathsf{d}} = \mathsf{repr}_{\mathbb{P}}(\mathsf{pk_d}) [\), and \(\mathsf{AssetBase}\kern0.08em⋆ = \mathsf{repr}_{\mathbb{P}}(\mathsf{AssetBase})]\).

and use these in the inputs to \(\mathsf{NoteCommit^{Orchard}}\).

Replace the lines deriving \(\mathsf{esk}\), \(\mathsf{rcm}\), and \(\text{φ}\) with

Derive \(\mathsf{esk} = \mathsf{H^{esk,Orchard}_{rseed}}(\underline{\text{ρ}})\)

Derive \(\mathsf{rcm} = \mathsf{H^{rcm,Orchard}_{rseed}}(\mathsf{leadByte}, \underline{\text{ρ}}, \text{φ}, \mathsf{g}\!⋆_{\mathsf{d}}, \mathsf{g}\!⋆_{\mathsf{d}}, \mathsf{v}[, \mathsf{AssetBase}\kern0.08em⋆])\)

Derive \(\text{φ} = \mathsf{H^{\text{φ},Orchard}_{rseed}}(\underline{\text{ρ}})\)

§ 4.8.2 ‘Dummy Notes (Sapling)’

Add

Let \(\mathsf{H^{rcm,Sapling}}\) be as defined in § 4.7.2 ‘Sending Notes (Sapling)’.

Replace the line deriving \(\mathsf{rcm}\) with

Derive \(\mathsf{rcm} = \mathsf{H^{rcm,Sapling}_{rseed}}(\bot)\)

Correct

A Spend description for a dummy Sapling input note is constructed as follows:

to

A Spend description for a dummy Sapling input note with note plaintext lead byte \(\mathtt{0x02}\) is constructed as follows:

§ 4.8.3 ‘Dummy Notes (Orchard)’

Insert before "The spend-related fields …":

Let \(\mathsf{leadByte}\) be the note plaintext lead byte, chosen according to § 3.2.1 ‘Note Plaintexts and Memo Fields’ with \(\mathsf{protocol} = \mathsf{Orchard}\).

Let \(\mathsf{H^{rcm,Orchard}}\) and \(\mathsf{H^{\text{φ},Orchard}}\) be as defined in § 4.7.3 ‘Sending Notes (Orchard)’.

Replace the lines deriving \(\mathsf{rcm}\) and \(\text{φ}\) with

Let \(\mathsf{g}\!⋆_{\mathsf{d}} = \mathsf{repr}_{\mathbb{P}}(\mathsf{g_d})\), \(\mathsf{pk}\!⋆_{\mathsf{d}} = \mathsf{repr}_{\mathbb{P}}(\mathsf{pk_d}) [\), and \(\mathsf{AssetBase}\kern0.08em⋆ = \mathsf{repr}_{\mathbb{P}}(\mathsf{AssetBase})]\).

Derive \(\mathsf{rcm} = \mathsf{H^{rcm,Orchard}_{rseed}}(\mathsf{leadByte}, \underline{\text{ρ}}, \text{φ}, \mathsf{g}\!⋆_{\mathsf{d}}, \mathsf{g}\!⋆_{\mathsf{d}}, \mathsf{v}[, \mathsf{AssetBase}\kern0.08em⋆])\)

Derive \(\text{φ} = \mathsf{H^{\text{φ},Orchard}_{rseed}}(\underline{\text{ρ}})\)

and use \(\mathsf{g}⋆_{\mathsf{d}}\), \(\mathsf{pk}⋆_{\mathsf{d}}\), and \(\mathsf{AssetBase}\kern0.08em⋆\) in the inputs to \(\mathsf{NoteCommit^{Orchard}}\).

§ 4.20.2 and § 4.20.3 ‘Decryption using an Incoming/Full Viewing Key (Sapling and Orchard)’

For both § 4.20.2 and § 4.20.3, replace

Let the constants \(\mathsf{CanopyActivationHeight}\) and \(\mathsf{ZIP212GracePeriod}\) be as defined in § 5.3 ‘Constants’.

Let \(\mathsf{height}\) be the block height of the block containing this transaction.

with

Let \(\mathsf{protocol}\) and \(\mathsf{allowedLeadBytes}\) be as defined in § 3.2.1 ‘Note Plaintexts and Memo Fields’.

Let \(\mathsf{H^{rcm,Sapling}}\) and \(\mathsf{H^{\text{esk},Sapling}}\) be as defined in § 4.7.2 ‘Sending Notes (Sapling)’.

Let \(\mathsf{H^{rcm,Orchard}}\), \(\mathsf{H^{\text{esk},Orchard}}\), and \(\mathsf{H^{\text{φ},Orchard}}\) be as defined in § 4.7.3 ‘Sending Notes (Orchard)’.

Let \(\mathsf{height}\) be the block height of the block containing this transaction, and let \(\mathsf{txVersion}\) be the transaction version.

For § 4.20.3, replace

if \(\mathsf{esk} \geq r_{\mathbb{G}}\) or \(\mathsf{pk_d} = \bot\), return \(\bot\)

with

if \(\mathsf{esk} \geq r_{\mathbb{G}}\) or \(\mathsf{pk_d} = \bot\) or (for Sapling) \(\mathsf{pk_d} \not\in \mathbb{J}^{(r)*}\) (see note below), return \(\bot\)

and in the note containing "However, this is technically redundant with the later check that returns \(\bot\) if \(\mathsf{pk_d} \not\in \mathbb{J}^{(r)*}\)", delete the word "later".

For both § 4.20.2 and § 4.20.3, replace

[Pre-Canopy] if \(\mathsf{leadByte} \neq \mathtt{0x01}\), return \(\bot\)
[Pre-Canopy] let \(\underline{\mathsf{rcm}} = \mathsf{rseed}\)
[Canopy onward] if \(\mathsf{height} < \mathsf{CanopyActivationHeight} + \mathsf{ZIP212GracePeriod}\) and \(\mathsf{leadByte} \not\in \{ \mathtt{0x01}, \mathtt{0x02} \}\), return \(\bot\)
[Canopy onward] if \(\mathsf{height} \geq \mathsf{CanopyActivationHeight} + \mathsf{ZIP212GracePeriod}\) and \(\mathsf{leadByte} \neq \mathtt{0x02}\), return \(\bot\)
for Sapling, let \(\mathsf{pre\_rcm} = [4]\) and \(\mathsf{pre\_esk} = [5]\)
for Orchard, let \(\underline{\text{ρ}} = \mathsf{I2LEOSP}_{256}(\mathsf{nf^{old}}\) from the same Action description\()\), \(\mathsf{pre\_rcm} = [5] \,||\, \underline{\text{ρ}}\), and \(\mathsf{pre\_esk} = [4] \,||\, \underline{\text{ρ}}\)

with

if \(\mathsf{leadByte} \not\in \mathsf{allowedLeadBytes^{protocol}}(\mathsf{height}, \mathsf{txVersion})\), return \(\bot\)
let \(\underline{\text{ρ}} = \mathsf{I2LEOSP}_{256}(\mathsf{nf^{old}}\) from the same Action description\()\)

For § 4.20.2, replace

[Canopy onward] let \(\underline{\mathsf{rcm}} = \begin{cases} \mathsf{rseed},&\!\!\!\text{if } \mathsf{leadByte} = \mathtt{0x01} \\ \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}(\mathsf{pre\_rcm})),&\!\!\!\text{otherwise} \end{cases}\)
let \(\mathsf{rcm} = \mathsf{LEOS2IP}_{256}(\underline{\mathsf{rcm}})\) and \(\mathsf{g_d} = \mathsf{DiversifyHash}(\mathsf{d})\). if \(\mathsf{rcm} \geq r_{\mathbb{G}}\) or (for Sapling) \(\mathsf{g_d} = \bot\), return \(\bot\)
[Canopy onward] if \(\mathsf{leadByte} \neq \mathtt{0x01}\):
\(\hspace{1.5em}\) \(\mathsf{esk} = \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}(\mathsf{pre\_esk}))\)
\(\hspace{1.5em}\) if \(\mathsf{repr}_{\mathbb{G}}(\mathsf{KA.DerivePublic}(\mathsf{esk}, \mathsf{g_d})) \neq \mathtt{ephemeralKey}\), return \(\bot\)
let \(\mathsf{pk_d} = \mathsf{KA.DerivePublic}(\mathsf{ivk}, \mathsf{g_d})\)

with

let \(\mathsf{g_d} = \mathsf{DiversifyHash}(\mathsf{d})\); for Sapling, if \(\mathsf{g_d} = \bot\), return \(\bot\)
[Canopy onward] if \(\mathsf{leadByte} \neq \mathtt{0x01}\):
\(\hspace{1.5em}\) let \(\mathsf{esk} = \mathsf{H^{esk,protocol}_{rseed}}(\underline{\text{ρ}})\)
\(\hspace{1.5em}\) if \(\mathsf{repr}_{\mathbb{G}}(\mathsf{KA.DerivePublic}(\mathsf{esk}, \mathsf{g_d})) \neq \mathtt{ephemeralKey}\), return \(\bot\)
let \(\mathsf{pk_d} = \mathsf{KA.DerivePublic}(\mathsf{ivk}, \mathsf{g_d})\)
let \(\mathsf{g}\!⋆_{\mathsf{d}} = \mathsf{repr}_{\mathbb{P}}(\mathsf{g_d})\), \(\mathsf{pk}\!⋆_{\mathsf{d}} = \mathsf{repr}_{\mathbb{P}}(\mathsf{pk_d}) [\), and \(\mathsf{AssetBase}\kern0.08em⋆ = \mathsf{repr}_{\mathbb{P}}(\mathsf{AssetBase})]\)
let \(\mathsf{rcm} = \begin{cases} \mathsf{LEOS2IP}_{256}(\mathsf{rseed}),&\!\!\!\text{if } \mathsf{leadByte} = \mathtt{0x01} \\ \mathsf{H^{rcm,protocol}_{rseed}}(\mathsf{leadByte}, \underline{\text{ρ}}, \mathsf{g}\!⋆_{\mathsf{d}}, \mathsf{pk}\!⋆_{\mathsf{d}}, \mathsf{v}[, \mathsf{AssetBase}\kern0.08em⋆]),&\!\!\!\text{otherwise} \end{cases}\)
if \(\mathsf{rcm} \geq r_{\mathbb{G}}\), return \(\bot\)

(The order of operations has to be altered because the derivation of \(\mathsf{rcm}\) can depend on \(\mathsf{g_d}\) and \(\mathsf{pk_d}\).)

For § 4.20.3, replace

[Canopy onward] let \(\underline{\mathsf{rcm}} = \begin{cases} \mathsf{rseed},&\!\!\!\text{if } \mathsf{leadByte} = \mathtt{0x01} \\ \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}(\mathsf{pre\_rcm})),&\!\!\!\text{otherwise} \end{cases}\)
let \(\mathsf{rcm} = \mathsf{LEOS2IP}_{256}(\underline{\mathsf{rcm}})\) and \(\mathsf{g_d} = \mathsf{DiversifyHash}(\mathsf{d})\)
if \(\mathsf{rcm} \geq r_{\mathbb{G}}\) or (for Sapling) \(\mathsf{g_d} = \bot\) or \(\mathsf{pk_d} \not\in \mathbb{J}^{(r)*}\) (see note below), return \(\bot\)

with

let \(\mathsf{g_d} = \mathsf{DiversifyHash}(\mathsf{d})\); for Sapling, if \(\mathsf{g_d} = \bot\), return \(\bot\)
let \(\mathsf{g}\!⋆_{\mathsf{d}} = \mathsf{repr}_{\mathbb{P}}(\mathsf{g_d}) [\) and \(\mathsf{AssetBase}\kern0.08em⋆ = \mathsf{repr}_{\mathbb{P}}(\mathsf{AssetBase})]\)
let \(\mathsf{rcm} = \begin{cases} \mathsf{LEOS2IP}_{256}(\mathsf{rseed}),&\!\!\!\text{if } \mathsf{leadByte} = \mathtt{0x01} \\ \mathsf{H^{rcm,protocol}_{rseed}}(\mathsf{leadByte}, \underline{\text{ρ}}, \mathsf{g}\!⋆_{\mathsf{d}}, \mathsf{pk}\!⋆_{\mathsf{d}}, \mathsf{v}[, \mathsf{AssetBase}\kern0.08em⋆]),&\!\!\!\text{otherwise} \end{cases}\)

(Note that there was previously a type error in both § 4.20.2 and § 4.20.3: \(\mathsf{ToScalar}\) returns an integer, not a byte sequence, and so cannot be assigned to \(\underline{\mathsf{rcm}}\).)

Replace \(\mathsf{ToBase^{Orchard}}(\mathsf{PRF^{expand}_{rseed}}([9] \,||\, \underline{\text{ρ}}))\) with \(\mathsf{H^{\text{φ},Orchard}_{rseed}}(\underline{\text{ρ}})\).

§ 5.3 ‘Constants’

Add a definition for \(\mathsf{ZIPXXXActivationHeight} \;{\small ⦂}\; \mathbb{N}\) as the activation height of this ZIP on Mainnet and Testnet.

ZIP 32

Add a \(\ast\) to the arrows leading to \(\mathsf{ask}\) and \(\mathsf{rivk}\) in the diagram in section ‘Orchard internal key derivation’ ^[11], with the following note:

\(\ast\) The derivations of \(\mathsf{ask}\) and \(\mathsf{rivk}\) shown in the diagram are not the only possibility. For further detail see § 4.2.3 ‘Orchard Key Components’ in the protocol specification. However, if \(\mathsf{ask}\), \(\mathsf{ak}\), \(\mathsf{nk}\), \(\mathsf{rivk}\), and \(\mathsf{rivk_{internal}}\) are not generated as in the diagram, then it may not be possible to recover the resulting notes as specified in {{ reference to this ZIP }} in the event that attacks using quantum computers become practical.

ZIP 212

Add a note before the Abstract:

This ZIP reflects the changes made to note encryption for the Canopy upgrade. It does not include subsequent changes in {{ reference to this ZIP }}.

ZIP 226

Add a requirement in the section Note Structure & Commitment that \(\text{ρ}\) and \(\text{φ}\) MUST be computed according to § 4.7.3 ‘Sending Notes (Orchard)’ with \(\mathsf{leadByte} = 3\) (for a note that is not a dummy note, a split note, or TODO an [issue note]).

Rationale

Cryptographic background

This rationale is written primarily for cryptologists and protocol designers familiar with the Zcash shielded protocols. It is recommended to first read the slides of, and/or watch the following presentations:

• Understanding Zcash Security at Zcon3 ^[12]
• Post-Quantum Zcash at ZconVI ^[4:1]

To understand the modelling of hash function and commitment security against a quantum adversary we also recommend ^[13].

Flow diagram for the Orchard and OrchardZSA protocols

This diagram shows, approximately, the derivation of Orchard keys, addresses, notes, note commitments, and nullifiers. It omits type conversions between curve points, field elements, byte sequences, and bit sequences, and so is not sufficiently precise to be used directly as a guide for implementation.

The bold lines are changes introduced by this ZIP, which all take the form of additional inputs to derivation functions or alternative derivations.

graph BT
  linkStyle default stroke:#0000a0, stroke-width:1.2px;
  classDef func fill:#d0ffb8;
  classDef sensitive fill:#ffb0b0;

  sk([sk]):::sensitive --> Hnk[H<sup>nk</sup>]:::func ---> nk([nk])
  sk --> Hask[H<sup>ask</sup>]:::func --> ask([ask]):::sensitive
  sk -....-> HrivkLegacy[H<sup>rivkLegacy</sup>]:::func -.-> rivk([rivk])
  ask --> ak([ak])
  sk ==> Hqk[H<sup>qk</sup>]:::func ==> qk([qk]):::sensitive
  qk ===> Hrivk[H<sup>rivk</sup>]:::func
  ak ==> Hrivk
  nk ==> Hrivk
  Hrivk ==> rivk
  ak -.-> HrivkInternal[H<sup>rivkInternal</sup>]:::func
  nk -.-> HrivkInternal
  rivk -.-> HrivkInternal -.-> rivkInternal([rivk<sub>internal</sub>])
  rivkInternal -.-> Commitivk[Commit<sup>ivk</sup>]:::func
  rivk ---> Commitivk
  ak --> Commitivk
  nk --> Commitivk
  Commitivk --> ivk([ivk])
  d([d]) --> HashToCurve:::func --> gd([g<sub>d</sub>])
  gd --> ivkmul[［ivk］g<sub>d</sub>&nbsp;]:::func
  ivk --> ivkmul
  gd --> NoteCommit:::func
  pkd --> NoteCommit
  rseed --> Hpsi[H<sup>φ</sup>]:::func
  v([v, AssetBase]) ==> pre_rcm([pre_rcm])
  pkd ===> pre_rcm
  gd ==> pre_rcm
  rho([ρ]) --> pre_rcm
  psi ==> pre_rcm
  ivkmul --> pkd([pk<sub>d</sub>])
  v --> NoteCommit
  pre_rcm --> Hrcm[H<sup>rcm</sup>]:::func
  rseed([rseed]) --> Hrcm
  rho ---> Hpsi
  Hrcm --> rcm([rcm])
  Hpsi --> psi([φ])
  rcm --> NoteCommit
  psi --> NoteCommit
  rho --> NoteCommit
  cm --> DeriveNullifier:::func
  psi --> DeriveNullifier
  rho --> DeriveNullifier
  nk --> DeriveNullifier
  NoteCommit --> cm([cm])
  DeriveNullifier --> nf([nf])
  cm --> cmx([cm<sub><i>x</i></sub>])

  NoteCommit ~~~~~~ KeyBox:::keybox
  classDef keybox stroke:#000000, fill:#fffff0;
  classDef spacer opacity:0;
  subgraph KeyBox[<div style="margin:1.2em;font-size:22px"><b>Key</b></div>]
    direction BT
    function:::func ~~~ dummyC
    key([sensitive key]):::sensitive ~~~ dummyA
    value([value]) ~~~ dummyE
    dummyC( ) -->|existing| dummyD( ) ~~~ spacer( ):::spacer
    dummyA( ) ==>|new| dummyB( ) ~~~ spacer
    dummyE( ) -.->|optional| dummyF( ) ~~~ spacer
  end

Legacy case

graph BT
  linkStyle default stroke:#0000a0, stroke-width:1.2px;
  classDef func fill:#d0ffb8;
  classDef sensitive fill:#ffb0b0;
  classDef spacer opacity:0;

  HrivkLegacy[H<sup>rivkLegacy</sup>]:::func -----> rivk([rivk])
  Hnk[H<sup>nk</sup>]:::func -----> nk([nk])
  Hask[H<sup>ask</sup>]:::func ---> ask([ask]):::sensitive
  ak --> Commitivk
  subgraph PostQC[<div style="margin:1.2em;font-size:20px"><b>Post-Q circuit</b></div>]
    direction BT
    ask --> ak([ak])
    ask ~~~ spacer2( ):::spacer
    subgraph PostQHC[<div style="margin:1.2em;font-size:20px"><b>Post-Q H/W circuit</b></div>]
      direction BT
      sk ~~~~ spacer1( ):::spacer
      sk --> HrivkLegacy[H<sup>rivkLegacy</sup>]:::func
      sk([sk]):::sensitive --> Hnk[H<sup>nk</sup>]:::func
      sk --> Hask[H<sup>ask</sup>]:::func
    end
  end
  subgraph PreQC[<div style="margin:1.2em;font-size:20px"><b>Pre-Q circuit</b></div>]
    direction BT
    rivk --> Commitivk[Commit<sup>ivk</sup>]:::func
    nk --> Commitivk
    Commitivk --> ivk([ivk])
    ivk ~~~ spacer3( ):::spacer
  end

FROST (and optionally more-efficient PQ hardware wallet) case

graph BT
  linkStyle default stroke:#0000a0, stroke-width:1.2px;
  classDef func fill:#d0ffb8;
  classDef sensitive fill:#ffb0b0;
  classDef spacer opacity:0;

  sk([sk]):::sensitive --> Hnk[H<sup>nk</sup>]:::func ---> nk([nk])
  sk -.-> Hask[H<sup>ask</sup>]:::func -.-> ask
  sk ==> Hqk[H<sup>qk</sup>]:::func ===> qk([qk]):::sensitive
  ask([ask]):::sensitive --> ak([ak])
  subgraph PostQC[<div style="margin:1em;font-size:20px"><b>Post-Q circuit</b></div>]
    direction BT
    qk([qk]):::sensitive ==> Hrivk[H<sup>rivk</sup>]:::func
    Hrivk ~~~ spacer1( ):::spacer
  end
  ak ==> Hrivk
  nk([nk]) ==> Hrivk
  nk ~~~ spacer2( ):::spacer
  Hrivk ==> rivk
  subgraph PreQC[<div style="margin:1em;font-size:20px"><b>Pre-Q circuit</b></div>]
    direction BT
    rivk([rivk]) --> Commitivk[Commit<sup>ivk</sup>]:::func
    ak --> Commitivk
    nk --> Commitivk
    Commitivk --> ivk([ivk])
    ivk ~~~ spacer3( ):::spacer
  end

Let us consider the security of the Orchard protocol against a discrete-log-breaking adversary — which by definition includes quantum adversaries. Similar attacks apply to the Sapling protocol.

Suppose that the proof system has been replaced by one that is post-quantum knowledge-sound.

Repairing the note commitment Merkle tree

\(\mathsf{MerkleCRH^{Orchard}}\) is instantiated using \(\mathsf{SinsimillaHash}\) ^[14]. Its collision resistance depends on the discrete log relation problem on the Pallas curve ^[15], and so it is not post-quantum collision-resistant. However, because the note commitment tree is public, it is possible to re-hash all of its leaves to construct a new Merkle tree using a post-quantum collision-resistant hash function. Suppose this has been done.

The post-quantum security of Merkle trees —considered as position-binding vector commitments which is the property required by Zcash [^zcash-security-slides]— is proven under reasonable assumptions in ^[16], Section 6.

Attacks against binding of note commitments

We still face the problem that \(\mathsf{NoteCommit^{Orchard}}\) is not binding against a discrete-log-breaking adversary: given the discrete log relations between bases, we can easily write a linear equation in the scalar field with multiple solutions of the inputs for a given commitment.

This allows an adversary to find two distinct notes corresponding to openings of \(\mathsf{NoteCommit^{Orchard}}\) on the same commitment. They create one note as an output and spend the other note — which may have a greater value (or a value in a different asset), breaking the Balance property.

Repairing note commitments

We prefer to fix this without changing \(\mathsf{NoteCommit^{Orchard}}\) itself. Instead we change how \(\mathsf{rcm}\) is computed to be a hash of \((\mathsf{rseed}, \text{ρ}, \text{φ}, \mathsf{g_d}, \mathsf{pk_d}, \mathsf{v}[, \mathsf{AssetBase}])\), as detailed in the [Specification] section. Specifically, when \(\mathsf{leadByte} = \mathtt{0x03}\) we have:

\(\mathsf{H^{rcm,Orchard}_{rseed}}(\mathsf{leadByte}, \underline{\text{ρ}}, \text{φ}, \mathsf{g}\!⋆_{\mathsf{d}}, \mathsf{pk}\!⋆_{\mathsf{d}}, \mathsf{v}[, \mathsf{AssetBase}\kern0.08em⋆]) = \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}(\mathsf{pre\_rcm}))\)

\(\text{where } \mathsf{pre\_rcm} = [\mathtt{0x0A}] \,||\, \underline{\text{ρ}} \,||\, \mathsf{I2LEOSP}_{256}(\text{φ})\)
\(\hphantom{\text{where } \mathsf{pre\_rcm} = [\mathtt{0x0A}]} \,||\, \mathsf{LEBS2OSP}_{256}(\mathsf{g}\!⋆_{\mathsf{d}}) \,||\, \mathsf{LEBS2OSP}_{256}(\mathsf{pk}\!⋆_{\mathsf{d}})\)
\(\hphantom{\text{where } \mathsf{pre\_rcm} = [\mathtt{0x0A}]} \,||\, \mathsf{I2LEOSP}_{64}(\mathsf{v}) \,[\,||\, \mathsf{LEBS2OSP}_{256}(\mathsf{AssetBase}\kern0.08em⋆)]\)

Then we view the output of \(\mathsf{NoteCommit^{Orchard}}(\mathsf{g_d}, \mathsf{pk_d}, \mathsf{v}, \textP\mathsf{inputs})\) as the point addition of a randomization term \([\mathsf{H^{rcm,Orchard}_{rseed}}(\mathsf{pre\_rcm})]\, \mathcal{R}\), and some other function of \(\mathsf{rseed}\) and \(\mathsf{pre\_rcm}\) which, without loss of generality, we can write as \([f(\mathsf{inputs})]\, \mathcal{R}\). That is, \[\mathsf{NoteCommit^{Orchard}}(\mathsf{inputs}) = [\mathsf{H^{rcm,Orchard}}(\mathsf{inputs}) + f(\mathsf{rseed}, \mathsf{pre\_rcm})]\, \mathcal{R}.\]

First we informally argue security in the classical ROM. We will model \(\mathsf{H^{rcm}}\) as a random oracle independent of \(f\) with uniform output on \(\mathbb{F}_{r_{\mathbb{P}}}\).

The fact that \(\mathsf{NoteCommit^{Orchard}}\) has \(\text{φ} = \mathsf{H}^{\text{φ}}(\mathsf{rseed}, \text{ρ})\) as an input does not affect the analysis provided that \(\mathsf{H^{rcm}}\) and \(\mathsf{H}^{\text{φ}}\) can be treated as independent. In practice both are defined in terms of \(\mathsf{PRF^{expand}}\), but with strict domain separation, and so the assumption of independence is reasonable as long as BLAKE2b-512 can be modelled as a random oracle. Note that since the input to \(\mathsf{H^{rcm}}\) needs more than one BLAKE2b input block, we require that a HAIFA sponge can be modelled as a random oracle which is justified by ^[17].

For each \(\mathsf{H^{rcm}}\) oracle query the adversary chooses \(\mathsf{inputs}\) and obtains a "random" \(\mathsf{rcm} = \mathsf{H^{rcm}}(\mathsf{inputs})\), such that the distribution of \(\mathsf{rcm} + f(\mathsf{inputs})\) is computationally indistinguishable from the uniform distribution on \(\mathbb{F}_{r_\mathbb{P}}\). Therefore \(\mathsf{cm}_x = \mathsf{Extract}_{\mathbb{P}}([\mathsf{H^{rcm}}(\mathsf{inputs}) + f(\mathsf{inputs})]\, \mathcal{R})\) is computationally indistinguishable from an output of \(\mathsf{Extract}_{\mathbb{P}}\) applied to uniformly distributed Pallas curve points. The number of such outputs is \((\mathbb{F}_{r_\mathbb{P}} + 1)/2\) (one for each possible \(x\)-coordinate of Pallas curve points, plus one for the zero point \(\mathcal{O}_{\mathbb{P}}\) which is mapped to \(0\)).

Only one point maps to \(0\), as opposed to two points mapping to every other possible output of \(\mathsf{Extract}_{\mathbb{P}}\), but that has negligible effect.

The number of queries needed to find a collision therefore follows a distribution negligibly far from that expected for a collision attack on an ideal hash function mapping from the input domain to a set of size \((\mathbb{F}_{r_\mathbb{P}} + 1)/2 \approx 2^{253}\).

In order to adapt this argument to the quantum setting, we need to consider collapsing hash functions as defined in ^[13:1].

TODO: \(\mathsf{Extract}_{\mathbb{P}}\) is not collapsing. Is \(\mathsf{Extract}_{\mathbb{P}}([\mathsf{H^{rcm}}(\mathsf{inputs}) + f(\mathsf{inputs})]\, \mathcal{R})\) collapsing?

By the argument in ^[18], the best known generic quantum attack on a hash function is simply the classical attack of ^[19]. (In particular, the Brassard–Høyer–Tapp algorithm ^[20] is entirely unimplementable for a 253-bit output size: to achieve the claimed speed-up, it would require running Grover's algorithm with a quantum circuit that does random accesses to a \(2^{92.3}\)-bit quantum memory.) Therefore, an output size of 253 bits does not exclude a hash function from being post-quantum collision-resistant. It is possible that there could be better-than-generic quantum attacks against BLAKE2b, but none have been published to our knowledge. In practice, we consider it reasonable to assume that BLAKE2b-512 has the properties needed for \(\mathsf{H^{rcm}}\) to be post-quantum collision-resistant.

TODO: discuss ^[21] (sponge security), ^[13:2] (collapse-binding property).

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 circuit, Orchard note commitments can be considered binding on all of the note fields.

Note that the argument associated with Theorem 5.4.4 in the protocol specification ("A \(\bot\) output from \(\mathsf{SinsemillaHashToPoint}\) yields a nontrivial discrete log 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-log-breaking or quantum adversary. Therefore, the post-quantum recovery circuit will need to use complete curve additions to implement Sinsemilla.

Attacks against binding of ivk

The security of Orchard against double-spending also depends on the binding property of … Informally, the security argument is that there is only one value of ..

It is also possible to use an attack against the binding property of \(\mathsf{Commit^{ivk}}\) to steal Orchard notes.

We use essentially the same fix as for \(\mathsf{NoteCommit^{Orchard}}\), with \(\mathsf{rivk}\) in place of \(\mathsf{rcm}\).

There is a complication: contrary to the situation with notes, it is not feasible to … for existing addresses that might still be in use.

Usage with FROST

It is possible to use … with FROST by setting \(\mathsf{use\_qk}\) to true when … The value of \(\mathsf{qk}\) used to construct \(\mathsf{rivk}\) MUST be remembered.

However, this requires the party who constructs the proof …

This preserves the security property that a \(t\)-of-\(n\) threshold of parties is needed to authorize access to the funds, but unfortunately loses the usual advantage of FROST that the parties can sign using their shares without reconstructing the secret key. That is, during the process of using the post-quantum protocol to recover funds, there will necessarily be at least one party with sufficient information to reconstruct the secret key, who could therefore potentially misappropriate the funds.

It might be possible to use a multi-party computation to address this, but it seems difficult (essentially equivalent to defining a post-quantum threshold signature scheme that can securely use existing Shamir secret shares) and we leave it to future work.

Usage with hardware wallets

The same \(\mathsf{use\_qk}\) option can help with hardware wallets where we do not want the \(\mathsf{ask}\) value to leave the hardware. In this case we give the host wallet \((\mathsf{ak}, \mathsf{nk}, K)\).

Informal Security Argument

The argument is that if \(\mathsf{H^rcm}\) and \(\mathsf{H^{φ}}\) are random oracles, \(\mathsf{rcm}\) is an unpredictable function of the note fields. There are two values of \(\mathsf{cm}\) that match \(\mathsf{cm}_x\) in their \(x\)-coordinate. Because the output of \(\mathsf{NoteCommit^{Orchard}}\) is of the form \(\mathsf{cm} = F(\mathsf{note}) + [\mathsf{rcm}]\, \mathcal{R}\), for any given note we have exactly two values of \(\mathsf{rcm}\) that will pass the commitment check.

Suppose there are \(N\) legitimate notes in the tree. In an attack where the adversary is trying to find a note that will pass the commitment check without actually being a note in the tree, they succeed with probability \(2N/r_{\mathbb{P}}\) per attempt where \(r_{\mathbb{P}}\) is the order of the Pallas curve, and that is negligible because \(N \leq 2^{32} \ll r_{\mathbb{P}}\).

We're not finished yet because we also have to prove that the nullifier is computed deterministically for a given note.

All of the inputs to \(\mathsf{DeriveNullifier}\) are things we committed to in the protocol so far except \(\mathsf{nk}\). By the same argument used pre-quantumly, there is only one \(\mathsf{ivk}\) for a given \((\mathsf{g_d}, \mathsf{pk_d})\). So in order to just use the existing protocol for this part, we would need to prove that there is only one \(\mathsf{nk}\) such that \(\mathsf{Commit^{ivk}_{rivk}}(\mathsf{ak}, \mathsf{nk}) = \mathsf{ivk}\). Unfortunately that's not true; \(\mathsf{Commit^{ivk}}\) is instantiated by \(\mathsf{SinsemillaShortCommit}\) which is not post-quantum binding.

Instead, 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} \rightarrow \mathsf{ak}\) is deterministic). In particular, \(\mathsf{ivk}\) is essentially a random function of \(\mathsf{sk}\), and so we expect that an adversary has no better attack than to guess values of \(\mathsf{sk}\) until they hit 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 is \(2T/(r_{\mathbb{P}}-1)\), which is negligible provided that \(T \ll r_{\mathbb{P}}\).

The idea is that, without changing the currently proposed OrchardZSA protocol, we can make sure that notes created from now on will remain spendable after we switch off the pre-quantum OrchardZSA protocol.

Problem: neither \(\mathsf{NoteCommit}\) nor \(\mathsf{Commit^{ivk}}\) are post-quantum binding.

However, we can work around this by modifying the definition of \(\mathsf{pre\_rcm}\) for v6 transactions, so that \(\mathsf{rcm}\) and \(\mathsf{cm}\) become pq-{binding, hiding} commitments to \((\mathsf{g_d}, \mathsf{pk_d}, \mathsf{v}, [\mathsf{AssetBase},\!]\, \text{ρ})\) randomized by \(\mathsf{rseed}\). Then we check the derivations of \(\mathsf{rcm}\) and \(\text{φ}\) in the circuit.

When we rehash the commitment tree using a pq-collision-resistant hash instead of Sinsemilla, we will include both \(\text{ρ}\) and \(\mathsf{cm}_x\) for each note (i.e. what is currently the leaf layer becomes \(\mathsf{MerkleCRH}(\text{ρ}, \mathsf{cm}_x)\) where \(\mathsf{MerkleCRH}\) is pq-collision-resistant). This change might not be necessary; it just removes potential complications due to duplicate commitments for the same note.

Define:

• \(\mathsf{H^{rcm,Orchard}_{rseed}}(\mathsf{leadByte}, \underline{\text{ρ}}, \text{φ}, \mathsf{g_d}, \mathsf{pk_d}, \mathsf{v}[, \mathsf{AssetBase}]) = \mathsf{ToScalar}(\mathsf{PRF^{expand}_{rseed}}(\mathsf{pre\_rcm}))\)
  where \(\mathsf{pre\_rcm} = [10] \,||\, \underline{\text{ρ}} \,||\, \mathsf{I2LEOSP}_{256}(\text{φ})\)
  \(\hspace{9.13em} ||\, \mathsf{LEBS2OSP}_{256}(\mathsf{repr}_{\mathbb{P}}(\mathsf{g_d})) \,||\, \mathsf{LEBS2OSP}_{256}(\mathsf{repr}_{\mathbb{P}}(\mathsf{pk_d}))\)
  \(\hspace{9.13em} ||\, \mathsf{I2LEOSP}_{64}(\mathsf{v}) \,[\,||\, \mathsf{LEBS2OSP}_{256}(\mathsf{repr}_{\mathbb{P}}(\mathsf{AssetBase}))]\)
  when \(\mathsf{leadByte} = 3\).
• \(\mathsf{H^{φ}_{rseed}}(\underline{\text{ρ}}) = \mathsf{ToBase^{Orchard}}(\mathsf{PRF^{expand}_{rseed}}([9] \,||\, \underline{\text{ρ}}))\)
• \(\mathsf{H}^{\mathsf{ext\_rivk}}_{\mathsf{sk}}(\mathsf{ak}, \mathsf{nk}) = \mathsf{ToScalar^{Orchard}}(\mathsf{PRF^{expand}_{sk}}([\mathtt{0x84}] \,||\, \mathsf{I2LEOSP}_{256}(\mathsf{ak})\)
  \(\hspace{21.46em} ||\, \mathsf{I2LEOSP}_{256}(\mathsf{nk})))\)
• \(\mathsf{H}^{\mathsf{int\kern0.08em\_\kern0.08emrivk}}_{K}(\mathsf{ak}, \mathsf{nk}) = \mathsf{ToScalar^{Orchard}}(\mathsf{PRF}^{\mathsf{expand}}_{K}([\mathtt{0x83}] \,||\, \mathsf{I2LEOSP}_{256}(\mathsf{ak})\)
  \(\hspace{21.46em} ||\, \mathsf{I2LEOSP}_{256}(\mathsf{nk})))\)
• \(\mathcal{G}^{\mathsf{Orchard}} = \mathsf{GroupHash}^{\mathbb{P}}(\texttt{“z.cash:Orchard”}, \texttt{“G”})\)

A valid instance of a Recovery statement assures that given a primary input:
\[ \begin{array}{l} ( \mathsf{rt^{Orchard}} \;{\small ⦂}\; \{ 0\,.\!.q_{\mathbb{P}}-1 \}, \\ \hphantom{(}\mathsf{rk} \;{\small ⦂}\; \mathsf{SpendAuthSig^{Orchard}.Public} ), \end{array} \] the prover knows an auxiliary input:
\[ \begin{array}{l} ( \mathsf{use\_qk} \;{\small ⦂}\; \mathbb{B}, \\ \hphantom{(}\mathsf{path} \;{\small ⦂}\; \{ 0\,.\!.q_{\mathbb{P}}-1 \}^{[\mathsf{MerkleDepth^{Orchard}}]}, \\ \hphantom{(}\mathsf{pos} \;{\small ⦂}\; \{ 0\,.\!.2^{\mathsf{MerkleDepth^{Orchard}}}-1 \}, \\ \hphantom{(}\mathsf{domain} \;{\small ⦂}\; \{ \mathsf{ext\_rivk}, \mathsf{int\_rivk} \}, \\ \hphantom{(}K \;{\small ⦂}\; \mathbb{B}^{[\ell_{\mathsf{sk}}]}, \\ \hphantom{(}\mathsf{\alpha} \;{\small ⦂}\; \mathbb{F}_{r_{\mathbb{P}}}, \\ \hphantom{(}\mathsf{ak}^{\mathbb{P}} \;{\small ⦂}\; \mathbb{P}*, \\ \hphantom{(}\mathsf{rivk} \;{\small ⦂}\; \mathbb{F}_{r_{\mathbb{P}}}, \\ \hphantom{(}\mathsf{rseed} \;{\small ⦂}\; \mathbb{B}^{{\kern-0.1em\tiny\mathbb{Y}}[32]}, \\ \hphantom{(}\mathsf{g_d} \;{\small ⦂}\; \mathbb{P}^*, \\ \hphantom{(}\mathsf{v} \;{\small ⦂}\; \{ 0\,.\!.2^{\ell_{\mathsf{value}}}-1 \}, \\ \hphantom{(}\text{ρ} \;{\small ⦂}\; \mathbb{F}_{q_{\mathbb{P}}} ) \end{array} \] such that the following conditions hold:
\[ \begin{array}{l} \{\;\, \mathsf{use\_qk} \Rightarrow \big(\;\, \mathsf{rk} = \mathsf{SpendAuthSig^{Orchard}.RandomizePublic}(\alpha, \mathsf{ak}^{\mathbb{P}}) \\ \hspace{7.4em} \wedge\; \mathsf{rivk} = \mathsf{H^{rivk}_qk}(\mathsf{ak}, \mathsf{nk}) \,\big) \\ \wedge\; \text{not } \mathsf{use\_qk} \Rightarrow \big(\;\, \mathsf{ak}^{\mathbb{P}} = [\mathsf{ToScalar^{Orchard}}(\mathsf{PRF^{expand}_{sk}}([6]))]\, \mathcal{G}^{\mathsf{Orchard}} \\ \hspace{9.1em} \wedge\; \mathsf{nk} = \mathsf{ToBase^{Orchard}}(\mathsf{PRF^{expand}_{sk}}([7])) \\ \hspace{9.1em} \wedge\; \mathsf{rivk} = \mathsf{ToScalar^{Orchard}}(\mathsf{PRF^{expand}_{sk}}([8])) \,\big) \\ \wedge\; \mathsf{ak} = \mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}^{\mathbb{P}}) \\ \wedge\; \text{let } \mathsf{ivk} = \mathsf{Commit^{ivk}_{rivk}}(\mathsf{ak}, \mathsf{nk}) \\ \wedge\; \mathsf{ivk} \not\in \{0, \bot\} \\ \wedge\; \text{let } \mathsf{pk_d} = [\mathsf{ivk}]\, \mathsf{g_d} \\ \wedge\; \text{let } \text{φ} = \mathsf{H}^{\text{φ}}_{\mathsf{rseed}}(\underline{\text{ρ}}) \\ \wedge\; \text{let } \mathsf{rcm} = \mathsf{H^{rcm}_{rseed}}(\underline{\text{ρ}}, \text{φ}, \mathsf{g_d}, \mathsf{pk_d}, \mathsf{v}) \\ \wedge\; \text{let } \mathsf{cm} = \mathsf{NoteCommit^{Orchard}_{rcm}}(\mathsf{repr}_{\mathbb{P}}(\mathsf{g_d}), \mathsf{repr}_{\mathbb{P}}(\mathsf{pk_d}), \mathsf{v}, \text{ρ}, \text{φ}) \\ \wedge\; \mathsf{cm} \neq \bot \\ \wedge\; \text{let } \mathsf{cm}_x = \mathsf{Extract}_{\mathbb{P}}(\mathsf{cm}) \\ \wedge\; \text{let } \mathsf{leaf} = \mathsf{MerkleCRH}(\mathsf{cm}_x, \text{ρ}) \\ \wedge\; \mathsf{path} \text{ is a path to } \mathsf{leaf} \text{ in the rehashed commitment tree} \\ \wedge\; \mathsf{nf} = \mathsf{DeriveNullifier_{nk}}(\text{ρ}, \text{φ}, \mathsf{cm}) \text{ is the revealed nullifier} \\ \} \end{array} \]

(We don't need to check the derivation of \(\mathsf{g_d}\) from \(\mathsf{d}\).)

Cost

• 6 uses of \(\mathsf{PRF^{expand}}\), with a total of 7 BLAKE2b-512 input blocks
  • It's slightly annoying that \(\mathsf{H^{rcm}}\) requires two input blocks.
  • We could get away with one fewer if we did not support the case \(\mathsf{rivk\_is\_internal} \wedge \text{not } \mathsf{direct\_ask}\), but it seems cleaner to support that.
• 1 use of \(\mathsf{Commit^{ivk}}\) (\(\mathsf{SinsemillaShortCommit}\))
• 1 use of \(\mathsf{NoteCommit^{Orchard}}\) (\(\mathsf{SinsemillaCommit}\))
• 1 full-width fixed-base Pallas scalar multiplication, \([\mathsf{ask}]\, \mathcal{G}^{\mathsf{Orchard}}\)
• 1 full-width variable-base Pallas scalar multiplication, \([\mathsf{ivk}]\, \mathsf{g_d}\)
• 1 Merkle tree path check
• 1 additional use of \(\mathsf{MerkleCRH}\) to compute \(\mathsf{leaf}\).

The expensive parts of this are the 6 BLAKE2b compressions.

Deployment

As far as I'm aware, all existing Zcash wallets already derive \((\mathsf{ak}, \mathsf{nk}, \mathsf{rivk})\) from a spending key \(\mathsf{sk}\) in the way specified in § 4.2.3 Orchard Key Components and assumed by this protocol.

TODO: FROST

The part of the protocol that is new is the different input for \(\mathsf{pre\_rcm}\). It would have been possible to use a separate pq-binding commitment, but \(\mathsf{H^rcm}\) is already pq-binding and so doing it this way involves fewer components. This also allows us to avoid any security compromise and use 256-bit cryptovalues for both integrity and randomization, which would otherwise have been difficult.

I suggest to deploy this change with v6 transactions. That is, every shielded output of a v6-onward transaction will be a pq-resilient note. This implies that when we turn off the pre-quantum protocol, we burn v5 and earlier outputs. Since v6 already changes the note encryption (in order to support memo bundles), this approach to deployment reduces the risk of the kind of mess that happened with ZIP 212, where some wallets were following the old protocol after the Canopy upgrade and sending non-conformant note plaintexts.

When a compliant wallet receives a note in a v5 or earlier transaction, the associated funds are not pq-resilient and need to be spent to v6 in order to make them so.

Note: if we prioritize spending non-pq-resilient notes, it is conceivable that an adversary could exploit this to improve arity leakage attacks. On the other hand, adversaries can already choose note values to manipulate the note selection algorithm to some extent.

Decisions from R&D Meeting 2025-04-02

• Do this for Orchard
  • Supported in v6 txs.
  • Maybe supported in v5 txs.
    • Argument for not doing so is that when rehashing the tree, we could omit all cms from v5 txs, resulting in a smaller tree (which coincidentally excludes the sandblasting notes).
    • Argument for doing so is that it's not any more complicated to do, and we cannot distinguish v5 and v6 notes within the Orchard pool.
      • Also, even in this case we can omit all v5 notes from the tree created before today as they didn't know about this protocol, which also excludes the sandblasting notes. So the tree would also be much smaller, just not quite as small as if we didn't do this for v5.
  • When PQ adversary becomes real:
    • The live Orchard circuit (which would be OrchardZSA) is turned off.
    • An Orchard PQ recovery circuit is turned on.
      • If we are in an emergency situation and there is no efficient PQ payment protocol deployed, the Orchard PQ recovery circuit could be extended to also permit creating notes; it would be inefficient and slow, but would let payments continue.
      • In the ideal case, there would be some other PQ-sound protocol deployed (e.g. the long-term storage symmetric protocol, or the eventual PQ payment protocol), and so we only need the Orchard PQ recovery circuit for claiming notes out of the Orchard pool.
    • A timer of 3 years (measured in block-years) starts.
    • When the timer expires, the Orchard PQ recovery circuit is turned off, and all value in the Orchard pool at that time is removed from circulation via the NSM.
• Don't do this for Sapling
  • Can't reuse the full security argument, so there's a bunch of extra work this incurs, that would risk us not deploying it concurrently with v6 txs.
  • Incompatible with non-hardened ZIP 32 child key derivation.
  • Instead, when PQ adversary becomes real, Sapling protocol is turned off, and all value in the Sapling pool at that time is removed from circulation via the NSM.
    • Rationale: Sapling funds cannot be spent safely in PQ world, and directing them to NSM is better for the Zcash ecosystem than burning them (as it helps with the network security / development budget), and also people will have had time to .
• The protocol turning-off and removal from circulation gets implemented as part of NU7 with a consensus flag IS_PQ_ADVERSARY_REAL set to false (so the rules do nothing in NU7, but can be tested).
  • When someone gets around to implementing the Orchard PQ recovery circuit (maybe alongside the PQ payment protocol, maybe earlier), it can also be integrated into the above ahead of time behind the IS_PQ_ADVERSARY_REAL flag.
  • This makes the "react to a PQ adversary" ZIP / NU simply "set IS_PQ_ADVERSARY_REAL to true", and we don't get delayed squabbling about what to do with the now-unusable ZEC left in the pool.

References