6
GitHub - txaty/go-merkletree: High performance Golang Merkle Tree implementation...
source link: https://github.com/txaty/go-merkletree
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Go Merkle Tree
High performance Merkle Tree Computation in Go (supports parallelization).
Installation
go get -u github.com/txaty/go-merkletreeExample
package main
import (
"crypto/rand"
"crypto/sha256"
"fmt"
mt "github.com/txaty/go-merkletree"
)
// first define a data structure with Serialize method to be used as data block
type testData struct {
data []byte
}
func (t *testData) Serialize() ([]byte, error) {
return t.data, nil
}
// define a hash function in this format
func hashFunc(data []byte) ([]byte, error) {
sha256Func := sha256.New()
sha256Func.Write(data)
return sha256Func.Sum(nil), nil
}
func main() {
// generate dummy data blocks
var blocks []mt.DataBlock
for i := 0; i < 1000; i++ {
block := &testData{
data: make([]byte, 100),
}
_, err := rand.Read(block.data)
handleError(err)
blocks = append(blocks, block)
}
// create a simple configuration for Merkle Tree generation
config := &mt.Config{
HashFunc: hashFunc, // if nil, use SHA256 by default
// if true, handle odd-number-node situation by duplicating the last node
AllowDuplicates: true,
}
// build a new Merkle Tree
tree, err := mt.New(config, blocks)
handleError(err)
// get the root hash of the Merkle Tree
rootHash := tree.Root
// get proves
proofs := tree.Proofs
// verify the proofs
for i := 0; i < len(proofs); i++ {
ok, err := tree.Verify(blocks[i], proofs[i])
handleError(err)
fmt.Println(ok)
}
// or you can also do this
for i := 0; i < len(blocks); i++ {
// if hashFunc is nil, use SHA256 by default
ok, err := mt.Verify(blocks[i], proofs[i], rootHash, hashFunc)
handleError(err)
fmt.Println(ok)
}
}
func handleError(err error) {
if err != nil {
panic(err)
}
}Benchmark
Benchmark with cbergoon/merkletree (in bench branch).
In our implementation, tree.Build() performs tree generation and the proof generation at the same time (time complexity: O(nlogn)), cbergoon/merkletree's tree.NewTree() only generates the tree. So we benchmark our tree building process with cbergoon/merkletree's tree build + get merkle path tree.GetMerklePath() for each data block as the proof generation test.
1,000 blocks:
| Linux (i7-9750H) | M1 Macbook Air |
|---|---|
|
|
10,000 blocks:
| Linux (i7-9750H) | M1 Macbook Air |
|---|---|
|
|
100,000 blocks
| Linux (i7-9750H) | M1 Macbook Air |
|---|---|
|
|
(63145758422 ns/op means each function execution takes 63145758422 nanoseconds (around 63.15 seconds, 10^9 ns = 1s))
In conclusion, with large sets of data blocks, our implementation is much faster than cbergoon/merkletree at both tree & proof generation and data block verification.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK