trie

package
v0.8.4 Latest Latest
Warning

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

 Go to latest Published: Apr 29, 2024 License: Apache-2.0 Imports: 10 Imported by: 6

Documentation

Index

Constants

View Source 
const NodeKeyValidBytes = 31

NodeKeyValidBytes is the number of least significant bytes in the node key that are considered valid to addressing the leaf node, and thus limits the maximum trie depth to NodeKeyValidBytes * 8. We need to truncate the node key because the key is the output of Poseidon hash and the key space doesn't fully occupy the range of power of two. It can lead to an ambiguous bit representation of the key in the finite field causing a soundness issue in the zk circuit.

Variables

View Source 
var (
	// ErrNodeKeyAlreadyExists is used when a node key already exists.
	ErrInvalidField = errors.New("Key not inside the Finite Field")
	// ErrNodeKeyAlreadyExists is used when a node key already exists.
	ErrNodeKeyAlreadyExists = errors.New("key already exists")
	// ErrKeyNotFound is used when a key is not found in the ZkTrieImpl.
	ErrKeyNotFound = errors.New("key not found in ZkTrieImpl")
	// ErrNodeBytesBadSize is used when the data of a node has an incorrect
	// size and can't be parsed.
	ErrNodeBytesBadSize = errors.New("node data has incorrect size in the DB")
	// ErrReachedMaxLevel is used when a traversal of the MT reaches the
	// maximum level.
	ErrReachedMaxLevel = errors.New("reached maximum level of the merkle tree")
	// ErrInvalidNodeFound is used when an invalid node is found and can't
	// be parsed.
	ErrInvalidNodeFound = errors.New("found an invalid node in the DB")
	// ErrInvalidProofBytes is used when a serialized proof is invalid.
	ErrInvalidProofBytes = errors.New("the serialized proof is invalid")
	// ErrEntryIndexAlreadyExists is used when the entry index already
	// exists in the tree.
	ErrEntryIndexAlreadyExists = errors.New("the entry index already exists in the tree")
	// ErrNotWritable is used when the ZkTrieImpl is not writable and a
	// write function is called
	ErrNotWritable = errors.New("merkle Tree not writable")
)

Functions

func BuildZkTrieProof 

func BuildZkTrieProof(rootHash *zkt.Hash, k *big.Int, lvl int, getNode func(key *zkt.Hash) (*Node, error)) (*Proof,
	*Node, error)

BuildZkTrieProof prove uniformed way to turn some data collections into Proof struct

func LeafHash added in v0.5.0 

func LeafHash(k, v *zkt.Hash) (*zkt.Hash, error)

LeafHash computes the key of a leaf node given the hIndex and hValue of the entry of the leaf.

func ProofMagicBytes 

func ProofMagicBytes() []byte

func VerifyProofZkTrie 

func VerifyProofZkTrie(rootHash *zkt.Hash, proof *Proof, node *Node) bool

VerifyProof verifies the Merkle Proof for the entry and root. nodeHash can be nil when try to verify a nonexistent proof

Types

type Database 

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

func NewZkTrieMemoryDb 

func NewZkTrieMemoryDb() *Database

func (*Database) Get added in v0.1.1 

func (db *Database) Get(key []byte) ([]byte, error)

func (*Database) Init 

func (db *Database) Init(k, v []byte)

Init flush db with batches of k/v without locking

func (*Database) Put added in v0.1.1 

func (db *Database) Put(k, v []byte) error

func (*Database) UpdatePreimage added in v0.1.1 

func (db *Database) UpdatePreimage([]byte, *big.Int)

type Node 

type Node struct {
	// Type is the type of node in the tree.
	Type NodeType
	// ChildL is the node hash of the left child of a parent node.
	ChildL *zkt.Hash
	// ChildR is the node hash of the right child of a parent node.
	ChildR *zkt.Hash
	// NodeKey is the node's key stored in a leaf node.
	NodeKey *zkt.Hash
	// ValuePreimage can store at most 256 byte32 as fields (represnted by BIG-ENDIAN integer)
	// and the first 24 can be compressed (each bytes32 consider as 2 fields), in hashing the compressed
	// elemments would be calculated first
	ValuePreimage []zkt.Byte32
	// CompressedFlags use each bit for indicating the compressed flag for the first 24 fields
	CompressedFlags uint32

	// KeyPreimage is the original key value that derives the NodeKey, kept here only for proof
	KeyPreimage *zkt.Byte32
	// contains filtered or unexported fields
}

