IX FROST Guide: Threshold RedPallas: FROST and its Zcash integration surfaces 4 Signing and aggregation 6 The aggregate as a spend-authorisation signature

5 Re-randomised FROST for spend authorisation

This section states the re-randomised variant of FROST that ZIP 312 specifies, in the order of the mechanism: why spend authorisation requires a shifted key; the re-randomisable threshold scheme; the derivations of the randomiser, with the bound showing that the specified derivation, fed the signature digest as its message, succeeds only with negligible probability; the signers’ duty to check the signed message; the re-randomised rounds with their correctness; and the requirements and trust model of ZIP 312 that this flow forces. The ciphersuite is generic, with the randomiser hash $H_{R}$ of Definition 4.1, part (f); the Pallas instance is Construction 6.1. ZIP 312 is Draft.

5.1 Spend authorisation under randomised validating keys

The single-signer objects are cited, not re-derived. The spend-authorisation instance of RedPallas (Ironwood Guide, §“The RedPallas signature scheme”, Construction “RedPallas” and Definition “Spend-authorisation and binding-signature instances”) works in the Pallas group, of prime order $q=p_{\mathsf{Vesta}}$ , with base

B=G^{\mathsf{SpendAuth}}=\mathsf{GroupHash}(\texttt{z.cash:Orchard},\texttt{G}).

A key pair is $(x,X=[x]B)$ . A signature on a message $M$ is $\sigma=\underline{R}\,\|\,\mathsf{I2LEOSP}_{256}(S)$ , with challenge $c=\mathsf{H}^{\circledast}(\underline{R}\,\|\,\underline{X}\,\|\,M)$ , where $\mathsf{H}^{\circledast}$ reduces modulo $p_{\mathsf{Vesta}}$ the BLAKE2b-512 output under the personalisation Zcash_RedPallasH. Validation accepts if and only if the first $32$ bytes decode to a point $R$ , a non-canonical encoding decoding to $\bot$ and being rejected; $S<p_{\mathsf{Vesta}}$ ; and $[S]B=R+[c]X$ , the cofactor being one on Pallas. The nonce and challenge hashes take $\underline{X}$ : the scheme is key-prefixed (Remark “Key prefixing” there). The message of every spend-authorisation signature is the signature digest $\mathsf{SigHash}$ (Ironwood Guide, §“Transaction digests and signatures”, Definition “Signature digest”). The deployed rules are those of the protocol specification, §“RedDSA, RedJubjub, and RedPallas” and §“Spend Authorization Signature (Sapling and Orchard)”.

Re-randomisation by a randomiser $\alpha\in\mathbb{F}_{q}$ maps a key pair $(x,X)$ to $(x+\alpha,\,X+[\alpha]B)$ (Crypto Guide, §“Key re-randomisation and unlinkability”, Definition “Key re-randomisation”); the identity randomiser is $0$ . The randomiser generator $\mathsf{GenRandom}$ draws $T$ uniformly from the $80$ -byte strings and returns $\mathsf{H}^{\circledast}(T)$ (Ironwood Guide, Definition “Randomiser generator and key re-randomisation”).

For each Action the spender draws $\alpha:=\mathsf{GenRandom}()$ and sets

\mathsf{rsk}:=\mathsf{ask}+\alpha,\qquad\mathsf{rk}:=\mathsf{ak}^{\mathbb{P}}+% [\alpha]G^{\mathsf{SpendAuth}}=[\mathsf{rsk}]G^{\mathsf{SpendAuth}},

with $\mathsf{ask}$ sign-normalised; the Action publishes $\mathsf{rk}$ and the signature under $\mathsf{rsk}$ on $\mathsf{SigHash}$ (Ironwood Guide, §“Randomised validating keys”, Construction “Randomised validating key”). Two consensus rules apply: $\mathsf{rk}\neq\mathcal{O}$ , and the signature is valid under $\mathsf{rk}$ on $\mathsf{SigHash}$ (protocol specification, §“Action Descriptions” and §“Spend Authorization Signature (Sapling and Orchard)”). The verifier’s key is therefore $\mathsf{rk}$ , which equals $\mathsf{ak}^{\mathbb{P}}$ only for $\alpha=0$ , an event of probability at most $1/p_{\mathsf{Vesta}}+2^{-512}$ under $\mathsf{GenRandom}$ (Ironwood Guide, Assumption “The RedPallas hash as a random oracle”). Only these scheme-level statements are inherited. The Ironwood Guide constructs $\mathsf{ask}$ only for keys with $\mathsf{use\_qsk}=\mathsf{false}$ (Remark “Scope of the key derivations”), so its key-derived theorems are not cited for threshold keys (§7.5).

For every Action of the Orchard protocol, in either pool, the single signer proceeds in the order: draw $\alpha$ ; compute $\mathsf{rk}$ ; compute $\mathsf{SigHash}$ of the transaction, which commits to $\mathsf{rk}$ ; sign it under $\mathsf{rsk}$ . The Action proof takes $\alpha$ as auxiliary (secret) input and $\mathsf{rk}$ as primary input and, being authorising data, may be computed after signing (Ironwood Guide, §“Construction of a transaction”, Construction “Ironwood-pool bundle”, steps “Randomised keys”, “Proof”, “Digest” and “Spend authorisation”; ZIP 229, “Motivation”). Sapling spends are outside the volume.

