merkletree

package
v0.0.1 Latest Latest
Warning

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

 Go to latest Published: Jul 4, 2023 License: Apache-2.0, MIT Imports: 18 Imported by: 2

Documentation

Index

Constants

View Source 
const BytesInInt int = 64 / 8

BytesInInt represents the amount of bytes used to encode an int

View Source 
const NodeSize = 32
View Source 
const SparseBlockLog2Size = 8 // bench and tune if it is an issue

256 nodes per block, resulting in 8KiB blocks

View Source 
const SparseBlockSize = 1 << SparseBlockLog2Size

Variables

This section is empty.

Functions

This section is empty.

Types

type CommAndLoc 

type CommAndLoc struct {
	Comm Node
	Loc  Location
}

CommAndLoc represents Commitment and Location

type Hybrid 

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

func NewHybrid 

func NewHybrid(log2Leafs int) (Hybrid, error)

func (*Hybrid) BatchSet 

func (ht *Hybrid) BatchSet(vals []CommAndLoc) error

BatchSet can be used for optimisation if necessary Current algorith is O(M*log2(N)) where M=len(vals) and N=#leafs There exists an optimization of applying all Set operations at the same time avoiding the repeated updates to the same nodes. This results in complexity always better than O(M*log2(N)), O(M+log2(N)) in the best case scenario, with the worse case of O(N).

func (Hybrid) CollectProof 

func (ht Hybrid) CollectProof(level int, idx uint64) (ProofData, error)

CollectProof collects a proof from the specified node to the root of the tree

func (Hybrid) GetNode 

func (ht Hybrid) GetNode(level int, idx uint64) (Node, error)

func (*Hybrid) MarshalCBOR 

func (h *Hybrid) MarshalCBOR(w io.Writer) error

func (Hybrid) MaxLevel 

func (ht Hybrid) MaxLevel() int

func (Hybrid) Root 

func (ht Hybrid) Root() Node

func (*Hybrid) SetNode 

func (ht *Hybrid) SetNode(level int, idx uint64, n *Node) error

func (*Hybrid) UnmarshalCBOR 

func (h *Hybrid) UnmarshalCBOR(r io.Reader) (err error)

type Location 

type Location struct {
	Level int
	Index uint64
}

Location represents a location in the MerkleTree Level is counted from the leaf layer, with 0 being leaf layer.

func (Location) LeafIndex 

func (l Location) LeafIndex() uint64

type MerkleTree 

type MerkleTree interface {
	// Depth returns the Depth of the tree. A single-node tree has Depth 1
	Depth() int
	// LeafCount returns the amount of leafs in the Merkle tree
	LeafCount() uint64
	// Root returns the root node of the tree
	Root() *Node
	// Leafs returns all the leaf nodes in the tree
	Leafs() []Node
	// Node returns the node at given lvl and idx
	Node(int, uint64) *Node
	// ConstructProof constructs a Merkle proof of the subtree (or leaf) at level lvl with index idx.
	// level 0 is the root and index 0 is the left-most node in a level.
	ConstructProof(lvl int, idx uint64) (*ProofData, error)
	// ValidateFromLeafs checks that the Merkle tree is correctly constructed based on all the leafData
	ValidateFromLeafs(leafData [][]byte) error
	// Validate checks that the Merkle tree is correctly constructed, based on the internal nodes
	Validate() bool
	// Serialize serializes the MerkleTree into a byte slice
	Serialize() ([]byte, error)
}

MerkleTree represents a Merkle tree which can be used to construct proof of containment for either leafs, subtrees or a sequence of leafs (subtrees)

type Node 

type Node [NodeSize]byte

func TruncatedHash 

func TruncatedHash(data []byte) *Node

func ZeroCommitmentForLevel 

func ZeroCommitmentForLevel(lvl int) Node

simple access by level, only levels between 0 and 64 inclusive are avaliable otherwise panics

func ZeroCommitmentForSize 

func ZeroCommitmentForSize(size uint64) (Node, error)

func (*Node) IsZero 

func (n *Node) IsZero() bool

func (*Node) MarshalCBOR 

func (n *Node) MarshalCBOR(w io.Writer) error

func (*Node) UnmarshalCBOR 

func (n *Node) UnmarshalCBOR(r io.Reader) error

type ProofData 

type ProofData struct {
	Path []Node
	// index indicates the index within the level where the element whose membership to prove is located
	// Leftmost node is index 0
	Index uint64
}

func (ProofData) ComputeRoot 

func (d ProofData) ComputeRoot(subtree *Node) (*Node, error)

