mtree

package module
v0.3.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 26, 2020 License: MIT Imports: 6 Imported by: 0

README

mtree

GoDoc Go Report Card

Merkle Tree implementation in golang for large number of leaf-nodes

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 Merkle Tree

Project Status

In this implementation, the leaf-nodes are not the data blocks. Instead, they are the hashes of the corresponding data blocks. The merkle tree does not maintain those data blocks as the leaf-nodes. This is efficient when each data block is coming from a database or directly from the disk.

  • Variable branching factor
  • MarshalBinary and UnmarshalBinary
  • Update leaf-nodes partially
  • Append leaf-nodes
  • 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"}

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

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

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

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

	data[1] = "MODIFIED"

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

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

func check(err error) {
	if err != nil {
		panic(err)
	}
}
Evaluation

Evaluation results on a pc using examples/bench

Branching factor: 16
Leaf-node count: 10,000,000

Compute Merkle tree duration: 1183.887 ms
Block Height: 7
MarshalBinary Size of merkle tree: 341 MB
Clone duration: 173.938 ms

Verify duration: 26 μs

Update node count: 10,000
Update duration: 48.606 ms
Affected node count: 32,606
CommitUpdates duration: 0.959 ms

Append node count: 10,000
Append duration: 4.512 ms
Affected node count: 10,671
CommitUpdates duration: 203.841 ms
License

This project is licensed under the MIT License.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrorInvalidInputLength = errors.New("Invalid input length")

	ErrorInvalidBranchingFactor = errors.New(
		"Branching factor must be at least 2",
	)

	ErrorBranchingFactorNotMatch = errors.New("Branching Factor doesn't match")

	ErrorInvalidHashFunc = errors.New("Invalid hash function")
)

errors

Functions

This section is empty.

Types

type MemoryStore added in v0.3.0 

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

MemoryStore implements Store interface as on-memory store for the tree

func NewMemoryStore added in v0.3.1 

func NewMemoryStore(tp *TreeProps) *MemoryStore

NewMemoryStore create a new MemoryStore instance

func (*MemoryStore) Clone added in v0.3.0 

func (s *MemoryStore) Clone() (Store, error)

Clone the store

func (*MemoryStore) CommitUpdates added in v0.3.1 

func (s *MemoryStore) CommitUpdates(bundle UpdateBundle) error

CommitUpdates commits updated nodes

func (*MemoryStore) GetLeafCount added in v0.3.2 

func (s *MemoryStore) GetLeafCount() (int, error)

GetLeafCount gives the node count of the specified row

func (*MemoryStore) ReadChildBlock added in v0.3.0 

func (s *MemoryStore) ReadChildBlock(p Position) ([]byte, error)

ReadChildBlock gives the child nodes of a node at the specified position as a single byte slice (block)

func (*MemoryStore) ReadNode added in v0.3.0 

func (s *MemoryStore) ReadNode(p Position) ([]byte, error)

ReadNode gives the node at the specified position

func (*MemoryStore) ReadRow added in v0.3.0 

func (s *MemoryStore) ReadRow(rowIdx int) ([]byte, error)

ReadRow gives the nodes at the specified row as a single byte slice

func (*MemoryStore) SetLeafCount added in v0.3.2 

func (s *MemoryStore) SetLeafCount(nleaf int) error

SetLeafCount adapts the tree size if according to nleaf

func (*MemoryStore) SetTreeProps added in v0.3.0 

func (s *MemoryStore) SetTreeProps(tp *TreeProps)

SetTreeProps sets the tree props

func (*MemoryStore) TreeHeight added in v0.3.2 

func (s *MemoryStore) TreeHeight() (int, error)

TreeHeight gives the row count (height) of the tree

func (*MemoryStore) WriteNode added in v0.3.0 

func (s *MemoryStore) WriteNode(p Position, node []byte) error

WriteNode insert the node to the specified position

func (*MemoryStore) WriteRow added in v0.3.0 

func (s *MemoryStore) WriteRow(rowIdx int, nodes []byte) error

WriteRow inserts the nodes to the specified row

type MerkleTree 

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

MerkleTree type

func New 

func New(hashFunc crypto.Hash, nbranch int) (*MerkleTree, error)

New creates a new MerkleTree instance

func NewWithStore added in v0.3.0 

func NewWithStore(
	hashFunc crypto.Hash, nbranch int, store Store,
) (*MerkleTree, error)

NewWithStore creates a new MerkleTree instance with a given store

func (*MerkleTree) Clone 

func (m *MerkleTree) Clone() (*MerkleTree, error)

Clone create a new tree instance from existing one

func (*MerkleTree) Compute 

func (m *MerkleTree) Compute(lnodes []byte) error

Compute builds the merkle tree from given leaf-nodes It commits the results to the store during the process

func (*MerkleTree) GetStore added in v0.3.0 

func (m *MerkleTree) GetStore() Store

GetStore gives current store ref

func (*MerkleTree) Height 

