merkle

package module
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Oct 24, 2022 License: Apache-2.0 Imports: 7 Imported by: 9

README

merkle-tree

Efficient on-the-fly Merkle Tree implementation. This implementation allows generating minimal partial trees that proven membership of several leaves at once, without repeating nodes in the proof or including nodes that can be calculated.

Usage

TODO: add info

How it Works

Tree Construction

This library constructs a tree sequentially, in-memory, using O(log(n)) memory (n being the number of tree leaves).

Leaves are added to the tree one-by-one using the Tree.AddLeaf() method.

The following animation illustrates the way a tree is constructed:

legend Tree construction

For each node added we do the following (the leaf layer is 0):

  • Check if there's a pending node at the current layer in pending_left_siblings.
    • If there isn't - add the currently processing node to the current layer in the list.
    • If there is - use it along with the currently processing node to calculate the parent node and add it to the tree (then clear it from the list).

When there is a power-of-two number of leaves and this process is repeated for all leaves and internal nodes encountered, the end result in the pending_left_siblings list is that all entries are empty, except the last, which represents the root of the tree.

Since we process leaves sequentially from left to right, each left sibling (odd-indexed leaf) will end up being added to pending_left_siblings until its right sibling arrives. At this time both siblings are available and their parent can be calculated. We then go up a layer and repeat the process.

Proof Construction

TODO: add info

Documentation

Index

Examples

Constants

View Source 
const MaxUint = ^uint(0)
View Source 
const NodeSize = shared.NodeSize

Variables

View Source 
var EmptyNode node
View Source 
var ErrMissingValueAtBaseLayer = errors.New("reader for base layer must be included")
View Source 
var PaddingValue = node{

	OnProvenPath: false,
	// contains filtered or unexported fields
}

PaddingValue is used for padding unbalanced trees. This value should not be permitted at the leaf layer to distinguish padding from actual members of the tree.

View Source 
var RootHeightFromWidth = shared.RootHeightFromWidth

Functions

func GenerateProof 

func GenerateProof(
	provenLeafIndices map[uint64]bool,
	treeCache CacheReader,
) (sortedProvenLeafIndices []uint64, provenLeaves, proofNodes [][]byte, err error)

func GetNode 

func GetNode(c CacheReader, nodePos Position) ([]byte, error)

GetNode reads the node at the requested Position from the cache or calculates it if not available.

func GetSha256Parent 

func GetSha256Parent(lChild, rChild []byte) []byte

func NewPositionsIterator 

func NewPositionsIterator(positions Set) *positionsIterator

func NewSparseBoolStack 

func NewSparseBoolStack(trueIndices Set) *sparseBoolStack

func ValidatePartialTree 

func ValidatePartialTree(leafIndices []uint64, leaves, proof [][]byte, expectedRoot []byte,
	hash HashFunc,
) (bool, error)

ValidatePartialTree uses leafIndices, leaves and proof to calculate the merkle root of the tree and then compares it to expectedRoot.

Types

type CacheReader 

type CacheReader = shared.CacheReader

type CacheWriter 

type CacheWriter = shared.CacheWriter

type HashFunc 

type HashFunc = shared.HashFunc

type LayerReadWriter 

type LayerReadWriter = shared.LayerReadWriter

type LayerReader 

type LayerReader = shared.LayerReader

type LayerWriter 

type LayerWriter = shared.LayerWriter

type LeafIterator 

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

type ParkingSnapshot 

type ParkingSnapshot [][]byte

func ValidatePartialTreeWithParkingSnapshots 

func ValidatePartialTreeWithParkingSnapshots(leafIndices []uint64, leaves, proof [][]byte, expectedRoot []byte,
	hash HashFunc,
) (bool, []ParkingSnapshot, error)

ValidatePartialTree uses leafIndices, leaves and proof to calculate the merkle root of the tree and then compares it to expectedRoot. Additionally, it reconstructs the parked nodes when each proven leaf was originally added to the tree and returns a list of snapshots. This method is ~15% slower than ValidatePartialTree.

type Position 

type Position struct {
	Index  uint64
	Height uint
}

func (Position) String 

func (p Position) String() string

type Set 

type Set map[uint64]bool

func SetOf 

func SetOf(members ...uint64) Set

func (Set) AsSortedSlice 

func (s Set) AsSortedSlice() []uint64

type Tree 

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

Tree calculates a merkle tree root. It can optionally calculate a proof, or partial tree, for leaves defined in advance. Leaves are appended to the tree incrementally. It uses O(log(n)) memory to calculate the root and O(k*log(n)) (k being the number of leaves to prove) memory to calculate proofs.

Tree is NOT thread safe.

Example

Annotated example explaining how to use this package 

// First, we create a cache writer with caching policy and layer read-writer factory:
cacheWriter := cache.NewWriter(cache.MinHeightPolicy(0), cache.MakeSliceReadWriterFactory())

