verkle

package module
v0.0.0-...-ca69838 Latest Latest
Warning

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

 Go to latest Published: Jan 11, 2024 License: Unlicense Imports: 12 Imported by: 0

README

Lint and Test DeepSource goreports API Reference

go-verkle

An implementation of Verkle trees. When production-ready, the code is to be merged back into go-ethereum.

Node width is set to 256 children.

Setup

Download the precomputed Lagrange point file available in this release, and place it in the directory that you will run the program from. While not strictly required (it will be generated upon startup if not present), this will save a lot of startup time when running the tests.

Running the tests
$ go test .
Benchmarks
$ go test . -bench Bench

Documentation

Index

Constants

View Source 
const (
	NodeWidth         = 256
	NodeBitWidth byte = 8
)

Variables

View Source 
var ErrInvalidNodeEncoding = errors.New("invalid node encoding")

Functions

func CopyFr 

func CopyFr(dst, src *Fr)

func CopyPoint 

func CopyPoint(dst, src *Point)

func Equal 

func Equal(self *Point, other *Point) bool

func FromBytes 

func FromBytes(fr *Fr, data []byte)

func FromLEBytes 

func FromLEBytes(fr *Fr, data []byte)

func MakeVerkleMultiProof 

func MakeVerkleMultiProof(root VerkleNode, keys [][]byte, keyvals map[string][]byte) (*Proof, []*Point, []byte, []*Fr, error)

func StemFromBytes 

func StemFromBytes(fr *Fr, data []byte)

func ToDot 

func ToDot(root VerkleNode) string

func VerifyVerkleProof 

func VerifyVerkleProof(proof *Proof, Cs []*Point, indices []uint8, ys []*Fr, tc *Config) bool

Types

type Committer 

type Committer interface {
	CommitToPoly([]Fr, int) *Point
}

Committer represents an object that is able to create the commitment to a polynomial.

type Config 

type Config = IPAConfig

func GetConfig 

func GetConfig() *Config

type Empty 

type Empty struct{}

func (Empty) Commit 

func (n Empty) Commit() *Point

func (Empty) Commitment 

func (Empty) Commitment() *Point

func (Empty) Copy 

func (Empty) Copy() VerkleNode

func (Empty) Delete 

func (Empty) Delete([]byte, NodeResolverFn) error

func (Empty) Get 

func (Empty) Get([]byte, NodeResolverFn) ([]byte, error)

func (Empty) GetProofItems 

func (Empty) GetProofItems(keylist) (*ProofElements, []byte, [][]byte)

func (Empty) Hash 

func (Empty) Hash() *Fr

func (Empty) Insert 

func (Empty) Insert([]byte, []byte, NodeResolverFn) error

func (Empty) InsertOrdered 

func (e Empty) InsertOrdered(key []byte, value []byte, _ NodeFlushFn) error

func (Empty) Serialize 

func (Empty) Serialize() ([]byte, error)

type Fr 

type Fr = fr.Element
var FrOne Fr
var FrZero Fr

type HashedNode 

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

func (*HashedNode) Commit 

func (n *HashedNode) Commit() *Point

func (*HashedNode) Commitment 

func (n *HashedNode) Commitment() *Point

func (*HashedNode) Copy 

func (n *HashedNode) Copy() VerkleNode

func (*HashedNode) Delete 

func (*HashedNode) Delete([]byte, NodeResolverFn) error

func (*HashedNode) Get 

func (*HashedNode) Get([]byte, NodeResolverFn) ([]byte, error)

func (*HashedNode) GetProofItems 

func (*HashedNode) GetProofItems(keylist) (*ProofElements, []byte, [][]byte)

func (*HashedNode) Hash 

func (n *HashedNode) Hash() *Fr

func (*HashedNode) Insert 

func (*HashedNode) Insert([]byte, []byte, NodeResolverFn) error

func (*HashedNode) InsertOrdered 

func (*HashedNode) InsertOrdered([]byte, []byte, NodeFlushFn) error

func (*HashedNode) Serialize 

func (*HashedNode) Serialize() ([]byte, error)

type IPAConfig 

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

func (*IPAConfig) CommitToPoly 

func (ipac *IPAConfig) CommitToPoly(poly []Fr, _ int) *Point

type InternalNode 

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

Represents an internal node at any level

func CreateInternalNode 

func CreateInternalNode(bitlist []byte, raw []byte, depth byte, comm []byte) (*InternalNode, error)

func (*InternalNode) Children 

func (n *InternalNode) Children() []VerkleNode

func (*InternalNode) Commit 

func (n *InternalNode) Commit() *Point

func (*InternalNode) Commitment 

func (n *InternalNode) Commitment() *Point

func (*InternalNode) Copy 

func (n *InternalNode) Copy() VerkleNode

func (*InternalNode) Delete 

func (n *InternalNode) Delete(key []byte, resolver NodeResolverFn) error

