smt

Documentation

Overview

Package smt contains the implementation of the sparse Merkle tree logic.

Index

• func Prepare(nodes []Node, depth uint) error
• type HStar3
  • func NewHStar3(nodes []Node, hash HashChildrenFn, depth, top uint) (HStar3, error)
  • func (h HStar3) Prepare() []node.ID
  • func (h HStar3) Update(na NodeAccessor) ([]Node, error)
• type HashChildrenFn
• type Hasher
• type Layout
  • func NewLayout(heights []uint) Layout
  • func (l Layout) Locate(depth uint) (uint, uint)
• type Node
• type NodeAccessor
• type NodeBatchAccessor
• type NodesRow
  • func NewNodesRow(nodes []Node) (NodesRow, error)
• type Tile
  • func (t Tile) Merge(updates NodesRow) (Tile, error)
• type TileSet
  • func NewTileSet(treeID int64, hasher Hasher, layout Layout) *TileSet
  • func (t *TileSet) Add(tile Tile) error
  • func (t *TileSet) Hashes() map[node.ID][]byte
• type TileSetMutation
  • func NewTileSetMutation(ts *TileSet) *TileSetMutation
  • func (t *TileSetMutation) Build() ([]Tile, error)
  • func (t *TileSetMutation) Set(id node.ID, hash []byte)
• type Writer
  • func NewWriter(treeID int64, hasher Hasher, height, split uint) *Writer
  • func (w *Writer) Split(nodes []Node) ([][]Node, error)
  • func (w *Writer) Write(ctx context.Context, nodes []Node, acc NodeBatchAccessor) (Node, error)

Functions

func Prepare

func Prepare(nodes []Node, depth uint) error

Prepare sorts the nodes slice for it to be usable by HStar3 algorithm and the sparse Merkle tree Writer. It also verifies that the nodes are placed at the required depth, and there are no duplicate IDs.

TODO(pavelkalinnikov): Make this algorithm independent of Node type.

Types

type HStar3

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

HStar3 is a faster non-recursive HStar2.

func NewHStar3

func NewHStar3(nodes []Node, hash HashChildrenFn, depth, top uint) (HStar3, error)

NewHStar3 returns a new instance of HStar3 for the given set of node hash updates at the specified tree depth. This HStar3 is capable of propagating these updates up to the passed-in top level of the tree.

Warning: This call and other HStar3 methods modify the nodes slice in-place, so the caller must ensure to not reuse it.

func (HStar3) Prepare

func (h HStar3) Prepare() []node.ID

Prepare returns the list of all the node IDs that the Update method will load in order to compute node hash updates from the initial tree depth up to the top level specified in the constructor. The ordering of the returned IDs is arbitrary. This method may be useful for creating a NodeAccessor, e.g. by batch-reading the nodes from elsewhere.

TODO(pavelkalinnikov): Return only tile IDs.

func (HStar3) Update

func (h HStar3) Update(na NodeAccessor) ([]Node, error)

Update applies the updates to the sparse Merkle tree. Returns an error if any of the NodeAccessor.Get calls does so, e.g. if a node is undefined. Warning: HStar3 must not be used further after this call.

Returns the slice of updates at the top level of the sparse Merkle tree induced by the provided lower level updates. Typically it will contain only one item for the root hash of a tile or a (sub)tree, but the caller may arrange multiple subtrees in one HStar3, in which case the corresponding returned top-level updates will be sorted lexicographically by node ID.

Note that Update invocations can be chained. For example, a bunch of HStar3 instances at depth 256 can return updates for depth 8 (in parallel), which are then merged together and passed into another HStar3 at depth 8 which computes the overall tree root update.

For that reason, Update doesn't invoke NodeAccessor.Set for the topmost nodes. If it did then chained Updates would Set the borderline nodes twice.

type HashChildrenFn

type HashChildrenFn func(left, right []byte) []byte

HashChildrenFn computes a node hash based on its child nodes' hashes.

type Hasher

type Hasher interface {
	// HashEmpty returns the hash of an empty subtree with the given root. Note
	// that the empty node ID indicates the root of the entire tree.
	HashEmpty(treeID int64, root node.ID) []byte
	// HashChildren returns the node hash based on its children node hashes.
	HashChildren(l, r []byte) []byte
}

Hasher provides sparse Merkle tree hash functions.

type Layout

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

Layout defines the mapping between tree nodes and tiles.

The tree is divided into horizontal tiers of the heights specified in the constructor. The tiers are counted down from the tree root. Nodes located at the tier borders are roots of the corresponding tiles. A tile includes all the nodes strictly below the tile root, within a single tier.

func NewLayout

func NewLayout(heights []uint) Layout

NewLayout creates a tree layout based on the passed-in tier heights.

func (Layout) Locate

func (l Layout) Locate(depth uint) (uint, uint)

Locate returns the tier info that nodes at the given depth belong to. The first returned value is the depth of the root node, for any tile in this tier. The second value is the height of the tiles.

If depth is 0, or beyond the tree height, then the result is undefined.

type Node

type Node struct {
	ID   node.ID
	Hash []byte
}

Node represents a sparse Merkle tree node.

type NodeAccessor

