[][src]Crate ic_crypto_tree_hash

Re-exports

pub use flat_map::FlatMap;

Modules

flat_map

Introduces FlatMap structure, a sorted map with fast lookups and appends. It stores keys and values in vectors.

proto

Protocol buffer equivalents to LabeledTree<Vec<u8>> and Witness, for backwards- and forwards-compatible XNet wire format.

Macros

flatmap

Creates a FlatMap from a list of key => value pairs.

Structs

Digest

The computed hash of the data in a Leaf; or of a LabeledTree.

HashTreeBuilderImpl

An implementation of the HashTreeBuilder-trait.

Label

A blob used as a label in the tree.

Path

Represents a path (a collection of Label) in a hash tree.

WitnessGeneratorImpl

An implementation of the WitnessGenerator-trait.

Enums

HashTree

A binary tree representation of a LabeledTree, with Digest leaves.

InvalidHashTreeError

An error indicating that a hash tree doesn't correspond to a valid LabeledTree.

LabeledTree

A sorted, labeled rose tree whose leaves contain values of type T.

MixedHashTree

A hash tree that contains the data requested by the call to read_certified_state and digests for pruned parts of the hash tree.

TreeHashError

Errors occurring in tree_hash module.

Witness

A subset of a HashTree that is sufficient to verify whether some specific partial data is consistent with the original data (for which the HashTree was computed). In particular a Witness includes no digests for the partial data it verifies; nor for the HashTree root.

Traits

HashTreeBuilder

HashTreeBuilder enables an iterative construction of a LabeledTree, which can also be accessed in form of a HashTree. The constructed LabeledTree is a part of the state of the Builder, and is build successively by adding leaves and subtrees. During the construction, the builder maintains an auxiliary state that describes the current position in the LabeledTree under construction. The auxiliary state is a list of nodes that corresponds to the path in the tree from the root to the current node being constructed. An example code to build the following labeled tree with a sub-tree and three leaves:

WitnessGenerator

WitnessGenerator is a container for a HashTree that offers access to the contained tree, and also provides operations related to the tree, like for example the computation of Witness-objects.

Functions

first_sub_witness

Returns the leftmost direct labeled sub-witness, if any, and its label.

lookup_path

Descends into the subtree of t following the given path. Returns the reference to the corresponding subtree.

prune_witness

Prunes from witness the nodes in partial_tree. If partial_tree is inconsistent with witness, e.g. includes nodes not covered by witness; or attempts to prune a non-empty SubTree by providing an empty one; an error is returned.

recompute_digest

Computes and returns a digest for (partial) data given in partial_tree, using information from witness to compensate for the missing data in the tree. If partial_tree is inconsistent with 'witness', i.e. if witness does not contain enough information for digest-computation, an error is returned.

sparse_labeled_tree_from_paths

Converts a list of Paths into a sparse LabeledTree.

sub_witness

Returns the direct sub-witness with the given label, if present.