Definition 5.1 (Strong unforgeability under re-randomised keys).

A re-randomisable signature scheme is a signature scheme $(\mathsf{GenPrivate},\mathsf{DerivePublic},\mathsf{Sign},\mathsf{Validate})$ with private-key set $\mathsf{Private}$ and public-key set $\mathsf{Public}$ , together with a randomiser set $\mathcal{R}$ , a randomised generator $\mathsf{GenRandom}$ with values in $\mathcal{R}$ , maps

\mathsf{RandomizePrivate}\colon\mathcal{R}\times\mathsf{Private}\to\mathsf{% Private},\qquad\mathsf{RandomizePublic}\colon\mathcal{R}\times\mathsf{Public}% \to\mathsf{Public},

and an identity randomiser $\alpha_{\mathrm{id}}\in\mathcal{R}$ , such that:

1.

each $\mathsf{RandomizePrivate}(\alpha,\cdot)$ is injective and efficiently invertible;
2.

$\mathsf{RandomizePrivate}(\alpha_{\mathrm{id}},\cdot)$ is the identity;
3.

for every $\mathit{sk}$ , the value $\mathsf{RandomizePrivate}(\alpha,\mathit{sk})$ with $\alpha\leftarrow\mathsf{GenRandom}()$ is distributed as $\mathsf{GenPrivate}()$ ;
4.

$\mathsf{RandomizePublic}(\alpha,\mathsf{DerivePublic}(\mathit{sk}))=\mathsf{% DerivePublic}(\mathsf{RandomizePrivate}(\alpha,\mathit{sk}))$ for every $\alpha$ and $\mathit{sk}$ .

Let $\mathit{sk}\leftarrow\mathsf{GenPrivate}()$ and $\mathit{vk}:=\mathsf{DerivePublic}(\mathit{sk})$ . The signing oracle keeps a set $\mathcal{Q}$ , initially empty; on a query $(m,\alpha)$ it returns $\sigma:=\mathsf{Sign}_{\mathsf{RandomizePrivate}(\alpha,\mathit{sk})}(m)$ and adds $(m,\sigma)$ to $\mathcal{Q}$ . The scheme is SURK-CMA secure if no efficient adversary, given $\mathit{vk}$ and the oracle, outputs, except with negligible probability, a triple $(m^{\prime},\sigma^{\prime},\alpha^{\prime})$ with

\mathsf{Validate}_{\mathsf{RandomizePublic}(\alpha^{\prime},\mathit{vk})}(m^{% \prime},\sigma^{\prime})=1\quad\text{and}\quad(m^{\prime},\sigma^{\prime})% \notin\mathcal{Q}.

Freshness is on the message–signature pair; the forgery may be under any re-randomisation of $\mathit{vk}$ , the identity included.

The definition is that of the protocol specification, §“Signature with Re-Randomizable Keys”, adapted there from Fleischhacker et al. (PKC 2016, Section 3) with the randomiser and key arguments swapped; the specification requires every spend-authorisation instance to meet it (§“Spend Authorization Signature (Sapling and Orchard)”). The single-signer spend-authorisation instance meets it: the Ironwood Guide’s Proposition “Unforgeability under re-randomisation” (“RedPallas unforgeability”), part (ii), under discrete logarithms on Pallas and the RedPallas hash as a random oracle, requires freshness only of the triple of key, message and signature, and states the implication. The threshold form of the notion is an open problem (Definition 1.1; Table 3).

Proposition 5.2 (A fixed-key aggregate under a randomised key).

Let key material with signing key $s$ and group key $\mathit{PK}=[s]B$ be valid (Definition 2.5), over a ciphersuite meeting Assumption 4.2 with distance $\delta$ .

(i)

For every signing set $I$ , $\sum_{i\in I}\lambda_{I,i}\,\mathit{sk}_{i}=s$ . Hence every honest run of FROST (Constructions 4.4, 4.8 and 4.9) outputs a signature valid under the one key $\mathit{PK}$ , whatever $I$ , apart from the failed runs of Theorem 4.11.
(ii)

Fix $\alpha\in\mathbb{F}_{q}$ with $\alpha\neq 0$ and $\mathit{PK}+[\alpha]B\neq\mathcal{O}$ before the experiment. In any experiment whose parties make at most $Q_{2}$ queries to $H_{2}$ in total, the probability that one output pair $(m,(R,z))$ , designated in advance (such as the aggregate of a run), is accepted by the single-party verification (Definition 4.1, part (e)) both under $\mathit{PK}$ and under $\mathit{PK}+[\alpha]B$ is at most

$(Q_{2}+2)\,(1/q+\delta).$

Proof.

(i) Lemma 2.4 with $f$ the sharing polynomial gives the sum; Theorem 4.11 gives the rest.

