Interface MerkleTreeNodeSource

All Known Implementing Classes:
ListMerkleTreeNodeSource
public interface MerkleTreeNodeSource
Source of Merkle tree node hashes for the proof generators in MerkleTreePrimitives, backed by whatever a log or CA keeps its tree in.

The generators walk the tree in the recursive form of RFC 9162 Section 2.1 and the draft's Section 4.4.1, and every hash they need is either a full subtree - a range [start, end) whose size is a power of two and whose start is a multiple of that size, MTH(D[start:end]) being one node of the tree - or a right-hand range that MerkleTreePrimitives.computeMerkleTreeHash(MerkleTreeNodeSource, long, long, MerkleTreeHash) combines from at most one full subtree per level. So a production log, which cannot hold its entries in memory, only has to answer for the nodes it would store or cache anyway; an in-memory tree of entry hashes can be adapted with ListMerkleTreeNodeSource.

A proof over a tree of size n makes O(log n) requests per proof element for a range that is not itself full, O(log^2 n) in all. Requests are never made outside the ranges the caller passed to the generator, so an implementation may treat any other request as an error.

See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    byte[]
    getFullSubtreeHash(long start, long end)
    Returns the hash MTH(D[start:end]) of a full subtree.

  • Method Details

    • getFullSubtreeHash

      byte[] getFullSubtreeHash(long start, long end)
      Returns the hash MTH(D[start:end]) of a full subtree.
      Parameters:
      start - subtree start index (inclusive), a multiple of end - start
      end - subtree end index (exclusive); end - start is a power of two
      Returns:
      the node hash; for end == start + 1 this is the entry hash MTH({entry}), i.e. MerkleTreeHash.hashLeaf(byte[]) of the entry
      Throws:
      IllegalArgumentException - if the node is not available, for instance because end is beyond the tree's current size