1 Introduction

This volume of The Zcash Arboretum constructs threshold spend authorisation for Orchard-protocol notes, for Actions of either pool of the Orchard protocol (Ironwood Guide, §“The Orchard protocol and its two pools”, Definitions “Orchard protocol” and “Orchard pool, Ironwood pool”). Any threshold number of the participants, the threshold and the number of participants being those of Definition 2.1, jointly produce, for an Action spending a note of a threshold key, a signature that consensus accepts as an ordinary RedPallas spend-authorisation signature, with the same format and the same validation as a signature by a single holder of the spend authorising key $\mathrm{𝖺𝗌𝗄}$. No signing run reconstructs the signing key; a trusted dealer computes it at key generation; no step of distributed key generation computes it, and no source cited in this volume proves that protocol secure (Remark 3.9). RedPallas and spend authorisation are cited, not re-derived: Ironwood Guide, §“The RedPallas signature scheme” and §“Randomised validating keys”.

The construction has two layers. The first is FROST, the two-round threshold Schnorr protocol of Komlo and Goldberg as RFC 9591 specifies it, run on a Shamir sharing of $\mathrm{𝖺𝗌𝗄}$. The second is its re-randomised variant (ePrint 2024/436), specified for Zcash in ZIP 312, which shifts the shares, the verification shares and the group key of each signing run by one randomiser so that the aggregate verifies under the Action’s randomised validating key; it is defined in §5.2 and constructed in §5.5 (Construction 5.10) with the randomiser of §5.3, and its correctness is Theorem 5.11.

The Orchard pool is spend-only: no transaction increases its value, and every Orchard-pool Action creates its note at the address of the note it consumes (ZIP 258, Draft, “Consensus rules from NU6.3 activation”; Ironwood Guide, §“The Orchard protocol and its two pools”), so no value enters the pool and, by consensus, only a party able to authorise spends for an address can create an Orchard-pool note to it. ZIP 326 (Draft) forbids conforming wallets to send Orchard-pool funds to a key derived with $\mathrm{𝗎𝗌𝖾}\mathrm{\_}\mathrm{𝗊𝗌𝗄}=\mathrm{𝗍𝗋𝗎𝖾}$ (ZIP 2005), which every key from distributed key generation must use, so under that rule such a key holds no Orchard-pool notes, a rule that consensus does not enforce, while a dealer-shared key whose $\mathrm{𝖺𝗌𝗄}$ is derived from a spending key may spend notes of either pool; both facts are established, with their sources, in §6.4.

The volume constructs FROST as RFC 9591 specifies it; key generation by a trusted dealer and by a distributed protocol; the re-randomised variant for RedPallas that ZIP 312 specifies, with its ciphersuite FROST(Pallas, BLAKE2b-512); the proof that its output is an ordinary spend-authorisation signature; the key-generation constraints of ZIP 2005; and the security of each part, with its assumptions and status. ZIP 312 also defines the ciphersuite FROST(Jubjub, BLAKE2b-512) for Sapling spend authorisation by RedJubjub; it is named here and not developed. Transparent inputs, transports and particular tools are outside the scope. The volume assumes the Math Guide and the Crypto Guide, and cites the Ironwood Guide for RedPallas, randomised validating keys, the signature digest and the construction of a transaction. It is non-normative: the protocol specification, the ZIPs and RFC 9591 are authoritative.

The volume describes the protocol as specified for NU7 (Ironwood Guide, §“Scope and status”, Definition “Network upgrade”), whose deployment ZIP 259 has status Draft; NU7 changes neither spend authorisation nor the transaction formats on which the volume relies, version-$5$ and version-$6$ transactions remaining valid (ZIP 259, Abstract). NU6.3 is active, and its rules, including those of ZIP 2005 that ZIP 258 deploys, are part of the protocol so described.

The Ironwood Guide, §“Scope and status”, Definition “ZIP”, names the ZIP statuses Draft and Reserved. A ZIP has status Proposed when, after Draft, it has been advanced upon consideration, feedback and rough consensus of the community (ZIP 0, “ZIP Status Field”). A ZIP of status Draft, Proposed, Active, Implemented or Final carries normative text; a Reserved, Withdrawn, Rejected or Obsolete ZIP carries none.

The sources of the volume, each with its standing, are the following.

1. (a)

   D. Connolly, C. Komlo, I. Goldberg and C. A. Wood, “The Flexible Round-Optimized Schnorr Threshold (FROST) Protocol for Two-Round Schnorr Signatures”, RFC 9591, June 2024, a product of the IRTF Crypto Forum Research Group in the category Informational, not an Internet Standards Track specification, specifies two-round FROST signing over any prime-order group and hash, with ciphersuites for none of the Zcash groups, leaves key generation out of scope, gives a trusted dealer for completeness in its Appendix C, and is normative text in the sense of Definition 1.1.

2. (b)

   ZIP 312, “FROST for Spend Authorization Multisignatures”, status Draft, category Wallet, specifies the re-randomised variant for Zcash as changes to RFC 9591 (randomiser generation, Round Two, and re-randomised signing, aggregation and share verification) together with the ciphersuites FROST(Jubjub, BLAKE2b-512) and FROST(Pallas, BLAKE2b-512), names $\mathrm{𝖺𝗌𝗄}$ as the key to be shared, requires key generation to be consistent with FROST without specifying one, and specifies no consensus rule.

