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    DefaultOptions, Options,
20    config::{
21        FixintEncoding, LittleEndian, RejectTrailing, WithOtherEndian, WithOtherIntEncoding,
22        WithOtherLimit, WithOtherTrailing,
23    },
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::Version;
32use versions::EPOCH_VERSION;
33
34use crate::{
35    PeerConfig,
36    data::{EpochNumber, Leaf2, VidCommitment, ViewNumber},
37    stake_table::StakeTableEntries,
38    traits::{ValidatedState, node_implementation::NodeType},
39    vote::{Certificate, HasViewNumber},
40};
41
42/// A view's state
43#[derive(Debug, Deserialize, Serialize, PartialEq, Eq)]
44#[serde(bound = "")]
45pub enum ViewInner<TYPES: NodeType> {
46    /// A pending view with an available block but not leaf proposal yet.
47    ///
48    /// Storing this state allows us to garbage collect blocks for views where a proposal is never
49    /// made. This saves memory when a leader fails and subverts a DoS attack where malicious
50    /// leaders repeatedly request availability for blocks that they never propose.
51    Da {
52        /// Payload commitment to the available block.
53        payload_commitment: VidCommitment,
54        /// An epoch to which the data belongs to. Relevant for validating against the correct stake table
55        epoch: Option<EpochNumber>,
56    },
57    /// Undecided view
58    Leaf {
59        /// Proposed leaf
60        leaf: LeafCommitment<TYPES>,
61        /// Validated state.
62        state: Arc<TYPES::ValidatedState>,
63        /// Optional state delta.
64        delta: Option<Arc<<TYPES::ValidatedState as ValidatedState<TYPES>>::Delta>>,
65        /// An epoch to which the data belongs to. Relevant for validating against the correct stake table
66        epoch: Option<EpochNumber>,
67    },
68    /// Leaf has failed
69    Failed,
70}
71impl<TYPES: NodeType> Clone for ViewInner<TYPES> {
72    fn clone(&self) -> Self {
73        match self {
74            Self::Da {
75                payload_commitment,
76                epoch,
77            } => Self::Da {
78                payload_commitment: *payload_commitment,
79                epoch: *epoch,
80            },
81            Self::Leaf {
82                leaf,
83                state,
84                delta,
85                epoch,
86            } => Self::Leaf {
87                leaf: *leaf,
88                state: Arc::clone(state),
89                delta: delta.clone(),
90                epoch: *epoch,
91            },
92            Self::Failed => Self::Failed,
93        }
94    }
95}
96/// The hash of a leaf.
97pub type LeafCommitment<TYPES> = Commitment<Leaf2<TYPES>>;
98
99/// Optional validated state and state delta.
100pub type StateAndDelta<TYPES> = (
101    Option<Arc<<TYPES as NodeType>::ValidatedState>>,
102    Option<Arc<<<TYPES as NodeType>::ValidatedState as ValidatedState<TYPES>>::Delta>>,
103);
104
105pub async fn verify_leaf_chain<T: NodeType>(
106    mut leaf_chain: Vec<Leaf2<T>>,
107    stake_table: &[PeerConfig<T>],
108    success_threshold: U256,
109    expected_height: u64,
110    upgrade_lock: &crate::message::UpgradeLock<T>,
111) -> anyhow::Result<Leaf2<T>> {
112    // Sort the leaf chain by view number
113    leaf_chain.sort_by_key(|l| l.view_number());
114    // Reverse it
115    leaf_chain.reverse();
116
117    // Check we actually have a chain long enough for deciding
118    if leaf_chain.len() < 3 {
119        return Err(anyhow!("Leaf chain is not long enough for a decide"));
120    }
121
122    let newest_leaf = leaf_chain.first().unwrap();
123    let parent = &leaf_chain[1];
124    let grand_parent = &leaf_chain[2];
125
126    // Check if the leaves form a decide
127    if newest_leaf.justify_qc().view_number() != parent.view_number()
128        || parent.justify_qc().view_number() != grand_parent.view_number()
129    {
130        return Err(anyhow!("Leaf views do not chain"));
131    }
132    if newest_leaf.justify_qc().data.leaf_commit != parent.commit()
133        || parent.justify_qc().data().leaf_commit != grand_parent.commit()
134    {
135        return Err(anyhow!("Leaf commits do not chain"));
136    }
137    if parent.view_number() != grand_parent.view_number() + 1 {
138        return Err(anyhow::anyhow!(
139            "Decide rule failed, parent does not directly extend grandparent"
140        ));
141    }
142
143    // Get the stake table entries
144    let stake_table_entries = StakeTableEntries::<T>::from(stake_table.to_vec()).0;
145
146    // verify all QCs are valid
147    newest_leaf
148        .justify_qc()
149        .is_valid_cert(&stake_table_entries, success_threshold, upgrade_lock)
150        .await?;
151    parent
152        .justify_qc()
153        .is_valid_cert(&stake_table_entries, success_threshold, upgrade_lock)
154        .await?;
155    grand_parent
156        .justify_qc()
157        .is_valid_cert(&stake_table_entries, success_threshold, upgrade_lock)
158        .await?;
159
160    // Verify the root is in the chain of decided leaves
161    let mut last_leaf = parent;
162    for leaf in leaf_chain.iter().skip(2) {
163        ensure!(last_leaf.justify_qc().view_number() == leaf.view_number());
164        ensure!(last_leaf.justify_qc().data().leaf_commit == leaf.commit());
165        leaf.justify_qc()
166            .is_valid_cert(&stake_table_entries, success_threshold, upgrade_lock)
167            .await?;
168        if leaf.height() == expected_height {
169            return Ok(leaf.clone());
170        }
171        last_leaf = leaf;
172    }
173    Err(anyhow!("Epoch Root was not found in the decided chain"))
174}
175
176impl<TYPES: NodeType> ViewInner<TYPES> {
177    /// Return the underlying undecide leaf commitment and validated state if they exist.
178    #[must_use]
179    pub fn leaf_and_state(&self) -> Option<(LeafCommitment<TYPES>, &Arc<TYPES::ValidatedState>)> {
180        if let Self::Leaf { leaf, state, .. } = self {
181            Some((*leaf, state))
182        } else {
183            None
184        }
185    }
186
187    /// return the underlying leaf hash if it exists
188    #[must_use]
189    pub fn leaf_commitment(&self) -> Option<LeafCommitment<TYPES>> {
190        if let Self::Leaf { leaf, .. } = self {
191            Some(*leaf)
192        } else {
193            None
194        }
195    }
196
197    /// return the underlying validated state if it exists
198    #[must_use]
199    pub fn state(&self) -> Option<&Arc<TYPES::ValidatedState>> {
200        if let Self::Leaf { state, .. } = self {
201            Some(state)
202        } else {
203            None
204        }
205    }
206
207    /// Return the underlying validated state and state delta if they exist.
208    #[must_use]
209    pub fn state_and_delta(&self) -> StateAndDelta<TYPES> {
210        if let Self::Leaf { state, delta, .. } = self {
211            (Some(Arc::clone(state)), delta.clone())
212        } else {
213            (None, None)
214        }
215    }
216
217    /// return the underlying block payload commitment if it exists
218    #[must_use]
219    pub fn payload_commitment(&self) -> Option<VidCommitment> {
220        if let Self::Da {
221            payload_commitment, ..
222        } = self
223        {
224            Some(*payload_commitment)
225        } else {
226            None
227        }
228    }
229
230    /// Returns `Epoch` if possible
231    // #3967 REVIEW NOTE: This type is kinda ugly, should we Result<Option<Epoch>> instead?
232    pub fn epoch(&self) -> Option<Option<EpochNumber>> {
233        match self {
234            Self::Da { epoch, .. } | Self::Leaf { epoch, .. } => Some(*epoch),
235            Self::Failed => None,
236        }
237    }
238}
239
240impl<TYPES: NodeType> Deref for View<TYPES> {
241    type Target = ViewInner<TYPES>;
242
243    fn deref(&self) -> &Self::Target {
244        &self.view_inner
245    }
246}
247
248/// This exists so we can perform state transitions mutably
249#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
250#[serde(bound = "")]
251pub struct View<TYPES: NodeType> {
252    /// The view data. Wrapped in a struct so we can mutate
253    pub view_inner: ViewInner<TYPES>,
254}
255
256/// A struct containing information about a finished round.
257#[derive(Debug, Clone)]
258pub struct RoundFinishedEvent {
259    /// The round that finished
260    pub view_number: ViewNumber,
261}
262
263/// Whether or not to stop inclusively or exclusively when walking
264#[derive(Copy, Clone, Debug)]
265pub enum Terminator<T> {
266    /// Stop right before this view number
267    Exclusive(T),
268    /// Stop including this view number
269    Inclusive(T),
270}
271
272/// Type alias for byte array of SHA256 digest length
273type Sha256Digest = [u8; <sha2::Sha256 as OutputSizeUser>::OutputSize::USIZE];
274
275#[tagged("BUILDER_COMMITMENT")]
276#[derive(Clone, Debug, Default, Hash, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
277/// Commitment that builders use to sign block options.
278/// A thin wrapper around a Sha256 digest.
279pub struct BuilderCommitment(Sha256Digest);
280
281impl BuilderCommitment {
282    /// Create new commitment for `data`
283    pub fn from_bytes(data: impl AsRef<[u8]>) -> Self {
284        Self(sha2::Sha256::digest(data.as_ref()).into())
285    }
286
287    /// Create a new commitment from a raw Sha256 digest
288    pub fn from_raw_digest(digest: impl Into<Sha256Digest>) -> Self {
289        Self(digest.into())
290    }
291}
292
293impl AsRef<Sha256Digest> for BuilderCommitment {
294    fn as_ref(&self) -> &Sha256Digest {
295        &self.0
296    }
297}
298
299type BincodeOpts = WithOtherTrailing<
300    WithOtherIntEncoding<
301        WithOtherEndian<WithOtherLimit<DefaultOptions, bincode::config::Infinite>, LittleEndian>,
302        FixintEncoding,
303    >,
304    RejectTrailing,
305>;
306
307/// For the wire format, we use bincode with the following options:
308///   - No upper size limit
309///   - Little endian encoding
310///   - Varint encoding
311///   - Reject trailing bytes
312#[must_use]
313pub fn bincode_opts() -> BincodeOpts {
314    bincode::DefaultOptions::new()
315        .with_no_limit()
316        .with_little_endian()
317        .with_fixint_encoding()
318        .reject_trailing_bytes()
319}
320
321/// Returns an epoch number given a block number and an epoch height
322#[must_use]
323pub fn epoch_from_block_number(block_number: u64, epoch_height: u64) -> u64 {
324    if epoch_height == 0 {
325        0
326    } else if block_number == 0 {
327        1
328    } else if block_number.is_multiple_of(epoch_height) {
329        block_number / epoch_height
330    } else {
331        block_number / epoch_height + 1
332    }
333}
334
335/// Returns the block number of the epoch root in the given epoch
336///
337/// WARNING: This is NOT the root block for the given epoch.
338/// To find that root block number for epoch e, call `root_block_in_epoch(e-2,_)`.
339#[must_use]
340pub fn root_block_in_epoch(epoch: u64, epoch_height: u64) -> u64 {
341    if epoch_height == 0 || epoch < 1 {
342        0
343    } else {
344        epoch_height * epoch - 5
345    }
346}
347
348/// Get the block height of the transition block for the given epoch
349///
350/// This is the height at which we begin the transition to LEAVE the specified 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(
364    with_epoch: bool,
365    block_number: u64,
366    epoch_height: u64,
367) -> Option<EpochNumber> {
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.is_multiple_of(epoch_height) {
374            Some(block_number / epoch_height)
375        } else {
376            Some(block_number / epoch_height + 1)
377        }
378        .map(EpochNumber::new)
379    } else {
380        None
381    }
382}
383
384/// Returns Some(1) if epochs are enabled by `base`, otherwise returns None
385#[must_use]
386pub fn genesis_epoch_from_version(base: Version) -> Option<EpochNumber> {
387    (base >= EPOCH_VERSION).then(|| EpochNumber::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).is_multiple_of(epoch_height)
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.is_multiple_of(epoch_height)
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.is_multiple_of(epoch_height)
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).is_multiple_of(epoch_height)
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.is_multiple_of(epoch_height) || 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.is_multiple_of(epoch_height) || 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