func (m *MerkleTree) Height() (int, error)

Height returns the merkle tree height

func (*MerkleTree) LeafCount added in v0.3.0 

func (m *MerkleTree) LeafCount() (int, error)

LeafCount returns the leaf-nodes count

func (*MerkleTree) MarshalBinary 

func (m *MerkleTree) MarshalBinary() ([]byte, error)

MarshalBinary encodes the merkle tree

func (*MerkleTree) Root 

func (m *MerkleTree) Root() ([]byte, error)

Root returns the merkle root hash

func (*MerkleTree) UnmarshalBinary 

func (m *MerkleTree) UnmarshalBinary(b []byte) error

UnmarshalBinary decoded the merkle tree

func (*MerkleTree) Update 

func (m *MerkleTree) Update(
	lnodes map[int][]byte,
) (UpdateBundle, error)

Update computes new hashes of affected nodes for the modified leaf nodes. It doesn't commit the changes. Instead, it returns those affected nodes. Use CommitUpdates() to commit the changes.

func (*MerkleTree) Verify 

func (m *MerkleTree) Verify(node []byte, p Position) (bool, error)

Verify the integrity of the node at the specified position

func (*MerkleTree) VerifyLeaf added in v0.3.0 

func (m *MerkleTree) VerifyLeaf(lnode []byte, idx int) (bool, error)

VerifyLeaf verifies the integrity of the leaf-node at the specified index

func (*MerkleTree) VerifyTree added in v0.3.1 

func (m *MerkleTree) VerifyTree() (bool, error)

VerifyTree verifies the entire tree

type Node added in v0.3.1 

type Node struct {
	Position Position
	Sum      []byte
}

Node defines a node in the tree

type Position added in v0.3.0 

type Position struct {
	RowIdx  int
	NodeIdx int
}

Position of a node in the tree

type Store added in v0.3.0 

type Store interface {

	// SetTreeProps sets the tree props
	SetTreeProps(tp *TreeProps)

	// SetLeafCount sets the new leaf count
	SetLeafCount(nleaf int) error

	// GetLeafCount gets the current leaf count
	GetLeafCount() (int, error)

	// TreeHeight gives the current tree height
	TreeHeight() (int, error)

	// Clone the store
	Clone() (Store, error)

	// WriteRow inserts the nodes to the specified row
	WriteRow(rowIdx int, nodes []byte) error

	// ReadRow gives the nodes at the specified row as a single byte slice
	ReadRow(rowIdx int) ([]byte, error)

	// CommitUpdates commits updated nodes
	CommitUpdates(bundle UpdateBundle) error

	// WriteNode insert the node to the specified position
	WriteNode(p Position, node []byte) error

	// ReadNode gives the node at the specified position
	ReadNode(p Position) ([]byte, error)

	// ReadChildBlock gives the child nodes of a node at the specified position
	// as a single byte slice (block)
	ReadChildBlock(p Position) ([]byte, error)
}

Store interface for merkle tree

type TreeProps added in v0.3.0 

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

TreeProps contain tree props and related helper methods

func NewTreeProps added in v0.3.0 

func NewTreeProps(nodeSize, blockSize int) (*TreeProps, error)

NewTreeProps create a pointer to a new TreeProps struct

func (*TreeProps) BlockCount added in v0.3.0 

func (t *TreeProps) BlockCount(nodeCount int) int

BlockCount gives how many blocks are required to cover the given node count

func (*TreeProps) BlockIndex added in v0.3.0 

func (t *TreeProps) BlockIndex(nodeIdx int) int

BlockIndex gives the index of the block where the given node exists

func (*TreeProps) BlockSize added in v0.3.0 

func (t *TreeProps) BlockSize() int

BlockSize gives block size

func (*TreeProps) BlockStart added in v0.3.0 

func (t *TreeProps) BlockStart(blockIdx int) int

BlockStart gives the index of first node in the given block index

func (*TreeProps) ByteCount added in v0.3.0 

func (t *TreeProps) ByteCount(nodeCount int) int

ByteCount gives how many bytes are required to cover the given node count

func (*TreeProps) NodeCount added in v0.3.0 

func (t *TreeProps) NodeCount(byteCount int) int

NodeCount gives how many nodes can be put in a given number of bytes

func (*TreeProps) NodeSize added in v0.3.0 

func (t *TreeProps) NodeSize() int

NodeSize gives node size

func (*TreeProps) TreeHeight added in v0.3.0 

func (t *TreeProps) TreeHeight(nleaf int) int

TreeHeight computes height of the tree

func (*TreeProps) TreeSize added in v0.3.0 

func (t *TreeProps) TreeSize(nleaf int) int

TreeSize computes total number of nodes in the tree

type UpdateBundle added in v0.3.2 

type UpdateBundle struct {
	NLeaf int
	Nodes []Node
}

UpdateBundle contains the information to commit updates

Source Files

View all Source files

Directories

Path Synopsis
examples
bench
usage

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.