(ii) Write $\mathit{PK}^{\prime}:=\mathit{PK}+[\alpha]B$ . Acceptance of $(R,z)$ on $m$ under both keys means $[z]B=R+[c]\,\mathit{PK}=R+[c^{\prime}]\,\mathit{PK}^{\prime}$ , where

c=H_{2}\bigl{(}\mathsf{ser}_{\mathbb{G}}(R)\,\|\,\mathsf{ser}_{\mathbb{G}}(% \mathit{PK})\,\|\,m\bigr{)},\qquad c^{\prime}=H_{2}\bigl{(}\mathsf{ser}_{% \mathbb{G}}(R)\,\|\,\mathsf{ser}_{\mathbb{G}}(\mathit{PK}^{\prime})\,\|\,m% \bigr{)};

hence $[c]\,\mathit{PK}=[c^{\prime}]\,\mathit{PK}^{\prime}$ , that is $c\,s=c^{\prime}(s+\alpha)$ . The two inputs differ, since $\mathit{PK}^{\prime}\neq\mathit{PK}$ and $\mathsf{ser}_{\mathbb{G}}$ is injective. Add the two queries at the inputs of the designated pair if they are missing, so that at most $Q_{2}+2$ queries are made. Call a query with key component $\mathit{PK}$ and one with key component $\mathit{PK}^{\prime}$ and the same $R$ and $m$ partners; each query has at most one partner. For each query define a target, where $s+\alpha\neq 0$ because $\mathit{PK}^{\prime}\neq\mathcal{O}$ . If $s\neq 0$ and the partner was answered earlier, the target is the value the query’s own answer must take for the equation to hold: $c\,s/(s+\alpha)$ for a query with key $\mathit{PK}^{\prime}$ , and $c^{\prime}(s+\alpha)/s$ for a query with key $\mathit{PK}$ . If $s=0$ , the equation reads $c^{\prime}\alpha=0$ , and every query with key $\mathit{PK}^{\prime}$ has target $0$ . A pair valid under both keys makes some query hit its target: the later-answered query of the pair if $s\neq 0$ , the query with key $\mathit{PK}^{\prime}$ if $s=0$ . Each target is fixed before the fresh answer is drawn, and that answer takes any fixed value with probability at most $1/q+\delta$ (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”, part (3)). The union bound over the at most $Q_{2}+2$ queries gives the claim. □

The argument is that of the Ironwood Guide’s Remark “Key prefixing” for the unshifted response. The bound is for $\alpha$ fixed in advance; with $\alpha$ chosen adaptively, one query may pair with many. For FROST(Pallas, BLAKE2b-512) the per-query term $1/q+\delta$ is below $2^{-253.9}$ .

Spend authorisation re-randomises the validating key of every Action with a randomiser from $\mathsf{GenRandom}$ , which makes validating keys unlinkable (Ironwood Guide, Proposition “Unlinkability of randomised validating keys”); a signer bound to one key cannot follow it (ZIP 312, “Motivation”). By part (i), a plain FROST aggregate is valid under $\mathit{PK}=\mathsf{ak}^{\mathbb{P}}$ , which consensus accepts only in an Action with $\mathsf{rk}=\mathsf{ak}^{\mathbb{P}}$ , that is with randomiser zero, publishing the spend validating key in every such Action. By part (ii), it is valid under $\mathsf{rk}$ for a nonzero randomiser only with the stated probability. The re-randomised variant shifts every participant’s share, every verification share and the group key by one common scalar.

5.2 Re-randomisable threshold signatures

Definition 5.3 (Re-randomisable threshold signature scheme).

A re-randomisable threshold signature scheme is a scheme of Definition 2.8 over a group $\mathbb{G}$ of prime order $q$ with generator $B$ , together with a randomiser set $\mathcal{X}$ and:

1.

a randomised algorithm $\mathsf{GenRand}$ with values in $\mathcal{X}$ ;
2.

an effective-randomiser map $H_{r}\colon\mathcal{X}\times\{0,1\}^{*}\to\mathbb{F}_{q}$ , sending a randomiser $\alpha$ and an auxiliary string $\mathit{aux}$ to the effective randomiser $\hat{\alpha}:=H_{r}(\alpha,\mathit{aux})$ ;

the shifts

	$\displaystyle\mathsf{RandShare}(\mathit{sk}_{i},\alpha,\mathit{aux}):=\mathit{% sk}_{i}+\hat{\alpha},\qquad\mathsf{RandPKShare}(\mathit{PK}_{i},\alpha,\mathit% {aux}):=\mathit{PK}_{i}+[\hat{\alpha}]B,$
	$\displaystyle\mathsf{RandPK}(\mathit{PK},\alpha,\mathit{aux}):=\mathit{PK}+[% \hat{\alpha}]B;$

such that the following correctness holds. For valid key material with signing key $s$ , every $(\alpha,\mathit{aux})$ with $\mathit{PK}+[\hat{\alpha}]B$ in the domain of $\mathsf{ser}_{\mathbb{G}}$ (every $(\alpha,\mathit{aux})$ when $\mathsf{ser}_{\mathbb{G}}$ is total), every signing set $I$ and every message $m$ : the shifted shares, verification shares and group key are valid key material for $s+\hat{\alpha}$ ; and a run of the signing rounds on the shifted material over $I$ on $m$ in which every party is honest outputs either $\bot$ or a signature that verification accepts under $\mathit{PK}+[\hat{\alpha}]B$ , and outputs $\bot$ with negligible probability.

