Penumbra 的水母 Merkle 树

此存储库是 Diem 水母 Merkle 树 crate 的分支，经过修改以内联依赖项并删除 Penumbra 使用中不需要的部分。

lib.rs:

此模块实现了由存储模块支持的 JellyfishMerkleTree。树本身不持久化任何内容，但实现了 R/W 逻辑。写入路径将批量生成所有中间结果，以供存储层提交；读取路径将直接返回结果。公开的 API 只有 new、put_value_sets、put_value_set 和 get_with_proof。每次根据已知版本使用 value_set 进行 put 之后，树将返回一个包含所有新节点和陈旧节点索引的新根哈希值和一个 TreeUpdateBatch。

水母 Merkle 树本身逻辑上是一个 256 位稀疏 Merkle 树，具有优化，即任何包含 0 个或 1 个叶子的子树将替换为该叶节点或具有默认哈希值占位符节点。通过此优化，我们可以通过避免在树的许多稀疏级别上进行哈希运算来节省 CPU。物理上，树的结构与修改后的以太坊 Patricia Merkle 树类似，但有一些修改。标准水母 Merkle 树将类似于以下图示

                                    .──────────────────────.
                            _.─────'                        `──────.
                       _.──'                                        `───.
                   _.─'                                                  `──.
               _.─'                                                          `──.
             ,'                                                                  `.
          ,─'                                                                      '─.
        ,'                                                                            `.
      ,'                                                                                `.
     ╱                                                                                    ╲
    ╱                                                                                      ╲
   ╱                                                                                        ╲
  ╱                                                                                          ╲
 ;                                                                                            :
 ;                                                                                            :
;                                                                                              :
│                                                                                              │
+──────────────────────────────────────────────────────────────────────────────────────────────+
 .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.
/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \
+----++----++----++----++----++----++----++----++----++----++----++----++----++----++----++----+
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
 ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■

 ■: the [`Value`] type this tree stores.

水母默克尔树由InternalNode和LeafNode组成。InternalNode类似于以太坊Patricia Merkle中的分支节点，有16个子节点表示4级二叉树，而LeafNode在Patricia Merkle中也有类似结构。在上图中，水母中的每个bell是一个InternalNode，而每个触须是一个LeafNode。需要注意的是，水母默克尔没有以太坊Patricia Merkle中extension节点的对应物。