func (*InternalNode) Flush 

func (n *InternalNode) Flush(flush NodeFlushFn)

Flush hashes the children of an internal node and replaces them with HashedNode. It also sends the current node on the flush channel.

func (*InternalNode) FlushAtDepth 

func (n *InternalNode) FlushAtDepth(depth uint8, flush NodeFlushFn)

FlushAtDepth goes over all internal nodes of a given depth, and flushes them to disk. Its purpose it to free up space if memory is running scarce.

func (*InternalNode) Get 

func (n *InternalNode) Get(k []byte, getter NodeResolverFn) ([]byte, error)

func (*InternalNode) GetProofItems 

func (n *InternalNode) GetProofItems(keys keylist) (*ProofElements, []byte, [][]byte)

func (*InternalNode) Hash 

func (n *InternalNode) Hash() *Fr

func (*InternalNode) Insert 

func (n *InternalNode) Insert(key []byte, value []byte, resolver NodeResolverFn) error

func (*InternalNode) InsertOrdered 

func (n *InternalNode) InsertOrdered(key []byte, value []byte, flush NodeFlushFn) (err error)

func (*InternalNode) InsertStem 

func (n *InternalNode) InsertStem(stem []byte, node VerkleNode, resolver NodeResolverFn, overwrite bool) error

InsertStem inserts a pre-constructed node into the tree at stem stem. If the `overwrite` bit is set to true, if and the inserted node is a leaf, it will attempt to merge that leaf with the one already present in the trie (if such a leaf is already present). Merging a leaf and another type of node (i.e. a subtree insertion) will return an error.

func (*InternalNode) InsertStemOrdered 

func (n *InternalNode) InsertStemOrdered(key []byte, leaf *LeafNode, flush NodeFlushFn) error

InsertStemOrdered does the same thing as InsertOrdered but is meant to insert a pre-build LeafNode at a given stem, instead of individual leaves.

func (*InternalNode) Serialize 

func (n *InternalNode) Serialize() ([]byte, error)

func (*InternalNode) SetChild 

func (n *InternalNode) SetChild(i int, c VerkleNode) error

type KeyValuePair 

type KeyValuePair struct {
	Key   []byte
	Value []byte
}

A structure representing a tuple

func SerializeProof 

func SerializeProof(proof *Proof) ([]byte, []KeyValuePair, error)

SerializeProof serializes the proof in the rust-verkle format: * len(Proof of absence stem) || Proof of absence stems * len(depths) || serialize(depth || ext statusi) * len(commitments) || serialize(commitment) * Multipoint proof it also returns the serialized keys and values

type LeafNode 

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

func NewLeafNode 

func NewLeafNode(stem []byte, values [][]byte) *LeafNode

New creates a new leaf node

func NewLeafNodeWithSingleValue 

func NewLeafNodeWithSingleValue(key []byte, value []byte, depth byte) *LeafNode

func (*LeafNode) Commit 

func (n *LeafNode) Commit() *Point

func (*LeafNode) Commitment 

func (n *LeafNode) Commitment() *Point

func (*LeafNode) Copy 

func (n *LeafNode) Copy() VerkleNode

func (*LeafNode) Delete 

func (n *LeafNode) Delete(k []byte, _ NodeResolverFn) error

func (*LeafNode) Get 

func (n *LeafNode) Get(k []byte, _ NodeResolverFn) ([]byte, error)

func (*LeafNode) GetProofItems 

func (n *LeafNode) GetProofItems(keys keylist) (*ProofElements, []byte, [][]byte)

func (*LeafNode) Hash 

func (n *LeafNode) Hash() *Fr

func (*LeafNode) Insert 

func (n *LeafNode) Insert(k []byte, value []byte, _ NodeResolverFn) error

func (*LeafNode) InsertOrdered 

func (n *LeafNode) InsertOrdered(key []byte, value []byte, _ NodeFlushFn) error

func (*LeafNode) Key 

func (n *LeafNode) Key(i int) []byte

func (*LeafNode) Serialize 

func (n *LeafNode) Serialize() ([]byte, error)

func (*LeafNode) ToHashedNode 

func (n *LeafNode) ToHashedNode() *HashedNode

func (*LeafNode) Value 

func (n *LeafNode) Value(i int) []byte

type NodeFlushFn 

type NodeFlushFn func(VerkleNode)

type NodeResolverFn 

type NodeResolverFn func([]byte) ([]byte, error)

type Point 

type Point = banderwagon.Element

func Generator 

func Generator() *Point

type Proof 

type Proof struct {
	Multipoint *ipa.MultiProof // multipoint argument
	ExtStatus  []byte          // the extension status of each stem
	Cs         []*Point        // commitments, sorted by their path in the tree
	PoaStems   [][]byte        // stems proving another stem is absent
	Keys       [][]byte
	Values     [][]byte
}

func DeserializeProof 