The definition is that of ePrint 2024/436, Definition 5, which names the algorithms, with general $\mathsf{RandShare}$ , $\mathsf{RandPKShare}$ and $\mathsf{RandPK}$ and a distribution on $\mathcal{X}$ , without a correctness relation; the correctness clause is this volume’s. The auxiliary string models a contribution from the transcript of another protocol, so that a new session changes the shifted key even under a repeated $\alpha$ (Remark 1 there).

FROST is an instance, with the identity exception of Theorem 5.11 in a suite whose element serialisation is not total, with $H_{r}$ a hash into scalars, whose role the randomiser hash $H_{R}$ of ZIP 312 plays, and with Rounds One and Two and aggregation run unchanged on the shifted material (ePrint 2024/436, Figure 5, read in additive notation and with the challenge input order of RFC 9591, nonce commitment, key, message, in place of the figure’s key, nonce commitment, message; ZIP 312, “Re-randomizable FROST”); its rounds are constructed once, in Construction 5.10. The shifted material is valid key material: for the sharing polynomial $f$ , the polynomial $f+\hat{\alpha}$ has degree at most $t-1$ , constant term $s+\hat{\alpha}$ and values $\mathit{sk}_{i}+\hat{\alpha}$ , and $[s+\hat{\alpha}]B=\mathit{PK}+[\hat{\alpha}]B$ , $[\mathit{sk}_{i}+\hat{\alpha}]B=\mathit{PK}_{i}+[\hat{\alpha}]B$ . Recombination on it is Lemma 2.4 applied to $f+\hat{\alpha}$ , whose case $f=1$ gives $\sum_{i\in I}\lambda_{I,i}=1$ . Correctness of the instance is Theorem 5.11.

5.3 Randomiser generation

Construction 5.4 (Randomiser generation of ZIP 312).

After Round One, let $m$ be the message and $L$ the commitment list of Definition 4.3, sorted in ascending order of the nonzero identifiers. The Coordinator draws $u$ uniformly from the $N_{\mathrm{s}}$ -byte strings, $N_{\mathrm{s}}$ the length of a serialised scalar ( $32$ for FROST(Pallas, BLAKE2b-512)), and sets

\hat{\alpha}:=H_{R}\bigl{(}u\,\|\,\mathrm{enc}(L,m)\bigr{)},

where $\mathrm{enc}$ is any encoding from which $m$ and, for each member of $L$ , its identifier, hiding commitment and binding commitment are recovered uniquely. It sends $\hat{\alpha}$ itself to the signers. Class (Definition 1.1): specified (ZIP 312, Draft).

The construction is that of ZIP 312, “Randomizer Generation” and “Round Two - Signature Share Generation”. The ZIP’s default encoding is a byte serialisation of the message and the commitment list; it permits any other encoding under which all these values are unambiguously encoded.

In spend authorisation the message is $m=\mathsf{SigHash}(T)$ for the transaction $T$ , and $\mathsf{SigHash}$ commits to the randomised validating key of every Action: ZIP 244, “T.4c: orchard_actions_noncompact_digest”, field T.4c.ii, kept for version 6, and with the same structure for the Ironwood pool, by ZIP 229, “Transaction Identifiers, Auth Digests, and Signature Digests” (Ironwood Guide, Definition “Signature digest”). The aggregate is accepted only under $\mathsf{rk}$ , which for the shifted key of Definition 5.3 is $\mathit{PK}+[\hat{\alpha}]B$ . A valid threshold spend by Construction 5.4 with this message therefore needs a fixed point: a randomiser $\hat{\alpha}$ equal to $H_{R}$ of an input containing the digest of a transaction that contains $\mathit{PK}+[\hat{\alpha}]B$ .

Proposition 5.5 (No randomiser derived from the signature digest).

Let $\mathit{PK}$ be the group key of an Orchard-protocol threshold key, with $q=p_{\mathsf{Vesta}}$ and $B=G^{\mathsf{SpendAuth}}$ . Let $H_{R}=\mathrm{ToScalar}\circ H^{\prime}_{R}$ , where $H^{\prime}_{R}$ is a random oracle onto a set of size $h$ and $\mathrm{ToScalar}$ maps a uniform element of that set to within $\delta$ of uniform on $\mathbb{F}_{q}$ , the one-function form of Assumption 4.2; for FROST(Pallas, BLAKE2b-512), $h=2^{512}$ . Let an algorithm $\mathcal{A}$ , given $\mathit{PK}$ and making at most $q_{h}$ queries to $H^{\prime}_{R}$ , output a transaction $T$ with at most $N_{A}$ Actions, an index $j$ , and a string $x=u\,\|\,\mathrm{enc}(L,m)$ with $u$ of $N_{\mathrm{s}}$ bytes, as in Construction 5.4. It wins if $m=\mathsf{SigHash}(T)$ and the randomised validating key of Action $j$ of $T$ equals $\mathit{PK}+[H_{R}(x)]B$ . With $Q:=q_{h}+1$ ,

