merkletree

README

go-merkle-tree

A Bitcoin Merkle Tree, implemented in Go

Many people have written many things about Merkle Trees. For a good overview (uses, characteristics, etc.), read Marc Clifton's Understanding Merkle Trees - Why use them, who uses them, and how to use them.

Warning

This is alpha software.

Notes

• this tree duplicates leaf-hashes such that the cardinality of the tree is always a power of 2
• this tree prefixes a byte (0x00 for leaf, 0x01 for branch) to the input to the provided hashing function

Usage

Construction

blocks := [][]byte{
    []byte("alpha"),
    []byte("beta"),
    []byte("kappa"),
}

tree := NewTree(Sha256DoubleHash, blocks)

fmt.Println(tree.ToString(func(bytes []byte) string {
    return hex.EncodeToString(bytes)[0:16]
}, 0))

/*

    output:

    (B root: 3d4bd4dd0a71aeb3
      (B root: 8b3ee349b69b427f
        (L root: c246ba39b1c6c18d)
        (L root: 24960c3aab1f4b41))
      (B root: da2f01ea4b9f38ad
        (L root: 37ce7f776537a298)
        (L root: 37ce7f776537a298)))

 */

Create and Print Audit Proof

blocks := [][]byte{
    []byte("alpha"),
    []byte("beta"),
    []byte("kappa"),
}

tree := NewTree(Sha256DoubleHash, blocks)
checksum := tree.checksumFunc(true, []byte("alpha"))
proof, _ := tree.CreateProof(checksum)

fmt.Println(proof.ToString(func(bytes []byte) string {
    return hex.EncodeToString(bytes)[0:16]
}))

/*

    output:

    route from c246ba39b1c6c18d (leaf) to root:

    c246ba39b1c6c18d + 24960c3aab1f4b41 = 8b3ee349b69b427f
    8b3ee349b69b427f + da2f01ea4b9f38ad = 3d4bd4dd0a71aeb3

*/

Verify Audit Proof

blocks := [][]byte{
    []byte("alpha"),
    []byte("beta"),
    []byte("kappa"),
}

tree := NewTree(Sha256DoubleHash, blocks)

proof, err := tree.CreateProof(tree.rows[0][0].GetChecksum())
if err != nil {
    panic(err)
}

tree.VerifyProof(proof) // true

Acknowledgements

This implementation was inspired by:

• Marc Clifton's Understanding Merkle Trees - Why use them, who uses them, and how to use them
• Miguel Mota's merkle-tree (in particular: proof generation)

Documentation

Index

• Constants
• func IdentityHashForTest(strbytes []byte) []byte
• func Sha256DoubleHash(data []byte) []byte
• func VerifyProof(leafHash []byte, pathToTarget []*ProofPart, target []byte) bool
• func VerifyProofCustomHash(leafHash []byte, pathToTarget []*ProofPart, target []byte, ...) bool
• type Branch
  • func NewBranch(sumFunc func(bool, []byte) []byte, left Node, right Node) *Branch
  • func (b *Branch) GetHash() []byte
  • func (b *Branch) ToString(f HashToStrFunc, n int) string
• type HashToStrFunc
• type Leaf
  • func NewLeaf(sumFunc func(bool, []byte) []byte, block []byte) *Leaf
  • func NewLeafFromHash(hash []byte) *Leaf
  • func (l *Leaf) GetHash() []byte
  • func (l *Leaf) ToString(f HashToStrFunc, n int) string
• type Node
• type Proof
  • func (p *Proof) Equals(o *Proof) bool
  • func (m *Proof) ToString(f HashToStrFunc) string
• type ProofPart
  • func (pf *ProofPart) Deserialize(data []byte) error
  • func (pf *ProofPart) Serialize() ([]byte, error)
• type Tree
  • func NewTree(providedSumFunc func([]byte) []byte, blocks [][]byte) *Tree
  • func NewTreeFromHashes(providedSumFunc func([]byte) []byte, hashes [][]byte) *Tree
  • func (t *Tree) CreateProof(leafChecksum []byte) (*Proof, error)
  • func (t *Tree) ToString(f HashToStrFunc, n int) string

Constants

const (
	ProofPartSerializeSize = 1 + 32
)

Functions

func IdentityHashForTest

func IdentityHashForTest(strbytes []byte) []byte

func Sha256DoubleHash

func Sha256DoubleHash(data []byte) []byte

func VerifyProof

func VerifyProof(leafHash []byte, pathToTarget []*ProofPart, target []byte) bool

func VerifyProofCustomHash

func VerifyProofCustomHash(leafHash []byte, pathToTarget []*ProofPart, target []byte, hashFunc func([]byte) []byte) bool

Types

type Branch

type Branch struct {
	Hash  []byte
	Left  Node
	Right Node
}

func NewBranch

func NewBranch(sumFunc func(bool, []byte) []byte, left Node, right Node) *Branch

func (*Branch) GetHash

func (b *Branch) GetHash() []byte

func (*Branch) ToString

func (b *Branch) ToString(f HashToStrFunc, n int) string

type HashToStrFunc

type HashToStrFunc func([]byte) string

type Leaf

type Leaf struct {
	Hash []byte
	Data []byte
}

func NewLeaf

func NewLeaf(sumFunc func(bool, []byte) []byte, block []byte) *Leaf

func NewLeafFromHash

func NewLeafFromHash(hash []byte) *Leaf

func (*Leaf) GetHash

func (l *Leaf) GetHash() []byte

func (*Leaf) ToString

func (l *Leaf) ToString(f HashToStrFunc, n int) string

type Node

type Node interface {
	GetHash() []byte
	ToString(HashToStrFunc, int) string
}

type Proof

type Proof struct {
	HashFunc func(isLeaf bool, xs []byte) []byte
	// PathToRoot is a path from the LeafHash up to the root of the Merkle
	// tree. Note that the LeafHash and the Root hash are not included in
	// the this list. Rather, the list is everything in between these two
	// items. To put it visually, below is how to think about a Merkle proof
	// as it is described by this library:
	//
	//             RootHash
	//            /        \
	//        ... PathToRoot ...
	//          /            \
	//         ... LeafHash ...
	//
	PathToRoot []*ProofPart
	// LeafHash is the hash of an element at the lowest level of
	// the Merkle tree. It is the hash of the element we want to
	// prove actually exists in the tree.
	LeafHash []byte
}

func (*Proof) Equals

func (p *Proof) Equals(o *Proof) bool

func (*Proof) ToString

func (m *Proof) ToString(f HashToStrFunc) string

type ProofPart

type ProofPart struct {
	IsRight bool
	Hash    []byte
}

func (*ProofPart) Deserialize

func (pf *ProofPart) Deserialize(data []byte) error

func (*ProofPart) Serialize

func (pf *ProofPart) Serialize() ([]byte, error)

type Tree

type Tree struct {
	Root     Node
	Rows     [][]Node
	HashFunc func(isLeaf bool, block []byte) []byte
}

func NewTree

func NewTree(providedSumFunc func([]byte) []byte, blocks [][]byte) *Tree

func NewTreeFromHashes

func NewTreeFromHashes(providedSumFunc func([]byte) []byte, hashes [][]byte) *Tree

func (*Tree) CreateProof

func (t *Tree) CreateProof(leafChecksum []byte) (*Proof, error)

func (*Tree) ToString

func (t *Tree) ToString(f HashToStrFunc, n int) string