pallet_domains/
block_tree.rs

1//! Domain block tree
2
3#[cfg(not(feature = "std"))]
4extern crate alloc;
5
6use crate::{
7    BalanceOf, BlockTree, BlockTreeNodeFor, BlockTreeNodes, Config, ConsensusBlockHash,
8    DomainBlockNumberFor, DomainGenesisBlockExecutionReceipt, DomainHashingFor,
9    DomainRuntimeUpgradeRecords, ExecutionInbox, ExecutionReceiptOf, ExecutionReceiptRefOf,
10    HeadDomainNumber, HeadReceiptNumber, InboxedBundleAuthor,
11    LatestConfirmedDomainExecutionReceipt, LatestSubmittedER, NewAddedHeadReceipt, Pallet,
12    ReceiptHashFor,
13};
14#[cfg(not(feature = "std"))]
15use alloc::vec::Vec;
16use frame_support::{PalletError, ensure};
17use frame_system::pallet_prelude::BlockNumberFor;
18use parity_scale_codec::{Decode, Encode};
19use scale_info::TypeInfo;
20use sp_core::Get;
21use sp_domains::execution_receipt::execution_receipt_v0::ExecutionReceiptV0;
22use sp_domains::execution_receipt::{ExecutionReceipt, ExecutionReceiptRef, Transfers};
23use sp_domains::merkle_tree::MerkleTree;
24use sp_domains::{ChainId, DomainId, DomainsTransfersTracker, OnChainRewards, OperatorId};
25use sp_runtime::traits::{BlockNumberProvider, CheckedSub, One, Saturating, Zero};
26use sp_std::cmp::Ordering;
27use sp_std::collections::btree_map::BTreeMap;
28
29/// Block tree specific errors
30#[derive(TypeInfo, Encode, Decode, PalletError, Debug, PartialEq)]
31pub enum Error {
32    InvalidExtrinsicsRoots,
33    UnknownParentBlockReceipt,
34    BuiltOnUnknownConsensusBlock,
35    InFutureReceipt,
36    PrunedReceipt,
37    StaleReceipt,
38    NewBranchReceipt,
39    BadGenesisReceipt,
40    UnexpectedReceiptType,
41    MaxHeadDomainNumber,
42    MissingDomainBlock,
43    InvalidTraceRoot,
44    InvalidExecutionTrace,
45    UnavailableConsensusBlockHash,
46    InvalidStateRoot,
47    BalanceOverflow,
48    DomainTransfersTracking,
49    InvalidDomainTransfers,
50    OverwritingER,
51    RuntimeNotFound,
52    LastBlockNotFound,
53    UnmatchedNewHeadReceipt,
54}
55
56#[derive(TypeInfo, Debug, Encode, Decode, Clone, PartialEq, Eq)]
57pub struct BlockTreeNode<Number, Hash, DomainNumber, DomainHash, Balance> {
58    /// The full ER for this block.
59    pub execution_receipt: ExecutionReceipt<Number, Hash, DomainNumber, DomainHash, Balance>,
60    /// A set of all operators who have committed to this ER within a bundle. Used to determine who to
61    /// slash if a fraudulent branch of the `block_tree` is pruned.
62    ///
63    /// NOTE: there may be duplicated operator id as an operator can submit multiple bundles with the
64    /// same head receipt to a consensus block.
65    pub operator_ids: Vec<OperatorId>,
66}
67
68#[derive(Debug, PartialEq, Eq)]
69pub(crate) enum AcceptedReceiptType {
70    // New head receipt that extend the longest branch
71    NewHead,
72    // Receipt that confirms the head receipt that added in the current block
73    CurrentHead,
74}
75
76#[derive(Debug, PartialEq, Eq)]
77pub(crate) enum RejectedReceiptType {
78    // Receipt that is newer than the head receipt but does not extend the head receipt
79    InFuture,
80    // Receipt that already been pruned
81    Pruned,
82    // Receipt that confirm a non-head receipt or head receipt of the previous block
83    Stale,
84    // Receipt that tries to create a new branch of the block tree
85    //
86    // The honests operator must submit fraud proof to prune the bad receipt at the
87    // same height before submitting the valid receipt.
88    NewBranch,
89}
90
91impl From<RejectedReceiptType> for Error {
92    fn from(rejected_receipt: RejectedReceiptType) -> Error {
93        match rejected_receipt {
94            RejectedReceiptType::InFuture => Error::InFutureReceipt,
95            RejectedReceiptType::Pruned => Error::PrunedReceipt,
96            RejectedReceiptType::Stale => Error::StaleReceipt,
97            RejectedReceiptType::NewBranch => Error::NewBranchReceipt,
98        }
99    }
100}
101
102/// The type of receipt regarding to its freshness
103#[derive(Debug, PartialEq, Eq)]
104pub(crate) enum ReceiptType {
105    Accepted(AcceptedReceiptType),
106    Rejected(RejectedReceiptType),
107}
108
109pub(crate) fn does_receipt_exists<T: Config>(
110    domain_id: DomainId,
111    domain_number: DomainBlockNumberFor<T>,
112    receipt_hash: ReceiptHashFor<T>,
113) -> bool {
114    BlockTree::<T>::get(domain_id, domain_number)
115        .map(|h| h == receipt_hash)
116        .unwrap_or(false)
117}
118
119/// Get the receipt type of the given receipt based on the current block tree state
120pub(crate) fn execution_receipt_type<T: Config>(
121    domain_id: DomainId,
122    execution_receipt: &ExecutionReceiptRefOf<T>,
123) -> ReceiptType {
124    let ExecutionReceiptRef::V0(ExecutionReceiptV0 {
125        domain_block_number,
126        ..
127    }) = execution_receipt;
128    let receipt_number = *domain_block_number;
129    let head_receipt_number = HeadReceiptNumber::<T>::get(domain_id);
130    let head_receipt_extended = NewAddedHeadReceipt::<T>::get(domain_id).is_some();
131    let next_receipt_number = head_receipt_number.saturating_add(One::one());
132    let latest_confirmed_domain_block_number =
133        Pallet::<T>::latest_confirmed_domain_block_number(domain_id);
134
135    match receipt_number.cmp(&next_receipt_number) {
136        Ordering::Greater => ReceiptType::Rejected(RejectedReceiptType::InFuture),
137        Ordering::Equal => {
138            // we do not allow consecutive ER in a single consensus block
139            // if the head receipt is already extended, then reject this ER
140            // as it is a Future ER
141            if head_receipt_extended {
142                ReceiptType::Rejected(RejectedReceiptType::InFuture)
143            } else {
144                ReceiptType::Accepted(AcceptedReceiptType::NewHead)
145            }
146        }
147        Ordering::Less => {
148            // Reject receipt that already confirmed
149            if !latest_confirmed_domain_block_number.is_zero()
150                && receipt_number <= latest_confirmed_domain_block_number
151            {
152                return ReceiptType::Rejected(RejectedReceiptType::Pruned);
153            }
154
155            // Reject receipt that try to create new branch in the block tree
156            let already_exist = does_receipt_exists::<T>(
157                domain_id,
158                receipt_number,
159                execution_receipt.hash::<DomainHashingFor<T>>(),
160            );
161            if !already_exist {
162                return ReceiptType::Rejected(RejectedReceiptType::NewBranch);
163            }
164
165            // Add confirm to the head receipt that added in the current block or it is
166            // the first genesis receipt
167            let is_first_genesis_receipt =
168                receipt_number.is_zero() && HeadDomainNumber::<T>::get(domain_id).is_zero();
169            if receipt_number == head_receipt_number
170                && (head_receipt_extended || is_first_genesis_receipt)
171            {
172                return ReceiptType::Accepted(AcceptedReceiptType::CurrentHead);
173            }
174
175            // Add confirm to a non-head receipt or head receipt of the previous block
176            ReceiptType::Rejected(RejectedReceiptType::Stale)
177        }
178    }
179}
180
181/// Verify the execution receipt
182pub(crate) fn verify_execution_receipt<T: Config>(
183    domain_id: DomainId,
184    execution_receipt: &ExecutionReceiptRefOf<T>,
185) -> Result<(), Error> {
186    let ExecutionReceiptRef::V0(ExecutionReceiptV0 {
187        consensus_block_number,
188        consensus_block_hash,
189        domain_block_number,
190        inboxed_bundles,
191        parent_domain_block_receipt_hash,
192        execution_trace,
193        execution_trace_root,
194        final_state_root,
195        ..
196    }) = execution_receipt;
197
198    // Checking if the incoming ER is expected regarding to its `domain_block_number` or freshness
199    if let ReceiptType::Rejected(rejected_receipt_type) =
200        execution_receipt_type::<T>(domain_id, execution_receipt)
201    {
202        return Err(rejected_receipt_type.into());
203    }
204
205    // If there is new head receipt added in the current block, as long as the incoming
206    // receipt is the same as the new head receipt we can safely skip the following checks,
207    // if they are not the same, we just reject the incoming receipt and expecting a fraud
208    // proof will be submit if the new head receipt is fraudulent and then the incoming
209    // receipt will be re-submit.
210    if let Some(new_added_head_receipt) = NewAddedHeadReceipt::<T>::get(domain_id) {
211        ensure!(
212            new_added_head_receipt == execution_receipt.hash::<DomainHashingFor<T>>(),
213            Error::UnmatchedNewHeadReceipt,
214        );
215        return Ok(());
216    }
217
218    // The genesis receipt is generated and added to the block tree by the runtime upon domain
219    // instantiation thus it is unchallengeable, we can safely skip other checks as long as we
220    // can ensure it is always be the same.
221    if domain_block_number.is_zero() {
222        ensure!(
223            does_receipt_exists::<T>(
224                domain_id,
225                *domain_block_number,
226                execution_receipt.hash::<DomainHashingFor<T>>(),
227            ),
228            Error::BadGenesisReceipt
229        );
230        return Ok(());
231    }
232
233    // Check if the ER has at least 2 trace root (for Initialization and Finalization of block at least)
234    if execution_trace.len() < 2 {
235        return Err(Error::InvalidExecutionTrace);
236    }
237
238    let maybe_domain_runtime_upgraded_at = {
239        let runtime_id = Pallet::<T>::runtime_id(domain_id).ok_or(Error::RuntimeNotFound)?;
240        DomainRuntimeUpgradeRecords::<T>::get(runtime_id).remove(consensus_block_number)
241    };
242
243    // Check if the ER is derived from the correct consensus block in the current chain
244    let excepted_consensus_block_hash =
245        match ConsensusBlockHash::<T>::get(domain_id, consensus_block_number) {
246            Some(hash) => hash,
247            None => {
248                // The `initialize_block` of non-system pallets is skipped in the `validate_transaction`,
249                // thus the hash of best block, which is recorded in the this pallet's `on_initialize` hook,
250                // is unavailable at this point.
251                let parent_block_number =
252                    frame_system::Pallet::<T>::current_block_number() - One::one();
253                if *consensus_block_number == parent_block_number {
254                    frame_system::Pallet::<T>::parent_hash()
255
256                // The domain runtime upgrade is forced to happen even if there is no bundle, in this case,
257                // the `ConsensusBlockHash` will be empty so we need to get the consensus block hash from
258                // `DomainRuntimeUpgradeRecords`
259                } else if let Some(ref upgrade_entry) = maybe_domain_runtime_upgraded_at {
260                    upgrade_entry.at_hash
261                } else {
262                    return Err(Error::UnavailableConsensusBlockHash);
263                }
264            }
265        };
266    ensure!(
267        *consensus_block_hash == excepted_consensus_block_hash,
268        Error::BuiltOnUnknownConsensusBlock
269    );
270
271    // Check if the ER is derived from the expected inboxed bundles of the consensus block
272    let bundles_extrinsics_roots: Vec<_> =
273        inboxed_bundles.iter().map(|b| b.extrinsics_root).collect();
274    let execution_inbox =
275        ExecutionInbox::<T>::get((domain_id, domain_block_number, consensus_block_number));
276    let expected_extrinsics_roots: Vec<_> =
277        execution_inbox.iter().map(|b| b.extrinsics_root).collect();
278    ensure!(
279        (!bundles_extrinsics_roots.is_empty() || maybe_domain_runtime_upgraded_at.is_some())
280            && bundles_extrinsics_roots == expected_extrinsics_roots,
281        Error::InvalidExtrinsicsRoots
282    );
283
284    // Check if the `execution_trace_root` is well-format
285    let mut trace = Vec::with_capacity(execution_trace.len());
286    for root in execution_trace {
287        trace.push(
288            root.encode()
289                .try_into()
290                .map_err(|_| Error::InvalidTraceRoot)?,
291        );
292    }
293    let expected_execution_trace_root: sp_core::H256 = MerkleTree::from_leaves(trace.as_slice())
294        .root()
295        .ok_or(Error::InvalidTraceRoot)?
296        .into();
297    ensure!(
298        expected_execution_trace_root == *execution_trace_root,
299        Error::InvalidTraceRoot
300    );
301
302    // check state root on ER and in the Execution trace
303    if let Some(expected_final_state_root) = execution_trace.last() {
304        ensure!(
305            final_state_root == expected_final_state_root,
306            Error::InvalidStateRoot
307        );
308    }
309
310    // Check if the ER is extending an existing parent ER
311    if let Some(parent_block_number) = domain_block_number.checked_sub(&One::one()) {
312        let parent_block_exist = does_receipt_exists::<T>(
313            domain_id,
314            parent_block_number,
315            *parent_domain_block_receipt_hash,
316        );
317        ensure!(parent_block_exist, Error::UnknownParentBlockReceipt);
318    }
319
320    Ok(())
321}
322
323/// Details of the confirmed domain block such as operators, rewards they would receive.
324#[derive(Debug, PartialEq)]
325pub(crate) struct ConfirmedDomainBlockInfo<ConsensusNumber, DomainNumber, Balance> {
326    pub consensus_block_number: ConsensusNumber,
327    pub domain_block_number: DomainNumber,
328    pub operator_ids: Vec<OperatorId>,
329    pub rewards: Balance,
330    pub invalid_bundle_authors: Vec<OperatorId>,
331    pub total_storage_fee: Balance,
332    pub paid_bundle_storage_fees: BTreeMap<OperatorId, u32>,
333}
334
335pub(crate) type ProcessExecutionReceiptResult<T> = Result<
336    Option<ConfirmedDomainBlockInfo<BlockNumberFor<T>, DomainBlockNumberFor<T>, BalanceOf<T>>>,
337    Error,
338>;
339
340/// Process the execution receipt to add it to the block tree
341/// Returns the domain block number that was pruned, if any
342pub(crate) fn process_execution_receipt<T: Config>(
343    domain_id: DomainId,
344    submitter: OperatorId,
345    execution_receipt: ExecutionReceiptOf<T>,
346    receipt_type: AcceptedReceiptType,
347) -> ProcessExecutionReceiptResult<T> {
348    let er_hash = execution_receipt.hash::<DomainHashingFor<T>>();
349    let receipt_block_number = *execution_receipt.domain_block_number();
350    match receipt_type {
351        AcceptedReceiptType::NewHead => {
352            add_new_receipt_to_block_tree::<T>(domain_id, submitter, execution_receipt)?;
353
354            // Update the head receipt number
355            HeadReceiptNumber::<T>::insert(domain_id, receipt_block_number);
356            NewAddedHeadReceipt::<T>::insert(domain_id, er_hash);
357
358            // Prune expired domain block
359            if let Some(to_prune) =
360                receipt_block_number.checked_sub(&T::BlockTreePruningDepth::get())
361            {
362                let BlockTreeNode {
363                    execution_receipt,
364                    operator_ids,
365                } = match prune_receipt::<T>(domain_id, to_prune)? {
366                    Some(n) => n,
367                    // The receipt at `to_prune` may already been pruned if there is fraud proof being
368                    // processed previously and the `HeadReceiptNumber` is reverted.
369                    None => return Ok(None),
370                };
371
372                // Collect the paid bundle storage fees and the invalid bundle author
373                let mut paid_bundle_storage_fees = BTreeMap::new();
374                let mut invalid_bundle_authors = Vec::new();
375                let consensus_block_number = *execution_receipt.consensus_block_number();
376                let bundle_digests =
377                    ExecutionInbox::<T>::get((domain_id, to_prune, consensus_block_number));
378                let inboxed_bundles = execution_receipt.inboxed_bundles();
379                for (index, bd) in bundle_digests.into_iter().enumerate() {
380                    if let Some(bundle_author) = InboxedBundleAuthor::<T>::take(bd.header_hash) {
381                        // It is okay to index `ER::bundles` here since `verify_execution_receipt` have checked
382                        // the `ER::bundles` have the same length of `ExecutionInbox`
383                        if inboxed_bundles[index].is_invalid() {
384                            invalid_bundle_authors.push(bundle_author);
385                        } else {
386                            paid_bundle_storage_fees
387                                .entry(bundle_author)
388                                .and_modify(|s| *s += bd.size)
389                                .or_insert(bd.size);
390                        }
391                    }
392                }
393
394                // Remove the block's `ExecutionInbox` as the domain block is confirmed and no need to verify
395                // its receipt's `extrinsics_root` anymore.
396                let _ = ExecutionInbox::<T>::clear_prefix((domain_id, to_prune), u32::MAX, None);
397
398                LatestConfirmedDomainExecutionReceipt::<T>::insert(
399                    domain_id,
400                    execution_receipt.clone(),
401                );
402
403                ConsensusBlockHash::<T>::remove(domain_id, consensus_block_number);
404
405                let block_fees = execution_receipt
406                    .block_fees()
407                    .total_fees()
408                    .ok_or(Error::BalanceOverflow)?;
409
410                ensure!(
411                    execution_receipt
412                        .transfers()
413                        .is_valid(ChainId::Domain(domain_id)),
414                    Error::InvalidDomainTransfers
415                );
416
417                update_domain_transfers::<T>(domain_id, execution_receipt.transfers(), block_fees)
418                    .map_err(|_| Error::DomainTransfersTracking)?;
419
420                update_domain_runtime_upgrade_records::<T>(domain_id, consensus_block_number)?;
421
422                // handle chain rewards from the domain
423                execution_receipt
424                    .block_fees()
425                    .chain_rewards
426                    .iter()
427                    .for_each(|(chain_id, reward)| {
428                        T::OnChainRewards::on_chain_rewards(*chain_id, *reward)
429                    });
430
431                return Ok(Some(ConfirmedDomainBlockInfo {
432                    consensus_block_number,
433                    domain_block_number: to_prune,
434                    operator_ids,
435                    rewards: execution_receipt.block_fees().domain_execution_fee,
436                    invalid_bundle_authors,
437                    total_storage_fee: execution_receipt.block_fees().consensus_storage_fee,
438                    paid_bundle_storage_fees,
439                }));
440            }
441        }
442        AcceptedReceiptType::CurrentHead => {
443            // Add confirmation to the current head receipt
444            BlockTreeNodes::<T>::mutate(er_hash, |maybe_node| {
445                let node = maybe_node.as_mut().expect(
446                    "The domain block of `CurrentHead` receipt is checked to be exist in `execution_receipt_type`; qed"
447                );
448                node.operator_ids.push(submitter);
449            });
450        }
451    }
452
453    // Update the `LatestSubmittedER` for the operator
454    let key = (domain_id, submitter);
455    if receipt_block_number > Pallet::<T>::latest_submitted_er(key) {
456        LatestSubmittedER::<T>::insert(key, receipt_block_number)
457    }
458
459    Ok(None)
460}
461
462type TransferTrackerError<T> =
463    <<T as Config>::DomainsTransfersTracker as DomainsTransfersTracker<BalanceOf<T>>>::Error;
464
465/// Updates domain transfers for following scenarios
466/// 1. Block fees are burned on domain
467/// 2. Confirming incoming XDM transfers to the Domain
468/// 3. Noting outgoing transfers from the domain
469/// 4. Cancelling outgoing transfers from the domain.
470fn update_domain_transfers<T: Config>(
471    domain_id: DomainId,
472    transfers: &Transfers<BalanceOf<T>>,
473    block_fees: BalanceOf<T>,
474) -> Result<(), TransferTrackerError<T>> {
475    let Transfers {
476        transfers_in,
477        transfers_out,
478        transfers_rejected,
479        rejected_transfers_claimed,
480    } = transfers;
481
482    // confirm incoming transfers
483    let er_chain_id = ChainId::Domain(domain_id);
484    transfers_in
485        .iter()
486        .try_for_each(|(from_chain_id, amount)| {
487            T::DomainsTransfersTracker::confirm_transfer(*from_chain_id, er_chain_id, *amount)
488        })?;
489
490    // note outgoing transfers
491    transfers_out.iter().try_for_each(|(to_chain_id, amount)| {
492        T::DomainsTransfersTracker::note_transfer(er_chain_id, *to_chain_id, *amount)
493    })?;
494
495    // note rejected transfers
496    transfers_rejected
497        .iter()
498        .try_for_each(|(from_chain_id, amount)| {
499            T::DomainsTransfersTracker::reject_transfer(*from_chain_id, er_chain_id, *amount)
500        })?;
501
502    // claim rejected transfers
503    rejected_transfers_claimed
504        .iter()
505        .try_for_each(|(to_chain_id, amount)| {
506            T::DomainsTransfersTracker::claim_rejected_transfer(er_chain_id, *to_chain_id, *amount)
507        })?;
508
509    // deduct execution fees from domain
510    T::DomainsTransfersTracker::reduce_domain_balance(domain_id, block_fees)?;
511
512    Ok(())
513}
514
515// Update the domain runtime upgrade record at `consensus_number` if there is one
516fn update_domain_runtime_upgrade_records<T: Config>(
517    domain_id: DomainId,
518    consensus_number: BlockNumberFor<T>,
519) -> Result<(), Error> {
520    let runtime_id = Pallet::<T>::runtime_id(domain_id).ok_or(Error::RuntimeNotFound)?;
521    let mut domain_runtime_upgrade_records = DomainRuntimeUpgradeRecords::<T>::get(runtime_id);
522
523    if let Some(upgrade_entry) = domain_runtime_upgrade_records.get_mut(&consensus_number) {
524        // Decrease the `reference_count` by one and remove the whole entry if it drop to zero
525        if upgrade_entry.reference_count > One::one() {
526            upgrade_entry.reference_count =
527                upgrade_entry.reference_count.saturating_sub(One::one());
528        } else {
529            domain_runtime_upgrade_records.remove(&consensus_number);
530        }
531
532        if !domain_runtime_upgrade_records.is_empty() {
533            DomainRuntimeUpgradeRecords::<T>::set(runtime_id, domain_runtime_upgrade_records);
534        } else {
535            DomainRuntimeUpgradeRecords::<T>::remove(runtime_id);
536        }
537    }
538    Ok(())
539}
540
541fn add_new_receipt_to_block_tree<T: Config>(
542    domain_id: DomainId,
543    submitter: OperatorId,
544    execution_receipt: ExecutionReceiptOf<T>,
545) -> Result<(), Error> {
546    // Construct and add a new domain block to the block tree
547    let er_hash = execution_receipt.hash::<DomainHashingFor<T>>();
548    let domain_block_number = execution_receipt.domain_block_number();
549
550    ensure!(
551        !BlockTree::<T>::contains_key(domain_id, domain_block_number),
552        Error::OverwritingER,
553    );
554
555    BlockTree::<T>::insert(domain_id, domain_block_number, er_hash);
556    let block_tree_node = BlockTreeNode {
557        execution_receipt,
558        operator_ids: sp_std::vec![submitter],
559    };
560    BlockTreeNodes::<T>::insert(er_hash, block_tree_node);
561
562    Ok(())
563}
564
565/// Import the genesis receipt to the block tree
566pub(crate) fn import_genesis_receipt<T: Config>(
567    domain_id: DomainId,
568    genesis_receipt: ExecutionReceiptOf<T>,
569) {
570    let er_hash = genesis_receipt.hash::<DomainHashingFor<T>>();
571    let domain_block_number = *genesis_receipt.domain_block_number();
572
573    LatestConfirmedDomainExecutionReceipt::<T>::insert(domain_id, genesis_receipt.clone());
574    DomainGenesisBlockExecutionReceipt::<T>::insert(domain_id, genesis_receipt.clone());
575
576    let block_tree_node = BlockTreeNode {
577        execution_receipt: genesis_receipt,
578        operator_ids: sp_std::vec![],
579    };
580    // NOTE: no need to update the head receipt number as `HeadReceiptNumber` is using `ValueQuery`
581    BlockTree::<T>::insert(domain_id, domain_block_number, er_hash);
582    BlockTreeNodes::<T>::insert(er_hash, block_tree_node);
583}
584
585pub(crate) fn prune_receipt<T: Config>(
586    domain_id: DomainId,
587    receipt_number: DomainBlockNumberFor<T>,
588) -> Result<Option<BlockTreeNodeFor<T>>, Error> {
589    let receipt_hash = match BlockTree::<T>::take(domain_id, receipt_number) {
590        Some(er_hash) => er_hash,
591        None => return Ok(None),
592    };
593    let block_tree_node =
594        BlockTreeNodes::<T>::take(receipt_hash).ok_or(Error::MissingDomainBlock)?;
595
596    // If the pruned ER is the operator's `latest_submitted_er` for this domain, it means either:
597    //
598    // - All the ER the operator submitted for this domain are confirmed and pruned, so the operator
599    //   can't be targeted by fraud proof later unless it submit other new ERs.
600    //
601    // - All the bad ER the operator submitted for this domain are pruned and the operator is already
602    //   slashed, so wwe don't need `LatestSubmittedER` to determine if the operator is pending slash.
603    //
604    // In both cases, it is safe to remove the `LatestSubmittedER` for the operator in this domain
605    for operator_id in block_tree_node.operator_ids.iter() {
606        let key = (domain_id, operator_id);
607        let latest_submitted_er = Pallet::<T>::latest_submitted_er(key);
608        if *block_tree_node.execution_receipt.domain_block_number() == latest_submitted_er {
609            LatestSubmittedER::<T>::remove(key);
610        }
611    }
612
613    Ok(Some(block_tree_node))
614}
615
616pub(crate) fn invalid_bundle_authors_for_receipt<T: Config>(
617    domain_id: DomainId,
618    er: &ExecutionReceiptOf<T>,
619) -> Vec<OperatorId> {
620    let bundle_digests = ExecutionInbox::<T>::get((
621        domain_id,
622        er.domain_block_number(),
623        er.consensus_block_number(),
624    ));
625    bundle_digests
626        .into_iter()
627        .enumerate()
628        .filter_map(|(index, digest)| {
629            let bundle_author = InboxedBundleAuthor::<T>::get(digest.header_hash)?;
630            if er.inboxed_bundles()[index].is_invalid() {
631                Some(bundle_author)
632            } else {
633                None
634            }
635        })
636        .collect()
637}
638
639#[cfg(test)]
640mod tests {
641    use super::*;
642    use crate::tests::{
643        BlockTreePruningDepth, Domains, Test, create_dummy_bundle_with_receipts,
644        create_dummy_receipt, extend_block_tree, extend_block_tree_from_zero,
645        get_block_tree_node_at, new_test_ext_with_extensions, register_genesis_domain,
646        run_to_block,
647    };
648    use crate::{FrozenDomains, RawOrigin as DomainOrigin};
649    use frame_support::dispatch::RawOrigin;
650    use frame_support::{assert_err, assert_ok};
651    use frame_system::Origin;
652    use sp_core::H256;
653    use sp_domains::bundle::{BundleDigest, InboxedBundle, InvalidBundleType};
654
655    #[test]
656    fn test_genesis_receipt() {
657        let mut ext = new_test_ext_with_extensions();
658        ext.execute_with(|| {
659            let domain_id = register_genesis_domain(0u128, 1);
660
661            // The genesis receipt should be added to the block tree
662            let block_tree_node_at_0 = BlockTree::<Test>::get(domain_id, 0).unwrap();
663
664            let genesis_node = BlockTreeNodes::<Test>::get(block_tree_node_at_0).unwrap();
665            assert!(genesis_node.operator_ids.is_empty());
666            assert_eq!(HeadReceiptNumber::<Test>::get(domain_id), 0);
667
668            // The genesis receipt should be able pass the verification and is unchallengeable
669            let genesis_receipt = genesis_node.execution_receipt;
670            let invalid_genesis_receipt = {
671                let mut receipt = genesis_receipt.clone();
672                receipt.set_final_state_root(H256::random());
673                receipt
674            };
675            assert_ok!(verify_execution_receipt::<Test>(
676                domain_id,
677                &genesis_receipt.as_execution_receipt_ref()
678            ));
679            // Submitting an invalid genesis ER will result in `NewBranchReceipt` because the operator
680            // need to submit fraud proof to pruned a ER first before submitting an ER at the same height
681            assert_err!(
682                verify_execution_receipt::<Test>(
683                    domain_id,
684                    &invalid_genesis_receipt.as_execution_receipt_ref()
685                ),
686                Error::NewBranchReceipt
687            );
688        });
689    }
690
691    #[test]
692    fn test_new_head_receipt() {
693        let creator = 0u128;
694        let operator_id = 0u64;
695        let block_tree_pruning_depth = <Test as Config>::BlockTreePruningDepth::get();
696
697        let mut ext = new_test_ext_with_extensions();
698        ext.execute_with(|| {
699            let domain_id = register_genesis_domain(creator, 1);
700
701            // The genesis node of the block tree
702            let genesis_node = get_block_tree_node_at::<Test>(domain_id, 0).unwrap();
703            let mut receipt = genesis_node.execution_receipt;
704            assert_eq!(
705                *receipt.consensus_block_number(),
706                frame_system::Pallet::<Test>::current_block_number()
707            );
708            let mut receipt_of_block_1 = None;
709            let mut bundle_header_hash_of_block_1 = None;
710            for block_number in 1..=(block_tree_pruning_depth + 3) {
711                // Finilize parent block and initialize block at `block_number`
712                run_to_block::<Test>(block_number, *receipt.consensus_block_hash());
713
714                if block_number != 1 {
715                    // `ConsensusBlockHash` should be set to `Some` since last consensus block contains bundle
716                    assert_eq!(
717                        ConsensusBlockHash::<Test>::get(domain_id, block_number - 1),
718                        Some(frame_system::Pallet::<Test>::block_hash(block_number - 1))
719                    );
720                    // ER point to last consensus block should have `NewHead` type
721                    assert_eq!(
722                        execution_receipt_type::<Test>(
723                            domain_id,
724                            &receipt.as_execution_receipt_ref()
725                        ),
726                        ReceiptType::Accepted(AcceptedReceiptType::NewHead)
727                    );
728                    assert_ok!(verify_execution_receipt::<Test>(
729                        domain_id,
730                        &receipt.as_execution_receipt_ref()
731                    ));
732                }
733
734                // Submit a bundle with the receipt of the last block
735                let bundle_extrinsics_root = H256::random();
736                let bundle = create_dummy_bundle_with_receipts(
737                    domain_id,
738                    operator_id,
739                    bundle_extrinsics_root,
740                    receipt,
741                );
742                let bundle_header_hash = bundle.sealed_header().pre_hash();
743                let bundle_size = bundle.size();
744                assert_ok!(crate::Pallet::<Test>::submit_bundle(
745                    DomainOrigin::ValidatedUnsigned.into(),
746                    bundle,
747                ));
748                // `bundle_extrinsics_root` should be tracked in `ExecutionInbox`
749                assert_eq!(
750                    ExecutionInbox::<Test>::get((domain_id, block_number, block_number)),
751                    vec![BundleDigest {
752                        header_hash: bundle_header_hash,
753                        extrinsics_root: bundle_extrinsics_root,
754                        size: bundle_size,
755                    }]
756                );
757                assert!(InboxedBundleAuthor::<Test>::contains_key(
758                    bundle_header_hash
759                ));
760
761                // Head receipt number should be updated
762                let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
763                assert_eq!(head_receipt_number, block_number - 1);
764
765                // As we only extending the block tree there should be no fork
766                let parent_domain_block_receipt =
767                    BlockTree::<Test>::get(domain_id, head_receipt_number).unwrap();
768
769                // The submitter should be added to `operator_ids`
770                let parent_node = BlockTreeNodes::<Test>::get(parent_domain_block_receipt).unwrap();
771                assert_eq!(parent_node.operator_ids.len(), 1);
772                assert_eq!(parent_node.operator_ids[0], operator_id);
773
774                // Construct a `NewHead` receipt of the just submitted bundle, which will be included
775                // in the next bundle
776                receipt = create_dummy_receipt(
777                    block_number,
778                    H256::random(),
779                    parent_domain_block_receipt,
780                    vec![bundle_extrinsics_root],
781                );
782
783                // Record receipt of block #1 for later use
784                if block_number == 1 {
785                    receipt_of_block_1.replace(receipt.clone());
786                    bundle_header_hash_of_block_1.replace(bundle_header_hash);
787                }
788            }
789
790            // The receipt of the block 1 is pruned at the last iteration, verify it will result in
791            // `PrunedReceipt` error
792            let pruned_receipt = receipt_of_block_1.unwrap();
793            let pruned_bundle = bundle_header_hash_of_block_1.unwrap();
794            assert!(BlockTree::<Test>::get(domain_id, 1).is_none());
795            assert!(ExecutionInbox::<Test>::get((domain_id, 1, 1)).is_empty());
796            assert!(!InboxedBundleAuthor::<Test>::contains_key(pruned_bundle));
797            assert_eq!(
798                execution_receipt_type::<Test>(
799                    domain_id,
800                    &pruned_receipt.as_execution_receipt_ref()
801                ),
802                ReceiptType::Rejected(RejectedReceiptType::Pruned)
803            );
804            assert_err!(
805                verify_execution_receipt::<Test>(
806                    domain_id,
807                    &pruned_receipt.as_execution_receipt_ref()
808                ),
809                Error::PrunedReceipt
810            );
811            assert!(
812                ConsensusBlockHash::<Test>::get(domain_id, pruned_receipt.consensus_block_number(),)
813                    .is_none()
814            );
815        });
816    }
817
818    #[test]
819    fn test_confirm_current_head_receipt() {
820        let creator = 0u128;
821        let operator_id1 = 0u64;
822        let operator_id2 = 1u64;
823        let mut ext = new_test_ext_with_extensions();
824        ext.execute_with(|| {
825            let domain_id = register_genesis_domain(creator, 2);
826            let next_head_receipt = extend_block_tree_from_zero(domain_id, operator_id1, 3);
827
828            // Submit the new head receipt
829            assert_eq!(
830                execution_receipt_type::<Test>(
831                    domain_id,
832                    &next_head_receipt.as_execution_receipt_ref()
833                ),
834                ReceiptType::Accepted(AcceptedReceiptType::NewHead)
835            );
836            assert_ok!(verify_execution_receipt::<Test>(
837                domain_id,
838                &next_head_receipt.as_execution_receipt_ref()
839            ));
840            let bundle = create_dummy_bundle_with_receipts(
841                domain_id,
842                operator_id1,
843                H256::random(),
844                next_head_receipt.clone(),
845            );
846            assert_ok!(crate::Pallet::<Test>::submit_bundle(
847                DomainOrigin::ValidatedUnsigned.into(),
848                bundle,
849            ));
850
851            let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
852            let current_head_receipt =
853                get_block_tree_node_at::<Test>(domain_id, head_receipt_number)
854                    .unwrap()
855                    .execution_receipt;
856
857            // Now `next_head_receipt` become the head receipt
858            assert_eq!(next_head_receipt, current_head_receipt);
859
860            // Head receipt added in the current block is consider valid
861            assert_eq!(
862                execution_receipt_type::<Test>(
863                    domain_id,
864                    &current_head_receipt.as_execution_receipt_ref()
865                ),
866                ReceiptType::Accepted(AcceptedReceiptType::CurrentHead)
867            );
868            assert_ok!(verify_execution_receipt::<Test>(
869                domain_id,
870                &current_head_receipt.as_execution_receipt_ref()
871            ));
872
873            // Re-submit the head receipt by a different operator is okay
874            let bundle = create_dummy_bundle_with_receipts(
875                domain_id,
876                operator_id2,
877                H256::random(),
878                current_head_receipt,
879            );
880            assert_ok!(crate::Pallet::<Test>::submit_bundle(
881                DomainOrigin::ValidatedUnsigned.into(),
882                bundle,
883            ));
884
885            let head_node = get_block_tree_node_at::<Test>(domain_id, head_receipt_number).unwrap();
886            assert_eq!(head_node.operator_ids, vec![operator_id1, operator_id2]);
887        });
888    }
889
890    #[test]
891    fn test_non_head_receipt() {
892        let creator = 0u128;
893        let operator_id1 = 0u64;
894        let operator_id2 = 1u64;
895        let mut ext = new_test_ext_with_extensions();
896        ext.execute_with(|| {
897            let domain_id = register_genesis_domain(creator, 2);
898            extend_block_tree_from_zero(domain_id, operator_id1, 3);
899
900            // Receipt that confirm a non-head receipt is stale receipt
901            let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
902            let stale_receipt = get_block_tree_node_at::<Test>(domain_id, head_receipt_number - 1)
903                .unwrap()
904                .execution_receipt;
905            let stale_receipt_hash = stale_receipt.hash::<DomainHashingFor<Test>>();
906
907            // Stale receipt can pass the verification
908            assert_eq!(
909                execution_receipt_type::<Test>(
910                    domain_id,
911                    &stale_receipt.as_execution_receipt_ref()
912                ),
913                ReceiptType::Rejected(RejectedReceiptType::Stale)
914            );
915            assert_err!(
916                verify_execution_receipt::<Test>(
917                    domain_id,
918                    &stale_receipt.as_execution_receipt_ref()
919                ),
920                Error::StaleReceipt
921            );
922
923            // Stale receipt will be rejected and won't be added to the block tree
924            let bundle = create_dummy_bundle_with_receipts(
925                domain_id,
926                operator_id2,
927                H256::random(),
928                stale_receipt,
929            );
930            assert!(crate::Pallet::<Test>::submit_bundle(RawOrigin::None.into(), bundle).is_err());
931
932            assert_eq!(
933                BlockTreeNodes::<Test>::get(stale_receipt_hash)
934                    .unwrap()
935                    .operator_ids,
936                vec![operator_id1]
937            );
938        });
939    }
940
941    #[test]
942    fn test_previous_head_receipt() {
943        let creator = 0u128;
944        let operator_id1 = 0u64;
945        let operator_id2 = 1u64;
946        let mut ext = new_test_ext_with_extensions();
947        ext.execute_with(|| {
948            let domain_id = register_genesis_domain(creator, 2);
949            extend_block_tree_from_zero(domain_id, operator_id1, 3);
950
951            // No new receipt submitted in current block
952            assert!(NewAddedHeadReceipt::<Test>::get(domain_id).is_none());
953
954            // Receipt that confirm a head receipt of the previous block is stale receipt
955            let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
956            let previous_head_receipt =
957                get_block_tree_node_at::<Test>(domain_id, head_receipt_number)
958                    .unwrap()
959                    .execution_receipt;
960
961            // Stale receipt can not pass the verification
962            assert_eq!(
963                execution_receipt_type::<Test>(
964                    domain_id,
965                    &previous_head_receipt.as_execution_receipt_ref()
966                ),
967                ReceiptType::Rejected(RejectedReceiptType::Stale)
968            );
969            assert_err!(
970                verify_execution_receipt::<Test>(
971                    domain_id,
972                    &previous_head_receipt.as_execution_receipt_ref()
973                ),
974                Error::StaleReceipt
975            );
976
977            // Stale receipt will be rejected and won't be added to the block tree
978            let bundle = create_dummy_bundle_with_receipts(
979                domain_id,
980                operator_id2,
981                H256::random(),
982                previous_head_receipt,
983            );
984            assert!(crate::Pallet::<Test>::submit_bundle(RawOrigin::None.into(), bundle).is_err());
985        });
986    }
987
988    #[test]
989    fn test_new_branch_receipt() {
990        let creator = 0u128;
991        let operator_id1 = 0u64;
992        let operator_id2 = 1u64;
993        let mut ext = new_test_ext_with_extensions();
994        ext.execute_with(|| {
995            let domain_id = register_genesis_domain(creator, 2);
996            extend_block_tree_from_zero(domain_id, operator_id1, 3);
997
998            let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
999            assert!(BlockTree::<Test>::get(domain_id, head_receipt_number).is_some());
1000
1001            // Construct new branch receipt that fork away from an existing node of
1002            // the block tree
1003            let new_branch_receipt = {
1004                let mut head_receipt =
1005                    get_block_tree_node_at::<Test>(domain_id, head_receipt_number)
1006                        .unwrap()
1007                        .execution_receipt;
1008                head_receipt.set_final_state_root(H256::random());
1009                head_receipt
1010            };
1011            let new_branch_receipt_hash = new_branch_receipt.hash::<DomainHashingFor<Test>>();
1012
1013            // New branch receipt can pass the verification
1014            assert_eq!(
1015                execution_receipt_type::<Test>(
1016                    domain_id,
1017                    &new_branch_receipt.as_execution_receipt_ref()
1018                ),
1019                ReceiptType::Rejected(RejectedReceiptType::NewBranch)
1020            );
1021            assert_err!(
1022                verify_execution_receipt::<Test>(
1023                    domain_id,
1024                    &new_branch_receipt.as_execution_receipt_ref()
1025                ),
1026                Error::NewBranchReceipt
1027            );
1028
1029            // Submit the new branch receipt will be rejected
1030            let bundle = create_dummy_bundle_with_receipts(
1031                domain_id,
1032                operator_id2,
1033                H256::random(),
1034                new_branch_receipt,
1035            );
1036            assert!(crate::Pallet::<Test>::submit_bundle(RawOrigin::None.into(), bundle).is_err());
1037            assert!(BlockTreeNodes::<Test>::get(new_branch_receipt_hash).is_none());
1038        });
1039    }
1040
1041    #[test]
1042    fn test_prune_domain_execution_receipt() {
1043        let creator = 0u128;
1044        let operator_id = 0u64;
1045        let mut ext = new_test_ext_with_extensions();
1046        ext.execute_with(|| {
1047            let domain_id = register_genesis_domain(creator, 1);
1048            let _next_receipt = extend_block_tree_from_zero(domain_id, operator_id, 3);
1049            let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
1050
1051            // freeze domain
1052            assert!(!FrozenDomains::<Test>::get().contains(&domain_id));
1053            Domains::freeze_domain(Origin::<Test>::Root.into(), domain_id).unwrap();
1054            assert!(FrozenDomains::<Test>::get().contains(&domain_id));
1055
1056            // prune execution recept
1057            let head_receipt_hash = BlockTree::<Test>::get(domain_id, head_receipt_number).unwrap();
1058            Domains::prune_domain_execution_receipt(
1059                Origin::<Test>::Root.into(),
1060                domain_id,
1061                head_receipt_hash,
1062            )
1063            .unwrap();
1064            assert_eq!(
1065                HeadReceiptNumber::<Test>::get(domain_id),
1066                head_receipt_number - 1
1067            );
1068
1069            // unfreeze domain
1070            Domains::unfreeze_domain(Origin::<Test>::Root.into(), domain_id).unwrap();
1071            assert!(!FrozenDomains::<Test>::get().contains(&domain_id));
1072        })
1073    }
1074
1075    #[test]
1076    fn test_invalid_receipt() {
1077        let creator = 0u128;
1078        let operator_id = 0u64;
1079        let mut ext = new_test_ext_with_extensions();
1080        ext.execute_with(|| {
1081            let domain_id = register_genesis_domain(creator, 1);
1082            let next_receipt = extend_block_tree_from_zero(domain_id, operator_id, 3);
1083            let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
1084
1085            // Construct a future receipt
1086            let mut future_receipt = next_receipt.clone();
1087            future_receipt.set_domain_block_number(head_receipt_number + 2);
1088            future_receipt.set_consensus_block_number(head_receipt_number as u32 + 2);
1089            ExecutionInbox::<Test>::insert(
1090                (
1091                    domain_id,
1092                    future_receipt.domain_block_number(),
1093                    future_receipt.consensus_block_number(),
1094                ),
1095                future_receipt
1096                    .inboxed_bundles()
1097                    .iter()
1098                    .map(|b| BundleDigest {
1099                        header_hash: H256::random(),
1100                        extrinsics_root: b.extrinsics_root,
1101                        size: 0,
1102                    })
1103                    .collect::<Vec<_>>(),
1104            );
1105            assert_eq!(
1106                execution_receipt_type::<Test>(
1107                    domain_id,
1108                    &future_receipt.as_execution_receipt_ref()
1109                ),
1110                ReceiptType::Rejected(RejectedReceiptType::InFuture)
1111            );
1112            assert_err!(
1113                verify_execution_receipt::<Test>(
1114                    domain_id,
1115                    &future_receipt.as_execution_receipt_ref()
1116                ),
1117                Error::InFutureReceipt
1118            );
1119
1120            // Receipt with unknown extrinsics roots
1121            let mut unknown_extrinsics_roots_receipt = next_receipt.clone();
1122            unknown_extrinsics_roots_receipt
1123                .set_inboxed_bundles(vec![InboxedBundle::valid(H256::random(), H256::random())]);
1124            assert_err!(
1125                verify_execution_receipt::<Test>(
1126                    domain_id,
1127                    &unknown_extrinsics_roots_receipt.as_execution_receipt_ref()
1128                ),
1129                Error::InvalidExtrinsicsRoots
1130            );
1131
1132            // Receipt with unknown consensus block hash
1133            let mut unknown_consensus_block_receipt = next_receipt.clone();
1134            unknown_consensus_block_receipt.set_consensus_block_hash(H256::random());
1135            assert_err!(
1136                verify_execution_receipt::<Test>(
1137                    domain_id,
1138                    &unknown_consensus_block_receipt.as_execution_receipt_ref()
1139                ),
1140                Error::BuiltOnUnknownConsensusBlock
1141            );
1142
1143            // Receipt with unknown parent receipt
1144            let mut unknown_parent_receipt = next_receipt.clone();
1145            unknown_parent_receipt.set_parent_receipt_hash(H256::random());
1146            assert_err!(
1147                verify_execution_receipt::<Test>(
1148                    domain_id,
1149                    &unknown_parent_receipt.as_execution_receipt_ref()
1150                ),
1151                Error::UnknownParentBlockReceipt
1152            );
1153
1154            // Receipt with execution_trace length less than two
1155            let mut invalid_execution_trace_receipt = next_receipt;
1156
1157            // Receipt with only one element in execution trace vector
1158            invalid_execution_trace_receipt.set_execution_traces(vec![
1159                invalid_execution_trace_receipt
1160                    .execution_traces()
1161                    .first()
1162                    .cloned()
1163                    .expect("First element should be there; qed"),
1164            ]);
1165            assert_err!(
1166                verify_execution_receipt::<Test>(
1167                    domain_id,
1168                    &invalid_execution_trace_receipt.as_execution_receipt_ref()
1169                ),
1170                Error::InvalidExecutionTrace
1171            );
1172
1173            // Receipt with zero element in execution trace vector
1174            invalid_execution_trace_receipt.set_execution_traces(vec![]);
1175            assert_err!(
1176                verify_execution_receipt::<Test>(
1177                    domain_id,
1178                    &invalid_execution_trace_receipt.as_execution_receipt_ref()
1179                ),
1180                Error::InvalidExecutionTrace
1181            );
1182        });
1183    }
1184
1185    #[test]
1186    fn test_invalid_receipt_with_head_receipt_already_extended() {
1187        let creator = 0u128;
1188        let operator_id = 0u64;
1189        let mut ext = new_test_ext_with_extensions();
1190        ext.execute_with(|| {
1191            let domain_id = register_genesis_domain(creator, 1);
1192            let next_receipt = extend_block_tree_from_zero(domain_id, operator_id, 3);
1193            let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
1194
1195            // reject extending receipt if the HeadReceiptNumber is already extended
1196            assert!(NewAddedHeadReceipt::<Test>::get(domain_id).is_none());
1197            NewAddedHeadReceipt::<Test>::set(domain_id, Some(H256::random()));
1198
1199            // Construct a future receipt
1200            let mut future_receipt = next_receipt.clone();
1201            future_receipt.set_domain_block_number(head_receipt_number + 1);
1202            future_receipt.set_consensus_block_number(head_receipt_number as u32 + 1);
1203
1204            ExecutionInbox::<Test>::insert(
1205                (
1206                    domain_id,
1207                    future_receipt.domain_block_number(),
1208                    future_receipt.consensus_block_number(),
1209                ),
1210                future_receipt
1211                    .inboxed_bundles()
1212                    .iter()
1213                    .map(|b| BundleDigest {
1214                        header_hash: H256::random(),
1215                        extrinsics_root: b.extrinsics_root,
1216                        size: 0,
1217                    })
1218                    .collect::<Vec<_>>(),
1219            );
1220            assert_eq!(
1221                execution_receipt_type::<Test>(
1222                    domain_id,
1223                    &future_receipt.as_execution_receipt_ref()
1224                ),
1225                ReceiptType::Rejected(RejectedReceiptType::InFuture)
1226            );
1227            assert_err!(
1228                verify_execution_receipt::<Test>(
1229                    domain_id,
1230                    &future_receipt.as_execution_receipt_ref()
1231                ),
1232                Error::InFutureReceipt
1233            );
1234        });
1235    }
1236
1237    #[test]
1238    fn test_invalid_trace_root_receipt() {
1239        let creator = 0u128;
1240        let operator_id1 = 0u64;
1241        let mut ext = new_test_ext_with_extensions();
1242        ext.execute_with(|| {
1243            let domain_id = register_genesis_domain(creator, 2);
1244            let mut next_receipt = extend_block_tree_from_zero(domain_id, operator_id1, 3);
1245            let mut traces = next_receipt.execution_traces().to_vec();
1246            traces.push(H256::random());
1247            next_receipt.set_execution_traces(traces);
1248            next_receipt.set_final_state_root(*next_receipt.execution_traces().last().unwrap());
1249
1250            let mut trace = Vec::with_capacity(next_receipt.execution_traces().len());
1251            for root in next_receipt.execution_traces() {
1252                trace.push(
1253                    root.encode()
1254                        .try_into()
1255                        .map_err(|_| Error::InvalidTraceRoot)
1256                        .expect("H256 to Blake3Hash should be successful; qed"),
1257                );
1258            }
1259            let new_execution_trace_root = MerkleTree::from_leaves(trace.as_slice())
1260                .root()
1261                .expect("Compute merkle root of trace should success")
1262                .into();
1263            next_receipt.set_execution_trace_root(new_execution_trace_root);
1264            assert_ok!(verify_execution_receipt::<Test>(
1265                domain_id,
1266                &next_receipt.as_execution_receipt_ref()
1267            ));
1268
1269            // Receipt with wrong value of `execution_trace_root`
1270            let mut invalid_receipt = next_receipt.clone();
1271            invalid_receipt.set_execution_trace_root(H256::random());
1272            assert_err!(
1273                verify_execution_receipt::<Test>(
1274                    domain_id,
1275                    &invalid_receipt.as_execution_receipt_ref()
1276                ),
1277                Error::InvalidTraceRoot
1278            );
1279
1280            // Receipt with wrong value of trace
1281            let mut invalid_receipt = next_receipt.clone();
1282            let mut traces = invalid_receipt.execution_traces().to_vec();
1283            traces[0] = H256::random();
1284            invalid_receipt.set_execution_traces(traces);
1285            assert_err!(
1286                verify_execution_receipt::<Test>(
1287                    domain_id,
1288                    &invalid_receipt.as_execution_receipt_ref()
1289                ),
1290                Error::InvalidTraceRoot
1291            );
1292
1293            // Receipt with additional trace
1294            let mut invalid_receipt = next_receipt.clone();
1295            let mut traces = invalid_receipt.execution_traces().to_vec();
1296            traces.push(H256::random());
1297            invalid_receipt.set_execution_traces(traces);
1298            assert_err!(
1299                verify_execution_receipt::<Test>(
1300                    domain_id,
1301                    &invalid_receipt.as_execution_receipt_ref()
1302                ),
1303                Error::InvalidTraceRoot
1304            );
1305
1306            // Receipt with missing trace
1307            let mut invalid_receipt = next_receipt;
1308            let mut traces = invalid_receipt.execution_traces().to_vec();
1309            traces.pop();
1310            invalid_receipt.set_execution_traces(traces);
1311            assert_err!(
1312                verify_execution_receipt::<Test>(
1313                    domain_id,
1314                    &invalid_receipt.as_execution_receipt_ref()
1315                ),
1316                Error::InvalidTraceRoot
1317            );
1318        });
1319    }
1320
1321    #[test]
1322    fn test_collect_invalid_bundle_author() {
1323        let creator = 0u128;
1324        let challenge_period = BlockTreePruningDepth::get();
1325        let operator_set: Vec<_> = (0..14).collect();
1326        let mut ext = new_test_ext_with_extensions();
1327        ext.execute_with(|| {
1328            let domain_id = register_genesis_domain(creator, operator_set.len());
1329            let next_receipt = extend_block_tree_from_zero(domain_id, operator_set[0], 3);
1330
1331            // Submit bundle for every operator
1332            for operator_id in operator_set.iter() {
1333                let bundle = create_dummy_bundle_with_receipts(
1334                    domain_id,
1335                    *operator_id,
1336                    H256::random(),
1337                    next_receipt.clone(),
1338                );
1339                assert_ok!(crate::Pallet::<Test>::submit_bundle(
1340                    DomainOrigin::ValidatedUnsigned.into(),
1341                    bundle,
1342                ));
1343            }
1344            let head_receipt_number = HeadReceiptNumber::<Test>::get(domain_id);
1345            let head_node = get_block_tree_node_at::<Test>(domain_id, head_receipt_number).unwrap();
1346            assert_eq!(head_node.operator_ids, operator_set);
1347
1348            // Get the `bundles_extrinsics_roots` that contains all the submitted bundles
1349            let current_block_number = frame_system::Pallet::<Test>::current_block_number();
1350            let execution_inbox = ExecutionInbox::<Test>::get((
1351                domain_id,
1352                current_block_number,
1353                current_block_number,
1354            ));
1355            let bundles_extrinsics_roots: Vec<_> = execution_inbox
1356                .into_iter()
1357                .map(|b| b.extrinsics_root)
1358                .collect();
1359            assert_eq!(bundles_extrinsics_roots.len(), operator_set.len());
1360
1361            // Prepare the invalid bundles and invalid bundle authors
1362            let mut bundles = vec![];
1363            let mut invalid_bundle_authors = vec![];
1364            for (i, (operator, extrinsics_root)) in operator_set
1365                .iter()
1366                .zip(bundles_extrinsics_roots)
1367                .enumerate()
1368            {
1369                if i % 2 == 0 {
1370                    invalid_bundle_authors.push(*operator);
1371                    bundles.push(InboxedBundle::invalid(
1372                        InvalidBundleType::OutOfRangeTx(0),
1373                        extrinsics_root,
1374                    ));
1375                } else {
1376                    bundles.push(InboxedBundle::valid(H256::random(), extrinsics_root));
1377                }
1378            }
1379            let mut target_receipt = create_dummy_receipt(
1380                current_block_number,
1381                H256::random(),
1382                next_receipt.hash::<DomainHashingFor<Test>>(),
1383                vec![],
1384            );
1385            target_receipt.set_inboxed_bundles(bundles);
1386
1387            // Extend the block tree by `challenge_period + 1` blocks
1388            let next_receipt = extend_block_tree(
1389                domain_id,
1390                operator_set[0],
1391                current_block_number + challenge_period + 1u32,
1392                target_receipt,
1393            );
1394            // Confirm `target_receipt`
1395            let confirmed_domain_block = process_execution_receipt::<Test>(
1396                domain_id,
1397                operator_set[0],
1398                next_receipt,
1399                AcceptedReceiptType::NewHead,
1400            )
1401            .unwrap()
1402            .unwrap();
1403
1404            // Invalid bundle authors should be collected correctly
1405            assert_eq!(
1406                confirmed_domain_block.invalid_bundle_authors,
1407                invalid_bundle_authors
1408            );
1409        });
1410    }
1411}