frost_dkg/
lib.rs

1/*
2    Copyright Michael Lodder. All Rights Reserved.
3    SPDX-License-Identifier: Apache-2.0
4*/
5//! The FROST Distributed Key Generation protocol.
6//!
7//! The full paper can be found [here](https://eprint.iacr.org/2020/852.pdf).
8
9#![cfg_attr(docsrs, feature(doc_cfg))]
10#![warn(
11    missing_docs,
12    missing_debug_implementations,
13    missing_copy_implementations,
14    trivial_casts,
15    trivial_numeric_casts,
16    unused,
17    clippy::mod_module_files
18)]
19#![deny(clippy::unwrap_used)]
20
21mod data;
22mod error;
23mod parameters;
24mod participant;
25mod traits;
26
27pub use data::*;
28pub use error::*;
29pub use parameters::*;
30pub use participant::*;
31pub use traits::*;
32
33pub use elliptic_curve;
34pub use elliptic_curve_tools;
35pub use rand_core;
36pub use vsss_rs;
37
38use elliptic_curve::{
39    Field, Group, PrimeField,
40    group::GroupEncoding,
41    subtle::{Choice, ConditionallySelectable},
42};
43use elliptic_curve_tools::SumOfProducts;
44use std::collections::BTreeSet;
45use vsss_rs::{IdentifierPrimeField, ParticipantIdGeneratorCollection, ShareVerifierGroup};
46
47/// Round 1 broadcast data used to publicly verify a DKG output.
48pub fn publicly_verify_dkg_results<G>(
49    round1_data: &[Round1Data<G>],
50    parameters: &Parameters<G>,
51    public_key: G,
52) -> DkgResult<()>
53where
54    G: SumOfProducts + GroupEncoding + Default + ConditionallySelectable,
55    G::Scalar: ScalarHash,
56{
57    // Perform the same checks as `Participant::receive_round1data`, then also
58    // check that the public key computed from the commitments matches.
59    if round1_data.len() < parameters.threshold {
60        return Err(Error::Pvss(format!(
61            "Not enough round 1 records. Expected at least {}, found {}",
62            parameters.threshold,
63            round1_data.len()
64        )));
65    }
66    if round1_data.len() > parameters.limit {
67        return Err(Error::Pvss(format!(
68            "Too many round 1 records. Expected at most {}, found {}",
69            parameters.limit,
70            round1_data.len()
71        )));
72    }
73
74    let all_participant_ids: Vec<IdentifierPrimeField<G::Scalar>> =
75        ParticipantIdGeneratorCollection::from(&parameters.participant_number_generators)
76            .iter()
77            .take(parameters.limit)
78            .collect();
79    if all_participant_ids.len() != parameters.limit {
80        return Err(Error::Pvss(format!(
81            "Participant ID generators produced {} identifiers, expected {}",
82            all_participant_ids.len(),
83            parameters.limit
84        )));
85    }
86
87    let mut computed_public_key = G::default();
88    let mut all_refresh = true;
89    let mut sender_ordinals = BTreeSet::new();
90
91    for (i, round1_data) in round1_data.iter().enumerate() {
92        if !sender_ordinals.insert(round1_data.sender_ordinal) {
93            return Err(Error::Pvss(format!(
94                "Data at {} duplicates sender ordinal {}",
95                i + 1,
96                round1_data.sender_ordinal
97            )));
98        }
99        let Some(id) = all_participant_ids.get(round1_data.sender_ordinal) else {
100            return Err(Error::Pvss(format!(
101                "Data at {} does not exist in the set of participants",
102                i + 1
103            )));
104        };
105        if *id != round1_data.sender_id {
106            return Err(Error::Pvss(format!(
107                "Data at {} does not match the expected sender ID",
108                i + 1
109            )));
110        }
111        if id.is_zero().into() {
112            return Err(Error::Pvss(format!(
113                "Data at {} contains an ID that is zero",
114                i + 1
115            )));
116        }
117        if round1_data.feldman_commitments.is_empty() {
118            return Err(Error::Pvss(format!(
119                "Data at {} has no Feldman commitments",
120                i + 1
121            )));
122        }
123        if round1_data.feldman_commitments.len() != parameters.threshold {
124            return Err(Error::Pvss(format!(
125                "Data at {} has commitments that do not match the expected threshold. Expected {}, found {}",
126                i + 1,
127                parameters.threshold,
128                round1_data.feldman_commitments.len()
129            )));
130        }
131        if round1_data.feldman_commitments[1..]
132            .iter()
133            .fold(Choice::from(0u8), |acc, c| acc | c.is_identity())
134            .into()
135        {
136            return Err(Error::Pvss(format!(
137                "Data at {} has a Feldman commitment that is the identity element, which is not allowed",
138                i + 1
139            )));
140        }
141
142        let feldman_valid = match round1_data.sender_type {
143            ParticipantType::Secret => {
144                SecretParticipantImpl::check_feldman_verifier(*round1_data.feldman_commitments[0])
145                    && round1_data.feldman_commitments[0].0 == round1_data.verifying_share
146            }
147            ParticipantType::Refresh => {
148                RefreshParticipantImpl::check_feldman_verifier(*round1_data.feldman_commitments[0])
149                    && round1_data.feldman_commitments[0].0 != round1_data.verifying_share
150            }
151        };
152
153        if !feldman_valid {
154            return Err(Error::Pvss(format!(
155                "Data at {} has an invalid Feldman commitment for its participant type",
156                i + 1
157            )));
158        }
159
160        verify_signature(
161            SchnorrContext {
162                ordinal: round1_data.sender_ordinal,
163                id: &round1_data.sender_id,
164                participant_type: &round1_data.sender_type,
165                threshold: parameters.threshold,
166                limit: parameters.limit,
167                message_generator: &parameters.message_generator,
168                feldman_verifiers: &round1_data.feldman_commitments,
169                verifying_share: &round1_data.verifying_share,
170                all_participant_ids: &all_participant_ids,
171            },
172            &round1_data.signature,
173        )
174        .map_err(|_e| Error::Pvss(format!("Data at {} failed signature verification", i + 1)))?;
175
176        all_refresh &= matches!(round1_data.sender_type, ParticipantType::Refresh);
177        computed_public_key += round1_data.feldman_commitments[0].0;
178    }
179
180    let public_key_identity = bool::from(computed_public_key.is_identity());
181    if all_refresh && !public_key_identity || !all_refresh && public_key_identity {
182        return Err(Error::Pvss(
183            "The computed public key is not valid for the given participants".to_string(),
184        ));
185    }
186
187    if computed_public_key != public_key {
188        return Err(Error::Pvss(format!(
189            "The public keys do not match: expected {}, computed {}",
190            hex::encode(public_key.to_bytes()),
191            hex::encode(computed_public_key.to_bytes())
192        )));
193    }
194
195    Ok(())
196}
197
198struct SchnorrContext<'a, G>
199where
200    G: Group + GroupEncoding + Default,
201{
202    ordinal: usize,
203    id: &'a IdentifierPrimeField<G::Scalar>,
204    participant_type: &'a ParticipantType,
205    threshold: usize,
206    limit: usize,
207    message_generator: &'a G,
208    feldman_verifiers: &'a [ShareVerifierGroup<G>],
209    verifying_share: &'a G,
210    all_participant_ids: &'a [IdentifierPrimeField<G::Scalar>],
211}
212
213pub(crate) fn verify_signature<G>(
214    context: SchnorrContext<'_, G>,
215    signature: &Signature<G>,
216) -> DkgResult<()>
217where
218    G: SumOfProducts + GroupEncoding + Default + ConditionallySelectable,
219    G::Scalar: ScalarHash,
220{
221    let bytes = bytes_for_schnorr(&context, &signature.r);
222    let challenge = G::Scalar::hash_to_scalar(&bytes);
223
224    let computed_r =
225        *context.message_generator * signature.s - *context.verifying_share * challenge;
226    if signature.r != computed_r {
227        return Err(Error::Round(format!(
228            "Round {}: received an invalid round 1 signature proof from ordinal '{}', ID '{:?}'",
229            Round::One,
230            context.ordinal,
231            context.id,
232        )));
233    }
234    Ok(())
235}
236
237pub(crate) fn bytes_for_schnorr<G>(context: &SchnorrContext<'_, G>, r_i: &G) -> Vec<u8>
238where
239    G: SumOfProducts + GroupEncoding + Default + ConditionallySelectable,
240    G::Scalar: ScalarHash,
241{
242    let mut bytes = Vec::with_capacity(512);
243    // ID
244    bytes.extend_from_slice(context.id.0.to_repr().as_ref());
245    // Add these values for domain separation to prevent replay attacks.
246    bytes.extend_from_slice(&(context.ordinal as u16).to_be_bytes());
247    bytes.extend_from_slice(&u16::from(*context.participant_type).to_be_bytes());
248    bytes.extend_from_slice(&(context.threshold as u16).to_be_bytes());
249    bytes.extend_from_slice(&(context.limit as u16).to_be_bytes());
250    bytes.extend_from_slice(context.message_generator.to_bytes().as_ref());
251    for id in context.all_participant_ids {
252        bytes.extend_from_slice(id.0.to_repr().as_ref());
253    }
254    // Add R_i.
255    bytes.extend_from_slice(r_i.to_bytes().as_ref());
256    // Add the verifying share.
257    bytes.extend_from_slice(context.verifying_share.to_bytes().as_ref());
258    // Add the verifiers.
259    for vf in context.feldman_verifiers {
260        bytes.extend_from_slice(vf.0.to_bytes().as_ref());
261    }
262    bytes
263}
264
265#[cfg(test)]
266mod tests {
267    use super::*;
268    use elliptic_curve::{Field, group::GroupEncoding, subtle::ConditionallySelectable};
269    use elliptic_curve_tools::SumOfProducts;
270    use rand_core::SeedableRng;
271    use serde::{Deserialize, Serialize};
272    use std::num::NonZeroUsize;
273    use vsss_rs::{
274        DefaultShare, IdentifierPrimeField, ParticipantIdGenerator, ReadableShareSet,
275        ValuePrimeField, shamir,
276    };
277
278    #[test]
279    fn works() {
280        const THRESHOLD: usize = 2;
281        const LIMIT: usize = 3;
282
283        let threshold = NonZeroUsize::new(THRESHOLD).expect("threshold is non-zero");
284        let limit = NonZeroUsize::new(LIMIT).expect("limit is non-zero");
285
286        let parameters =
287            Parameters::<k256::ProjectivePoint>::new(threshold, limit).expect("valid parameters");
288
289        let mut participants = (1..=3)
290            .map(|id| {
291                let id = IdentifierPrimeField(k256::Scalar::from(id as u64));
292                SecretParticipant::<k256::ProjectivePoint>::new_secret(id, &parameters)
293                    .expect("create secret participant")
294            })
295            .collect::<Vec<_>>();
296
297        for _ in [Round::One, Round::Two, Round::Three] {
298            let generators = next_round(&mut participants);
299            receive(&mut participants, generators);
300        }
301
302        let shares = participants
303            .iter()
304            .map(|p| p.secret_share().expect("participant has a secret share"))
305            .collect::<Vec<_>>();
306
307        let res = shares.combine();
308        assert!(res.is_ok());
309        let secret = res.expect("combine shares");
310
311        let expected_pk = k256::ProjectivePoint::GENERATOR * *secret;
312
313        assert_eq!(
314            participants[1]
315                .public_key()
316                .expect("participant has public key"),
317            expected_pk
318        );
319
320        let participant: Box<dyn AnyParticipant<k256::ProjectivePoint>> =
321            Box::new(participants.pop().expect("participant exists"));
322        let output = participant.into_output().expect("completed DKG output");
323        assert_eq!(output.public_key(), expected_pk);
324        assert_eq!(output.participant_ids().len(), LIMIT);
325        assert_eq!(output.feldman_verifiers().len(), THRESHOLD);
326        assert_eq!(*output.secret_share().identifier, k256::Scalar::from(3u64));
327        assert!(!format!("{output:?}").contains("secret_share"));
328    }
329
330    #[test]
331    fn public_verification_rejects_invalid_record_sets() {
332        const THRESHOLD: usize = 2;
333        const LIMIT: usize = 3;
334
335        let parameters = Parameters::<k256::ProjectivePoint>::new(
336            NonZeroUsize::new(THRESHOLD).expect("threshold is non-zero"),
337            NonZeroUsize::new(LIMIT).expect("limit is non-zero"),
338        )
339        .expect("valid parameters");
340        let mut participants = (1..=LIMIT)
341            .map(|id| {
342                SecretParticipant::<k256::ProjectivePoint>::new_secret(
343                    IdentifierPrimeField(k256::Scalar::from(id as u64)),
344                    &parameters,
345                )
346                .expect("create secret participant")
347            })
348            .collect::<Vec<_>>();
349
350        for _ in [Round::One, Round::Two, Round::Three] {
351            let generators = next_round(&mut participants);
352            receive(&mut participants, generators);
353        }
354
355        let round1_data = participants[0]
356            .received_round1_data()
357            .iter()
358            .flatten()
359            .cloned()
360            .collect::<Vec<_>>();
361        let public_key = participants[0]
362            .public_key()
363            .expect("participant has public key");
364        assert!(publicly_verify_dkg_results(&round1_data, &parameters, public_key).is_ok());
365
366        let threshold_records = &round1_data[..THRESHOLD];
367        let threshold_public_key = threshold_records
368            .iter()
369            .map(|data| data.feldman_commitments[0].0)
370            .sum();
371        assert!(
372            publicly_verify_dkg_results(threshold_records, &parameters, threshold_public_key)
373                .is_ok()
374        );
375
376        let too_few =
377            publicly_verify_dkg_results(&round1_data[..THRESHOLD - 1], &parameters, public_key);
378        assert!(matches!(too_few, Err(Error::Pvss(message)) if message.contains("Not enough")));
379
380        let duplicate_records = vec![round1_data[0].clone(), round1_data[0].clone()];
381        let duplicate = publicly_verify_dkg_results(&duplicate_records, &parameters, public_key);
382        assert!(
383            matches!(duplicate, Err(Error::Pvss(message)) if message.contains("duplicates sender ordinal"))
384        );
385
386        let mut empty_commitments = round1_data[..THRESHOLD].to_vec();
387        empty_commitments[0].feldman_commitments.clear();
388        let empty =
389            publicly_verify_dkg_results(&empty_commitments, &parameters, threshold_public_key);
390        assert!(
391            matches!(empty, Err(Error::Pvss(message)) if message.contains("no Feldman commitments"))
392        );
393
394        let mut too_many_records = round1_data.clone();
395        too_many_records.push(round1_data[0].clone());
396        let too_many = publicly_verify_dkg_results(&too_many_records, &parameters, public_key);
397        assert!(matches!(too_many, Err(Error::Pvss(message)) if message.contains("Too many")));
398    }
399
400    #[test]
401    fn advance_produces_opaque_transport_messages() {
402        const THRESHOLD: usize = 2;
403        const LIMIT: usize = 3;
404
405        let parameters = Parameters::<k256::ProjectivePoint>::new(
406            NonZeroUsize::new(THRESHOLD).expect("threshold is non-zero"),
407            NonZeroUsize::new(LIMIT).expect("limit is non-zero"),
408        )
409        .expect("valid parameters");
410        let mut participants = (1..=LIMIT)
411            .map(|id| {
412                SecretParticipant::<k256::ProjectivePoint>::new_secret(
413                    IdentifierPrimeField(k256::Scalar::from(id as u64)),
414                    &parameters,
415                )
416                .expect("create secret participant")
417            })
418            .collect::<Vec<_>>();
419
420        for round in [Round::One, Round::Two] {
421            let batches = participants
422                .iter_mut()
423                .map(
424                    |participant| match participant.advance().expect("advance participant") {
425                        AdvanceResult::Messages(messages) => messages,
426                        AdvanceResult::Complete => panic!("protocol completed too early"),
427                    },
428                )
429                .collect::<Vec<_>>();
430
431            for batch in batches {
432                match round {
433                    Round::One => {
434                        assert_eq!(batch.len(), 1);
435                        assert!(!batch.is_empty());
436                        assert!(matches!(
437                            batch.messages()[0].destination(),
438                            MessageDestination::Broadcast
439                        ));
440                    }
441                    Round::Two => {
442                        assert_eq!(batch.len(), LIMIT - 1);
443                        assert!((&batch).into_iter().all(|message| matches!(
444                            message.destination(),
445                            MessageDestination::Direct { .. }
446                        )));
447                    }
448                    _ => unreachable!("only messaging rounds are tested here"),
449                }
450
451                for output in batch.into_per_recipient() {
452                    let recipient = &mut participants[output.dst_ordinal];
453                    assert_eq!(recipient.id(), output.dst_id);
454                    recipient
455                        .receive(output.data.as_bytes())
456                        .expect("receive opaque protocol message");
457                }
458            }
459        }
460
461        for participant in &mut participants {
462            assert!(matches!(
463                participant.advance().expect("complete participant"),
464                AdvanceResult::Complete
465            ));
466        }
467        assert!(participants.iter().all(Participant::completed));
468    }
469
470    #[test]
471    fn recovery() {
472        type SecretShare =
473            DefaultShare<IdentifierPrimeField<k256::Scalar>, ValuePrimeField<k256::Scalar>>;
474        const THRESHOLD: usize = 2;
475        const LIMIT: usize = 3;
476
477        let threshold = NonZeroUsize::new(THRESHOLD).expect("threshold is non-zero");
478        let limit = NonZeroUsize::new(LIMIT).expect("limit is non-zero");
479        let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(0);
480
481        let original_secret = k256::Scalar::random(&mut rng);
482        let public_key = k256::ProjectivePoint::GENERATOR * original_secret;
483
484        let original_peer_ids = (1..=LIMIT)
485            .map(|_| IdentifierPrimeField(k256::Scalar::random(&mut rng)))
486            .collect::<Vec<_>>();
487        let original_peer_id_list = ParticipantIdGenerator::list(&original_peer_ids);
488        let original_shares = shamir::split_secret_with_participant_generators::<SecretShare>(
489            THRESHOLD,
490            LIMIT,
491            &IdentifierPrimeField(original_secret),
492            &mut rng,
493            &[original_peer_id_list],
494        )
495        .expect("split original secret");
496
497        let new_peer_ids = (1..=LIMIT)
498            .map(|_| IdentifierPrimeField(k256::Scalar::random(&mut rng)))
499            .collect::<Vec<_>>();
500
501        let parameters = Parameters::<k256::ProjectivePoint>::new(threshold, limit)
502            .expect("valid parameters")
503            .with_participant_number_generators(vec![ParticipantIdGenerator::list(&new_peer_ids)])
504            .expect("valid participant identifiers");
505        let mut participants = Vec::with_capacity(LIMIT);
506        for i in 0..LIMIT {
507            let participant = SecretParticipant::<k256::ProjectivePoint>::with_secret(
508                new_peer_ids[i],
509                &original_shares[i],
510                &parameters,
511                &ReconstructionSet::new(&original_peer_ids).expect("valid reconstruction set"),
512            )
513            .expect("create participant from existing share");
514            participants.push(participant);
515        }
516
517        for _ in [Round::One, Round::Two, Round::Three] {
518            let generators = next_round(&mut participants);
519            receive(&mut participants, generators);
520        }
521
522        let shares = participants
523            .iter()
524            .map(|p| p.secret_share().expect("participant has a secret share"))
525            .collect::<Vec<_>>();
526
527        let res = shares.combine();
528        assert!(res.is_ok());
529        let secret = res.expect("combine shares");
530
531        assert_eq!(secret.0, original_secret);
532        assert_eq!(
533            participants[1]
534                .public_key()
535                .expect("participant has public key"),
536            public_key
537        );
538    }
539
540    #[test]
541    fn secret_participants_resume_from_checkpoints_between_rounds() {
542        let parameters = test_parameters();
543        let mut participants = (1u64..=3)
544            .map(|id| {
545                SecretParticipant::<k256::ProjectivePoint>::new_secret(
546                    IdentifierPrimeField(k256::Scalar::from(id)),
547                    &parameters,
548                )
549                .expect("create secret participant")
550            })
551            .collect::<Vec<_>>();
552
553        run_with_checkpoints(&mut participants);
554
555        let public_key = participants[0]
556            .public_key()
557            .expect("participant has public key");
558        assert!(
559            participants
560                .iter()
561                .all(|participant| participant.public_key() == Some(public_key))
562        );
563    }
564
565    #[test]
566    fn refresh_participants_resume_from_checkpoints_between_rounds() {
567        let parameters = test_parameters();
568        let mut initial_participants = (1u64..=3)
569            .map(|id| {
570                SecretParticipant::<k256::ProjectivePoint>::new_secret(
571                    IdentifierPrimeField(k256::Scalar::from(id)),
572                    &parameters,
573                )
574                .expect("create secret participant")
575            })
576            .collect::<Vec<_>>();
577        run_with_checkpoints(&mut initial_participants);
578
579        let mut participants = initial_participants
580            .iter()
581            .map(|participant| {
582                RefreshParticipant::<k256::ProjectivePoint>::new_refresh(
583                    participant.id(),
584                    Some(
585                        &participant
586                            .secret_share()
587                            .expect("participant has a secret share"),
588                    ),
589                    &parameters,
590                )
591                .expect("create refresh participant")
592            })
593            .collect::<Vec<_>>();
594
595        run_with_checkpoints(&mut participants);
596
597        let refreshed_shares = participants
598            .iter()
599            .map(|participant| {
600                participant
601                    .secret_share()
602                    .expect("participant has a refreshed secret share")
603            })
604            .collect::<Vec<_>>();
605        let refreshed_secret = refreshed_shares
606            .combine()
607            .expect("combine refreshed shares");
608        assert_eq!(refreshed_secret.0.is_zero().unwrap_u8(), 1);
609        assert!(participants.iter().all(|participant| {
610            participant
611                .public_key()
612                .is_some_and(|public_key| bool::from(public_key.is_identity()))
613        }));
614    }
615
616    fn test_parameters() -> Parameters<'static, k256::ProjectivePoint> {
617        Parameters::new(
618            NonZeroUsize::new(2).expect("threshold is non-zero"),
619            NonZeroUsize::new(3).expect("limit is non-zero"),
620        )
621        .expect("valid parameters")
622    }
623
624    fn run_with_checkpoints<I>(participants: &mut [Participant<I, k256::ProjectivePoint>])
625    where
626        I: ParticipantImpl<k256::ProjectivePoint> + Default + Serialize + for<'de> Deserialize<'de>,
627    {
628        for _ in [Round::One, Round::Two, Round::Three] {
629            checkpoint_participants(participants);
630
631            let round_generators = participants
632                .iter_mut()
633                .map(|participant| participant.run().expect("run participant round"))
634                .collect::<Vec<_>>();
635            for round_generator in round_generators {
636                for output in round_generator.iter().expect("serialize round output") {
637                    participants[output.dst_ordinal]
638                        .receive(output.data.as_bytes())
639                        .expect("receive round output");
640                }
641            }
642
643            checkpoint_participants(participants);
644        }
645    }
646
647    fn checkpoint_participants<I>(participants: &mut [Participant<I, k256::ProjectivePoint>])
648    where
649        I: ParticipantImpl<k256::ProjectivePoint> + Default + Serialize + for<'de> Deserialize<'de>,
650    {
651        for participant in participants {
652            let encoded = postcard::to_stdvec(&*participant).expect("serialize participant state");
653            *participant = postcard::from_bytes(&encoded).expect("deserialize participant state");
654        }
655    }
656
657    fn next_round<G>(participants: &mut [SecretParticipant<G>]) -> Vec<RoundOutputGenerator<G>>
658    where
659        G: SumOfProducts + GroupEncoding + Default + ConditionallySelectable,
660        G::Scalar: ScalarHash,
661    {
662        let mut round_generators = Vec::with_capacity(participants.len());
663        for participant in participants {
664            let generator = participant.run().expect("run participant round");
665            round_generators.push(generator);
666        }
667        round_generators
668    }
669
670    fn receive<G>(
671        participants: &mut [SecretParticipant<G>],
672        round_generators: Vec<RoundOutputGenerator<G>>,
673    ) where
674        G: SumOfProducts + GroupEncoding + Default + ConditionallySelectable,
675        G::Scalar: ScalarHash,
676    {
677        for round_generator in &round_generators {
678            for ParticipantRoundOutput {
679                dst_ordinal: ordinal,
680                dst_id: id,
681                data,
682                ..
683            } in round_generator.iter().expect("serialize round output")
684            {
685                if let Some(participant) = participants.get_mut(ordinal) {
686                    assert_eq!(participant.ordinal, ordinal);
687                    assert_eq!(participant.id, id);
688                    let res = participant.receive(data.as_slice());
689                    assert!(res.is_ok());
690                }
691            }
692        }
693    }
694}
frost_dkg/lib.rs

frost_dkg/
lib.rs
