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

txaty · · 1299 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

很高兴和大家分享我最近开源的 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) ![Screenshot 2022-05-15 at 20.22.11.png](https://static.golangjob.cn/220815/101dfca0fa20740c89c37fbecea9c4c9.png)

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1299 次点击  
加入收藏 微博
3 回复  |  直到 2022-08-19 09:54:48
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传