modular_frost/
sign.rs

1use core::{ops::Deref, fmt::Debug};
2use std::{
3  io::{self, Read, Write},
4  collections::HashMap,
5};
6
7use rand_core::{RngCore, CryptoRng, SeedableRng};
8use rand_chacha::ChaCha20Rng;
9
10use zeroize::{Zeroize, Zeroizing};
11
12use transcript::Transcript;
13
14use ciphersuite::group::{
15  ff::{Field, PrimeField},
16  GroupEncoding,
17};
18use multiexp::BatchVerifier;
19
20use crate::{
21  curve::Curve,
22  Participant, FrostError, ThresholdParams, ThresholdKeys, ThresholdView,
23  algorithm::{WriteAddendum, Addendum, Algorithm},
24  validate_map,
25};
26
27pub(crate) use crate::nonce::*;
28
29/// Trait enabling writing preprocesses and signature shares.
30pub trait Writable {
31  fn write<W: Write>(&self, writer: &mut W) -> io::Result<()>;
32
33  fn serialize(&self) -> Vec<u8> {
34    let mut buf = vec![];
35    self.write(&mut buf).unwrap();
36    buf
37  }
38}
39
40impl<T: Writable> Writable for Vec<T> {
41  fn write<W: Write>(&self, writer: &mut W) -> io::Result<()> {
42    for w in self {
43      w.write(writer)?;
44    }
45    Ok(())
46  }
47}
48
49// Pairing of an Algorithm with a ThresholdKeys instance.
50#[derive(Zeroize)]
51struct Params<C: Curve, A: Algorithm<C>> {
52  // Skips the algorithm due to being too large a bound to feasibly enforce on users
53  #[zeroize(skip)]
54  algorithm: A,
55  keys: ThresholdKeys<C>,
56}
57
58impl<C: Curve, A: Algorithm<C>> Params<C, A> {
59  fn new(algorithm: A, keys: ThresholdKeys<C>) -> Params<C, A> {
60    Params { algorithm, keys }
61  }
62
63  fn multisig_params(&self) -> ThresholdParams {
64    self.keys.params()
65  }
66}
67
68/// Preprocess for an instance of the FROST signing protocol.
69#[derive(Clone, PartialEq, Eq)]
70pub struct Preprocess<C: Curve, A: Addendum> {
71  pub(crate) commitments: Commitments<C>,
72  /// The addendum used by the algorithm.
73  pub addendum: A,
74}
75
76impl<C: Curve, A: Addendum> Writable for Preprocess<C, A> {
77  fn write<W: Write>(&self, writer: &mut W) -> io::Result<()> {
78    self.commitments.write(writer)?;
79    self.addendum.write(writer)
80  }
81}
82
83/// A cached preprocess.
84///
85/// A preprocess MUST only be used once. Reuse will enable third-party recovery of your private
86/// key share. Additionally, this MUST be handled with the same security as your private key share,
87/// as knowledge of it also enables recovery.
88// Directly exposes the [u8; 32] member to void needing to route through std::io interfaces.
89// Still uses Zeroizing internally so when users grab it, they have a higher likelihood of
90// appreciating how to handle it and don't immediately start copying it just by grabbing it.
91#[derive(Zeroize)]
92pub struct CachedPreprocess(pub Zeroizing<[u8; 32]>);
93
94/// Trait for the initial state machine of a two-round signing protocol.
95pub trait PreprocessMachine: Send {
96  /// Preprocess message for this machine.
97  type Preprocess: Clone + PartialEq + Writable;
98  /// Signature produced by this machine.
99  type Signature: Clone + PartialEq + Debug;
100  /// SignMachine this PreprocessMachine turns into.
101  type SignMachine: SignMachine<Self::Signature, Preprocess = Self::Preprocess>;
102
103  /// Perform the preprocessing round required in order to sign.
104  /// Returns a preprocess message to be broadcast to all participants, over an authenticated
105  /// channel.
106  fn preprocess<R: RngCore + CryptoRng>(self, rng: &mut R)
107    -> (Self::SignMachine, Self::Preprocess);
108}
109
110/// State machine which manages signing for an arbitrary signature algorithm.
111pub struct AlgorithmMachine<C: Curve, A: Algorithm<C>> {
112  params: Params<C, A>,
113}
114
115impl<C: Curve, A: Algorithm<C>> AlgorithmMachine<C, A> {
116  /// Creates a new machine to generate a signature with the specified keys.
117  pub fn new(algorithm: A, keys: ThresholdKeys<C>) -> AlgorithmMachine<C, A> {
118    AlgorithmMachine { params: Params::new(algorithm, keys) }
119  }
120
121  fn seeded_preprocess(
122    self,
123    seed: CachedPreprocess,
124  ) -> (AlgorithmSignMachine<C, A>, Preprocess<C, A::Addendum>) {
125    let mut params = self.params;
126
127    let mut rng = ChaCha20Rng::from_seed(*seed.0);
128    let (nonces, commitments) = Commitments::new::<_>(
129      &mut rng,
130      params.keys.original_secret_share(),
131      &params.algorithm.nonces(),
132    );
133    let addendum = params.algorithm.preprocess_addendum(&mut rng, &params.keys);
134
135    let preprocess = Preprocess { commitments, addendum };
136
137    // Also obtain entropy to randomly sort the included participants if we need to identify blame
138    let mut blame_entropy = [0; 32];
139    rng.fill_bytes(&mut blame_entropy);
140    (
141      AlgorithmSignMachine { params, seed, nonces, preprocess: preprocess.clone(), blame_entropy },
142      preprocess,
143    )
144  }
145
146  #[cfg(any(test, feature = "tests"))]
147  pub(crate) fn unsafe_override_preprocess(
148    self,
149    nonces: Vec<Nonce<C>>,
150    preprocess: Preprocess<C, A::Addendum>,
151  ) -> AlgorithmSignMachine<C, A> {
152    AlgorithmSignMachine {
153      params: self.params,
154      seed: CachedPreprocess(Zeroizing::new([0; 32])),
155
156      nonces,
157      preprocess,
158      // Uses 0s since this is just used to protect against a malicious participant from
159      // deliberately increasing the amount of time needed to identify them (and is accordingly
160      // not necessary to function)
161      blame_entropy: [0; 32],
162    }
163  }
164}
165
166impl<C: Curve, A: Algorithm<C>> PreprocessMachine for AlgorithmMachine<C, A> {
167  type Preprocess = Preprocess<C, A::Addendum>;
168  type Signature = A::Signature;
169  type SignMachine = AlgorithmSignMachine<C, A>;
170
171  fn preprocess<R: RngCore + CryptoRng>(
172    self,
173    rng: &mut R,
174  ) -> (Self::SignMachine, Preprocess<C, A::Addendum>) {
175    let mut seed = CachedPreprocess(Zeroizing::new([0; 32]));
176    rng.fill_bytes(seed.0.as_mut());
177    self.seeded_preprocess(seed)
178  }
179}
180
181/// Share of a signature produced via FROST.
182#[derive(Clone, PartialEq, Eq)]
183pub struct SignatureShare<C: Curve>(C::F);
184impl<C: Curve> Writable for SignatureShare<C> {
185  fn write<W: Write>(&self, writer: &mut W) -> io::Result<()> {
186    writer.write_all(self.0.to_repr().as_ref())
187  }
188}
189#[cfg(any(test, feature = "tests"))]
190impl<C: Curve> SignatureShare<C> {
191  pub(crate) fn invalidate(&mut self) {
192    self.0 += C::F::ONE;
193  }
194}
195
196/// Trait for the second machine of a two-round signing protocol.
197pub trait SignMachine<S>: Send + Sync + Sized {
198  /// Params used to instantiate this machine which can be used to rebuild from a cache.
199  type Params;
200  /// Keys used for signing operations.
201  type Keys;
202  /// Preprocess message for this machine.
203  type Preprocess: Clone + PartialEq + Writable;
204  /// SignatureShare message for this machine.
205  type SignatureShare: Clone + PartialEq + Writable;
206  /// SignatureMachine this SignMachine turns into.
207  type SignatureMachine: SignatureMachine<S, SignatureShare = Self::SignatureShare>;
208
209  /// Cache this preprocess for usage later.
210  ///
211  /// This cached preprocess MUST only be used once. Reuse of it enables recovery of your private
212  /// key share. Third-party recovery of a cached preprocess also enables recovery of your private
213  /// key share, so this MUST be treated with the same security as your private key share.
214  fn cache(self) -> CachedPreprocess;
215
216  /// Create a sign machine from a cached preprocess.
217  ///
218  /// After this, the preprocess must be deleted so it's never reused. Any reuse will presumably
219  /// cause the signer to leak their secret share.
220  fn from_cache(
221    params: Self::Params,
222    keys: Self::Keys,
223    cache: CachedPreprocess,
224  ) -> (Self, Self::Preprocess);
225
226  /// Read a Preprocess message.
227  ///
228  /// Despite taking self, this does not save the preprocess. It must be externally cached and
229  /// passed into sign.
230  fn read_preprocess<R: Read>(&self, reader: &mut R) -> io::Result<Self::Preprocess>;
231
232  /// Sign a message.
233  ///
234  /// Takes in the participants' preprocess messages. Returns the signature share to be broadcast
235  /// to all participants, over an authenticated channel. The parties who participate here will
236  /// become the signing set for this session.
237  fn sign(
238    self,
239    commitments: HashMap<Participant, Self::Preprocess>,
240    msg: &[u8],
241  ) -> Result<(Self::SignatureMachine, Self::SignatureShare), FrostError>;
242}
243
244/// Next step of the state machine for the signing process.
245#[derive(Zeroize)]
246pub struct AlgorithmSignMachine<C: Curve, A: Algorithm<C>> {
247  params: Params<C, A>,
248  seed: CachedPreprocess,
249
250  pub(crate) nonces: Vec<Nonce<C>>,
251  // Skips the preprocess due to being too large a bound to feasibly enforce on users
252  #[zeroize(skip)]
253  pub(crate) preprocess: Preprocess<C, A::Addendum>,
254  pub(crate) blame_entropy: [u8; 32],
255}
256
257impl<C: Curve, A: Algorithm<C>> SignMachine<A::Signature> for AlgorithmSignMachine<C, A> {
258  type Params = A;
259  type Keys = ThresholdKeys<C>;
260  type Preprocess = Preprocess<C, A::Addendum>;
261  type SignatureShare = SignatureShare<C>;
262  type SignatureMachine = AlgorithmSignatureMachine<C, A>;
263
264  fn cache(self) -> CachedPreprocess {
265    self.seed
266  }
267
268  fn from_cache(
269    algorithm: A,
270    keys: ThresholdKeys<C>,
271    cache: CachedPreprocess,
272  ) -> (Self, Self::Preprocess) {
273    AlgorithmMachine::new(algorithm, keys).seeded_preprocess(cache)
274  }
275
276  fn read_preprocess<R: Read>(&self, reader: &mut R) -> io::Result<Self::Preprocess> {
277    Ok(Preprocess {
278      commitments: Commitments::read::<_>(reader, &self.params.algorithm.nonces())?,
279      addendum: self.params.algorithm.read_addendum(reader)?,
280    })
281  }
282
283  fn sign(
284    mut self,
285    mut preprocesses: HashMap<Participant, Preprocess<C, A::Addendum>>,
286    msg: &[u8],
287  ) -> Result<(Self::SignatureMachine, SignatureShare<C>), FrostError> {
288    let multisig_params = self.params.multisig_params();
289
290    let mut included = Vec::with_capacity(preprocesses.len() + 1);
291    included.push(multisig_params.i());
292    for l in preprocesses.keys() {
293      included.push(*l);
294    }
295    included.sort_unstable();
296
297    // Included < threshold
298    if included.len() < usize::from(multisig_params.t()) {
299      Err(FrostError::InvalidSigningSet("not enough signers"))?;
300    }
301    // OOB index
302    if u16::from(included[included.len() - 1]) > multisig_params.n() {
303      Err(FrostError::InvalidParticipant(multisig_params.n(), included[included.len() - 1]))?;
304    }
305    // Same signer included multiple times
306    for i in 0 .. (included.len() - 1) {
307      if included[i] == included[i + 1] {
308        Err(FrostError::DuplicatedParticipant(included[i]))?;
309      }
310    }
311
312    let view = self.params.keys.view(included.clone()).unwrap();
313    validate_map(&preprocesses, &included, multisig_params.i())?;
314
315    {
316      // Domain separate FROST
317      self.params.algorithm.transcript().domain_separate(b"FROST");
318    }
319
320    let nonces = self.params.algorithm.nonces();
321    #[allow(non_snake_case)]
322    let mut B = BindingFactor(HashMap::<Participant, _>::with_capacity(included.len()));
323    {
324      // Parse the preprocesses
325      for l in &included {
326        {
327          self
328            .params
329            .algorithm
330            .transcript()
331            .append_message(b"participant", C::F::from(u64::from(u16::from(*l))).to_repr());
332        }
333
334        if *l == self.params.keys.params().i() {
335          let commitments = self.preprocess.commitments.clone();
336          commitments.transcript(self.params.algorithm.transcript());
337
338          let addendum = self.preprocess.addendum.clone();
339          {
340            let mut buf = vec![];
341            addendum.write(&mut buf).unwrap();
342            self.params.algorithm.transcript().append_message(b"addendum", buf);
343          }
344
345          B.insert(*l, commitments);
346          self.params.algorithm.process_addendum(&view, *l, addendum)?;
347        } else {
348          let preprocess = preprocesses.remove(l).unwrap();
349          preprocess.commitments.transcript(self.params.algorithm.transcript());
350          {
351            let mut buf = vec![];
352            preprocess.addendum.write(&mut buf).unwrap();
353            self.params.algorithm.transcript().append_message(b"addendum", buf);
354          }
355
356          B.insert(*l, preprocess.commitments);
357          self.params.algorithm.process_addendum(&view, *l, preprocess.addendum)?;
358        }
359      }
360
361      // Re-format into the FROST-expected rho transcript
362      let mut rho_transcript = A::Transcript::new(b"FROST_rho");
363      rho_transcript.append_message(b"group_key", self.params.keys.group_key().to_bytes());
364      rho_transcript.append_message(b"message", C::hash_msg(msg));
365      rho_transcript.append_message(
366        b"preprocesses",
367        C::hash_commitments(self.params.algorithm.transcript().challenge(b"preprocesses").as_ref()),
368      );
369
370      // Generate the per-signer binding factors
371      B.calculate_binding_factors(&rho_transcript);
372
373      // Merge the rho transcript back into the global one to ensure its advanced, while
374      // simultaneously committing to everything
375      self
376        .params
377        .algorithm
378        .transcript()
379        .append_message(b"rho_transcript", rho_transcript.challenge(b"merge"));
380    }
381
382    #[allow(non_snake_case)]
383    let Rs = B.nonces(&nonces);
384
385    let our_binding_factors = B.binding_factors(multisig_params.i());
386    let nonces = self
387      .nonces
388      .drain(..)
389      .enumerate()
390      .map(|(n, nonces)| {
391        let [base, mut actual] = nonces.0;
392        *actual *= our_binding_factors[n];
393        *actual += base.deref();
394        actual
395      })
396      .collect::<Vec<_>>();
397
398    let share = self.params.algorithm.sign_share(&view, &Rs, nonces, msg);
399
400    Ok((
401      AlgorithmSignatureMachine {
402        params: self.params,
403        view,
404        B,
405        Rs,
406        share,
407        blame_entropy: self.blame_entropy,
408      },
409      SignatureShare(share),
410    ))
411  }
412}
413
414/// Trait for the final machine of a two-round signing protocol.
415pub trait SignatureMachine<S>: Send + Sync {
416  /// SignatureShare message for this machine.
417  type SignatureShare: Clone + PartialEq + Writable;
418
419  /// Read a Signature Share message.
420  fn read_share<R: Read>(&self, reader: &mut R) -> io::Result<Self::SignatureShare>;
421
422  /// Complete signing.
423  /// Takes in everyone elses' shares. Returns the signature.
424  fn complete(self, shares: HashMap<Participant, Self::SignatureShare>) -> Result<S, FrostError>;
425}
426
427/// Final step of the state machine for the signing process.
428///
429/// This may panic if an invalid algorithm is provided.
430#[allow(non_snake_case)]
431pub struct AlgorithmSignatureMachine<C: Curve, A: Algorithm<C>> {
432  params: Params<C, A>,
433  view: ThresholdView<C>,
434  B: BindingFactor<C>,
435  Rs: Vec<Vec<C::G>>,
436  share: C::F,
437  blame_entropy: [u8; 32],
438}
439
440impl<C: Curve, A: Algorithm<C>> SignatureMachine<A::Signature> for AlgorithmSignatureMachine<C, A> {
441  type SignatureShare = SignatureShare<C>;
442
443  fn read_share<R: Read>(&self, reader: &mut R) -> io::Result<SignatureShare<C>> {
444    Ok(SignatureShare(C::read_F(reader)?))
445  }
446
447  fn complete(
448    self,
449    mut shares: HashMap<Participant, SignatureShare<C>>,
450  ) -> Result<A::Signature, FrostError> {
451    let params = self.params.multisig_params();
452    validate_map(&shares, self.view.included(), params.i())?;
453
454    let mut responses = HashMap::new();
455    responses.insert(params.i(), self.share);
456    let mut sum = self.share;
457    for (l, share) in shares.drain() {
458      responses.insert(l, share.0);
459      sum += share.0;
460    }
461
462    // Perform signature validation instead of individual share validation
463    // For the success route, which should be much more frequent, this should be faster
464    // It also acts as an integrity check of this library's signing function
465    if let Some(sig) = self.params.algorithm.verify(self.view.group_key(), &self.Rs, sum) {
466      return Ok(sig);
467    }
468
469    // We could remove blame_entropy by taking in an RNG here
470    // Considering we don't need any RNG for a valid signature, and we only use the RNG here for
471    // performance reasons, it doesn't feel worthwhile to include as an argument to every
472    // implementor of the trait
473    let mut rng = ChaCha20Rng::from_seed(self.blame_entropy);
474    let mut batch = BatchVerifier::new(self.view.included().len());
475    for l in self.view.included() {
476      if let Ok(statements) = self.params.algorithm.verify_share(
477        self.view.verification_share(*l),
478        &self.B.bound(*l),
479        responses[l],
480      ) {
481        batch.queue(&mut rng, *l, statements);
482      } else {
483        Err(FrostError::InvalidShare(*l))?;
484      }
485    }
486
487    if let Err(l) = batch.verify_vartime_with_vartime_blame() {
488      Err(FrostError::InvalidShare(l))?;
489    }
490
491    // If everyone has a valid share, and there were enough participants, this should've worked
492    // The only known way to cause this, for valid parameters/algorithms, is to deserialize a
493    // semantically invalid FrostKeys
494    Err(FrostError::InternalError("everyone had a valid share yet the signature was still invalid"))
495  }
496}
modular_frost/sign.rs

modular_frost/
sign.rs
