package smt

import "github.com/google/trillian/merkle/smt"

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

Index ¶

• func Prepare(updates []NodeUpdate, depth uint) error
• type HStar3
• func NewHStar3(updates []NodeUpdate, hash HashChildrenFn, depth, top uint) (HStar3, error)
• func (h HStar3) Prepare() []tree.NodeID2
• func (h HStar3) Update(na NodeAccessor) ([]NodeUpdate, error)
• type HashChildrenFn
• type NodeAccessor
• type NodeBatchAccessor
• type NodeUpdate
• type Tile
• type Writer
• func NewWriter(treeID int64, hasher hashers.MapHasher, height, split uint) *Writer
• func (w *Writer) Split(upd []NodeUpdate) ([][]NodeUpdate, error)
• func (w *Writer) Write(ctx context.Context, upd []NodeUpdate, acc NodeBatchAccessor) (NodeUpdate, error)

Functions ¶

func Prepare ¶

func Prepare(updates []NodeUpdate, depth uint) error

Prepare sorts the updates 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 NodeUpdate type.

Types ¶

type HStar3 ¶

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

HStar3 is a faster non-recursive HStar2.

TODO(pavelkalinnikov): Swap in the code, and document it properly.

func NewHStar3 ¶

func NewHStar3(updates []NodeUpdate, 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 updates slice in-place, so the caller must ensure to not reuse it.

func (HStar3) Prepare ¶

func (h HStar3) Prepare() []tree.NodeID2

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) ([]NodeUpdate, 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 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 tree.NodeID2) ([]byte, error)
	// Set sets the hash of the given node.
	Set(id tree.NodeID2, 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 []tree.NodeID2) (map[tree.NodeID2][]byte, error)
	// Set applies the given node hash updates.
	Set(ctx context.Context, upd []NodeUpdate) 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 NodeUpdate ¶

type NodeUpdate struct {
	ID   tree.NodeID2
	Hash []byte
}

NodeUpdate represents an update of a node hash in a sparse Merkle tree.

type Tile ¶

type Tile struct {
	ID     tree.NodeID2
	Leaves []NodeUpdate
}

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.

TODO(pavelkalinnikov): Make Tile immutable. TODO(pavelkalinnikov): Introduce invariants on the order/content of Leaves. TODO(pavelkalinnikov): Rename NodeUpdate to a more generic Node or NodeHash.

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 hashers.MapHasher, 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(upd []NodeUpdate) ([][]NodeUpdate, error)

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

func (*Writer) Write ¶

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

Write applies the given list of 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 []NodeUpdate slices returned from the Split method. For the top shard, the input is all the NodeUpdates 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.

Source Files ¶

hasher.go hstar3.go tile.go updates.go writer.go