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

很高兴和大家分享我最近开源的 Golang 默克尔树（Merkle Tree）的轮子，生成proof和验证proof的方法比cbergoon/merkletree要快很多。

GitHub: https://github.com/txaty/go-merkletree

Go Doc: 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倍）：

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倍）:

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倍）:

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在我的电脑上已经无法短时间得到结果了）：

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://zhuanlan.zhihu.com/p/553599674