Penumbra的Jellyfish Merkle树

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

lib.rs:

此模块实现了由存储模块支持的 JellyfishMerkleTree。树本身不持久化任何内容，但实现了R/W逻辑。写路径将以批量的方式生成所有中间结果供存储层提交，读路径将直接返回结果。公共API仅包括 new、put_value_sets、put_value_set 和 get_with_proof。每次基于已知版本的 value_set 进行put操作后，树将返回一个新的根哈希值，以及包含所有新节点和过时节点索引的 TreeUpdateBatch。

Jellyfish Merkle树本身在逻辑上是一个256位的稀疏Merkle树，具有一种优化，即任何包含0个或1个叶子节点的子树将被替换为该叶子节点或具有默认哈希值的占位符节点。通过这种优化，我们可以在树的许多稀疏级别上避免哈希，从而节省CPU资源。在物理上，树的结构与Ethereum修改后的Patricia Merkle树相似，但有一些修改。一个标准的Jellyfish Merkle树将如下所示

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

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

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