Lib.rs

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

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

                                   .──────────────────────.
                           _.─────'                        `──────.
                      _.──'                                        `───.
                  _.─'                                                  `──.
              _.─'                                                          `──.
            ,'                                                                  `.
         ,─'                                                                      '─.
       ,'                                                                            `.
     ,'                                                                                `.
    ╱                                                                                    ╲
   ╱                                                                                      ╲
  ╱                                                                                        ╲
 ╱                                                                                          ╲
;                                                                                            :
;                                                                                            :
;                                                                                              :
│                                                                                              │
+──────────────────────────────────────────────────────────────────────────────────────────────+
.''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.
/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \
+----++----++----++----++----++----++----++----++----++----++----++----++----++----++----++----+
(  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
 )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
(  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
 )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
(  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
 )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
(  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
 )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
(  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■
■: the [`Value`] type this tree stores.

海星默克尔树由InternalNode和LeafNode组成。InternalNode类似于Ethereum Patricia Merkle中的分支节点，有16个子节点来表示4层二叉树，而LeafNode与Patricia Merkle中的类似。在上面的图中，海星中的每个bell都是一个InternalNode，而每个触手都是一个LeafNode。需要注意的是，海星默克尔没有Ethereum Patricia Merkle中extension节点的对应物。