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 of Definition 4.1, part (f); the Pallas instance is Construction 6.1. ZIP 312 is Draft.
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
A key pair is
Re-randomisation by a randomiser
For each Action the spender draws
with sign-normalised; the Action publishes and the
signature under on (Ironwood Guide,
§“Randomised validating keys”, Construction “Randomised validating
key”). Two consensus rules apply:
For every Action of the Orchard protocol, in either pool, the single signer proceeds in the order: draw ; compute ; compute of the transaction, which commits to ; sign it under . The Action proof takes as auxiliary (secret) input and 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.
A re-randomisable signature scheme is a signature scheme with private-key set and public-key set , together with a randomiser set , a randomised generator with values in , maps
and an identity randomiser
each
for every , the value
with
for every and ,
Let
Freshness is on the message–signature pair; the forgery may be under any re-randomisation of , 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).
Let key material with signing key and group key
Fix
(ii) Write
hence
The argument is that of the Ironwood Guide’s Remark “Key
prefixing” for the unshifted response. The bound is for fixed in
advance; with chosen adaptively, one query may pair with many.
For FROST(Pallas, BLAKE2b-512) the per-query term
Spend authorisation re-randomises the validating key of every Action with a
randomiser from , 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
A re-randomisable threshold signature scheme is a scheme of Definition 2.8 over a group of prime order with generator , together with a randomiser set and:
a randomised algorithm with values in ;
an effective-randomiser map
the shifts
such that the following correctness holds. For valid key material
with signing key , every with
The definition is that of ePrint 2024/436, Definition 5, which names the algorithms, with general , and and a distribution on , 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 (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 a hash into scalars, whose role the
randomiser hash 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 , the
polynomial
After Round One, let be the message and the commitment list of Definition 4.3, sorted in ascending order of the nonzero identifiers. The Coordinator draws uniformly from the -byte strings, the length of a serialised scalar ( for FROST(Pallas, BLAKE2b-512)), and sets
where is any encoding from which and, for each member of , its identifier, hiding commitment and binding commitment are recovered uniquely. It sends 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
Let be the group key of an Orchard-protocol threshold key,
with
for an algorithm of about twice the running time of , where is its probability of breaking the Ironwood Guide’s Assumption “Collision resistance of BLAKE2b”.
Only is modelled as a random oracle; the digest tree of
is computed with BLAKE2b under other personalisations,
and only its collision resistance is used. Let be the winning
probability. Define an algorithm 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
, of size , and challenges. On input and
challenges
On success the two runs coincide until the -th query is asked, so both
query the same string at index , and both win with that ,
with outputs and and challenges
If the tuples of randomised validating keys of and 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 .
Otherwise contains the point
With the lower bound,
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),
After Round One, let be the commitment list over the signing set . The Coordinator draws a seed uniformly from the -byte strings and sends it to every member of over a confidential and authenticated channel (Definition 2.10, type (b)). The Coordinator and every member of compute
with 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: 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
Under Assumption 4.2, let an algorithm, the observer, make
at most queries to and, at one point, choose a byte string
and receive
of the pair in which is replaced by a uniform element of
independent of all else. For Construction 5.4,
The proof is that of Lemma 4.5 with in place of
and bytes in place of . The observer queries
at with probability at most
At
The randomiser of ZIP 312 is the effective randomiser of ePrint 2024/436, not its . The correspondence carries correctness (Theorem 5.11), not the paper’s unforgeability game, whose signing oracle applies itself to an adversarial (Definition 6 and Figure 4, with and of Figure 5). Only Construction 5.6 presents the paper’s interface. Wherever the Coordinator sends 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.
In spend authorisation the signed message is
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 is outside ZIP 312 and designed but unspecified.
The key material is valid (Definition 2.5); the ciphersuite has the randomiser hash (Definition 4.1, part (f)).
Randomiser. The Coordinator chooses the signing set and,
for each
Round Two. Member performs the checks of
Construction 4.8, its check (1) being the message check of
Definition 5.9; in the seed variant it computes
returned as in RFC 9591 over an authenticated, not confidential, channel (Definition 2.10, type (a)).
Aggregation. The Coordinator runs Construction 4.9 with in place of , and verifies the aggregate under .
Share verification. The share equation of
Construction 4.9 is checked with
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 is a signature under
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 and by . Round One keeps the unshifted share in the nonce hash, the randomiser not yet existing. The keys and 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.
Let the key material be valid, with signing key and group key
; let
which the single-party verification accepts on under
By Definition 5.3 and the paragraph following it, the
shifted shares
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.
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
and
ZIP 312, “Requirements”, states three requirements, in lower case, although its “Terminology” invokes the key words of RFC 2119:
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;
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);
the threat model must be taken into account, which Definition 5.14 makes exact.
The threat model of ZIP 312 consists of two clauses.
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” participants, “as specified in FROST”; the ZIP’s is . An approval is a share returned after the message check (Definition 5.9).
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 , every signer receives it, or the seed
with , and whoever holds it computes
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.
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.