Struct HashTree 

pub struct HashTree { /* private fields */ }

An append-only RFC 6962 tree that holds hashes and nothing else.

It is fed leaf hashes, SHA-256(0x00 ‖ leaf-bytes) computed by whoever read the leaf, and never sees a leaf’s bytes: a log builds it by streaming its stored leaves through, one at a time, and extends it on append with the leaf hash it already computed, so no leaf is hashed twice.

Invariants

• Level h holds the root of every complete perfect subtree of height h, left to right: entry i is the hash of leaves i·2^h .. (i+1)·2^h. Level 0 is the leaf hashes. So a tree of n leaves holds 2n − popcount(n) hashes, fewer than two per leaf.
• Every RFC 6962 subtree MTH(D[a:b]) is either one of those perfect subtrees or the hash of a perfect left subtree and a smaller right one, so roots and proofs are computed from the stored hashes alone, and are byte-identical to a raw-leaf AppendOnlyTree’s over the same leaves.
• Nothing is removed or replaced: Self::push_leaf_hash is the only mutation.

Implementations

impl HashTree

pub fn new() -> Self

Builds a new empty tree.

pub fn with_capacity(leaves: u64) -> Self

Builds an empty tree with room for leaves leaves and their interior hashes, so a tree streamed to a known size allocates once per level and holds no spare capacity. A size beyond this target’s address space reserves nothing and the tree grows as it is fed.

pub fn len(&self) -> u64

Returns the number of leaves in the tree.

pub fn is_empty(&self) -> bool

Returns true if no leaf has been appended.

pub fn retained_bytes(&self) -> usize

The bytes of hash storage the tree holds, spare capacity included. Never more than two 32-byte hashes per leaf for a tree built by Self::with_capacity to its size.

pub fn push_leaf_hash(&mut self, leaf_hash: [u8; 32]) -> u64

Appends a leaf by its RFC 6962 leaf hash and returns the new tree size.

The new leaf completes one perfect subtree per trailing set bit of the old size; each is hashed once, here, and kept.

pub fn root(&self) -> TrustResult<RootHash>

Returns the current root hash with the current leaf count.

Errors

Returns TrustError::MerkleTree if a hash the tree must hold is missing, which only a broken invariant can cause.

pub fn prove_inclusion(&self, leaf_index: u64) -> TrustResult<InclusionProof>

Builds the RFC 6962 inclusion proof PATH(leaf_index, D[n]).

Errors

Returns TrustError::MerkleTree if leaf_index is not below the tree length, with the same reason AppendOnlyTree::prove_inclusion gives.

pub fn prove_consistency( &self, old_size: u64, new_size: u64, ) -> TrustResult<ConsistencyProof>

Builds the RFC 6962 consistency proof PROOF(old_size, D[new_size]).

Errors

Returns TrustError::MerkleTree unless 0 < old_size <= new_size and new_size is the tree length, with the same reasons AppendOnlyTree::prove_consistency gives.

Trait Implementations

impl Clone for HashTree

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for HashTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for HashTree

fn default() -> Self

Returns the “default value” for a type.