sui_types/
committee.rs

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

sui_types/
committee.rs
