hotshot/traits/election/
two_static_committees.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::{
8    cmp::max,
9    collections::{BTreeMap, BTreeSet},
10};
11
12use alloy::primitives::U256;
13use hotshot_types::{
14    drb::DrbResult,
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::Result;
24
25/// Tuple type for eligible leaders
26type EligibleLeaders<T> = (Vec<PeerConfig<T>>, Vec<PeerConfig<T>>);
27
28/// Tuple type for stake tables
29type StakeTables<T> = (HSStakeTable<T>, HSStakeTable<T>);
30
31/// Tuple type for indexed stake tables
32type IndexedStakeTables<T> = (
33    BTreeMap<<T as NodeType>::SignatureKey, PeerConfig<T>>,
34    BTreeMap<<T as NodeType>::SignatureKey, PeerConfig<T>>,
35);
36
37#[derive(Clone, Debug, Eq, PartialEq, Hash)]
38/// The static committee election
39pub struct TwoStaticCommittees<T: NodeType> {
40    /// The nodes eligible for leadership.
41    /// NOTE: This is currently a hack because the DA leader needs to be the quorum
42    /// leader but without voting rights.
43    eligible_leaders: EligibleLeaders<T>,
44
45    /// The nodes on the committee and their stake
46    stake_table: StakeTables<T>,
47
48    /// The nodes on the committee and their stake
49    da_stake_table: StakeTables<T>,
50
51    /// The nodes on the committee and their stake, indexed by public key
52    indexed_stake_table: IndexedStakeTables<T>,
53
54    /// The nodes on the committee and their stake, indexed by public key
55    indexed_da_stake_table: IndexedStakeTables<T>,
56
57    /// The first epoch which will be encountered. For testing, will panic if an epoch-carrying function is called
58    /// when first_epoch is None or is Some greater than that epoch.
59    first_epoch: Option<T::Epoch>,
60}
61
62impl<TYPES: NodeType> Membership<TYPES> for TwoStaticCommittees<TYPES> {
63    type Error = hotshot_utils::anytrace::Error;
64    /// Create a new election
65    fn new(committee_members: Vec<PeerConfig<TYPES>>, da_members: Vec<PeerConfig<TYPES>>) -> Self {
66        // For each eligible leader, get the stake table entry
67        let eligible_leaders: Vec<PeerConfig<TYPES>> = committee_members
68            .clone()
69            .into_iter()
70            .filter(|member| member.stake_table_entry.stake() > U256::ZERO)
71            .collect();
72
73        let eligible_leaders1 = eligible_leaders
74            .iter()
75            .enumerate()
76            .filter(|(idx, _)| idx % 2 == 0)
77            .map(|(_, leader)| leader.clone())
78            .collect();
79        let eligible_leaders2 = eligible_leaders
80            .iter()
81            .enumerate()
82            .filter(|(idx, _)| idx % 2 == 1)
83            .map(|(_, leader)| leader.clone())
84            .collect();
85
86        // For each member, get the stake table entry
87        let members: Vec<PeerConfig<TYPES>> = committee_members
88            .clone()
89            .into_iter()
90            .filter(|member| member.stake_table_entry.stake() > U256::ZERO)
91            .collect();
92
93        let members1: Vec<PeerConfig<TYPES>> = members
94            .iter()
95            .enumerate()
96            .filter(|(idx, _)| idx % 2 == 0)
97            .map(|(_, leader)| leader.clone())
98            .collect();
99        let members2: Vec<PeerConfig<TYPES>> = members
100            .iter()
101            .enumerate()
102            .filter(|(idx, _)| idx % 2 == 1)
103            .map(|(_, leader)| leader.clone())
104            .collect();
105
106        // For each member, get the stake table entry
107        let da_members: Vec<PeerConfig<TYPES>> = da_members
108            .clone()
109            .into_iter()
110            .filter(|member| member.stake_table_entry.stake() > U256::ZERO)
111            .collect();
112
113        let da_members1: Vec<PeerConfig<TYPES>> = da_members
114            .iter()
115            .enumerate()
116            .filter(|(idx, _)| idx % 2 == 0)
117            .map(|(_, leader)| leader.clone())
118            .collect();
119        let da_members2: Vec<PeerConfig<TYPES>> = da_members
120            .iter()
121            .enumerate()
122            .filter(|(idx, _)| idx % 2 == 1)
123            .map(|(_, leader)| leader.clone())
124            .collect();
125
126        // Index the stake table by public key
127        let indexed_stake_table1: BTreeMap<TYPES::SignatureKey, _> = members1
128            .iter()
129            .map(|member| {
130                (
131                    TYPES::SignatureKey::public_key(&member.stake_table_entry),
132                    member.clone(),
133                )
134            })
135            .collect();
136
137        let indexed_stake_table2: BTreeMap<TYPES::SignatureKey, _> = members2
138            .iter()
139            .map(|member| {
140                (
141                    TYPES::SignatureKey::public_key(&member.stake_table_entry),
142                    member.clone(),
143                )
144            })
145            .collect();
146
147        // Index the stake table by public key
148        let indexed_da_stake_table1: BTreeMap<TYPES::SignatureKey, _> = da_members1
149            .iter()
150            .map(|member| {
151                (
152                    TYPES::SignatureKey::public_key(&member.stake_table_entry),
153                    member.clone(),
154                )
155            })
156            .collect();
157
158        let indexed_da_stake_table2: BTreeMap<TYPES::SignatureKey, _> = da_members2
159            .iter()
160            .map(|member| {
161                (
162                    TYPES::SignatureKey::public_key(&member.stake_table_entry),
163                    member.clone(),
164                )
165            })
166            .collect();
167
168        Self {
169            eligible_leaders: (eligible_leaders1, eligible_leaders2),
170            stake_table: (members1.into(), members2.into()),
171            da_stake_table: (da_members1.into(), da_members2.into()),
172            indexed_stake_table: (indexed_stake_table1, indexed_stake_table2),
173            indexed_da_stake_table: (indexed_da_stake_table1, indexed_da_stake_table2),
174            first_epoch: None,
175        }
176    }
177
178    /// Get the stake table for the current view
179    fn stake_table(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> HSStakeTable<TYPES> {
180        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
181        if *epoch != 0 && *epoch % 2 == 0 {
182            self.stake_table.0.clone()
183        } else {
184            self.stake_table.1.clone()
185        }
186    }
187
188    /// Get the stake table for the current view
189    fn da_stake_table(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> HSStakeTable<TYPES> {
190        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
191        if *epoch != 0 && *epoch % 2 == 0 {
192            self.da_stake_table.0.clone()
193        } else {
194            self.da_stake_table.1.clone()
195        }
196    }
197
198    /// Get all members of the committee for the current view
199    fn committee_members(
200        &self,
201        _view_number: <TYPES as NodeType>::View,
202        epoch: Option<<TYPES as NodeType>::Epoch>,
203    ) -> BTreeSet<<TYPES as NodeType>::SignatureKey> {
204        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
205        if *epoch != 0 && *epoch % 2 == 0 {
206            self.stake_table
207                .0
208                .iter()
209                .map(|sc| TYPES::SignatureKey::public_key(&sc.stake_table_entry))
210                .collect()
211        } else {
212            self.stake_table
213                .1
214                .iter()
215                .map(|sc| TYPES::SignatureKey::public_key(&sc.stake_table_entry))
216                .collect()
217        }
218    }
219
220    /// Get all members of the committee for the current view
221    fn da_committee_members(
222        &self,
223        _view_number: <TYPES as NodeType>::View,
224        epoch: Option<<TYPES as NodeType>::Epoch>,
225    ) -> BTreeSet<<TYPES as NodeType>::SignatureKey> {
226        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
227        if *epoch != 0 && *epoch % 2 == 0 {
228            self.da_stake_table
229                .0
230                .iter()
231                .map(|da| TYPES::SignatureKey::public_key(&da.stake_table_entry))
232                .collect()
233        } else {
234            self.da_stake_table
235                .1
236                .iter()
237                .map(|da| TYPES::SignatureKey::public_key(&da.stake_table_entry))
238                .collect()
239        }
240    }
241
242    /// Get the stake table entry for a public key
243    fn stake(
244        &self,
245        pub_key: &<TYPES as NodeType>::SignatureKey,
246        epoch: Option<<TYPES as NodeType>::Epoch>,
247    ) -> Option<PeerConfig<TYPES>> {
248        // Only return the stake if it is above zero
249        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
250        if *epoch != 0 && *epoch % 2 == 0 {
251            self.indexed_stake_table.0.get(pub_key).cloned()
252        } else {
253            self.indexed_stake_table.1.get(pub_key).cloned()
254        }
255    }
256
257    /// Get the DA stake table entry for a public key
258    fn da_stake(
259        &self,
260        pub_key: &<TYPES as NodeType>::SignatureKey,
261        epoch: Option<<TYPES as NodeType>::Epoch>,
262    ) -> Option<PeerConfig<TYPES>> {
263        // Only return the stake if it is above zero
264        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
265        if *epoch != 0 && *epoch % 2 == 0 {
266            self.indexed_da_stake_table.0.get(pub_key).cloned()
267        } else {
268            self.indexed_da_stake_table.1.get(pub_key).cloned()
269        }
270    }
271
272    /// Check if a node has stake in the committee
273    fn has_stake(
274        &self,
275        pub_key: &<TYPES as NodeType>::SignatureKey,
276        epoch: Option<<TYPES as NodeType>::Epoch>,
277    ) -> bool {
278        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
279        if *epoch != 0 && *epoch % 2 == 0 {
280            self.indexed_stake_table
281                .0
282                .get(pub_key)
283                .is_some_and(|x| x.stake_table_entry.stake() > U256::ZERO)
284        } else {
285            self.indexed_stake_table
286                .1
287                .get(pub_key)
288                .is_some_and(|x| x.stake_table_entry.stake() > U256::ZERO)
289        }
290    }
291    /// Check if a node has stake in the committee
292    fn has_da_stake(
293        &self,
294        pub_key: &<TYPES as NodeType>::SignatureKey,
295        epoch: Option<<TYPES as NodeType>::Epoch>,
296    ) -> bool {
297        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
298        if *epoch != 0 && *epoch % 2 == 0 {
299            self.indexed_da_stake_table
300                .0
301                .get(pub_key)
302                .is_some_and(|x| x.stake_table_entry.stake() > U256::ZERO)
303        } else {
304            self.indexed_da_stake_table
305                .1
306                .get(pub_key)
307                .is_some_and(|x| x.stake_table_entry.stake() > U256::ZERO)
308        }
309    }
310
311    /// Index the vector of public keys with the current view number
312    fn lookup_leader(
313        &self,
314        view_number: <TYPES as NodeType>::View,
315        epoch: Option<<TYPES as NodeType>::Epoch>,
316    ) -> Result<TYPES::SignatureKey> {
317        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
318        if *epoch != 0 && *epoch % 2 == 0 {
319            #[allow(clippy::cast_possible_truncation)]
320            let index = *view_number as usize % self.eligible_leaders.0.len();
321            let res = self.eligible_leaders.0[index].clone();
322            Ok(TYPES::SignatureKey::public_key(&res.stake_table_entry))
323        } else {
324            #[allow(clippy::cast_possible_truncation)]
325            let index = *view_number as usize % self.eligible_leaders.1.len();
326            let res = self.eligible_leaders.1[index].clone();
327            Ok(TYPES::SignatureKey::public_key(&res.stake_table_entry))
328        }
329    }
330
331    /// Get the total number of nodes in the committee
332    fn total_nodes(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> usize {
333        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
334        if *epoch != 0 && *epoch % 2 == 0 {
335            self.stake_table.0.len()
336        } else {
337            self.stake_table.1.len()
338        }
339    }
340
341    /// Get the total number of DA nodes in the committee
342    fn da_total_nodes(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> usize {
343        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
344        if *epoch != 0 && *epoch % 2 == 0 {
345            self.da_stake_table.0.len()
346        } else {
347            self.da_stake_table.1.len()
348        }
349    }
350
351    /// Get the voting success threshold for the committee
352    fn success_threshold(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> U256 {
353        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
354        if *epoch != 0 && *epoch % 2 == 0 {
355            U256::from(((self.stake_table.0.len() as u64 * 2) / 3) + 1)
356        } else {
357            U256::from(((self.stake_table.1.len() as u64 * 2) / 3) + 1)
358        }
359    }
360
361    /// Get the voting success threshold for the committee
362    fn da_success_threshold(&self, epoch: Option<TYPES::Epoch>) -> U256 {
363        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
364        if *epoch != 0 && *epoch % 2 == 0 {
365            U256::from(((self.da_stake_table.0.len() as u64 * 2) / 3) + 1)
366        } else {
367            U256::from(((self.da_stake_table.1.len() as u64 * 2) / 3) + 1)
368        }
369    }
370
371    /// Get the voting failure threshold for the committee
372    fn failure_threshold(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> U256 {
373        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
374        if *epoch != 0 && *epoch % 2 == 0 {
375            U256::from(((self.stake_table.0.len() as u64) / 3) + 1)
376        } else {
377            U256::from(((self.stake_table.1.len() as u64) / 3) + 1)
378        }
379    }
380
381    /// Get the voting upgrade threshold for the committee
382    fn upgrade_threshold(&self, epoch: Option<<TYPES as NodeType>::Epoch>) -> U256 {
383        let epoch = epoch.expect("epochs cannot be disabled with TwoStaticCommittees");
384        if *epoch != 0 && *epoch % 2 == 0 {
385            U256::from(max(
386                (self.stake_table.0.len() as u64 * 9) / 10,
387                ((self.stake_table.0.len() as u64 * 2) / 3) + 1,
388            ))
389        } else {
390            U256::from(max(
391                (self.stake_table.1.len() as u64 * 9) / 10,
392                ((self.stake_table.1.len() as u64 * 2) / 3) + 1,
393            ))
394        }
395    }
396    fn has_stake_table(&self, _epoch: TYPES::Epoch) -> bool {
397        true
398    }
399    fn has_randomized_stake_table(&self, _epoch: TYPES::Epoch) -> anyhow::Result<bool> {
400        Ok(true)
401    }
402
403    fn add_drb_result(&mut self, _epoch: <TYPES as NodeType>::Epoch, _drb_result: DrbResult) {}
404
405    fn set_first_epoch(&mut self, epoch: TYPES::Epoch, _initial_drb_result: DrbResult) {
406        self.first_epoch = Some(epoch);
407    }
408
409    fn first_epoch(&self) -> Option<TYPES::Epoch> {
410        self.first_epoch
411    }
412}
hotshot/traits/election/two_static_committees.rs

hotshot/traits/election/
two_static_committees.rs
