Method new_mid_state

final-spv/src/merkle_tree.rs:105–162

Constructs a "mid-state" Merkle tree, designed for generating secure SPV (Simplified Payment Verification) proofs. This structure, when used with the corresponding `calculate_root_with_merkle_proof` (or `BlockInclusionProof::get_root`) method, helps mitigate vulnerabilities associated with standard Bitcoin Merkle trees in SPV contexts, such as certain forms of hash duplication or ambiguity attacks

(transactions: &[CircuitTransaction])

    /// This acts as a domain separation, ensuring that the internal nodes of this mid-state tree cannot be misinterpreted
    /// as leaf txids or other hash types during verification.
    pub fn new_mid_state(transactions: &[CircuitTransaction]) -> Self {
        if transactions.len() == 1 {
            // root is the coinbase mid-state txid (which is a standard txid)
            return BitcoinMerkleTree {
                nodes: vec![vec![transactions[0].mid_state_txid()]],
            };
        }

        let mid_state_txids: Vec<[u8; 32]> =
            transactions.iter().map(|tx| tx.mid_state_txid()).collect();

        let mut tree = BitcoinMerkleTree {
            nodes: vec![mid_state_txids], // Level 0: Leaf nodes (txids)
        };

        // Construct the tree
        let mut curr_level_offset: usize = 1;
        let mut prev_level_size = tree.nodes[0].len();
        let mut prev_level_index_offset = 0;
        let mut preimage: [u8; 64] = [0; 64]; // Preimage for SHA256(SHA256(LeftChild) || SHA256(RightChild))
        while prev_level_size > 1 {
            tree.nodes.push(vec![]);
            for i in 0..(prev_level_size / 2) {
                let left_child_node =
                    tree.nodes[curr_level_offset - 1][prev_level_index_offset + i * 2];
                let right_child_node =
                    tree.nodes[curr_level_offset - 1][prev_level_index_offset + i * 2 + 1];

                if left_child_node == right_child_node {
                    // This check is also present in the mid-state tree construction.
                    // While the primary defense is in the proof verification, preventing duplicate
                    // inputs at this stage is good practice.
                    panic!("Duplicate hashes in the Merkle tree, indicating mutation");
                }
                // Preimage construction: SHA256(LeftChildNode) || SHA256(RightChildNode)
                preimage[..32].copy_from_slice(&calculate_sha256(&left_child_node));
                preimage[32..].copy_from_slice(&calculate_sha256(&right_child_node));
                // The new node is SHA256 of this preimage
                let combined_mid_state_hash = calculate_sha256(&preimage);
                tree.nodes[curr_level_offset].push(combined_mid_state_hash);
            }
            // Handle odd number of nodes at the previous level by duplicating the last node's hash processing
            if prev_level_size % 2 == 1 {
                let mut preimage: [u8; 64] = [0; 64];
                let last_node = tree.nodes[curr_level_offset - 1]
                    [prev_level_index_offset + prev_level_size - 1];
                // Preimage: SHA256(LastNode) || SHA256(LastNode)
                preimage[..32].copy_from_slice(&calculate_sha256(&last_node));
                preimage[32..].copy_from_slice(&calculate_sha256(&last_node));
                let combined_mid_state_hash = calculate_sha256(&preimage);
                tree.nodes[curr_level_offset].push(combined_mid_state_hash);
            }
            curr_level_offset += 1;
            prev_level_size = prev_level_size.div_ceil(2);
            prev_level_index_offset = 0;
        }
        tree
    }