merkledb

README

merkledb

Binary merkle tree database, backed by leveldb. Built to persist ZTYP SSZ data structures.

This library is under development, and not quite optimized.

The main idea is to hit the DB as few times as possible, while still structuring it as a binary tree without duplicates.

• Lookups for a specific node do not require iteration from the top-node, the generalized index can be used to select a range of all known nodes at a specific position.
• The DB returns virtual nodes; to lazy-load the children nodes
• Puts of nodes with children are transformed into batch-writes before writing to the db

Keys have:

• a 3-byte namespace prefix, since leveldb doesn't have tables
• a generalized index, big-endian, length prefixed. This groups adjacent/parent nodes close together, and enables smarter iteration.
• 32 bytes of the node itself

Values have:

• a 1-byte type prefix, to distinguish single-node (0: Root) and pair-node (1: PairNode) Node types.
• an 8-byte little-endian slot value, to track when the node was inserted
• if a pair-node: 32 byte left node key, then 32 byte right node key

License

MIT, see LICENSE file.

Documentation

Index

• type MerkleDB
  • func New(prefix [prefixLen]byte, db *leveldb.DB) MerkleDB
• type SlottedNode
• type VirtualNode
  • func NewVirtualNode(db MerkleDB, gindex Gindex, key Root, left Root, right Root) VirtualNode

Types

type MerkleDB

type MerkleDB interface {
	// Put a node and its subtree in the DB
	Put(slot uint64, node Node, fn HashFn) error
	// Get a node from the DB
	Get(gindex Gindex, key Root) (SlottedNode, error)
	// Has the node or not
	Has(gindex Gindex, key Root) (bool, error)
	// Delete the node at (gindex, key), does not remove any subtree
	Delete(gindex Gindex, key Root) error
	// Range retrieval of slotted values from the DB, between startSlot and endSlot, at the given gindex.
	// There may be multiple nodes per slot.
	Range(startSlot uint64, endSlot uint64, gindex Gindex) ([]SlottedNode, error)
}

func New

func New(prefix [prefixLen]byte, db *leveldb.DB) MerkleDB

Wrap the database with a binary-tree merkle interface.

type SlottedNode

type SlottedNode struct {
	Slot uint64
	Node Node
}

type VirtualNode

type VirtualNode interface {
	Node
	Detach() error
}

func NewVirtualNode

func NewVirtualNode(db MerkleDB, gindex Gindex, key Root, left Root, right Root) VirtualNode