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

hotshot/traits/election/
two_static_committees.rs
