sc_consensus_nakamoto/
block_preparation.rs

1//! Block preparation and verification abstractions.
2//!
3//! This module provides data structures for efficient block verification:
4//! - [`UtxoProvider`]: Trait for abstracting UTXO access from different backends
5//! - [`TxExecutionLevels`]: Groups transactions by parallel execution level
6//! - [`PreparedBlock`]: Block with pre-fetched UTXOs ready for verification
7//! - [`VerifiedBlock`]: A block that passed verification, ready to apply to state
8//!
9//! # Design Goals
10//!
11//! 1. **Eliminate duplicate UTXO lookups**: Fetch UTXOs once during prepare, reuse in verify and apply
12//! 2. **Enable batch fetching**: Single batch read instead of N individual reads
13//! 3. **Support parallel verification**: TxExecutionLevels identifies independent transactions
14//! 4. **Backend agnostic**: UtxoProvider works with Substrate state or native storage
15
16use bitcoin::{Block, OutPoint, TxOut};
17use std::collections::{HashMap, HashSet};
18use subcoin_primitives::runtime::Coin;
19
20/// Abstraction for UTXO access.
21///
22/// This trait decouples block verification from storage implementation,
23/// enabling:
24/// - Substrate state lookups during normal operation
25/// - Native RocksDB lookups for optimized storage
26/// - Pre-fetched data during batch verification
27/// - Cached lookups for improved performance
28pub trait UtxoProvider {
29    /// Get a single UTXO by outpoint.
30    ///
31    /// Returns `None` if the UTXO doesn't exist.
32    fn get(&self, outpoint: &OutPoint) -> Option<Coin>;
33
34    /// Batch-fetch multiple UTXOs.
35    ///
36    /// Returns a map containing only the UTXOs that were found.
37    /// Missing outpoints are silently omitted from the result.
38    ///
39    /// Default implementation calls `get()` for each outpoint.
40    /// Implementations should override for better performance.
41    fn batch_get(&self, outpoints: &[OutPoint]) -> HashMap<OutPoint, Coin> {
42        outpoints
43            .iter()
44            .filter_map(|op| self.get(op).map(|coin| (*op, coin)))
45            .collect()
46    }
47}
48
49/// Implementation for HashMap (used with pre-fetched UTXOs).
50///
51/// This allows verification to use pre-fetched data without
52/// any storage access.
53impl UtxoProvider for HashMap<OutPoint, Coin> {
54    fn get(&self, outpoint: &OutPoint) -> Option<Coin> {
55        HashMap::get(self, outpoint).cloned()
56    }
57
58    fn batch_get(&self, outpoints: &[OutPoint]) -> HashMap<OutPoint, Coin> {
59        outpoints
60            .iter()
61            .filter_map(|op| HashMap::get(self, op).map(|coin| (*op, coin.clone())))
62            .collect()
63    }
64}
65
66/// Transactions grouped by parallel execution level.
67///
68/// - Level 0: No in-block dependencies (coinbase, txs spending only external UTXOs)
69/// - Level 1: Depends only on level 0 transactions
70/// - Level N: Depends only on levels < N
71///
72/// All transactions within the same level can execute in parallel.
73#[derive(Debug, Clone)]
74pub struct TxExecutionLevels {
75    /// levels[i] contains indices of transactions that can run at level i.
76    levels: Vec<Vec<usize>>,
77}
78
79impl TxExecutionLevels {
80    /// Build execution levels by analyzing in-block dependencies.
81    ///
82    /// A transaction at index `i` depends on transaction at index `j` (where `j < i`)
83    /// if transaction `i` spends an output created by transaction `j`.
84    pub fn build(block: &Block) -> Self {
85        let tx_count = block.txdata.len();
86
87        if tx_count == 0 {
88            return Self { levels: vec![] };
89        }
90
91        // Track which outputs are created by which transaction
92        let mut output_creators: HashMap<OutPoint, usize> = HashMap::new();
93
94        // Track dependencies for each transaction
95        // dependencies[i] = set of tx indices that tx i depends on
96        let mut dependencies: Vec<HashSet<usize>> = vec![HashSet::new(); tx_count];
97
98        for (tx_idx, tx) in block.txdata.iter().enumerate() {
99            let txid = tx.compute_txid();
100
101            // Record outputs created by this transaction
102            for vout in 0..tx.output.len() {
103                let outpoint = OutPoint {
104                    txid,
105                    vout: vout as u32,
106                };
107                output_creators.insert(outpoint, tx_idx);
108            }
109
110            // Check if any input is from a tx in this block (skip coinbase)
111            if tx_idx > 0 {
112                for input in &tx.input {
113                    if let Some(&creator_idx) = output_creators.get(&input.previous_output) {
114                        dependencies[tx_idx].insert(creator_idx);
115                    }
116                }
117            }
118        }
119
120        // Build levels using topological sort
121        Self::topological_levels(&dependencies)
122    }
123
124    /// Convert dependencies into parallel execution levels.
125    fn topological_levels(dependencies: &[HashSet<usize>]) -> Self {
126        let n = dependencies.len();
127
128        if n == 0 {
129            return Self { levels: vec![] };
130        }
131
132        // Compute in-degree (number of dependencies) for each tx
133        let mut in_degree: Vec<usize> = dependencies.iter().map(|deps| deps.len()).collect();
134
135        // Track which transactions depend on each transaction
136        let mut dependents: Vec<Vec<usize>> = vec![Vec::new(); n];
137        for (tx_idx, deps) in dependencies.iter().enumerate() {
138            for &dep in deps {
139                dependents[dep].push(tx_idx);
140            }
141        }
142
143        let mut levels = Vec::new();
144        let mut remaining: HashSet<usize> = (0..n).collect();
145
146        while !remaining.is_empty() {
147            // Find all txs with no remaining dependencies (in_degree == 0)
148            let level: Vec<usize> = remaining
149                .iter()
150                .filter(|&&idx| in_degree[idx] == 0)
151                .copied()
152                .collect();
153
154            if level.is_empty() {
155                // This shouldn't happen in valid Bitcoin blocks
156                // (would indicate a cycle, which is impossible)
157                panic!("Cycle detected in transaction dependencies - invalid block");
158            }
159
160            // Remove processed txs and update in-degrees
161            for &tx_idx in &level {
162                remaining.remove(&tx_idx);
163                for &dependent in &dependents[tx_idx] {
164                    in_degree[dependent] = in_degree[dependent].saturating_sub(1);
165                }
166            }
167
168            levels.push(level);
169        }
170
171        Self { levels }
172    }
173
174    /// Returns the number of execution levels.
175    ///
176    /// A value of 1 means all transactions can run in parallel.
177    /// Higher values indicate more sequential dependencies.
178    pub fn depth(&self) -> usize {
179        self.levels.len()
180    }
181
182    /// Returns true if all transactions can execute in parallel (single level).
183    pub fn is_fully_parallel(&self) -> bool {
184        self.levels.len() <= 1
185    }
186
187    /// Iterate over levels for parallel execution.
188    pub fn iter(&self) -> impl Iterator<Item = &[usize]> {
189        self.levels.iter().map(|v| v.as_slice())
190    }
191
192    /// Get a specific level.
193    pub fn get_level(&self, level: usize) -> Option<&[usize]> {
194        self.levels.get(level).map(|v| v.as_slice())
195    }
196
197    /// Total number of transactions across all levels.
198    pub fn tx_count(&self) -> usize {
199        self.levels.iter().map(|l| l.len()).sum()
200    }
201}
202
203/// In-block output information.
204#[derive(Debug, Clone)]
205pub struct InBlockOutput {
206    /// The transaction output.
207    pub txout: TxOut,
208    /// Whether this is from the coinbase transaction.
209    pub is_coinbase: bool,
210    /// Index of the transaction that created this output.
211    pub tx_index: usize,
212}
213
214/// A block with pre-fetched UTXOs ready for verification.
215///
216/// This structure enables efficient verification by:
217/// 1. Pre-fetching all required UTXOs in a single batch
218/// 2. Tracking in-block outputs for same-block spending
219/// 3. Providing execution levels for parallel verification
220#[derive(Debug)]
221pub struct PreparedBlock {
222    /// The Bitcoin block.
223    pub block: Block,
224    /// Block height.
225    pub height: u32,
226    /// Pre-fetched UTXOs for inputs spending external outputs.
227    /// Key: OutPoint being spent
228    /// Value: The Coin (UTXO) data
229    pub input_utxos: HashMap<OutPoint, Coin>,
230    /// Outputs created within this block (for in-block spending).
231    pub in_block_outputs: HashMap<OutPoint, InBlockOutput>,
232    /// Transaction execution levels for intra-block parallelism.
233    pub execution_levels: TxExecutionLevels,
234}
235
236impl PreparedBlock {
237    /// Prepare a block for verification by pre-fetching required UTXOs.
238    ///
239    /// This method:
240    /// 1. Scans the block to identify all required outpoints
241    /// 2. Separates external UTXOs from in-block outputs
242    /// 3. Batch-fetches external UTXOs from the provider
243    /// 4. Builds execution levels for parallel verification
244    pub fn prepare<P: UtxoProvider>(block: Block, height: u32, utxo_provider: &P) -> Self {
245        // First pass: collect in-block outputs
246        let mut in_block_outputs: HashMap<OutPoint, InBlockOutput> = HashMap::new();
247
248        for (tx_idx, tx) in block.txdata.iter().enumerate() {
249            let txid = tx.compute_txid();
250            let is_coinbase = tx_idx == 0;
251
252            for (vout, txout) in tx.output.iter().enumerate() {
253                let outpoint = OutPoint {
254                    txid,
255                    vout: vout as u32,
256                };
257                in_block_outputs.insert(
258                    outpoint,
259                    InBlockOutput {
260                        txout: txout.clone(),
261                        is_coinbase,
262                        tx_index: tx_idx,
263                    },
264                );
265            }
266        }
267
268        // Second pass: collect external outpoints to fetch
269        let mut external_outpoints: Vec<OutPoint> = Vec::new();
270
271        for tx in block.txdata.iter().skip(1) {
272            // Skip coinbase
273            for input in &tx.input {
274                if !in_block_outputs.contains_key(&input.previous_output) {
275                    external_outpoints.push(input.previous_output);
276                }
277            }
278        }
279
280        // Batch-fetch external UTXOs
281        let input_utxos = utxo_provider.batch_get(&external_outpoints);
282
283        // Build execution levels
284        let execution_levels = TxExecutionLevels::build(&block);
285
286        Self {
287            block,
288            height,
289            input_utxos,
290            in_block_outputs,
291            execution_levels,
292        }
293    }
294
295    /// Get a UTXO needed for verification.
296    ///
297    /// Checks in-block outputs first, then pre-fetched external UTXOs.
298    /// Returns (TxOut, is_coinbase, coin_height).
299    pub fn get_utxo(&self, outpoint: &OutPoint) -> Option<(TxOut, bool, u32)> {
300        // Check in-block outputs first
301        if let Some(in_block) = self.in_block_outputs.get(outpoint) {
302            return Some((in_block.txout.clone(), in_block.is_coinbase, self.height));
303        }
304
305        // Check pre-fetched external UTXOs
306        if let Some(coin) = self.input_utxos.get(outpoint) {
307            let txout = TxOut {
308                value: bitcoin::Amount::from_sat(coin.amount),
309                script_pubkey: bitcoin::ScriptBuf::from_bytes(coin.script_pubkey.clone()),
310            };
311            return Some((txout, coin.is_coinbase, coin.height));
312        }
313
314        None
315    }
316
317    /// Check if all required external UTXOs were found.
318    ///
319    /// Returns a list of missing outpoints if any are missing.
320    pub fn missing_utxos(&self) -> Vec<OutPoint> {
321        let mut missing = Vec::new();
322
323        for tx in self.block.txdata.iter().skip(1) {
324            for input in &tx.input {
325                let outpoint = &input.previous_output;
326                if !self.in_block_outputs.contains_key(outpoint)
327                    && !self.input_utxos.contains_key(outpoint)
328                {
329                    missing.push(*outpoint);
330                }
331            }
332        }
333
334        missing
335    }
336
337    /// Returns the number of transactions in the block.
338    pub fn tx_count(&self) -> usize {
339        self.block.txdata.len()
340    }
341
342    /// Returns the block hash.
343    pub fn block_hash(&self) -> bitcoin::BlockHash {
344        self.block.block_hash()
345    }
346
347    /// Convert to a VerifiedBlock after successful verification.
348    ///
349    /// This transfers ownership of the pre-fetched UTXOs to the VerifiedBlock,
350    /// allowing apply_verified_block to use them without re-fetching.
351    pub fn into_verified(self, script_verification_duration: std::time::Duration) -> VerifiedBlock {
352        VerifiedBlock {
353            block: self.block,
354            height: self.height,
355            spent_utxos: self.input_utxos,
356            script_verification_duration,
357        }
358    }
359}
360
361/// A block that has passed verification, ready to apply to state.
362///
363/// This structure carries the pre-fetched UTXOs from verification,
364/// eliminating duplicate lookups when applying the block.
365#[derive(Debug)]
366pub struct VerifiedBlock {
367    /// The Bitcoin block.
368    pub block: Block,
369    /// Block height.
370    pub height: u32,
371    /// Pre-fetched UTXOs that were spent by this block.
372    /// These are the external UTXOs (not in-block spending).
373    /// Passed through from verification so apply doesn't need to re-fetch.
374    pub spent_utxos: HashMap<OutPoint, Coin>,
375    /// Time spent on script verification.
376    pub script_verification_duration: std::time::Duration,
377}
378
379impl VerifiedBlock {
380    /// Returns the block hash.
381    pub fn block_hash(&self) -> bitcoin::BlockHash {
382        self.block.block_hash()
383    }
384
385    /// Get a spent UTXO by outpoint.
386    ///
387    /// Only contains external UTXOs (not in-block outputs).
388    pub fn get_spent_utxo(&self, outpoint: &OutPoint) -> Option<&Coin> {
389        self.spent_utxos.get(outpoint)
390    }
391
392    /// Returns the number of transactions in the block.
393    pub fn tx_count(&self) -> usize {
394        self.block.txdata.len()
395    }
396}
397
398#[cfg(test)]
399mod tests {
400    use super::*;
401    use bitcoin::absolute::LockTime;
402    use bitcoin::blockdata::block::{Header, Version};
403    use bitcoin::blockdata::transaction::{Transaction, TxIn, Version as TxVersion};
404    use bitcoin::hashes::Hash;
405    use bitcoin::{Amount, CompactTarget, ScriptBuf, Sequence, Witness};
406
407    fn create_coinbase(height: u32) -> Transaction {
408        let script = vec![0x01, height as u8];
409        Transaction {
410            version: TxVersion::TWO,
411            lock_time: LockTime::ZERO,
412            input: vec![TxIn {
413                previous_output: OutPoint::null(),
414                script_sig: ScriptBuf::from_bytes(script),
415                sequence: Sequence::MAX,
416                witness: Witness::new(),
417            }],
418            output: vec![bitcoin::TxOut {
419                value: Amount::from_sat(5_000_000_000),
420                script_pubkey: ScriptBuf::new_p2pkh(&bitcoin::PubkeyHash::all_zeros()),
421            }],
422        }
423    }
424
425    fn create_spending_tx(inputs: &[OutPoint]) -> Transaction {
426        Transaction {
427            version: TxVersion::TWO,
428            lock_time: LockTime::ZERO,
429            input: inputs
430                .iter()
431                .map(|op| TxIn {
432                    previous_output: *op,
433                    script_sig: ScriptBuf::new(),
434                    sequence: Sequence::MAX,
435                    witness: Witness::new(),
436                })
437                .collect(),
438            output: vec![bitcoin::TxOut {
439                value: Amount::from_sat(1_000_000),
440                script_pubkey: ScriptBuf::new_p2pkh(&bitcoin::PubkeyHash::all_zeros()),
441            }],
442        }
443    }
444
445    fn create_block(txs: Vec<Transaction>) -> Block {
446        Block {
447            header: Header {
448                version: Version::TWO,
449                prev_blockhash: bitcoin::BlockHash::all_zeros(),
450                merkle_root: bitcoin::TxMerkleNode::all_zeros(),
451                time: 0,
452                bits: CompactTarget::from_consensus(0),
453                nonce: 0,
454            },
455            txdata: txs,
456        }
457    }
458
459    fn test_coin(amount: u64) -> Coin {
460        Coin {
461            is_coinbase: false,
462            amount,
463            height: 100,
464            script_pubkey: vec![0x51],
465        }
466    }
467
468    #[test]
469    fn test_hashmap_provider() {
470        let mut utxos = HashMap::new();
471        let outpoint1 = OutPoint {
472            txid: bitcoin::Txid::from_byte_array([1; 32]),
473            vout: 0,
474        };
475        let outpoint2 = OutPoint {
476            txid: bitcoin::Txid::from_byte_array([2; 32]),
477            vout: 0,
478        };
479        utxos.insert(outpoint1, test_coin(1000));
480        utxos.insert(outpoint2, test_coin(2000));
481
482        // Test get
483        assert!(utxos.get(&outpoint1).is_some());
484        let missing = OutPoint {
485            txid: bitcoin::Txid::from_byte_array([99; 32]),
486            vout: 0,
487        };
488        assert!(UtxoProvider::get(&utxos, &missing).is_none());
489
490        // Test batch_get
491        let result = utxos.batch_get(&[outpoint1, outpoint2, missing]);
492        assert_eq!(result.len(), 2);
493        assert!(result.contains_key(&outpoint1));
494        assert!(result.contains_key(&outpoint2));
495        assert!(!result.contains_key(&missing));
496    }
497
498    #[test]
499    fn test_prepared_block_external_utxos() {
500        let coinbase = create_coinbase(1);
501
502        let external_utxo = OutPoint {
503            txid: bitcoin::Txid::from_byte_array([99; 32]),
504            vout: 0,
505        };
506
507        let tx1 = create_spending_tx(&[external_utxo]);
508        let block = create_block(vec![coinbase, tx1]);
509
510        // Create mock UTXO provider with the external UTXO
511        let mut utxos: HashMap<OutPoint, Coin> = HashMap::new();
512        utxos.insert(
513            external_utxo,
514            Coin {
515                is_coinbase: false,
516                amount: 5_000_000,
517                height: 50,
518                script_pubkey: vec![0x51],
519            },
520        );
521
522        let prepared = PreparedBlock::prepare(block, 100, &utxos);
523
524        // Should have the external UTXO pre-fetched
525        assert!(prepared.input_utxos.contains_key(&external_utxo));
526        assert!(prepared.missing_utxos().is_empty());
527
528        // get_utxo should return the external UTXO with correct height
529        let (_, is_coinbase, height) = prepared.get_utxo(&external_utxo).unwrap();
530        assert!(!is_coinbase);
531        assert_eq!(height, 50); // Original height, not block height
532    }
533
534    #[test]
535    fn test_prepared_block_in_block_spending() {
536        let coinbase = create_coinbase(1);
537        let coinbase_out = OutPoint {
538            txid: coinbase.compute_txid(),
539            vout: 0,
540        };
541
542        // tx1 spends coinbase (in-block)
543        let tx1 = create_spending_tx(&[coinbase_out]);
544        let block = create_block(vec![coinbase, tx1]);
545
546        // Empty provider - no external UTXOs needed
547        let utxos: HashMap<OutPoint, Coin> = HashMap::new();
548
549        let prepared = PreparedBlock::prepare(block, 100, &utxos);
550
551        // Coinbase output should be in in_block_outputs
552        assert!(prepared.in_block_outputs.contains_key(&coinbase_out));
553        assert!(prepared.missing_utxos().is_empty());
554
555        // get_utxo should return it with block height
556        let (_, is_coinbase, height) = prepared.get_utxo(&coinbase_out).unwrap();
557        assert!(is_coinbase);
558        assert_eq!(height, 100); // Block height for in-block outputs
559    }
560
561    #[test]
562    fn test_prepared_block_missing_utxo() {
563        let coinbase = create_coinbase(1);
564
565        let external_utxo = OutPoint {
566            txid: bitcoin::Txid::from_byte_array([99; 32]),
567            vout: 0,
568        };
569
570        let tx1 = create_spending_tx(&[external_utxo]);
571        let block = create_block(vec![coinbase, tx1]);
572
573        // Empty provider - UTXO not found
574        let utxos: HashMap<OutPoint, Coin> = HashMap::new();
575
576        let prepared = PreparedBlock::prepare(block, 100, &utxos);
577
578        // Should report missing UTXO
579        let missing = prepared.missing_utxos();
580        assert_eq!(missing.len(), 1);
581        assert_eq!(missing[0], external_utxo);
582    }
583
584    // TxExecutionLevels tests
585
586    #[test]
587    fn test_execution_levels_no_dependencies() {
588        // Block with coinbase + 3 independent txs (all spend external UTXOs)
589        let coinbase = create_coinbase(1);
590
591        let external_utxo1 = OutPoint {
592            txid: bitcoin::Txid::from_byte_array([1; 32]),
593            vout: 0,
594        };
595        let external_utxo2 = OutPoint {
596            txid: bitcoin::Txid::from_byte_array([2; 32]),
597            vout: 0,
598        };
599        let external_utxo3 = OutPoint {
600            txid: bitcoin::Txid::from_byte_array([3; 32]),
601            vout: 0,
602        };
603
604        let tx1 = create_spending_tx(&[external_utxo1]);
605        let tx2 = create_spending_tx(&[external_utxo2]);
606        let tx3 = create_spending_tx(&[external_utxo3]);
607
608        let block = create_block(vec![coinbase, tx1, tx2, tx3]);
609        let levels = TxExecutionLevels::build(&block);
610
611        // All 4 txs should be in level 0 (no dependencies)
612        assert_eq!(levels.depth(), 1);
613        assert!(levels.is_fully_parallel());
614        assert_eq!(levels.tx_count(), 4);
615
616        let level0 = levels.get_level(0).unwrap();
617        assert_eq!(level0.len(), 4);
618    }
619
620    #[test]
621    fn test_execution_levels_chain_dependency() {
622        // tx0 (coinbase) -> tx1 -> tx2 -> tx3 (chain of dependencies)
623        let coinbase = create_coinbase(1);
624        let coinbase_out = OutPoint {
625            txid: coinbase.compute_txid(),
626            vout: 0,
627        };
628
629        let tx1 = create_spending_tx(&[coinbase_out]);
630        let tx1_out = OutPoint {
631            txid: tx1.compute_txid(),
632            vout: 0,
633        };
634
635        let tx2 = create_spending_tx(&[tx1_out]);
636        let tx2_out = OutPoint {
637            txid: tx2.compute_txid(),
638            vout: 0,
639        };
640
641        let tx3 = create_spending_tx(&[tx2_out]);
642
643        let block = create_block(vec![coinbase, tx1, tx2, tx3]);
644        let levels = TxExecutionLevels::build(&block);
645
646        // Should have 4 levels: [coinbase], [tx1], [tx2], [tx3]
647        assert_eq!(levels.depth(), 4);
648        assert!(!levels.is_fully_parallel());
649
650        assert_eq!(levels.get_level(0).unwrap(), &[0]); // coinbase
651        assert_eq!(levels.get_level(1).unwrap(), &[1]); // tx1
652        assert_eq!(levels.get_level(2).unwrap(), &[2]); // tx2
653        assert_eq!(levels.get_level(3).unwrap(), &[3]); // tx3
654    }
655
656    #[test]
657    fn test_execution_levels_diamond_dependency() {
658        // Diamond pattern:
659        //       coinbase
660        //       /      \
661        //     tx1      tx2  (both spend coinbase, can run in parallel)
662        //       \      /
663        //         tx3      (spends both tx1 and tx2)
664
665        let coinbase = create_coinbase(1);
666
667        // Coinbase with 2 outputs
668        let mut coinbase_2out = coinbase.clone();
669        coinbase_2out.output.push(bitcoin::TxOut {
670            value: Amount::from_sat(1_000_000),
671            script_pubkey: ScriptBuf::new_p2pkh(&bitcoin::PubkeyHash::all_zeros()),
672        });
673
674        let coinbase_out0 = OutPoint {
675            txid: coinbase_2out.compute_txid(),
676            vout: 0,
677        };
678        let coinbase_out1 = OutPoint {
679            txid: coinbase_2out.compute_txid(),
680            vout: 1,
681        };
682
683        let tx1 = create_spending_tx(&[coinbase_out0]);
684        let tx1_out = OutPoint {
685            txid: tx1.compute_txid(),
686            vout: 0,
687        };
688
689        let tx2 = create_spending_tx(&[coinbase_out1]);
690        let tx2_out = OutPoint {
691            txid: tx2.compute_txid(),
692            vout: 0,
693        };
694
695        let tx3 = create_spending_tx(&[tx1_out, tx2_out]);
696
697        let block = create_block(vec![coinbase_2out, tx1, tx2, tx3]);
698        let levels = TxExecutionLevels::build(&block);
699
700        // Should have 3 levels:
701        // Level 0: [coinbase]
702        // Level 1: [tx1, tx2] - both depend only on coinbase
703        // Level 2: [tx3] - depends on tx1 and tx2
704        assert_eq!(levels.depth(), 3);
705
706        assert_eq!(levels.get_level(0).unwrap(), &[0]);
707        let level1 = levels.get_level(1).unwrap();
708        assert_eq!(level1.len(), 2);
709        assert!(level1.contains(&1));
710        assert!(level1.contains(&2));
711        assert_eq!(levels.get_level(2).unwrap(), &[3]);
712    }
713
714    #[test]
715    fn test_empty_block() {
716        let block = create_block(vec![]);
717        let levels = TxExecutionLevels::build(&block);
718
719        assert_eq!(levels.depth(), 0);
720        assert!(levels.is_fully_parallel());
721        assert_eq!(levels.tx_count(), 0);
722    }
723
724    #[test]
725    fn test_coinbase_only_block() {
726        let coinbase = create_coinbase(1);
727        let block = create_block(vec![coinbase]);
728
729        let levels = TxExecutionLevels::build(&block);
730
731        assert_eq!(levels.depth(), 1);
732        assert!(levels.is_fully_parallel());
733        assert_eq!(levels.tx_count(), 1);
734    }
735}
sc_consensus_nakamoto/block_preparation.rs

sc_consensus_nakamoto/
block_preparation.rs
