hotshot/traits/election/
randomized_committee.rs

1// Copyright (c) 2021-2024 Espresso Systems (espressosys.com)
2// This file is part of the HotShot repository.
3
4// You should have received a copy of the MIT License
5// along with the HotShot repository. If not, see <https://mit-license.org/>.
6
7use std::collections::{BTreeMap, BTreeSet};
8
9use alloy::primitives::U256;
10use hotshot_types::{
11    drb::{
12        election::{generate_stake_cdf, select_randomized_leader, RandomizedCommittee},
13        DrbResult,
14    },
15    stake_table::HSStakeTable,
16    traits::{
17        election::Membership,
18        node_implementation::NodeType,
19        signature_key::{SignatureKey, StakeTableEntryType},
20    },
21    PeerConfig,
22};
23use hotshot_utils::anytrace::*;
24
25#[derive(Clone, Debug)]
26
27/// The static committee election
28pub struct Committee<T: NodeType> {
29    /// The nodes on the committee and their stake
30    stake_table: HSStakeTable<T>,
31
32    /// The nodes on the committee and their stake
33    da_stake_table: HSStakeTable<T>,
34
35    /// Stake tables randomized with the DRB, used (only) for leader election
36    randomized_committee: RandomizedCommittee<<T::SignatureKey as SignatureKey>::StakeTableEntry>,
37
38    /// The nodes on the committee and their stake, indexed by public key
39    indexed_stake_table: BTreeMap<T::SignatureKey, PeerConfig<T>>,
40
41    /// The nodes on the committee and their stake, indexed by public key
42    indexed_da_stake_table: BTreeMap<T::SignatureKey, PeerConfig<T>>,
43
44    /// The first epoch which will be encountered. For testing, will panic if an epoch-carrying function is called
45    /// when first_epoch is None or is Some greater than that epoch.
46    first_epoch: Option<T::Epoch>,
47}
48
49impl<TYPES: NodeType> Membership<TYPES> for Committee<TYPES> {
50    type Error = hotshot_utils::anytrace::Error;
51    /// Create a new election
52    fn new(committee_members: Vec<PeerConfig<TYPES>>, da_members: Vec<PeerConfig<TYPES>>) -> Self {
53        // For each eligible leader, get the stake table entry
54        let eligible_leaders: Vec<PeerConfig<TYPES>> = committee_members
55            .iter()
56            .filter(|&member| member.stake_table_entry.stake() > U256::ZERO)
57            .cloned()
58            .collect();
59
60        // For each member, get the stake table entry
61        let members: Vec<PeerConfig<TYPES>> = committee_members
62            .iter()
63            .filter(|&member| member.stake_table_entry.stake() > U256::ZERO)
64            .cloned()
65            .collect();
66
67        // For each member, get the stake table entry
68        let da_members: Vec<PeerConfig<TYPES>> = da_members
69            .iter()
70            .filter(|&member| member.stake_table_entry.stake() > U256::ZERO)
71            .cloned()
72            .collect();
73
74        // Index the stake table by public key
75        let indexed_stake_table: BTreeMap<TYPES::SignatureKey, PeerConfig<TYPES>> = members
76            .iter()
77            .map(|config| {
78                (
79                    TYPES::SignatureKey::public_key(&config.stake_table_entry),
80                    config.clone(),
81                )
82            })
83            .collect();
84
85        // Index the stake table by public key
86        let indexed_da_stake_table: BTreeMap<TYPES::SignatureKey, PeerConfig<TYPES>> = da_members
87            .iter()
88            .map(|config| {
89                (
90                    TYPES::SignatureKey::public_key(&config.stake_table_entry),
91                    config.clone(),
92                )
93            })
94            .collect();
95
96        // We use a constant value of `[0u8; 32]` for the drb, since this is just meant to be used in tests
97        let randomized_committee = generate_stake_cdf(
98            eligible_leaders
99                .clone()
100                .into_iter()
101                .map(|leader| leader.stake_table_entry)
102                .collect::<Vec<_>>(),
103            [0u8; 32],
104        );
105
106        Self {
107            stake_table: members.into(),
108            da_stake_table: da_members.into(),
109            randomized_committee,
110            indexed_stake_table,
111            indexed_da_stake_table,
112            first_epoch: None,
113        }
114    }
115
116    /// Get the stake table for the current view
117    fn stake_table(&self, _epoch: Option<<TYPES as NodeType>::Epoch>) -> HSStakeTable<TYPES> {
118        self.stake_table.clone()
119    }
120
121    /// Get the stake table for the current view
122    fn da_stake_table(&self, _epoch: Option<<TYPES as NodeType>::Epoch>) -> HSStakeTable<TYPES> {
123        self.da_stake_table.clone()
124    }
125
126    /// Get all members of the committee for the current view
127    fn committee_members(
128        &self,
129        _view_number: <TYPES as NodeType>::View,
130        _epoch: Option<<TYPES as NodeType>::Epoch>,
131    ) -> BTreeSet<<TYPES as NodeType>::SignatureKey> {
132        self.stake_table
133            .iter()
134            .map(|x| TYPES::SignatureKey::public_key(&x.stake_table_entry))
135            .collect()
136    }
137
138    /// Get all members of the committee for the current view
139    fn da_committee_members(
140        &self,
141        _view_number: <TYPES as NodeType>::View,
142        _epoch: Option<<TYPES as NodeType>::Epoch>,
143    ) -> BTreeSet<<TYPES as NodeType>::SignatureKey> {
144        self.da_stake_table
145            .iter()
146            .map(|x| TYPES::SignatureKey::public_key(&x.stake_table_entry))
147            .collect()
148    }
149
150    /// Get the stake table entry for a public key
151    fn stake(
152        &self,
153        pub_key: &<TYPES as NodeType>::SignatureKey,
154        _epoch: Option<<TYPES as NodeType>::Epoch>,
155    ) -> Option<PeerConfig<TYPES>> {
156        // Only return the stake if it is above zero
157        self.indexed_stake_table.get(pub_key).cloned()
158    }
159
160    /// Get the stake table entry for a public key
161    fn da_stake(
162        &self,
163        pub_key: &<TYPES as NodeType>::SignatureKey,
164        _epoch: Option<<TYPES as NodeType>::Epoch>,
165    ) -> Option<PeerConfig<TYPES>> {
166        // Only return the stake if it is above zero
167        self.indexed_da_stake_table.get(pub_key).cloned()
168    }
169
170    /// Check if a node has stake in the committee
171    fn has_stake(
172        &self,
173        pub_key: &<TYPES as NodeType>::SignatureKey,
174        _epoch: Option<<TYPES as NodeType>::Epoch>,
175    ) -> bool {
176        self.indexed_stake_table
177            .get(pub_key)
178            .is_some_and(|x| x.stake_table_entry.stake() > U256::ZERO)
179    }
180
181    /// Check if a node has stake in the committee
182    fn has_da_stake(
183        &self,
184        pub_key: &<TYPES as NodeType>::SignatureKey,
185        _epoch: Option<<TYPES as NodeType>::Epoch>,
186    ) -> bool {
187        self.indexed_da_stake_table
188            .get(pub_key)
189            .is_some_and(|x| x.stake_table_entry.stake() > U256::ZERO)
190    }
191
192    /// Index the vector of public keys with the current view number
193    fn lookup_leader(
194        &self,
195        view_number: <TYPES as NodeType>::View,
196        _epoch: Option<<TYPES as NodeType>::Epoch>,
197    ) -> Result<TYPES::SignatureKey> {
198        let res = select_randomized_leader(&self.randomized_committee, *view_number);
199
200        Ok(TYPES::SignatureKey::public_key(&res))
201    }
202
203    /// Get the total number of nodes in the committee
204    fn total_nodes(&self, _epoch: Option<<TYPES as NodeType>::Epoch>) -> usize {
205        self.stake_table.len()
206    }
207    /// Get the total number of nodes in the committee
208    fn da_total_nodes(&self, _epoch: Option<<TYPES as NodeType>::Epoch>) -> usize {
209        self.da_stake_table.len()
210    }
211    /// Get the voting success threshold for the committee
212    fn success_threshold(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> U256 {
213        ((self.total_stake(epoch) * U256::from(2)) / U256::from(3)) + U256::from(1)
214    }
215
216    /// Get the voting success threshold for the committee
217    fn da_success_threshold(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> U256 {
218        ((self.total_da_stake(epoch) * U256::from(2)) / U256::from(3)) + U256::from(1)
219    }
220
221    /// Get the voting failure threshold for the committee
222    fn failure_threshold(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> U256 {
223        (self.total_stake(epoch) / U256::from(3)) + U256::from(1)
224    }
225
226    /// Get the voting upgrade threshold for the committee
227    fn upgrade_threshold(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> U256 {
228        let len = self.total_stake(epoch);
229
230        U256::max(
231            (len * U256::from(9)) / U256::from(10),
232            ((len * U256::from(2)) / U256::from(3)) + U256::from(1),
233        )
234    }
235
236    fn has_stake_table(&self, _epoch: TYPES::Epoch) -> bool {
237        true
238    }
239    fn has_randomized_stake_table(&self, _epoch: TYPES::Epoch) -> anyhow::Result<bool> {
240        Ok(true)
241    }
242
243    fn add_drb_result(&mut self, _epoch: <TYPES as NodeType>::Epoch, _drb_result: DrbResult) {}
244
245    fn set_first_epoch(&mut self, epoch: TYPES::Epoch, _initial_drb_result: DrbResult) {
246        self.first_epoch = Some(epoch);
247    }
248
249    fn first_epoch(&self) -> Option<TYPES::Epoch> {
250        self.first_epoch
251    }
252}
hotshot/traits/election/randomized_committee.rs

hotshot/traits/election/
randomized_committee.rs
