Documentation
¶
Index ¶
- Constants
- type CommAndLoc
- type Hybrid
- func (ht *Hybrid) BatchSet(vals []CommAndLoc) error
- func (ht Hybrid) CollectProof(level int, idx uint64) (ProofData, error)
- func (ht Hybrid) GetNode(level int, idx uint64) (Node, error)
- func (h *Hybrid) MarshalCBOR(w io.Writer) error
- func (ht Hybrid) MaxLevel() int
- func (ht Hybrid) Root() Node
- func (ht *Hybrid) SetNode(level int, idx uint64, n *Node) error
- func (h *Hybrid) UnmarshalCBOR(r io.Reader) (err error)
- type Location
- type MerkleTree
- type Node
- type ProofData
- func (d ProofData) ComputeRoot(subtree *Node) (*Node, error)
- func (d ProofData) Depth() int
- func (pd *ProofData) MarshalCBOR(w io.Writer) error
- func (nd *ProofData) UnmarshalCBOR(r io.Reader) error
- func (d ProofData) ValidateLeaf(data []byte, root *Node) error
- func (d ProofData) ValidateSubtree(subtree *Node, root *Node) error
- type ProofDataSerialization
- type SparseArray
- type TreeData
- func (d TreeData) ConstructProof(lvl int, idx uint64) (*ProofData, error)
- func (d TreeData) Depth() int
- func (d TreeData) LeafCount() uint64
- func (d TreeData) Leafs() []Node
- func (d TreeData) Node(lvl int, idx uint64) *Node
- func (d TreeData) Root() *Node
- func (d TreeData) Serialize() ([]byte, error)
- func (d TreeData) Validate() bool
- func (d TreeData) ValidateFromLeafs(leafs [][]byte) error
Constants ¶
const BytesInInt int = 64 / 8
BytesInInt represents the amount of bytes used to encode an int
const NodeSize = 32
const SparseBlockLog2Size = 8 // bench and tune if it is an issue
256 nodes per block, resulting in 8KiB blocks
const SparseBlockSize = 1 << SparseBlockLog2Size
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CommAndLoc ¶
CommAndLoc represents Commitment and Location
type Hybrid ¶
type Hybrid struct {
// contains filtered or unexported fields
}
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 ¶
CollectProof collects a proof from the specified node to the root of the tree
type Location ¶
Location represents a location in the MerkleTree Level is counted from the leaf layer, with 0 being leaf layer.
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 ¶
func TruncatedHash ¶
func ZeroCommitmentForLevel ¶
simple access by level, only levels between 0 and 64 inclusive are avaliable otherwise panics
func ZeroCommitmentForSize ¶
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) Depth ¶
Depth returns the level in the tree which the node this proof validates is located
func (ProofData) ValidateLeaf ¶
ValidateLeaf validates that the data given as input is contained in a Merkle tree with a specific 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 ¶
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 ¶
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 ¶
GrowTreeHashedLeafs constructs a tree from leafs nodes, i.e. leaf data that has been hashed to construct a Node
func (TreeData) ConstructProof ¶
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 ¶
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) Leafs ¶
Leafs return a slice consisting of all the leaf nodes, i.e. leaf data that has been hashed into a Node structure
func (TreeData) Serialize ¶
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 ¶
Validate returns true of this tree has been constructed correctly from the leafs (hashed data)
func (TreeData) ValidateFromLeafs ¶
ValidateFromLeafs validates the structure of this Merkle tree, given the raw data elements the tree was constructed from
Source Files