func DeserializeProof(proofSerialized []byte, keyvals []KeyValuePair) (*Proof, error)

DeserializeProof deserializes the proof found in blocks, into a format that can be used to rebuild a stateless version of the tree.

type ProofElements 

type ProofElements struct {
	Cis    []*Point
	Zis    []byte
	Yis    []*Fr
	Fis    [][]Fr
	ByPath map[string]*Point // Gather commitments by path
	// contains filtered or unexported fields
}

ProofElements gathers the elements needed to build a proof.

func GetCommitmentsForMultiproof 

func GetCommitmentsForMultiproof(root VerkleNode, keys [][]byte) (*ProofElements, []byte, [][]byte)

func (*ProofElements) Merge 

func (pe *ProofElements) Merge(other *ProofElements)

Merge merges the elements of two proofs and removes duplicates.

type StatelessNode 

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

StatelessNode represents a node for execution in a stateless context, i.e. that its children/values are not all known. It can represent both an InternalNode or a LeafNode.

func NewStateless 

func NewStateless() *StatelessNode

func NewStatelessWithCommitment 

func NewStatelessWithCommitment(point *Point) *StatelessNode

func (*StatelessNode) Children 

func (n *StatelessNode) Children() []VerkleNode

func (*StatelessNode) Commit 

func (n *StatelessNode) Commit() *Point

func (*StatelessNode) Commitment 

func (n *StatelessNode) Commitment() *Point

func (*StatelessNode) Copy 

func (n *StatelessNode) Copy() VerkleNode

func (*StatelessNode) Delete 

func (n *StatelessNode) Delete(key []byte, resolver NodeResolverFn) error

Delete writes the value `0` at `key` since verkle trees need to distinguish between a node that used to be present and was then deleted, and a node that was never present.

func (*StatelessNode) Flush 

func (n *StatelessNode) Flush(flush NodeFlushFn)

func (*StatelessNode) Get 

func (n *StatelessNode) Get(k []byte, getter NodeResolverFn) ([]byte, error)

func (*StatelessNode) GetProofItems 

func (n *StatelessNode) GetProofItems(keys keylist) (*ProofElements, []byte, [][]byte)

func (*StatelessNode) Hash 

func (n *StatelessNode) Hash() *Fr

func (*StatelessNode) Insert 

func (n *StatelessNode) Insert(key []byte, value []byte, resolver NodeResolverFn) error

func (*StatelessNode) InsertAtStem 

func (n *StatelessNode) InsertAtStem(stem []byte, values [][]byte, resolver NodeResolverFn, _ bool) error

func (*StatelessNode) InsertOrdered 

func (*StatelessNode) InsertOrdered([]byte, []byte, NodeFlushFn) error

func (*StatelessNode) Serialize 

func (n *StatelessNode) Serialize() ([]byte, error)

func (*StatelessNode) SetChild 

func (n *StatelessNode) SetChild(i int, v VerkleNode) error

func (*StatelessNode) ToHashedNode 

func (n *StatelessNode) ToHashedNode() *HashedNode

type VerkleNode 

type VerkleNode interface {
	// Insert or Update value into the tree
	Insert([]byte, []byte, NodeResolverFn) error

	// Insert "à la" Stacktrie. Same thing as insert, except that
	// values are expected to be ordered, and the commitments and
	// hashes for each subtrie are computed online, as soon as it
	// is clear that no more values will be inserted in there.
	InsertOrdered([]byte, []byte, NodeFlushFn) error

	// Delete a leaf with the given key
	Delete([]byte, NodeResolverFn) error

	// Get value at a given key
	Get([]byte, NodeResolverFn) ([]byte, error)

	// Commit computes the commitment of the node. The
	// result (the curve point) is cached.
	Commit() *Point

	// Commitment is a getter for the cached commitment
	// to this node.
	Commitment() *Point

	// Hash returns the field representation of the commitment.
	Hash() *Fr

	// GetProofItems collects the various proof elements, and
	// returns them breadth-first. On top of that, it returns
	// one "extension status" per stem, and an alternate stem
	// if the key is missing but another stem has been found.
	GetProofItems(keylist) (*ProofElements, []byte, [][]byte)

	// Serialize encodes the node to RLP.
	Serialize() ([]byte, error)

	// Copy a node and its children
	Copy() VerkleNode
	// contains filtered or unexported methods
}

func MergeTrees 

func MergeTrees(subroots []*InternalNode) VerkleNode

MergeTrees takes a series of subtrees that got filled following a command-and-conquer method, and merges them into a single tree.

func New 

func New() VerkleNode

New creates a new tree root

func ParseNode 

func ParseNode(serialized []byte, depth byte, comm []byte) (VerkleNode, error)

func TreeFromProof 

func TreeFromProof(proof *Proof, rootC *Point) (VerkleNode, error)

TreeFromProof builds a stateless tree from the proof

Source Files

View all Source files

Directories

Path Synopsis

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.