3. (c)

   ZIP 2005, “Ironwood Quantum Recoverability”, status Proposed, category Consensus, whose key rules take effect with NU6.3, which ZIP 258 (Draft) deploys, and stand in the protocol as specified for NU7, is used for its constraints on FROST key generation and the keys they produce: “Usage with FROST”, its replacement text for § 4.2.3 “Orchard Key Components” (“Changes to the Protocol Specification”), and “Deployment”.

4. (d)

   C. P. L. Gouvêa and C. Komlo, “Re-Randomized FROST”, IACR ePrint 2024/436, an unrefereed preprint with no peer-reviewed venue, defines re-randomisable threshold signatures and their unforgeability game and claims unforgeability of Rerandomized FROST in the random-oracle model under the algebraic one-more discrete logarithm assumption, with a proof that §7.4 finds incomplete (Remark 7.17), so that the claim is an open problem (Table 3); a result that rests on it alone is stated as the preprint’s, not as established.

5. (e)

   C. Komlo and I. Goldberg, “FROST: Flexible Round-Optimized Schnorr Threshold Signatures”, IACR ePrint 2020/852, published at SAC 2020 (LNCS 12804, pp. 34–65) and cited by RFC 9591 as [FROST20], gives the original scheme, its distributed key generation, in which every participant acts as a Feldman dealer and proves knowledge of its constant coefficient by a Schnorr proof (its Figure 1), and the original security argument.

6. (f)

   M. Bellare, S. Tessaro and C. Zhu, “Stronger Security for Non-Interactive Threshold Signatures: BLS and FROST”, IACR ePrint 2022/833, cited in its current revision, has a preliminary version that is part of M. Bellare, E. Crites, C. Komlo, M. Maller, S. Tessaro and C. Zhu, “Better than Advertised Security for Non-Interactive Threshold Signatures”, CRYPTO 2022, which RFC 9591 cites as [StrongerSec22]; each work is cited by its own title and authors.

7. (g)

   E. Crites, C. Komlo and M. Maller, “How to Prove Schnorr Assuming Schnorr: Security of Multi- and Threshold Signatures”, IACR ePrint 2021/1375, which defines FROST2 and analyses it with its own key generation, is cited only for FROST2 in §7.2 and for the nearest result recorded in Remark 7.13.

8. (h)

   The revision of ZIP 312 proposed in zcash/zips pull request 895, linked from ZIP 2005, “Deployment”, is unmerged and not normative text, and is cited only as a published design.

Notation is additive throughout; the multiplicative forms of the papers are converted at citation. The generic sections work in a group $𝔾$ of prime order $q$ with generator $B$ and identity $𝒪$, whose discrete logarithm problem and random oracles are those of the Crypto Guide, §“The discrete logarithm problem”, Definition “Discrete logarithm problem, DLP”, and §“The random oracle model”. The Pallas instance sets

(Ironwood Guide, §“Fields, groups, and encodings”, and §“The spending key and the spend-side secrets”, Construction “Spend validating key and sign normalisation”). Scalar multiplication is written $[k]P$, and scalars are elements of ${𝔽}_q$. The star encoding $P^{\star }$, the encodings ${\mathrm{LE}}_k$ and ${\mathrm{𝖨𝟤𝖫𝖤𝖮𝖲𝖯}}_k$, concatenation $\parallel$ and monospace byte-string literals are those of the Ironwood Guide, §“Fields, groups, and encodings”. The element and scalar serialisations ${\mathrm{𝗌𝖾𝗋}}_{𝔾}$, ${\mathrm{𝗌𝖾𝗋}}_{{𝔽}_q}$ and their inverses ${\mathrm{𝖽𝖾𝗌𝖾𝗋}}_{𝔾}$, ${\mathrm{𝖽𝖾𝗌𝖾𝗋}}_{{𝔽}_q}$ are components of a ciphersuite (Definition 4.1).

The spend-side symbols follow the Ironwood Guide, §“The spending key and the spend-side secrets”: $\mathrm{𝖺𝗌𝗄}$ is the spend authorising key, ${\mathrm{𝖺𝗄}}^{\mathbb{P}}=[\mathrm{𝖺𝗌𝗄}]G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$ the spend validating key as a point, $\mathrm{𝖺𝗄}={\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}({\mathrm{𝖺𝗄}}^{\mathbb{P}})$ its extracted coordinate, and $\mathrm{𝗇𝗄}$, $\mathrm{𝗋𝗌𝗄}$ and $\mathrm{𝗋𝗄}$ are as there. ZIP 2005 uses the same notation.

A signing set is written $I$ and its Lagrange coefficients ${\lambda }_{I,i}$ (Definition 2.3), the symbols of the Crypto Guide, §“Secret sharing”, in Construction “Shamir $t$-of-$n$ secret sharing” and in Remark “The leak, and where it is harmless”, which names this volume as the consumer of ${\lambda }_{I,i}$-weighted recombination. The generator $G$ of that Guide’s Construction “Feldman verifiable secret sharing” is $B$ here. The group key and verification shares are $\mathrm{𝑃𝐾}$ and ${\mathrm{𝑃𝐾}}_i$, the secret shares ${\mathrm{𝑠𝑘}}_i$ (Definition 2.5). Query counts of cited bounds are written $Q$, or $q_s$ and $q_h$ with subscripts, never a bare $q$, which is the group order. The British spelling randomiser replaces ZIP 312’s randomizer; titles of ZIPs and papers keep their own spelling. Table 1 maps the names of the sources to those of the volume; later text uses the latter, and §6 also the protocol specification’s names where it follows that text.