verkle

package module
v0.1.5 Latest Latest
Warning

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

 Go to latest Published: Dec 27, 2023 License: Unlicense Imports: 15 Imported by: 0

README

Go Version Lint and Test DeepSource goreports API Reference Block replay

go-verkle

A Go implementation of Verkle Tree datastructure defined in the spec.

Test & Benchmarks

To run the tests and benchmarks, run the following commands:

$ go test ./...

To run the benchmarks:

go test ./... -bench=. -run=none -benchmem

Security

If you find any security vulnerability, please don't open a GH issue and contact repo owners directly.

LICENSE

License.

Documentation

Index

Constants

View Source 
const (
	LeafValueSize      = 32
	NodeWidth          = 256
	NodeBitWidth  byte = 8
	StemSize           = 31
)
View Source 
const (
	CodeHashVectorPosition     = 3 // Defined by the spec.
	EmptyCodeHashFirstHalfIdx  = CodeHashVectorPosition * 2
	EmptyCodeHashSecondHalfIdx = EmptyCodeHashFirstHalfIdx + 1
)
View Source 
const IPA_PROOF_DEPTH = 8

Variables

View Source 
var (
	EmptyCodeHashPoint           Point
	EmptyCodeHashFirstHalfValue  Fr
	EmptyCodeHashSecondHalfValue Fr
)

EmptyCodeHashPoint is a cached point that is used to represent an empty code hash. This value is initialized once in GetConfig().

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

Functions

func FromBytes 

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

func FromLEBytes 

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

func HexToPrefixedString 

func HexToPrefixedString(data []byte) string

HexToPrefixedString turns a byte slice into its hex representation and prefixes it with `0x`.

func MakeVerkleMultiProof 

func MakeVerkleMultiProof(preroot, postroot VerkleNode, keys [][]byte, resolver NodeResolverFn) (*Proof, []*Point, []byte, []*Fr, error)

func PrefixedHexStringToBytes 

func PrefixedHexStringToBytes(input string) ([]byte, error)

PrefixedHexStringToBytes does the opposite of HexToPrefixedString.

func SerializeProof 

func SerializeProof(proof *Proof) (*VerkleProof, StateDiff, 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

func StemFromBytes 

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

func ToDot 

func ToDot(root VerkleNode) string

func VerifyVerkleProof 

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

func VerifyVerkleProofWithPreState 

func VerifyVerkleProofWithPreState(proof *Proof, preroot VerkleNode) error

VerifyVerkleProofWithPreState takes a proof and a trusted tree root and verifies that the proof is valid.

Types

type BatchNewLeafNodeData 

type BatchNewLeafNodeData struct {
	Stem   []byte
	Values map[byte][]byte
}

BatchNewLeafNodeData is a struct that contains the data needed to create a new leaf node.

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) CommitLog added in v0.1.3 

func (n Empty) CommitLog() *Point

func (Empty) Commitment 

func (Empty) Commitment() *Point

func (Empty) Copy 

func (Empty) Copy() VerkleNode

func (Empty) Delete 

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

func (Empty) Get 

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

func (Empty) GetProofItems 

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

func (Empty) Hash 

func (Empty) Hash() *Fr

func (Empty) Insert 

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

func (Empty) Serialize 

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

func (Empty) ToDot added in v0.1.3 

func (Empty) ToDot(string, string) string

type ExportableInternalNode 

type ExportableInternalNode struct {
	Children []interface{} `json:"children"`

	Commitment []byte `json:"commitment"`
}

A few proxy types that export their fields, so that the core type does not. The conversion from one type to the other is done by calling toExportable on an InternalNode.

type ExportableLeafNode 

type ExportableLeafNode struct {
	Stem   []byte   `json:"stem"`
	Values [][]byte `json:"values"`

	C  [32]byte `json:"commitment"`
	C1 [32]byte `json:"c1"`
	C2 [32]byte `json:"c2"`
}

A few proxy types that export their fields, so that the core type does not. The conversion from one type to the other is done by calling toExportable on an InternalNode.

type Fr 

type Fr = banderwagon.Fr
var (
	FrZero Fr
	FrOne  Fr
)

type HashedNode 

type HashedNode struct{}

func (HashedNode) Commit 

func (HashedNode) Commit() *Point

func (HashedNode) CommitLog added in v0.1.3 

func (HashedNode) CommitLog() *Point

func (HashedNode) Commitment 

func (HashedNode) Commitment() *Point

func (HashedNode) Copy 

func (HashedNode) Copy() VerkleNode

func (HashedNode) Delete 

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

func (HashedNode) Get 

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

func (HashedNode) GetProofItems 

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

func (HashedNode) Hash 

func (HashedNode) Hash() *Fr

func (HashedNode) Insert 

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

func (HashedNode) Serialize 

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

func (HashedNode) ToDot added in v0.1.3 

func (HashedNode) ToDot(parent, path string) string

type IPAConfig 

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

func (*IPAConfig) CommitToPoly 

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

type IPAProof 

