dkg/
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::{
6  ops::Deref,
7  fmt::{self, Debug},
8};
9#[allow(unused_imports)]
10use std_shims::prelude::*;
11use std_shims::{sync::Arc, vec, vec::Vec, collections::HashMap, io};
12
13use zeroize::{Zeroize, Zeroizing};
14
15use ciphersuite::{
16  group::{
17    ff::{Field, PrimeField},
18    GroupEncoding,
19  },
20  Ciphersuite,
21};
22
23/// The ID of a participant, defined as a non-zero u16.
24#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Zeroize)]
25#[cfg_attr(feature = "borsh", derive(borsh::BorshSerialize))]
26pub struct Participant(u16);
27impl Participant {
28  /// Create a new Participant identifier from a u16.
29  pub const fn new(i: u16) -> Option<Participant> {
30    if i == 0 {
31      None
32    } else {
33      Some(Participant(i))
34    }
35  }
36
37  /// Convert a Participant identifier to bytes.
38  #[allow(clippy::wrong_self_convention)]
39  pub const fn to_bytes(&self) -> [u8; 2] {
40    self.0.to_le_bytes()
41  }
42}
43
44impl From<Participant> for u16 {
45  fn from(participant: Participant) -> u16 {
46    participant.0
47  }
48}
49
50impl fmt::Display for Participant {
51  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
52    write!(f, "{}", self.0)
53  }
54}
55
56/// Errors encountered when working with threshold keys.
57#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
58pub enum DkgError {
59  /// A parameter was zero.
60  #[error("a parameter was 0 (threshold {t}, participants {n})")]
61  ZeroParameter {
62    /// The specified threshold.
63    t: u16,
64    /// The specified total amount of participants.
65    n: u16,
66  },
67
68  /// The threshold exceeded the amount of participants.
69  #[error("invalid threshold (max {n}, got {t})")]
70  InvalidThreshold {
71    /// The specified threshold.
72    t: u16,
73    /// The specified total amount of participants.
74    n: u16,
75  },
76
77  /// Invalid participant identifier.
78  #[error("invalid participant (1 <= participant <= {n}, yet participant is {participant})")]
79  InvalidParticipant {
80    /// The total amount of participants.
81    n: u16,
82    /// The specified participant.
83    participant: Participant,
84  },
85
86  /// An incorrect amount of participants was specified.
87  #[error("incorrect amount of verification shares (n = {n} yet {shares} provided)")]
88  IncorrectAmountOfVerificationShares {
89    /// The amount of participants.
90    n: u16,
91    /// The amount of shares provided.
92    shares: usize,
93  },
94
95  /// An inapplicable method of interpolation was specified.
96  #[error("inapplicable method of interpolation ({0})")]
97  InapplicableInterpolation(&'static str),
98
99  /// An incorrect amount of participants was specified.
100  #[error("incorrect amount of participants. {t} <= amount <= {n}, yet amount is {amount}")]
101  IncorrectAmountOfParticipants {
102    /// The threshold required.
103    t: u16,
104    /// The total amount of participants.
105    n: u16,
106    /// The amount of participants specified.
107    amount: usize,
108  },
109
110  /// A participant was duplicated.
111  #[error("a participant ({0}) was duplicated")]
112  DuplicatedParticipant(Participant),
113
114  /// Not participating in declared signing set.
115  #[error("not participating in declared signing set")]
116  NotParticipating,
117}
118
119// Manually implements BorshDeserialize so we can enforce it's a valid index
120#[cfg(feature = "borsh")]
121impl 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/// Parameters for a multisig.
129#[derive(Clone, Copy, PartialEq, Eq, Debug, Zeroize)]
130#[cfg_attr(feature = "borsh", derive(borsh::BorshSerialize))]
131pub struct ThresholdParams {
132  /// Participants needed to sign on behalf of the group.
133  t: u16,
134  /// Amount of participants.
135  n: u16,
136  /// Index of the participant being acted for.
137  i: Participant,
138}
139
140/// An iterator over all participant indexes.
141struct AllParticipantIndexes {
142  i: u16,
143  n: u16,
144}
145impl Iterator for AllParticipantIndexes {
146  type Item = Participant;
147  fn next(&mut self) -> Option<Participant> {
148    if self.i > self.n {
149      None?;
150    }
151    let res = Participant::new(self.i).unwrap();
152
153    // If i == n == u16::MAX, we cause `i > n` by setting `n` to `0` so the iterator becomes empty
154    if self.i == u16::MAX {
155      self.n = 0;
156    } else {
157      self.i += 1;
158    }
159
160    Some(res)
161  }
162}
163
164impl ThresholdParams {
165  /// Create a new set of parameters.
166  pub const fn new(t: u16, n: u16, i: Participant) -> Result<ThresholdParams, DkgError> {
167    if (t == 0) || (n == 0) {
168      return Err(DkgError::ZeroParameter { t, n });
169    }
170
171    if t > n {
172      return Err(DkgError::InvalidThreshold { t, n });
173    }
174    if i.0 > n {
175      return Err(DkgError::InvalidParticipant { n, participant: i });
176    }
177
178    Ok(ThresholdParams { t, n, i })
179  }
180
181  /// The threshold for a multisig with these parameters.
182  pub const fn t(&self) -> u16 {
183    self.t
184  }
185  /// The amount of participants for a multisig with these parameters.
186  pub const fn n(&self) -> u16 {
187    self.n
188  }
189  /// The participant index of the share with these parameters.
190  pub const fn i(&self) -> Participant {
191    self.i
192  }
193
194  /// An iterator over all participant indexes.
195  pub fn all_participant_indexes(&self) -> impl Iterator<Item = Participant> {
196    AllParticipantIndexes { i: 1, n: self.n }
197  }
198}
199
200#[cfg(feature = "borsh")]
201impl borsh::BorshDeserialize for ThresholdParams {
202  fn deserialize_reader<R: io::Read>(reader: &mut R) -> io::Result<Self> {
203    let t = u16::deserialize_reader(reader)?;
204    let n = u16::deserialize_reader(reader)?;
205    let i = Participant::deserialize_reader(reader)?;
206    ThresholdParams::new(t, n, i).map_err(|e| io::Error::other(format!("{e:?}")))
207  }
208}
209
210/// A method of interpolation.
211#[derive(Clone, PartialEq, Eq, Debug, Zeroize)]
212pub enum Interpolation<F: Zeroize + PrimeField> {
213  /// A list of constant coefficients, one for each of the secret key shares.
214  /*
215    There's no benefit to using a full linear combination here, as the additive term would have
216    an entirely known evaluation with a fixed, public coefficient of `1`. Accordingly, the entire
217    key can simply be offset with the additive term to achieve the same effect.
218  */
219  Constant(Vec<F>),
220  /// Lagrange interpolation.
221  Lagrange,
222}
223
224impl<F: Zeroize + PrimeField> Interpolation<F> {
225  /// The interpolation factor for this participant, within this signing set.
226  fn interpolation_factor(&self, i: Participant, included: &[Participant]) -> F {
227    match self {
228      Interpolation::Constant(c) => c[usize::from(u16::from(i) - 1)],
229      Interpolation::Lagrange => {
230        let i_f = F::from(u64::from(u16::from(i)));
231
232        let mut num = F::ONE;
233        let mut denom = F::ONE;
234        for l in included {
235          if i == *l {
236            continue;
237          }
238
239          let share = F::from(u64::from(u16::from(*l)));
240          num *= share;
241          denom *= share - i_f;
242        }
243
244        // Safe as this will only be 0 if we're part of the above loop
245        // (which we have an if case to avoid)
246        num * denom.invert().unwrap()
247      }
248    }
249  }
250}
251
252/// A key share for a thresholdized secret key.
253///
254/// This is the 'core' structure containing all relevant data, expected to be wrapped into an
255/// heap-allocated pointer to minimize copies on the stack (`ThresholdKeys`, the publicly exposed
256/// type).
257#[derive(Clone, PartialEq, Eq)]
258struct ThresholdCore<C: Ciphersuite> {
259  params: ThresholdParams,
260  group_key: C::G,
261  verification_shares: HashMap<Participant, C::G>,
262  interpolation: Interpolation<C::F>,
263  secret_share: Zeroizing<C::F>,
264}
265
266impl<C: Ciphersuite> fmt::Debug for ThresholdCore<C> {
267  fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
268    fmt
269      .debug_struct("ThresholdCore")
270      .field("params", &self.params)
271      .field("group_key", &self.group_key)
272      .field("verification_shares", &self.verification_shares)
273      .field("interpolation", &self.interpolation)
274      .finish_non_exhaustive()
275  }
276}
277
278impl<C: Ciphersuite> Zeroize for ThresholdCore<C> {
279  fn zeroize(&mut self) {
280    self.params.zeroize();
281    self.group_key.zeroize();
282    for share in self.verification_shares.values_mut() {
283      share.zeroize();
284    }
285    self.interpolation.zeroize();
286    self.secret_share.zeroize();
287  }
288}
289
290/// Threshold keys usable for signing.
291#[derive(Clone, Debug, Zeroize)]
292pub struct ThresholdKeys<C: Ciphersuite> {
293  // Core keys.
294  #[zeroize(skip)]
295  core: Arc<Zeroizing<ThresholdCore<C>>>,
296
297  // Scalar applied to these keys.
298  scalar: C::F,
299  // Offset applied to these keys.
300  offset: C::F,
301}
302
303/// View of keys, interpolated and with the expected linear combination taken for usage.
304#[derive(Clone)]
305pub struct ThresholdView<C: Ciphersuite> {
306  interpolation: Interpolation<C::F>,
307  scalar: C::F,
308  offset: C::F,
309  group_key: C::G,
310  included: Vec<Participant>,
311  secret_share: Zeroizing<C::F>,
312  original_verification_shares: HashMap<Participant, C::G>,
313  verification_shares: HashMap<Participant, C::G>,
314}
315
316impl<C: Ciphersuite> fmt::Debug for ThresholdView<C> {
317  fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
318    fmt
319      .debug_struct("ThresholdView")
320      .field("interpolation", &self.interpolation)
321      .field("scalar", &self.scalar)
322      .field("offset", &self.offset)
323      .field("group_key", &self.group_key)
324      .field("included", &self.included)
325      .field("original_verification_shares", &self.original_verification_shares)
326      .field("verification_shares", &self.verification_shares)
327      .finish_non_exhaustive()
328  }
329}
330
331impl<C: Ciphersuite> Zeroize for ThresholdView<C> {
332  fn zeroize(&mut self) {
333    self.scalar.zeroize();
334    self.offset.zeroize();
335    self.group_key.zeroize();
336    self.included.zeroize();
337    self.secret_share.zeroize();
338    for share in self.original_verification_shares.values_mut() {
339      share.zeroize();
340    }
341    for share in self.verification_shares.values_mut() {
342      share.zeroize();
343    }
344  }
345}
346
347impl<C: Ciphersuite> ThresholdKeys<C> {
348  /// Create a new set of ThresholdKeys.
349  pub fn new(
350    params: ThresholdParams,
351    interpolation: Interpolation<C::F>,
352    secret_share: Zeroizing<C::F>,
353    verification_shares: HashMap<Participant, C::G>,
354  ) -> Result<ThresholdKeys<C>, DkgError> {
355    if verification_shares.len() != usize::from(params.n()) {
356      Err(DkgError::IncorrectAmountOfVerificationShares {
357        n: params.n(),
358        shares: verification_shares.len(),
359      })?;
360    }
361    for participant in verification_shares.keys().copied() {
362      if u16::from(participant) > params.n() {
363        Err(DkgError::InvalidParticipant { n: params.n(), participant })?;
364      }
365    }
366
367    match &interpolation {
368      Interpolation::Constant(_) => {
369        if params.t() != params.n() {
370          Err(DkgError::InapplicableInterpolation("constant interpolation for keys where t != n"))?;
371        }
372      }
373      Interpolation::Lagrange => {}
374    }
375
376    let t = (1 ..= params.t()).map(Participant).collect::<Vec<_>>();
377    let group_key =
378      t.iter().map(|i| verification_shares[i] * interpolation.interpolation_factor(*i, &t)).sum();
379
380    Ok(ThresholdKeys {
381      core: Arc::new(Zeroizing::new(ThresholdCore {
382        params,
383        interpolation,
384        secret_share,
385        group_key,
386        verification_shares,
387      })),
388      scalar: C::F::ONE,
389      offset: C::F::ZERO,
390    })
391  }
392
393  /// Scale the keys by a given scalar to allow for various account and privacy schemes.
394  ///
395  /// This scalar is ephemeral and will not be included when these keys are serialized. The
396  /// scalar is applied on top of any already-existing scalar/offset.
397  ///
398  /// Returns `None` if the scalar is equal to `0`.
399  #[must_use]
400  pub fn scale(mut self, scalar: C::F) -> Option<ThresholdKeys<C>> {
401    if bool::from(scalar.is_zero()) {
402      None?;
403    }
404    self.scalar *= scalar;
405    self.offset *= scalar;
406    Some(self)
407  }
408
409  /// Offset the keys by a given scalar to allow for various account and privacy schemes.
410  ///
411  /// This offset is ephemeral and will not be included when these keys are serialized. The
412  /// offset is applied on top of any already-existing scalar/offset.
413  #[must_use]
414  pub fn offset(mut self, offset: C::F) -> ThresholdKeys<C> {
415    self.offset += offset;
416    self
417  }
418
419  /// Return the current scalar in-use for these keys.
420  pub fn current_scalar(&self) -> C::F {
421    self.scalar
422  }
423
424  /// Return the current offset in-use for these keys.
425  pub fn current_offset(&self) -> C::F {
426    self.offset
427  }
428
429  /// Return the parameters for these keys.
430  pub fn params(&self) -> ThresholdParams {
431    self.core.params
432  }
433
434  /// Return the original group key, without any tweaks applied.
435  pub fn original_group_key(&self) -> C::G {
436    self.core.group_key
437  }
438
439  /// Return the interpolation method for these keys.
440  pub fn interpolation(&self) -> &Interpolation<C::F> {
441    &self.core.interpolation
442  }
443
444  /// Return the group key, with the expected linear combination taken.
445  pub fn group_key(&self) -> C::G {
446    (self.core.group_key * self.scalar) + (C::generator() * self.offset)
447  }
448
449  /// Return the underlying secret share for these keys, without any tweaks applied.
450  pub fn original_secret_share(&self) -> &Zeroizing<C::F> {
451    &self.core.secret_share
452  }
453
454  /// Return the original (untweaked) verification share for the specified participant.
455  ///
456  /// This will panic if the participant index is invalid for these keys.
457  pub fn original_verification_share(&self, l: Participant) -> C::G {
458    self.core.verification_shares[&l]
459  }
460
461  /// Obtain a view of these keys, interpolated for the specified signing set, with the specified
462  /// linear combination taken.
463  pub fn view(&self, mut included: Vec<Participant>) -> Result<ThresholdView<C>, DkgError> {
464    if (included.len() < self.params().t.into()) ||
465      (usize::from(self.params().n()) < included.len())
466    {
467      Err(DkgError::IncorrectAmountOfParticipants {
468        t: self.params().t,
469        n: self.params().n,
470        amount: included.len(),
471      })?;
472    }
473    included.sort();
474    {
475      let mut found = included[0] == self.params().i();
476      for i in 1 .. included.len() {
477        if included[i - 1] == included[i] {
478          Err(DkgError::DuplicatedParticipant(included[i]))?;
479        }
480        found |= included[i] == self.params().i();
481      }
482      if !found {
483        Err(DkgError::NotParticipating)?;
484      }
485    }
486    {
487      let last = *included.last().unwrap();
488      if u16::from(last) > self.params().n() {
489        Err(DkgError::InvalidParticipant { n: self.params().n(), participant: last })?;
490      }
491    }
492
493    // The interpolation occurs multiplicatively, letting us scale by the scalar now
494    let secret_share_scaled = Zeroizing::new(self.scalar * self.original_secret_share().deref());
495    let mut secret_share = Zeroizing::new(
496      self.core.interpolation.interpolation_factor(self.params().i(), &included) *
497        secret_share_scaled.deref(),
498    );
499
500    let mut verification_shares = HashMap::with_capacity(included.len());
501    for i in &included {
502      let verification_share = self.core.verification_shares[i];
503      let verification_share = verification_share *
504        self.scalar *
505        self.core.interpolation.interpolation_factor(*i, &included);
506      verification_shares.insert(*i, verification_share);
507    }
508
509    /*
510      The offset is included by adding it to the participant with the lowest ID.
511
512      This is done after interpolating to ensure, regardless of the method of interpolation, that
513      the method of interpolation does not scale the offset. For Lagrange interpolation, we could
514      add the offset to every key share before interpolating, yet for Constant interpolation, we
515      _have_ to add it as we do here (which also works even when we intend to perform Lagrange
516      interpolation).
517    */
518    if included[0] == self.params().i() {
519      *secret_share += self.offset;
520    }
521    *verification_shares.get_mut(&included[0]).unwrap() += C::generator() * self.offset;
522
523    Ok(ThresholdView {
524      interpolation: self.core.interpolation.clone(),
525      scalar: self.scalar,
526      offset: self.offset,
527      group_key: self.group_key(),
528      secret_share,
529      original_verification_shares: self.core.verification_shares.clone(),
530      verification_shares,
531      included,
532    })
533  }
534
535  /// Write these keys to a type satisfying `std::io::Write`.
536  ///
537  /// This will not include the ephemeral scalar/offset.
538  pub fn write<W: io::Write>(&self, writer: &mut W) -> io::Result<()> {
539    writer.write_all(&u32::try_from(C::ID.len()).unwrap().to_le_bytes())?;
540    writer.write_all(C::ID)?;
541    writer.write_all(&self.core.params.t.to_le_bytes())?;
542    writer.write_all(&self.core.params.n.to_le_bytes())?;
543    writer.write_all(&self.core.params.i.to_bytes())?;
544    match &self.core.interpolation {
545      Interpolation::Constant(c) => {
546        writer.write_all(&[0])?;
547        for c in c {
548          writer.write_all(c.to_repr().as_ref())?;
549        }
550      }
551      Interpolation::Lagrange => writer.write_all(&[1])?,
552    };
553    let mut share_bytes = self.core.secret_share.to_repr();
554    writer.write_all(share_bytes.as_ref())?;
555    share_bytes.as_mut().zeroize();
556    for l in 1 ..= self.core.params.n {
557      writer.write_all(
558        self.core.verification_shares[&Participant::new(l).unwrap()].to_bytes().as_ref(),
559      )?;
560    }
561    Ok(())
562  }
563
564  /// Serialize these keys to a `Vec<u8>`.
565  ///
566  /// This will not include the ephemeral scalar/offset.
567  pub fn serialize(&self) -> Zeroizing<Vec<u8>> {
568    let mut serialized = Zeroizing::new(vec![]);
569    self.write::<Vec<u8>>(serialized.as_mut()).unwrap();
570    serialized
571  }
572
573  /// Read keys from a type satisfying `std::io::Read`.
574  pub fn read<R: io::Read>(reader: &mut R) -> io::Result<ThresholdKeys<C>> {
575    {
576      let different = || io::Error::other("deserializing ThresholdKeys for another curve");
577
578      let mut id_len = [0; 4];
579      reader.read_exact(&mut id_len)?;
580      if u32::try_from(C::ID.len()).unwrap().to_le_bytes() != id_len {
581        Err(different())?;
582      }
583
584      let mut id = vec![0; C::ID.len()];
585      reader.read_exact(&mut id)?;
586      if id != C::ID {
587        Err(different())?;
588      }
589    }
590
591    let (t, n, i) = {
592      let mut read_u16 = || -> io::Result<u16> {
593        let mut value = [0; 2];
594        reader.read_exact(&mut value)?;
595        Ok(u16::from_le_bytes(value))
596      };
597      (
598        read_u16()?,
599        read_u16()?,
600        Participant::new(read_u16()?).ok_or(io::Error::other("invalid participant index"))?,
601      )
602    };
603
604    let mut interpolation = [0];
605    reader.read_exact(&mut interpolation)?;
606    let interpolation = match interpolation[0] {
607      0 => Interpolation::Constant({
608        let mut res = Vec::with_capacity(usize::from(n));
609        for _ in 0 .. n {
610          res.push(C::read_F(reader)?);
611        }
612        res
613      }),
614      1 => Interpolation::Lagrange,
615      _ => Err(io::Error::other("invalid interpolation method"))?,
616    };
617
618    let secret_share = Zeroizing::new(C::read_F(reader)?);
619
620    let mut verification_shares = HashMap::new();
621    for l in (1 ..= n).map(Participant) {
622      verification_shares.insert(l, <C as Ciphersuite>::read_G(reader)?);
623    }
624
625    ThresholdKeys::new(
626      ThresholdParams::new(t, n, i).map_err(io::Error::other)?,
627      interpolation,
628      secret_share,
629      verification_shares,
630    )
631    .map_err(io::Error::other)
632  }
633}
634
635impl<C: Ciphersuite> ThresholdView<C> {
636  /// Return the scalar applied to this view.
637  pub fn scalar(&self) -> C::F {
638    self.scalar
639  }
640
641  /// Return the offset applied to this view.
642  pub fn offset(&self) -> C::F {
643    self.offset
644  }
645
646  /// Return the group key.
647  pub fn group_key(&self) -> C::G {
648    self.group_key
649  }
650
651  /// Return the included signers.
652  pub fn included(&self) -> &[Participant] {
653    &self.included
654  }
655
656  /// Return the interpolation factor for a signer.
657  pub fn interpolation_factor(&self, participant: Participant) -> Option<C::F> {
658    if !self.included.contains(&participant) {
659      None?
660    }
661    Some(self.interpolation.interpolation_factor(participant, &self.included))
662  }
663
664  /// Return the interpolated secret share, with the expected linear combination taken.
665  pub fn secret_share(&self) -> &Zeroizing<C::F> {
666    &self.secret_share
667  }
668
669  /// Return the original (untweaked) verification share for the specified participant.
670  ///
671  /// This will panic if the participant index is invalid for these keys.
672  pub fn original_verification_share(&self, l: Participant) -> C::G {
673    self.original_verification_shares[&l]
674  }
675
676  /// Return the interpolated verification share, with the expected linear combination taken,
677  /// for the specified participant.
678  ///
679  /// This will panic if the participant was not included in the signing set.
680  pub fn verification_share(&self, l: Participant) -> C::G {
681    self.verification_shares[&l]
682  }
683}
dkg/lib.rs

dkg/
lib.rs
