hotshot_types/
utils.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//! Utility functions, type aliases, helper structs and enum definitions.
8
9use std::{
10    hash::{Hash, Hasher},
11    ops::Deref,
12    sync::Arc,
13};
14
15use alloy::primitives::U256;
16use anyhow::{anyhow, ensure};
17use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
18use bincode::{
19    config::{
20        FixintEncoding, LittleEndian, RejectTrailing, WithOtherEndian, WithOtherIntEncoding,
21        WithOtherLimit, WithOtherTrailing,
22    },
23    DefaultOptions, Options,
24};
25use committable::{Commitment, Committable};
26use digest::OutputSizeUser;
27use serde::{Deserialize, Serialize};
28use sha2::Digest;
29use tagged_base64::tagged;
30use typenum::Unsigned;
31use vbs::version::StaticVersionType;
32
33use crate::{
34    data::{Leaf2, VidCommitment},
35    stake_table::StakeTableEntries,
36    traits::{
37        node_implementation::{ConsensusTime, NodeType, Versions},
38        ValidatedState,
39    },
40    vote::{Certificate, HasViewNumber},
41    PeerConfig,
42};
43
44/// A view's state
45#[derive(Debug, Deserialize, Serialize, PartialEq, Eq)]
46#[serde(bound = "")]
47pub enum ViewInner<TYPES: NodeType> {
48    /// A pending view with an available block but not leaf proposal yet.
49    ///
50    /// Storing this state allows us to garbage collect blocks for views where a proposal is never
51    /// made. This saves memory when a leader fails and subverts a DoS attack where malicious
52    /// leaders repeatedly request availability for blocks that they never propose.
53    Da {
54        /// Payload commitment to the available block.
55        payload_commitment: VidCommitment,
56        /// An epoch to which the data belongs to. Relevant for validating against the correct stake table
57        epoch: Option<TYPES::Epoch>,
58    },
59    /// Undecided view
60    Leaf {
61        /// Proposed leaf
62        leaf: LeafCommitment<TYPES>,
63        /// Validated state.
64        state: Arc<TYPES::ValidatedState>,
65        /// Optional state delta.
66        delta: Option<Arc<<TYPES::ValidatedState as ValidatedState<TYPES>>::Delta>>,
67        /// An epoch to which the data belongs to. Relevant for validating against the correct stake table
68        epoch: Option<TYPES::Epoch>,
69    },
70    /// Leaf has failed
71    Failed,
72}
73impl<TYPES: NodeType> Clone for ViewInner<TYPES> {
74    fn clone(&self) -> Self {
75        match self {
76            Self::Da {
77                payload_commitment,
78                epoch,
79            } => Self::Da {
80                payload_commitment: *payload_commitment,
81                epoch: *epoch,
82            },
83            Self::Leaf {
84                leaf,
85                state,
86                delta,
87                epoch,
88            } => Self::Leaf {
89                leaf: *leaf,
90                state: Arc::clone(state),
91                delta: delta.clone(),
92                epoch: *epoch,
93            },
94            Self::Failed => Self::Failed,
95        }
96    }
97}
98/// The hash of a leaf.
99pub type LeafCommitment<TYPES> = Commitment<Leaf2<TYPES>>;
100
101/// Optional validated state and state delta.
102pub type StateAndDelta<TYPES> = (
103    Option<Arc<<TYPES as NodeType>::ValidatedState>>,
104    Option<Arc<<<TYPES as NodeType>::ValidatedState as ValidatedState<TYPES>>::Delta>>,
105);
106
107pub async fn verify_leaf_chain<T: NodeType, V: Versions>(
108    mut leaf_chain: Vec<Leaf2<T>>,
109    stake_table: &[PeerConfig<T>],
110    success_threshold: U256,
111    expected_height: u64,
112    upgrade_lock: &crate::message::UpgradeLock<T, V>,
113) -> anyhow::Result<Leaf2<T>> {
114    // Sort the leaf chain by view number
115    leaf_chain.sort_by_key(|l| l.view_number());
116    // Reverse it
117    leaf_chain.reverse();
118
119    // Check we actually have a chain long enough for deciding
120    if leaf_chain.len() < 3 {
121        return Err(anyhow!("Leaf chain is not long enough for a decide"));
122    }
123
124    let newest_leaf = leaf_chain.first().unwrap();
125    let parent = &leaf_chain[1];
126    let grand_parent = &leaf_chain[2];
127
128    // Check if the leaves form a decide
129    if newest_leaf.justify_qc().view_number() != parent.view_number()
130        || parent.justify_qc().view_number() != grand_parent.view_number()
131    {
132        return Err(anyhow!("Leaf views do not chain"));
133    }
134    if newest_leaf.justify_qc().data.leaf_commit != parent.commit()
135        || parent.justify_qc().data().leaf_commit != grand_parent.commit()
136    {
137        return Err(anyhow!("Leaf commits do not chain"));
138    }
139    if parent.view_number() != grand_parent.view_number() + 1 {
140        return Err(anyhow::anyhow!(
141            "Decide rule failed, parent does not directly extend grandparent"
142        ));
143    }
144
145    // Get the stake table entries
146    let stake_table_entries = StakeTableEntries::<T>::from(stake_table.to_vec()).0;
147
148    // verify all QCs are valid
149    newest_leaf
150        .justify_qc()
151        .is_valid_cert(&stake_table_entries, success_threshold, upgrade_lock)
152        .await?;
153    parent
154        .justify_qc()
155        .is_valid_cert(&stake_table_entries, success_threshold, upgrade_lock)
156        .await?;
157    grand_parent
158        .justify_qc()
159        .is_valid_cert(&stake_table_entries, success_threshold, upgrade_lock)
160        .await?;
161
162    // Verify the root is in the chain of decided leaves
163    let mut last_leaf = parent;
164    for leaf in leaf_chain.iter().skip(2) {
165        ensure!(last_leaf.justify_qc().view_number() == leaf.view_number());
166        ensure!(last_leaf.justify_qc().data().leaf_commit == leaf.commit());
167        leaf.justify_qc()
168            .is_valid_cert(&stake_table_entries, success_threshold, upgrade_lock)
169            .await?;
170        if leaf.height() == expected_height {
171            return Ok(leaf.clone());
172        }
173        last_leaf = leaf;
174    }
175    Err(anyhow!("Epoch Root was not found in the decided chain"))
176}
177
178impl<TYPES: NodeType> ViewInner<TYPES> {
179    /// Return the underlying undecide leaf commitment and validated state if they exist.
180    #[must_use]
181    pub fn leaf_and_state(&self) -> Option<(LeafCommitment<TYPES>, &Arc<TYPES::ValidatedState>)> {
182        if let Self::Leaf { leaf, state, .. } = self {
183            Some((*leaf, state))
184        } else {
185            None
186        }
187    }
188
189    /// return the underlying leaf hash if it exists
190    #[must_use]
191    pub fn leaf_commitment(&self) -> Option<LeafCommitment<TYPES>> {
192        if let Self::Leaf { leaf, .. } = self {
193            Some(*leaf)
194        } else {
195            None
196        }
197    }
198
199    /// return the underlying validated state if it exists
200    #[must_use]
201    pub fn state(&self) -> Option<&Arc<TYPES::ValidatedState>> {
202        if let Self::Leaf { state, .. } = self {
203            Some(state)
204        } else {
205            None
206        }
207    }
208
209    /// Return the underlying validated state and state delta if they exist.
210    #[must_use]
211    pub fn state_and_delta(&self) -> StateAndDelta<TYPES> {
212        if let Self::Leaf { state, delta, .. } = self {
213            (Some(Arc::clone(state)), delta.clone())
214        } else {
215            (None, None)
216        }
217    }
218
219    /// return the underlying block payload commitment if it exists
220    #[must_use]
221    pub fn payload_commitment(&self) -> Option<VidCommitment> {
222        if let Self::Da {
223            payload_commitment, ..
224        } = self
225        {
226            Some(*payload_commitment)
227        } else {
228            None
229        }
230    }
231
232    /// Returns `Epoch` if possible
233    // #3967 REVIEW NOTE: This type is kinda ugly, should we Result<Option<Epoch>> instead?
234    pub fn epoch(&self) -> Option<Option<TYPES::Epoch>> {
235        match self {
236            Self::Da { epoch, .. } | Self::Leaf { epoch, .. } => Some(*epoch),
237            Self::Failed => None,
238        }
239    }
240}
241
242impl<TYPES: NodeType> Deref for View<TYPES> {
243    type Target = ViewInner<TYPES>;
244
245    fn deref(&self) -> &Self::Target {
246        &self.view_inner
247    }
248}
249
250/// This exists so we can perform state transitions mutably
251#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
252#[serde(bound = "")]
253pub struct View<TYPES: NodeType> {
254    /// The view data. Wrapped in a struct so we can mutate
255    pub view_inner: ViewInner<TYPES>,
256}
257
258/// A struct containing information about a finished round.
259#[derive(Debug, Clone)]
260pub struct RoundFinishedEvent<TYPES: NodeType> {
261    /// The round that finished
262    pub view_number: TYPES::View,
263}
264
265/// Whether or not to stop inclusively or exclusively when walking
266#[derive(Copy, Clone, Debug)]
267pub enum Terminator<T> {
268    /// Stop right before this view number
269    Exclusive(T),
270    /// Stop including this view number
271    Inclusive(T),
272}
273
274/// Type alias for byte array of SHA256 digest length
275type Sha256Digest = [u8; <sha2::Sha256 as OutputSizeUser>::OutputSize::USIZE];
276
277#[tagged("BUILDER_COMMITMENT")]
278#[derive(Clone, Debug, Default, Hash, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
279/// Commitment that builders use to sign block options.
280/// A thin wrapper around a Sha256 digest.
281pub struct BuilderCommitment(Sha256Digest);
282
283impl BuilderCommitment {
284    /// Create new commitment for `data`
285    pub fn from_bytes(data: impl AsRef<[u8]>) -> Self {
286        Self(sha2::Sha256::digest(data.as_ref()).into())
287    }
288
289    /// Create a new commitment from a raw Sha256 digest
290    pub fn from_raw_digest(digest: impl Into<Sha256Digest>) -> Self {
291        Self(digest.into())
292    }
293}
294
295impl AsRef<Sha256Digest> for BuilderCommitment {
296    fn as_ref(&self) -> &Sha256Digest {
297        &self.0
298    }
299}
300
301/// For the wire format, we use bincode with the following options:
302///   - No upper size limit
303///   - Little endian encoding
304///   - Varint encoding
305///   - Reject trailing bytes
306#[allow(clippy::type_complexity)]
307#[must_use]
308pub fn bincode_opts() -> WithOtherTrailing<
309    WithOtherIntEncoding<
310        WithOtherEndian<WithOtherLimit<DefaultOptions, bincode::config::Infinite>, LittleEndian>,
311        FixintEncoding,
312    >,
313    RejectTrailing,
314> {
315    bincode::DefaultOptions::new()
316        .with_no_limit()
317        .with_little_endian()
318        .with_fixint_encoding()
319        .reject_trailing_bytes()
320}
321
322/// Returns an epoch number given a block number and an epoch height
323#[must_use]
324pub fn epoch_from_block_number(block_number: u64, epoch_height: u64) -> u64 {
325    if epoch_height == 0 {
326        0
327    } else if block_number == 0 {
328        1
329    } else if block_number.is_multiple_of(epoch_height) {
330        block_number / epoch_height
331    } else {
332        block_number / epoch_height + 1
333    }
334}
335
336/// Returns the block number of the epoch root in the given epoch
337///
338/// WARNING: This is NOT the root block for the given epoch.
339/// To find that root block number for epoch e, call `root_block_in_epoch(e-2,_)`.
340#[must_use]
341pub fn root_block_in_epoch(epoch: u64, epoch_height: u64) -> u64 {
342    if epoch_height == 0 || epoch < 1 {
343        0
344    } else {
345        epoch_height * epoch - 5
346    }
347}
348
349/// Get the block height of the transition block for the given epoch
350///
351/// This is the height at which we begin the transition to LEAVE the specified epoch
352#[must_use]
353pub fn transition_block_for_epoch(epoch: u64, epoch_height: u64) -> u64 {
354    if epoch_height == 0 || epoch < 1 {
355        0
356    } else {
357        epoch_height * epoch - 3
358    }
359}
360
361/// Returns an `Option<Epoch>` based on a boolean condition of whether or not epochs are enabled, a block number,
362/// and the epoch height. If epochs are disabled or the epoch height is zero, returns None.
363#[must_use]
364pub fn option_epoch_from_block_number<TYPES: NodeType>(
365    with_epoch: bool,
366    block_number: u64,
367    epoch_height: u64,
368) -> Option<TYPES::Epoch> {
369    if with_epoch {
370        if epoch_height == 0 {
371            None
372        } else if block_number == 0 {
373            Some(1u64)
374        } else if block_number.is_multiple_of(epoch_height) {
375            Some(block_number / epoch_height)
376        } else {
377            Some(block_number / epoch_height + 1)
378        }
379        .map(TYPES::Epoch::new)
380    } else {
381        None
382    }
383}
384
385/// Returns Some(1) if epochs are enabled by V::Base, otherwise returns None
386#[must_use]
387pub fn genesis_epoch_from_version<V: Versions, TYPES: NodeType>() -> Option<TYPES::Epoch> {
388    (V::Base::VERSION >= V::Epochs::VERSION).then(|| TYPES::Epoch::new(1))
389}
390
391/// A function for generating a cute little user mnemonic from a hash
392#[must_use]
393pub fn mnemonic<H: Hash>(bytes: H) -> String {
394    let mut state = std::collections::hash_map::DefaultHasher::new();
395    bytes.hash(&mut state);
396    mnemonic::to_string(state.finish().to_le_bytes())
397}
398
399/// A helper enum to indicate whether a node is in the epoch transition
400/// A node is in epoch transition when its high QC is for the last block in an epoch
401#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, Hash)]
402pub enum EpochTransitionIndicator {
403    /// A node is currently in the epoch transition
404    InTransition,
405    /// A node is not in the epoch transition
406    NotInTransition,
407}
408
409/// Return true if the given block number is the final full block, the "transition block"
410#[must_use]
411pub fn is_transition_block(block_number: u64, epoch_height: u64) -> bool {
412    if block_number == 0 || epoch_height == 0 {
413        false
414    } else {
415        (block_number + 3).is_multiple_of(epoch_height)
416    }
417}
418/// returns true if it's the first transition block (epoch height - 2)
419#[must_use]
420pub fn is_first_transition_block(block_number: u64, epoch_height: u64) -> bool {
421    if block_number == 0 || epoch_height == 0 {
422        false
423    } else {
424        block_number % epoch_height == epoch_height - 2
425    }
426}
427/// Returns true if the block is part of the epoch transition (including the last non null block)  
428#[must_use]
429pub fn is_epoch_transition(block_number: u64, epoch_height: u64) -> bool {
430    if block_number == 0 || epoch_height == 0 {
431        false
432    } else {
433        block_number % epoch_height >= epoch_height - 3 || block_number.is_multiple_of(epoch_height)
434    }
435}
436
437/// Returns true if the block is the last block in the epoch
438#[must_use]
439pub fn is_last_block(block_number: u64, epoch_height: u64) -> bool {
440    if block_number == 0 || epoch_height == 0 {
441        false
442    } else {
443        block_number.is_multiple_of(epoch_height)
444    }
445}
446
447/// Returns true if the block number is in trasntion but not the transition block
448/// or the last block in the epoch.  
449///
450/// This function is useful for determining if a proposal extending this QC must follow
451/// the special rules for transition blocks.
452#[must_use]
453pub fn is_middle_transition_block(block_number: u64, epoch_height: u64) -> bool {
454    if block_number == 0 || epoch_height == 0 {
455        false
456    } else {
457        let blocks_left = epoch_height - (block_number % epoch_height);
458        blocks_left == 1 || blocks_left == 2
459    }
460}
461
462/// Returns true if the given block number is the third from the last in the epoch based on the
463/// given epoch height.
464#[must_use]
465pub fn is_epoch_root(block_number: u64, epoch_height: u64) -> bool {
466    if block_number == 0 || epoch_height == 0 {
467        false
468    } else {
469        (block_number + 5).is_multiple_of(epoch_height)
470    }
471}
472
473/// Returns true if the given block number is equal or greater than the epoch root block
474#[must_use]
475pub fn is_ge_epoch_root(block_number: u64, epoch_height: u64) -> bool {
476    if block_number == 0 || epoch_height == 0 {
477        false
478    } else {
479        block_number.is_multiple_of(epoch_height) || block_number % epoch_height >= epoch_height - 5
480    }
481}
482
483/// Returns true if the given block number is strictly greater than the epoch root block
484pub fn is_gt_epoch_root(block_number: u64, epoch_height: u64) -> bool {
485    if block_number == 0 || epoch_height == 0 {
486        false
487    } else {
488        block_number.is_multiple_of(epoch_height) || block_number % epoch_height > epoch_height - 5
489    }
490}
491
492#[cfg(test)]
493mod test {
494    use super::*;
495
496    #[test]
497    fn test_epoch_from_block_number() {
498        // block 0 is always epoch 1
499        let epoch = epoch_from_block_number(0, 10);
500        assert_eq!(1, epoch);
501
502        let epoch = epoch_from_block_number(1, 10);
503        assert_eq!(1, epoch);
504
505        let epoch = epoch_from_block_number(10, 10);
506        assert_eq!(1, epoch);
507
508        let epoch = epoch_from_block_number(11, 10);
509        assert_eq!(2, epoch);
510
511        let epoch = epoch_from_block_number(20, 10);
512        assert_eq!(2, epoch);
513
514        let epoch = epoch_from_block_number(21, 10);
515        assert_eq!(3, epoch);
516
517        let epoch = epoch_from_block_number(21, 0);
518        assert_eq!(0, epoch);
519    }
520
521    #[test]
522    fn test_is_last_block_in_epoch() {
523        assert!(!is_epoch_transition(5, 10));
524        assert!(!is_epoch_transition(6, 10));
525        assert!(is_epoch_transition(7, 10));
526        assert!(is_epoch_transition(8, 10));
527        assert!(is_epoch_transition(9, 10));
528        assert!(is_epoch_transition(10, 10));
529        assert!(!is_epoch_transition(11, 10));
530
531        assert!(!is_epoch_transition(10, 0));
532    }
533
534    #[test]
535    fn test_is_epoch_root() {
536        assert!(is_epoch_root(5, 10));
537        assert!(!is_epoch_root(6, 10));
538        assert!(!is_epoch_root(7, 10));
539        assert!(!is_epoch_root(8, 10));
540        assert!(!is_epoch_root(9, 10));
541        assert!(!is_epoch_root(10, 10));
542        assert!(!is_epoch_root(11, 10));
543
544        assert!(!is_epoch_transition(10, 0));
545    }
546
547    #[test]
548    fn test_root_block_in_epoch() {
549        // block 0 is always epoch 0
550        let epoch = 3;
551        let epoch_height = 10;
552        let epoch_root_block_number = root_block_in_epoch(3, epoch_height);
553
554        assert!(is_epoch_root(25, epoch_height));
555
556        assert_eq!(epoch_root_block_number, 25);
557
558        assert_eq!(
559            epoch,
560            epoch_from_block_number(epoch_root_block_number, epoch_height)
561        );
562    }
563}
hotshot_types/utils.rs

hotshot_types/
utils.rs
