高性能默克尔树（Merkle Tree）库: txaty/go-merkletree

很高兴和大家分享我最近开源的 Golang 默克尔树（Merkle Tree）的轮子，生成proof和验证proof的方法比cbergoon/merkletree要快很多。 GitHub: [https://github.com/txaty/go-merkletree](https://github.com/txaty/go-merkletree) Go Doc: [https://pkg.go.dev/github.com/txaty/go-merkletree](https://pkg.go.dev/github.com/txaty/go-merkletree) 我觉得我们用 Merkle Tree 的大部分场景需要的是 Merkle root 和每个叶节点的 proof，这样我们就可以通过 proof 来重新计算 Merkle root，然后比较计算结果和原来的 root 来证明叶节点的 membership 或存在性。 如果计算出的根与原始根相等，则叶节点是存在的。 所以与其他一些实现不同的是，在构建新的 Merkle Tree 时，我写的库只构建叶节点 proof 和 Merkle root，而不用缓存整个树。 通过这种方法进行优化，可以运行得比 GitHub 上类似的star最多的库：cbergoon/merkletree 快几十上百倍。 并且我还写了用 goroutine 并行优化的方法。 下面是和 cbergoon/merkletree 的benchmark。测试了 proof 生成和验证两个方法。因为 cbergoon/merkletree 的 NewTree() 方法只生成树，不生成 proof，GetMerklePath() 才生成一个叶节点的 proof，所以 proof 生成是通过 NewTree() 和对每个叶节点 call 一遍 GetMerklePath() 来测的。下面是 benchmark 结果： 1,000个数据块（证明快4.7倍，验证快3.6倍）： ```bash 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个数据块（证明快24倍，验证快8.2倍）: ```bash 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个数据块（证明快333倍，验证快42倍）: ```bash 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 ``` 1000,000个数据块（cbergoon/merkle在我的电脑上已经无法短时间得到结果了）： ```bash goos: linux goarch: amd64 pkg: github.com/txaty/go-merkletree cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz BenchmarkMerkleTreeProofGen BenchmarkMerkleTreeProofGen-12 1 1558584621 ns/op BenchmarkMerkleTreeProofGenParallel BenchmarkMerkleTreeProofGenParallel-12 2 806060148 ns/op BenchmarkMerkleTreeVerify BenchmarkMerkleTreeVerify-12 1 8041060031 ns/op PASS ``` 然后并行的方法也比原方法在算多数据块的时候会快很多。我感觉现在并行的实现还不够好，所以还会想进一步优化的方法。 希望我的库可以帮到你。同时如果发现问题的话请提 issue，感谢！ Go Forum 链接：[https://forum.golangbridge.org/t/high-performance-go-merkle-tree-implementation/28490](https://forum.golangbridge.org/t/high-performance-go-merkle-tree-implementation/28490) 知乎链接：[https://zhuanlan.zhihu.com/p/553599674](https://zhuanlan.zhihu.com/p/553599674)