Merkle Tree

Binary Merkle tree implementation based on amortized radix-16 Merkle tree (AR16MT) described in the Jellyfish Merkle tree white paper. Unlike Jellyfish Merkle tree, our construction uses vanilla binary tree hashing algorithm to make it easier for the circuit creation. The depth of the tree is 256, and Blake2 is used as the hashing function.

Snapshot tests

In order to check backward compatibility of the tree implementation, it is snapshot-tested using the insta crate. If any of snapshot tests fail, be sure to either fix your code, or update the snapshots being aware that the made changes are probably not backward-compatible.

Benchmarking

The loadtest example is a CLI app allowing to measure tree performance. It allows using the in-memory or RocksDB storage backend, and Blake2 or no-op hashing functions. For example, the following command launches a benchmark with 75 blocks each containing 150,000 insertion operations.

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

The order of timings should be as follows (measured on MacBook Pro with 12-core Apple M2 Max CPU and 32 GB DDR5 RAM using the command line above):

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

Full tree mode (with proofs) launched with the following command:

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

...has the following order of timings:

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

Launch the example with the --help flag for more details.

Benchmarking pruning

--prune option enables tree pruning with some reasonable parameters and just the latest tree version retained. The pruner should output merkle_tree.pruning.* metrics like this:

[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

(at the end of the test in a setup with 3,000 blocks x 5,000 write ops / block). The same setup without pruning has the following order of RocksDB storage consumption at the end of the test:

[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

I.e., pruning reduces RocksDB size approximately 8.7 times in this case.