Documentation ¶
Overview ¶
Package mmr is responsible for calculating the merkle mountain range root, proof and the verification
Index ¶
- Variables
- func GetPeaks(mmrSize uint64) (positions []uint64)
- func LeafIndexToMMRSize(index uint64) uint64
- func LeafIndexToPos(index uint64) uint64
- func PosHeightInTree(pos uint64) uint32
- func UseLogger(l logger)
- type Batch
- type BatchElem
- type Iterator
- type MMR
- type MemStore
- type Proof
- func (m *Proof) CalculateRoot() ([]byte, error)
- func (m *Proof) CalculateRootWithNewLeaf(leaves []types.Leaf, newIndex uint64, newElem []byte, newMMRSize uint64) ([]byte, error)
- func (m *Proof) LeavesToVerify(leaves []types.Leaf)
- func (m *Proof) MMRSize() uint64
- func (m *Proof) ProofItems() [][]byte
- func (m *Proof) Verify(root []byte) bool
- type Store
Constants ¶
This section is empty.
Variables ¶
var ErrCorruptedProof = errors.New("corrupted proof: proof items is not enough to build a tree")
ErrCorruptedProof is of the type error. It is returned when proof is considered corrupt
var ErrGenProofForInvalidLeaves = errors.New("leaves is an empty list, or beyond the mmr range")
ErrGenProofForInvalidLeaves is of the type error. It is returned when the list of leaves is empty or beyond mmr range
var ErrGetRootOnEmpty = errors.New("get root on an empty MMR")
ErrGetRootOnEmpty is of the type error. It is returned when the MMR is empty
var ErrInconsistentStore = errors.New("inconsistent store")
ErrInconsistentStore is of the type error. It is returned when the store is considered inconsistent
Functions ¶
func GetPeaks ¶
GetPeaks returns the positions of the peaks of the MMR using the MMR size.
- It starts by finding the leftmost peak.
- It then finds the next peak (right peak) by moving to the right sibling. If that node isn't in the MMR (which it won't), it take its left child. If that child is not in the MMR either, it keeps taking its left child until it finds a node that exists in the MMR.
- The process is repeated until it is at the last node.
func LeafIndexToMMRSize ¶
LeafIndexToMMRSize returns the mmr size of an mmr tree provided the leaf index passed as an argument is the last leaf in the tree.
func LeafIndexToPos ¶
LeafIndexToPos returns the position of a leaf from its index.
func PosHeightInTree ¶
PosHeightInTree calculates and returns the height of a node in the tree using its position.
Types ¶
type Batch ¶
type Batch struct {
// contains filtered or unexported fields
}
Batch contains the a slice of Batch elements and a Store
type BatchElem ¶
type BatchElem struct {
// contains filtered or unexported fields
}
BatchElem holds the fields of data for a Batch Element
type Iterator ¶
type Iterator struct { Items [][]byte // contains filtered or unexported fields }
Iterator is a wrapper for a slice of bytes. It exposes helper methods for accessing about the slice and storing data to it
type MMR ¶
type MMR struct {
// contains filtered or unexported fields
}
MMR contains fields for computing the MMR tree.
func NewMMR ¶
NewMMR returns a new MMR type. It takes four arguments. It takes the mmrSize, Store, leaves and Hasher interfaces. It accepts any type that satisfies both the Store and Hasher interfaces. The parameter 'leaves' are leaves whose proof of inclusion would be verified.
func (*MMR) Commit ¶
func (m *MMR) Commit()
Commit calls the commit method on the batch property. It adds a batch element to the store
func (*MMR) GenProof ¶
GenProof generates merkle proof for positions. It sorts positions, pushes merkle proof to proof by peak from left to right. It then pushes bagged right hand side root
type MemStore ¶
MemStore is a map of bytes with uint64 values as its key
func NewMemStore ¶
func NewMemStore() MemStore
NewMemStore creates an returns a map of the MemStore type
type Proof ¶
type Proof struct { Hasher types.Hasher Leaves []types.Leaf // contains filtered or unexported fields }
Proof is the mmr proof. It is constructed to verify an MMR leaf.
func NewProof ¶
NewProof creates and returns new Proof. It takes the mmrSize, proof which is of type *Iterator and any type that satisfies the Merge interface.
func (*Proof) CalculateRoot ¶
CalculateRoot calculates and returns the root of the MMR tree using the leaves, mmrSize and proofs. It sorts the leaves by position, calculates the root of each peak and bags the peaks
func (*Proof) CalculateRootWithNewLeaf ¶
func (m *Proof) CalculateRootWithNewLeaf(leaves []types.Leaf, newIndex uint64, newElem []byte, newMMRSize uint64) ([]byte, error)
CalculateRootWithNewLeaf calculates and returns a new root provided a new leaf element, new position and new MMRsize. from merkle proof of leaf n to calculate merkle root of n + 1 leaves. By observing the MMR construction graph we know it is possible. https://github.com/jjyr/merkle-mountain-range#construct this is kinda tricky, but it works, and useful
func (*Proof) LeavesToVerify ¶
LeavesToVerify sets leaves to the leaves property in Proof
func (*Proof) ProofItems ¶
ProofItems returns all the proof items from the Iterator.