binprefix

package
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Apr 10, 2024 License: BSD-3-Clause Imports: 12 Imported by: 2

Documentation

Overview

Package binprefix implements the hash tree interface by following the merkle binary prefix tree algorithm.

https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-melara.pdf

The merkle tree is stored in-memory until it reaches a certain threshold of depth where it will write the nodes in disk. A leaf is always stored on disk because of the value it holds. 

	         Interior (Root)
	           /        \
	        0 /          \ 1
	         /            \
	      Interior       Interior
	       /    \          /   \
	    0 /      \ 1    0 /     \ 1
	     /        \      /       \
	DiskNode  Interior  Empty   Interior
	            /   \             /    \
 --------------/-----\-----------/------\----------- Memory Depth
              / 0     \ 1     0 /        \ 1
             /         \       /          \
        DiskNode   DiskNode  DiskNode   DiskNode

The drawing above demonstrates an example of a tree. Here the memory depth is set at 3 which means that every node after this level will be a disk node. It will be loaded to its in-memory type when traversing the tree. The node at prefix 00 is an example of a leaf node which is a disk node even above the memory depth level.

Documentation Last Review: 08.10.2020

Index

Constants

View Source 
const (
	// DepthLength is the length in bytes of the binary representation of the
	// depth.
	DepthLength = 2

	// MaxDepth is the maximum depth the tree should reach. It is equivalent to
	// the maximum key length in bytes.
	MaxDepth = 32
)

Variables

This section is empty.

Functions

This section is empty.

Types

type DiskNode 

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

DiskNode is an implementation of a tree node which is stored on the disk.

- implements binprefix.TreeNode

func NewDiskNode 

func NewDiskNode(depth uint16, hash []byte, ctx serde.Context, factory serde.Factory) *DiskNode

NewDiskNode creates a new disk node.

func (*DiskNode) Clone 

func (n *DiskNode) Clone() TreeNode

Clone implements binprefix.TreeNode. It clones the disk node but both the old and the new will read the same bucket.

func (*DiskNode) Delete 

func (n *DiskNode) Delete(key *big.Int, bucket kv.Bucket) (TreeNode, error)

Delete implements binprefix.TreeNode. It loads the node and deletes the key if it exists. The whole path to the key is loaded in-memory until the tree is persisted.

func (*DiskNode) GetHash 

func (n *DiskNode) GetHash() []byte

GetHash implements binprefix.TreeNode. It returns the hash of the disk node if it is set, otherwise it returns nil.

func (*DiskNode) GetType 

func (n *DiskNode) GetType() byte

GetType returns the type of the node.

func (*DiskNode) Insert 

func (n *DiskNode) Insert(key *big.Int, value []byte, bucket kv.Bucket) (TreeNode, error)

Insert implements binprefix.TreeNode. It loads the node and inserts the key/value pair using in-memory operations. The whole path to the key will be loaded and kept in-memory until the tree is persisted.

func (*DiskNode) Prepare 

func (n *DiskNode) Prepare(nonce []byte, prefix *big.Int,
	bucket kv.Bucket, fac crypto.HashFactory) ([]byte, error)

Prepare implements binprefix.TreeNode. It loads the node and calculates its hash. The subtree might be loaded in-memory if deeper hashes have not been computed yet.

func (*DiskNode) Search 

func (n *DiskNode) Search(key *big.Int, path *Path, bucket kv.Bucket) ([]byte, error)

Search implements binprefix.TreeNode. It loads the disk node and then search for the key.

func (*DiskNode) Serialize 

func (n *DiskNode) Serialize(ctx serde.Context) ([]byte, error)

Serialize implements serde.Message. It always returns an error as a disk node cannot be serialized.

func (*DiskNode) Visit 

func (n *DiskNode) Visit(fn func(TreeNode) error) error

Visit implements binprefix.TreeNode.

type EmptyNode 

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

EmptyNode is leaf node with no value.

- implements binprefix.TreeNode

func NewEmptyNode 

func NewEmptyNode(depth uint16, key *big.Int) *EmptyNode

NewEmptyNode creates a new empty node.

func NewEmptyNodeWithDigest 

func NewEmptyNodeWithDigest(depth uint16, key *big.Int, hash []byte) *EmptyNode

NewEmptyNodeWithDigest creates a new empty node with its digest.

func (*EmptyNode) Clone 

func (n *EmptyNode) Clone() TreeNode

Clone implements binprefix.TreeNode. It returns a deep copy of the empty node.

func (*EmptyNode) Delete 

func (n *EmptyNode) Delete(key *big.Int, b kv.Bucket) (TreeNode, error)

