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

hotshot/traits/election/
randomized_committee.rs
