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