type IPAProof struct {
	CL              [IPA_PROOF_DEPTH][32]byte `json:"cl"`
	CR              [IPA_PROOF_DEPTH][32]byte `json:"cr"`
	FinalEvaluation [32]byte                  `json:"finalEvaluation"`
}

func (*IPAProof) MarshalJSON 

func (ipp *IPAProof) MarshalJSON() ([]byte, error)

func (*IPAProof) UnmarshalJSON 

func (ipp *IPAProof) UnmarshalJSON(data []byte) error

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) (*InternalNode, error)

func (*InternalNode) BatchSerialize 

func (n *InternalNode) BatchSerialize() ([]SerializedNode, error)

BatchSerialize is an optimized serialization API when multiple VerkleNodes serializations are required, and all are available in memory.

func (*InternalNode) Children 

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

Children return the children of the node. The returned slice is internal to the tree, so callers *must* consider it readonly.

func (*InternalNode) Commit 

func (n *InternalNode) Commit() *Point

func (*InternalNode) CommitLog added in v0.1.3 

func (n *InternalNode) CommitLog() *Point

func (*InternalNode) Commitment 

func (n *InternalNode) Commitment() *Point

func (*InternalNode) Copy 

func (n *InternalNode) Copy() VerkleNode

func (*InternalNode) CreatePath 

func (n *InternalNode) CreatePath(path []byte, stemInfo stemInfo, comms []*Point, values [][]byte) ([]*Point, error)

CreatePath inserts a given stem in the tree, placing it as described by stemInfo. Its third parameters is the list of commitments that have not been assigned a node. It returns the same list, save the commitments that were consumed during this call.

func (*InternalNode) Delete 

func (n *InternalNode) Delete(key []byte, resolver NodeResolverFn) (bool, 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(key []byte, resolver NodeResolverFn) ([]byte, error)

func (*InternalNode) GetProofItems 

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

func (*InternalNode) GetValuesAtStem 

func (n *InternalNode) GetValuesAtStem(stem []byte, resolver NodeResolverFn) ([][]byte, error)

GetValuesAtStem returns the all NodeWidth values of the stem. The returned slice is internal to the tree, so it *must* be considered readonly for callers.

func (*InternalNode) Hash 

func (n *InternalNode) Hash() *Fr

func (*InternalNode) Insert 

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

func (*InternalNode) InsertMigratedLeaves 

func (n *InternalNode) InsertMigratedLeaves(leaves []LeafNode, resolver NodeResolverFn) error

func (*InternalNode) InsertValuesAtStem 

func (n *InternalNode) InsertValuesAtStem(stem []byte, values [][]byte, resolver NodeResolverFn) error

func (*InternalNode) Serialize 

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

Serialize returns the serialized form of the internal node. The format is: <nodeType><bitlist><commitment>

func (*InternalNode) SetChild 

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

SetChild *replaces* the child at the given index with the given node.

func (*InternalNode) ToDot added in v0.1.3 

func (n *InternalNode) ToDot(parent, path string) string

func (*InternalNode) ToJSON 

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

Turn an internal node into a JSON string

type LeafNode 

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

func BatchNewLeafNode 

func BatchNewLeafNode(nodesValues []BatchNewLeafNodeData) ([]LeafNode, error)

BatchNewLeafNode creates a new leaf node from the given data. It optimizes LeafNode creation by batching expensive cryptography operations. It returns the LeafNodes sorted by stem.

func NewLeafNode 

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

New creates a new leaf node

func NewLeafNodeWithNoComms 

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

NewLeafNodeWithNoComms create a leaf node but does not compute its commitments. The created node's commitments are intended to be initialized with `SetTrustedBytes` in a deserialization context.

func (*LeafNode) Commit 

func (n *LeafNode) Commit() *Point

func (*LeafNode) CommitLog added in v0.1.3 

func (n *LeafNode) CommitLog() *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) (bool, error)

Delete deletes a value from the leaf, return `true` as a second return value, if the parent should entirely delete the child.

func (*LeafNode) Get 

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

func (*LeafNode) GetProofItems 

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

func (*LeafNode) Hash 

func (n *LeafNode) Hash() *Fr

func (*LeafNode) Insert 

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

func (*LeafNode) Key 

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

func (*LeafNode) Serialize 

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

Serialize serializes a LeafNode. The format is: <nodeType><stem><bitlist><comm><c1comm><c2comm><children...>

func (*LeafNode) ToDot added in v0.1.3 

func (n *LeafNode) ToDot(parent, path string) string

func (*LeafNode) Value 

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

func (*LeafNode) Values 

func (n *LeafNode) Values() [][]byte

type NodeFlushFn 

type NodeFlushFn func([]byte, VerkleNode)

type NodeResolverFn 

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

type Point 

type Point = banderwagon.Element

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
	PreValues  [][]byte
	PostValues [][]byte
}

func DeserializeProof 

func DeserializeProof(vp *VerkleProof, statediff StateDiff) (*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
	Vals   [][]byte          // list of values read from the tree
	// contains filtered or unexported fields
}