Node is the struct that represents a node in the MT. The node should not be modified after creation because the cached key won't be updated.

func DecodeSMTProof 

func DecodeSMTProof(data []byte) (*Node, error)

DecodeProof try to decode a node bytes, return can be nil for any non-node data (magic code)

func NewEmptyNode added in v0.5.0 

func NewEmptyNode() *Node

NewEmptyNode creates a new empty node.

func NewLeafNode added in v0.5.0 

func NewLeafNode(k *zkt.Hash, valueFlags uint32, valuePreimage []zkt.Byte32) *Node

NewLeafNode creates a new leaf node.

func NewNodeFromBytes 

func NewNodeFromBytes(b []byte) (*Node, error)

NewNodeFromBytes creates a new node by parsing the input []byte.

func NewParentNode added in v0.5.0 

func NewParentNode(ntype NodeType, childL *zkt.Hash, childR *zkt.Hash) *Node

NewParentNode creates a new parent node.

func (*Node) CanonicalValue added in v0.3.1 

func (n *Node) CanonicalValue() []byte

CanonicalValue returns the byte form of a node required to be persisted, and strip unnecessary fields from the encoding (current only KeyPreimage for Leaf node) to keep a minimum size for content being stored in backend storage

func (*Node) Copy added in v0.8.1 

func (n *Node) Copy() *Node

Copy creates a new Node instance from the given node

func (*Node) Data 

func (n *Node) Data() []byte

Data returns the wrapped data inside LeafNode and cast them into bytes for other node type it just return nil

func (*Node) IsTerminal added in v0.6.0 

func (n *Node) IsTerminal() bool

IsTerminal returns if the node is 'terminated', i.e. empty or leaf node

func (*Node) NodeHash added in v0.5.0 

func (n *Node) NodeHash() (*zkt.Hash, error)

NodeHash computes the hash digest of the node by hashing the content in a specific way for each type of node. This key is used as the hash of the Merkle tree for each node.

func (*Node) String 

func (n *Node) String() string

String outputs a string representation of a node (different for each type).

func (*Node) Value 

func (n *Node) Value() []byte

Value returns the encoded bytes of a node, include all information of it

func (*Node) ValueHash added in v0.5.0 

func (n *Node) ValueHash() (*zkt.Hash, error)

ValueHash computes the hash digest of the value stored in the leaf node. For other node types, it returns the zero hash.

type NodeAux 

type NodeAux struct {
	Key   *zkt.Hash // Key is the node key
	Value *zkt.Hash // Value is the value hash in the node
}

NodeAux contains the auxiliary node used in a non-existence proof.

type NodeType 

type NodeType byte

NodeType defines the type of node in the MT. 

const (
	// NodeTypeParent indicates the type of parent Node that has children.
	NodeTypeParent NodeType = 0
	// NodeTypeLeaf indicates the type of a leaf Node that contains a key &
	// value.
	NodeTypeLeaf NodeType = 1
	// NodeTypeEmpty indicates the type of an empty Node.
	NodeTypeEmpty NodeType = 2

	// DBEntryTypeRoot indicates the type of a DB entry that indicates the
	// current Root of a MerkleTree
	DBEntryTypeRoot NodeType = 3

	NodeTypeLeaf_New  NodeType = 4
	NodeTypeEmpty_New NodeType = 5
	// branch node for both child are terminal nodes
	NodeTypeBranch_0 NodeType = 6
	// branch node for left child is terminal node and right child is branch
	NodeTypeBranch_1 NodeType = 7
	// branch node for left child is branch node and right child is terminal
	NodeTypeBranch_2 NodeType = 8
	// branch node for both child are branch nodes
	NodeTypeBranch_3 NodeType = 9
)

func (NodeType) DeduceDowngradeType added in v0.6.0 

func (n NodeType) DeduceDowngradeType(atRight bool) NodeType

DeduceDowngradeType deduce a new branch type from current branch when one of its child become terminal

func (NodeType) DeduceUpgradeType added in v0.6.0 

func (n NodeType) DeduceUpgradeType(goRight bool) NodeType

DeduceUploadType deduce a new branch type from current branch when one of its child become non-terminal

type Proof 

type Proof struct {
	// existence indicates wether this is a proof of existence or
	// non-existence.
	Existence bool

	// Siblings is a list of non-empty sibling node hashes.
	Siblings []*zkt.Hash
	// NodeInfos is a list of nod types along mpt path
	NodeInfos []NodeType
	// NodeKey record the key of node and path
	NodeKey *zkt.Hash
	// NodeAux contains the auxiliary information of the lowest common ancestor
	// node in a non-existence proof.
	NodeAux *NodeAux
	// contains filtered or unexported fields
}

Proof defines the required elements for a MT proof of existence or non-existence.

func (*Proof) Verify 

func (proof *Proof) Verify(nodeHash *zkt.Hash) (*zkt.Hash, error)

Verify the proof and calculate the root, nodeHash can be nil when try to verify a nonexistent proof

type ZkTrie 

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

ZkTrie wraps a trie with key hashing. In a secure trie, all access operations hash the key using keccak256. This prevents calling code from creating long chains of nodes that increase the access time.

Contrary to a regular trie, a ZkTrie can only be created with New and must have an attached database. The database also stores the preimage of each key.

ZkTrie is not safe for concurrent use.

func NewZkTrie 

func NewZkTrie(root zkt.Byte32, db ZktrieDatabase) (*ZkTrie, error)

NewSecure creates a trie SecureBinaryTrie bypasses all the buffer mechanism in *Database, it directly uses the underlying diskdb

func (*ZkTrie) Commit added in v0.8.1 

func (t *ZkTrie) Commit() error

Commit flushes the trie to database

func (*ZkTrie) Copy 

func (t *ZkTrie) Copy() *ZkTrie

Copy returns a copy of SecureBinaryTrie.

func (*ZkTrie) Hash 

func (t *ZkTrie) Hash() []byte

Hash returns the root hash of SecureBinaryTrie. It does not write to the database and can be used even if the trie doesn't have one.

func (*ZkTrie) Prove 

func (t *ZkTrie) Prove(key []byte, fromLevel uint, writeNode func(*Node) error) error

Prove is a simlified calling of ProveWithDeletion

func (*ZkTrie) ProveWithDeletion added in v0.5.1 

func (t *ZkTrie) ProveWithDeletion(key []byte, fromLevel uint, writeNode func(*Node) error, onHit func(*Node, *Node)) error

ProveWithDeletion constructs a merkle proof for key. The result contains all encoded nodes on the path to the value at key. The value itself is also included in the last node and can be retrieved by verifying the proof.

If the trie does not contain a value for key, the returned proof contains all nodes of the longest existing prefix of the key (at least the root node), ending with the node that proves the absence of the key.

If the trie contain value for key, the onHit is called BEFORE writeNode being called, both the hitted leaf node and its sibling node is provided as arguments so caller would receive enough information for launch a deletion and calculate the new root base on the proof data Also notice the sibling can be nil if the trie has only one leaf

func (*ZkTrie) Tree 

func (t *ZkTrie) Tree() *ZkTrieImpl

Tree exposed underlying ZkTrieImpl

func (*ZkTrie) TryDelete 

func (t *ZkTrie) TryDelete(key []byte) error

TryDelete removes any existing value for key from the trie. If a node was not found in the database, a MissingNodeError is returned.

func (*ZkTrie) TryGet 

func (t *ZkTrie) TryGet(key []byte) ([]byte, error)

TryGet returns the value for key stored in the trie. The value bytes must not be modified by the caller. If a node was not found in the database, a MissingNodeError is returned.

func (*ZkTrie) TryGetNode 

func (t *ZkTrie) TryGetNode(path []byte) ([]byte, int, error)

TryGetNode attempts to retrieve a trie node by compact-encoded path. It is not possible to use keybyte-encoding as the path might contain odd nibbles.

func (*ZkTrie) TryUpdate 

func (t *ZkTrie) TryUpdate(key []byte, vFlag uint32, vPreimage []zkt.Byte32) error

TryUpdate associates key with value in the trie. Subsequent calls to Get will return value. If value has length zero, any existing value is deleted from the trie and calls to Get will return nil.

The value bytes must not be modified by the caller while they are stored in the trie.

If a node was not found in the database, a MissingNodeError is returned.

NOTE: value is restricted to length of bytes32.

type ZkTrieImpl 

type ZkTrieImpl struct {
	Debug bool
	// contains filtered or unexported fields
}

ZkTrieImpl is the struct with the main elements of the ZkTrieImpl

