1use std::{
7 collections::{BTreeMap, BTreeSet, HashMap},
8 fmt::{Display, Formatter, Write},
9 hash::{Hash, Hasher},
10};
11
12use fastcrypto::traits::KeyPair;
13use iota_common::portable_random;
14use iota_multiaddr::Multiaddr;
15pub use iota_protocol_config::ProtocolVersion;
16use iota_sdk_types::{TransactionDigest, ValidatorCommitteeMember};
17use once_cell::sync::OnceCell;
18use rand::{
19 Rng, SeedableRng,
20 rngs::{ChaCha12Rng, ThreadRng},
21};
22use serde::{Deserialize, Serialize};
23
24use super::base_types::*;
25use crate::{
26 crypto::{
27 AggregateAuthorityPublicKey, AuthorityKeyPair, NetworkPublicKey,
28 random_committee_key_pairs_of_size,
29 },
30 error::{IotaError, IotaResult},
31 messages_checkpoint::{CertifiedCheckpointSummary, VerifiedCheckpoint},
32};
33
34pub type EpochId = u64;
35
36pub type StakeUnit = u64;
40
41pub type CommitteeDigest = [u8; 32];
42
43pub const TOTAL_VOTING_POWER: StakeUnit = 10_000;
53
54pub const QUORUM_THRESHOLD: StakeUnit = 6_667;
57
58pub const VALIDITY_THRESHOLD: StakeUnit = 3_334;
60
61#[derive(Clone, Debug, Serialize, Deserialize, Eq)]
62pub struct Committee {
63 pub epoch: EpochId,
64 pub voting_rights: Vec<(AuthorityName, StakeUnit)>,
65 expanded_keys: HashMap<AuthorityName, AggregateAuthorityPublicKey>,
66 index_map: HashMap<AuthorityName, usize>,
67}
68
69impl Committee {
70 pub fn new(epoch: EpochId, voting_rights: BTreeMap<AuthorityName, StakeUnit>) -> Self {
71 let mut voting_rights: Vec<(AuthorityName, StakeUnit)> =
72 voting_rights.iter().map(|(a, s)| (*a, *s)).collect();
73
74 assert!(!voting_rights.is_empty());
75 assert!(voting_rights.iter().any(|(_, s)| *s != 0));
76
77 voting_rights.sort_by_key(|(a, _)| *a);
78 let total_votes: StakeUnit = voting_rights.iter().map(|(_, votes)| *votes).sum();
79 assert_eq!(total_votes, TOTAL_VOTING_POWER);
80
81 let (expanded_keys, index_map) = Self::load_inner(&voting_rights);
82
83 Committee {
84 epoch,
85 voting_rights,
86 expanded_keys,
87 index_map,
88 }
89 }
90
91 pub fn from_committee_members(epoch: EpochId, members: &[ValidatorCommitteeMember]) -> Self {
94 Self::new(
95 epoch,
96 members
97 .iter()
98 .map(|member| (member.public_key.into(), member.stake))
99 .collect(),
100 )
101 }
102
103 pub fn committee_members(&self) -> Vec<ValidatorCommitteeMember> {
106 self.voting_rights
107 .iter()
108 .map(|(name, stake)| ValidatorCommitteeMember {
109 public_key: (*name).into(),
110 stake: *stake,
111 })
112 .collect()
113 }
114
115 pub fn new_for_testing_with_normalized_voting_power(
119 epoch: EpochId,
120 mut voting_weights: BTreeMap<AuthorityName, StakeUnit>,
121 ) -> Self {
122 let num_nodes = voting_weights.len();
123 let total_votes: StakeUnit = voting_weights.values().cloned().sum();
124
125 let normalization_coef = TOTAL_VOTING_POWER as f64 / total_votes as f64;
126 let mut total_sum = 0;
127 for (idx, (_auth, weight)) in voting_weights.iter_mut().enumerate() {
128 if idx < num_nodes - 1 {
129 *weight = (*weight as f64 * normalization_coef).floor() as u64; total_sum += *weight;
131 } else {
132 *weight = TOTAL_VOTING_POWER - total_sum;
134 }
135 }
136
137 Self::new(epoch, voting_weights)
138 }
139
140 pub fn load_inner(
142 voting_rights: &[(AuthorityName, StakeUnit)],
143 ) -> (
144 HashMap<AuthorityName, AggregateAuthorityPublicKey>,
145 HashMap<AuthorityName, usize>,
146 ) {
147 let expanded_keys: HashMap<AuthorityName, AggregateAuthorityPublicKey> = voting_rights
148 .iter()
149 .map(|(addr, _)| {
150 (
151 *addr,
152 (*addr)
153 .try_into()
154 .expect("Validator pubkey is always verified on-chain"),
155 )
156 })
157 .collect();
158
159 let index_map: HashMap<AuthorityName, usize> = voting_rights
160 .iter()
161 .enumerate()
162 .map(|(index, (addr, _))| (*addr, index))
163 .collect();
164 (expanded_keys, index_map)
165 }
166
167 pub fn authority_index(&self, author: &AuthorityName) -> Option<u32> {
175 self.index_map.get(author).map(|i| *i as u32)
176 }
177
178 pub fn authority_by_index(&self, index: u32) -> Option<&AuthorityName> {
179 self.voting_rights.get(index as usize).map(|(name, _)| name)
180 }
181
182 pub fn epoch(&self) -> EpochId {
183 self.epoch
184 }
185
186 pub fn public_key(
187 &self,
188 authority: &AuthorityName,
189 ) -> IotaResult<&AggregateAuthorityPublicKey> {
190 debug_assert_eq!(self.expanded_keys.len(), self.voting_rights.len());
191 match self.expanded_keys.get(authority) {
192 Some(v) => Ok(v),
193 None => Err(IotaError::InvalidCommittee(format!(
194 "Authority #{} not found, committee size {}",
195 authority,
196 self.expanded_keys.len()
197 ))),
198 }
199 }
200
201 pub fn sample(&self) -> &AuthorityName {
203 Self::choose_multiple_weighted(&self.voting_rights[..], 1, &mut ThreadRng::default())
205 .next()
206 .unwrap()
207 }
208
209 fn choose_multiple_weighted<'a>(
217 slice: &'a [(AuthorityName, StakeUnit)],
218 count: usize,
219 rng: &mut impl Rng,
220 ) -> impl Iterator<Item = &'a AuthorityName> {
221 portable_random::sample_weighted(rng, slice.len(), |i| slice[i].1 as f64, count)
222 .into_iter()
223 .map(|i| &slice[i].0)
224 }
225
226 pub fn choose_multiple_weighted_iter(
227 &self,
228 count: usize,
229 ) -> impl Iterator<Item = &AuthorityName> {
230 Self::choose_multiple_weighted(&self.voting_rights, count, &mut ThreadRng::default())
231 }
232
233 pub fn total_votes(&self) -> StakeUnit {
234 TOTAL_VOTING_POWER
235 }
236
237 pub fn quorum_threshold(&self) -> StakeUnit {
238 QUORUM_THRESHOLD
239 }
240
241 pub fn validity_threshold(&self) -> StakeUnit {
242 VALIDITY_THRESHOLD
243 }
244
245 pub fn threshold<const STRENGTH: bool>(&self) -> StakeUnit {
246 if STRENGTH {
247 QUORUM_THRESHOLD
248 } else {
249 VALIDITY_THRESHOLD
250 }
251 }
252
253 pub fn effective_threshold(&self, mut buffer_stake_bps: u64) -> StakeUnit {
262 if buffer_stake_bps > 10000 {
263 buffer_stake_bps = 10000;
264 }
265 let quorum_threshold = self.quorum_threshold();
266 let f = self.total_votes() - quorum_threshold;
267 let buffer_stake = (f * buffer_stake_bps).div_ceil(10000);
268 quorum_threshold + buffer_stake
269 }
270
271 pub fn num_members(&self) -> usize {
272 self.voting_rights.len()
273 }
274
275 pub fn members(&self) -> impl Iterator<Item = &(AuthorityName, StakeUnit)> {
276 self.voting_rights.iter()
277 }
278
279 pub fn names(&self) -> impl Iterator<Item = &AuthorityName> {
280 self.voting_rights.iter().map(|(name, _)| name)
281 }
282
283 pub fn stakes(&self) -> impl Iterator<Item = StakeUnit> + '_ {
284 self.voting_rights.iter().map(|(_, stake)| *stake)
285 }
286
287 pub fn stake_by_index(&self, index: u32) -> Option<StakeUnit> {
290 self.voting_rights
291 .get(index as usize)
292 .map(|(_, stake)| *stake)
293 }
294
295 pub fn authority_exists(&self, name: &AuthorityName) -> bool {
296 self.voting_rights
297 .binary_search_by_key(name, |(a, _)| *a)
298 .is_ok()
299 }
300
301 pub fn shuffle_by_stake_from_tx_digest(
304 &self,
305 tx_digest: &TransactionDigest,
306 ) -> Vec<AuthorityName> {
307 let digest_bytes = tx_digest.into_bytes();
308
309 let mut rng = ChaCha12Rng::from_seed(digest_bytes);
313 self.shuffle_by_stake_with_rng(None, None, &mut rng)
314 }
315
316 pub fn new_simple_test_committee_of_size(size: usize) -> (Self, Vec<AuthorityKeyPair>) {
319 let key_pairs: Vec<_> = random_committee_key_pairs_of_size(size)
320 .into_iter()
321 .collect();
322 let committee = Self::new_for_testing_with_normalized_voting_power(
323 0,
324 key_pairs
325 .iter()
326 .map(|key| {
327 (AuthorityName::from(key.public()), 1)
328 })
329 .collect(),
330 );
331 (committee, key_pairs)
332 }
333
334 pub fn new_simple_test_committee() -> (Self, Vec<AuthorityKeyPair>) {
337 Self::new_simple_test_committee_of_size(4)
338 }
339}
340
341impl CommitteeTrait<AuthorityName> for Committee {
342 fn shuffle_by_stake_with_rng(
343 &self,
344 preferences: Option<&BTreeSet<AuthorityName>>,
346 restrict_to: Option<&BTreeSet<AuthorityName>>,
348 rng: &mut impl Rng,
349 ) -> Vec<AuthorityName> {
350 let restricted = self
351 .voting_rights
352 .iter()
353 .filter(|(name, _)| {
354 if let Some(restrict_to) = restrict_to {
355 restrict_to.contains(name)
356 } else {
357 true
358 }
359 })
360 .cloned();
361
362 let (preferred, rest): (Vec<_>, Vec<_>) = if let Some(preferences) = preferences {
363 restricted.partition(|(name, _)| preferences.contains(name))
364 } else {
365 (Vec::new(), restricted.collect())
366 };
367
368 Self::choose_multiple_weighted(&preferred, preferred.len(), rng)
369 .chain(Self::choose_multiple_weighted(&rest, rest.len(), rng))
370 .cloned()
371 .collect()
372 }
373
374 fn weight(&self, author: &AuthorityName) -> StakeUnit {
375 match self.voting_rights.binary_search_by_key(author, |(a, _)| *a) {
376 Err(_) => 0,
377 Ok(idx) => self.voting_rights[idx].1,
378 }
379 }
380}
381
382impl PartialEq for Committee {
383 fn eq(&self, other: &Self) -> bool {
384 self.epoch == other.epoch && self.voting_rights == other.voting_rights
385 }
386}
387
388impl Hash for Committee {
389 fn hash<H: Hasher>(&self, state: &mut H) {
390 self.epoch.hash(state);
391 self.voting_rights.hash(state);
392 }
393}
394
395impl Display for Committee {
396 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
397 let mut voting_rights = String::new();
398 for (name, vote) in &self.voting_rights {
399 write!(voting_rights, "{}: {}, ", name.concise(), vote)?;
400 }
401 write!(
402 f,
403 "Committee (epoch={:?}, voting_rights=[{}])",
404 self.epoch, voting_rights
405 )
406 }
407}
408
409pub trait CommitteeTrait<K: Ord> {
410 fn shuffle_by_stake_with_rng(
411 &self,
412 preferences: Option<&BTreeSet<K>>,
414 restrict_to: Option<&BTreeSet<K>>,
416 rng: &mut impl Rng,
417 ) -> Vec<K>;
418
419 fn shuffle_by_stake(
420 &self,
421 preferences: Option<&BTreeSet<K>>,
423 restrict_to: Option<&BTreeSet<K>>,
425 ) -> Vec<K> {
426 self.shuffle_by_stake_with_rng(preferences, restrict_to, &mut ThreadRng::default())
427 }
428
429 fn weight(&self, author: &K) -> StakeUnit;
430}
431
432#[derive(Clone, Debug, Serialize, Deserialize)]
433pub struct NetworkMetadata {
434 pub network_address: Multiaddr,
435 pub primary_address: Multiaddr,
436 pub network_public_key: Option<NetworkPublicKey>,
437}
438
439#[derive(Clone, Debug, Serialize, Deserialize)]
440pub struct CommitteeWithNetworkMetadata {
441 epoch_id: EpochId,
442 validators: BTreeMap<AuthorityName, (StakeUnit, NetworkMetadata)>,
443
444 #[serde(skip)]
445 committee: OnceCell<Committee>,
446}
447
448impl CommitteeWithNetworkMetadata {
449 pub fn new(
450 epoch_id: EpochId,
451 validators: BTreeMap<AuthorityName, (StakeUnit, NetworkMetadata)>,
452 ) -> Self {
453 Self {
454 epoch_id,
455 validators,
456 committee: OnceCell::new(),
457 }
458 }
459 pub fn epoch(&self) -> EpochId {
460 self.epoch_id
461 }
462
463 pub fn validators(&self) -> &BTreeMap<AuthorityName, (StakeUnit, NetworkMetadata)> {
464 &self.validators
465 }
466
467 pub fn committee(&self) -> &Committee {
468 self.committee.get_or_init(|| {
469 Committee::new(
470 self.epoch_id,
471 self.validators
472 .iter()
473 .map(|(name, (stake, _))| (*name, *stake))
474 .collect(),
475 )
476 })
477 }
478}
479
480impl Display for CommitteeWithNetworkMetadata {
481 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
482 write!(
483 f,
484 "CommitteeWithNetworkMetadata (epoch={}, validators={:?})",
485 self.epoch_id, self.validators
486 )
487 }
488}
489
490#[derive(Debug)]
504pub struct CommitteeChainVerifier {
505 committee: Committee,
506}
507
508impl CommitteeChainVerifier {
509 pub fn new(trusted_committee: Committee) -> Self {
512 Self {
513 committee: trusted_committee,
514 }
515 }
516
517 pub fn epoch(&self) -> EpochId {
519 self.committee.epoch
520 }
521
522 pub fn committee(&self) -> &Committee {
524 &self.committee
525 }
526
527 pub fn verify_epoch_close(
536 &mut self,
537 summary: CertifiedCheckpointSummary,
538 ) -> IotaResult<VerifiedCheckpoint> {
539 if summary.data().epoch != self.committee.epoch {
543 return Err(IotaError::WrongEpoch {
544 expected_epoch: self.committee.epoch,
545 actual_epoch: summary.data().epoch,
546 });
547 }
548
549 if summary.data().end_of_epoch_data.is_none() {
550 return Err(IotaError::GenericAuthority {
551 error: format!(
552 "checkpoint {} is not the closing checkpoint of epoch {} (no \
553 end-of-epoch data)",
554 summary.data().sequence_number,
555 self.committee.epoch,
556 ),
557 });
558 }
559
560 let verified = summary.try_into_verified(&self.committee)?;
561 let end_of_epoch_data = verified
562 .end_of_epoch_data
563 .as_ref()
564 .expect("checked before verification");
565
566 self.committee = Committee::from_committee_members(
567 self.committee
568 .epoch
569 .checked_add(1)
570 .ok_or(IotaError::AdvanceEpoch {
571 error: "epoch number overflow".to_string(),
572 })?,
573 &end_of_epoch_data.next_epoch_committee,
574 );
575 Ok(verified)
576 }
577}
578
579#[cfg(test)]
580mod test {
581 use fastcrypto::traits::KeyPair;
582 use iota_sdk_types::{CheckpointSummary, EndOfEpochData};
583
584 use super::*;
585 use crate::{
586 crypto::{AuthorityKeyPair, get_key_pair},
587 messages_checkpoint::SignedCheckpointSummary,
588 utils::make_committee_key,
589 };
590
591 const RNG_SEED: [u8; 32] = [
592 21, 23, 199, 200, 234, 250, 252, 178, 94, 15, 202, 178, 62, 186, 88, 137, 233, 192, 130,
593 157, 179, 179, 65, 9, 31, 249, 221, 123, 225, 112, 199, 247,
594 ];
595
596 #[test]
597 fn test_shuffle_by_weight() {
598 let (_, sec1): (_, AuthorityKeyPair) = get_key_pair();
599 let (_, sec2): (_, AuthorityKeyPair) = get_key_pair();
600 let (_, sec3): (_, AuthorityKeyPair) = get_key_pair();
601 let a1: AuthorityName = sec1.public().into();
602 let a2: AuthorityName = sec2.public().into();
603 let a3: AuthorityName = sec3.public().into();
604
605 let mut authorities = BTreeMap::new();
606 authorities.insert(a1, 1);
607 authorities.insert(a2, 1);
608 authorities.insert(a3, 1);
609
610 let committee = Committee::new_for_testing_with_normalized_voting_power(0, authorities);
611
612 assert_eq!(committee.shuffle_by_stake(None, None).len(), 3);
613
614 let mut pref = BTreeSet::new();
615 pref.insert(a2);
616
617 for _ in 0..100 {
619 assert_eq!(
620 a2,
621 *committee
622 .shuffle_by_stake(Some(&pref), None)
623 .first()
624 .unwrap()
625 );
626 }
627
628 let mut restrict = BTreeSet::new();
629 restrict.insert(a2);
630
631 for _ in 0..100 {
632 let res = committee.shuffle_by_stake(None, Some(&restrict));
633 assert_eq!(1, res.len());
634 assert_eq!(a2, res[0]);
635 }
636
637 let res = committee.shuffle_by_stake(Some(&BTreeSet::new()), None);
639 assert_eq!(3, res.len());
640
641 let res = committee.shuffle_by_stake(None, Some(&BTreeSet::new()));
642 assert_eq!(0, res.len());
643 }
644
645 #[test]
650 fn committee_chain_verifier_walks_and_rejects() {
651 let mut rng = rand::rngs::StdRng::from_seed(RNG_SEED);
652 let (keys, committee) = make_committee_key(&mut rng);
653 let (other_keys, other_committee) = make_committee_key(&mut rng);
654
655 let close_of_epoch = |epoch: EpochId, end_of_epoch_data: Option<EndOfEpochData>| {
656 let summary = CheckpointSummary {
657 epoch,
658 sequence_number: epoch,
659 network_total_transactions: 0,
660 contents_digest: Default::default(),
661 previous_digest: None,
662 epoch_rolling_gas_cost_summary: Default::default(),
663 end_of_epoch_data,
664 timestamp_ms: 0,
665 version_specific_data: Vec::new(),
666 checkpoint_commitments: Vec::new(),
667 };
668 let signatures = keys
669 .iter()
670 .map(|k| SignedCheckpointSummary::sign(epoch, &summary, k, k.public().into()))
671 .collect();
672 let committee_at_epoch =
673 Committee::new(epoch, committee.voting_rights.iter().cloned().collect());
674 CertifiedCheckpointSummary::new(summary, signatures, &committee_at_epoch)
675 .expect("test summary must certify")
676 };
677 let handing_forward = Some(EndOfEpochData {
678 next_epoch_committee: committee.committee_members(),
679 next_epoch_protocol_version: 1,
680 epoch_commitments: Vec::new(),
681 epoch_supply_change: 0,
682 });
683
684 let mut verifier = CommitteeChainVerifier::new(committee.clone());
685
686 assert!(matches!(
688 verifier.verify_epoch_close(close_of_epoch(1, handing_forward.clone())),
689 Err(IotaError::WrongEpoch { .. })
690 ));
691 assert_eq!(verifier.epoch(), 0, "a rejected summary must not advance");
692
693 verifier
695 .verify_epoch_close(close_of_epoch(0, None))
696 .expect_err("a non-closing checkpoint must be rejected");
697 assert_eq!(verifier.epoch(), 0);
698
699 let foreign_non_closing = {
703 let summary = CheckpointSummary {
704 epoch: 0,
705 sequence_number: 0,
706 network_total_transactions: 0,
707 contents_digest: Default::default(),
708 previous_digest: None,
709 epoch_rolling_gas_cost_summary: Default::default(),
710 end_of_epoch_data: None,
711 timestamp_ms: 0,
712 version_specific_data: Vec::new(),
713 checkpoint_commitments: Vec::new(),
714 };
715 let signatures = other_keys
716 .iter()
717 .map(|k| SignedCheckpointSummary::sign(0, &summary, k, k.public().into()))
718 .collect();
719 CertifiedCheckpointSummary::new(summary, signatures, &other_committee)
720 .expect("certifies under the foreign committee")
721 };
722 assert!(matches!(
723 verifier.verify_epoch_close(foreign_non_closing),
724 Err(IotaError::GenericAuthority { .. })
725 ));
726 assert_eq!(verifier.epoch(), 0);
727
728 verifier
730 .verify_epoch_close(close_of_epoch(0, handing_forward.clone()))
731 .expect("epoch 0 close must verify");
732 assert_eq!(verifier.epoch(), 1);
733 verifier
734 .verify_epoch_close(close_of_epoch(1, handing_forward.clone()))
735 .expect("epoch 1 close must verify");
736 assert_eq!(verifier.epoch(), 2);
737
738 let mut wrong_root = CommitteeChainVerifier::new(other_committee);
740 wrong_root
741 .verify_epoch_close(close_of_epoch(0, handing_forward))
742 .expect_err("a chain signed by a different committee must be rejected");
743 assert_eq!(wrong_root.epoch(), 0);
744 }
745}