\mathrm{Pr}[\mathcal{A}\ \text{wins}]\;\leq\;\frac{Q}{h}+\sqrt{Q\cdot\mathrm{% Adv}^{\mathrm{cr}}(\mathcal{B})+Q^{2}N_{A}\,(1/q+\delta)}

for an algorithm $\mathcal{B}$ of about twice the running time of $\mathcal{A}$ , where $\mathrm{Adv}^{\mathrm{cr}}(\mathcal{B})$ is its probability of breaking the Ironwood Guide’s Assumption “Collision resistance of BLAKE2b”.

Proof.

Only $H^{\prime}_{R}$ is modelled as a random oracle; the digest tree of $\mathsf{SigHash}$ is computed with BLAKE2b under other personalisations, and only its collision resistance is used. Let $\epsilon$ be the winning probability. Define an algorithm $\mathcal{F}$ for the Crypto Guide’s Theorem “General forking lemma” (§“Security in the random oracle model and the forking lemma”), with challenge set the range of $H^{\prime}_{R}$ , of size $h$ , and $Q$ challenges. On input $\mathit{PK}$ and challenges $c_{1},\dots,c_{Q}$ , it runs $\mathcal{A}$ , answering its $k$ -th distinct query to $H^{\prime}_{R}$ with $c_{k}$ ; on the output $(T,j,x)$ it queries $x$ itself if $\mathcal{A}$ did not; it returns $(I,(T,j,x))$ , with $I$ the index of the query at $x$ if $\mathcal{A}$ wins and $I=0$ otherwise. Its acceptance probability is $\epsilon$ , so the forking algorithm succeeds with probability

\mathit{frk}\;\geq\;\epsilon\Bigl{(}\frac{\epsilon}{Q}-\frac{1}{h}\Bigr{)}.

On success the two runs coincide until the $I$ -th query is asked, so both query the same string $x$ at index $I$ , and both win with that $x$ , with outputs $T_{1}$ and $T_{2}$ and challenges $c_{I}\neq c^{\prime}_{I}$ . The string $x$ determines $m$ , since $u$ has fixed length and the encoding is unambiguous; hence $\mathsf{SigHash}(T_{1})=\mathsf{SigHash}(T_{2})=m$ .

If the tuples of randomised validating keys of $T_{1}$ and $T_{2}$ differ, descent through the two digest trees from their equal roots yields two distinct pairs of personalisation and input with equal BLAKE2b output, each node hashing a uniquely decodable input (ZIP 244, “TxId Digest” and “Signature Digest”; ZIP 229, “Transaction Identifiers, Auth Digests, and Signature Digests”): at the first node whose inputs differ, the two pairs collide. Running the forking algorithm and this descent is $\mathcal{B}$ .

Otherwise $T_{2}$ contains the point $\mathit{PK}+[\mathrm{ToScalar}(c_{I})]B$ , which the first run placed at index $j$ of $T_{1}$ . The second run is independent of $c_{I}$ . For a fixed fork index $i$ , each of the at most $N_{A}$ keys of $T_{2}$ equals $\mathit{PK}+[\mathrm{ToScalar}(c_{i})]B$ only if $\mathrm{ToScalar}(c_{i})$ takes one value fixed by the second run, which has probability at most $1/q+\delta$ (Math Guide, Theorem “Properties of statistical distance”, part (3)); summing over the keys and over the $Q$ indices,

\mathit{frk}\;\leq\;\mathrm{Adv}^{\mathrm{cr}}(\mathcal{B})+QN_{A}\,(1/q+% \delta).

With the lower bound, $\epsilon^{2}-(Q/h)\,\epsilon-K\leq 0$ for $K:=Q\cdot\mathrm{Adv}^{\mathrm{cr}}(\mathcal{B})+Q^{2}N_{A}(1/q+\delta)$ , so $\epsilon\leq\bigl{(}Q/h+\sqrt{(Q/h)^{2}+4K}\bigr{)}/2\leq Q/h+\sqrt{K}$ . □

The derivation of Construction 5.4 with the digest as message therefore yields a valid threshold spend only with negligible probability: infeasible in the random-oracle model, not impossible. For FROST(Pallas, BLAKE2b-512), $1/q+\delta<2^{-253.9}$ and $Q/h=Q\cdot 2^{-512}$ . Construction 5.4 is the only specified derivation, so no specified randomiser derivation is usable for spend authorisation; the order that a usable one must respect is Proposition 6.12.

Construction 5.6 (Seed-and-commitments randomiser).

After Round One, let $L$ be the commitment list over the signing set $I$ . The Coordinator draws a seed $v$ uniformly from the $32$ -byte strings and sends it to every member of $I$ over a confidential and authenticated channel (Definition 2.10, type (b)). The Coordinator and every member of $I$ compute

\hat{\alpha}:=H_{R}\bigl{(}v\,\|\,\mathsf{enc}(L)\bigr{)},

