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`]. Each snapshot is a consistent point-in-time view;
11//! its accessors observe one moment of the membership state, so derived values
12//! from the same snapshot are guaranteed to come from one logical instant.
13//! Reads of the views before the first epoch go through the
14//! [`GenesisStakeTables`] from [`Membership::genesis_stake_tables`].
15
16use std::{fmt::Debug, sync::Arc};
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::{one_honest_threshold, supermajority_threshold, upgrade_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 of the membership.
49    fn first_epoch(&self) -> 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        supermajority_threshold(self.total_da_stake())
133    }
134
135    /// Failure threshold (1/3 + 1) for this epoch.
136    fn failure_threshold(&self) -> U256 {
137        one_honest_threshold(self.total_stake())
138    }
139
140    /// Threshold required for a protocol upgrade.
141    fn upgrade_threshold(&self) -> U256 {
142        upgrade_threshold(self.total_stake())
143    }
144
145    /// The leader for `view` in this epoch, returning a HotShot-internal
146    /// error type. Default impl wraps [`Self::lookup_leader`].
147    fn leader(&self, view: ViewNumber) -> anytrace::Result<T::SignatureKey> {
148        use hotshot_utils::anytrace::*;
149        let epoch = self.epoch();
150        self.lookup_leader(view).wrap().context(info!(
151            "Failed to get leader for view {view} in epoch {epoch}"
152        ))
153    }
154}
155
156/// The stake tables of views before the first epoch, when epochs were not
157/// enabled yet: the genesis stake table and the genesis DA committee.
158///
159/// The members of the stake table take turns as leader, in order, whatever
160/// their stake. Epochs pick leaders at random instead.
161#[derive(Debug)]
162pub struct GenesisStakeTables<T: NodeType> {
163    stake_table: Vec<PeerConfig<T>>,
164    da_stake_table: Vec<PeerConfig<T>>,
165    /// The keys of `stake_table`, in the same order.
166    committee_members: Vec<T::SignatureKey>,
167    /// The keys of `da_stake_table`, in the same order.
168    da_committee_members: Vec<T::SignatureKey>,
169}
170
171impl<T: NodeType> GenesisStakeTables<T> {
172    /// Keeps both tables as given, in order.
173    pub fn new(stake_table: Vec<PeerConfig<T>>, da_stake_table: Vec<PeerConfig<T>>) -> Self {
174        Self {
175            committee_members: keys(&stake_table),
176            da_committee_members: keys(&da_stake_table),
177            stake_table,
178            da_stake_table,
179        }
180    }
181
182    pub fn stake_table(&self) -> impl ExactSizeIterator<Item = &PeerConfig<T>> + Send + '_ {
183        self.stake_table.iter()
184    }
185
186    pub fn da_stake_table(&self) -> impl ExactSizeIterator<Item = &PeerConfig<T>> + Send + '_ {
187        self.da_stake_table.iter()
188    }
189
190    pub fn committee_members(&self) -> impl ExactSizeIterator<Item = &T::SignatureKey> + Send + '_ {
191        self.committee_members.iter()
192    }
193
194    pub fn da_committee_members(
195        &self,
196    ) -> impl ExactSizeIterator<Item = &T::SignatureKey> + Send + '_ {
197        self.da_committee_members.iter()
198    }
199
200    pub fn stake(&self, key: &T::SignatureKey) -> Option<PeerConfig<T>> {
201        entry(&self.committee_members, &self.stake_table, key)
202    }
203
204    pub fn da_stake(&self, key: &T::SignatureKey) -> Option<PeerConfig<T>> {
205        entry(&self.da_committee_members, &self.da_stake_table, key)
206    }
207
208    pub fn has_stake(&self, key: &T::SignatureKey) -> bool {
209        self.stake(key)
210            .is_some_and(|p| p.stake_table_entry.stake() > U256::ZERO)
211    }
212
213    pub fn has_da_stake(&self, key: &T::SignatureKey) -> bool {
214        self.da_stake(key)
215            .is_some_and(|p| p.stake_table_entry.stake() > U256::ZERO)
216    }
217
218    /// The leader for `view`.
219    ///
220    /// # Errors
221    ///
222    /// Returns an error if the stake table is empty.
223    pub fn leader(&self, view: ViewNumber) -> anytrace::Result<T::SignatureKey> {
224        if self.committee_members.is_empty() {
225            return Err(anytrace::info!(
226                "Failed to get leader for view {view}: the genesis stake table is empty"
227            ));
228        }
229        let index = *view as usize % self.committee_members.len();
230        Ok(self.committee_members[index].clone())
231    }
232
233    pub fn total_nodes(&self) -> usize {
234        self.stake_table.len()
235    }
236
237    pub fn da_total_nodes(&self) -> usize {
238        self.da_stake_table.len()
239    }
240
241    pub fn success_threshold(&self) -> U256 {
242        supermajority_threshold(total_stake(&self.stake_table))
243    }
244
245    pub fn da_success_threshold(&self) -> U256 {
246        supermajority_threshold(total_stake(&self.da_stake_table))
247    }
248
249    pub fn failure_threshold(&self) -> U256 {
250        one_honest_threshold(total_stake(&self.stake_table))
251    }
252
253    pub fn upgrade_threshold(&self) -> U256 {
254        upgrade_threshold(total_stake(&self.stake_table))
255    }
256}
257
258fn keys<T: NodeType>(table: &[PeerConfig<T>]) -> Vec<T::SignatureKey> {
259    table
260        .iter()
261        .map(|p| p.stake_table_entry.public_key())
262        .collect()
263}
264
265/// The entry of `table` for `key`, where `keys` are the keys of `table`.
266fn entry<T: NodeType>(
267    keys: &[T::SignatureKey],
268    table: &[PeerConfig<T>],
269    key: &T::SignatureKey,
270) -> Option<PeerConfig<T>> {
271    let index = keys.iter().position(|k| k == key)?;
272    Some(table[index].clone())
273}
274
275fn total_stake<T: NodeType>(table: &[PeerConfig<T>]) -> U256 {
276    table
277        .iter()
278        .fold(U256::ZERO, |acc, p| acc + p.stake_table_entry.stake())
279}
280
281/// A protocol for determining membership in and participating in a committee.
282///
283/// Per-epoch reads go through [`Self::snapshot`], and reads of the views
284/// before the first epoch through [`Self::genesis_stake_tables`].
285///
286/// Each snapshot is a consistent point-in-time view; derived values read from
287/// the same snapshot are guaranteed to come from one logical moment.
288pub trait Membership<T: NodeType>: Debug + Send + Sync {
289    type Error: std::error::Error + Send + Sync + 'static;
290
291    /// A consistent per-epoch view, returned by [`Self::snapshot`].
292    type Snapshot: MembershipSnapshot<T, Error = Self::Error>;
293
294    /// Capture a consistent per-epoch view.
295    ///
296    /// Returns `None` if no committee is loaded for `epoch`.
297    fn snapshot(&self, epoch: EpochNumber) -> Option<Self::Snapshot>;
298
299    /// The stake tables of views before the first epoch.
300    fn genesis_stake_tables(&self) -> Arc<GenesisStakeTables<T>>;
301
302    /// The first epoch, which runs on the genesis stake table.
303    fn first_epoch(&self) -> EpochNumber;
304
305    /// Get the highest epoch for which a stake table is currently in memory,
306    /// or `None` if no stake tables are loaded. It is where catchup resumes
307    /// from, so an implementation that leaves it at `None` makes catchup
308    /// rediscover that point one epoch at a time.
309    fn highest_known_epoch(&self) -> Option<EpochNumber>;
310
311    /// Gets the validated block header and epoch number of the epoch root
312    /// at the given block height.
313    fn get_epoch_root(
314        &self,
315        e: EpochNumber,
316        coordinator: &EpochMembershipCoordinator<T>,
317    ) -> impl Future<Output = Result<Leaf2<T>, Self::Error>> + Send;
318
319    /// Gets the DRB result for the given epoch.
320    fn get_epoch_drb(
321        &self,
322        e: EpochNumber,
323        coordinator: &EpochMembershipCoordinator<T>,
324    ) -> impl Future<Output = Result<DrbResult, Self::Error>> + Send;
325
326    /// Handles notifications that a new epoch root has been created.
327    fn add_epoch_root(
328        &self,
329        h: T::BlockHeader,
330        coordinator: &EpochMembershipCoordinator<T>,
331    ) -> impl Future<Output = Result<(), Self::Error>> + Send;
332
333    /// Called to notify the Membership when a new DRB result has been calculated.
334    fn add_drb_result(&self, e: EpochNumber, d: DrbResult);
335
336    /// Load the committee for `epoch` from local storage.
337    ///
338    /// Returns `true` if a snapshot for `epoch` is available afterwards.
339    fn load_stake_table(&self, epoch: EpochNumber) -> impl Future<Output = bool> + Send;
340
341    /// Register a DA committee that takes effect starting at `first_epoch`.
342    fn add_da_committee(&self, first_epoch: EpochNumber, da_committee: Vec<PeerConfig<T>>);
343}
hotshot_types/traits/election.rs

hotshot_types/traits/
election.rs
