iota_types/
committee.rs

1// Copyright (c) 2021, Facebook, Inc. and its affiliates
2// Copyright (c) Mysten Labs, Inc.
3// Modifications Copyright (c) 2024 IOTA Stiftung
4// SPDX-License-Identifier: Apache-2.0
5
6use std::{
7    collections::{BTreeMap, BTreeSet, HashMap},
8    fmt::{Display, Formatter, Write},
9    hash::{Hash, Hasher},
10};
11
12use fastcrypto::traits::KeyPair;
13pub use iota_protocol_config::ProtocolVersion;
14use once_cell::sync::OnceCell;
15use rand::{
16    Rng, SeedableRng,
17    rngs::{StdRng, ThreadRng},
18    seq::SliceRandom,
19};
20use serde::{Deserialize, Serialize};
21
22use super::base_types::*;
23use crate::{
24    crypto::{AuthorityKeyPair, AuthorityPublicKey, random_committee_key_pairs_of_size},
25    error::{IotaError, IotaResult},
26    multiaddr::Multiaddr,
27};
28
29pub type EpochId = u64;
30
31// TODO: the stake and voting power of a validator can be different so
32// in some places when we are actually referring to the voting power, we
33// should use a different type alias, field name, etc.
34pub type StakeUnit = u64;
35
36pub type CommitteeDigest = [u8; 32];
37
38// The voting power, quorum threshold and max voting power are defined in the
39// `voting_power.move` module. We're following the very same convention in the
40// validator binaries.
41
42/// Set total_voting_power as 10_000 by convention. Individual voting powers can
43/// be interpreted as easily understandable basis points (e.g., voting_power:
44/// 100 = 1%, voting_power: 1 = 0.01%). Fixing the total voting power allows
45/// clients to hardcode the quorum threshold and total_voting power rather
46/// than recomputing these.
47pub const TOTAL_VOTING_POWER: StakeUnit = 10_000;
48
49/// Quorum threshold for our fixed voting power--any message signed by this much
50/// voting power can be trusted up to BFT assumptions
51pub const QUORUM_THRESHOLD: StakeUnit = 6_667;
52
53/// Validity threshold defined by f+1
54pub const VALIDITY_THRESHOLD: StakeUnit = 3_334;
55
56#[derive(Clone, Debug, Serialize, Deserialize, Eq)]
57pub struct Committee {
58    pub epoch: EpochId,
59    pub voting_rights: Vec<(AuthorityName, StakeUnit)>,
60    expanded_keys: HashMap<AuthorityName, AuthorityPublicKey>,
61    index_map: HashMap<AuthorityName, usize>,
62}
63
64impl Committee {
65    pub fn new(epoch: EpochId, voting_rights: BTreeMap<AuthorityName, StakeUnit>) -> Self {
66        let mut voting_rights: Vec<(AuthorityName, StakeUnit)> =
67            voting_rights.iter().map(|(a, s)| (*a, *s)).collect();
68
69        assert!(!voting_rights.is_empty());
70        assert!(voting_rights.iter().any(|(_, s)| *s != 0));
71
72        voting_rights.sort_by_key(|(a, _)| *a);
73        let total_votes: StakeUnit = voting_rights.iter().map(|(_, votes)| *votes).sum();
74        assert_eq!(total_votes, TOTAL_VOTING_POWER);
75
76        let (expanded_keys, index_map) = Self::load_inner(&voting_rights);
77
78        Committee {
79            epoch,
80            voting_rights,
81            expanded_keys,
82            index_map,
83        }
84    }
85
86    /// Normalize the given weights to TOTAL_VOTING_POWER and create the
87    /// committee. Used for testing only: a production system is using the
88    /// voting weights of the Iota System object.
89    pub fn new_for_testing_with_normalized_voting_power(
90        epoch: EpochId,
91        mut voting_weights: BTreeMap<AuthorityName, StakeUnit>,
92    ) -> Self {
93        let num_nodes = voting_weights.len();
94        let total_votes: StakeUnit = voting_weights.values().cloned().sum();
95
96        let normalization_coef = TOTAL_VOTING_POWER as f64 / total_votes as f64;
97        let mut total_sum = 0;
98        for (idx, (_auth, weight)) in voting_weights.iter_mut().enumerate() {
99            if idx < num_nodes - 1 {
100                *weight = (*weight as f64 * normalization_coef).floor() as u64; // adjust the weights following the normalization coef
101                total_sum += *weight;
102            } else {
103                // the last element is taking all the rest
104                *weight = TOTAL_VOTING_POWER - total_sum;
105            }
106        }
107
108        Self::new(epoch, voting_weights)
109    }
110
111    // We call this if these have not yet been computed
112    pub fn load_inner(
113        voting_rights: &[(AuthorityName, StakeUnit)],
114    ) -> (
115        HashMap<AuthorityName, AuthorityPublicKey>,
116        HashMap<AuthorityName, usize>,
117    ) {
118        let expanded_keys: HashMap<AuthorityName, AuthorityPublicKey> = voting_rights
119            .iter()
120            .map(|(addr, _)| {
121                (
122                    *addr,
123                    (*addr)
124                        .try_into()
125                        .expect("Validator pubkey is always verified on-chain"),
126                )
127            })
128            .collect();
129
130        let index_map: HashMap<AuthorityName, usize> = voting_rights
131            .iter()
132            .enumerate()
133            .map(|(index, (addr, _))| (*addr, index))
134            .collect();
135        (expanded_keys, index_map)
136    }
137
138    pub fn authority_index(&self, author: &AuthorityName) -> Option<u32> {
139        self.index_map.get(author).map(|i| *i as u32)
140    }
141
142    pub fn authority_by_index(&self, index: u32) -> Option<&AuthorityName> {
143        self.voting_rights.get(index as usize).map(|(name, _)| name)
144    }
145
146    pub fn epoch(&self) -> EpochId {
147        self.epoch
148    }
149
150    pub fn public_key(&self, authority: &AuthorityName) -> IotaResult<&AuthorityPublicKey> {
151        debug_assert_eq!(self.expanded_keys.len(), self.voting_rights.len());
152        match self.expanded_keys.get(authority) {
153            Some(v) => Ok(v),
154            None => Err(IotaError::InvalidCommittee(format!(
155                "Authority #{} not found, committee size {}",
156                authority,
157                self.expanded_keys.len()
158            ))),
159        }
160    }
161
162    /// Samples authorities by weight
163    pub fn sample(&self) -> &AuthorityName {
164        // unwrap safe unless committee is empty
165        Self::choose_multiple_weighted(&self.voting_rights[..], 1, &mut ThreadRng::default())
166            .next()
167            .unwrap()
168    }
169
170    fn choose_multiple_weighted<'a>(
171        slice: &'a [(AuthorityName, StakeUnit)],
172        count: usize,
173        rng: &mut impl Rng,
174    ) -> impl Iterator<Item = &'a AuthorityName> {
175        // unwrap is safe because we validate the committee composition in `new` above.
176        // See https://docs.rs/rand/latest/rand/distributions/weighted/enum.WeightedError.html
177        // for possible errors.
178        slice
179            .choose_multiple_weighted(rng, count, |(_, weight)| *weight as f64)
180            .unwrap()
181            .map(|(a, _)| a)
182    }
183
184    pub fn choose_multiple_weighted_iter(
185        &self,
186        count: usize,
187    ) -> impl Iterator<Item = &AuthorityName> {
188        self.voting_rights
189            .choose_multiple_weighted(&mut ThreadRng::default(), count, |(_, weight)| {
190                *weight as f64
191            })
192            .unwrap()
193            .map(|(a, _)| a)
194    }
195
196    pub fn total_votes(&self) -> StakeUnit {
197        TOTAL_VOTING_POWER
198    }
199
200    pub fn quorum_threshold(&self) -> StakeUnit {
201        QUORUM_THRESHOLD
202    }
203
204    pub fn validity_threshold(&self) -> StakeUnit {
205        VALIDITY_THRESHOLD
206    }
207
208    pub fn threshold<const STRENGTH: bool>(&self) -> StakeUnit {
209        if STRENGTH {
210            QUORUM_THRESHOLD
211        } else {
212            VALIDITY_THRESHOLD
213        }
214    }
215
216    pub fn num_members(&self) -> usize {
217        self.voting_rights.len()
218    }
219
220    pub fn members(&self) -> impl Iterator<Item = &(AuthorityName, StakeUnit)> {
221        self.voting_rights.iter()
222    }
223
224    pub fn names(&self) -> impl Iterator<Item = &AuthorityName> {
225        self.voting_rights.iter().map(|(name, _)| name)
226    }
227
228    pub fn stakes(&self) -> impl Iterator<Item = StakeUnit> + '_ {
229        self.voting_rights.iter().map(|(_, stake)| *stake)
230    }
231
232    pub fn authority_exists(&self, name: &AuthorityName) -> bool {
233        self.voting_rights
234            .binary_search_by_key(name, |(a, _)| *a)
235            .is_ok()
236    }
237
238    /// Derive a seed deterministically from the transaction digest and shuffle
239    /// the validators.
240    pub fn shuffle_by_stake_from_tx_digest(
241        &self,
242        tx_digest: &TransactionDigest,
243    ) -> Vec<AuthorityName> {
244        // the 32 is as requirement of the default StdRng::from_seed choice
245        let digest_bytes = tx_digest.into_inner();
246
247        // permute the validators deterministically, based on the digest
248        let mut rng = StdRng::from_seed(digest_bytes);
249        self.shuffle_by_stake_with_rng(None, None, &mut rng)
250    }
251
252    // ===== Testing-only methods =====
253    //
254    pub fn new_simple_test_committee_of_size(size: usize) -> (Self, Vec<AuthorityKeyPair>) {
255        let key_pairs: Vec<_> = random_committee_key_pairs_of_size(size)
256            .into_iter()
257            .collect();
258        let committee = Self::new_for_testing_with_normalized_voting_power(
259            0,
260            key_pairs
261                .iter()
262                .map(|key| {
263                    (AuthorityName::from(key.public()), /* voting right */ 1)
264                })
265                .collect(),
266        );
267        (committee, key_pairs)
268    }
269
270    /// Generate a simple committee with 4 validators each with equal voting
271    /// stake of 1.
272    pub fn new_simple_test_committee() -> (Self, Vec<AuthorityKeyPair>) {
273        Self::new_simple_test_committee_of_size(4)
274    }
275}
276
277impl CommitteeTrait<AuthorityName> for Committee {
278    fn shuffle_by_stake_with_rng(
279        &self,
280        // try these authorities first
281        preferences: Option<&BTreeSet<AuthorityName>>,
282        // only attempt from these authorities.
283        restrict_to: Option<&BTreeSet<AuthorityName>>,
284        rng: &mut impl Rng,
285    ) -> Vec<AuthorityName> {
286        let restricted = self
287            .voting_rights
288            .iter()
289            .filter(|(name, _)| {
290                if let Some(restrict_to) = restrict_to {
291                    restrict_to.contains(name)
292                } else {
293                    true
294                }
295            })
296            .cloned();
297
298        let (preferred, rest): (Vec<_>, Vec<_>) = if let Some(preferences) = preferences {
299            restricted.partition(|(name, _)| preferences.contains(name))
300        } else {
301            (Vec::new(), restricted.collect())
302        };
303
304        Self::choose_multiple_weighted(&preferred, preferred.len(), rng)
305            .chain(Self::choose_multiple_weighted(&rest, rest.len(), rng))
306            .cloned()
307            .collect()
308    }
309
310    fn weight(&self, author: &AuthorityName) -> StakeUnit {
311        match self.voting_rights.binary_search_by_key(author, |(a, _)| *a) {
312            Err(_) => 0,
313            Ok(idx) => self.voting_rights[idx].1,
314        }
315    }
316}
317
318impl PartialEq for Committee {
319    fn eq(&self, other: &Self) -> bool {
320        self.epoch == other.epoch && self.voting_rights == other.voting_rights
321    }
322}
323
324impl Hash for Committee {
325    fn hash<H: Hasher>(&self, state: &mut H) {
326        self.epoch.hash(state);
327        self.voting_rights.hash(state);
328    }
329}
330
331impl Display for Committee {
332    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
333        let mut voting_rights = String::new();
334        for (name, vote) in &self.voting_rights {
335            write!(voting_rights, "{}: {}, ", name.concise(), vote)?;
336        }
337        write!(
338            f,
339            "Committee (epoch={:?}, voting_rights=[{}])",
340            self.epoch, voting_rights
341        )
342    }
343}
344
345pub trait CommitteeTrait<K: Ord> {
346    fn shuffle_by_stake_with_rng(
347        &self,
348        // try these authorities first
349        preferences: Option<&BTreeSet<K>>,
350        // only attempt from these authorities.
351        restrict_to: Option<&BTreeSet<K>>,
352        rng: &mut impl Rng,
353    ) -> Vec<K>;
354
355    fn shuffle_by_stake(
356        &self,
357        // try these authorities first
358        preferences: Option<&BTreeSet<K>>,
359        // only attempt from these authorities.
360        restrict_to: Option<&BTreeSet<K>>,
361    ) -> Vec<K> {
362        self.shuffle_by_stake_with_rng(preferences, restrict_to, &mut ThreadRng::default())
363    }
364
365    fn weight(&self, author: &K) -> StakeUnit;
366}
367
368#[derive(Clone, Debug, Serialize, Deserialize)]
369pub struct NetworkMetadata {
370    pub network_address: Multiaddr,
371    pub primary_address: Multiaddr,
372}
373
374#[derive(Clone, Debug, Serialize, Deserialize)]
375pub struct CommitteeWithNetworkMetadata {
376    epoch_id: EpochId,
377    validators: BTreeMap<AuthorityName, (StakeUnit, NetworkMetadata)>,
378
379    #[serde(skip)]
380    committee: OnceCell<Committee>,
381}
382
383impl CommitteeWithNetworkMetadata {
384    pub fn new(
385        epoch_id: EpochId,
386        validators: BTreeMap<AuthorityName, (StakeUnit, NetworkMetadata)>,
387    ) -> Self {
388        Self {
389            epoch_id,
390            validators,
391            committee: OnceCell::new(),
392        }
393    }
394    pub fn epoch(&self) -> EpochId {
395        self.epoch_id
396    }
397
398    pub fn validators(&self) -> &BTreeMap<AuthorityName, (StakeUnit, NetworkMetadata)> {
399        &self.validators
400    }
401
402    pub fn committee(&self) -> &Committee {
403        self.committee.get_or_init(|| {
404            Committee::new(
405                self.epoch_id,
406                self.validators
407                    .iter()
408                    .map(|(name, (stake, _))| (*name, *stake))
409                    .collect(),
410            )
411        })
412    }
413}
414
415impl Display for CommitteeWithNetworkMetadata {
416    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
417        write!(
418            f,
419            "CommitteeWithNetworkMetadata (epoch={}, validators={:?})",
420            self.epoch_id, self.validators
421        )
422    }
423}
424
425#[cfg(test)]
426mod test {
427    use fastcrypto::traits::KeyPair;
428
429    use super::*;
430    use crate::crypto::{AuthorityKeyPair, get_key_pair};
431
432    #[test]
433    fn test_shuffle_by_weight() {
434        let (_, sec1): (_, AuthorityKeyPair) = get_key_pair();
435        let (_, sec2): (_, AuthorityKeyPair) = get_key_pair();
436        let (_, sec3): (_, AuthorityKeyPair) = get_key_pair();
437        let a1: AuthorityName = sec1.public().into();
438        let a2: AuthorityName = sec2.public().into();
439        let a3: AuthorityName = sec3.public().into();
440
441        let mut authorities = BTreeMap::new();
442        authorities.insert(a1, 1);
443        authorities.insert(a2, 1);
444        authorities.insert(a3, 1);
445
446        let committee = Committee::new_for_testing_with_normalized_voting_power(0, authorities);
447
448        assert_eq!(committee.shuffle_by_stake(None, None).len(), 3);
449
450        let mut pref = BTreeSet::new();
451        pref.insert(a2);
452
453        // preference always comes first
454        for _ in 0..100 {
455            assert_eq!(
456                a2,
457                *committee
458                    .shuffle_by_stake(Some(&pref), None)
459                    .first()
460                    .unwrap()
461            );
462        }
463
464        let mut restrict = BTreeSet::new();
465        restrict.insert(a2);
466
467        for _ in 0..100 {
468            let res = committee.shuffle_by_stake(None, Some(&restrict));
469            assert_eq!(1, res.len());
470            assert_eq!(a2, res[0]);
471        }
472
473        // empty preferences are valid
474        let res = committee.shuffle_by_stake(Some(&BTreeSet::new()), None);
475        assert_eq!(3, res.len());
476
477        let res = committee.shuffle_by_stake(None, Some(&BTreeSet::new()));
478        assert_eq!(0, res.len());
479    }
480}
iota_types/committee.rs

iota_types/
committee.rs