with $\mathsf{enc}(L)$ the encoding of Definition 4.3; the message is not an input. Two rules are part of the construction and are this volume’s own: $H_{R}$ in both computations, the Coordinator’s and every member’s, so that all parties obtain one scalar; and the confidential and authenticated channel for the seed, which the proof of Proposition 7.24, step (iv), shows necessary. Class (Definition 1.1): designed but unspecified.

The interface is that of ePrint 2024/436, Figure 5 and Remark 1, with $(\alpha,\mathit{aux})=(v,\mathsf{enc}(L))$ and every signer applying $H_{R}$ ; the encoding of the commitment list is that of RFC 9591, Section 4.3. A seed flow is published only in the revision of ZIP 312 proposed in pull request 895, and the merged ZIP 312 has none. That hashing the signer-chosen commitments hedges a faulty generator at the Coordinator is asserted informally in ePrint 2024/436, Section 7, and proved nowhere; the Coordinator sees $L$ before it chooses the seed, and it remains trusted for unlinkability (Definition 5.14).

Lemma 5.7 (Distance of the randomiser from uniform).

Under Assumption 4.2, let an algorithm, the observer, make at most $q_{h}$ queries to $H_{R}$ and, at one point, choose a byte string $w$ and receive $\hat{\alpha}:=H_{R}(u\,\|\,w)$ , for $u$ uniform on the $N_{u}$ -byte strings and independent of all else. The pair formed by the observer’s view and $\hat{\alpha}$ is within statistical distance

\delta+q_{h}\cdot 2^{-8N_{u}}

of the pair in which $\hat{\alpha}$ is replaced by a uniform element of $\mathbb{F}_{q}$ independent of all else. For Construction 5.4, $N_{u}=N_{\mathrm{s}}$ and $w=\mathrm{enc}(L,m)$ ; for Construction 5.6, $N_{u}=32$ and $w=\mathsf{enc}(L)$ ; with $N_{u}=32$ the bound is $\delta+q_{h}\cdot 2^{-256}$ .

Proof.

The proof is that of Lemma 4.5 with $H_{R}$ in place of $H_{3}$ and $N_{u}$ bytes in place of $32$ . The observer queries $H_{R}$ at $u\,\|\,w$ with probability at most $q_{h}\cdot 2^{-8N_{u}}$ , by the union bound over its queries, each having prefix $u$ with probability $2^{-8N_{u}}$ in the experiment in which the answer used for $\hat{\alpha}$ is resampled. Outside that event the two experiments coincide, and the resampled answer is within $\delta$ of uniform; the triangle inequality (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”) gives the bound. □

At $q_{h}=2^{64}$ and $N_{u}=32$ the bound is below $2^{-191.99}$ . The randomiser is thus close to uniform, not exactly uniform as ZIP 312, “Rationale”, states.

Remark 5.8 (Effective randomiser).

The randomiser of ZIP 312 is the effective randomiser $\hat{\alpha}$ of ePrint 2024/436, not its $\alpha$ . The correspondence carries correctness (Theorem 5.11), not the paper’s unforgeability game, whose signing oracle applies $H_{r}$ itself to an adversarial $(\alpha,\mathit{aux})$ (Definition 6 and Figure 4, with $\mathsf{RandShare}$ and $\mathsf{RandPK}$ of Figure 5). Only Construction 5.6 presents the paper’s interface. Wherever the Coordinator sends $\hat{\alpha}$ itself, as in the wire form of Construction 5.4 or when it forwards a randomiser chosen elsewhere, it chooses the effective randomiser outright and the signers use it unchecked; the paper’s game does not model this. This remark is the volume’s one statement of that fact; later statements cite it.

5.4 Authorisation of the signed message

Definition 5.9 (Message check).

In spend authorisation the signed message is $m=\mathsf{SigHash}(T)$ for a transaction $T$ (Ironwood Guide, Definition “Signature digest”), which alone does not show a signer what it authorises. With $m$ the Coordinator sends transaction data $D_{T}$ , further data of $T$ , over the confidential and authenticated channel of Definition 2.10, type (b). A signer performs the message check if, before returning a share, it verifies that $m$ is the signature digest determined by $D_{T}$ , or computes $m$ from $D_{T}$ itself. A signature share counts as an approval of the pair $(\mathsf{rk},m)$ , with $\mathsf{rk}$ the shifted group key of its request, only if its signer performed the message check.

ZIP 312, “Round Two - Signature Share Generation”, makes the check a MUST and names as possible data the transaction itself, openings of value commitments and decryptions of note ciphertexts; RFC 9591, Section 7.7 (“Input Message Validation”), recommends such input validation. The honest participants of the security games of §7 perform the check by definition, and their returned shares are the approvals the games count. A signer that omits it authorises whatever the transaction builder chose. Class (Definition 1.1): the obligation is specified; the mechanism by which a signer obtains and checks $D_{T}$ is outside ZIP 312 and designed but unspecified.

5.5 Re-randomised signing, aggregation and share verification

Construction 5.10 (Re-randomised signing of ZIP 312).

