While implementing SnapSync(#19) , I needed a data structure where the left and right nodes of the tree were tree node pointers rather than hashes, so I started implementing a new tree.
We measured its performance and it was better than the existing zktrie, so we implemented generalizations and additional interfaces with the possibility of using it commonly in GETH in the future.
Implementation
Compared to traditional zktrie, it has the following differences
The left and right nodes of the parent node are not Hash: In zktrie, the children are always hash nodes, which means you always have to read and decode the blob with a hash every time you visit a node.
The tree hash is not always calculated: In zktrie, the hash of every node in the visited path is recalculated every time the tree is modified. This causes a significant performance impact. The newly implemented tree performs well because it does not compute hashes during tree modification, but it does not retain the hashes of nodes abandoned along the way.
Create separate node structures for each type and introduce the TreeNode interface
Added HashNode type: If you implement a new tree with only EmptyNode, ParentNode, and LeafNode, you need to read all tree nodes on tree load because of the change history mentioned in 1. To prevent this, we added the HashNode.
Benchmark test results (input count : 100)
zk merkle tree (zktrie compatibility mode) : Due to change 2, the newly implemented tree will not be able to provide data if intermediate states of the tree are required. Compatibility mode will match the behavior of the existing zktrie.
Rationale
While implementing SnapSync(#19) , I needed a data structure where the left and right nodes of the tree were tree node pointers rather than hashes, so I started implementing a new tree. We measured its performance and it was better than the existing
zktrie, so we implemented generalizations and additional interfaces with the possibility of using it commonly in GETH in the future.Implementation
Compared to traditional zktrie, it has the following differences
Hash: Inzktrie, the children are always hash nodes, which means you always have to read and decode the blob with a hash every time you visit a node.zktrie, the hash of every node in the visited path is recalculated every time the tree is modified. This causes a significant performance impact. The newly implemented tree performs well because it does not compute hashes during tree modification, but it does not retain the hashes of nodes abandoned along the way.TreeNodeinterfaceHashNodetype: If you implement a new tree with onlyEmptyNode,ParentNode, andLeafNode, you need to read all tree nodes on tree load because of the change history mentioned in 1. To prevent this, we added theHashNode.Benchmark test results (input count : 100) zk merkle tree (zktrie compatibility mode) : Due to change 2, the newly implemented tree will not be able to provide data if intermediate states of the tree are required. Compatibility mode will match the behavior of the existing
zktrie.