merkle

Documentation

Overview

Package merkle provides the tools to create a merkle tree and keep track of its historical states.

Index

• Constants
• func BranchRoot(item []byte, index uint32, proof [][]byte, treeHeight uint32) ([]byte, error)
• func VerifyMerkleProof(root, item []byte, index uint32, proof [][]byte, treeHeight uint32) bool
• type HistoricalTree
  • func NewTree(treeHeight uint32) *HistoricalTree
  • func NewTreeFromItems(items [][]byte, treeHeight uint32) *HistoricalTree
  • func (m *HistoricalTree) Insert(item []byte)
  • func (m *HistoricalTree) Item(index uint32) ([]byte, error)
  • func (m *HistoricalTree) Items() [][]byte
  • func (m *HistoricalTree) MerkleProof(index uint32, count uint32) ([][]byte, error)
  • func (m *HistoricalTree) NumOfItems() uint32
  • func (m *HistoricalTree) Root(count uint32) ([]byte, error)
• type StateKey

Constants

const MessageTreeHeight uint32 = 32

MessageTreeHeight is the depth of the merkle tree that is used in the messaging contracts.

const SnapshotTreeHeight uint32 = 6

SnapshotTreeHeight is the depth of the merkle tree that is used in the snapshot contracts.

Functions

func BranchRoot

func BranchRoot(item []byte, index uint32, proof [][]byte, treeHeight uint32) ([]byte, error)

BranchRoot calculates the merkle root given the item and the proof.

func VerifyMerkleProof

func VerifyMerkleProof(root, item []byte, index uint32, proof [][]byte, treeHeight uint32) bool

VerifyMerkleProof verifies a Merkle branch against a root of a tree.

Types

type HistoricalTree

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

HistoricalTree implements a merkle tree with the ability to generate historical state of the tree. This includes historical roots, as well as historical proofs.

func NewTree

func NewTree(treeHeight uint32) *HistoricalTree

NewTree returns an empty Merkle Tree.

func NewTreeFromItems

func NewTreeFromItems(items [][]byte, treeHeight uint32) *HistoricalTree

NewTreeFromItems returns a new Merkle Tree from a slice of byte slices.

func (*HistoricalTree) Insert

func (m *HistoricalTree) Insert(item []byte)

Insert inserts a new leaf into the merkle tree. This is done using O(1) time.

func (*HistoricalTree) Item

func (m *HistoricalTree) Item(index uint32) ([]byte, error)

Item returns the inserted item with the given `index`.

func (*HistoricalTree) Items

func (m *HistoricalTree) Items() [][]byte

Items returns the list of items that were inserted in the Merkle tree.

func (*HistoricalTree) MerkleProof

func (m *HistoricalTree) MerkleProof(index uint32, count uint32) ([][]byte, error)

MerkleProof returns the proof of inclusion:

• For leaf with given `index` MerkleProof
• At the time when `count` leafs have been inserted

This is done using O(1) time.

func (*HistoricalTree) NumOfItems

func (m *HistoricalTree) NumOfItems() uint32

NumOfItems returns the amount of leafs inserted in the merkle tree.

func (*HistoricalTree) Root

func (m *HistoricalTree) Root(count uint32) ([]byte, error)

Root returns the merkle root of the tree after a certain amount of leafs were inserted. This is done using O(1) time.

type StateKey

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

StateKey implements a key for the historical state map.