mtree

mtree

Merkle Tree implementation in golang

A hash tree or Merkle tree is a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash in the labels of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures. Hash trees are a generalization of hash lists and hash chains. More details

An example of a binary hash tree. By Azaghal - Own work, CC0, Link

Project Status

• Variable branching factor
• Binary Serialization
• Update leaf-nodes partially
• Append leaf-nodes
• Support custom store (you can provide your own store either on-memory or persistent)
• Find different leaf-nodes between two trees (useful for data synchronization)

Documentation

See the docs here.

Install

go get github.com/aungmawjj/mtree

Example Usage

package main

import (
	"crypto"
	"fmt"

	_ "crypto/sha256"

	"github.com/aungmawjj/mtree"
)

func main() {

	nbranch := 2 // branching factor of merkle tree

	hashFunc := crypto.SHA256
	hasher := hashFunc.New()

	data := []string{"Foo", "Bar", "Apple", "Orange", "Tree", "Box", "Big", "Cow"}

	// compute leaf-nodes for the merkle tree
	lnodes := make([][]byte, len(data))
	for i, d := range data {
		hasher.Write([]byte(d))
		lnodes[i] = hasher.Sum(nil)
		hasher.Reset()
	}

	m, _ := mtree.New(hashFunc, nbranch)
	m.Compute(lnodes)

	height, _ := m.Height()
	fmt.Println("Tree Height:", height)
	// Tree Height 4

	hasher.Reset()
	hasher.Write([]byte(data[1]))
	res, _ := m.Verify(1, hasher.Sum(nil))

	fmt.Println("Data block at index 1 verify result:", res)
	// Data block at index 1 verify result: true
	hasher.Reset()

	data[1] = "MODIFIED"

	hasher.Reset()
	hasher.Write([]byte(data[1]))
	res, _ = m.Verify(1, hasher.Sum(nil))

	fmt.Println("Data block at index 1 verify result:", res)
	// Data block at index 1 verify result: false
	hasher.Reset()
}

License

This project is licensed under the MIT License.