Documentation
¶
Index ¶
- Variables
- func BuildZkTrieProof(rootKey *zkt.Hash, k *big.Int, lvl int, ...) (*Proof, *Node, error)
- func LeafKey(k, v *zkt.Hash) (*zkt.Hash, error)
- func ProofMagicBytes() []byte
- func VerifyProofZkTrie(rootKey *zkt.Hash, proof *Proof, node *Node) bool
- type Database
- type Node
- type NodeAux
- type NodeType
- type Proof
- type ZkTrie
- func (t *ZkTrie) Copy() *ZkTrie
- func (t *ZkTrie) Hash() []byte
- func (t *ZkTrie) Prove(key []byte, fromLevel uint, writeNode func(*Node) error) error
- func (t *ZkTrie) Tree() *ZkTrieImpl
- func (t *ZkTrie) TryDelete(key []byte) error
- func (t *ZkTrie) TryGet(key []byte) ([]byte, error)
- func (t *ZkTrie) TryGetNode(path []byte) ([]byte, int, error)
- func (t *ZkTrie) TryUpdate(key []byte, vFlag uint32, vPreimage []zkt.Byte32) error
- type ZkTrieImpl
- func (mt *ZkTrieImpl) GetLeafNode(key *zkt.Hash) (*Node, error)
- func (mt *ZkTrieImpl) GetNode(key *zkt.Hash) (*Node, error)
- func (mt *ZkTrieImpl) GraphViz(w io.Writer, rootKey *zkt.Hash) error
- func (mt *ZkTrieImpl) MaxLevels() int
- func (mt *ZkTrieImpl) PrintGraphViz(rootKey *zkt.Hash) error
- func (mt *ZkTrieImpl) Root() *zkt.Hash
- func (mt *ZkTrieImpl) TryDelete(kHash *zkt.Hash) error
- func (mt *ZkTrieImpl) TryGet(kHash *zkt.Hash) ([]byte, error)
- func (mt *ZkTrieImpl) TryUpdate(kHash *zkt.Hash, vFlag uint32, vPreimage []zkt.Byte32) error
- func (mt *ZkTrieImpl) Walk(rootKey *zkt.Hash, f func(*Node)) error
- type ZktrieDatabase
Constants ¶
This section is empty.
Variables ¶
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(rootKey *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 LeafKey ¶
LeafKey computes the key of a leaf node given the hIndex and hValue of the entry of the leaf.
func ProofMagicBytes ¶
func ProofMagicBytes() []byte
Types ¶
type Database ¶
type Database struct {
// contains filtered or unexported fields
}
func NewZkTrieMemoryDb ¶
func NewZkTrieMemoryDb() *Database
type Node ¶
type Node struct {
// Type is the type of node in the tree.
Type NodeType
// ChildL is the left child of a middle node.
ChildL *zkt.Hash
// ChildR is the right child of a middle 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 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 ¶
DecodeProof try to decode a node bytes, return can be nil for any non-node data (magic code)
func NewNodeFromBytes ¶
NewNodeFromBytes creates a new node by parsing the input []byte.
func NewNodeLeaf ¶
NewNodeLeaf creates a new leaf node.
func NewNodeMiddle ¶
NewNodeMiddle creates a new middle node.
func (*Node) CanonicalValue ¶ added in v0.3.1
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) Data ¶
Data returns the wrapped data inside LeafNode and cast them into bytes for other node type it just return nil
func (*Node) Key ¶
Key computes the key 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 merklee tree for each node.
type NodeType ¶
type NodeType byte
NodeType defines the type of node in the MT.
const ( // NodeTypeMiddle indicates the type of middle Node that has children. NodeTypeMiddle 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 )
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 keys.
Siblings []*zkt.Hash
// Key is the key of leaf in existence case
Key *zkt.Hash
NodeAux *NodeAux
// contains filtered or unexported fields
}
Proof defines the required elements for a MT proof of existence or non-existence.
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) Hash ¶
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 ¶
Prove 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.
func (*ZkTrie) TryDelete ¶
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 ¶
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 ¶
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 ¶
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) GetLeafNode ¶ added in v0.2.0
func (mt *ZkTrieImpl) GetLeafNode(key *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(key *zkt.Hash) (*Node, error)
GetNode gets a node by key 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 (NewNodeEmpty(), nil)</del>
func (*ZkTrieImpl) GraphViz ¶
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) PrintGraphViz ¶
func (mt *ZkTrieImpl) PrintGraphViz(rootKey *zkt.Hash) error
PrintGraphViz prints directly the GraphViz() output
func (*ZkTrieImpl) TryDelete ¶
func (mt *ZkTrieImpl) TryDelete(kHash *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(kHash *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 ¶
tryUpdate update a Key & 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(rootKey *zkt.Hash, f func(*Node)) error
Walk iterates over all the branches of a ZkTrieImpl with the given rootKey if rootKey is nil, it will get the current RootKey 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
Source Files