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

hotshot_types/traits/
election.rs
