verkle

package module
v0.0.0-...-15cf0d5 Latest Latest
Warning

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

Go to latest
Published: Jul 15, 2024 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 (
	KeySize            = 32
	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 GetCommitmentsForMultiproof

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

func HashPointToBytes

func HashPointToBytes(point *Point) [32]byte

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 StemFromLEBytes

func StemFromLEBytes(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   Stem
	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) 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, []Stem, 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)

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   Stem     `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) 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, []Stem, 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)

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) 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, []Stem, error)

func (*InternalNode) GetValuesAtStem

func (n *InternalNode) GetValuesAtStem(stem Stem, 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 Stem, 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) 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 Stem, values [][]byte) (*LeafNode, error)

New creates a new leaf node

func NewLeafNodeWithNoComms

func NewLeafNodeWithNoComms(stem Stem, 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) 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, []Stem, 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) 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   []Stem          // 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 (*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 Stem

type Stem []byte

func KeyToStem

func KeyToStem(key []byte) Stem

type StemStateDiff

type StemStateDiff struct {
	Stem        [StemSize]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) 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, []Stem, 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)

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

	// 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, []Stem, error)

	// 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. 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            [][StemSize]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

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL