静态数据Merkle树

完全二叉Merkle树

完全二叉Merkle树(CBMT)可用于为静态项目列表生成Merkle根和Merkle证明。目前，CBMT用于计算交易根。基本上，CBMT是一个完全二叉树，其中每一层（除最后一层外）都是完全填充的，所有节点都尽可能地靠左。它也是一个满二叉树，其中除了叶子节点外的每个节点都有两个孩子。与其它Merkle树相比，CBMT的哈希计算量最小，证明大小也最小。

节点组织

为了说明，我们从零开始按从上到下和从左到右的顺序排列树节点。在具有n个项目的CBMT中，根是第一个节点，第一个项目的哈希是节点0，第二个是节点n+1，等等。我们选择这种节点组织方式，因为它可以很容易地计算一个项目的节点顺序。

例如，具有6个项目的CBMT（假设哈希值为[T0, T1, T2, T3, T4, T5]）和具有7个项目的CBMT（假设哈希值为[T0, T1, T2, T3, T4, T5, T6]）的示例如下

        with 6 items                       with 7 items

              B0 -- node 0                       B0 -- node 0
             /  \                               /  \
           /      \                           /      \
         /          \                       /          \
       /              \                   /              \
      B1 -- node 1    B2 -- node 2       B1 -- node 1    B2 -- node 2
     /  \            /  \               /  \            /  \
    /    \          /    \             /    \          /    \
   /      \        /      \           /      \        /      \
  B3(3)   B4(4)  TO(5)    T1(6)      B3(3)   B4(4)   B5(5)   T0(6)
 /  \    /  \                       /  \    /  \    /  \
T2  T3  T4  T5                     T1  T2  T3  T4  T5  T6
(7) (8) (9) (10)                   (7) (8) (9)(10)(11) (12)

特别地，包含0个元素的树为空树（0个节点）且其根为 T::default()。

树结构

CBMT可以使用非常节省空间的方式表示，只需要使用一个数组。数组中的节点按照升序排列。

例如，上面的两个树可以表示为

// an array with 11 elements, the first element is node 0(BO), second is node 1, etc.
[B0, B1, B2, B3, B4, T0, T1, T2, T3, T4, T5]

// an array with 13 elements, the first element is node 0(BO), second is node 1, etc.
[B0, B1, B2, B3, B4, B5, T0, T1, T2, T3, T4, T5, T6]

假设有一个包含n个元素的CBMT，数组的长度为2n-1，元素i（从0开始）的索引为i+n-1。对于索引为i的节点，其父节点的索引为(i-1)/2，其兄弟节点的索引为(i+1)^1-1（^是异或运算）且其子节点的索引为[2i+1, 2i+2]。

默克尔证明

默克尔证明可以证明一个或多个元素的存在。应仅包含形成叶子到根路径的节点兄弟节点，不包括已在路径中的节点。我们还指定证明中的节点按降序排列（这样，证明生成和验证的算法可以更加简单）。需要证明的元素索引对于完成根的计算至关重要，因为索引不是元素的内部特征，因此索引也包含在证明中，并且为了获得正确的对应关系，我们指定索引应按对应哈希的升序排列。例如，如果我们想证明[T1, T4]在上面的6个元素列表中，则应仅包含节点[T5, T0, B3]和索引[9, 6]作为证明的一部分。

使用方法

您可以通过提供Merge trait实现来使用任何类型生成默克尔树。例如

use merkle_tree::CBMT;

struct MergeI32 {}

impl Merge for MergeI32 {
    type Item = i32;
    fn merge(left: &Self::Item, right: &Self::Item) -> Self::Item {
        right.wrapping_sub(*left)
    }
}

type CBMTI32 = CBMT<i32, MergeI32>;

let leaves = vec![2i32, 3, 5, 7, 11];
let indices = vec![0, 4];
let proof_leaves = vec![2i32, 11];
let root = CBMTI32::build_merkle_root(&leaves);
let proof = CBMTI32::build_merkle_proof(&leaves, &indices).unwrap();
let tree = CBMTI32::build_merkle_tree(leaves);
proof.verify(&proof_leaves, &root);