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

• func IdentityHashForTest(strbytes []byte) []byte
• func Sha256DoubleHash(data []byte) []byte
• type Branch
  • func NewBranch(sumFunc func(bool, []byte) []byte, left Node, right Node) *Branch
  • func (b *Branch) GetChecksum() []byte
  • func (b *Branch) ToString(f checksumToStrFunc, n int) string
• type Leaf
  • func NewLeaf(sumFunc func(bool, []byte) []byte, block []byte) *Leaf
  • func (l *Leaf) GetChecksum() []byte
  • func (l *Leaf) ToString(f checksumToStrFunc, n int) string
• type Node
• type Proof
  • func (p *Proof) Equals(o *Proof) bool
  • func (m *Proof) ToString(f checksumToStrFunc) string
• type ProofPart
• type Tree
  • func NewTree(providedSumFunc func([]byte) []byte, blocks [][]byte) *Tree
  • func (t *Tree) CreateProof(leafChecksum []byte) (*Proof, error)
  • func (t *Tree) ToString(f checksumToStrFunc, n int) string
  • func (t *Tree) VerifyProof(p *Proof) bool

Functions

func IdentityHashForTest

func IdentityHashForTest(strbytes []byte) []byte

func Sha256DoubleHash

func Sha256DoubleHash(data []byte) []byte

Types

type Branch

type Branch struct {
	// contains filtered or unexported fields
}

func NewBranch

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

func (*Branch) GetChecksum

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

func (*Branch) ToString

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

type Leaf

type Leaf struct {
	// contains filtered or unexported fields
}

func NewLeaf

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

func (*Leaf) GetChecksum

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

func (*Leaf) ToString

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

type Node

type Node interface {
	GetChecksum() []byte
	ToString(checksumToStrFunc, int) string
}

type Proof

type Proof struct {
	// contains filtered or unexported fields
}

func (*Proof) Equals

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

func (*Proof) ToString

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

type ProofPart

type ProofPart struct {
	// contains filtered or unexported fields
}

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

func NewTree

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

func (*Tree) CreateProof

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

func (*Tree) ToString

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

func (*Tree) VerifyProof

func (t *Tree) VerifyProof(p *Proof) bool