Hello, gophers. Wish you have a good day!
I am glad to share my newly implemented Golang Merkle Tree computation library with good performance.
GitHub Link: https://github.com/txaty/go-merkletree
Go Doc: https://pkg.go.dev/github.com/txaty/go-merkletree
I think what we need for a Merkle Tree most of the time is the Merkle root and the proof of each leaf node so that we can prove the membership/existence of a leaf node by recomputing the root with its proof and then comparing the calculated root with the original root. If the calculated root is equivalent to the original one, then the leaf node’s membership is valid (it exists).
So unlike some other implementations, when building a new Merkle Tree, my program only constructs the leaf node proofs and finally generates the Merkle root rather than caching the tree itself. With this optimization, my program can run much faster than the most started similar library on GitHub: cbergoon/merkletree. I improve the performance better by parallelization with goroutines.
Here is a quick benchmark between my Merkle Tree library with cbergoon/merkletree. I measure the
- time of proof generation - to generate the Merkle root and proofs of all the leaf nodes, and
- time of verification - to verify all the leaf nodes in the tree.
In my library, the tree building and proof generation happen simultaneously. In cbergoon/merkletree, tree building only builds the tree, the proof (Merkle path) is acquired by calling GetMerklePath() function for every leaf node.
1,000 nodes (proof gen 4.7x faster, verification 3.6x faster):
goos: linux
goarch: amd64
pkg: github.com/txaty/go-merkletree
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkMerkleTreeProofGen
BenchmarkMerkleTreeProofGen-12 774 1525119 ns/op
BenchmarkMerkleTreeProofGenParallel
BenchmarkMerkleTreeProofGenParallel-12 866 1402052 ns/op
Benchmark_cbergoonMerkleTreeProofGen
Benchmark_cbergoonMerkleTreeProofGen-12 165 7142707 ns/op
BenchmarkMerkleTreeVerify
BenchmarkMerkleTreeVerify-12 172 6886498 ns/op
Benchmark_cbergoonMerkleTreeVerify
Benchmark_cbergoonMerkleTreeVerify-12 46 24741956 ns/op
PASS
10,000 nodes (proof gen 24x faster, verification 8.2x faster):
goos: linux
goarch: amd64
pkg: github.com/txaty/go-merkletree
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkMerkleTreeProofGen
BenchmarkMerkleTreeProofGen-12 55 20999696 ns/op
BenchmarkMerkleTreeProofGenParallel
BenchmarkMerkleTreeProofGenParallel-12 128 9295963 ns/op
Benchmark_cbergoonMerkleTreeProofGen
Benchmark_cbergoonMerkleTreeProofGen-12 2 504747049 ns/op
BenchmarkMerkleTreeVerify
BenchmarkMerkleTreeVerify-12 12 93694508 ns/op
Benchmark_cbergoonMerkleTreeVerify
Benchmark_cbergoonMerkleTreeVerify-12 2 771403038 ns/op
PASS
100,000 nodes (proof gen 333x faster, verification 42x faster):
goos: linux
goarch: amd64
pkg: github.com/txaty/go-merkletree
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkMerkleTreeProofGen
BenchmarkMerkleTreeProofGen-12 6 181101101 ns/op
BenchmarkMerkleTreeProofGenParallel
BenchmarkMerkleTreeProofGenParallel-12 10 107610935 ns/op
Benchmark_cbergoonMerkleTreeProofGen
Benchmark_cbergoonMerkleTreeProofGen-12 1 60383341291 ns/op
BenchmarkMerkleTreeVerify
BenchmarkMerkleTreeVerify-12 1 1148882340 ns/op
Benchmark_cbergoonMerkleTreeVerify
Benchmark_cbergoonMerkleTreeVerify-12 1 48003616811 ns/op
PASS
Also, the parallelized algorithm runs much faster than the original algorithm in terms of large numbers of blocks. Right now, the parallelization is not perfect enough, and I am still thinking of how to improve it.
Wish my library can help you. If you find any issue in my code, please inform me (e.g., submit an issue). Thanks 