Delete implements binprefix.TreeNode. It ignores the delete as an empty node already means the key is missing.

func (*EmptyNode) GetDepth 

func (n *EmptyNode) GetDepth() uint16

GetDepth returns the depth of the node.

func (*EmptyNode) GetHash 

func (n *EmptyNode) GetHash() []byte

GetHash implements binprefix.TreeNode. It returns the hash of the node.

func (*EmptyNode) GetPrefix 

func (n *EmptyNode) GetPrefix() *big.Int

GetPrefix returns the prefix of the node.

func (*EmptyNode) GetType 

func (n *EmptyNode) GetType() byte

GetType implements binprefix.TreeNode. It returns the empty node type.

func (*EmptyNode) Insert 

func (n *EmptyNode) Insert(key *big.Int, value []byte, b kv.Bucket) (TreeNode, error)

Insert implements binprefix.TreeNode. It replaces the empty node by a leaf node that contains the key and the value.

func (*EmptyNode) Prepare 

func (n *EmptyNode) Prepare(
	nonce []byte,
	prefix *big.Int, b kv.Bucket, fac crypto.HashFactory,
) ([]byte, error)

Prepare implements binprefix.TreeNode. It updates the hash of the node if not already set and returns the digest.

func (*EmptyNode) Search 

func (n *EmptyNode) Search(key *big.Int, path *Path, b kv.Bucket) ([]byte, error)

Search implements binprefix.TreeNode. It always return a empty value.

func (*EmptyNode) Serialize 

func (n *EmptyNode) Serialize(ctx serde.Context) ([]byte, error)

Serialize implements serde.Message. It returns the JSON data of the empty node.

func (*EmptyNode) Visit 

func (n *EmptyNode) Visit(fn func(node TreeNode) error) error

Visit implements binprefix.TreeNode. It executes the callback with the node.

type EmptyNodeJSON 

type EmptyNodeJSON struct {
	Digest []byte
	Depth  uint16
	Prefix []byte
}

EmptyNodeJSON is the JSON representation of an empty node.

type InteriorNode 

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

InteriorNode is a node with two children.

- implements binprefix.TreeNode

func NewInteriorNode 

func NewInteriorNode(depth uint16, prefix *big.Int) *InteriorNode

NewInteriorNode creates a new interior node with two empty nodes as children.

func NewInteriorNodeWithChildren 

func NewInteriorNodeWithChildren(
	depth uint16,
	prefix *big.Int,
	hash []byte,
	left, right TreeNode,
) *InteriorNode

NewInteriorNodeWithChildren creates a new interior node with the two given children.

func (*InteriorNode) Clone 

func (n *InteriorNode) Clone() TreeNode

Clone implements binprefix.TreeNode. It returns a deep copy of the interior node.

func (*InteriorNode) Delete 

func (n *InteriorNode) Delete(key *big.Int, b kv.Bucket) (TreeNode, error)

Delete implements binprefix.TreeNode. It deletes the leaf node associated to the key if it exists, otherwise nothing will change.

func (*InteriorNode) GetDepth 

func (n *InteriorNode) GetDepth() uint16

GetDepth returns the depth of the node.

func (*InteriorNode) GetHash 

func (n *InteriorNode) GetHash() []byte

GetHash implements binprefix.TreeNode. It returns the hash of the node.

func (*InteriorNode) GetPrefix 

func (n *InteriorNode) GetPrefix() *big.Int

GetPrefix returns the prefix of the node.

func (*InteriorNode) GetType 

func (n *InteriorNode) GetType() byte

GetType implements binprefix.TreeNode. It returns the interior node type.

func (*InteriorNode) Insert 

func (n *InteriorNode) Insert(key *big.Int, value []byte, b kv.Bucket) (TreeNode, error)

Insert implements binprefix.TreeNode. It inserts the key/value pair to the right path.

func (*InteriorNode) Prepare 

func (n *InteriorNode) Prepare(
	nonce []byte,
	prefix *big.Int, b kv.Bucket, fac crypto.HashFactory,
) ([]byte, error)

Prepare implements binprefix.TreeNode. It updates the hash of the node if not already set and returns the digest.

func (*InteriorNode) Search 

func (n *InteriorNode) Search(key *big.Int, path *Path, b kv.Bucket) ([]byte, error)

Search implements binprefix.TreeNode. It recursively search for the value in the correct child.

func (*InteriorNode) Serialize 

func (n *InteriorNode) Serialize(ctx serde.Context) ([]byte, error)

Serialize implements serde.Message. It returns the JSON data of the interior node.

