Documentation
¶
Overview ¶
Package smt contains the implementation of the sparse Merkle tree logic.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
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 ¶
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 ¶
HashChildrenFn computes a node hash based on its child nodes' hashes.
type Hasher ¶ added in v1.4.0
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 ¶ added in v1.4.0
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 ¶ added in v1.4.0
NewLayout creates a tree layout based on the passed-in tier heights.
func (Layout) Locate ¶ added in v1.4.0
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 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 ¶ added in v1.3.9
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 ¶ added in v1.3.9
NewNodesRow creates a NodesRow from the given list of nodes. The nodes are reordered in-place if not already sorted.
type Tile ¶ added in v1.3.5
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.
type TileSet ¶ added in v1.3.6
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 ¶ added in v1.3.6
NewTileSet creates an empty TileSet with the given tree parameters.
type TileSetMutation ¶ added in v1.3.6
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 ¶ added in v1.3.6
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 ¶ added in v1.3.6
func (t *TileSetMutation) Build() ([]Tile, error)
Build returns the full set of tiles modified by this mutation.
func (*TileSetMutation) Set ¶ added in v1.3.6
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 ¶
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 ¶
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 ¶
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.
Source Files
Directories