// TODO: Optimize to avoid allocations
// In current rust generic iterators do not work with recursion :(
Optimize to avoid allocations
In current rust generic iterators do not work with recursion :(
Optimize to avoid allocations In current rust generic iterators do not work with recursion : (
fn merklize_inner(
    engine_proto: &sha256::HashEngine,
    mut iter: impl ExactSizeIterator<Item = MerkleNode>,
    depth: u8,
    extend: bool,
    empty_node: Option<MerkleNode>,
) -> (MerkleNode, u8) {
    let len = iter.len() + extend as usize;
    let empty_node = empty_node.unwrap_or_else(|| MerkleNode::hash(&[0xFF]));
    // Computing tagged hash as per BIP-340
    let mut tag_engine = engine_proto.clone();
    tag_engine.input("depth=".as_bytes());
    tag_engine.input(depth.to_string().as_bytes());
    tag_engine.input(":width=".as_bytes());
    tag_engine.input(len.to_string().as_bytes());
    tag_engine.input(":height=".as_bytes());
    let mut engine = MerkleNode::engine();
    if len <= 2 {
        tag_engine.input("0:".as_bytes());
        let tag_hash =
            sha256::Hash::hash(&sha256::Hash::from_engine(tag_engine));
        engine.input(&tag_hash[..]);
        engine.input(&tag_hash[..]);
        let mut leaf_tag_engine = engine_proto.clone();
        leaf_tag_engine.input("leaf".as_bytes());
        let leaf_tag =
            sha256::Hash::hash(&sha256::Hash::from_engine(leaf_tag_engine));
        let mut leaf_engine = MerkleNode::engine();
        leaf_engine.input(&leaf_tag[..]);
        leaf_engine.input(&leaf_tag[..]);
        let mut leaf1 = leaf_engine.clone();
        leaf1.input(
            iter.next()
                .as_ref()
                .map(|d| d.as_ref())
                .unwrap_or_else(|| empty_node.as_ref()),
        );
        MerkleNode::from_engine(leaf1).commit_encode(&mut engine);
        leaf_engine.input(
            iter.next()
                .as_ref()
                .map(|d| d.as_ref())
                .unwrap_or_else(|| empty_node.as_ref()),
        );
        MerkleNode::from_engine(leaf_engine).commit_encode(&mut engine);
        (MerkleNode::from_engine(engine), 1)
    } else {
        let div = len / 2 + len % 2;
        let (node1, height1) = merklize_inner(
            engine_proto,
            // Normally we should use `iter.by_ref().take(div)`, but currently
            // rust compilers is unable to parse recursion with generic types
            iter.by_ref().take(div).collect::<Vec<_>>().into_iter(),
            depth + 1,
            false,
            Some(empty_node),
        );
        let iter = if extend {
            iter.chain(vec![empty_node]).collect::<Vec<_>>().into_iter()
        } else {
            iter.collect::<Vec<_>>().into_iter()
        };
        let (node2, height2) = merklize_inner(
            engine_proto,
            iter,
            depth + 1,
            (div % 2 + len % 2) / 2 == 1,
            Some(empty_node),
        );
        assert_eq!(
            height1,
            height2,
            "merklization algorithm failure: height of subtrees is not equal \
             (width = {}, depth = {}, prev_extend = {}, next_extend = {})",
            len,
            depth,
            extend,
            div % 2 == 1 && len % 2 == 1
        );
        tag_engine.input(height1.to_string().as_bytes());
        tag_engine.input(":".as_bytes());
        let tag_hash =
            sha256::Hash::hash(&sha256::Hash::from_engine(tag_engine));
        engine.input(&tag_hash[..]);
        engine.input(&tag_hash[..]);
        node1.commit_encode(&mut engine);
        node2.commit_encode(&mut engine);
        (MerkleNode::from_engine(engine), height1 + 1)
    }
}
fn merklize_inner ( engine_proto : & sha256 :: HashEngine , mut iter : impl ExactSizeIterator < Item = MerkleNode > , depth : u8 , extend : bool , empty_node : Option < MerkleNode > , ) -> ( MerkleNode , u8 ) { let len = iter . len ( ) + extend as usize ; let empty_node = empty_node . unwrap_or_else ( | | MerkleNode :: hash ( & [ 0xFF ] ) ) ; // Computing tagged hash as per BIP-340 let mut tag_engine = engine_proto . clone ( ) ; tag_engine . input ( " " . as_bytes ( ) ) ; tag_engine . input ( depth . to_string ( ) . as_bytes ( ) ) ; tag_engine . input ( " " . as_bytes ( ) ) ; tag_engine . input ( len . to_string ( ) . as_bytes ( ) ) ; tag_engine . input ( " " . as_bytes ( ) ) ; let mut engine = MerkleNode :: engine ( ) ; if len <= 2 { tag_engine . input ( " " . as_bytes ( ) ) ; let tag_hash = sha256 :: Hash :: hash ( & sha256 :: Hash :: from_engine ( tag_engine ) ) ; engine . input ( & tag_hash [ .. ] ) ; engine . input ( & tag_hash [ .. ] ) ; let mut leaf_tag_engine = engine_proto . clone ( ) ; leaf_tag_engine . input ( " " . as_bytes ( ) ) ; let leaf_tag = sha256 :: Hash :: hash ( & sha256 :: Hash :: from_engine ( leaf_tag_engine ) ) ; let mut leaf_engine = MerkleNode :: engine ( ) ; leaf_engine . input ( & leaf_tag [ .. ] ) ; leaf_engine . input ( & leaf_tag [ .. ] ) ; let mut leaf1 = leaf_engine . clone ( ) ; leaf1 . input ( iter . next ( ) . as_ref ( ) . map ( | d | d . as_ref ( ) ) . unwrap_or_else ( | | empty_node . as_ref ( ) ) , ) ; MerkleNode :: from_engine ( leaf1 ) . commit_encode ( & mut engine ) ; leaf_engine . input ( iter . next ( ) . as_ref ( ) . map ( | d | d . as_ref ( ) ) . unwrap_or_else ( | | empty_node . as_ref ( ) ) , ) ; MerkleNode :: from_engine ( leaf_engine ) . commit_encode ( & mut engine ) ; ( MerkleNode :: from_engine ( engine ) , 1 ) } else { let div = len / 2 + len % 2 ; let ( node1 , height1 ) = merklize_inner ( engine_proto , // Normally we should use `iter.by_ref().take(div)`, but currently // rust compilers is unable to parse recursion with generic types iter . by_ref ( ) . take ( div ) . collect :: < Vec < _ > > ( ) . into_iter ( ) , depth + 1 , false , Some ( empty_node ) , ) ; let iter = if extend { iter . chain ( vec ! [ empty_node ] ) . collect :: < Vec < _ > > ( ) . into_iter ( ) } else { iter . collect :: < Vec < _ > > ( ) . into_iter ( ) } ; let ( node2 , height2 ) = merklize_inner ( engine_proto , iter , depth + 1 , ( div % 2 + len % 2 ) / 2 == 1 , Some ( empty_node ) , ) ; assert_eq ! ( height1 height2 " \
 " len depth extend div 2 1 len 2 1 ) ; tag_engine . input ( height1 . to_string ( ) . as_bytes ( ) ) ; tag_engine . input ( " " . as_bytes ( ) ) ; let tag_hash = sha256 :: Hash :: hash ( & sha256 :: Hash :: from_engine ( tag_engine ) ) ; engine . input ( & tag_hash [ .. ] ) ; engine . input ( & tag_hash [ .. ] ) ; node1 . commit_encode ( & mut engine ) ; node2 . commit_encode ( & mut engine ) ; ( MerkleNode :: from_engine ( engine ) , height1 + 1 ) } }
TODO: Optimize to avoid allocations
In current rust generic iterators do not work with recursion :(
TODO : Optimize to avoid allocations In current rust generic iterators do not work with recursion : (
engine_proto
&sha256::HashEngine
iter
impl ExactSizeIterator<Item = MerkleNode>
depth
u8
extend
bool
empty_node
Option<MerkleNode>