func NewZkTrieImpl 

func NewZkTrieImpl(storage ZktrieDatabase, maxLevels int) (*ZkTrieImpl, error)

func NewZkTrieImplWithRoot 

func NewZkTrieImplWithRoot(storage ZktrieDatabase, root *zkt.Hash, maxLevels int) (*ZkTrieImpl, error)

NewZkTrieImplWithRoot loads a new ZkTrieImpl. If in the storage already exists one will open that one, if not, will create a new one.

func (*ZkTrieImpl) Commit added in v0.8.1 

func (mt *ZkTrieImpl) Commit() error

Commit calculates the root for the entire trie and persist all the dirty nodes

func (*ZkTrieImpl) Copy added in v0.8.1 

func (mt *ZkTrieImpl) Copy() *ZkTrieImpl

Copy creates a new independent zkTrie from the given trie

func (*ZkTrieImpl) GetLeafNode added in v0.2.0 

func (mt *ZkTrieImpl) GetLeafNode(nodeKey *zkt.Hash) (*Node, error)

GetLeafNode is more underlying method than TryGet, which obtain an leaf node or nil if not exist

func (*ZkTrieImpl) GetNode 

func (mt *ZkTrieImpl) GetNode(nodeHash *zkt.Hash) (*Node, error)

GetNode gets a node by node hash from the MT. Empty nodes are not stored in the tree; they are all the same and assumed to always exist. <del>for non exist key, return (NewEmptyNode(), nil)</del>

func (*ZkTrieImpl) GraphViz 

func (mt *ZkTrieImpl) GraphViz(w io.Writer, rootHash *zkt.Hash) error

GraphViz uses Walk function to generate a string GraphViz representation of the tree and writes it to w

func (*ZkTrieImpl) MaxLevels 

func (mt *ZkTrieImpl) MaxLevels() int

MaxLevels returns the MT maximum level

func (*ZkTrieImpl) Prove added in v0.8.2 

func (mt *ZkTrieImpl) Prove(kHash *zkt.Hash, fromLevel uint, writeNode func(*Node) error) error

Prove constructs a merkle proof for SMT, it respect the protocol used by the ethereum-trie but save the node data with a compact form

func (*ZkTrieImpl) Root 

func (mt *ZkTrieImpl) Root() (*zkt.Hash, error)

Root returns the MerkleRoot

func (*ZkTrieImpl) TryDelete 

func (mt *ZkTrieImpl) TryDelete(nodeKey *zkt.Hash) error

Delete removes the specified Key from the ZkTrieImpl and updates the path from the deleted key to the Root with the new values. This method removes the key from the ZkTrieImpl, but does not remove the old nodes from the key-value database; this means that if the tree is accessed by an old Root where the key was not deleted yet, the key will still exist. If is desired to remove the key-values from the database that are not under the current Root, an option could be to dump all the leafs (using mt.DumpLeafs) and import them in a new ZkTrieImpl in a new database (using mt.ImportDumpedLeafs), but this will lose all the Root history of the ZkTrieImpl

func (*ZkTrieImpl) TryGet 

func (mt *ZkTrieImpl) TryGet(nodeKey *zkt.Hash) ([]byte, error)

TryGet returns the value for key stored in the trie. The value bytes must not be modified by the caller. If a node was not found in the database, a MissingNodeError is returned.

func (*ZkTrieImpl) TryUpdate 

func (mt *ZkTrieImpl) TryUpdate(nodeKey *zkt.Hash, vFlag uint32, vPreimage []zkt.Byte32) error

TryUpdate updates a nodeKey & value into the ZkTrieImpl. Where the `k` determines the path from the Root to the Leaf. This also return the updated leaf node

func (*ZkTrieImpl) Walk 

func (mt *ZkTrieImpl) Walk(rootHash *zkt.Hash, f func(*Node)) error

Walk iterates over all the branches of a ZkTrieImpl with the given rootHash if rootHash is nil, it will get the current RootHash of the current state of the ZkTrieImpl. For each node, it calls the f function given in the parameters. See some examples of the Walk function usage in the ZkTrieImpl.go and merkletree_test.go

type ZktrieDatabase 

type ZktrieDatabase interface {
	UpdatePreimage(preimage []byte, hashField *big.Int)
	Put(k, v []byte) error
	Get(key []byte) ([]byte, error)
}

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.