func (*InteriorNode) Visit 

func (n *InteriorNode) Visit(fn func(TreeNode) error) error

Visit implements binprefix.TreeNode. It executes the callback with the node and recursively with the children.

type InteriorNodeJSON 

type InteriorNodeJSON struct {
	Digest []byte
	Depth  uint16
	Prefix []byte
}

InteriorNodeJSON is the JSON representation of an interior node.

type LeafNode 

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

LeafNode is a leaf node with a key and a value.

- implements binprefix.TreeNode

func NewLeafNode 

func NewLeafNode(depth uint16, key *big.Int, value []byte) *LeafNode

NewLeafNode creates a new leaf node.

func NewLeafNodeWithDigest 

func NewLeafNodeWithDigest(depth uint16, key *big.Int, value, hash []byte) *LeafNode

NewLeafNodeWithDigest creates a new leaf node with its digest.

func (*LeafNode) Clone 

func (n *LeafNode) Clone() TreeNode

Clone implements binprefix.TreeNode. It returns a copy of the leaf node.

func (*LeafNode) Delete 

func (n *LeafNode) Delete(key *big.Int, b kv.Bucket) (TreeNode, error)

Delete implements binprefix.TreeNode. It removes the leaf if the key matches.

func (*LeafNode) GetDepth 

func (n *LeafNode) GetDepth() uint16

GetDepth returns the depth of the node.

func (*LeafNode) GetHash 

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

GetHash implements binprefix.TreeNode. It returns the hash of the node.

func (*LeafNode) GetKey 

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

GetKey returns the key of the leaf node.

func (*LeafNode) GetType 

func (n *LeafNode) GetType() byte

GetType implements binprefix.TreeNode. It returns the leaf node type.

func (*LeafNode) GetValue 

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

GetValue returns the value of the leaf node.

func (*LeafNode) Insert 

func (n *LeafNode) Insert(key *big.Int, value []byte, b kv.Bucket) (TreeNode, error)

Insert implements binprefix.TreeNode. It replaces the leaf node by an interior node that contains both the current pair and the new one to insert.

func (*LeafNode) Prepare 

func (n *LeafNode) Prepare(
	nonce []byte,
	prefix *big.Int, b kv.Bucket, fac crypto.HashFactory,
) ([]byte, error)

Prepare implements binprefix.TreeNode. It updates the hash of the node if not already set and returns the digest.

func (*LeafNode) Search 

func (n *LeafNode) Search(key *big.Int, path *Path, b kv.Bucket) ([]byte, error)

Search implements binprefix.TreeNode. It returns the value if the key matches.

func (*LeafNode) Serialize 

func (n *LeafNode) Serialize(ctx serde.Context) ([]byte, error)

Serialize implements serde.Message. It returns the JSON data of the leaf node.

func (*LeafNode) Visit 

func (n *LeafNode) Visit(fn func(TreeNode) error) error

Visit implements binprefix.TreeNode. It executes the callback with the node.

type LeafNodeJSON 

type LeafNodeJSON struct {
	Digest []byte
	Depth  uint16
	Prefix []byte
	Value  []byte
}

LeafNodeJSON is the JSON representation of a leaf node.

type MerkleTree 

type MerkleTree struct {
	sync.Mutex
	// contains filtered or unexported fields
}

MerkleTree is an implementation of a Merkle prefix binary tree. This particular implementation assumes the keys will have the same length so that only the longest unique prefix along the path can be a leaf node.

The leafs of the tree will be stored on the disk when committing the tree. Modifications on a staged tree are done in-memory.

- implements hashtree.Tree

func NewMerkleTree 

func NewMerkleTree(db kv.DB, nonce Nonce) *MerkleTree

NewMerkleTree creates a new Merkle tree-based storage.

func (*MerkleTree) Commit 

func (t *MerkleTree) Commit() error

Commit implements hashtree.StagingTree. It writes the leaf nodes to the disk and a trade-off of other nodes.

func (*MerkleTree) Get 

func (t *MerkleTree) Get(key []byte) ([]byte, error)

Get implements store.Readable. It returns the value associated with the key if it exists, otherwise it returns nil.

func (*MerkleTree) GetPath 

func (t *MerkleTree) GetPath(key []byte) (hashtree.Path, error)

GetPath implements hashtree.Tree. It returns a path to a given key that can be used to prove the inclusion or the absence of a key.

func (*MerkleTree) GetRoot 

func (t *MerkleTree) GetRoot() []byte

GetRoot implements hashtree.Tree. It returns the root hash of the tree.

func (*MerkleTree) Load 

func (t *MerkleTree) Load() error