The key material is valid (Definition 2.5); the ciphersuite has the randomiser hash $H_{R}$ (Definition 4.1, part (f)).

(1)

Round One. Each participant runs Construction 4.4 unchanged and sends its commitments over an authenticated channel (Definition 2.10, type (a)).
(2)

Randomiser. The Coordinator chooses the signing set $I$ and, for each $i\in I$ , one unused commitment pair, forms the commitment list $L$ , and obtains $\hat{\alpha}$ by Construction 5.4 or Construction 5.6, fresh for this run. It sends to each $P_{i}$ , $i\in I$ , the tuple $(m,L,\hat{\alpha},D_{T})$ , or $(m,L,v,D_{T})$ with the seed $v$ of Construction 5.6, where $D_{T}$ is the data of Definition 5.9, over a confidential and authenticated channel (Definition 2.10, type (b)); RFC 9591 requires authentication only.
(3)

Round Two. Member $P_{i}$ performs the checks of Construction 4.8, its check (1) being the message check of Definition 5.9; in the seed variant it computes $\hat{\alpha}:=H_{R}(v\,\|\,\mathsf{enc}(L))$ . It computes $\mathit{PK}^{\prime}:=\mathit{PK}+[\hat{\alpha}]B$ from its stored group key and runs Construction 4.8 with $\mathit{sk}_{i}+\hat{\alpha}$ in place of $\mathit{sk}_{i}$ and $\mathit{PK}^{\prime}$ in place of $\mathit{PK}$ . The shifted group key $\mathit{PK}^{\prime}$ , not $\mathit{PK}$ , is the key serialised into $H_{1}$ for the binding factors and into $H_{2}$ for the challenge (Definition 4.7). Its share is

$z_{i}:=d_{i}+e_{i}\rho_{i}+\lambda_{I,i}\,(\mathit{sk}_{i}+\hat{\alpha})\,c,$

returned as in RFC 9591 over an authenticated, not confidential, channel (Definition 2.10, type (a)).
(4)

Aggregation. The Coordinator runs Construction 4.9 with $\mathit{PK}^{\prime}$ in place of $\mathit{PK}$ , and verifies the aggregate under $\mathit{PK}^{\prime}$ .
(5)

Share verification. The share equation of Construction 4.9 is checked with $\mathit{PK}_{i}+[\hat{\alpha}]B$ in place of $\mathit{PK}_{i}$ and with the shifted group key:

$[z_{i}]B\;=\;R_{i}+[c\,\lambda_{I,i}]\,\bigl{(}\mathit{PK}_{i}+[\hat{\alpha}]B% \bigr{)}.$

Every signing run uses a fresh randomiser, generated in its own Round Two: a randomiser used for two runs of one key gives both the same shifted key and links them. The output $(R,z)$ is a signature under $\mathsf{rk}:=\mathit{PK}^{\prime}$ . Class (Definition 1.1): specified (ZIP 312, Draft), the seed variant designed but unspecified.

The construction is that of ZIP 312, “Round One - Commitment”, “Round Two - Signature Share Generation” and “Signature Share Verification and Aggregation”, over RFC 9591, Sections 5.1 to 5.4: the randomised signing, aggregation and share-verification functions are the regular ones with the share, the verification share and the group key shifted by $\hat{\alpha}$ and by $[\hat{\alpha}]B$ . Round One keeps the unshifted share in the nonce hash, the randomiser not yet existing. The keys $\mathit{PK}$ and $\mathit{PK}_{i}$ are those stored from key generation, never taken from the messages of the run (Construction 4.9). What the returned shares reveal to a party that sees them is Proposition 7.25.

Theorem 5.11 (Correctness of re-randomised FROST).

Let the key material be valid, with signing key $s$ and group key $\mathit{PK}$ ; let $\hat{\alpha}\in\mathbb{F}_{q}$ , $I$ a signing set and $m$ a message that every member of $I$ accepts. Outside the exceptions below, a run of Construction 5.10 in which every party is honest outputs $(R,z)$ with

R=[r]B,\qquad r:=\sum_{i\in I}(d_{i}+e_{i}\rho_{i}),\qquad z=r+c\,(s+\hat{% \alpha}),

which the single-party verification accepts on $m$ under $\mathit{PK}+[\hat{\alpha}]B$ , and every share satisfies its shifted share equation. The exceptions are those of Theorem 4.11 for the shifted material, together with the identity case of the shifted group key: in a suite whose element serialisation is not total, the run fails when $\mathit{PK}+[\hat{\alpha}]B=\mathcal{O}$ .

Proof.