ProofElements gathers the elements needed to build a proof.

func GetCommitmentsForMultiproof 

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

func (*ProofElements) Merge 

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

Merge merges the elements of two proofs and removes duplicates.

type SerializedNode 

type SerializedNode struct {
	Node            VerkleNode
	CommitmentBytes [banderwagon.UncompressedSize]byte
	Path            []byte
	SerializedBytes []byte
}

SerializedNode contains a serialization of a tree node. It provides everything that the client needs to save the node to the database. For example, CommitmentBytes is usually use as key and SerializedBytes as value. Providing both allows this library to do more optimizations.

type SerializedPoint 

type SerializedPoint = []byte

type SerializedPointCompressed 

type SerializedPointCompressed = []byte

type StateDiff 

type StateDiff []StemStateDiff

func (StateDiff) Copy 

func (sd StateDiff) Copy() StateDiff

type StemStateDiff 

type StemStateDiff struct {
	Stem        [31]byte         `json:"stem"`
	SuffixDiffs SuffixStateDiffs `json:"suffixDiffs"`
}

func (StemStateDiff) MarshalJSON 

func (ssd StemStateDiff) MarshalJSON() ([]byte, error)

func (*StemStateDiff) UnmarshalJSON 

func (ssd *StemStateDiff) UnmarshalJSON(data []byte) error

type SuffixStateDiff 

type SuffixStateDiff struct {
	Suffix       byte      `json:"suffix"`
	CurrentValue *[32]byte `json:"currentValue"`
	NewValue     *[32]byte `json:"newValue"`
}

func (SuffixStateDiff) MarshalJSON 

func (ssd SuffixStateDiff) MarshalJSON() ([]byte, error)

func (*SuffixStateDiff) UnmarshalJSON 

func (ssd *SuffixStateDiff) UnmarshalJSON(data []byte) error

type SuffixStateDiffs 

type SuffixStateDiffs []SuffixStateDiff

type UnknownNode 

type UnknownNode struct{}

func (UnknownNode) Commit 

func (n UnknownNode) Commit() *Point

func (UnknownNode) CommitLog added in v0.1.3 

func (n UnknownNode) CommitLog() *Point

func (UnknownNode) Commitment 

func (UnknownNode) Commitment() *Point

func (UnknownNode) Copy 

func (UnknownNode) Copy() VerkleNode

func (UnknownNode) Delete 

func (UnknownNode) Delete([]byte, NodeResolverFn) (bool, error)

func (UnknownNode) Get 

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

func (UnknownNode) GetProofItems 

func (UnknownNode) GetProofItems(keylist, NodeResolverFn) (*ProofElements, []byte, [][]byte, error)

func (UnknownNode) Hash 

func (UnknownNode) Hash() *Fr

func (UnknownNode) Insert 

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

func (UnknownNode) Serialize 

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

func (UnknownNode) ToDot added in v0.1.3 

func (UnknownNode) ToDot(string, string) string

type VerkleNode 

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

	// Delete a leaf with the given key
	Delete([]byte, NodeResolverFn) (bool, 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

	// Same as Commit but prints logs
	CommitLog() *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, NodeResolverFn) (*ProofElements, []byte, [][]byte, error)

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

	// Copy a node and its children
	Copy() VerkleNode

	// ToDot returns a string representing this subtree in DOT language
	ToDot(string, string) string
	// 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. This method is deprecated, use with caution.

func New 

func New() VerkleNode

New creates a new tree root

func NewStatelessInternal 

func NewStatelessInternal(depth byte, comm *Point) VerkleNode

func ParseNode 

func ParseNode(serializedNode []byte, depth byte) (VerkleNode, error)

ParseNode deserializes a node into its proper VerkleNode instance. The serialized bytes have the format: - Internal nodes: <nodeType><bitlist><commitment> - Leaf nodes: <nodeType><stem><bitlist><comm><c1comm><c2comm><children...>

func PostStateTreeFromStateDiff 

func PostStateTreeFromStateDiff(preroot VerkleNode, statediff StateDiff) (VerkleNode, error)

PostStateTreeFromProof uses the pre-state trie and the list of updated values to produce the stateless post-state trie.

func PreStateTreeFromProof 

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

PreStateTreeFromProof builds a stateless prestate tree from the proof.

type VerkleProof 

type VerkleProof struct {
	OtherStems            [][31]byte `json:"otherStems"`
	DepthExtensionPresent []byte     `json:"depthExtensionPresent"`
	CommitmentsByPath     [][32]byte `json:"commitmentsByPath"`
	D                     [32]byte   `json:"d"`
	IPAProof              *IPAProof  `json:"ipa_proof"`
}

func (*VerkleProof) Copy 

func (vp *VerkleProof) Copy() *VerkleProof

func (*VerkleProof) MarshalJSON 

func (vp *VerkleProof) MarshalJSON() ([]byte, error)

func (*VerkleProof) UnmarshalJSON 

func (vp *VerkleProof) UnmarshalJSON(data []byte) error

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.