type NodeAccessor interface {
	// Get returns the hash of the given node. Returns an error if the hash is
	// undefined, or can't be obtained for another reason.
	Get(id node.ID) ([]byte, error)
	// Set sets the hash of the given node.
	Set(id node.ID, hash []byte)
}

NodeAccessor provides read and write access to Merkle tree node hashes.

The Update algorithm uses it to read the existing nodes of the tree and write the nodes that are updated. The nodes that it writes do not intersect with the nodes that it reads.

type NodeBatchAccessor

type NodeBatchAccessor interface {
	// Get returns the hashes of the given nodes, as a map keyed by their IDs.
	// The returned hashes may be missing or be nil for empty subtrees.
	Get(ctx context.Context, ids []node.ID) (map[node.ID][]byte, error)
	// Set applies the given node hash updates.
	Set(ctx context.Context, nodes []Node) error
}

NodeBatchAccessor reads and writes batches of Merkle tree node hashes. It is a batch interface for efficiency reasons, as it is designed to guard tree storage / database access. The Writer type operates on a per-shard basis, i.e. it calls Get and Set method exactly once for each shard.

type NodesRow

type NodesRow []Node

NodesRow contains nodes at the same tree level sorted by ID from left to right. The IDs of the nodes are unique.

TODO(pavelkalinnikov): Hide nodes so that only this package can modify them.

func NewNodesRow

func NewNodesRow(nodes []Node) (NodesRow, error)

NewNodesRow creates a NodesRow from the given list of nodes. The nodes are reordered in-place if not already sorted.

type Tile

type Tile struct {
	ID     node.ID
	Leaves NodesRow
}

Tile represents a sparse Merkle tree tile, i.e. a dense set of tree nodes located under a single "root" node at a distance not exceeding the tile height. A tile is identified by the ID of its root node. The Tile struct contains the list of non-empty leaf nodes, which can be used to reconstruct all the remaining inner nodes of the tile.

Invariants of this structure that must be preserved at all times:

• ID is a prefix of Leaves' IDs, i.e. the nodes are in the same subtree.
• IDs of Leaves have the same length, i.e. the nodes are at the same level.
• Leaves are ordered by ID from left to right.
• IDs of Leaves are unique.

Algorithms that create Tile structures must ensure that these invariants hold. Use NewNodesRow function for ordering nodes correctly.

func (Tile) Merge

func (t Tile) Merge(updates NodesRow) (Tile, error)

Merge returns a new tile which is a combination of this tile with the given updates. The resulting tile contains all the nodes from the updates, and all the nodes from the original tile not present in the updates.

type TileSet

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

TileSet represents a set of Merkle tree tiles and the corresponding nodes. This type is not thread-safe.

TODO(pavelkalinnikov): Make it immutable.

func NewTileSet

func NewTileSet(treeID int64, hasher Hasher, layout Layout) *TileSet

NewTileSet creates an empty TileSet with the given tree parameters.

func (*TileSet) Add

func (t *TileSet) Add(tile Tile) error

Add puts the given tile into the set. Not thread-safe.

TODO(pavelkalinnikov): Take a whole list of Tiles instead.

func (*TileSet) Hashes

func (t *TileSet) Hashes() map[node.ID][]byte

Hashes returns a map containing all node hashes keyed by node IDs.

type TileSetMutation

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

TileSetMutation accumulates tree tiles that need to be updated. This type is not thread-safe.

func NewTileSetMutation

func NewTileSetMutation(ts *TileSet) *TileSetMutation

NewTileSetMutation creates a mutation which is based off the provided TileSet. This means that each modification is checked against the hashes in this set, and is applied if it does change the hash.

func (*TileSetMutation) Build

func (t *TileSetMutation) Build() ([]Tile, error)

Build returns the full set of tiles modified by this mutation.

func (*TileSetMutation) Set

func (t *TileSetMutation) Set(id node.ID, hash []byte)

Set updates the hash of the given tree node. Not thread-safe.

TODO(pavelkalinnikov): Elaborate on the expected order of Set calls. Currently, Build method sorts nodes to allow any order, but it can be avoided.

type Writer

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

Writer handles sharded writes to a sparse Merkle tree. The tree has two levels of shards: the single topmost shard spanning depths from 0 to split, and 2^split second-level shards each spanning levels from split to height. If the split height is 0 then effectively there is only one "global" shard.

func NewWriter

func NewWriter(treeID int64, hasher Hasher, height, split uint) *Writer

NewWriter creates a new Writer for the specified tree of the given height, with two levels of sharding, where the upper shard is `split` levels high.

func (*Writer) Split

func (w *Writer) Split(nodes []Node) ([][]Node, error)

Split sorts and splits the given list of node hash updates into shards, i.e. the subsets belonging to different subtrees. The nodes must belong to the same tree level which is equal to the tree height.

func (*Writer) Write

func (w *Writer) Write(ctx context.Context, nodes []Node, acc NodeBatchAccessor) (Node, error)

Write applies the given list of node updates to a single shard, and returns the resulting update of the shard root. It uses the given node accessor for reading and writing tree nodes.

The typical usage pattern is as follows. For the lower shards, the input is the []Node slices returned from the Split method. For the top shard, the input is all the Node values from the lower shards Write calls.

In another case, Write can be performed without Split if the shard split depth is 0, which effectively means that there is only one "global" shard.