/// Constructs a witness for the specified partial tree.
///
/// # Panics
///
/// Panics if the partial tree a structure that is different from the
/// labeled tree that was used to construct this hash tree.
Constructs a witness for the specified partial tree.
Constructs a witness for the specified partial tree .
pub fn witness<B: WitnessBuilder>(&self, partial_tree: &LabeledTree<Vec<u8>>) -> B::Tree {
        fn add_forks<B: WitnessBuilder>(
            ht: &HashTree,
            pos: NodeId,
            offset: usize,
            size: usize,
            subwitness: B::Tree,
        ) -> B::Tree {
            // WARNING: FANCY DISCRETE MATH AHEAD
            //
            // The hash trees we build have a particular structure not reflected
            // in the type: all the children of forks are either forks or nodes.
            //
            // Furthermore, because of the way we build forks (pairing vertices
            // from left to right until there is only one left), they form a
            // very specific structure that is fully determined by the number of
            // nodes we had in the beginning.  Most importantly, we can compute
            // the path to K-th node without having to search it by label.
            //
            // The main observation is that if we build a subtree out of N
            // nodes, the binary representation of N can be used to determine
            // the structure of the tree we get.
            //
            // It's easy to prove by induction that if
            //
            //   N = 2^k_1 + 2^k_2 + ... + 2^k^m  (k_1 > k_2 > ... k_m)
            //
            // where k_i corresponds to the position of i-th non-zero bit of N,
            // then the tree has a shape of _m_ full binary trees (FBTs), where
            // j-th tree has k_j leaf nodes, grouped from right to left:
            //
            //    T = FBT(k_1) ^ (FBT(k_2) ^ ( ... ^ FBT(k_m)))
            //
            // Example: if N = 7 = 0b111, we have 3 FBTs with 4, 2 and 1 leaves:
            //        ^
            //    ^      ^
            //  ^   ^   ^ `
            // 0 1 2 3 4 5 6
            //
            // So if we need to locate i-th leaf node out of N in T, we can
            // follow the following procedure locate(T, i, N):
            //
            //   locate(T, 0, 1) = T
            //   locate(T, i, N = 2^k) = if i < N/2
            //                           then locate(left(T),  i,     N/2)
            //                           else locate(right(T), i-N/2, N/2)
            //   locate(T, i, N = 2^k + M) = if i < 2^k
            //                               then locate(left(T),  i,     2^k)
            //                               else locate(right(T), i-2^k, M)
            match ht.view(pos) {
                HashTreeView::Fork(_, l, r) => {
                    if size.is_power_of_two() {
                        let h = size / 2;
                        if offset < h {
                            B::make_fork(
                                add_forks::<B>(ht, l, offset, h, subwitness),
                                B::make_pruned(ht.digest(r).clone()),
                            )
                        } else {
                            B::make_fork(
                                B::make_pruned(ht.digest(l).clone()),
                                add_forks::<B>(ht, r, offset - h, h, subwitness),
                            )
                        }
                    } else {
                        let k = 32 - (size as u32).leading_zeros();
                        let mask = 1 << (k - 1);
                        if offset < mask {
                            B::make_fork(
                                add_forks::<B>(ht, l, offset, mask, subwitness),
                                B::make_pruned(ht.digest(r).clone()),
                            )
                        } else {
                            B::make_fork(
                                B::make_pruned(ht.digest(l).clone()),
                                add_forks::<B>(ht, r, offset - mask, size - mask, subwitness),
                            )
                        }
                    }
                }
                _ => subwitness,
            }
        }
        fn child_witness<B: WitnessBuilder>(
            ht: &HashTree,
            parent: NodeId,
            pos: NodeId,
            l: &Label,
            subtree: &LabeledTree<Vec<u8>>,
        ) -> B::Tree {
            let label_range = ht.node_labels_range(parent);
            let len = label_range.end - label_range.start;
            let labels = &ht.node_labels[label_range.clone()];
            match labels.binary_search(l) {
                Ok(offset) => {
                    let idx = label_range.start + offset;
                    let node_id = NodeId::node(idx);
                    let subwitness = B::make_node(
                        l.clone(),
                        go::<B>(ht, node_id, ht.node_children[idx], subtree),
                    );
                    if pos.kind() == NodeKind::Node {
                        subwitness
                    } else {
                        add_forks::<B>(ht, pos, offset, len, subwitness)
                    }
                }
                Err(offset) => {
                    let pruned_label_at = |o| {
                        add_forks::<B>(
                            ht,
                            pos,
                            o,
                            len,
                            B::make_node(
                                ht.node_labels[label_range.start + o].clone(),
                                B::make_pruned(
                                    ht.digest(ht.node_children[label_range.start + o]).clone(),
                                ),
                            ),
                        )
                    };
                    // Build a proof of absence
                    if offset == 0 {
                        // The missing child is before the first label.
                        pruned_label_at(offset)
                    } else if offset == len {
                        // The missing child is after the last label.
                        pruned_label_at(offset - 1)
                    } else {
                        // The missing child is between two present children.
                        B::merge_trees(pruned_label_at(offset - 1), pruned_label_at(offset))
                    }
                }
            }
        }
        fn go<B: WitnessBuilder>(
            ht: &HashTree,
            parent: NodeId,
            pos: NodeId,
            t: &LabeledTree<Vec<u8>>,
        ) -> B::Tree {
            match t {
                LabeledTree::Leaf(data) => {
                    if pos.kind() == NodeKind::Leaf {
                        B::make_leaf(&data[..])
                    } else {
                        panic!(
                            "inconsistent tree structure: not a leaf in the original tree, \
                             parent = {:?}, pos = {:?}, hash_tree = {:?}, labeled_tree = {:?}",
                            parent, pos, ht, t
                        );
                    }
                }
                LabeledTree::SubTree(children) => children
                    .iter()
                    .map(|(l, t)| child_witness::<B>(ht, parent, pos, l, t))
                    .fold(B::make_pruned(ht.digest(pos).clone()), B::merge_trees),
            }
        }
        go::<B>(self, NodeId::empty(), self.root, partial_tree)
    }
