dkg_mirror/
lib.rs

1#![cfg_attr(docsrs, feature(doc_auto_cfg))]
2#![doc = include_str!("../README.md")]
3#![cfg_attr(not(feature = "std"), no_std)]
4
5use core::fmt::{self, Debug};
6
7#[cfg(feature = "std")]
8use thiserror::Error;
9
10use zeroize::Zeroize;
11
12/// MuSig-style key aggregation.
13pub mod musig;
14
15/// Encryption types and utilities used to secure DKG messages.
16#[cfg(feature = "std")]
17pub mod encryption;
18
19/// The PedPoP distributed key generation protocol described in the
20/// [FROST paper](https://eprint.iacr.org/2020/852), augmented to be verifiable.
21#[cfg(feature = "std")]
22pub mod pedpop;
23
24/// Promote keys between ciphersuites.
25#[cfg(feature = "std")]
26pub mod promote;
27
28/// Tests for application-provided curves and algorithms.
29#[cfg(any(test, feature = "tests"))]
30pub mod tests;
31
32/// The ID of a participant, defined as a non-zero u16.
33#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Zeroize)]
34#[cfg_attr(feature = "borsh", derive(borsh::BorshSerialize))]
35pub struct Participant(pub(crate) u16);
36impl Participant {
37  /// Create a new Participant identifier from a u16.
38  pub fn new(i: u16) -> Option<Participant> {
39    if i == 0 {
40      None
41    } else {
42      Some(Participant(i))
43    }
44  }
45
46  /// Convert a Participant identifier to bytes.
47  #[allow(clippy::wrong_self_convention)]
48  pub fn to_bytes(&self) -> [u8; 2] {
49    self.0.to_le_bytes()
50  }
51}
52
53impl From<Participant> for u16 {
54  fn from(participant: Participant) -> u16 {
55    participant.0
56  }
57}
58
59impl fmt::Display for Participant {
60  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
61    write!(f, "{}", self.0)
62  }
63}
64
65/// Various errors possible during key generation.
66#[derive(Clone, PartialEq, Eq, Debug)]
67#[cfg_attr(feature = "std", derive(Error))]
68pub enum DkgError<B: Clone + PartialEq + Eq + Debug> {
69  /// A parameter was zero.
70  #[cfg_attr(feature = "std", error("a parameter was 0 (threshold {0}, participants {1})"))]
71  ZeroParameter(u16, u16),
72  /// The threshold exceeded the amount of participants.
73  #[cfg_attr(feature = "std", error("invalid threshold (max {1}, got {0})"))]
74  InvalidThreshold(u16, u16),
75  /// Invalid participant identifier.
76  #[cfg_attr(
77    feature = "std",
78    error("invalid participant (0 < participant <= {0}, yet participant is {1})")
79  )]
80  InvalidParticipant(u16, Participant),
81
82  /// Invalid signing set.
83  #[cfg_attr(feature = "std", error("invalid signing set"))]
84  InvalidSigningSet,
85  /// Invalid amount of participants.
86  #[cfg_attr(feature = "std", error("invalid participant quantity (expected {0}, got {1})"))]
87  InvalidParticipantQuantity(usize, usize),
88  /// A participant was duplicated.
89  #[cfg_attr(feature = "std", error("duplicated participant ({0})"))]
90  DuplicatedParticipant(Participant),
91  /// A participant was missing.
92  #[cfg_attr(feature = "std", error("missing participant {0}"))]
93  MissingParticipant(Participant),
94
95  /// An invalid proof of knowledge was provided.
96  #[cfg_attr(feature = "std", error("invalid proof of knowledge (participant {0})"))]
97  InvalidCommitments(Participant),
98  /// An invalid DKG share was provided.
99  #[cfg_attr(feature = "std", error("invalid share (participant {participant}, blame {blame})"))]
100  InvalidShare { participant: Participant, blame: Option<B> },
101}
102
103#[cfg(feature = "std")]
104mod lib {
105  pub use super::*;
106
107  use core::ops::Deref;
108  use std::{io, sync::Arc, collections::HashMap};
109
110  use zeroize::Zeroizing;
111
112  use ciphersuite::{
113    group::{
114      ff::{Field, PrimeField},
115      GroupEncoding,
116    },
117    Ciphersuite,
118  };
119
120  #[cfg(feature = "borsh")]
121  impl borsh::BorshDeserialize for Participant {
122    fn deserialize_reader<R: io::Read>(reader: &mut R) -> io::Result<Self> {
123      Participant::new(u16::deserialize_reader(reader)?)
124        .ok_or_else(|| io::Error::other("invalid participant"))
125    }
126  }
127
128  // Validate a map of values to have the expected included participants
129  pub(crate) fn validate_map<T, B: Clone + PartialEq + Eq + Debug>(
130    map: &HashMap<Participant, T>,
131    included: &[Participant],
132    ours: Participant,
133  ) -> Result<(), DkgError<B>> {
134    if (map.len() + 1) != included.len() {
135      Err(DkgError::InvalidParticipantQuantity(included.len(), map.len() + 1))?;
136    }
137
138    for included in included {
139      if *included == ours {
140        if map.contains_key(included) {
141          Err(DkgError::DuplicatedParticipant(*included))?;
142        }
143        continue;
144      }
145
146      if !map.contains_key(included) {
147        Err(DkgError::MissingParticipant(*included))?;
148      }
149    }
150
151    Ok(())
152  }
153
154  /// Parameters for a multisig.
155  // These fields should not be made public as they should be static
156  #[derive(Clone, Copy, PartialEq, Eq, Debug, Zeroize)]
157  #[cfg_attr(feature = "borsh", derive(borsh::BorshSerialize))]
158  pub struct ThresholdParams {
159    /// Participants needed to sign on behalf of the group.
160    pub(crate) t: u16,
161    /// Amount of participants.
162    pub(crate) n: u16,
163    /// Index of the participant being acted for.
164    pub(crate) i: Participant,
165  }
166
167  impl ThresholdParams {
168    /// Create a new set of parameters.
169    pub fn new(t: u16, n: u16, i: Participant) -> Result<ThresholdParams, DkgError<()>> {
170      if (t == 0) || (n == 0) {
171        Err(DkgError::ZeroParameter(t, n))?;
172      }
173
174      if t > n {
175        Err(DkgError::InvalidThreshold(t, n))?;
176      }
177      if u16::from(i) > n {
178        Err(DkgError::InvalidParticipant(n, i))?;
179      }
180
181      Ok(ThresholdParams { t, n, i })
182    }
183
184    /// Return the threshold for a multisig with these parameters.
185    pub fn t(&self) -> u16 {
186      self.t
187    }
188    /// Return the amount of participants for a multisig with these parameters.
189    pub fn n(&self) -> u16 {
190      self.n
191    }
192    /// Return the participant index of the share with these parameters.
193    pub fn i(&self) -> Participant {
194      self.i
195    }
196  }
197
198  #[cfg(feature = "borsh")]
199  impl borsh::BorshDeserialize for ThresholdParams {
200    fn deserialize_reader<R: io::Read>(reader: &mut R) -> io::Result<Self> {
201      let t = u16::deserialize_reader(reader)?;
202      let n = u16::deserialize_reader(reader)?;
203      let i = Participant::deserialize_reader(reader)?;
204      ThresholdParams::new(t, n, i).map_err(|e| io::Error::other(format!("{e:?}")))
205    }
206  }
207
208  /// Calculate the lagrange coefficient for a signing set.
209  pub fn lagrange<F: PrimeField>(i: Participant, included: &[Participant]) -> F {
210    let i_f = F::from(u64::from(u16::from(i)));
211
212    let mut num = F::ONE;
213    let mut denom = F::ONE;
214    for l in included {
215      if i == *l {
216        continue;
217      }
218
219      let share = F::from(u64::from(u16::from(*l)));
220      num *= share;
221      denom *= share - i_f;
222    }
223
224    // Safe as this will only be 0 if we're part of the above loop
225    // (which we have an if case to avoid)
226    num * denom.invert().unwrap()
227  }
228
229  /// Keys and verification shares generated by a DKG.
230  /// Called core as they're expected to be wrapped into an Arc before usage in various operations.
231  #[derive(Clone, PartialEq, Eq)]
232  pub struct ThresholdCore<C: Ciphersuite> {
233    /// Threshold Parameters.
234    pub(crate) params: ThresholdParams,
235
236    /// Secret share key.
237    pub(crate) secret_share: Zeroizing<C::F>,
238    /// Group key.
239    pub(crate) group_key: C::G,
240    /// Verification shares.
241    pub(crate) verification_shares: HashMap<Participant, C::G>,
242  }
243
244  impl<C: Ciphersuite> fmt::Debug for ThresholdCore<C> {
245    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
246      fmt
247        .debug_struct("ThresholdCore")
248        .field("params", &self.params)
249        .field("group_key", &self.group_key)
250        .field("verification_shares", &self.verification_shares)
251        .finish_non_exhaustive()
252    }
253  }
254
255  impl<C: Ciphersuite> Zeroize for ThresholdCore<C> {
256    fn zeroize(&mut self) {
257      self.params.zeroize();
258      self.secret_share.zeroize();
259      self.group_key.zeroize();
260      for share in self.verification_shares.values_mut() {
261        share.zeroize();
262      }
263    }
264  }
265
266  impl<C: Ciphersuite> ThresholdCore<C> {
267    pub(crate) fn new(
268      params: ThresholdParams,
269      secret_share: Zeroizing<C::F>,
270      verification_shares: HashMap<Participant, C::G>,
271    ) -> ThresholdCore<C> {
272      let t = (1 ..= params.t()).map(Participant).collect::<Vec<_>>();
273      ThresholdCore {
274        params,
275        secret_share,
276        group_key: t.iter().map(|i| verification_shares[i] * lagrange::<C::F>(*i, &t)).sum(),
277        verification_shares,
278      }
279    }
280
281    /// Parameters for these keys.
282    pub fn params(&self) -> ThresholdParams {
283      self.params
284    }
285
286    /// Secret share for these keys.
287    pub fn secret_share(&self) -> &Zeroizing<C::F> {
288      &self.secret_share
289    }
290
291    /// Group key for these keys.
292    pub fn group_key(&self) -> C::G {
293      self.group_key
294    }
295
296    pub(crate) fn verification_shares(&self) -> HashMap<Participant, C::G> {
297      self.verification_shares.clone()
298    }
299
300    /// Write these keys to a type satisfying std::io::Write.
301    pub fn write<W: io::Write>(&self, writer: &mut W) -> io::Result<()> {
302      writer.write_all(&u32::try_from(C::ID.len()).unwrap().to_le_bytes())?;
303      writer.write_all(C::ID)?;
304      writer.write_all(&self.params.t.to_le_bytes())?;
305      writer.write_all(&self.params.n.to_le_bytes())?;
306      writer.write_all(&self.params.i.to_bytes())?;
307      let mut share_bytes = self.secret_share.to_repr();
308      writer.write_all(share_bytes.as_ref())?;
309      share_bytes.as_mut().zeroize();
310      for l in 1 ..= self.params.n {
311        writer
312          .write_all(self.verification_shares[&Participant::new(l).unwrap()].to_bytes().as_ref())?;
313      }
314      Ok(())
315    }
316
317    /// Serialize these keys to a `Vec<u8>`.
318    pub fn serialize(&self) -> Zeroizing<Vec<u8>> {
319      let mut serialized = Zeroizing::new(vec![]);
320      self.write::<Vec<u8>>(serialized.as_mut()).unwrap();
321      serialized
322    }
323
324    /// Read keys from a type satisfying std::io::Read.
325    pub fn read<R: io::Read>(reader: &mut R) -> io::Result<ThresholdCore<C>> {
326      {
327        let different = || io::Error::other("deserializing ThresholdCore for another curve");
328
329        let mut id_len = [0; 4];
330        reader.read_exact(&mut id_len)?;
331        if u32::try_from(C::ID.len()).unwrap().to_le_bytes() != id_len {
332          Err(different())?;
333        }
334
335        let mut id = vec![0; C::ID.len()];
336        reader.read_exact(&mut id)?;
337        if id != C::ID {
338          Err(different())?;
339        }
340      }
341
342      let (t, n, i) = {
343        let mut read_u16 = || -> io::Result<u16> {
344          let mut value = [0; 2];
345          reader.read_exact(&mut value)?;
346          Ok(u16::from_le_bytes(value))
347        };
348        (
349          read_u16()?,
350          read_u16()?,
351          Participant::new(read_u16()?).ok_or(io::Error::other("invalid participant index"))?,
352        )
353      };
354
355      let secret_share = Zeroizing::new(C::read_F(reader)?);
356
357      let mut verification_shares = HashMap::new();
358      for l in (1 ..= n).map(Participant) {
359        verification_shares.insert(l, <C as Ciphersuite>::read_G(reader)?);
360      }
361
362      Ok(ThresholdCore::new(
363        ThresholdParams::new(t, n, i).map_err(|_| io::Error::other("invalid parameters"))?,
364        secret_share,
365        verification_shares,
366      ))
367    }
368  }
369
370  /// Threshold keys usable for signing.
371  #[derive(Clone, Debug, Zeroize)]
372  pub struct ThresholdKeys<C: Ciphersuite> {
373    // Core keys.
374    // If this is the last reference, the underlying keys will be dropped. When that happens, the
375    // private key present within it will be zeroed out (as it's within Zeroizing).
376    #[zeroize(skip)]
377    pub(crate) core: Arc<ThresholdCore<C>>,
378
379    // Offset applied to these keys.
380    pub(crate) offset: Option<C::F>,
381  }
382
383  /// View of keys, interpolated and offset for usage.
384  #[derive(Clone)]
385  pub struct ThresholdView<C: Ciphersuite> {
386    offset: C::F,
387    group_key: C::G,
388    included: Vec<Participant>,
389    secret_share: Zeroizing<C::F>,
390    original_verification_shares: HashMap<Participant, C::G>,
391    verification_shares: HashMap<Participant, C::G>,
392  }
393
394  impl<C: Ciphersuite> fmt::Debug for ThresholdView<C> {
395    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
396      fmt
397        .debug_struct("ThresholdView")
398        .field("offset", &self.offset)
399        .field("group_key", &self.group_key)
400        .field("included", &self.included)
401        .field("original_verification_shares", &self.original_verification_shares)
402        .field("verification_shares", &self.verification_shares)
403        .finish_non_exhaustive()
404    }
405  }
406
407  impl<C: Ciphersuite> Zeroize for ThresholdView<C> {
408    fn zeroize(&mut self) {
409      self.offset.zeroize();
410      self.group_key.zeroize();
411      self.included.zeroize();
412      self.secret_share.zeroize();
413      for share in self.original_verification_shares.values_mut() {
414        share.zeroize();
415      }
416      for share in self.verification_shares.values_mut() {
417        share.zeroize();
418      }
419    }
420  }
421
422  impl<C: Ciphersuite> ThresholdKeys<C> {
423    /// Create a new set of ThresholdKeys from a ThresholdCore.
424    pub fn new(core: ThresholdCore<C>) -> ThresholdKeys<C> {
425      ThresholdKeys { core: Arc::new(core), offset: None }
426    }
427
428    /// Offset the keys by a given scalar to allow for various account and privacy schemes.
429    ///
430    /// This offset is ephemeral and will not be included when these keys are serialized. It also
431    /// accumulates, so calling offset multiple times will produce a offset of the offsets' sum.
432    #[must_use]
433    pub fn offset(&self, offset: C::F) -> ThresholdKeys<C> {
434      let mut res = self.clone();
435      // Carry any existing offset
436      // Enables schemes like Monero's subaddresses which have a per-subaddress offset and then a
437      // one-time-key offset
438      res.offset = Some(offset + res.offset.unwrap_or(C::F::ZERO));
439      res
440    }
441
442    /// Return the current offset in-use for these keys.
443    pub fn current_offset(&self) -> Option<C::F> {
444      self.offset
445    }
446
447    /// Return the parameters for these keys.
448    pub fn params(&self) -> ThresholdParams {
449      self.core.params
450    }
451
452    /// Return the secret share for these keys.
453    pub fn secret_share(&self) -> &Zeroizing<C::F> {
454      &self.core.secret_share
455    }
456
457    /// Return the group key, with any offset applied.
458    pub fn group_key(&self) -> C::G {
459      self.core.group_key + (C::generator() * self.offset.unwrap_or(C::F::ZERO))
460    }
461
462    /// Return all participants' verification shares without any offsetting.
463    pub(crate) fn verification_shares(&self) -> HashMap<Participant, C::G> {
464      self.core.verification_shares()
465    }
466
467    /// Serialize these keys to a `Vec<u8>`.
468    pub fn serialize(&self) -> Zeroizing<Vec<u8>> {
469      self.core.serialize()
470    }
471
472    /// Obtain a view of these keys, with any offset applied, interpolated for the specified signing
473    /// set.
474    pub fn view(&self, mut included: Vec<Participant>) -> Result<ThresholdView<C>, DkgError<()>> {
475      if (included.len() < self.params().t.into()) ||
476        (usize::from(self.params().n()) < included.len())
477      {
478        Err(DkgError::InvalidSigningSet)?;
479      }
480      included.sort();
481
482      let mut secret_share = Zeroizing::new(
483        lagrange::<C::F>(self.params().i(), &included) * self.secret_share().deref(),
484      );
485
486      let mut verification_shares = self.verification_shares();
487      for (i, share) in &mut verification_shares {
488        *share *= lagrange::<C::F>(*i, &included);
489      }
490
491      // The offset is included by adding it to the participant with the lowest ID
492      let offset = self.offset.unwrap_or(C::F::ZERO);
493      if included[0] == self.params().i() {
494        *secret_share += offset;
495      }
496      *verification_shares.get_mut(&included[0]).unwrap() += C::generator() * offset;
497
498      Ok(ThresholdView {
499        offset,
500        group_key: self.group_key(),
501        secret_share,
502        original_verification_shares: self.verification_shares(),
503        verification_shares,
504        included,
505      })
506    }
507  }
508
509  impl<C: Ciphersuite> From<ThresholdCore<C>> for ThresholdKeys<C> {
510    fn from(keys: ThresholdCore<C>) -> ThresholdKeys<C> {
511      ThresholdKeys::new(keys)
512    }
513  }
514
515  impl<C: Ciphersuite> ThresholdView<C> {
516    /// Return the offset for this view.
517    pub fn offset(&self) -> C::F {
518      self.offset
519    }
520
521    /// Return the group key.
522    pub fn group_key(&self) -> C::G {
523      self.group_key
524    }
525
526    /// Return the included signers.
527    pub fn included(&self) -> &[Participant] {
528      &self.included
529    }
530
531    /// Return the interpolated, offset secret share.
532    pub fn secret_share(&self) -> &Zeroizing<C::F> {
533      &self.secret_share
534    }
535
536    /// Return the original verification share for the specified participant.
537    pub fn original_verification_share(&self, l: Participant) -> C::G {
538      self.original_verification_shares[&l]
539    }
540
541    /// Return the interpolated, offset verification share for the specified participant.
542    pub fn verification_share(&self, l: Participant) -> C::G {
543      self.verification_shares[&l]
544    }
545  }
546}
547#[cfg(feature = "std")]
548pub use lib::*;
dkg_mirror/lib.rs

dkg_mirror/
lib.rs
