简介
本文先介绍了 sparse merkle tree,接下来介绍 zksync 中数据持久化。
merkle tree
merkle tree 常用于区块链存储数据和快速校验数据。其构造特点是叶节点使用数据的 hash 进行标记,中间节点使用所有子节点的 hash进行标记。

对于 merke tree 的操作,包含:插入节点、获取树根、计算 merkle 证明、检验 merkle 证明。
计算 merkle 证明包含:
1)计算存在证明
2)计算不存在证明
在原始的 merkle tree 上,很容易生成存在性证明,但是难以生成不存在证明。
sparse merkle tree
为了解决这个问题,同时零知识证明也要求账号在树上的位置具有确定性,因此引入 sparse merkle tree,有如下特点:
1 | 一棵满二叉树 |
优化
1)预计算空值哈希
由于大部分情况下,树并不会真的满,而是非常的稀疏。可以预计算H(null)、H(H(null)|H(null))、H(H(H(null)|H(null))|H(H(null)|H(null)))等层级上的值,达到加速的效果。
2)并行计算左右子树哈希
H(H(left)|H(right)) 这类操作要求 快速计算左右子树的哈希值,并行计算可以计算。
实现
文献参考
sparse-merkle-trees-visual-introduction
相关文章推荐