By Definition 5.3 and the paragraph following it, the shifted shares $\mathit{sk}_{j}+\hat{\alpha}$ , verification shares $\mathit{PK}_{j}+[\hat{\alpha}]B$ and group key $\mathit{PK}+[\hat{\alpha}]B$ are valid key material for $s+\hat{\alpha}$ , with sharing polynomial $f+\hat{\alpha}$ . Steps (3) to (5) of Construction 5.10 are Constructions 4.8 and 4.9 run on that key material. Round One enters those constructions only through the nonces, each an answer of $H_{3}$ whichever share enters its input. Theorem 4.11 applied to the shifted material gives $R=[r]B$ , $z=r+c(s+\hat{\alpha})$ and acceptance under $\mathit{PK}+[\hat{\alpha}]B$ , outside its cases; and Proposition 4.10, part (ii), applied to it gives the shifted share equations. Both use only validity of the key material. When $\mathit{PK}+[\hat{\alpha}]B=\mathcal{O}$ in a suite whose element serialisation is not total, $\mathsf{ser}_{\mathbb{G}}(\mathit{PK}^{\prime})$ is undefined, and so are the binding factors of Definition 4.7; the run fails. □

ZIP 312, “Rationale”, makes the same argument, and ePrint 2024/436, Equation (2), displays it; the ZIP cites, rather than proves, the coefficient sum one on which it rests, which Lemma 2.4 proves.

Example 5.12 (The two-of-three run, re-randomised).

Every number below is output by the volume’s toy script. The toy curve, the key material, the encodings, the message toy message and the signing set $I=\{1,3\}$ are those of Example 4.12. Members $1$ and $3$ draw fresh Round One nonces: reusing that example’s nonces would reuse a nonce pair (Lemma 4.13). The randomiser is that of Construction 5.6, with a fixed seed and $H_{R}$ BLAKE2b-512 under the personalisation of FROST(Pallas, BLAKE2b-512) reduced modulo $967$ : $\hat{\alpha}=565$ . The shifted group key and shares are

\mathit{PK}+[565]B=(268,139),\qquad\mathit{sk}_{1}+\hat{\alpha}=697,\qquad% \mathit{sk}_{3}+\hat{\alpha}=319,

and $\lambda_{I,1}+\lambda_{I,3}=1$ modulo $967$ . With the shifted key in $H_{1}$ and $H_{2}$ , the binding factors are $\rho_{1}=480$ and $\rho_{3}=303$ , the group commitment is $R=(302,757)$ and the challenge is $c=151$ . The shares are $z_{1}=151$ and $z_{3}=652$ , and each satisfies its shifted share equation against $\mathit{PK}_{i}+[\hat{\alpha}]B$ . The aggregate is $z=803=r+c(s+\hat{\alpha})$ , and $[z]B=R+[c](\mathit{PK}+[\hat{\alpha}]B)$ holds.

5.6 Trust model of ZIP 312

Remark 5.13 (Requirements of ZIP 312).

ZIP 312, “Requirements”, states three requirements, in lower case, although its “Terminology” invokes the key words of RFC 2119:

(a)

all signatures generated by following the ZIP must verify as Sapling or Orchard spend-authorisation signatures under the appropriate validating key, which Proposition 6.3 proves for the Pallas suite, the Sapling suite being outside the volume;
(b)

they should meet the security criteria of the protocol specification for signatures with re-randomisable keys, Definition 5.1, whose threshold form is an open problem (Table 3);
(c)

the threat model must be taken into account, which Definition 5.14 makes exact.

Definition 5.14 (Threat model of ZIP 312).

The threat model of ZIP 312 consists of two clauses.

(i)

The Coordinator is trusted with the privacy of the transaction, unlinkability included. A rogue Coordinator can break both, but “should not be able to create signed transactions without the approval of” $t$ participants, “as specified in FROST”; the ZIP’s $\mathrm{MIN\_PARTICIPANTS}$ is $t$ . An approval is a share returned after the message check (Definition 5.9).
(ii)

Every key-share holder is likewise trusted with the privacy of the transaction and with unlinkability.

The clauses are those of ZIP 312, “Threat Model”. The should of clause (i) is lower case, within a threat model that the Requirements say must be taken into account; it is not a must not. ePrint 2024/436, Section 5.1, states the same split: the party choosing the randomiser is trusted with privacy, not with security. The privacy trust is forced by the flow: the Coordinator generates $\hat{\alpha}$ , every signer receives it, or the seed with $L$ , and whoever holds it computes $\mathit{PK}=\mathsf{rk}-[\hat{\alpha}]B$ and links the run to the key (the proof of Proposition 7.24, step (iv)). The unforgeability clause has no proof, as §7.5 records (Remark 7.22). In RFC 9591, Section 7, the Coordinator holds no private information; trust in it for privacy is what re-randomisation adds.

ZIP 312, “Non-requirements”, excludes four things: removal of the Coordinator role (RFC 9591, Section 7.5, “Removing the Coordinator Role”); prevention of key-share holders from linking a signing run to its transaction on the chain; a key-generation procedure, for which it refers to RFC 9591; and network privacy.

Remark 5.15 (Unlinkability as ZIP 312 states it).

ZIP 312, “Terminology”, defines unlinkability as statistical independence of signatures from the signers’ long-term keys, ensuring, “for perfectly uniform generation of Randomizers and no leakage of metadata”, that it is “impossible to determine whether two transactions were generated by the same party”. The statement is informal: it names no observer and no view. Definition 7.23 makes it exact against a specified observer, and Lemma 5.7 replaces perfect uniformity.