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]
308#[allow(clippy::type_complexity)]
309pub fn bincode_opts() -> WithOtherTrailing<
310    WithOtherIntEncoding<
311        WithOtherEndian<WithOtherLimit<DefaultOptions, bincode::config::Infinite>, LittleEndian>,
312        FixintEncoding,
313    >,
314    RejectTrailing,
315> {
316    bincode::DefaultOptions::new()
317        .with_no_limit()
318        .with_little_endian()
319        .with_fixint_encoding()
320        .reject_trailing_bytes()
321}
322
323/// Returns an epoch number given a block number and an epoch height
324#[must_use]
325pub fn epoch_from_block_number(block_number: u64, epoch_height: u64) -> u64 {
326    if epoch_height == 0 {
327        0
328    } else if block_number == 0 {
329        1
330    } else if block_number % epoch_height == 0 {
331        block_number / epoch_height
332    } else {
333        block_number / epoch_height + 1
334    }
335}
336
337/// Returns the block number of the epoch root in the given epoch
338///
339/// WARNING: This is NOT the root block for the given epoch.
340/// To find that root block number for epoch e, call `root_block_in_epoch(e-2,_)`.
341#[must_use]
342pub fn root_block_in_epoch(epoch: u64, epoch_height: u64) -> u64 {
343    if epoch_height == 0 || epoch < 1 {
344        0
345    } else {
346        epoch_height * epoch - 5
347    }
348}
349
350/// Get the block height of the transition block for the given epoch
351#[must_use]
352pub fn transition_block_for_epoch(epoch: u64, epoch_height: u64) -> u64 {
353    if epoch_height == 0 || epoch < 1 {
354        0
355    } else {
356        epoch_height * epoch - 3
357    }
358}
359
360/// Returns an `Option<Epoch>` based on a boolean condition of whether or not epochs are enabled, a block number,
361/// and the epoch height. If epochs are disabled or the epoch height is zero, returns None.
362#[must_use]
363pub fn option_epoch_from_block_number<TYPES: NodeType>(
364    with_epoch: bool,
365    block_number: u64,
366    epoch_height: u64,
367) -> Option<TYPES::Epoch> {
368    if with_epoch {
369        if epoch_height == 0 {
370            None
371        } else if block_number == 0 {
372            Some(1u64)
373        } else if block_number % epoch_height == 0 {
374            Some(block_number / epoch_height)
375        } else {
376            Some(block_number / epoch_height + 1)
377        }
378        .map(TYPES::Epoch::new)
379    } else {
380        None
381    }
382}
383
384/// Returns Some(1) if epochs are enabled by V::Base, otherwise returns None
385#[must_use]
386pub fn genesis_epoch_from_version<V: Versions, TYPES: NodeType>() -> Option<TYPES::Epoch> {
387    (V::Base::VERSION >= V::Epochs::VERSION).then(|| TYPES::Epoch::new(1))
388}
389
390/// A function for generating a cute little user mnemonic from a hash
391#[must_use]
392pub fn mnemonic<H: Hash>(bytes: H) -> String {
393    let mut state = std::collections::hash_map::DefaultHasher::new();
394    bytes.hash(&mut state);
395    mnemonic::to_string(state.finish().to_le_bytes())
396}
397
398/// A helper enum to indicate whether a node is in the epoch transition
399/// A node is in epoch transition when its high QC is for the last block in an epoch
400#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, Hash)]
401pub enum EpochTransitionIndicator {
402    /// A node is currently in the epoch transition
403    InTransition,
404    /// A node is not in the epoch transition
405    NotInTransition,
406}
407
408/// Return true if the given block number is the final full block, the "transition block"
409#[must_use]
410pub fn is_transition_block(block_number: u64, epoch_height: u64) -> bool {
411    if block_number == 0 || epoch_height == 0 {
412        false
413    } else {
414        (block_number + 3) % epoch_height == 0
415    }
416}
417/// returns true if it's the first transition block (epoch height - 2)
418#[must_use]
419pub fn is_first_transition_block(block_number: u64, epoch_height: u64) -> bool {
420    if block_number == 0 || epoch_height == 0 {
421        false
422    } else {
423        block_number % epoch_height == epoch_height - 2
424    }
425}
426/// Returns true if the block is part of the epoch transition (including the last non null block)  
427#[must_use]
428pub fn is_epoch_transition(block_number: u64, epoch_height: u64) -> bool {
429    if block_number == 0 || epoch_height == 0 {
430        false
431    } else {
432        block_number % epoch_height >= epoch_height - 3 || block_number % epoch_height == 0
433    }
434}
435
436/// Returns true if the block is the last block in the epoch
437#[must_use]
438pub fn is_last_block(block_number: u64, epoch_height: u64) -> bool {
439    if block_number == 0 || epoch_height == 0 {
440        false
441    } else {
442        block_number % epoch_height == 0
443    }
444}
445
446/// Returns true if the block number is in trasntion but not the transition block
447/// or the last block in the epoch.  
448///
449/// This function is useful for determining if a proposal extending this QC must follow
450/// the special rules for transition blocks.
451#[must_use]
452pub fn is_middle_transition_block(block_number: u64, epoch_height: u64) -> bool {
453    if block_number == 0 || epoch_height == 0 {
454        false
455    } else {
456        let blocks_left = epoch_height - (block_number % epoch_height);
457        blocks_left == 1 || blocks_left == 2
458    }
459}
460
461/// Returns true if the given block number is the third from the last in the epoch based on the
462/// given epoch height.
463#[must_use]
464pub fn is_epoch_root(block_number: u64, epoch_height: u64) -> bool {
465    if block_number == 0 || epoch_height == 0 {
466        false
467    } else {
468        (block_number + 5) % epoch_height == 0
469    }
470}
471
472/// Returns true if the given block number is equal or greater than the epoch root block
473#[must_use]
474pub fn is_ge_epoch_root(block_number: u64, epoch_height: u64) -> bool {
475    if block_number == 0 || epoch_height == 0 {
476        false
477    } else {
478        block_number % epoch_height >= epoch_height - 5
479    }
480}
481
482/// Returns true if the given block number is strictly greater than the epoch root block
483pub fn is_gt_epoch_root(block_number: u64, epoch_height: u64) -> bool {
484    if block_number == 0 || epoch_height == 0 {
485        false
486    } else {
487        block_number % epoch_height > epoch_height - 5
488    }
489}
490
491#[cfg(test)]
492mod test {
493    use super::*;
494
495    #[test]
496    fn test_epoch_from_block_number() {
497        // block 0 is always epoch 1
498        let epoch = epoch_from_block_number(0, 10);
499        assert_eq!(1, epoch);
500
501        let epoch = epoch_from_block_number(1, 10);
502        assert_eq!(1, epoch);
503
504        let epoch = epoch_from_block_number(10, 10);
505        assert_eq!(1, epoch);
506
507        let epoch = epoch_from_block_number(11, 10);
508        assert_eq!(2, epoch);
509
510        let epoch = epoch_from_block_number(20, 10);
511        assert_eq!(2, epoch);
512
513        let epoch = epoch_from_block_number(21, 10);
514        assert_eq!(3, epoch);
515
516        let epoch = epoch_from_block_number(21, 0);
517        assert_eq!(0, epoch);
518    }
519
520    #[test]
521    fn test_is_last_block_in_epoch() {
522        assert!(!is_epoch_transition(5, 10));
523        assert!(!is_epoch_transition(6, 10));
524        assert!(is_epoch_transition(7, 10));
525        assert!(is_epoch_transition(8, 10));
526        assert!(is_epoch_transition(9, 10));
527        assert!(is_epoch_transition(10, 10));
528        assert!(!is_epoch_transition(11, 10));
529
530        assert!(!is_epoch_transition(10, 0));
531    }
532
533    #[test]
534    fn test_is_epoch_root() {
535        assert!(is_epoch_root(5, 10));
536        assert!(!is_epoch_root(6, 10));
537        assert!(!is_epoch_root(7, 10));
538        assert!(!is_epoch_root(8, 10));
539        assert!(!is_epoch_root(9, 10));
540        assert!(!is_epoch_root(10, 10));
541        assert!(!is_epoch_root(11, 10));
542
543        assert!(!is_epoch_transition(10, 0));
544    }
545
546    #[test]
547    fn test_root_block_in_epoch() {
548        // block 0 is always epoch 0
549        let epoch = 3;
550        let epoch_height = 10;
551        let epoch_root_block_number = root_block_in_epoch(3, epoch_height);
552
553        assert!(is_epoch_root(25, epoch_height));
554
555        assert_eq!(epoch_root_block_number, 25);
556
557        assert_eq!(
558            epoch,
559            epoch_from_block_number(epoch_root_block_number, epoch_height)
560        );
561    }
562}
hotshot_types/utils.rs

hotshot_types/
utils.rs
