zksync 存储：sparse-merkle-tree 存储

zkp

Modified: 2022-07-02

简介

本文先介绍了 sparse merkle tree，接下来介绍 zksync 中数据持久化。

merkle tree 常用于区块链存储数据和快速校验数据。其构造特点是叶节点使用数据的 hash 进行标记，中间节点使用所有子节点的 hash进行标记。

对于 merke tree 的操作，包含：插入节点、获取树根、计算 merkle 证明、检验 merkle 证明。

计算 merkle 证明包含：

1）计算存在证明

2）计算不存在证明

在原始的 merkle tree 上，很容易生成存在性证明，但是难以生成不存在证明。

为了解决这个问题，同时零知识证明也要求账号在树上的位置具有确定性，因此引入 sparse merkle tree，有如下特点：

一棵满二叉树
数据是索引的，每个数据会放到对应的索引的叶子上
存在性证明，merkle path
不存在性证明，需要证明是 null

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)) 这类操作要求快速计算左右子树的哈希值，并行计算可以计算。