Method new

final-spv/src/merkle_tree.rs:21–78

Constructs a standard Bitcoin Merkle tree. Leaf nodes are transaction IDs (txids), which are double-SHA256 hashes of transaction data. Internal nodes are formed by `DSHA256(LeftChildHash || RightChildHash)`.

(transactions: Vec<[u8; 32]>)

    /// Leaf nodes are transaction IDs (txids), which are double-SHA256 hashes of transaction data.
    /// Internal nodes are formed by `DSHA256(LeftChildHash || RightChildHash)`.
    pub fn new(transactions: Vec<[u8; 32]>) -> Self {
        if transactions.len() == 1 {
            // root is the coinbase txid
            return BitcoinMerkleTree {
                nodes: vec![transactions],
            };
        }

        let mut tree = BitcoinMerkleTree {
            nodes: vec![transactions],
        };

        // 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];
        while prev_level_size > 1 {
            tree.nodes.push(vec![]);
            for i in 0..(prev_level_size / 2) {
                if tree.nodes[curr_level_offset - 1][prev_level_index_offset + i * 2]
                    == tree.nodes[curr_level_offset - 1][prev_level_index_offset + i * 2 + 1]
                {
                    // This check helps prevent certain attacks involving duplicate hashes,
                    // although the primary defense against CVE-2012-2459 and similar issues
                    // in SPV often requires more structural changes or careful proof verification,
                    // which the `new_mid_state` tree aims to provide. For more, please check:
                    // https://github.com/bitcoin/bitcoin/blob/31d3eebfb92ae0521e18225d69be95e78fb02672/src/consensus/merkle.cpp#L9
                    panic!("Duplicate hashes in the Merkle tree, indicating mutation");
                }
                preimage[..32].copy_from_slice(
                    &tree.nodes[curr_level_offset - 1][prev_level_index_offset + i * 2],
                );
                preimage[32..].copy_from_slice(
                    &tree.nodes[curr_level_offset - 1][prev_level_index_offset + i * 2 + 1],
                );
                let combined_hash = calculate_double_sha256(&preimage);
                tree.nodes[curr_level_offset].push(combined_hash);
            }
            if prev_level_size % 2 == 1 {
                let mut preimage: [u8; 64] = [0; 64];
                preimage[..32].copy_from_slice(
                    &tree.nodes[curr_level_offset - 1]
                        [prev_level_index_offset + prev_level_size - 1],
                );
                preimage[32..].copy_from_slice(
                    &tree.nodes[curr_level_offset - 1]
                        [prev_level_index_offset + prev_level_size - 1],
                );
                let combined_hash = calculate_double_sha256(&preimage);
                tree.nodes[curr_level_offset].push(combined_hash);
            }
            curr_level_offset += 1;
            prev_level_size = prev_level_size.div_ceil(2);
            prev_level_index_offset = 0;
        }
        tree
    }