README
¶
Go Merkle Tree
High performance Golang Merkle Tree, supporting parallelization and OpenZeppelin sibling-sorting.
Merkle Tree
Below is a Merkle Tree data structure sample illustration generated by the set of data blocks {A, B, C, D}. Each leaf node of the tree corresponds to the hash value of a block in the data block set, whereas each branch node corresponds to the hash value of the concatenation of the child node hashes (i.e. Hash( hash_a || hash_b), or Hash(hash_a + hash_b)).This structure is particularly beneficial for proof of membership/existence. In order to demonstrate the presence of a data block, such as block C, one merely requires Hash_11, Hash_0, and the Top Hash (i.e., Merkle Root). The individual can subsequently calculate new Hash_10, Hash_1, and Top Hash, and compare the new Top Hash with the previous one to verify whether the block exists in the data block set.
Installation
go get -u github.com/txaty/go-merkletree
Configuration
// Customizable hash function used for tree generation.
HashFunc TypeHashFunc
// Number of goroutines run in parallel.
// If RunInParallel is true and NumRoutine is set to 0, use number of CPU as the number of goroutines.
NumRoutines int
// Mode of the Merkle Tree generation.
Mode TypeConfigMode
// If RunInParallel is true, the generation runs in parallel, otherwise runs without parallelization.
// This increase the performance for the calculation of large number of data blocks, e.g. over 10,000 blocks.
RunInParallel bool
// SortSiblingPairs is the parameter for OpenZeppelin compatibility.
// If set to `true`, the hashing sibling pairs are sorted.
SortSiblingPairs bool
// If true, the leaf nodes are NOT hashed before being added to the Merkle Tree.
DisableLeafHashing bool
To define a new Hash function:
func myHashFunc(data []byte) ([]byte, error) {
sha256Func := sha256.New()
sha256Func.Write(data)
return sha256Func.Sum(nil), nil
}
Critical Advisory: It's essential to ensure that the hash functions employed by parallel algorithms are concurrent-safe.
DefaultHashFunc, which is the default hash function used for tasks executed sequentially in this library, does NOT offer concurrent-safety, given its re-utilization of the same SHA256 digest.
Example
Proof generation and verification of all blocks
package main
import (
"crypto/rand"
"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
}
// generate dummy data blocks
func generateRandBlocks(size int) (blocks []mt.DataBlock) {
for i := 0; i < size; i++ {
block := &testData{
data: make([]byte, 100),
}
_, err := rand.Read(block.data)
handleError(err)
blocks = append(blocks, block)
}
return
}
func main() {
blocks := generateRandBlocks(10)
// the first argument is config, if it is nil, then default config is adopted
tree, err := mt.New(nil, blocks)
handleError(err)
// get proofs
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 verify the proofs without the tree but with Merkle root
// obtain the Merkle root
rootHash := tree.Root
for i := 0; i < len(blocks); i++ {
// if hashFunc is nil, use SHA256 by default
ok, err := mt.Verify(blocks[i], proofs[i], rootHash, nil)
handleError(err)
fmt.Println(ok)
}
}
func handleError(err error) {
if err != nil {
panic(err)
}
}
Build tree and generate proofs for a few blocks
blocks := generateRandBlocks(10)
// create a Merkle Tree config and set mode to tree building
config := &mt.Config{
Mode: ModeTreeBuild,
}
tree, err := mt.New(config, blocks)
handleError(err)
// get the proof for a specific data block
// method GenerateProof is only available when ModeTreeBuild or ModeProofGenAndTreeBuild
proof0, err := tree.GenerateProof(blocks[0])
handleError(err)
proof3, err := tree.GenerateProof(blocks[3])
handleError(err)
Parallel run
blocks := generateRandBlocks(10)
// create a Merkle Tree config and set parallel run parameters
config := &mt.Config{
RunInParallel: true,
NumRoutines: 4,
}
tree, err := mt.New(config, blocks)
handleError(err)
Benchmark
Setup:
| AWS EC2 | CPU | Memory | OS | Hash Function | Go Version |
|---|---|---|---|---|---|
| c5.4xlarge | 16 Core | 32GB | Ubuntu 22.04 LTS | SHA256 | 1.21.4 |
Benchmark tasks:
- Proof generation for all the blocks: at the end we can obtain the Merkle Root and the proofs of all the data blocks.
- Proof verification: verify a single proof.
|
|
|
Note: Please note that the size of each data block is determined by the tree depth, which is represented on the x-axis of the figures. In order to better visualize the full range of values, the y-axis is shown using a logarithmic scale. However, it's important to keep in mind that the real time difference between data points will be larger than what is depicted on the figure due to the logarithmic scale.
Benchmark implementation can be found in txaty/merkle-tree-bench.
Dependencies
This project requires the following dependencies:
- golang.org/x/sync: This package provides
errgroupwhich is utilized to manage errors stemming from goroutines. - gomonkey: This is a versatile Go library designed to facilitate monkey patching during unit testing. Please be aware that users operating on Apple Silicon MacBooks may encounter 'permission denied' issues. Nevertheless, these potential issues do not impact the functionality or use of the Merkle Tree library.
License
Released under the MIT License.
Documentation
¶
Overview ¶
Package merkletree implements a high-performance Merkle Tree in Go. It supports parallel execution for enhanced performance and offers compatibility with OpenZeppelin through sorted sibling pairs.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrInvalidNumOfDataBlocks is the error for an invalid number of data blocks. ErrInvalidNumOfDataBlocks = errors.New("the number of data blocks must be greater than 1") // ErrInvalidConfigMode is the error for an invalid configuration mode. ErrInvalidConfigMode = errors.New("invalid configuration mode") // ErrProofIsNil is the error for a nil proof. ErrProofIsNil = errors.New("proof is nil") // ErrDataBlockIsNil is the error for a nil data block. ErrDataBlockIsNil = errors.New("data block is nil") // ErrProofInvalidModeTreeNotBuilt is the error for an invalid mode in Proof() function. // Proof() function requires a built tree to generate the proof. ErrProofInvalidModeTreeNotBuilt = errors.New("merkle tree is not in built, could not generate proof by this method") // ErrProofInvalidDataBlock is the error for an invalid data block in Proof() function. ErrProofInvalidDataBlock = errors.New("data block is not a member of the merkle tree") )
var FLAG bool
Functions ¶
func DefaultHashFunc ¶
DefaultHashFunc is the default hash function used when no user-specified hash function is provided. It implements the SHA256 hash function and reuses sha256Digest to reduce memory allocations.
func DefaultHashFuncParallel ¶
DefaultHashFuncParallel is the default hash function used by parallel algorithms when no user-specified hash function is provided. It implements the SHA256 hash function and creates a new hash digest for each call, ensuring that it is safe for concurrent use.
Types ¶
type Config ¶
type Config struct {
// Customizable hash function used for tree generation.
HashFunc TypeHashFunc
// Number of goroutines run in parallel.
// If RunInParallel is true and NumRoutine is set to 0, use number of CPU as the number of goroutines.
NumRoutines int
// Mode of the Merkle Tree generation.
Mode TypeConfigMode
// If RunInParallel is true, the generation runs in parallel, otherwise runs without parallelization.
// This increase the performance for the calculation of large number of data blocks, e.g. over 10,000 blocks.
RunInParallel bool
// SortSiblingPairs is the parameter for OpenZeppelin compatibility.
// If set to `true`, the hashing sibling pairs are sorted.
SortSiblingPairs bool
// If true, the leaf nodes are NOT hashed before being added to the Merkle Tree.
DisableLeafHashing bool
}
Config is the configuration of Merkle Tree.
type DataBlock ¶
type DataBlock interface {
// Serialize converts the data block into a byte slice.
// It returns the serialized byte slice and an error, if any occurs during the serialization process.
Serialize() ([]byte, error)
}
DataBlock is the interface for input data blocks used to generate the Merkle Tree. Implementations of DataBlock should provide a serialization method that converts the data block into a byte slice for hashing purposes.
type MerkleTree ¶
type MerkleTree struct {
*Config
// Root is the hash of the Merkle root node.
Root []byte
// Leaves are the hashes of the data blocks that form the Merkle Tree's leaves.
// These hashes are used to generate the tree structure.
// If the DisableLeafHashing configuration is set to true, the original data blocks are used as the leaves.
Leaves [][]byte
// Proofs are the proofs to the data blocks generated during the tree building process.
Proofs []*Proof
// Depth is the depth of the Merkle Tree.
Depth int
// NumLeaves is the number of leaves in the Merkle Tree.
// This value is fixed once the tree is built.
NumLeaves int
// contains filtered or unexported fields
}
MerkleTree implements the Merkle Tree data structure.
func New ¶
func New(config *Config, blocks []DataBlock) (m *MerkleTree, err error)
New generates a new Merkle Tree with the specified configuration and data blocks.
func (*MerkleTree) Proof ¶
func (m *MerkleTree) Proof(dataBlock DataBlock) (*Proof, error)
Proof generates the Merkle proof for a data block using the previously generated Merkle Tree structure. This method is only available when the configuration mode is ModeTreeBuild or ModeProofGenAndTreeBuild. In ModeProofGen, proofs for all the data blocks are already generated, and the Merkle Tree structure is not cached.
func (*MerkleTree) String ¶
func (m *MerkleTree) String()
type Proof ¶
type Proof struct {
Siblings [][]byte // Sibling nodes to the Merkle Tree path of the data block.
Path uint32 // Path variable indicating whether the neighbor is on the left or right.
}
Proof represents a Merkle Tree proof.
type TypeConfigMode ¶
type TypeConfigMode int
TypeConfigMode is the type in the Merkle Tree configuration indicating what operations are performed.
const ( // ModeProofGen is the proof generation configuration mode. ModeProofGen TypeConfigMode = iota // ModeTreeBuild is the tree building configuration mode. ModeTreeBuild // ModeProofGenAndTreeBuild is the proof generation and tree building configuration mode. ModeProofGenAndTreeBuild )
type TypeHashFunc ¶
TypeHashFunc is the signature of the hash functions used for Merkle Tree generation.
Source Files
Directories