1  use std::collections::{BTreeMap, HashMap};
  2  use std::fmt::Debug;
  3  use std::hash::Hash;
  4  use std::io::Write;
  5  
  6  use anyhow::{ensure, format_err};
  7  use async_trait::async_trait;
  8  use bitcoin::secp256k1;
  9  use bitcoin_hashes::sha256::{Hash as Sha256, HashEngine};
 10  use bls12_381::Scalar;
 11  use fedimint_core::config::{
 12      DkgError, DkgGroup, DkgMessage, DkgPeerMsg, DkgResult, ISupportedDkgMessage,
 13  };
 14  use fedimint_core::core::{Decoder, ModuleInstanceId, ModuleKind};
 15  use fedimint_core::encoding::{Decodable, Encodable};
 16  use fedimint_core::module::registry::ModuleDecoderRegistry;
 17  use fedimint_core::module::PeerHandle;
 18  use fedimint_core::net::peers::MuxPeerConnections;
 19  use fedimint_core::runtime::spawn;
 20  use fedimint_core::{BitcoinHash, NumPeersExt, PeerId};
 21  use rand::rngs::OsRng;
 22  use rand::{RngCore, SeedableRng};
 23  use rand_chacha::ChaChaRng;
 24  use serde::de::DeserializeOwned;
 25  use serde::Serialize;
 26  use sha3::Digest;
 27  use threshold_crypto::ff::Field;
 28  use threshold_crypto::group::Curve;
 29  use threshold_crypto::poly::Commitment;
 30  use threshold_crypto::serde_impl::SerdeSecret;
 31  use threshold_crypto::{
 32      G1Affine, G1Projective, G2Affine, G2Projective, PublicKeySet, SecretKeyShare,
 33  };
 34  
 35  struct Dkg<G> {
 36      gen_g: G,
 37      peers: Vec<PeerId>,
 38      our_id: PeerId,
 39      threshold: usize,
 40      f1_poly: Vec<Scalar>,
 41      f2_poly: Vec<Scalar>,
 42      hashed_commits: BTreeMap<PeerId, Sha256>,
 43      commitments: BTreeMap<PeerId, Vec<G>>,
 44      sk_shares: BTreeMap<PeerId, Scalar>,
 45      pk_shares: BTreeMap<PeerId, Vec<G>>,
 46  }
 47  
 48  /// Implementation of "Secure Distributed Key Generation for Discrete-Log Based
 49  /// Cryptosystems" by Rosario Gennaro and Stanislaw Jarecki and Hugo Krawczyk
 50  /// and Tal Rabin
 51  ///
 52  /// Prevents any manipulation of the secret key, but fails with any
 53  /// non-cooperative peers
 54  impl<G: DkgGroup> Dkg<G> {
 55      /// Creates the DKG and the first step of the algorithm
 56      pub fn new(
 57          group: G,
 58          our_id: PeerId,
 59          peers: Vec<PeerId>,
 60          threshold: usize,
 61          rng: &mut impl rand::RngCore,
 62      ) -> (Self, DkgStep<G>) {
 63          let f1_poly = random_scalar_coefficients(threshold - 1, rng);
 64          let f2_poly = random_scalar_coefficients(threshold - 1, rng);
 65  
 66          let mut dkg = Dkg {
 67              gen_g: group,
 68              peers,
 69              our_id,
 70              threshold,
 71              f1_poly,
 72              f2_poly,
 73              hashed_commits: Default::default(),
 74              commitments: Default::default(),
 75              sk_shares: Default::default(),
 76              pk_shares: Default::default(),
 77          };
 78  
 79          // broadcast our commitment to the polynomials
 80          let commit: Vec<G> = dkg
 81              .f1_poly
 82              .iter()
 83              .map(|c| dkg.gen_g * *c)
 84              .zip(dkg.f2_poly.iter().map(|c| dkg.gen_h() * *c))
 85              .map(|(g, h)| g + h)
 86              .collect();
 87  
 88          let hashed = dkg.hash(commit.clone());
 89          dkg.commitments.insert(our_id, commit);
 90          dkg.hashed_commits.insert(our_id, hashed);
 91          let step = dkg.broadcast(DkgMessage::HashedCommit(hashed));
 92  
 93          (dkg, step)
 94      }
 95  
 96      /// Runs a single step of the DKG algorithm, processing a `msg` from `peer`
 97      pub fn step(&mut self, peer: PeerId, msg: DkgMessage<G>) -> anyhow::Result<DkgStep<G>> {
 98          match msg {
 99              DkgMessage::HashedCommit(hashed) => {
100                  match self.hashed_commits.get(&peer) {
101                      Some(old) if *old != hashed => {
102                          return Err(format_err!("{peer} sent us two hashes!"))
103                      }
104                      _ => self.hashed_commits.insert(peer, hashed),
105                  };
106  
107                  if self.hashed_commits.len() == self.peers.len() {
108                      let our_commit = self.commitments[&self.our_id].clone();
109                      return Ok(self.broadcast(DkgMessage::Commit(our_commit)));
110                  }
111              }
112              DkgMessage::Commit(commit) => {
113                  let hash = self.hash(commit.clone());
114                  ensure!(self.threshold == commit.len(), "wrong degree from {peer}");
115                  ensure!(hash == self.hashed_commits[&peer], "wrong hash from {peer}");
116  
117                  match self.commitments.get(&peer) {
118                      Some(old) if *old != commit => {
119                          return Err(format_err!("{peer} sent us two commitments!"))
120                      }
121                      _ => self.commitments.insert(peer, commit),
122                  };
123  
124                  // once everyone has made commitments, send out shares
125                  if self.commitments.len() == self.peers.len() {
126                      let mut messages = vec![];
127                      for peer in &self.peers {
128                          let s1 = evaluate_polynomial_scalar(&self.f1_poly, &scalar(peer));
129                          let s2 = evaluate_polynomial_scalar(&self.f2_poly, &scalar(peer));
130  
131                          if *peer == self.our_id {
132                              self.sk_shares.insert(self.our_id, s1);
133                          } else {
134                              messages.push((*peer, DkgMessage::Share(s1, s2)));
135                          }
136                      }
137                      return Ok(DkgStep::Messages(messages));
138                  }
139              }
140              // Pedersen-VSS verifies the shares match the commitments
141              DkgMessage::Share(s1, s2) => {
142                  let share_product = (self.gen_g * s1) + (self.gen_h() * s2);
143                  let commitment = self
144                      .commitments
145                      .get(&peer)
146                      .ok_or_else(|| format_err!("{peer} sent share before commit"))?;
147                  let commit_product: G = commitment
148                      .iter()
149                      .enumerate()
150                      .map(|(idx, commit)| *commit * scalar(&self.our_id).pow(&[idx as u64, 0, 0, 0]))
151                      .reduce(|a, b| a + b)
152                      .expect("sums");
153  
154                  ensure!(share_product == commit_product, "bad commit from {peer}");
155                  match self.sk_shares.get(&peer) {
156                      Some(old) if *old != s1 => {
157                          return Err(format_err!("{peer} sent us two shares!"))
158                      }
159                      _ => self.sk_shares.insert(peer, s1),
160                  };
161  
162                  if self.sk_shares.len() == self.peers.len() {
163                      let extract: Vec<G> = self.f1_poly.iter().map(|c| self.gen_g * *c).collect();
164  
165                      self.pk_shares.insert(self.our_id, extract.clone());
166                      return Ok(self.broadcast(DkgMessage::Extract(extract)));
167                  }
168              }
169              // Feldman-VSS exposes the public key shares
170              DkgMessage::Extract(extract) => {
171                  let share = self
172                      .sk_shares
173                      .get(&peer)
174                      .ok_or_else(|| format_err!("{peer} sent extract before share"))?;
175                  let share_product = self.gen_g * *share;
176                  let extract_product: G = extract
177                      .iter()
178                      .enumerate()
179                      .map(|(idx, commit)| *commit * scalar(&self.our_id).pow(&[idx as u64, 0, 0, 0]))
180                      .reduce(|a, b| a + b)
181                      .expect("sums");
182  
183                  ensure!(share_product == extract_product, "bad extract from {peer}");
184                  ensure!(self.threshold == extract.len(), "wrong degree from {peer}");
185                  match self.pk_shares.get(&peer) {
186                      Some(old) if *old != extract => {
187                          return Err(format_err!("{peer} sent us two extracts!"))
188                      }
189                      _ => self.pk_shares.insert(peer, extract),
190                  };
191  
192                  if self.pk_shares.len() == self.peers.len() {
193                      let sks = self.sk_shares.values().sum();
194  
195                      let pks: Vec<G> = (0..self.threshold)
196                          .map(|idx| {
197                              self.pk_shares
198                                  .values()
199                                  .map(|shares| *shares.get(idx).unwrap())
200                                  .reduce(|a, b| a + b)
201                                  .expect("sums")
202                          })
203                          .collect();
204  
205                      return Ok(DkgStep::Result(DkgKeys {
206                          public_key_set: pks,
207                          secret_key_share: sks,
208                      }));
209                  }
210              }
211          }
212  
213          Ok(DkgStep::Messages(vec![]))
214      }
215  
216      fn hash(&self, poly: Vec<G>) -> Sha256 {
217          let mut engine = HashEngine::default();
218          for element in poly.iter() {
219              engine
220                  .write_all(element.to_bytes().as_ref())
221                  .expect("hashes");
222          }
223          Sha256::from_engine(engine)
224      }
225  
226      fn broadcast(&self, msg: DkgMessage<G>) -> DkgStep<G> {
227          let others = self.peers.iter().filter(|p| **p != self.our_id);
228          DkgStep::Messages(others.map(|peer| (*peer, msg.clone())).collect())
229      }
230  
231      /// Get a second generator by hashing the first one to the curve
232      fn gen_h(&self) -> G {
233          let mut hash_engine = sha3::Sha3_256::new();
234  
235          hash_engine.update(self.gen_g.clone().to_bytes().as_ref());
236  
237          G::random(&mut ChaChaRng::from_seed(hash_engine.finalize().into()))
238      }
239  }
240  
241  /// PeerIds are offset by 1, since evaluating a poly at 0 reveals the secret
242  pub fn scalar(peer: &PeerId) -> Scalar {
243      Scalar::from(peer.to_usize() as u64 + 1)
244  }
245  
246  pub struct DkgRunner<T> {
247      peers: Vec<PeerId>,
248      our_id: PeerId,
249      dkg_config: HashMap<T, usize>,
250  }
251  
252  /// Helper for running multiple DKGs over the same peer connections
253  ///
254  /// Messages are `(T, DkgMessage)` for creating a DKG for every `T`
255  impl<T> DkgRunner<T>
256  where
257      T: Serialize + DeserializeOwned + Unpin + Send + Clone + Eq + Hash,
258  {
259      /// Create multiple DKGs with the same `threshold` signatures required
260      pub fn multi(keys: Vec<T>, threshold: usize, our_id: &PeerId, peers: &[PeerId]) -> Self {
261          let dkg_config = keys.into_iter().map(|key| (key, threshold)).collect();
262  
263          Self {
264              our_id: *our_id,
265              peers: peers.to_vec(),
266              dkg_config,
267          }
268      }
269  
270      /// Create a single DKG with `threshold` signatures required
271      pub fn new(key: T, threshold: usize, our_id: &PeerId, peers: &[PeerId]) -> Self {
272          Self::multi(vec![key], threshold, our_id, peers)
273      }
274  
275      /// Create another DKG with `threshold` signatures required
276      pub fn add(&mut self, key: T, threshold: usize) {
277          self.dkg_config.insert(key, threshold);
278      }
279  
280      /// Create keys from G2 (96B keys, 48B messages) used in `tbs`
281      pub async fn run_g2(
282          &mut self,
283          module_id: ModuleInstanceId,
284          connections: &MuxPeerConnections<(ModuleInstanceId, String), DkgPeerMsg>,
285      ) -> DkgResult<HashMap<T, DkgKeys<G2Projective>>> {
286          self.run(module_id, G2Projective::generator(), connections)
287              .await
288      }
289  
290      /// Create keys from G1 (48B keys, 96B messages) used in `threshold_crypto`
291      pub async fn run_g1(
292          &mut self,
293          module_id: ModuleInstanceId,
294          connections: &MuxPeerConnections<(ModuleInstanceId, String), DkgPeerMsg>,
295      ) -> DkgResult<HashMap<T, DkgKeys<G1Projective>>> {
296          self.run(module_id, G1Projective::generator(), connections)
297              .await
298      }
299  
300      /// Runs the DKG algorithms with our peers
301      ///
302      /// WARNING: Currently we do not handle any unexpected messages, all peers
303      /// are expected to be cooperative
304      pub async fn run<G: DkgGroup>(
305          &mut self,
306          module_id: ModuleInstanceId,
307          group: G,
308          connections: &MuxPeerConnections<(ModuleInstanceId, String), DkgPeerMsg>,
309      ) -> DkgResult<HashMap<T, DkgKeys<G>>>
310      where
311          DkgMessage<G>: ISupportedDkgMessage,
312      {
313          // Use tokio channel to await on `recv` or we might block
314          let (send, mut receive) = tokio::sync::mpsc::channel(10_000);
315  
316          // For every `key` we run DKG in a new tokio task
317          self.dkg_config
318              .clone()
319              .into_iter()
320              .for_each(|(key, threshold)| {
321                  let our_id = self.our_id;
322                  let peers = self.peers.clone();
323                  let connections = connections.clone();
324                  let key = serde_json::to_string(&key).expect("serialization can't fail");
325                  let send = send.clone();
326  
327                  spawn("dkg runner", async move {
328                      let (dkg, step) = Dkg::new(group, our_id, peers, threshold, &mut OsRng);
329                      let result =
330                          Self::run_dkg_key((module_id, key.clone()), connections, dkg, step).await;
331                      send.send((key, result)).await.expect("channel open");
332                  });
333              });
334  
335          // Collect every key, returning an error if any fails
336          let mut results: HashMap<T, DkgKeys<G>> = HashMap::new();
337          while results.len() < self.dkg_config.len() {
338              let (key, result) = receive.recv().await.expect("channel open");
339              let key = serde_json::from_str(&key).expect("serialization can't fail");
340              results.insert(key, result?);
341          }
342          Ok(results)
343      }
344  
345      /// Runs the DKG algorithms for a given key and module id
346      async fn run_dkg_key<G: DkgGroup>(
347          key_id: (ModuleInstanceId, String),
348          connections: MuxPeerConnections<(ModuleInstanceId, String), DkgPeerMsg>,
349          mut dkg: Dkg<G>,
350          initial_step: DkgStep<G>,
351      ) -> DkgResult<DkgKeys<G>>
352      where
353          DkgMessage<G>: ISupportedDkgMessage,
354      {
355          if let DkgStep::Messages(messages) = initial_step {
356              for (peer, msg) in messages {
357                  let send_msg = DkgPeerMsg::DistributedGen(msg.to_msg());
358                  connections.send(&[peer], key_id.clone(), send_msg).await?;
359              }
360          }
361  
362          // process steps for each key
363          loop {
364              let (peer, msg) = connections.receive(key_id.clone()).await?;
365  
366              let message = match msg {
367                  DkgPeerMsg::DistributedGen(v) => Ok(v),
368                  _ => Err(format_err!(
369                      "Key {key_id:?} wrong message received: {msg:?}"
370                  )),
371              }?;
372  
373              let message = ISupportedDkgMessage::from_msg(message)?;
374              let step = dkg.step(peer, message)?;
375  
376              match step {
377                  DkgStep::Messages(messages) => {
378                      for (peer, msg) in messages {
379                          let send_msg = DkgPeerMsg::DistributedGen(msg.to_msg());
380                          connections.send(&[peer], key_id.clone(), send_msg).await?;
381                      }
382                  }
383                  DkgStep::Result(result) => {
384                      return Ok(result);
385                  }
386              }
387          }
388      }
389  }
390  
391  pub fn random_scalar_coefficients(degree: usize, rng: &mut impl RngCore) -> Vec<Scalar> {
392      (0..=degree).map(|_| random_scalar(rng)).collect()
393  }
394  
395  fn random_scalar(rng: &mut impl RngCore) -> Scalar {
396      Scalar::random(rng)
397  }
398  
399  pub fn evaluate_polynomial_scalar(coefficients: &[Scalar], x: &Scalar) -> Scalar {
400      coefficients
401          .iter()
402          .cloned()
403          .rev()
404          .reduce(|acc, coefficient| acc * x + coefficient)
405          .expect("We have at least one coefficient")
406  }
407  
408  #[derive(Debug, Clone)]
409  pub enum DkgStep<G: DkgGroup> {
410      Messages(Vec<(PeerId, DkgMessage<G>)>),
411      Result(DkgKeys<G>),
412  }
413  
414  #[derive(Debug, Clone)]
415  pub struct DkgKeys<G> {
416      pub public_key_set: Vec<G>,
417      pub secret_key_share: Scalar,
418  }
419  
420  /// Our secret key share of a threshold key
421  #[derive(Debug, Clone)]
422  pub struct ThresholdKeys {
423      pub public_key_set: PublicKeySet,
424      pub secret_key_share: SerdeSecret<SecretKeyShare>,
425  }
426  
427  impl DkgKeys<G2Projective> {
428      pub fn tbs(self) -> (Vec<G2Projective>, tbs::SecretKeyShare) {
429          (
430              self.public_key_set,
431              tbs::SecretKeyShare(self.secret_key_share),
432          )
433      }
434  }
435  
436  impl DkgKeys<G1Projective> {
437      pub fn threshold_crypto(&self) -> ThresholdKeys {
438          ThresholdKeys {
439              public_key_set: PublicKeySet::from(Commitment::from(self.public_key_set.clone())),
440              secret_key_share: SerdeSecret(SecretKeyShare::from_mut(
441                  &mut self.secret_key_share.clone(),
442              )),
443          }
444      }
445  
446      pub fn tpe(self) -> (Vec<G1Projective>, Scalar) {
447          (self.public_key_set, self.secret_key_share)
448      }
449  }
450  
451  pub fn evaluate_polynomial_g1(coefficients: &[G1Projective], x: &Scalar) -> G1Affine {
452      coefficients
453          .iter()
454          .cloned()
455          .rev()
456          .reduce(|acc, coefficient| acc * x + coefficient)
457          .expect("We have at least one coefficient")
458          .to_affine()
459  }
460  
461  pub fn evaluate_polynomial_g2(coefficients: &[G2Projective], x: &Scalar) -> G2Affine {
462      coefficients
463          .iter()
464          .cloned()
465          .rev()
466          .reduce(|acc, coefficient| acc * x + coefficient)
467          .expect("We have at least one coefficient")
468          .to_affine()
469  }
470  
471  // TODO: this trait is only needed to break the `DkgHandle` impl
472  // from it's definition that is still in `fedimint-core`
473  #[async_trait]
474  pub trait PeerHandleOps {
475      async fn run_dkg_g1<T>(&self, v: T) -> DkgResult<HashMap<T, DkgKeys<G1Projective>>>
476      where
477          T: Serialize + DeserializeOwned + Unpin + Send + Clone + Eq + Hash + Sync;
478  
479      async fn run_dkg_multi_g2<T>(&self, v: Vec<T>) -> DkgResult<HashMap<T, DkgKeys<G2Projective>>>
480      where
481          T: Serialize + DeserializeOwned + Unpin + Send + Clone + Eq + Hash + Sync;
482  
483      /// Exchanges a `DkgPeerMsg::PublicKey(key)` with all peers. Used by the
484      /// wallet module to setup the multisig wallet during DKG.
485      async fn exchange_pubkeys(
486          &self,
487          dkg_key: String,
488          key: secp256k1::PublicKey,
489      ) -> DkgResult<BTreeMap<PeerId, secp256k1::PublicKey>>;
490  
491      /// Exchanges a `DkgPeerMsg::Module(Vec<u8>)` with all peers. All peers are
492      /// required to be online and submit a response for this to return
493      /// properly. The caller's message will be included in the returned
494      /// `BTreeMap` under the `PeerId` of this peer. This allows modules to
495      /// exchange arbitrary data during distributed key generation.
496      async fn exchange_with_peers<T: Encodable + Decodable + Send + Sync>(
497          &self,
498          dkg_key: String,
499          data: T,
500          kind: ModuleKind,
501          decoder: Decoder,
502      ) -> DkgResult<BTreeMap<PeerId, T>>;
503  }
504  
505  #[async_trait]
506  impl<'a> PeerHandleOps for PeerHandle<'a> {
507      async fn run_dkg_g1<T>(&self, v: T) -> DkgResult<HashMap<T, DkgKeys<G1Projective>>>
508      where
509          T: Serialize + DeserializeOwned + Unpin + Send + Clone + Eq + Hash + Sync,
510      {
511          let mut dkg = DkgRunner::new(v, self.peers.threshold(), &self.our_id, &self.peers);
512          dkg.run_g1(self.module_instance_id, self.connections).await
513      }
514  
515      async fn run_dkg_multi_g2<T>(&self, v: Vec<T>) -> DkgResult<HashMap<T, DkgKeys<G2Projective>>>
516      where
517          T: Serialize + DeserializeOwned + Unpin + Send + Clone + Eq + Hash + Sync,
518      {
519          let mut dkg = DkgRunner::multi(v, self.peers.threshold(), &self.our_id, &self.peers);
520  
521          dkg.run_g2(self.module_instance_id, self.connections).await
522      }
523  
524      async fn exchange_pubkeys(
525          &self,
526          dkg_key: String,
527          key: secp256k1::PublicKey,
528      ) -> DkgResult<BTreeMap<PeerId, secp256k1::PublicKey>> {
529          let mut peer_peg_in_keys: BTreeMap<PeerId, secp256k1::PublicKey> = BTreeMap::new();
530  
531          self.connections
532              .send(
533                  &self.peers,
534                  (self.module_instance_id, dkg_key.clone()),
535                  DkgPeerMsg::PublicKey(key),
536              )
537              .await?;
538  
539          peer_peg_in_keys.insert(self.our_id, key);
540          while peer_peg_in_keys.len() < self.peers.len() {
541              match self
542                  .connections
543                  .receive((self.module_instance_id, dkg_key.clone()))
544                  .await?
545              {
546                  (peer, DkgPeerMsg::PublicKey(key)) => {
547                      peer_peg_in_keys.insert(peer, key);
548                  }
549                  (peer, msg) => {
550                      return Err(
551                          format_err!("Invalid message received from: {peer}: {msg:?}").into(),
552                      );
553                  }
554              }
555          }
556  
557          Ok(peer_peg_in_keys)
558      }
559  
560      async fn exchange_with_peers<T: Encodable + Decodable + Send + Sync>(
561          &self,
562          dkg_key: String,
563          data: T,
564          kind: ModuleKind,
565          decoder: Decoder,
566      ) -> DkgResult<BTreeMap<PeerId, T>> {
567          let mut peer_data: BTreeMap<PeerId, T> = BTreeMap::new();
568          let msg = DkgPeerMsg::Module(data.consensus_encode_to_vec());
569  
570          self.connections
571              .send(&self.peers, (self.module_instance_id, dkg_key.clone()), msg)
572              .await?;
573          peer_data.insert(self.our_id, data);
574  
575          let modules =
576              ModuleDecoderRegistry::new([(self.module_instance_id, kind.clone(), decoder)]);
577          while peer_data.len() < self.peers.len() {
578              match self
579                  .connections
580                  .receive((self.module_instance_id, dkg_key.clone()))
581                  .await?
582              {
583                  (peer, DkgPeerMsg::Module(bytes)) => {
584                      let received_data: T = T::consensus_decode_vec(bytes, &modules)
585                          .map_err(|_| DkgError::ModuleDecodeError(kind.clone()))?;
586                      peer_data.insert(peer, received_data);
587                  }
588                  (peer, msg) => {
589                      return Err(format_err!("Invalid message received from {peer}: {msg:?}").into());
590                  }
591              }
592          }
593  
594          Ok(peer_data)
595      }
596  }
597  
598  #[cfg(test)]
599  mod tests {
600      use std::collections::{HashMap, VecDeque};
601  
602      use fedimint_core::PeerId;
603      use rand::rngs::OsRng;
604      use threshold_crypto::{G1Projective, G2Projective};
605  
606      use crate::config::distributedgen::{
607          evaluate_polynomial_g2, scalar, Dkg, DkgGroup, DkgKeys, DkgStep, ThresholdKeys,
608      };
609  
610      #[test_log::test]
611      fn test_dkg() {
612          for (peer, keys) in run(G1Projective::generator()) {
613              let ThresholdKeys {
614                  public_key_set,
615                  secret_key_share,
616              } = keys.threshold_crypto();
617              assert_eq!(public_key_set.threshold(), 2);
618              assert_eq!(
619                  public_key_set.public_key_share(peer.to_usize()),
620                  secret_key_share.public_key_share()
621              );
622          }
623  
624          for (peer, keys) in run(G2Projective::generator()) {
625              let (pk, sk) = keys.tbs();
626              assert_eq!(pk.len(), 3);
627              assert_eq!(
628                  evaluate_polynomial_g2(&pk, &scalar(&peer)),
629                  sk.to_pub_key_share().0
630              );
631          }
632      }
633  
634      fn run<G: DkgGroup>(group: G) -> HashMap<PeerId, DkgKeys<G>> {
635          let mut rng = OsRng;
636          let num_peers = 4;
637          let threshold = 3;
638          let peers = (0..num_peers as u16).map(PeerId::from).collect::<Vec<_>>();
639  
640          let mut steps: VecDeque<(PeerId, DkgStep<G>)> = VecDeque::new();
641          let mut dkgs: HashMap<PeerId, Dkg<G>> = HashMap::new();
642          let mut keys: HashMap<PeerId, DkgKeys<G>> = HashMap::new();
643  
644          for peer in &peers {
645              let (dkg, step) = Dkg::new(group, *peer, peers.clone(), threshold, &mut rng);
646              dkgs.insert(*peer, dkg);
647              steps.push_back((*peer, step));
648          }
649  
650          while keys.len() < peers.len() {
651              match steps.pop_front() {
652                  Some((peer, DkgStep::Messages(messages))) => {
653                      for (receive_peer, msg) in messages {
654                          let receive_dkg = dkgs.get_mut(&receive_peer).unwrap();
655                          let step = receive_dkg.step(peer, msg);
656                          steps.push_back((receive_peer, step.unwrap()));
657                      }
658                  }
659                  Some((peer, DkgStep::Result(step_keys))) => {
660                      keys.insert(peer, step_keys);
661                  }
662                  _ => {}
663              }
664          }
665  
666          keys
667      }
668  }