This section states FROST signing as RFC 9591 specifies it, in execution order: the ciphersuite interface with its hash roles and the encoding of a commitment list; Round One, which draws hedged nonces and commits to them; Round Two, which binds each signature share to the message and to the whole commitment list; aggregation with share verification; the correctness of an honest run; and the single use of nonces, with the exact condition under which reuse of a nonce pair exposes a share. Threshold parameters, signing sets, Lagrange coefficients and key material are those of §2; the key material is the output of either key generation of §3.
A ciphersuite fixes the following data.
A group G of prime order q , written additively, with
identity O and generator B , and its scalar field
F q . Write
An element serialisation ser G , mapping
either every element of G or every element of G ∗ injectively
to a byte string of fixed length N e , and an element
deserialisation deser G , which maps a byte string to an
element of G ∗ or fails. It fails on every string that is not the
canonical encoding ser G (P) of some
A scalar serialisation ser F q , mapping F q injectively to byte strings of fixed length N s , and a scalar deserialisation deser F q , which fails on every string whose integer value is not below q and inverts ser F q otherwise.
Hash functions by role:
| H 1, H 2, H 3 : { 0, 1 } 8 ∗ → F q, H 4, H 5 : { 0, 1 } 8 ∗ → { 0, 1 } 8 N h, |
where { 0, 1 } 8 ∗ denotes the byte strings and N h is the digest length of the suite. The roles are: H 1 the binding factor, H 2 the challenge, H 3 the nonce, H 4 the message pre-hash and H 5 the commitment-list pre-hash.
The signature encoding
ser G (R) ∥ ser F q (z) of a pair
| [z] B = R + [c] PK, c := H 2 (ser G (R) ‖ ser G (PK) ‖ m) . |
This is the verification of the Crypto Guide’s Construction “Schnorr signature” (§“From identification to signature via the Fiat–Shamir transform”) in additive form, with hash H 2 .
A ciphersuite for re-randomised signing adds
the randomiser hash
The ciphersuites of RFC 9591 do not define H R .
The data are those of RFC 9591, Sections 3.1 (“Prime-Order Group”) and 3.2 (“Cryptographic Hash Function”), and Section 6 (“Ciphersuites”), whose Appendix A (“Schnorr Signature Encoding”) fixes the encoding and whose Appendix B (“Schnorr Signature Generation and Verification for Prime-Order Groups”) the verification equation. The requirements that RFC 9591, Section 6.6 (“Ciphersuite Requirements”), places on every ciphersuite are four: the group is of prime order and every deserialisation outputs an element of its set or fails; every hash function is domain-separated with a per-suite context string, FROST(Ed25519, SHA-512) excepted for H 2 for compatibility with RFC 8032; H 1 , H 2 and H 3 have output distributions close to uniform; and the signature encoding is specified. The suite FROST(Pallas, BLAKE2b-512) separates its hashes by BLAKE2b personalisations instead, its H 2 being that of RedPallas (Construction 6.1).
The generic element serialisation of RFC 9591, Section 3.1, fails on O . The suite FROST(Pallas, BLAKE2b-512), as ZIP 312 states it, instead serialises every element, by the star encoding (Ironwood Guide, Definition “Star encoding”; ZIP 312, “FROST(Pallas, BLAKE2b-512)”); the conflict between the two texts is stated after Construction 6.1. In both cases the element deserialisation rejects O . Whether ser G is total is the one property of a suite on which Theorem 4.11 distinguishes cases.
The hashes H 1 , H 2 , H 3 and H R are modelled as random oracles into F q (Crypto Guide, §“The random oracle model”, Definition “Random oracle”), independent of each other and of the proof-of-knowledge hash H dkg (Assumption 3.5): each answer at a new input is an independent sample from a distribution on F q within statistical distance δ of uniform (Math Guide, §“Statistical distance”), where δ is a parameter of the suite. The hashes H 4 and H 5 are modelled as independent random oracles into { 0, 1 } 8 N h ; hence an algorithm making Q queries finds a collision of either with probability at most
| Q (Q − 1) 2 ⋅ 2 − 8 N h |
(Math Guide, §“The union bound and a birthday calculation”, Proposition “Birthday bound”). For a suite that builds every role from one hash function under distinct personalisations, the assumption is that this function, keyed by its personalisation, is a random oracle; distinct personalisations then give independent oracles (Crypto Guide, §“Domain separation and personalisation”, Proposition “Domain separation yields independent oracles”), and δ is the bias of the reduction of its output into F q (Crypto Guide, §“Hashing to a field element”).
The assumption is the one hash assumption of every ciphersuite in this
volume. RFC 9591, Section 3.2, models the ciphersuite hash as a random
oracle in the security analyses it cites. The suite
FROST(Pallas, BLAKE2b-512) meets the assumption with
Let a ciphersuite be fixed and let I be a signing set (Definition 2.1). A commitment list over I is a sequence
| L = ((i, D i, E i)) i ∈ I, D i, E i ∈ G, |
with one triple for each member of I : D i is the hiding commitment and E i the binding commitment of member i . The identifiers are distinct and the triples are sorted in ascending order of the least non-negative representative of the identifier. The signing set is read off L as the set of its identifiers. The encoding of L is the byte string
| enc (L) := ∥ i ∈ I, ascending (ser F q (i) ‖ ser G (D i) ‖ ser G (E i)) |
of length
A commitment equal to O occurs only in a suite with total element serialisation, and check (3) of Construction 4.8 rejects it.
The ordering is a requirement of RFC 9591, which states that the list must be sorted in ascending order by identifier, and compares scalars by their least non-negative representative (Sections 3.1 and 4.3, “List Operations”); the encoding is that of Section 4.3. Every component has fixed length, each serialisation is injective, and the order of the triples is fixed; hence the length of enc (L) determines | I | , and the string parses uniquely into the triples. The map enc is therefore injective on commitment lists over one suite, which the binding factors of Definition 4.7 require.
Participant P i , holding the share sk i (Definition 2.5), proceeds as follows.
It draws two independent strings
| d i := H 3 (T d ∥ ser F q (sk i)), e i := H 3 (T e ∥ ser F q (sk i)) . |
It sets
It stores (d i, e i, D i, E i) , keeps (d i, e i) secret, and
sends
The strings T d and T e must be sampled uniformly from a secure source of randomness, and a nonce pair must not be used in more than one signing run.
The construction is RFC 9591, Section 5.1 (“Round One - Commitment”),
with the hedged nonce generation of Section 4.1 (“Nonce Generation”),
which always samples 32 bytes of fresh randomness and hashes them
together with the serialised share. Section 5.1 requires that the nonces
not be used in more than one signing and be generated from a source of
secure randomness; Section 7.3 (“Nonce Reuse Attacks”) requires the
randomness to be sampled uniformly. Nonces lie in F q , not in
F q ∗ : the zero nonce is not excluded, and its consequence is case
(1) of Theorem 4.11. Round One does not depend on the
message or on the signing set, so a participant may run it ahead of any
signing run and hold several unused pairs. The paper that introduced FROST
(ePrint 2020/852, Figure 2) samples the pair uniformly from
Under Assumption 4.2, let an algorithm, the observer, make
at most q h queries to H 3 and, at one point, choose a byte string
w and receive
| δ + q h ⋅ 2 − 256 |
of the pair obtained when d is replaced by a uniform element of F q independent of all else. For the two nonces of one execution of Round One, received for one string w with independent strings T d and T e , the corresponding distance is at most
| 2 (δ + q h ⋅ 2 − 256) + 2 − 256 . |
The argument is that of the Ironwood Guide’s Lemma “Distance of
GenRandom from uniform” (§“Randomised validating keys”), with 32
fresh bytes in place of 80 and H 3 in place of the RedPallas hash.
Let E be the event that the observer queries H 3 at
T ∥ w . In a second experiment the answer
H 3 (T ∥ w) is replaced, in the computation of d only, by an
independent sample of the answer distribution. In the lazy realisation of
the random oracle the answers at other inputs are independent of the answer
at T ∥ w , so the two experiments are identical until E occurs,
and their outputs are within statistical distance Pr [E]
(Crypto Guide, §“Security as a game”, Remark “Game-hopping”).
In the second experiment the observer’s view is independent of T , so
each query has prefix T with probability at most 2 − 256 , and
For the pair, the event
The nonces are therefore close to uniform, not uniform, whatever the share;
RFC 9591, Section 7.3, states that they are indistinguishable from values
sampled uniformly at random, and the lemma quantifies that statement. For
FROST(Pallas, BLAKE2b-512), with the δ of
Proposition 6.2, the first bound at
RFC 9591, Section 4.1, hashes the share with the fresh bytes to hedge against a generator whose output is predictable to an observer; Lemma 4.5 assumes T uniform, and the volume proves no statement for a predictable T . Nonces computed from the share and the message alone permit complete key recovery (RFC 9591, Sections 1 and 7.3), which is why fresh bytes are used.
Over
Under Assumption 4.2, two of N executions of Round One by one participant yield equal nonce pairs with probability at most
| (N 2) (2 − 255 + 1 / q + δ) 2 . |
For two executions
Let PK be the group key, m a message, that is a byte
string, and L a commitment list over a signing set I
(Definition 4.3). For
| ρ i := H 1 (ser G (PK) ‖ H 4 (m) ‖ H 5 (enc (L)) ∥ ser F q (i)) ; |
the commitment share of i is
| c := H 2 (ser G (R) ‖ ser G (PK) ‖ m), |
with ρ i defined whenever ser G (PK) is, and c whenever ser G (R) and ser G (PK) are. All four are functions of the public data (PK, m, L) , computed identically by every member of I and by the Coordinator.
The binding factor is that of RFC 9591, Section 4.4 (“Binding Factors
Computation”), the group commitment that of Section 4.5 (“Group
Commitment Computation”), and the challenge that of Section 4.6
(“Signature Challenge Computation”). The challenge input has the order
nonce commitment, public key, message of the single-party challenge of
Definition 4.1, part (e), so a verifier recomputes c from
(R, PK, m) alone. The paper’s binding value
Coordinator. It selects a signing set I with
Member P i , on receiving (m, L) :
it checks that m is a message it is willing to sign; for spend authorisation this is the check of Definition 5.9;
it checks that its identifier i appears in L with a commitment pair (D i, E i) that it stores and has not used;
it deserialises every commitment of L with deser G , which fails on a non-canonical encoding and on the encoding of O ;
it checks that the identifiers of L are distinct, without which λ I, i is undefined, and in ascending order, as RFC 9591 requires of a commitment list (Section 4.3).
It aborts if any check fails. Otherwise it computes ρ i , R and c (Definition 4.7), aborting if ρ i or c is undefined, and λ I, i (Definition 2.3), with I the set of identifiers of L ; sets the signature share
| z i := d i + e i ρ i + λ I, i sk i c ∈ F q ; |
deletes (d i, e i) and (D i, E i) ; and only then sends ser F q (z i) to the Coordinator over an authenticated channel (Definition 2.10, type (a)).
The construction is RFC 9591, Section 5.2 (“Round Two - Signature Share Generation”). The Coordinator’s choice of at least t and at most n participants is required by Section 5. Each participant must validate the commitment list by deserialising each element, must abort if deserialisation fails, and must ensure that its identifier and commitments from Round One appear in the list (Section 5.2); applications that restrict the messages a participant signs perform further validation, which Section 7.7 (“Input Message Validation”) recommends so that participants do not act as signing oracles for arbitrary messages. The computation of λ I, i fails on an absent or repeated identifier (Section 4.2, “Polynomials”). The share equation is that of Section 5.2. After computing its share, each participant must delete the nonce and the corresponding commitment, and must not use the nonce as input more than once. The deletion is the step on which Proposition 4.14 rests.
The Coordinator holds (m, L) and the group information (PK, (PK j) j = 1 n) stored from key generation (Definition 2.5). The shares arrive over authenticated channels without confidentiality (Definition 2.10, type (a)). The Coordinator proceeds as follows.
It deserialises each share with deser F q and aborts if any deserialisation fails.
It computes ρ i and R i for
It sets
It should verify (R, z) on m under PK by the single-party verification (Definition 4.1, part (e)) before publishing it, and should abort if the signature is invalid. It may check each share by the share equation
| [z i] B = R i + [c λ I, i] PK i, |
in particular when the aggregate is invalid. The keys PK and PK i in these checks are taken from the stored group information, never from the messages of the run.
The construction is RFC 9591, Section 5.3 (“Signature Share Aggregation”). The Coordinator must validate each share by deserialisation and must abort if validation fails; it should verify the signature under the group key before publishing or releasing it; if that verification fails, it may verify each share individually to identify and act on misbehaving participants; and the group key and the keys PK i used there must come from the stored group information. Section 5 requires an authenticated channel for identifying misbehaving participants and does not require confidentiality. The paper checks every share unconditionally before aggregating (ePrint 2020/852, Figure 3); the specified duties are the recommendation and the permission above, and this volume states those.
Let the key material be valid (Definition 2.5), let the Coordinator be honest, and let c be defined.
If the share of every member satisfies its share equation, then
The share of every member that follows Construction 4.8 satisfies its share equation.
Hence, if the aggregate is not accepted, the share equation of some member fails, and that member deviated from the protocol; the authenticated channel identifies it as the sender of the share.
(ii) For a member following the construction,
| [z i] B = [d i] B + [ρ i] [e i] B + [c λ I, i] [sk i] B = R i + [c λ I, i] PK i, |
since
(i) Let f be the polynomial of degree at most
| [z] B = ∑ i ∈ I R i + [c ∑ i ∈ I λ I, i sk i] B = R + [c f (0)] B = R + [c] PK, |
by Lemma 2.4 applied to f . The challenge c is the one the single-party verification recomputes from (R, PK, m) (Definition 4.7), so the verification accepts.
(iii) is the contrapositive of (i), with (ii). □
The mechanism for acting on an identified member is outside RFC 9591 (Section 5.4, “Identifiable Abort”). FROST provides no robustness (Sections 5.4 and 7): one member that withholds or corrupts its share prevents the signature, and a failed run is restarted from Round One with fresh nonces, since the consumed pairs are deleted.
Let the key material be valid (Definition 2.5), as key generation by a dealer or by the distributed protocol outputs it (Propositions 3.3 and 3.8); let I be a signing set and m a message that every member of I accepts; and let every party follow Constructions 4.4, 4.8 and 4.9. Then, outside the three cases below, the run outputs (R, z) with
| R = [r] B, z = r + c s, r := ∑ i ∈ I (d i + e i ρ i), |
which the single-party verification accepts on m under PK . In the three cases the run aborts.
Zero nonce. Some d i or e i ,
Identity group commitment. Only in a suite whose element
serialisation is not total, as the generic serialisation of RFC 9591 is
not:
Identity group key. Only in a suite whose element
serialisation is not total:
A suite with a total element serialisation, such as FROST(Pallas, BLAKE2b-512), has only case (1).
Write
| z = ∑ i ∈ I z i = r + c s, [z] B = [r] B + [c] [s] B = R + [c] PK, |
where
(1) Each of the 2 | I | nonces is an answer of H 3 ,
equal to 0 with probability at most
(2) Outside case (1), fix
(3) Since B generates a group of prime order,
For FROST(Pallas, BLAKE2b-512), with the δ of
Proposition 6.2, the bound of case (1) is below
2 − 251.9 for
The output of a threshold run is a single-party Schnorr signature under the group key. It carries no threshold marker: a verifier applies to it, with (PK, m) alone and no knowledge of t , n or I , the verification it applies to a signature of one signer. RFC 9591 states this in Section 5, under which signatures can be verified as if produced by a single signer holding s , and in Section 6, under which the verification instructions of each suite are equivalent to those for a single participant; Appendix B gives that verification.
Every number below is output by the volume’s toy script; none is computed
by hand. The group is the curve
Key material. A dealer with
| sk 1 = 132, sk 2 = 910, sk 3 = 721 . |
The coefficient commitments are
| PK 1 = (963, 797), PK 2 = (587, 458), PK 3 = (30, 509), |
each equal to [sk j] B .
Round One. Members 1 and 3 draw
| d 1 | = 155, | e 1 | = 457, | D 1 | = (942, 518), | E 1 | = (309, 697), | ||
| d 3 | = 464, | e 3 | = 724, | D 3 | = (958, 797), | E 3 | = (582, 220) . |
Round Two. The signing set is
| λ I, 1 = 3 ⋅ (3 − 1) − 1 = 3 / 2 = 485, λ I, 3 = 1 ⋅ (1 − 3) − 1 = − 1 / 2 = 483 |
modulo 967 . Then
Aggregation. The aggregate is
Let member P i answer k Round Two requests,
| z j = d + e ρ j + μ j sk i, μ j := λ I j, i c j, |
where ρ j , c j and I j are the binding factor of i , the
challenge and the signing set of request j , all computable from public
data. Each response is affine in the unknown
sk i is determined by (z j, v j) j ≤ k ;
(0, 0, 1) lies in the span of
the points (ρ j, μ j) do not all lie on one line
In particular, three responses with linearly independent coefficient
vectors determine sk i ; two responses with distinct binding
factors never do, and every value of sk i is then consistent
with them; and two responses with equal binding factors and
| sk i = (z 1 − z 2) / (μ 1 − μ 2) . |
(b) implies (a): if
(a) implies (c): suppose every point lies on
(c) implies (b): if two points have equal ρ and distinct μ ,
then
The particular cases follow: independent vectors span F q 3 ; two points
with distinct ρ lie on a line
The last case is the Crypto Guide’s Proposition “Nonce reuse reveals
the secret key” (§“Security in the random oracle model and the forking
lemma”) applied to the effective nonce
In the toy group of Example 4.12, member 1 answers three
requests on the message toy message over
A Coordinator that places in a Round Two request a commitment pair of member P i that P i has already used to answer a request obtains no response from P i , unless P i still stores a second copy of that pair from another execution of Round One, an event whose probability over N executions is at most (N 2) (2 − 255 + 1 / q + δ) 2 (Lemma 4.6). Outside that event a replay denies service only, and yields no second response under one nonce pair, the hypothesis of Lemma 4.13.
A member responds only for a pair that it stores and has not used, by check (2) of Construction 4.8, and it deletes a pair when it answers with it. Outside that event no second copy of the pair is stored, so a used pair is no longer stored, check (2) fails and the member aborts. □
The Coordinator may in addition track, per group key, the commitments already used (RFC 9591, Section 7.3).