pub fn witness < B : WitnessBuilder > ( & self , partial_tree : & LabeledTree < Vec < u8 > > ) -> B :: Tree { fn add_forks < B : WitnessBuilder > ( ht : & HashTree , pos : NodeId , offset : usize , size : usize , subwitness : B :: Tree , ) -> B :: Tree { // WARNING: FANCY DISCRETE MATH AHEAD // // The hash trees we build have a particular structure not reflected // in the type: all the children of forks are either forks or nodes. // // Furthermore, because of the way we build forks (pairing vertices // from left to right until there is only one left), they form a // very specific structure that is fully determined by the number of // nodes we had in the beginning.  Most importantly, we can compute // the path to K-th node without having to search it by label. // // The main observation is that if we build a subtree out of N // nodes, the binary representation of N can be used to determine // the structure of the tree we get. // // It's easy to prove by induction that if // //   N = 2^k_1 + 2^k_2 + ... + 2^k^m  (k_1 > k_2 > ... k_m) // // where k_i corresponds to the position of i-th non-zero bit of N, // then the tree has a shape of _m_ full binary trees (FBTs), where // j-th tree has k_j leaf nodes, grouped from right to left: // //    T = FBT(k_1) ^ (FBT(k_2) ^ ( ... ^ FBT(k_m))) // // Example: if N = 7 = 0b111, we have 3 FBTs with 4, 2 and 1 leaves: //        ^ //    ^      ^ //  ^   ^   ^ ` // 0 1 2 3 4 5 6 // // So if we need to locate i-th leaf node out of N in T, we can // follow the following procedure locate(T, i, N): // //   locate(T, 0, 1) = T //   locate(T, i, N = 2^k) = if i < N/2 //                           then locate(left(T),  i,     N/2) //                           else locate(right(T), i-N/2, N/2) //   locate(T, i, N = 2^k + M) = if i < 2^k //                               then locate(left(T),  i,     2^k) //                               else locate(right(T), i-2^k, M) match ht . view ( pos ) { HashTreeView :: Fork ( _ , l , r ) => { if size . is_power_of_two ( ) { let h = size / 2 ; if offset < h { B :: make_fork ( add_forks :: < B > ( ht , l , offset , h , subwitness ) , B :: make_pruned ( ht . digest ( r ) . clone ( ) ) , ) } else { B :: make_fork ( B :: make_pruned ( ht . digest ( l ) . clone ( ) ) , add_forks :: < B > ( ht , r , offset - h , h , subwitness ) , ) } } else { let k = 32 - ( size as u32 ) . leading_zeros ( ) ; let mask = 1 << ( k - 1 ) ; if offset < mask { B :: make_fork ( add_forks :: < B > ( ht , l , offset , mask , subwitness ) , B :: make_pruned ( ht . digest ( r ) . clone ( ) ) , ) } else { B :: make_fork ( B :: make_pruned ( ht . digest ( l ) . clone ( ) ) , add_forks :: < B > ( ht , r , offset - mask , size - mask , subwitness ) , ) } } } _ => subwitness , } } fn child_witness < B : WitnessBuilder > ( ht : & HashTree , parent : NodeId , pos : NodeId , l : & Label , subtree : & LabeledTree < Vec < u8 > > , ) -> B :: Tree { let label_range = ht . node_labels_range ( parent ) ; let len = label_range . end - label_range . start ; let labels = & ht . node_labels [ label_range . clone ( ) ] ; match labels . binary_search ( l ) { Ok ( offset ) => { let idx = label_range . start + offset ; let node_id = NodeId :: node ( idx ) ; let subwitness = B :: make_node ( l . clone ( ) , go :: < B > ( ht , node_id , ht . node_children [ idx ] , subtree ) , ) ; if pos . kind ( ) == NodeKind :: Node { subwitness } else { add_forks :: < B > ( ht , pos , offset , len , subwitness ) } } Err ( offset ) => { let pruned_label_at = | o | { add_forks :: < B > ( ht , pos , o , len , B :: make_node ( ht . node_labels [ label_range . start + o ] . clone ( ) , B :: make_pruned ( ht . digest ( ht . node_children [ label_range . start + o ] ) . clone ( ) , ) , ) , ) } ; // Build a proof of absence if offset == 0 { // The missing child is before the first label. pruned_label_at ( offset ) } else if offset == len { // The missing child is after the last label. pruned_label_at ( offset - 1 ) } else { // The missing child is between two present children. B :: merge_trees ( pruned_label_at ( offset - 1 ) , pruned_label_at ( offset ) ) } } } } fn go < B : WitnessBuilder > ( ht : & HashTree , parent : NodeId , pos : NodeId , t : & LabeledTree < Vec < u8 > > , ) -> B :: Tree { match t { LabeledTree :: Leaf ( data ) => { if pos . kind ( ) == NodeKind :: Leaf { B :: make_leaf ( & data [ .. ] ) } else { panic ! ( " \
 " parent pos ht t ) ; } } LabeledTree :: SubTree ( children ) => children . iter ( ) . map ( | ( l , t ) | child_witness :: < B > ( ht , parent , pos , l , t ) ) . fold ( B :: make_pruned ( ht . digest ( pos ) . clone ( ) ) , B :: merge_trees ) , } } go :: < B > ( self , NodeId :: empty ( ) , self . root , partial_tree ) }
Constructs a witness for the specified partial tree.
Constructs a witness for the specified partial tree .
&self
partial_tree
&LabeledTree<Vec<u8>>
panics
Panics if the partial tree a structure that is different from the
labeled tree that was used to construct this hash tree.
Panics if the partial tree a structure that is different from the labeled tree that was used to construct this hash tree .