func (ProofData) Depth 

func (d ProofData) Depth() int

Depth returns the level in the tree which the node this proof validates is located

func (*ProofData) MarshalCBOR 

func (pd *ProofData) MarshalCBOR(w io.Writer) error

func (*ProofData) UnmarshalCBOR 

func (nd *ProofData) UnmarshalCBOR(r io.Reader) error

func (ProofData) ValidateLeaf 

func (d ProofData) ValidateLeaf(data []byte, root *Node) error

ValidateLeaf validates that the data given as input is contained in a Merkle tree with a specific root

func (ProofData) ValidateSubtree 

func (d ProofData) ValidateSubtree(subtree *Node, root *Node) error

ValidateSubtree validates that a subtree is contained in the in a Merkle tree with a given root

type ProofDataSerialization 

type ProofDataSerialization struct {
	Index uint64
	Path  nodeArray
}

func (*ProofDataSerialization) MarshalCBOR 

func (t *ProofDataSerialization) MarshalCBOR(w io.Writer) error

func (*ProofDataSerialization) UnmarshalCBOR 

func (t *ProofDataSerialization) UnmarshalCBOR(r io.Reader) (err error)

type SparseArray 

type SparseArray[T any] struct {
	// contains filtered or unexported fields
}

func (SparseArray[T]) Get 

func (sa SparseArray[T]) Get(index uint64) T

func (*SparseArray[T]) GetSliceRef 

func (sa *SparseArray[T]) GetSliceRef(index uint64, length int) ([]T, error)

func (*SparseArray[T]) Set 

func (sa *SparseArray[T]) Set(index uint64, val *T) T

Set returns the old value

type TreeData 

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

func DeserializeTree 

func DeserializeTree(tree []byte) (*TreeData, error)

DeserializeTree deserializes a serialized Merkle tree This is done by first reading the amount of leafs as a 64 bit int Then decoding the tree, bottom-up, starting with the leafs as the amount of nodes in one level defines the amount of nodes in its parent level NOTE that correctness of the tree is NOT validated as part of this method

func GrowTree 

func GrowTree(leafData [][]byte) (*TreeData, error)

GrowTree constructs a Merkle from a list of leafData, the data of a given leaf is represented as a byte slice The construction rounds the amount of leafs up to the nearest two-power with zeroed nodes to ensure that the tree is perfect and hence all internal node's have well-defined children. TODO should things be hard-coded to work on 32 byte leafs?

func GrowTreeHashedLeafs 

func GrowTreeHashedLeafs(leafs []Node) *TreeData

GrowTreeHashedLeafs constructs a tree from leafs nodes, i.e. leaf data that has been hashed to construct a Node

func (TreeData) ConstructProof 

func (d TreeData) ConstructProof(lvl int, idx uint64) (*ProofData, error)

ConstructProof constructs a proof that a node at level lvl and index idx within that level, is contained in the tree. The root is in level 0 and the left-most node in a given level is indexed 0.

func (TreeData) Depth 

func (d TreeData) Depth() int

Depth returns the amount of levels in the tree, including the root level and leafs. I.e. a tree with 3 leafs will have one leaf level, a middle level and a root, and hence Depth 3.

func (TreeData) LeafCount 

func (d TreeData) LeafCount() uint64

LeafCount returns the amount of non-zero padded leafs in the tree

func (TreeData) Leafs 

func (d TreeData) Leafs() []Node

Leafs return a slice consisting of all the leaf nodes, i.e. leaf data that has been hashed into a Node structure

func (TreeData) Node 

func (d TreeData) Node(lvl int, idx uint64) *Node

Node returns the node at given lvl and idx

func (TreeData) Root 

func (d TreeData) Root() *Node

Root returns a pointer to the root node

func (TreeData) Serialize 

func (d TreeData) Serialize() ([]byte, error)

Serialize serializes the MerkleTree into a byte slice This is done by first including the amount of leafs as a 64 bit unsigned int Then encode the tree, bottom-up, starting with the leafs as the amount of nodes in one level defines the amount of nodes in its parent level NOTE that correctness of the tree is NOT validated as part of this method

func (TreeData) Validate 

func (d TreeData) Validate() bool

Validate returns true of this tree has been constructed correctly from the leafs (hashed data)

func (TreeData) ValidateFromLeafs 

func (d TreeData) ValidateFromLeafs(leafs [][]byte) error

ValidateFromLeafs validates the structure of this Merkle tree, given the raw data elements the tree was constructed from

Source Files

View all Source files

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.