espresso_types/v0/impls/
state.rs

1use std::ops::Add;
2
3use alloy::primitives::{Address, U256};
4use anyhow::{bail, Context};
5use committable::{Commitment, Committable};
6use hotshot_query_service::merklized_state::MerklizedState;
7use hotshot_types::{
8    data::{BlockError, ViewNumber},
9    traits::{
10        block_contents::BlockHeader, node_implementation::ConsensusTime,
11        signature_key::BuilderSignatureKey, states::StateDelta, ValidatedState as HotShotState,
12    },
13};
14use itertools::Itertools;
15use jf_merkle_tree::{
16    prelude::{MerkleProof, Sha3Digest, Sha3Node},
17    AppendableMerkleTreeScheme, ForgetableMerkleTreeScheme, ForgetableUniversalMerkleTreeScheme,
18    LookupResult, MerkleCommitment, MerkleTreeError, MerkleTreeScheme,
19    PersistentUniversalMerkleTreeScheme, UniversalMerkleTreeScheme,
20};
21use num_traits::CheckedSub;
22use serde::{Deserialize, Serialize};
23use thiserror::Error;
24use time::OffsetDateTime;
25use vbs::version::{StaticVersionType, Version};
26
27use super::{
28    fee_info::FeeError,
29    instance_state::NodeState,
30    reward::{find_validator_info, first_two_epochs},
31    v0_1::{
32        IterableFeeInfo, RewardAccount, RewardAmount, RewardMerkleCommitment, RewardMerkleTree,
33        REWARD_MERKLE_TREE_HEIGHT,
34    },
35    BlockMerkleCommitment, BlockSize, EpochVersion, FeeMerkleCommitment, L1Client,
36};
37use crate::{
38    traits::StateCatchup,
39    v0::impls::reward::RewardDistributor,
40    v0_3::{ChainConfig, ResolvableChainConfig},
41    BlockMerkleTree, Delta, FeeAccount, FeeAmount, FeeInfo, FeeMerkleTree, Header, Leaf2,
42    NsTableValidationError, PayloadByteLen, SeqTypes, UpgradeType, BLOCK_MERKLE_TREE_HEIGHT,
43    FEE_MERKLE_TREE_HEIGHT,
44};
45
46/// This enum is not used in code but functions as an index of
47/// possible validation errors.
48#[allow(dead_code)]
49pub enum StateValidationError {
50    ProposalValidation(ProposalValidationError),
51    BuilderValidation(BuilderValidationError),
52    Fee(FeeError),
53}
54
55/// Possible builder validation failures
56#[derive(Error, Debug, Eq, PartialEq)]
57pub enum BuilderValidationError {
58    #[error("Builder signature not found")]
59    SignatureNotFound,
60    #[error("Fee amount out of range: {0}")]
61    FeeAmountOutOfRange(FeeAmount),
62    #[error("Invalid Builder Signature")]
63    InvalidBuilderSignature,
64}
65
66/// Possible proposal validation failures
67#[derive(Error, Debug, Eq, PartialEq)]
68pub enum ProposalValidationError {
69    #[error("Invalid ChainConfig: expected={expected:?}, proposal={proposal:?}")]
70    InvalidChainConfig {
71        expected: Box<ChainConfig>,
72        proposal: Box<ResolvableChainConfig>,
73    },
74    #[error(
75        "Invalid Payload Size: (max_block_size={max_block_size}, proposed_block_size={block_size})"
76    )]
77    MaxBlockSizeExceeded {
78        max_block_size: BlockSize,
79        block_size: BlockSize,
80    },
81    #[error("Insufficient Fee: block_size={max_block_size}, base_fee={base_fee}, proposed_fee={proposed_fee}")]
82    InsufficientFee {
83        max_block_size: BlockSize,
84        base_fee: FeeAmount,
85        proposed_fee: FeeAmount,
86    },
87    #[error("Invalid Height: parent_height={parent_height}, proposal_height={proposal_height}")]
88    InvalidHeight {
89        parent_height: u64,
90        proposal_height: u64,
91    },
92    #[error("Invalid Block Root Error: expected={expected_root:?}, proposal={proposal_root:?}")]
93    InvalidBlockRoot {
94        expected_root: BlockMerkleCommitment,
95        proposal_root: BlockMerkleCommitment,
96    },
97    #[error("Invalid Fee Root Error: expected={expected_root:?}, proposal={proposal_root:?}")]
98    InvalidFeeRoot {
99        expected_root: FeeMerkleCommitment,
100        proposal_root: FeeMerkleCommitment,
101    },
102    #[error("Invalid Reward Root Error: expected={expected_root:?}, proposal={proposal_root:?}")]
103    InvalidRewardRoot {
104        expected_root: RewardMerkleCommitment,
105        proposal_root: RewardMerkleCommitment,
106    },
107    #[error("Invalid namespace table: {0}")]
108    InvalidNsTable(NsTableValidationError),
109    #[error("Some fee amount or their sum total out of range")]
110    SomeFeeAmountOutOfRange,
111    #[error("Invalid timestamp: proposal={proposal_timestamp}, parent={parent_timestamp}")]
112    DecrementingTimestamp {
113        proposal_timestamp: u64,
114        parent_timestamp: u64,
115    },
116    #[error("Timestamp drift too high: proposed:={proposal}, system={system}, diff={diff}")]
117    InvalidTimestampDrift {
118        proposal: u64,
119        system: u64,
120        diff: u64,
121    },
122    #[error("Inconsistent timestamps on header: timestamp:={timestamp}, timestamp_millis={timestamp_millis}")]
123    InconsistentTimestamps {
124        timestamp: u64,
125        timestamp_millis: u64,
126    },
127    #[error("l1_finalized has `None` value")]
128    L1FinalizedNotFound,
129    #[error("l1_finalized height is decreasing: parent={parent:?} proposed={proposed:?}")]
130    L1FinalizedDecrementing {
131        parent: Option<(u64, u64)>,
132        proposed: Option<(u64, u64)>,
133    },
134    #[error("Invalid proposal: l1_head height is decreasing")]
135    DecrementingL1Head,
136    #[error("Builder Validation Error: {0}")]
137    BuilderValidationError(BuilderValidationError),
138    #[error("Invalid proposal: l1 finalized does not match the proposal")]
139    InvalidL1Finalized,
140    #[error("reward root not found")]
141    RewardRootNotFound {},
142}
143
144impl StateDelta for Delta {}
145
146#[derive(Hash, Clone, Debug, Deserialize, Serialize, PartialEq, Eq)]
147/// State to be validated by replicas.
148pub struct ValidatedState {
149    /// Frontier of [`BlockMerkleTree`]
150    pub block_merkle_tree: BlockMerkleTree,
151    /// Frontier of [`FeeMerkleTree`]
152    pub fee_merkle_tree: FeeMerkleTree,
153    pub reward_merkle_tree: RewardMerkleTree,
154    /// Configuration [`Header`] proposals will be validated against.
155    pub chain_config: ResolvableChainConfig,
156}
157
158impl Default for ValidatedState {
159    fn default() -> Self {
160        let block_merkle_tree = BlockMerkleTree::from_elems(
161            Some(BLOCK_MERKLE_TREE_HEIGHT),
162            Vec::<Commitment<Header>>::new(),
163        )
164        .unwrap();
165
166        // Words of wisdom from @mrain: "capacity = arity^height"
167        // "For index space 2^160, arity 256 (2^8),
168        // you should set the height as 160/8=20"
169        let fee_merkle_tree = FeeMerkleTree::from_kv_set(
170            FEE_MERKLE_TREE_HEIGHT,
171            Vec::<(FeeAccount, FeeAmount)>::new(),
172        )
173        .unwrap();
174
175        let reward_merkle_tree = RewardMerkleTree::from_kv_set(
176            REWARD_MERKLE_TREE_HEIGHT,
177            Vec::<(RewardAccount, RewardAmount)>::new(),
178        )
179        .unwrap();
180
181        let chain_config = ResolvableChainConfig::from(ChainConfig::default());
182
183        Self {
184            block_merkle_tree,
185            fee_merkle_tree,
186            reward_merkle_tree,
187            chain_config,
188        }
189    }
190}
191
192impl ValidatedState {
193    /// Prefund an account with a given amount. Only for demo purposes.
194    pub fn prefund_account(&mut self, account: FeeAccount, amount: FeeAmount) {
195        self.fee_merkle_tree.update(account, amount).unwrap();
196    }
197
198    pub fn balance(&mut self, account: FeeAccount) -> Option<FeeAmount> {
199        match self.fee_merkle_tree.lookup(account) {
200            LookupResult::Ok(balance, _) => Some(*balance),
201            LookupResult::NotFound(_) => Some(0.into()),
202            LookupResult::NotInMemory => None,
203        }
204    }
205
206    /// Find accounts that are not in memory.
207    ///
208    /// As an optimization we could try to apply updates and return the
209    /// forgotten accounts to be fetched from peers and update them later.
210    pub fn forgotten_accounts(
211        &self,
212        accounts: impl IntoIterator<Item = FeeAccount>,
213    ) -> Vec<FeeAccount> {
214        accounts
215            .into_iter()
216            .unique()
217            .filter(|account| {
218                self.fee_merkle_tree
219                    .lookup(*account)
220                    .expect_not_in_memory()
221                    .is_ok()
222            })
223            .collect()
224    }
225
226    pub fn forgotten_reward_accounts(
227        &self,
228        accounts: impl IntoIterator<Item = RewardAccount>,
229    ) -> Vec<RewardAccount> {
230        accounts
231            .into_iter()
232            .unique()
233            .filter(|account| {
234                self.reward_merkle_tree
235                    .lookup(*account)
236                    .expect_not_in_memory()
237                    .is_ok()
238            })
239            .collect()
240    }
241
242    /// Check if the merkle tree is available
243    pub fn need_to_fetch_blocks_mt_frontier(&self) -> bool {
244        let num_leaves = self.block_merkle_tree.num_leaves();
245        if num_leaves == 0 {
246            false
247        } else {
248            self.block_merkle_tree
249                .lookup(num_leaves - 1)
250                .expect_ok()
251                .is_err()
252        }
253    }
254
255    /// Insert a fee deposit receipt
256    pub fn insert_fee_deposit(
257        &mut self,
258        fee_info: FeeInfo,
259    ) -> anyhow::Result<LookupResult<FeeAmount, (), ()>> {
260        Ok(self
261            .fee_merkle_tree
262            .update_with(fee_info.account, |balance| {
263                Some(balance.cloned().unwrap_or_default().add(fee_info.amount))
264            })?)
265    }
266
267    pub fn apply_proposal(
268        &mut self,
269        delta: &mut Delta,
270        parent_leaf: &Leaf2,
271        l1_deposits: Vec<FeeInfo>,
272    ) {
273        // pushing a block into merkle tree shouldn't fail
274        self.block_merkle_tree
275            .push(parent_leaf.block_header().commit())
276            .unwrap();
277
278        for FeeInfo { account, amount } in l1_deposits.iter() {
279            self.fee_merkle_tree
280                .update_with(account, |balance| {
281                    Some(balance.cloned().unwrap_or_default().add(*amount))
282                })
283                .expect("update_with succeeds");
284            delta.fees_delta.insert(*account);
285        }
286    }
287
288    pub fn charge_fees(
289        &mut self,
290        delta: &mut Delta,
291        fee_info: Vec<FeeInfo>,
292        recipient: FeeAccount,
293    ) -> Result<(), FeeError> {
294        for fee_info in fee_info {
295            self.charge_fee(fee_info, recipient)?;
296            delta.fees_delta.extend([fee_info.account, recipient]);
297        }
298        Ok(())
299    }
300
301    /// Charge a fee to an account, transferring the funds to the fee recipient account.
302    pub fn charge_fee(&mut self, fee_info: FeeInfo, recipient: FeeAccount) -> Result<(), FeeError> {
303        if fee_info.amount == 0.into() {
304            return Ok(());
305        }
306
307        let fee_state = self.fee_merkle_tree.clone();
308
309        // Deduct the fee from the paying account.
310        let FeeInfo { account, amount } = fee_info;
311        let mut err = None;
312        let fee_state = fee_state.persistent_update_with(account, |balance| {
313            let balance = balance.copied();
314            let Some(updated) = balance.unwrap_or_default().checked_sub(&amount) else {
315                // Return an error without updating the account.
316                err = Some(FeeError::InsufficientFunds { balance, amount });
317                return balance;
318            };
319            if updated == FeeAmount::default() {
320                // Delete the account from the tree if its balance ended up at 0; this saves some
321                // space since the account is no longer carrying any information.
322                None
323            } else {
324                // Otherwise store the updated balance.
325                Some(updated)
326            }
327        })?;
328
329        // Fail if there was an error during `persistent_update_with` (e.g. insufficient balance).
330        if let Some(err) = err {
331            return Err(err);
332        }
333
334        // If we successfully deducted the fee from the source account, increment the balance of the
335        // recipient account.
336        let fee_state = fee_state.persistent_update_with(recipient, |balance| {
337            Some(balance.copied().unwrap_or_default() + amount)
338        })?;
339
340        // If the whole update was successful, update the original state.
341        self.fee_merkle_tree = fee_state;
342        Ok(())
343    }
344}
345/// Block Proposal to be verified and applied.
346#[derive(Debug)]
347pub(crate) struct Proposal<'a> {
348    header: &'a Header,
349    block_size: u32,
350}
351
352impl<'a> Proposal<'a> {
353    pub(crate) fn new(header: &'a Header, block_size: u32) -> Self {
354        Self { header, block_size }
355    }
356    /// The L1 head block number in the proposal must be non-decreasing relative
357    /// to the parent.
358    fn validate_l1_head(&self, parent_l1_head: u64) -> Result<(), ProposalValidationError> {
359        if self.header.l1_head() < parent_l1_head {
360            return Err(ProposalValidationError::DecrementingL1Head);
361        }
362        Ok(())
363    }
364    /// The [`ChainConfig`] of proposal must be equal to the one stored in state.
365    ///
366    /// Equality is checked by comparing commitments.
367    fn validate_chain_config(
368        &self,
369        expected_chain_config: &ChainConfig,
370    ) -> Result<(), ProposalValidationError> {
371        let proposed_chain_config = self.header.chain_config();
372        if proposed_chain_config.commit() != expected_chain_config.commit() {
373            return Err(ProposalValidationError::InvalidChainConfig {
374                expected: Box::new(*expected_chain_config),
375                proposal: Box::new(proposed_chain_config),
376            });
377        }
378        Ok(())
379    }
380
381    /// The timestamp must be non-decreasing relative to parent.
382    fn validate_timestamp_non_dec(
383        &self,
384        parent_timestamp: u64,
385    ) -> Result<(), ProposalValidationError> {
386        if self.header.timestamp() < parent_timestamp {
387            return Err(ProposalValidationError::DecrementingTimestamp {
388                proposal_timestamp: self.header.timestamp(),
389                parent_timestamp,
390            });
391        }
392
393        Ok(())
394    }
395
396    /// The timestamp must not drift too much from local system time.
397    ///
398    /// The tolerance is currently `12` seconds. This value may be moved to
399    /// configuration in the future.
400    fn validate_timestamp_drift(&self, system_time: u64) -> Result<(), ProposalValidationError> {
401        // TODO 12 seconds of tolerance should be enough for reasonably
402        // configured nodes, but we should make this configurable.
403        let diff = self.header.timestamp().abs_diff(system_time);
404        if diff > 12 {
405            return Err(ProposalValidationError::InvalidTimestampDrift {
406                proposal: self.header.timestamp(),
407                system: system_time,
408                diff,
409            });
410        }
411
412        Ok(())
413    }
414
415    /// The `timestamp` and `timestamp_millis` fields must be coherent
416    fn validate_timestamp_consistency(&self) -> Result<(), ProposalValidationError> {
417        if self.header.timestamp() != self.header.timestamp_millis() / 1_000 {
418            return Err(ProposalValidationError::InconsistentTimestamps {
419                timestamp: self.header.timestamp(),
420                timestamp_millis: self.header.timestamp_millis(),
421            });
422        }
423
424        Ok(())
425    }
426
427    /// The proposed ['BlockMerkleTree'] must match the one in ['ValidatedState'].
428    fn validate_block_merkle_tree(
429        &self,
430        block_merkle_tree_root: BlockMerkleCommitment,
431    ) -> Result<(), ProposalValidationError> {
432        if self.header.block_merkle_tree_root() != block_merkle_tree_root {
433            return Err(ProposalValidationError::InvalidBlockRoot {
434                expected_root: block_merkle_tree_root,
435                proposal_root: self.header.block_merkle_tree_root(),
436            });
437        }
438
439        Ok(())
440    }
441}
442/// Type to hold cloned validated state and provide validation methods.
443///
444/// The [Self::validate] method must be called to validate the proposal.
445#[derive(Debug)]
446pub(crate) struct ValidatedTransition<'a> {
447    state: ValidatedState,
448    expected_chain_config: ChainConfig,
449    parent: &'a Header,
450    proposal: Proposal<'a>,
451}
452
453impl<'a> ValidatedTransition<'a> {
454    pub(crate) fn new(state: ValidatedState, parent: &'a Header, proposal: Proposal<'a>) -> Self {
455        let expected_chain_config = state
456            .chain_config
457            .resolve()
458            .expect("Chain Config not found in validated state");
459        Self {
460            state,
461            expected_chain_config,
462            parent,
463            proposal,
464        }
465    }
466
467    /// Top level validation routine. Performs all validation units in
468    /// the given order.
469    /// ```ignore
470    /// self.validate_timestamp()?;
471    /// self.validate_builder_fee()?;
472    /// self.validate_height()?;
473    /// self.validate_chain_config()?;
474    /// self.validate_block_size()?;
475    /// self.validate_fee()?;
476    /// self.validate_fee_merkle_tree()?;
477    /// self.validate_block_merkle_tree()?;
478    /// self.validate_l1_finalized()?;
479    /// self.validate_l1_head()?;
480    /// self.validate_namespace_table()?;
481    /// ```
482    pub(crate) fn validate(self) -> Result<Self, ProposalValidationError> {
483        self.validate_timestamp()?;
484        self.validate_builder_fee()?;
485        self.validate_height()?;
486        self.validate_chain_config()?;
487        self.validate_block_size()?;
488        self.validate_fee()?;
489        self.validate_fee_merkle_tree()?;
490        self.validate_block_merkle_tree()?;
491        self.validate_reward_merkle_tree()?;
492        self.validate_l1_finalized()?;
493        self.validate_l1_head()?;
494        self.validate_namespace_table()?;
495
496        Ok(self)
497    }
498
499    /// The proposal [Header::l1_finalized] must be `Some` and non-decreasing relative to parent.
500    fn validate_l1_finalized(&self) -> Result<(), ProposalValidationError> {
501        let proposed_finalized = self.proposal.header.l1_finalized();
502        let parent_finalized = self.parent.l1_finalized();
503
504        if proposed_finalized < parent_finalized {
505            // We are keeping the `Option` in the error b/c its the
506            // cleanest way to represent all the different error
507            // cases. The hash seems less useful and explodes the size
508            // of the error, so we strip it out.
509            return Err(ProposalValidationError::L1FinalizedDecrementing {
510                parent: parent_finalized.map(|block| (block.number, block.timestamp.to::<u64>())),
511                proposed: proposed_finalized
512                    .map(|block| (block.number, block.timestamp.to::<u64>())),
513            });
514        }
515        Ok(())
516    }
517    /// Wait for our view of the L1 chain to catch up to the proposal.
518    ///
519    /// The finalized [L1BlockInfo](super::L1BlockInfo) in the proposal must match the one fetched
520    /// from L1.
521    async fn wait_for_l1(self, l1_client: &L1Client) -> Result<Self, ProposalValidationError> {
522        self.wait_for_l1_head(l1_client).await;
523        self.wait_for_finalized_block(l1_client).await?;
524        Ok(self)
525    }
526
527    /// Wait for our view of the latest L1 block number to catch up to the
528    /// proposal.
529    async fn wait_for_l1_head(&self, l1_client: &L1Client) {
530        let _ = l1_client
531            .wait_for_block(self.proposal.header.l1_head())
532            .await;
533    }
534    /// Wait for our view of the finalized L1 block number to catch up to the
535    /// proposal.
536    async fn wait_for_finalized_block(
537        &self,
538        l1_client: &L1Client,
539    ) -> Result<(), ProposalValidationError> {
540        let proposed_finalized = self.proposal.header.l1_finalized();
541
542        if let Some(proposed_finalized) = proposed_finalized {
543            let finalized = l1_client
544                .wait_for_finalized_block(proposed_finalized.number())
545                .await;
546
547            if finalized != proposed_finalized {
548                return Err(ProposalValidationError::InvalidL1Finalized);
549            }
550        }
551
552        Ok(())
553    }
554
555    /// Ensure that L1 Head on proposal is not decreasing.
556    fn validate_l1_head(&self) -> Result<(), ProposalValidationError> {
557        self.proposal.validate_l1_head(self.parent.l1_head())?;
558        Ok(())
559    }
560    /// Validate basic numerical soundness and builder accounts by
561    /// verifying signatures. Signatures are identified by index of fee `Vec`.
562    fn validate_builder_fee(&self) -> Result<(), ProposalValidationError> {
563        // TODO move logic from stand alone fn to here.
564        if let Err(err) = validate_builder_fee(self.proposal.header) {
565            return Err(ProposalValidationError::BuilderValidationError(err));
566        }
567        Ok(())
568    }
569    /// Validates proposals [`ChainConfig`] against expectation by comparing commitments.
570    fn validate_chain_config(&self) -> Result<(), ProposalValidationError> {
571        self.proposal
572            .validate_chain_config(&self.expected_chain_config)?;
573        Ok(())
574    }
575    /// Validate that proposal block size does not exceed configured
576    /// `ChainConfig.max_block_size`.
577    fn validate_block_size(&self) -> Result<(), ProposalValidationError> {
578        let block_size = self.proposal.block_size as u64;
579        if block_size > *self.expected_chain_config.max_block_size {
580            return Err(ProposalValidationError::MaxBlockSizeExceeded {
581                max_block_size: self.expected_chain_config.max_block_size,
582                block_size: block_size.into(),
583            });
584        }
585        Ok(())
586    }
587    /// Validate that [`FeeAmount`] that is
588    /// sufficient for block size.
589    fn validate_fee(&self) -> Result<(), ProposalValidationError> {
590        // TODO this should be updated to `base_fee * bundle_size` when we have
591        // VID per bundle or namespace.
592        let Some(amount) = self.proposal.header.fee_info().amount() else {
593            return Err(ProposalValidationError::SomeFeeAmountOutOfRange);
594        };
595
596        if amount < self.expected_chain_config.base_fee * U256::from(self.proposal.block_size) {
597            return Err(ProposalValidationError::InsufficientFee {
598                max_block_size: self.expected_chain_config.max_block_size,
599                base_fee: self.expected_chain_config.base_fee,
600                proposed_fee: amount,
601            });
602        }
603        Ok(())
604    }
605    /// Validate that proposal height is `parent_height + 1`.
606    fn validate_height(&self) -> Result<(), ProposalValidationError> {
607        let parent_header = self.parent;
608        if self.proposal.header.height() != parent_header.height() + 1 {
609            return Err(ProposalValidationError::InvalidHeight {
610                parent_height: parent_header.height(),
611                proposal_height: self.proposal.header.height(),
612            });
613        }
614        Ok(())
615    }
616    /// Validate timestamp is not decreasing relative to parent and is
617    /// within a given tolerance of system time. Tolerance is
618    /// currently 12 seconds. This value may be moved to configuration
619    /// in the future. Do this check first so we don't add unnecessary drift.
620    fn validate_timestamp(&self) -> Result<(), ProposalValidationError> {
621        self.proposal.validate_timestamp_consistency()?;
622
623        self.proposal
624            .validate_timestamp_non_dec(self.parent.timestamp())?;
625
626        // Validate timestamp hasn't drifted too much from system time.
627        let system_time: u64 = OffsetDateTime::now_utc().unix_timestamp() as u64;
628        self.proposal.validate_timestamp_drift(system_time)?;
629
630        Ok(())
631    }
632    /// Validate [`BlockMerkleTree`] by comparing proposed commitment
633    /// that stored in [`ValidatedState`].
634    fn validate_block_merkle_tree(&self) -> Result<(), ProposalValidationError> {
635        let block_merkle_tree_root = self.state.block_merkle_tree.commitment();
636        self.proposal
637            .validate_block_merkle_tree(block_merkle_tree_root)?;
638
639        Ok(())
640    }
641
642    /// Validate [`RewardMerkleTree`] by comparing proposed commitment
643    /// against that stored in [`ValidatedState`].
644    fn validate_reward_merkle_tree(&self) -> Result<(), ProposalValidationError> {
645        let reward_merkle_tree_root = self.state.reward_merkle_tree.commitment();
646        if self.proposal.header.reward_merkle_tree_root() != reward_merkle_tree_root {
647            return Err(ProposalValidationError::InvalidRewardRoot {
648                expected_root: reward_merkle_tree_root,
649                proposal_root: self.proposal.header.reward_merkle_tree_root(),
650            });
651        }
652
653        Ok(())
654    }
655
656    /// Validate [`FeeMerkleTree`] by comparing proposed commitment
657    /// against that stored in [`ValidatedState`].
658    fn validate_fee_merkle_tree(&self) -> Result<(), ProposalValidationError> {
659        let fee_merkle_tree_root = self.state.fee_merkle_tree.commitment();
660        if self.proposal.header.fee_merkle_tree_root() != fee_merkle_tree_root {
661            return Err(ProposalValidationError::InvalidFeeRoot {
662                expected_root: fee_merkle_tree_root,
663                proposal_root: self.proposal.header.fee_merkle_tree_root(),
664            });
665        }
666
667        Ok(())
668    }
669    /// Proxy to [`super::NsTable::validate()`].
670    fn validate_namespace_table(&self) -> Result<(), ProposalValidationError> {
671        self.proposal
672            .header
673            .ns_table()
674            // Should be safe since `u32` will always fit in a `usize`.
675            .validate(&PayloadByteLen(self.proposal.block_size as usize))
676            .map_err(ProposalValidationError::from)
677    }
678}
679
680#[cfg(any(test, feature = "testing"))]
681impl ValidatedState {
682    pub fn forget(&self) -> Self {
683        Self {
684            fee_merkle_tree: FeeMerkleTree::from_commitment(self.fee_merkle_tree.commitment()),
685            block_merkle_tree: BlockMerkleTree::from_commitment(
686                self.block_merkle_tree.commitment(),
687            ),
688            reward_merkle_tree: RewardMerkleTree::from_commitment(
689                self.reward_merkle_tree.commitment(),
690            ),
691            chain_config: ResolvableChainConfig::from(self.chain_config.commit()),
692        }
693    }
694}
695
696impl From<NsTableValidationError> for ProposalValidationError {
697    fn from(err: NsTableValidationError) -> Self {
698        Self::InvalidNsTable(err)
699    }
700}
701
702impl From<ProposalValidationError> for BlockError {
703    fn from(err: ProposalValidationError) -> Self {
704        tracing::error!("Invalid Block Header: {err:#}");
705        BlockError::InvalidBlockHeader(err.to_string())
706    }
707}
708
709impl From<MerkleTreeError> for FeeError {
710    fn from(item: MerkleTreeError) -> Self {
711        Self::MerkleTreeError(item)
712    }
713}
714
715/// Validate builder accounts by verifying signatures. All fees are
716/// verified against signature by index.
717fn validate_builder_fee(proposed_header: &Header) -> Result<(), BuilderValidationError> {
718    // TODO since we are iterating, should we include account/amount in errors?
719    for (fee_info, signature) in proposed_header
720        .fee_info()
721        .iter()
722        .zip(proposed_header.builder_signature())
723    {
724        // check that `amount` fits in a u64
725        fee_info
726            .amount()
727            .as_u64()
728            .ok_or(BuilderValidationError::FeeAmountOutOfRange(fee_info.amount))?;
729
730        // Verify signatures.
731        if !fee_info.account().validate_fee_signature(
732            &signature,
733            fee_info.amount().as_u64().unwrap(),
734            proposed_header.metadata(),
735        ) && !fee_info
736            .account()
737            .validate_fee_signature_with_vid_commitment(
738                &signature,
739                fee_info.amount().as_u64().unwrap(),
740                proposed_header.metadata(),
741                &proposed_header.payload_commitment(),
742            )
743        {
744            return Err(BuilderValidationError::InvalidBuilderSignature);
745        }
746    }
747
748    Ok(())
749}
750
751impl ValidatedState {
752    /// Updates state with [`Header`] proposal.
753    ///   * Clones and updates [`ValidatedState`] (avoiding mutation).
754    ///   * Resolves [`ChainConfig`].
755    ///   * Performs catchup.
756    ///   * Charges fees.
757    pub async fn apply_header(
758        &self,
759        instance: &NodeState,
760        peers: &impl StateCatchup,
761        parent_leaf: &Leaf2,
762        proposed_header: &Header,
763        version: Version,
764        view_number: ViewNumber,
765    ) -> anyhow::Result<(Self, Delta)> {
766        // Clone state to avoid mutation. Consumer can take update
767        // through returned value.
768        let mut validated_state = self.clone();
769        validated_state.apply_upgrade(instance, version);
770
771        // TODO double check there is not some possibility we are
772        // validating proposal values against ChainConfig of the proposal.
773        let chain_config = validated_state
774            .get_chain_config(instance, peers, &proposed_header.chain_config())
775            .await?;
776
777        if Some(chain_config) != validated_state.chain_config.resolve() {
778            validated_state.chain_config = chain_config.into();
779        }
780
781        let l1_deposits = get_l1_deposits(
782            instance,
783            proposed_header,
784            parent_leaf,
785            chain_config.fee_contract,
786        )
787        .await;
788
789        // Find missing fee state entries. We will need to use the builder account which is paying a
790        // fee and the recipient account which is receiving it, plus any counts receiving deposits
791        // in this block.
792        let missing_accounts = self.forgotten_accounts(
793            [chain_config.fee_recipient]
794                .into_iter()
795                .chain(proposed_header.fee_info().accounts())
796                .chain(l1_deposits.accounts()),
797        );
798
799        let parent_height = parent_leaf.height();
800        let parent_view = parent_leaf.view_number();
801
802        // Ensure merkle tree has frontier
803        if self.need_to_fetch_blocks_mt_frontier() {
804            tracing::info!(
805                parent_height,
806                ?parent_view,
807                "fetching block frontier from peers"
808            );
809            peers
810                .remember_blocks_merkle_tree(
811                    instance,
812                    parent_height,
813                    parent_view,
814                    &mut validated_state.block_merkle_tree,
815                )
816                .await?;
817        }
818
819        // Fetch missing fee state entries
820        if !missing_accounts.is_empty() {
821            tracing::info!(
822                parent_height,
823                ?parent_view,
824                ?missing_accounts,
825                "fetching missing accounts from peers"
826            );
827
828            let missing_account_proofs = peers
829                .fetch_accounts(
830                    instance,
831                    parent_height,
832                    parent_view,
833                    validated_state.fee_merkle_tree.commitment(),
834                    missing_accounts,
835                )
836                .await?;
837
838            // Remember the fee state entries
839            for proof in missing_account_proofs.iter() {
840                proof
841                    .remember(&mut validated_state.fee_merkle_tree)
842                    .expect("proof previously verified");
843            }
844        }
845
846        let mut delta = Delta::default();
847        validated_state.apply_proposal(&mut delta, parent_leaf, l1_deposits);
848
849        validated_state.charge_fees(
850            &mut delta,
851            proposed_header.fee_info(),
852            chain_config.fee_recipient,
853        )?;
854
855        if version >= EpochVersion::version()
856            && !first_two_epochs(parent_leaf.height() + 1, instance).await?
857        {
858            let validator =
859                find_validator_info(instance, &mut validated_state, parent_leaf, view_number)
860                    .await?;
861
862            let block_reward = instance.block_reward().await;
863            let reward_distributor = RewardDistributor::new(validator, block_reward);
864            // apply rewards
865            reward_distributor
866                .distribute(&mut validated_state, &mut delta)
867                .context("failed to distribute rewards")?;
868        }
869
870        Ok((validated_state, delta))
871    }
872
873    /// Updates the `ValidatedState` if a protocol upgrade has occurred.
874    pub(crate) fn apply_upgrade(&mut self, instance: &NodeState, version: Version) {
875        // Check for protocol upgrade based on sequencer version
876        if version <= instance.current_version {
877            return;
878        }
879
880        let Some(upgrade) = instance.upgrades.get(&version) else {
881            return;
882        };
883
884        let cf = match upgrade.upgrade_type {
885            UpgradeType::Fee { chain_config } => chain_config,
886            UpgradeType::Epoch { chain_config } => chain_config,
887            UpgradeType::DrbAndHeader { chain_config } => chain_config,
888        };
889
890        self.chain_config = cf.into();
891    }
892
893    /// Retrieves the `ChainConfig`.
894    ///
895    ///  Returns the `NodeState` `ChainConfig` if the `ValidatedState` `ChainConfig` commitment matches the `NodeState` `ChainConfig`` commitment.
896    ///  If the commitments do not match, it returns the `ChainConfig` available in either `ValidatedState` or proposed header.
897    ///  If neither has the `ChainConfig`, it fetches the config from the peers.
898    ///
899    /// Returns an error if it fails to fetch the `ChainConfig` from the peers.
900    pub(crate) async fn get_chain_config(
901        &self,
902        instance: &NodeState,
903        peers: &impl StateCatchup,
904        header_cf: &ResolvableChainConfig,
905    ) -> anyhow::Result<ChainConfig> {
906        let state_cf = self.chain_config;
907
908        if state_cf.commit() == instance.chain_config.commit() {
909            return Ok(instance.chain_config);
910        }
911
912        let cf = match (state_cf.resolve(), header_cf.resolve()) {
913            (Some(cf), _) => cf,
914            (_, Some(cf)) if cf.commit() == state_cf.commit() => cf,
915            (_, Some(_)) | (None, None) => peers.fetch_chain_config(state_cf.commit()).await?,
916        };
917
918        Ok(cf)
919    }
920}
921
922pub async fn get_l1_deposits(
923    instance: &NodeState,
924    header: &Header,
925    parent_leaf: &Leaf2,
926    fee_contract_address: Option<Address>,
927) -> Vec<FeeInfo> {
928    if let (Some(addr), Some(block_info)) = (fee_contract_address, header.l1_finalized()) {
929        instance
930            .l1_client
931            .get_finalized_deposits(
932                addr,
933                parent_leaf
934                    .block_header()
935                    .l1_finalized()
936                    .map(|block_info| block_info.number),
937                block_info.number,
938            )
939            .await
940    } else {
941        vec![]
942    }
943}
944
945impl HotShotState<SeqTypes> for ValidatedState {
946    type Error = BlockError;
947    type Instance = NodeState;
948
949    type Time = ViewNumber;
950
951    type Delta = Delta;
952    fn on_commit(&self) {}
953    /// Validate parent against known values (from state) and validate
954    /// proposal descends from parent. Returns updated `ValidatedState`.
955    #[tracing::instrument(
956        skip_all,
957        fields(
958            node_id = instance.node_id,
959            view = ?parent_leaf.view_number(),
960            height = parent_leaf.height(),
961        ),
962    )]
963    async fn validate_and_apply_header(
964        &self,
965        instance: &Self::Instance,
966        parent_leaf: &Leaf2,
967        proposed_header: &Header,
968        payload_byte_len: u32,
969        version: Version,
970        view_number: u64,
971    ) -> Result<(Self, Self::Delta), Self::Error> {
972        let (validated_state, delta) = self
973            // TODO We can add this logic to `ValidatedTransition` or do something similar to that here.
974            .apply_header(
975                instance,
976                &instance.state_catchup,
977                parent_leaf,
978                proposed_header,
979                version,
980                ViewNumber::new(view_number),
981            )
982            .await
983            .map_err(|e| BlockError::FailedHeaderApply(e.to_string()))?;
984
985        // Validate the proposal.
986        let validated_state = ValidatedTransition::new(
987            validated_state,
988            parent_leaf.block_header(),
989            Proposal::new(proposed_header, payload_byte_len),
990        )
991        .validate()?
992        .wait_for_l1(&instance.l1_client)
993        .await?
994        .state;
995
996        // log successful progress about once in 10 - 20 seconds,
997        // TODO: we may want to make this configurable
998        if parent_leaf.view_number().u64() % 10 == 0 {
999            tracing::info!("validated and applied new header");
1000        }
1001        Ok((validated_state, delta))
1002    }
1003    /// Construct the state with the given block header.
1004    ///
1005    /// This can also be used to rebuild the state for catchup.
1006    fn from_header(block_header: &Header) -> Self {
1007        let fee_merkle_tree = if block_header.fee_merkle_tree_root().size() == 0 {
1008            // If the commitment tells us that the tree is supposed to be empty, it is convenient to
1009            // just create an empty tree, rather than a commitment-only tree.
1010            FeeMerkleTree::new(FEE_MERKLE_TREE_HEIGHT)
1011        } else {
1012            FeeMerkleTree::from_commitment(block_header.fee_merkle_tree_root())
1013        };
1014        let block_merkle_tree = if block_header.block_merkle_tree_root().size() == 0 {
1015            // If the commitment tells us that the tree is supposed to be empty, it is convenient to
1016            // just create an empty tree, rather than a commitment-only tree.
1017            BlockMerkleTree::new(BLOCK_MERKLE_TREE_HEIGHT)
1018        } else {
1019            BlockMerkleTree::from_commitment(block_header.block_merkle_tree_root())
1020        };
1021
1022        let reward_merkle_tree = if block_header.reward_merkle_tree_root().size() == 0 {
1023            RewardMerkleTree::new(REWARD_MERKLE_TREE_HEIGHT)
1024        } else {
1025            RewardMerkleTree::from_commitment(block_header.reward_merkle_tree_root())
1026        };
1027
1028        Self {
1029            fee_merkle_tree,
1030            block_merkle_tree,
1031            reward_merkle_tree,
1032            chain_config: block_header.chain_config(),
1033        }
1034    }
1035    /// Construct a genesis validated state.
1036    fn genesis(instance: &Self::Instance) -> (Self, Self::Delta) {
1037        (instance.genesis_state.clone(), Delta::default())
1038    }
1039}
1040
1041// Required for TestableState
1042#[cfg(any(test, feature = "testing"))]
1043impl std::fmt::Display for ValidatedState {
1044    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1045        write!(f, "{self:#?}")
1046    }
1047}
1048
1049#[cfg(any(test, feature = "testing"))]
1050impl hotshot_types::traits::states::TestableState<SeqTypes> for ValidatedState {
1051    fn create_random_transaction(
1052        _state: Option<&Self>,
1053        rng: &mut dyn rand::RngCore,
1054        _padding: u64,
1055    ) -> crate::Transaction {
1056        crate::Transaction::random(rng)
1057    }
1058}
1059
1060impl MerklizedState<SeqTypes, { Self::ARITY }> for BlockMerkleTree {
1061    type Key = Self::Index;
1062    type Entry = Commitment<Header>;
1063    type T = Sha3Node;
1064    type Commit = Self::Commitment;
1065    type Digest = Sha3Digest;
1066
1067    fn state_type() -> &'static str {
1068        "block_merkle_tree"
1069    }
1070
1071    fn header_state_commitment_field() -> &'static str {
1072        "block_merkle_tree_root"
1073    }
1074
1075    fn tree_height() -> usize {
1076        BLOCK_MERKLE_TREE_HEIGHT
1077    }
1078
1079    fn insert_path(
1080        &mut self,
1081        key: Self::Key,
1082        proof: &MerkleProof<Self::Entry, Self::Key, Self::T, { Self::ARITY }>,
1083    ) -> anyhow::Result<()> {
1084        let Some(elem) = proof.elem() else {
1085            bail!("BlockMerkleTree does not support non-membership proofs");
1086        };
1087        self.remember(key, elem, proof)?;
1088        Ok(())
1089    }
1090}
1091
1092impl MerklizedState<SeqTypes, { Self::ARITY }> for FeeMerkleTree {
1093    type Key = Self::Index;
1094    type Entry = Self::Element;
1095    type T = Sha3Node;
1096    type Commit = Self::Commitment;
1097    type Digest = Sha3Digest;
1098
1099    fn state_type() -> &'static str {
1100        "fee_merkle_tree"
1101    }
1102
1103    fn header_state_commitment_field() -> &'static str {
1104        "fee_merkle_tree_root"
1105    }
1106
1107    fn tree_height() -> usize {
1108        FEE_MERKLE_TREE_HEIGHT
1109    }
1110
1111    fn insert_path(
1112        &mut self,
1113        key: Self::Key,
1114        proof: &MerkleProof<Self::Entry, Self::Key, Self::T, { Self::ARITY }>,
1115    ) -> anyhow::Result<()> {
1116        match proof.elem() {
1117            Some(elem) => self.remember(key, elem, proof)?,
1118            None => self.non_membership_remember(key, proof)?,
1119        }
1120        Ok(())
1121    }
1122}
1123
1124impl MerklizedState<SeqTypes, { Self::ARITY }> for RewardMerkleTree {
1125    type Key = Self::Index;
1126    type Entry = Self::Element;
1127    type T = Sha3Node;
1128    type Commit = Self::Commitment;
1129    type Digest = Sha3Digest;
1130
1131    fn state_type() -> &'static str {
1132        "reward_merkle_tree"
1133    }
1134
1135    fn header_state_commitment_field() -> &'static str {
1136        "reward_merkle_tree_root"
1137    }
1138
1139    fn tree_height() -> usize {
1140        REWARD_MERKLE_TREE_HEIGHT
1141    }
1142
1143    fn insert_path(
1144        &mut self,
1145        key: Self::Key,
1146        proof: &MerkleProof<Self::Entry, Self::Key, Self::T, { Self::ARITY }>,
1147    ) -> anyhow::Result<()> {
1148        match proof.elem() {
1149            Some(elem) => self.remember(key, elem, proof)?,
1150            None => self.non_membership_remember(key, proof)?,
1151        }
1152        Ok(())
1153    }
1154}
1155
1156#[cfg(test)]
1157mod test {
1158    use hotshot::{helpers::initialize_logging, traits::BlockPayload};
1159    use hotshot_query_service::{testing::mocks::MockVersions, Resolvable};
1160    use hotshot_types::traits::signature_key::BuilderSignatureKey;
1161    use sequencer_utils::ser::FromStringOrInteger;
1162    use tracing::debug;
1163
1164    use super::*;
1165    use crate::{
1166        eth_signature_key::EthKeyPair, v0_1, v0_2, v0_3, v0_4, BlockSize, FeeAccountProof,
1167        FeeMerkleProof, Leaf, Payload, TimestampMillis, Transaction,
1168    };
1169
1170    impl Transaction {
1171        async fn into_mock_header(self) -> (Header, u32) {
1172            let instance = NodeState::mock_v2();
1173            let (payload, metadata) =
1174                Payload::from_transactions([self], &instance.genesis_state, &instance)
1175                    .await
1176                    .unwrap();
1177
1178            let header = Header::genesis::<MockVersions>(&instance, payload.clone(), &metadata);
1179
1180            let header = header.sign();
1181
1182            (header, payload.byte_len().0 as u32)
1183        }
1184    }
1185    impl Header {
1186        /// Build a new header from parent.
1187        fn next(self) -> Self {
1188            let time = OffsetDateTime::now_utc();
1189            let timestamp = time.unix_timestamp() as u64;
1190            let timestamp_millis = TimestampMillis::from_time(&time);
1191
1192            match self {
1193                Header::V1(_) => panic!("You called `Header.next()` on unimplemented version (v1)"),
1194                Header::V2(parent) => Header::V2(v0_2::Header {
1195                    height: parent.height + 1,
1196                    timestamp,
1197                    ..parent.clone()
1198                }),
1199                Header::V3(parent) => Header::V3(v0_3::Header {
1200                    height: parent.height + 1,
1201                    timestamp,
1202                    ..parent.clone()
1203                }),
1204                Header::V4(parent) => Header::V4(v0_4::Header {
1205                    height: parent.height + 1,
1206                    timestamp,
1207                    timestamp_millis,
1208                    ..parent.clone()
1209                }),
1210            }
1211        }
1212        /// Replaces builder signature w/ invalid one.
1213        fn sign(&self) -> Self {
1214            let key_pair = EthKeyPair::random();
1215            let fee_info = FeeInfo::new(key_pair.fee_account(), 1);
1216
1217            let sig = FeeAccount::sign_fee(
1218                &key_pair,
1219                fee_info.amount().as_u64().unwrap(),
1220                self.metadata(),
1221            )
1222            .unwrap();
1223
1224            match self {
1225                Header::V1(_) => panic!("You called `Header.sign()` on unimplemented version (v1)"),
1226                Header::V2(header) => Header::V2(v0_2::Header {
1227                    fee_info,
1228                    builder_signature: Some(sig),
1229                    ..header.clone()
1230                }),
1231                Header::V3(header) => Header::V3(v0_3::Header {
1232                    fee_info,
1233                    builder_signature: Some(sig),
1234                    ..header.clone()
1235                }),
1236                Header::V4(header) => Header::V4(v0_4::Header {
1237                    fee_info,
1238                    builder_signature: Some(sig),
1239                    ..header.clone()
1240                }),
1241            }
1242        }
1243
1244        /// Replaces builder signature w/ invalid one.
1245        fn invalid_builder_signature(&self) -> Self {
1246            let key_pair = EthKeyPair::random();
1247            let key_pair2 = EthKeyPair::random();
1248            let fee_info = FeeInfo::new(key_pair.fee_account(), 1);
1249
1250            let sig = FeeAccount::sign_fee(
1251                &key_pair2,
1252                fee_info.amount().as_u64().unwrap(),
1253                self.metadata(),
1254            )
1255            .unwrap();
1256
1257            match self {
1258                Header::V1(_) => panic!(
1259                    "You called `Header.invalid_builder_signature()` on unimplemented version (v1)"
1260                ),
1261                Header::V2(parent) => Header::V2(v0_2::Header {
1262                    fee_info,
1263                    builder_signature: Some(sig),
1264                    ..parent.clone()
1265                }),
1266                Header::V3(parent) => Header::V3(v0_3::Header {
1267                    fee_info,
1268                    builder_signature: Some(sig),
1269                    ..parent.clone()
1270                }),
1271                Header::V4(parent) => Header::V4(v0_4::Header {
1272                    fee_info,
1273                    builder_signature: Some(sig),
1274                    ..parent.clone()
1275                }),
1276            }
1277        }
1278    }
1279
1280    impl<'a> ValidatedTransition<'a> {
1281        fn mock(instance: NodeState, parent: &'a Header, proposal: Proposal<'a>) -> Self {
1282            let expected_chain_config = instance.chain_config;
1283
1284            Self {
1285                state: instance.genesis_state,
1286                expected_chain_config,
1287                parent,
1288                proposal,
1289            }
1290        }
1291    }
1292
1293    #[test]
1294    fn test_fee_proofs() {
1295        initialize_logging();
1296
1297        let mut tree = ValidatedState::default().fee_merkle_tree;
1298        let account1 = Address::random();
1299        let account2 = Address::default();
1300        tracing::info!(%account1, %account2);
1301
1302        let balance1 = U256::from(100);
1303        tree.update(FeeAccount(account1), FeeAmount(balance1))
1304            .unwrap();
1305
1306        // Membership proof.
1307        let (proof1, balance) = FeeAccountProof::prove(&tree, account1).unwrap();
1308        tracing::info!(?proof1, %balance);
1309        assert_eq!(balance, balance1);
1310        assert!(matches!(proof1.proof, FeeMerkleProof::Presence(_)));
1311        assert_eq!(proof1.verify(&tree.commitment()).unwrap(), balance1);
1312
1313        // Non-membership proof.
1314        let (proof2, balance) = FeeAccountProof::prove(&tree, account2).unwrap();
1315        tracing::info!(?proof2, %balance);
1316        assert_eq!(balance, U256::ZERO);
1317        assert!(matches!(proof2.proof, FeeMerkleProof::Absence(_)));
1318        assert_eq!(proof2.verify(&tree.commitment()).unwrap(), U256::ZERO);
1319
1320        // Test forget/remember. We cannot generate proofs in a completely sparse tree:
1321        let mut tree = FeeMerkleTree::from_commitment(tree.commitment());
1322        assert!(FeeAccountProof::prove(&tree, account1).is_none());
1323        assert!(FeeAccountProof::prove(&tree, account2).is_none());
1324        // After remembering the proofs, we can generate proofs again:
1325        proof1.remember(&mut tree).unwrap();
1326        proof2.remember(&mut tree).unwrap();
1327        FeeAccountProof::prove(&tree, account1).unwrap();
1328        FeeAccountProof::prove(&tree, account2).unwrap();
1329    }
1330
1331    #[tokio::test(flavor = "multi_thread")]
1332    async fn test_validation_l1_head() {
1333        initialize_logging();
1334
1335        // Setup.
1336        let tx = Transaction::of_size(10);
1337        let (header, block_size) = tx.into_mock_header().await;
1338
1339        // Success Case
1340        let proposal = Proposal::new(&header, block_size);
1341        // Note we are using the same header for parent and proposal,
1342        // this may be OK depending on what we are testing.
1343        ValidatedTransition::mock(NodeState::mock_v2(), &header, proposal)
1344            .validate_l1_head()
1345            .unwrap();
1346
1347        // Error Case
1348        let proposal = Proposal::new(&header, block_size);
1349        let err = proposal.validate_l1_head(u64::MAX).unwrap_err();
1350        assert_eq!(ProposalValidationError::DecrementingL1Head, err);
1351    }
1352
1353    #[tokio::test(flavor = "multi_thread")]
1354    async fn test_validation_builder_fee() {
1355        initialize_logging();
1356
1357        // Setup.
1358        let instance = NodeState::mock();
1359        let tx = Transaction::of_size(20);
1360        let (header, block_size) = tx.into_mock_header().await;
1361
1362        // Success Case
1363        let proposal = Proposal::new(&header, block_size);
1364        ValidatedTransition::mock(instance.clone(), &header, proposal)
1365            .validate_builder_fee()
1366            .unwrap();
1367
1368        // Error Case
1369        let header = header.invalid_builder_signature();
1370        let proposal = Proposal::new(&header, block_size);
1371        let err = ValidatedTransition::mock(instance, &header, proposal)
1372            .validate_builder_fee()
1373            .unwrap_err();
1374
1375        tracing::info!(%err, "task failed successfully");
1376        assert_eq!(
1377            ProposalValidationError::BuilderValidationError(
1378                BuilderValidationError::InvalidBuilderSignature
1379            ),
1380            err
1381        );
1382    }
1383
1384    #[tokio::test(flavor = "multi_thread")]
1385    async fn test_validation_chain_config() {
1386        initialize_logging();
1387
1388        // Setup.
1389        let instance = NodeState::mock();
1390        let tx = Transaction::of_size(20);
1391        let (header, block_size) = tx.into_mock_header().await;
1392
1393        // Success Case
1394        let proposal = Proposal::new(&header, block_size);
1395        ValidatedTransition::mock(instance.clone(), &header, proposal)
1396            .validate_chain_config()
1397            .unwrap();
1398
1399        // Error Case
1400        let proposal = Proposal::new(&header, block_size);
1401        let expected_chain_config = ChainConfig {
1402            max_block_size: BlockSize(3333),
1403            ..instance.chain_config
1404        };
1405        let err = proposal
1406            .validate_chain_config(&expected_chain_config)
1407            .unwrap_err();
1408
1409        tracing::info!(%err, "task failed successfully");
1410
1411        assert_eq!(
1412            ProposalValidationError::InvalidChainConfig {
1413                expected: Box::new(expected_chain_config),
1414                proposal: Box::new(header.chain_config())
1415            },
1416            err
1417        );
1418    }
1419
1420    #[tokio::test(flavor = "multi_thread")]
1421    async fn test_validation_max_block_size() {
1422        initialize_logging();
1423        const MAX_BLOCK_SIZE: usize = 10;
1424
1425        // Setup.
1426        let state = ValidatedState::default();
1427        let expected_chain_config = ChainConfig {
1428            max_block_size: BlockSize::from_integer(MAX_BLOCK_SIZE as u64).unwrap(),
1429            ..state.chain_config.resolve().unwrap()
1430        };
1431        let instance = NodeState::mock().with_chain_config(expected_chain_config);
1432        let tx = Transaction::of_size(20);
1433        let (header, block_size) = tx.into_mock_header().await;
1434
1435        // Error Case
1436        let proposal = Proposal::new(&header, block_size);
1437        let err = ValidatedTransition::mock(instance.clone(), &header, proposal)
1438            .validate_block_size()
1439            .unwrap_err();
1440
1441        tracing::info!(%err, "task failed successfully");
1442        assert_eq!(
1443            ProposalValidationError::MaxBlockSizeExceeded {
1444                max_block_size: instance.chain_config.max_block_size,
1445                block_size: BlockSize::from_integer(block_size as u64).unwrap()
1446            },
1447            err
1448        );
1449
1450        // Success Case
1451        let proposal = Proposal::new(&header, 1);
1452        ValidatedTransition::mock(instance, &header, proposal)
1453            .validate_block_size()
1454            .unwrap()
1455    }
1456
1457    #[tokio::test(flavor = "multi_thread")]
1458    async fn test_validation_base_fee() {
1459        initialize_logging();
1460        // Setup
1461        let tx = Transaction::of_size(20);
1462        let (header, block_size) = tx.into_mock_header().await;
1463        let state = ValidatedState::default();
1464        let instance = NodeState::mock_v2().with_chain_config(ChainConfig {
1465            base_fee: 1000.into(), // High expected base fee
1466            ..state.chain_config.resolve().unwrap()
1467        });
1468
1469        let proposal = Proposal::new(&header, block_size);
1470        let err = ValidatedTransition::mock(instance.clone(), &header, proposal)
1471            .validate_fee()
1472            .unwrap_err();
1473
1474        // Validation fails because the genesis fee (0) is too low.
1475        tracing::info!(%err, "task failed successfully");
1476        assert_eq!(
1477            ProposalValidationError::InsufficientFee {
1478                max_block_size: instance.chain_config.max_block_size,
1479                base_fee: instance.chain_config.base_fee,
1480                proposed_fee: header.fee_info().amount().unwrap()
1481            },
1482            err
1483        );
1484    }
1485
1486    #[tokio::test(flavor = "multi_thread")]
1487    async fn test_validation_height() {
1488        initialize_logging();
1489        // Setup
1490        let instance = NodeState::mock_v2();
1491        let tx = Transaction::of_size(10);
1492        let (parent, block_size) = tx.into_mock_header().await;
1493
1494        let proposal = Proposal::new(&parent, block_size);
1495        let err = ValidatedTransition::mock(instance.clone(), &parent, proposal)
1496            .validate_height()
1497            .unwrap_err();
1498
1499        // Validation fails because the proposal is using same default.
1500        tracing::info!(%err, "task failed successfully");
1501        assert_eq!(
1502            ProposalValidationError::InvalidHeight {
1503                parent_height: parent.height(),
1504                proposal_height: parent.height()
1505            },
1506            err
1507        );
1508
1509        // Success case. Increment height on proposal.
1510        let mut header = parent.clone();
1511        *header.height_mut() += 1;
1512        let proposal = Proposal::new(&header, block_size);
1513
1514        ValidatedTransition::mock(instance, &parent, proposal)
1515            .validate_height()
1516            .unwrap();
1517    }
1518
1519    #[tokio::test(flavor = "multi_thread")]
1520    async fn test_validation_timestamp_non_dec() {
1521        initialize_logging();
1522        let tx = Transaction::of_size(10);
1523        let (parent, block_size) = tx.into_mock_header().await;
1524
1525        // Error case
1526        let proposal = Proposal::new(&parent, block_size);
1527        let proposal_timestamp = proposal.header.timestamp();
1528        let err = proposal.validate_timestamp_non_dec(u64::MAX).unwrap_err();
1529
1530        // Validation fails because the proposal is using same default.
1531        tracing::info!(%err, "task failed successfully");
1532        assert_eq!(
1533            ProposalValidationError::DecrementingTimestamp {
1534                proposal_timestamp,
1535                parent_timestamp: u64::MAX,
1536            },
1537            err
1538        );
1539
1540        // Success case (genesis timestamp is `0`).
1541        let proposal = Proposal::new(&parent, block_size);
1542        proposal.validate_timestamp_non_dec(0).unwrap();
1543    }
1544
1545    #[tokio::test(flavor = "multi_thread")]
1546    async fn test_validation_timestamp_drift() {
1547        initialize_logging();
1548        // Setup
1549        let instance = NodeState::mock_v2();
1550        let (parent, block_size) = Transaction::of_size(10).into_mock_header().await;
1551
1552        let header = parent.clone();
1553        // Error case.
1554        let proposal = Proposal::new(&header, block_size);
1555        let proposal_timestamp = header.timestamp();
1556
1557        let mock_time = OffsetDateTime::now_utc().unix_timestamp() as u64;
1558        // TODO
1559        let err = ValidatedTransition::mock(instance.clone(), &parent, proposal)
1560            .validate_timestamp()
1561            .unwrap_err();
1562
1563        tracing::info!(%err, "task failed successfully");
1564        assert_eq!(
1565            ProposalValidationError::InvalidTimestampDrift {
1566                proposal: proposal_timestamp,
1567                system: mock_time,
1568                diff: mock_time
1569            },
1570            err
1571        );
1572
1573        let time = OffsetDateTime::now_utc();
1574        let timestamp: u64 = time.unix_timestamp() as u64;
1575        let timestamp_millis = TimestampMillis::from_time(&time).u64();
1576
1577        let mut header = parent.clone();
1578        header.set_timestamp(timestamp - 13, timestamp_millis - 13_000);
1579        let proposal = Proposal::new(&header, block_size);
1580
1581        let err = proposal.validate_timestamp_drift(timestamp).unwrap_err();
1582        tracing::info!(%err, "task failed successfully");
1583        assert_eq!(
1584            ProposalValidationError::InvalidTimestampDrift {
1585                proposal: timestamp - 13,
1586                system: timestamp,
1587                diff: 13
1588            },
1589            err
1590        );
1591
1592        // Success cases.
1593        let mut header = parent.clone();
1594        header.set_timestamp(timestamp, timestamp_millis);
1595        let proposal = Proposal::new(&header, block_size);
1596        proposal.validate_timestamp_drift(timestamp).unwrap();
1597
1598        header.set_timestamp(timestamp - 11, timestamp_millis - 11_000);
1599        let proposal = Proposal::new(&header, block_size);
1600        proposal.validate_timestamp_drift(timestamp).unwrap();
1601
1602        header.set_timestamp(timestamp - 12, timestamp_millis - 12_000);
1603        let proposal = Proposal::new(&header, block_size);
1604        proposal.validate_timestamp_drift(timestamp).unwrap();
1605    }
1606
1607    #[tokio::test(flavor = "multi_thread")]
1608    async fn test_validation_fee_root() {
1609        initialize_logging();
1610        // Setup
1611        let instance = NodeState::mock_v2();
1612        let (header, block_size) = Transaction::of_size(10).into_mock_header().await;
1613
1614        // Success case.
1615        let proposal = Proposal::new(&header, block_size);
1616        ValidatedTransition::mock(instance.clone(), &header, proposal)
1617            .validate_fee_merkle_tree()
1618            .unwrap();
1619
1620        // Error case.
1621        let proposal = Proposal::new(&header, block_size);
1622
1623        let mut fee_merkle_tree = instance.genesis_state.fee_merkle_tree;
1624        fee_merkle_tree
1625            .update_with(FeeAccount::default(), |_| Some(100.into()))
1626            .unwrap();
1627
1628        let err = proposal
1629            .validate_block_merkle_tree(fee_merkle_tree.commitment())
1630            .unwrap_err();
1631
1632        tracing::info!(%err, "task failed successfully");
1633        assert_eq!(
1634            ProposalValidationError::InvalidBlockRoot {
1635                expected_root: fee_merkle_tree.commitment(),
1636                proposal_root: header.block_merkle_tree_root(),
1637            },
1638            err
1639        );
1640    }
1641
1642    #[tokio::test(flavor = "multi_thread")]
1643    async fn test_validation_block_root() {
1644        initialize_logging();
1645        // Setup.
1646        let instance = NodeState::mock_v2();
1647        let (header, block_size) = Transaction::of_size(10).into_mock_header().await;
1648
1649        // Success case.
1650        let proposal = Proposal::new(&header, block_size);
1651        ValidatedTransition::mock(instance.clone(), &header, proposal)
1652            .validate_block_merkle_tree()
1653            .unwrap();
1654
1655        // Error case.
1656        let proposal = Proposal::new(&header, block_size);
1657        let mut block_merkle_tree = instance.genesis_state.block_merkle_tree;
1658        block_merkle_tree.push(header.commitment()).unwrap();
1659        block_merkle_tree
1660            .push(header.clone().next().commitment())
1661            .unwrap();
1662
1663        let err = proposal
1664            .validate_block_merkle_tree(block_merkle_tree.commitment())
1665            .unwrap_err();
1666
1667        tracing::info!(%err, "task failed successfully");
1668        assert_eq!(
1669            ProposalValidationError::InvalidBlockRoot {
1670                expected_root: block_merkle_tree.commitment(),
1671                proposal_root: proposal.header.block_merkle_tree_root(),
1672            },
1673            err
1674        );
1675    }
1676
1677    #[tokio::test(flavor = "multi_thread")]
1678    async fn test_validation_ns_table() {
1679        use NsTableValidationError::InvalidFinalOffset;
1680
1681        initialize_logging();
1682        // Setup.
1683        let tx = Transaction::of_size(10);
1684        let (header, block_size) = tx.into_mock_header().await;
1685
1686        // Success case.
1687        let proposal = Proposal::new(&header, block_size);
1688        ValidatedTransition::mock(NodeState::mock_v2(), &header, proposal)
1689            .validate_namespace_table()
1690            .unwrap();
1691
1692        // Error case
1693        let proposal = Proposal::new(&header, 40);
1694        let err = ValidatedTransition::mock(NodeState::mock_v2(), &header, proposal)
1695            .validate_namespace_table()
1696            .unwrap_err();
1697        tracing::info!(%err, "task failed successfully");
1698        // TODO NsTable has other error variants, but these should be
1699        // tested in unit tests of `NsTable.validate()`.
1700        assert_eq!(
1701            ProposalValidationError::InvalidNsTable(InvalidFinalOffset),
1702            err
1703        );
1704    }
1705
1706    #[test]
1707    fn test_charge_fee() {
1708        initialize_logging();
1709        let src = FeeAccount::generated_from_seed_indexed([0; 32], 0).0;
1710        let dst = FeeAccount::generated_from_seed_indexed([0; 32], 1).0;
1711        let amt = FeeAmount::from(1);
1712
1713        let fee_info = FeeInfo::new(src, amt);
1714
1715        let new_state = || {
1716            let mut state = ValidatedState::default();
1717            state.prefund_account(src, amt);
1718            state
1719        };
1720
1721        tracing::info!("test successful fee");
1722        let mut state = new_state();
1723        state.charge_fee(fee_info, dst).unwrap();
1724        assert_eq!(state.balance(src), Some(0.into()));
1725        assert_eq!(state.balance(dst), Some(amt));
1726
1727        tracing::info!("test insufficient balance");
1728        let err = state.charge_fee(fee_info, dst).unwrap_err();
1729        assert_eq!(state.balance(src), Some(0.into()));
1730        assert_eq!(state.balance(dst), Some(amt));
1731        assert_eq!(
1732            FeeError::InsufficientFunds {
1733                balance: None,
1734                amount: amt
1735            },
1736            err
1737        );
1738
1739        tracing::info!("test src not in memory");
1740        let mut state = new_state();
1741        state.fee_merkle_tree.forget(src).expect_ok().unwrap();
1742        assert_eq!(
1743            FeeError::MerkleTreeError(MerkleTreeError::ForgottenLeaf),
1744            state.charge_fee(fee_info, dst).unwrap_err()
1745        );
1746
1747        tracing::info!("test dst not in memory");
1748        let mut state = new_state();
1749        state.prefund_account(dst, amt);
1750        state.fee_merkle_tree.forget(dst).expect_ok().unwrap();
1751        assert_eq!(
1752            FeeError::MerkleTreeError(MerkleTreeError::ForgottenLeaf),
1753            state.charge_fee(fee_info, dst).unwrap_err()
1754        );
1755    }
1756
1757    #[test]
1758    fn test_fee_amount_serde_json_as_decimal() {
1759        let amt = FeeAmount::from(123);
1760        let serialized = serde_json::to_string(&amt).unwrap();
1761
1762        // The value is serialized as a decimal string.
1763        assert_eq!(serialized, "\"123\"");
1764
1765        // Deserialization produces the original value
1766        let deserialized: FeeAmount = serde_json::from_str(&serialized).unwrap();
1767        assert_eq!(deserialized, amt);
1768    }
1769
1770    #[test]
1771    fn test_fee_amount_from_units() {
1772        for (unit, multiplier) in [
1773            ("wei", 1),
1774            ("gwei", 1_000_000_000),
1775            ("eth", 1_000_000_000_000_000_000),
1776        ] {
1777            let amt: FeeAmount = serde_json::from_str(&format!("\"1 {unit}\"")).unwrap();
1778            assert_eq!(amt, multiplier.into());
1779        }
1780    }
1781
1782    #[test]
1783    fn test_fee_amount_serde_json_from_hex() {
1784        // For backwards compatibility, fee amounts can also be deserialized from a 0x-prefixed hex
1785        // string.
1786        let amt: FeeAmount = serde_json::from_str("\"0x123\"").unwrap();
1787        assert_eq!(amt, FeeAmount::from(0x123));
1788    }
1789
1790    #[test]
1791    fn test_fee_amount_serde_json_from_number() {
1792        // For convenience, fee amounts can also be deserialized from a JSON number.
1793        let amt: FeeAmount = serde_json::from_str("123").unwrap();
1794        assert_eq!(amt, FeeAmount::from(123));
1795    }
1796
1797    #[test]
1798    fn test_fee_amount_serde_bincode_unchanged() {
1799        // For non-human-readable formats, FeeAmount just serializes as the underlying U256.
1800        // note: for backward compat, it has to be the same as ethers' U256 instead of alloy's
1801        let n = ethers_core::types::U256::from(123);
1802        let amt = FeeAmount(U256::from(123));
1803        assert_eq!(
1804            bincode::serialize(&n).unwrap(),
1805            bincode::serialize(&amt).unwrap(),
1806        );
1807    }
1808
1809    #[tokio::test(flavor = "multi_thread")]
1810    async fn test_validate_builder_fee() {
1811        initialize_logging();
1812        let max_block_size = 10;
1813
1814        let validated_state = ValidatedState::default();
1815        let instance_state = NodeState::mock().with_chain_config(ChainConfig {
1816            base_fee: 1000.into(), // High base fee
1817            max_block_size: max_block_size.into(),
1818            ..validated_state.chain_config.resolve().unwrap()
1819        });
1820
1821        let parent: Leaf2 =
1822            Leaf::genesis::<MockVersions>(&instance_state.genesis_state, &instance_state)
1823                .await
1824                .into();
1825        let header = parent.block_header().clone();
1826        let metadata = parent.block_header().metadata();
1827
1828        debug!("{:?}", header.version());
1829
1830        let key_pair = EthKeyPair::random();
1831        let account = key_pair.fee_account();
1832
1833        let data = header.fee_info()[0].amount().as_u64().unwrap();
1834        let sig = FeeAccount::sign_builder_message(&key_pair, &data.to_be_bytes()).unwrap();
1835
1836        // ensure the signature is indeed valid
1837        account
1838            .validate_builder_signature(&sig, &data.to_be_bytes())
1839            .then_some(())
1840            .unwrap();
1841
1842        // test v1 sig
1843        let sig = FeeAccount::sign_fee(&key_pair, data, metadata).unwrap();
1844
1845        let header = match header {
1846            Header::V1(header) => Header::V1(v0_1::Header {
1847                builder_signature: Some(sig),
1848                fee_info: FeeInfo::new(account, data),
1849                ..header
1850            }),
1851            Header::V2(header) => Header::V2(v0_2::Header {
1852                builder_signature: Some(sig),
1853                fee_info: FeeInfo::new(account, data),
1854                ..header
1855            }),
1856            Header::V3(header) => Header::V3(v0_3::Header {
1857                builder_signature: Some(sig),
1858                fee_info: FeeInfo::new(account, data),
1859                ..header
1860            }),
1861            Header::V4(header) => Header::V4(v0_4::Header {
1862                builder_signature: Some(sig),
1863                fee_info: FeeInfo::new(account, data),
1864                ..header
1865            }),
1866        };
1867
1868        validate_builder_fee(&header).unwrap();
1869    }
1870}