本模块提供访问和更新持久化在键值存储中的Merkle累加器结构的算法。请注意，这不会直接写入存储，而是通过 HashReader 特性和通过内存中的 HashMap 产生写入。

Merkle累加器

给定一个不断增长的（仅追加）"叶"哈希系列，我们构建一个不断演变的Merkle树，对于树快照（由根哈希表示）中叶索引处的叶哈希的包含/排除证明可以提供。

叶节点

叶节点携带要存储和证明的哈希值。它们只添加到树中，但永远不会被删除或更新。

内部节点

非叶节点携带从其左右子节点推导出的哈希值。

占位符节点

为了确保每个叶节点都有一个指向根的Merkle证明，添加了占位符节点，使得从叶到根的路径上每个节点都有一个兄弟节点。占位符节点的哈希值为 ACCUMULATOR_PLACEHOLDER_HASH

占位符节点可以以叶子节点或非叶子节点的形式出现，但任何时刻最多只有一个占位符叶子节点。

冻结节点与非冻结节点

随着树中叶子节点的增加，占位符节点将被非占位符节点替换，当一个节点所有后代都是非占位符节点时，它变为“冻结”状态——即使添加新的叶子节点，其哈希值也不会再改变。所有附加的叶子节点（不包括一个可能的占位符叶子节点）按定义都是冻结的。

其他节点，如果有至少一个占位符后代，则是非冻结的。随着新元素附加到累加器上，这些节点的哈希值将发生变化。

叶子节点计数

给定Merkle累加器中叶子节点的数量，可以确定累加器的形状——哪些节点被填充，哪些节点是占位符节点。

示例：具有5个叶子节点的Merkle累加器的逻辑视图

           Non-fzn
          /       \
         /         \
        /           \
      Fzn2         Non-fzn
     /   \           /   \
    /     \         /     \
   Fzn1    Fzn3  Non-fzn  [Placeholder]
  /  \    /  \    /    \
 L0  L1  L2  L3 L4   [Placeholder]

位置和物理表示

随着Merkle累加器树向右和向上扩展，我们单调地编号新冻结的节点。一种方法是简单地使用节点的顺序索引，这就是我们在内存表示中做的方法。我们称这些识别节点下方的数字为“位置”，除非另有说明，这是顺序位置。

但是，对于写入磁盘，我们先将一个节点的所有子节点写入，然后再写入父节点。因此，对于磁盘写入顺序，使用后序位置作为索引更方便。有了这个，我们可以将Merkle累加器映射到一个键值存储：键是节点的后序位置，值是它携带的哈希值。

我们只存储冻结节点，在访问树时动态生成非冻结节点。这样，树的物理表示是只追加的，即一旦写入物理存储，节点就不会被修改或删除。

以下是我们在上面的示例中持久化的逻辑树

         Fzn2(6)
        /      \
       /        \
   Fzn1(2)       Fzn3(5)
  /     \       /     \
 L0(0)  L1(1)  L2(3)  L3(4)  L4(7)

当下一个叶子节点持久化时，物理表示将是

         Fzn2(6)
        /      \
       /        \
   Fzn1(2)       Fzn3(5)       Fzn4(9)
  /     \       /     \       /      \
 L0(0)  L1(1)  L2(3)  L3(4)  L4(7)   L5(8)

编号对应于树的后序遍历。

以键值对的形式思考

|<-key->|<--value-->|
|   0   | hash_L0   |
|   1   | hash_L1   |
|   2   | hash_Fzn1 |
|  ...  |   ...     |