Load tries to read the bucket and scan it for existing leafs and populate the tree with them.

func (*MerkleTree) Stage 

func (t *MerkleTree) Stage(fn func(store.Snapshot) error) (hashtree.StagingTree, error)

Stage implements hashtree.Tree. It executes the callback over a clone of the current tree and returns the clone with the root calculated.

func (*MerkleTree) WithTx 

func (t *MerkleTree) WithTx(tx store.Transaction) hashtree.StagingTree

WithTx implements hashtree.StagingTree. It returns a tree that shares the same underlying data, but it will perform operations on the database through the transaction.

type NodeFactory 

type NodeFactory struct{}

NodeFactory is the factory to deserialize tree nodes.

- implements serde.Factory

func (NodeFactory) Deserialize 

func (f NodeFactory) Deserialize(ctx serde.Context, data []byte) (serde.Message, error)

Deserialize implements serde.Factory. It populates the tree node associated to the data if appropriate, otherwise it returns an error.

type NodeJSON 

type NodeJSON struct {
	Leaf     *LeafNodeJSON     `json:",omitempty"`
	Interior *InteriorNodeJSON `json:",omitempty"`
	Empty    *EmptyNodeJSON    `json:",omitempty"`
}

NodeJSON is the wrapper around the different types of a tree node.

type NodeKey 

type NodeKey struct{}

NodeKey is the key for the node factory.

type Nonce 

type Nonce [8]byte

Nonce is the type of the tree nonce.

type Path 

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

Path is a path from the root to a leaf, represented as a series of interior nodes hashes. The end of the path is either a leaf with a key holding a value, or an empty node.

- implements hashtree.Path

func (Path) GetKey 

func (s Path) GetKey() []byte

GetKey implements hashtree.Path. It returns the key associated to the path.

func (Path) GetRoot 

func (s Path) GetRoot() []byte

GetRoot implements hashtree.Path. It returns the hash of the root node calculated from the leaf up to the root.

func (Path) GetValue 

func (s Path) GetValue() []byte

GetValue implements hashtree.Path. It returns the value pointed by the path.

type Tree 

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

Tree is an implementation of a Merkle binary prefix tree. Due to the structure of the tree, any prefix of a longer prefix is overridden which means that the key should have the same length.

Mutable operations on the tree don't update the hash root. It can be done after a batch of operations or a single one by using the CalculateRoot function.

func NewTree 

func NewTree(nonce Nonce) *Tree

NewTree creates a new empty tree.

func (*Tree) CalculateRoot 

func (t *Tree) CalculateRoot(fac crypto.HashFactory, b kv.Bucket) error

CalculateRoot updates the hashes of the tree.

func (*Tree) Clone 

func (t *Tree) Clone() *Tree

Clone returns a deep copy of the tree.

func (*Tree) Delete 

func (t *Tree) Delete(key []byte, b kv.Bucket) error

Delete removes a key from the tree.

func (*Tree) FillFromBucket 

func (t *Tree) FillFromBucket(bucket kv.Bucket) error

FillFromBucket scans the bucket for leafs to insert them in the tree. It will then persist the tree to restore the memory depth limit.

func (*Tree) Insert 

func (t *Tree) Insert(key, value []byte, b kv.Bucket) error

Insert inserts the key in the tree.

func (*Tree) Len 

func (t *Tree) Len() int

Len returns the number of leaves in the tree.

func (*Tree) Persist 

func (t *Tree) Persist(b kv.Bucket) error

Persist visits the whole tree and stores the leaf node in the database and replaces the node with disk nodes. Depending on the parameter, it also stores intermediate nodes on the disk.

func (*Tree) Search 

func (t *Tree) Search(key []byte, path *Path, b kv.Bucket) ([]byte, error)

Search returns the value associated to the key if it exists, otherwise nil. When path is defined, it will be filled with the interior nodes and the leaf node so that it can prove the inclusion or the absence of the key.

type TreeNode 

type TreeNode interface {
	serde.Message

	GetHash() []byte

	GetType() byte

	Search(key *big.Int, path *Path, bucket kv.Bucket) ([]byte, error)

	Insert(key *big.Int, value []byte, bucket kv.Bucket) (TreeNode, error)

	Delete(key *big.Int, bucket kv.Bucket) (TreeNode, error)

	Prepare(nonce []byte, prefix *big.Int, bucket kv.Bucket, fac crypto.HashFactory) ([]byte, error)

	Visit(func(node TreeNode) error) error

	Clone() TreeNode
}

TreeNode is the interface for the different types of nodes of a Merkle tree.

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.