github.com/ubanquan/go-merkletree

Go Merkle Tree

High performance Golang Merkle Tree implementation (supports parallelization).

About Merkle Tree

The illustration below is a sample Merkle Tree data structure generated by data block set {A, B, C, D}. Each leaf tree node is the hash of a block in the data block set and each branch node is the hash of the concatenation of its child node hashes (i.e. Hash(hash_a || hash_b), or Hash(hash_a + hash_b)). The structure is very useful for proof of existence/membership. To prove the existence of a data block, say block C, one only needs to have Hash_11, Hash_0, and Top Hash (Merkle Root). He/She can calculate new Hash_10, Hash_1 and Top Hash and check the new Top Hash with the previous one to determine whether the block is contained in the data block set.

Installation

go get -u github.com/txaty/go-merkletree

Configuration

type Config struct {
    // Customizable hash function used for tree generation.
    HashFunc HashFuncType
    // If 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
    // 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
    // If true, generate a dummy node with random hash value.
    // Otherwise, then the odd node situation is handled by duplicating the previous node.
    NoDuplicates bool
    // Mode of the Merkle Tree generation.
    Mode ModeType // ModeProofGen, ModeTreeBuild, and ModeProofGenAndTreeBuild
}

To define a new Hash function:

func NewHashFunc(data []byte) ([]byte, error) {
    sha256Func := sha256.New()
    sha256Func.Write(data)
    return sha256Func.Sum(nil), nil
}

Important Notice: please make sure the hash function used by paralleled algorithms is concurrent-safe.

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

Benchmark with cbergoon/merkletree (in bench branch, bench version: v0.1.9).

We measure two procedures: proof generation, and verification, both for all the data blocks. In my implementation, proof generation is done by calling New() with ModeProofGen configuration. In cebergoon/merkletree, proof generation is done by calling NewTree() and then calling GetMerklePath() for all the data blocks.

1,000 blocks:

Linux (i7-9750H)

M1 Macbook Air

goos: linux goarch: amd64 pkg: github.com/txaty/go-merkletree cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz BenchmarkMerkleTreeProofGen BenchmarkMerkleTreeProofGen-12 1201 930686 ns/op BenchmarkMerkleTreeProofGenParallel BenchmarkMerkleTreeProofGenParallel-12 1598 750095 ns/op Benchmark_cbergoonMerkleTreeProofGen Benchmark_cbergoonMerkleTreeProofGen-12 267 4347959 ns/op BenchmarkMerkleTreeVerify BenchmarkMerkleTreeVerify-12 283 4223839 ns/op Benchmark_cbergoonMerkleTreeVerify Benchmark_cbergoonMerkleTreeVerify-12 74 15432114 ns/op PASS

goos: darwin goarch: arm64 pkg: github.com/txaty/go-merkletree BenchmarkMerkleTreeProofGen BenchmarkMerkleTreeProofGen-8 3974 302030 ns/op BenchmarkMerkleTreeProofGenParallel BenchmarkMerkleTreeProofGenParallel-8 3807 311711 ns/op Benchmark_cbergoonMerkleTreeProofGen Benchmark_cbergoonMerkleTreeProofGen-8 421 2816790 ns/op BenchmarkMerkleTreeVerify BenchmarkMerkleTreeVerify-8 1029 1164076 ns/op Benchmark_cbergoonMerkleTreeVerify Benchmark_cbergoonMerkleTreeVerify-8 199 5984566 ns/op PASS

10,000 blocks:

Linux (i7-9750H)

M1 Macbook Air

goos: linux goarch: amd64 pkg: github.com/txaty/go-merkletree cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz BenchmarkMerkleTreeProofGen BenchmarkMerkleTreeProofGen-12 98 10478990 ns/op BenchmarkMerkleTreeProofGenParallel BenchmarkMerkleTreeProofGenParallel-12 223 5276430 ns/op Benchmark_cbergoonMerkleTreeProofGen Benchmark_cbergoonMerkleTreeProofGen-12 4 305694955 ns/op BenchmarkMerkleTreeVerify BenchmarkMerkleTreeVerify-12 20 57615278 ns/op Benchmark_cbergoonMerkleTreeVerify Benchmark_cbergoonMerkleTreeVerify-12 3 498598269 ns/op PASS

goos: darwin goarch: arm64 pkg: github.com/txaty/go-merkletree BenchmarkMerkleTreeProofGen BenchmarkMerkleTreeProofGen-8 326 3597411 ns/op BenchmarkMerkleTreeProofGenParallel BenchmarkMerkleTreeProofGenParallel-8 454 2580843 ns/op Benchmark_cbergoonMerkleTreeProofGen Benchmark_cbergoonMerkleTreeProofGen-8 5 227987708 ns/op BenchmarkMerkleTreeVerify BenchmarkMerkleTreeVerify-8 69 15942445 ns/op Benchmark_cbergoonMerkleTreeVerify Benchmark_cbergoonMerkleTreeVerify-8 4 277399750 ns/op PASS

100,000 blocks

Linux (i7-9750H)

M1 Macbook Air

goos: linux goarch: amd64 pkg: github.com/txaty/go-merkletree cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz BenchmarkMerkleTreeProofGen BenchmarkMerkleTreeProofGen-12 9 114271725 ns/op BenchmarkMerkleTreeProofGenParallel BenchmarkMerkleTreeProofGenParallel-12 22 51706887 ns/op Benchmark_cbergoonMerkleTreeProofGen Benchmark_cbergoonMerkleTreeProofGen-12 1 41303579165 ns/op BenchmarkMerkleTreeVerify BenchmarkMerkleTreeVerify-12 2 698644638 ns/op Benchmark_cbergoonMerkleTreeVerify Benchmark_cbergoonMerkleTreeVerify-12 1 43491258069 ns/op PASS

goos: darwin goarch: arm64 pkg: github.com/txaty/go-merkletree BenchmarkMerkleTreeProofGen BenchmarkMerkleTreeProofGen-8 21 53489736 ns/op BenchmarkMerkleTreeProofGenParallel BenchmarkMerkleTreeProofGenParallel-8 33 32653731 ns/op Benchmark_cbergoonMerkleTreeProofGen Benchmark_cbergoonMerkleTreeProofGen-8 1 28479999166 ns/op BenchmarkMerkleTreeVerify BenchmarkMerkleTreeVerify-8 6 194502812 ns/op Benchmark_cbergoonMerkleTreeVerify Benchmark_cbergoonMerkleTreeVerify-8 1 29557938250 ns/op PASS

(100 ns/op means each function execution takes 100 nanoseconds (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.