gomerkle

README

gomerkle

Golang merkle tree implementation based on RFC-6962 standard.

import "github.com/arturalbov/gomerkle"

Usage

package main

import (
	"crypto/sha256"
	"fmt"
	"github.com/arturalbov/gomerkle/merkle"
)

func main() {
	tree := merkle.NewTree(sha256.New())

	data := [][]byte{
		[]byte("Audrey Garza"),
		[]byte("Jan Neal"),
		[]byte("Kelly Taylor"),
		[]byte("Henrietta Oliver"),
		[]byte("Rebecca Stewart"),
		[]byte("Johnny Ross"),
		[]byte("Mark Reese"),
		[]byte("Holly Robertson"),
		[]byte("Jaime Davidson"),
		[]byte("Leo Montgomery"),
	}

	tree.BuildNewWithData(data)

	tree.Push([]byte("Karen Rice"))
	tree.Push([]byte("Van Briggs"))
	tree.Push([]byte("Eunice Greene"))

	proofs := tree.GetIndexProofs(2)

	fmt.Println(tree.ValidateIndexByProofs(2, data[2], proofs))
}

Issues

If you have any problems with or questions about this package, please contact us through a GitHub issue.

Contributing

You are invited to contribute new features, fixes, or updates, large or small; I am always thrilled to receive pull requests, and do my best to process them as fast as I can.

Documentation

Index

• type Node
  • func (n *Node) GetIndexProofs(i int) []Proof
• type Proof
  • func (p *Proof) SumWith(hashF hash.Hash, hash []byte) []byte
• type Subtree
  • func (t *Subtree) GetRootProofs() []Proof
• type Tree
  • func NewTree(hashF hash.Hash) *Tree
  • func NewTreeSized(hashF hash.Hash, full bool) *Tree
  • func (t *Tree) BuildNewWithData(data [][]byte)
  • func (t *Tree) ExportSubtreesRoots() []byte
  • func (t *Tree) GetIndexProofs(i int) []Proof
  • func (t *Tree) ImportSubtreesRoots(subTreesRoots []byte)
  • func (t *Tree) Push(data []byte)
  • func (t *Tree) Reset()
  • func (t *Tree) RootHash() []byte
  • func (t *Tree) ValidateIndex(i int, data []byte) bool
  • func (t *Tree) ValidateIndexByProofs(i int, data []byte, proofs []Proof) bool

Types

type Node

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

func (*Node) GetIndexProofs

func (n *Node) GetIndexProofs(i int) []Proof

type Proof

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

todo: make proof recursive to not use array of Proof

func (*Proof) SumWith

func (p *Proof) SumWith(hashF hash.Hash, hash []byte) []byte

calculate sum hash

type Subtree

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

subtrees always should have power of 2 number of elements. tree could contain few of subtrees. root hash calculates from right to left by summing subtree roots hashes.

func (*Subtree) GetRootProofs

func (t *Subtree) GetRootProofs() []Proof

get proofs for root of this subtree

type Tree

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

Merkle tree data structure based on RFC-6962 standard (https://tools.ietf.org/html/rfc6962#section-2.1) we separate whole tree to subtrees where nodes count equal power of 2 root hash calculates from right to left by summing subtree roots hashes.

func NewTree

func NewTree(hashF hash.Hash) *Tree

func NewTreeSized

func NewTreeSized(hashF hash.Hash, full bool) *Tree

func (*Tree) BuildNewWithData

func (t *Tree) BuildNewWithData(data [][]byte)

build completely new tree with data works the same (by time) as using Push method one by one

func (*Tree) ExportSubtreesRoots

func (t *Tree) ExportSubtreesRoots() []byte

from right to left we need to export root hash and height of tree from those bytes we could restore it later

func (*Tree) GetIndexProofs

func (t *Tree) GetIndexProofs(i int) []Proof

going from right trees to left

func (*Tree) ImportSubtreesRoots

func (t *Tree) ImportSubtreesRoots(subTreesRoots []byte)

from right to left after import we loosing indices (actually they don't need for pushing)

func (*Tree) Push

func (t *Tree) Push(data []byte)

n*log(n)

func (*Tree) Reset

func (t *Tree) Reset()

func (*Tree) RootHash

func (t *Tree) RootHash() []byte

root hash calculates from right to left by summing subtrees root hashes.

func (*Tree) ValidateIndex

func (t *Tree) ValidateIndex(i int, data []byte) bool

func (*Tree) ValidateIndexByProofs

func (t *Tree) ValidateIndexByProofs(i int, data []byte, proofs []Proof) bool