Merkle 树

基于在 Jellyfish Merkle 树 白皮书中描述的摊销基数-16 Merkle 树 (AR16MT) 的二叉 Merkle 树实现。与 Jellyfish Merkle 树不同，我们的构建使用普通的二叉树哈希算法，使其更容易创建电路。树的深度为 256，使用 Blake2 作为哈希函数。

快照测试

为了检查树实现的向后兼容性，使用 insta 道具进行快照测试。如果任何快照测试失败，请务必修复您的代码或更新快照，同时意识到所做的更改可能不是向后兼容的。

基准测试

loadtest 示例是一个 CLI 应用程序，允许测量树性能。它允许使用内存或 RocksDB 存储后端，以及 Blake2 或 no-op 哈希函数。例如，以下命令启动一个基准测试，包含 75 个区块，每个区块包含 150,000 个插入操作。

cargo run --release -p zksync_merkle_tree --example loadtest -- \
  --chunk-size=500 75 150000

时间测量的顺序应如下（在 MacBook Pro 上使用 12 核 Apple M2 Max CPU 和 32 GB DDR5 RAM 使用上述命令进行测量）

Processing block #74
[metric] merkle_tree.load_nodes = 0.400870959 seconds
[metric] merkle_tree.extend_patch = 0.119743375 seconds
[metric] merkle_tree.extend_patch.new_leaves = 150000
[metric] merkle_tree.extend_patch.new_internal_nodes = 57588
[metric] merkle_tree.extend_patch.moved_leaves = 53976
[metric] merkle_tree.extend_patch.updated_leaves = 0
[metric] merkle_tree.extend_patch.avg_leaf_level = 26.74396987880927
[metric] merkle_tree.extend_patch.max_leaf_level = 44
[metric] merkle_tree.extend_patch.db_reads = 278133
[metric] merkle_tree.extend_patch.patch_reads = 96024
[metric] merkle_tree.finalize_patch = 0.707021 seconds
[metric] merkle_tree.leaf_count = 11250000
[metric] merkle_tree.finalize_patch.hashed_bytes = 3205548448 bytes
Processed block #74 in 1.228553208s, root hash = 0x1ddec3794d0a1c5b44c2d9c7aa985cc61c70e988da2e6f2a810e0eb37f4322c0
Committed block #74 in 571.588041ms
Verifying tree consistency...
Verified tree consistency in 37.478218666s

使用以下命令启动包含证明的全树模式

cargo run --release -p zksync_merkle_tree --example loadtest -- \
  --chunk-size=500 --proofs --reads=50000 75 150000

...具有以下时间顺序

Processing block #74
[metric] merkle_tree.load_nodes = 0.5310345 seconds
[metric] merkle_tree.extend_patch = 0.905285834 seconds
[metric] merkle_tree.extend_patch.new_leaves = 150000
[metric] merkle_tree.extend_patch.new_internal_nodes = 57588
[metric] merkle_tree.extend_patch.moved_leaves = 53976
[metric] merkle_tree.extend_patch.updated_leaves = 0
[metric] merkle_tree.extend_patch.avg_leaf_level = 26.74396987880927
[metric] merkle_tree.extend_patch.max_leaf_level = 44
[metric] merkle_tree.extend_patch.key_reads = 50000
[metric] merkle_tree.extend_patch.db_reads = 400271
[metric] merkle_tree.extend_patch.patch_reads = 96024
[metric] merkle_tree.leaf_count = 11250000
[metric] merkle_tree.finalize_patch = 0.302226041 seconds
[metric] merkle_tree.finalize_patch.hashed_bytes = 3439057088 bytes
Processed block #74 in 1.814916125s, root hash = 0x1ddec3794d0a1c5b44c2d9c7aa985cc61c70e988da2e6f2a810e0eb37f4322c0
Committed block #74 in 904.560667ms
Verifying tree consistency...
Verified tree consistency in 37.935639292s

使用 --help 标志启动示例以获取更多详细信息。

基准测试修剪

--prune 选项启用具有一些合理参数的树修剪，并仅保留最新的树版本。修剪器应输出类似于 merkle_tree.pruning.* 的指标

[histogram] merkle_tree.pruning.load_stale_keys = 0.009145916 seconds
[histogram] rocksdb.write.batch_size{db=merkle_tree} = 649934 bytes
[gauge] rocksdb.live_data_size{db=merkle_tree, cf=default} = 1802196863 bytes
[gauge] rocksdb.total_sst_size{db=merkle_tree, cf=default} = 2057174959 bytes
[gauge] rocksdb.total_mem_table_size{db=merkle_tree, cf=default} = 67110912 bytes
[gauge] rocksdb.live_data_size{db=merkle_tree, cf=stale_keys} = 3275975 bytes
[gauge] rocksdb.total_sst_size{db=merkle_tree, cf=stale_keys} = 5141413 bytes
[gauge] rocksdb.total_mem_table_size{db=merkle_tree, cf=stale_keys} = 19924992 bytes
[histogram] merkle_tree.pruning.apply_patch = 0.031769875 seconds
[gauge] merkle_tree.pruning.target_retained_version = 2999
[histogram] merkle_tree.pruning.key_count = 48154
[gauge] merkle_tree.pruning.deleted_stale_key_versions{bound=start} = 2997
[gauge] merkle_tree.pruning.deleted_stale_key_versions{bound=end} = 3000

（在测试结束时设置 3,000 个区块 x 5,000 写操作/区块）。在测试结束时，不进行修剪的相同设置具有以下顺序的 RocksDB 存储消耗

[gauge] rocksdb.live_data_size{db=merkle_tree, cf=default} = 17723205116 bytes
[gauge] rocksdb.total_sst_size{db=merkle_tree, cf=default} = 17981011113 bytes
[gauge] rocksdb.total_mem_table_size{db=merkle_tree, cf=default} = 46139392 bytes
[gauge] rocksdb.live_data_size{db=merkle_tree, cf=stale_keys} = 441477770 bytes
[gauge] rocksdb.total_sst_size{db=merkle_tree, cf=stale_keys} = 441477770 bytes
[gauge] rocksdb.total_mem_table_size{db=merkle_tree, cf=stale_keys} = 19924992 bytes

即，在此情况下，修剪将 RocksDB 大小减少了大约 8.7 倍。