hotshot_types/traits/
election.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
7//! The election trait, used to decide which node is the leader and determine if a vote is valid.
8//!
9//! Reads of per-epoch state go through a [`MembershipSnapshot`] obtained from
10//! [`Membership::snapshot`]. Reads of pre-epoch state go through a
11//! [`NonEpochMembershipSnapshot`] obtained from [`Membership::non_epoch_snapshot`].
12//! Each snapshot is a consistent point-in-time view; its accessors observe
13//! one moment of the membership state, so derived values from the same
14//! snapshot are guaranteed to come from one logical instant.
15
16use std::fmt::Debug;
17
18use alloy_primitives::U256;
19use committable::{Commitment, Committable};
20use hotshot_utils::anytrace;
21
22use super::node_implementation::NodeType;
23use crate::{
24    PeerConfig,
25    data::{EpochNumber, Leaf2, ViewNumber},
26    drb::DrbResult,
27    epoch_membership::EpochMembershipCoordinator,
28    stake_table::supermajority_threshold,
29    traits::signature_key::StakeTableEntryType,
30};
31
32pub struct NoStakeTableHash;
33
34impl Committable for NoStakeTableHash {
35    fn commit(&self) -> Commitment<Self> {
36        Commitment::from_raw([0u8; 32])
37    }
38}
39
40/// A consistent per-epoch view of a [`Membership`].
41pub trait MembershipSnapshot<T: NodeType>: Clone + Send + Sync {
42    type Error: std::error::Error + Send + Sync + 'static;
43    type StakeTableHash: Committable;
44
45    /// The epoch this snapshot is bound to.
46    fn epoch(&self) -> EpochNumber;
47
48    /// The first epoch known to the membership (cached at snapshot creation).
49    fn first_epoch(&self) -> Option<EpochNumber>;
50
51    /// Whether a randomized stake table (DRB result) was available for this
52    /// epoch at the time the snapshot was captured.
53    fn has_drb(&self) -> bool;
54
55    /// The (non-DA) stake table for this epoch.
56    ///
57    /// Iteration order is the stake-table position order — the position
58    /// of a key in this iterator equals the value returned by the
59    /// implementation's `get_validator_index` (where applicable) and is
60    /// part of the per-epoch consensus contract.
61    fn stake_table(&self) -> impl ExactSizeIterator<Item = &PeerConfig<T>> + Send;
62
63    /// The DA stake table for this epoch.
64    fn da_stake_table(&self) -> impl ExactSizeIterator<Item = &PeerConfig<T>> + Send;
65
66    /// The set of public keys with stake in this epoch, in stake-table order.
67    fn committee_members(
68        &self,
69        view: ViewNumber,
70    ) -> impl ExactSizeIterator<Item = &T::SignatureKey> + Send;
71
72    /// The set of public keys in the DA committee for this epoch.
73    fn da_committee_members(
74        &self,
75        view: ViewNumber,
76    ) -> impl ExactSizeIterator<Item = &T::SignatureKey> + Send;
77
78    /// The stake-table entry for `key`, or `None` if the key is not in the
79    /// committee for this epoch.
80    fn stake(&self, key: &T::SignatureKey) -> Option<PeerConfig<T>>;
81
82    /// The DA stake-table entry for `key`, or `None`.
83    fn da_stake(&self, key: &T::SignatureKey) -> Option<PeerConfig<T>>;
84
85    /// Whether `key` has stake in this epoch.
86    fn has_stake(&self, key: &T::SignatureKey) -> bool;
87
88    /// Whether `key` has DA stake in this epoch.
89    fn has_da_stake(&self, key: &T::SignatureKey) -> bool;
90
91    /// The leader for `view` in this epoch.
92    ///
93    /// # Errors
94    ///
95    /// Returns an error if the leader cannot be calculated.
96    fn lookup_leader(&self, view: ViewNumber) -> Result<T::SignatureKey, Self::Error>;
97
98    /// The commitment of the stake table for this epoch, if available.
99    fn stake_table_hash(&self) -> Option<Commitment<Self::StakeTableHash>> {
100        None
101    }
102
103    /// Number of members in this epoch's stake table.
104    fn total_nodes(&self) -> usize {
105        self.stake_table().len()
106    }
107
108    /// Number of members in this epoch's DA committee.
109    fn da_total_nodes(&self) -> usize {
110        self.da_stake_table().len()
111    }
112
113    /// Sum of all stake in this epoch.
114    fn total_stake(&self) -> U256 {
115        self.stake_table()
116            .fold(U256::ZERO, |acc, e| acc + e.stake_table_entry.stake())
117    }
118
119    /// Sum of all DA stake in this epoch.
120    fn total_da_stake(&self) -> U256 {
121        self.da_stake_table()
122            .fold(U256::ZERO, |acc, e| acc + e.stake_table_entry.stake())
123    }
124
125    /// Quorum (supermajority) threshold for this epoch.
126    fn success_threshold(&self) -> U256 {
127        supermajority_threshold(self.total_stake())
128    }
129
130    /// DA quorum threshold for this epoch.
131    fn da_success_threshold(&self) -> U256 {
132        let total = self.total_da_stake();
133        let one = U256::ONE;
134        let two = U256::from(2);
135        let three = U256::from(3);
136        if total < U256::MAX / two {
137            ((total * two) / three) + one
138        } else {
139            ((total / three) * two) + two
140        }
141    }
142
143    /// Failure threshold (1/3 + 1) for this epoch.
144    fn failure_threshold(&self) -> U256 {
145        let total = self.total_stake();
146        (total / U256::from(3)) + U256::ONE
147    }
148
149    /// Threshold required for a protocol upgrade.
150    fn upgrade_threshold(&self) -> U256 {
151        let total = self.total_stake();
152        let nine = U256::from(9);
153        let ten = U256::from(10);
154        let normal = self.success_threshold();
155        let higher = if total < U256::MAX / nine {
156            (total * nine) / ten
157        } else {
158            (total / ten) * nine
159        };
160        std::cmp::max(higher, normal)
161    }
162
163    /// The leader for `view` in this epoch, returning a HotShot-internal
164    /// error type. Default impl wraps [`Self::lookup_leader`].
165    fn leader(&self, view: ViewNumber) -> anytrace::Result<T::SignatureKey> {
166        use hotshot_utils::anytrace::*;
167        let epoch = self.epoch();
168        self.lookup_leader(view).wrap().context(info!(
169            "Failed to get leader for view {view} in epoch {epoch}"
170        ))
171    }
172}
173
174/// A consistent view of the pre-epoch [`Membership`] state.
175///
176/// Used when consensus is operating before epochs are enabled (the
177/// `epoch == None` path in the legacy API).
178pub trait NonEpochMembershipSnapshot<T: NodeType>: Clone + Send + Sync {
179    type Error: std::error::Error + Send + Sync + 'static;
180
181    fn stake_table(&self) -> impl ExactSizeIterator<Item = &PeerConfig<T>> + Send + '_;
182    fn da_stake_table(&self) -> impl ExactSizeIterator<Item = &PeerConfig<T>> + Send + '_;
183    fn committee_members(
184        &self,
185        view: ViewNumber,
186    ) -> impl ExactSizeIterator<Item = &T::SignatureKey> + Send + '_;
187    fn da_committee_members(
188        &self,
189        view: ViewNumber,
190    ) -> impl ExactSizeIterator<Item = &T::SignatureKey> + Send + '_;
191    fn stake(&self, key: &T::SignatureKey) -> Option<PeerConfig<T>>;
192    fn da_stake(&self, key: &T::SignatureKey) -> Option<PeerConfig<T>>;
193    fn has_stake(&self, key: &T::SignatureKey) -> bool;
194    fn has_da_stake(&self, key: &T::SignatureKey) -> bool;
195    fn lookup_leader(&self, view: ViewNumber) -> Result<T::SignatureKey, Self::Error>;
196
197    fn total_nodes(&self) -> usize {
198        self.stake_table().len()
199    }
200
201    fn da_total_nodes(&self) -> usize {
202        self.da_stake_table().len()
203    }
204
205    fn total_stake(&self) -> U256 {
206        self.stake_table()
207            .fold(U256::ZERO, |acc, e| acc + e.stake_table_entry.stake())
208    }
209
210    fn total_da_stake(&self) -> U256 {
211        self.da_stake_table()
212            .fold(U256::ZERO, |acc, e| acc + e.stake_table_entry.stake())
213    }
214
215    fn success_threshold(&self) -> U256 {
216        supermajority_threshold(self.total_stake())
217    }
218
219    fn da_success_threshold(&self) -> U256 {
220        let total = self.total_da_stake();
221        let one = U256::ONE;
222        let two = U256::from(2);
223        let three = U256::from(3);
224        if total < U256::MAX / two {
225            ((total * two) / three) + one
226        } else {
227            ((total / three) * two) + two
228        }
229    }
230
231    fn failure_threshold(&self) -> U256 {
232        let total = self.total_stake();
233        (total / U256::from(3)) + U256::ONE
234    }
235
236    fn upgrade_threshold(&self) -> U256 {
237        let total = self.total_stake();
238        let nine = U256::from(9);
239        let ten = U256::from(10);
240        let normal = self.success_threshold();
241        let higher = if total < U256::MAX / nine {
242            (total * nine) / ten
243        } else {
244            (total / ten) * nine
245        };
246        std::cmp::max(higher, normal)
247    }
248
249    fn leader(&self, view: ViewNumber) -> anytrace::Result<T::SignatureKey> {
250        use hotshot_utils::anytrace::*;
251        self.lookup_leader(view)
252            .wrap()
253            .context(info!("Failed to get leader for view {view} (non-epoch)"))
254    }
255}
256
257/// A protocol for determining membership in and participating in a committee.
258///
259/// All read access goes through one of two snapshot types:
260/// - [`Self::snapshot`] for per-epoch reads
261/// - [`Self::non_epoch_snapshot`] for pre-epoch reads
262///
263/// Each snapshot is a consistent point-in-time view; derived values read from
264/// the same snapshot are guaranteed to come from one logical moment.
265pub trait Membership<T: NodeType>: Debug + Send + Sync {
266    type Error: std::error::Error + Send + Sync + 'static;
267
268    /// A consistent per-epoch view, returned by [`Self::snapshot`].
269    type Snapshot: MembershipSnapshot<T, Error = Self::Error>;
270
271    /// A consistent pre-epoch view, returned by [`Self::non_epoch_snapshot`].
272    type NonEpochSnapshot: NonEpochMembershipSnapshot<T, Error = Self::Error>;
273
274    /// Capture a consistent per-epoch view.
275    ///
276    /// Returns `None` if no committee is loaded for `epoch`.
277    fn snapshot(&self, epoch: EpochNumber) -> Option<Self::Snapshot>;
278
279    /// Capture a consistent pre-epoch view.
280    fn non_epoch_snapshot(&self) -> Self::NonEpochSnapshot;
281
282    /// Get first epoch if epochs are enabled, `None` otherwise.
283    fn first_epoch(&self) -> Option<EpochNumber>;
284
285    /// Get the highest epoch for which a stake table is currently in memory,
286    /// or `None` if no stake tables are loaded. Used at startup to find the
287    /// point from which to walk forward catching up missing epochs.
288    fn highest_known_epoch(&self) -> Option<EpochNumber> {
289        None
290    }
291
292    /// Gets the validated block header and epoch number of the epoch root
293    /// at the given block height.
294    fn get_epoch_root(
295        &self,
296        e: EpochNumber,
297        coordinator: &EpochMembershipCoordinator<T>,
298    ) -> impl Future<Output = Result<Leaf2<T>, Self::Error>> + Send;
299
300    /// Gets the DRB result for the given epoch.
301    fn get_epoch_drb(
302        &self,
303        e: EpochNumber,
304        coordinator: &EpochMembershipCoordinator<T>,
305    ) -> impl Future<Output = Result<DrbResult, Self::Error>> + Send;
306
307    /// Handles notifications that a new epoch root has been created.
308    fn add_epoch_root(
309        &self,
310        h: T::BlockHeader,
311        coordinator: &EpochMembershipCoordinator<T>,
312    ) -> impl Future<Output = Result<(), Self::Error>> + Send;
313
314    /// Called to notify the Membership when a new DRB result has been calculated.
315    fn add_drb_result(&self, e: EpochNumber, d: DrbResult);
316
317    /// Called to notify the Membership that Epochs are enabled.
318    /// Implementations should copy the pre-epoch stake table into epoch and epoch+1
319    /// when this is called. The value of initial_drb_result should be used for DRB
320    /// calculations for epochs (epoch+1) and earlier.
321    fn set_first_epoch(&self, e: EpochNumber, r: DrbResult);
322
323    /// Register a DA committee that takes effect starting at `first_epoch`.
324    fn add_da_committee(&self, first_epoch: EpochNumber, da_committee: Vec<PeerConfig<T>>);
325}
hotshot_types/traits/election.rs

hotshot_types/traits/
election.rs