// We then initialize the tree:
tree, err := NewTreeBuilder().WithCacheWriter(cacheWriter).Build()
if err != nil {
	fmt.Println("Error while building the tree:", err.Error())
	return
}

// We add the leaves one-by-one:
for i := uint64(0); i < 8; i++ {
	err := tree.AddLeaf(NewNodeFromUint64(i))
	if err != nil {
		fmt.Println("Error while adding a leaf:", err.Error())
		return
	}
}

// After adding some leaves we can access the root of the tree:
fmt.Println(tree.Root()) // 89a0f1577268cc19b0a39c7a69f804fd140640c699585eb635ebb03c06154cce

// If we need to generate a proof, we could derive the proven leaves from the root. Here we create a static set:
leavesToProve := setOf(0, 4, 7)

// We get a cache reader from the cache writer:
cacheReader, err := cacheWriter.GetReader()
if err != nil {
	fmt.Println("Error while getting cache reader:", err.Error())
	return
}

// We pass the cache into GenerateProof along with the set of leaves to prove:
sortedProvenLeafIndices, provenLeaves, proof, err := GenerateProof(leavesToProve, cacheReader)
if err != nil {
	fmt.Println("Error while getting generating proof:", err.Error())
	return
}

// We now have access to a sorted list of proven leaves, the values of those leaves and the Merkle proof for them:
fmt.Println(sortedProvenLeafIndices) // 0 4 7
fmt.Println(nodes(provenLeaves))     // 0000 0400 0700
fmt.Println(nodes(proof))            // 0100 0094 0500 0600

// We can validate these values using ValidatePartialTree:
valid, err := ValidatePartialTree(sortedProvenLeafIndices, provenLeaves, proof, tree.Root(), GetSha256Parent)
if err != nil {
	fmt.Println("Error while validating proof:", err.Error())
	return
}
fmt.Println(valid) // true

/***************************************************
|                       89a0                       |
|           ba94                    633b           |
|     cb59       .0094.       bd50        fa67     |
| =0000=.0100. 0200  0300 =0400=.0500..0600.=0700= |
***************************************************/

Output:

func NewCachingTree 

func NewCachingTree(cacheWriter CacheWriter) (*Tree, error)

func NewProvingTree 

func NewProvingTree(leavesToProves map[uint64]bool) (*Tree, error)

func NewTree 

func NewTree() (*Tree, error)

func (*Tree) AddLeaf 

func (t *Tree) AddLeaf(value []byte) error

AddLeaf incorporates a new leaf to the state of the tree. It updates the state required to eventually determine the root of the tree and also updates the proof, if applicable.

func (*Tree) GetParkedNodes 

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

func (*Tree) Proof 

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

Proof returns a partial tree proving the membership of leaves that were passed in leavesToProve when the tree was initialized. For a single proved leaf this is a standard merkle proof (one sibling per layer of the tree from the leaves to the root, excluding the proved leaf and root). If the tree is unbalanced (num. of leaves is not a power of 2) it will perform padding on-the-fly.

func (*Tree) Root 

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

Root returns the root of the tree. If the tree is unbalanced (num. of leaves is not a power of 2) it will perform padding on-the-fly.

func (*Tree) RootAndProof 

func (t *Tree) RootAndProof() ([]byte, [][]byte)

RootAndProof returns the root of the tree and a partial tree proving the membership of leaves that were passed in leavesToProve when the tree was initialized. For a single proved leaf this is a standard merkle proof (one sibling per layer of the tree from the leaves to the root, excluding the proved leaf and root). If the tree is unbalanced (num. of leaves is not a power of 2) it will perform padding on-the-fly.

func (*Tree) SetParkedNodes 

func (t *Tree) SetParkedNodes(nodes [][]byte) error

type TreeBuilder 

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

func NewTreeBuilder 

func NewTreeBuilder() TreeBuilder

func (TreeBuilder) Build 

func (tb TreeBuilder) Build() (*Tree, error)

func (TreeBuilder) WithCacheWriter 

func (tb TreeBuilder) WithCacheWriter(cacheWriter CacheWriter) TreeBuilder

func (TreeBuilder) WithHashFunc 

func (tb TreeBuilder) WithHashFunc(hash HashFunc) TreeBuilder

func (TreeBuilder) WithLeavesToProve 

func (tb TreeBuilder) WithLeavesToProve(leavesToProves map[uint64]bool) TreeBuilder

func (TreeBuilder) WithMinHeight 

func (tb TreeBuilder) WithMinHeight(minHeight uint) TreeBuilder

type Validator 

type Validator struct {
	Leaves         *LeafIterator
	ProofNodes     *proofIterator
	Hash           HashFunc
	StoreSnapshots bool
}

func (*Validator) CalcRoot 

func (v *Validator) CalcRoot(stopAtLayer uint) ([]byte, []ParkingSnapshot, error)

Source Files

View all Source files

Directories

Path Synopsis
readwriters

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.