Class MerkleTreePrimitives

java.lang.Object
org.bouncycastle.cert.plants.MerkleTreePrimitives
public class MerkleTreePrimitives extends Object
Merkle Tree primitives for Merkle Tree Certificates (PLANTS). Implements the generation and verification of subtree inclusion proofs and subtree consistency proofs, the Merkle Tree Hash over a range of entries, and interval covering.

All algorithms are expressed against the MerkleTreeHash operator, which the caller supplies; there are no direct org.bouncycastle.crypto.* or java.security.* dependencies in this class.

See Also:

  • Constructor Details

    • MerkleTreePrimitives

      public MerkleTreePrimitives()

  • Method Details

    • evaluateSubtreeInclusionProof

      public static byte[] evaluateSubtreeInclusionProof(long index, long start, long end, byte[] entryHash, List<byte[]> proof, MerkleTreeHash hash) throws InvalidProofException
      Evaluates a subtree inclusion proof, returning the expected subtree hash.
      Parameters:
      index - absolute index of the entry in the log
      start - subtree start index (inclusive)
      end - subtree end index (exclusive)
      entryHash - hash of the entry (MTH({entry}))
      proof - list of node hashes forming the inclusion proof
      hash - the Merkle tree hash implementation
      Returns:
      the expected subtree hash
      Throws:
      InvalidProofException - if the proof is malformed or cannot be evaluated
      See Also:

    • verifySubtreeInclusionProof

      public static boolean verifySubtreeInclusionProof(long index, long start, long end, byte[] entryHash, byte[] subtreeHash, List<byte[]> proof, MerkleTreeHash hash)
      Verifies a subtree inclusion proof by comparing the evaluated hash with the given subtree hash.
      Parameters:
      index - absolute index of the entry
      start - subtree start
      end - subtree end
      entryHash - hash of the entry
      subtreeHash - claimed subtree hash
      proof - inclusion proof
      hash - hash implementation
      Returns:
      true if the proof is valid, false otherwise

    • verifySubtreeConsistencyProof

      public static boolean verifySubtreeConsistencyProof(long start, long end, long n, byte[] subtreeHash, byte[] rootHash, List<byte[]> proof, MerkleTreeHash hash)
      Verifies a subtree consistency proof.
      Parameters:
      start - subtree start index
      end - subtree end index (exclusive)
      n - full tree size (number of entries)
      subtreeHash - hash of the subtree (MTH(D[start:end]))
      rootHash - hash of the full tree (MTH(D[0:n]))
      proof - list of node hashes forming the consistency proof
      hash - hash implementation
      Returns:
      true if the proof is valid, false otherwise
      See Also:

    • computeMerkleTreeHash

      public static byte[] computeMerkleTreeHash(List<byte[]> entryHashes, long start, long end, MerkleTreeHash hash)
      Computes the Merkle Tree Hash MTH(D[start:end]) over a range of entries, per RFC 9162 Section 2.1.1. The range need not be a subtree in the sense of Section 4.1; any non-empty [start, end) within the list is accepted, which is what the proof generators need for the intermediate node hashes they emit.
      Parameters:
      entryHashes - hashes of the tree's entries, entry i at position i (each MTH({entry}), i.e. MerkleTreeHash.hashLeaf(byte[]))
      start - range start index (inclusive)
      end - range end index (exclusive)
      hash - the Merkle tree hash implementation
      Returns:
      MTH(D[start:end])
      Throws:
      IllegalArgumentException - if the range is empty or not covered by entryHashes

    • computeMerkleTreeHash

      public static byte[] computeMerkleTreeHash(MerkleTreeNodeSource nodes, long start, long end, MerkleTreeHash hash)
      Computes the Merkle Tree Hash MTH(D[start:end]) over a range of entries from a storage-backed tree, per RFC 9162 Section 2.1.1. A range that is itself a full subtree is a single request to nodes; any other range is combined from at most one full subtree per level of the tree.
      Parameters:
      nodes - source of full-subtree hashes for the tree
      start - range start index (inclusive)
      end - range end index (exclusive)
      hash - the Merkle tree hash implementation
      Returns:
      MTH(D[start:end])
      Throws:
      IllegalArgumentException - if the range is empty, or nodes cannot supply a node

    • generateSubtreeInclusionProof

      public static List<byte[]> generateSubtreeInclusionProof(long index, long start, long end, List<byte[]> entryHashes, MerkleTreeHash hash)
      Generates a subtree inclusion proof for the entry at index within the subtree [start, end). Per Section 4.3 this is the Merkle inclusion proof PATH(index - start, D[start:end]) of RFC 9162 Section 2.1.3.1, computed over the subtree's entries. The result is accepted by evaluateSubtreeInclusionProof(long, long, long, byte[], List, MerkleTreeHash) and verifySubtreeInclusionProof(long, long, long, byte[], byte[], List, MerkleTreeHash) for the same index, start and end.
      Parameters:
      index - absolute index of the entry in the log
      start - subtree start index (inclusive)
      end - subtree end index (exclusive)
      entryHashes - hashes of the tree's entries, entry i at position i; only positions [start, end) are read
      hash - the Merkle tree hash implementation
      Returns:
      the sibling hashes from the entry up to the subtree root (empty for a size-one subtree)
      Throws:
      IllegalArgumentException - if [start, end) is not a valid subtree (Section 4.1), index lies outside it, or entryHashes does not cover it

    • generateSubtreeInclusionProof

      public static List<byte[]> generateSubtreeInclusionProof(long index, long start, long end, MerkleTreeNodeSource nodes, MerkleTreeHash hash)
      Generates a subtree inclusion proof for the entry at index within the subtree [start, end) of a storage-backed tree; see generateSubtreeInclusionProof(long, long, long, List, MerkleTreeHash).
      Parameters:
      index - absolute index of the entry in the log
      start - subtree start index (inclusive)
      end - subtree end index (exclusive)
      nodes - source of full-subtree hashes for the tree; only nodes within [start, end) are requested
      hash - the Merkle tree hash implementation
      Returns:
      the sibling hashes from the entry up to the subtree root (empty for a size-one subtree)
      Throws:
      IllegalArgumentException - if [start, end) is not a valid subtree (Section 4.1), index lies outside it, or nodes cannot supply a node

    • generateSubtreeConsistencyProof

      public static List<byte[]> generateSubtreeConsistencyProof(long start, long end, long n, List<byte[]> entryHashes, MerkleTreeHash hash)
      Generates a subtree consistency proof SUBTREE_PROOF(start, end, D_n) showing that the subtree [start, end) is contained in the tree of size n, per Section 4.4.1. The result is accepted by verifySubtreeConsistencyProof(long, long, long, byte[], byte[], List, MerkleTreeHash) for the same start, end and n. As the draft notes, with start == 0 this is the RFC 9162 consistency proof PROOF(end, D_n), and with end == start + 1 it is the inclusion proof PATH(start, D_n).
      Parameters:
      start - subtree start index (inclusive)
      end - subtree end index (exclusive)
      n - full tree size (number of entries)
      entryHashes - hashes of the tree's entries, entry i at position i; positions [0, n) are read
      hash - the Merkle tree hash implementation
      Returns:
      the node hashes forming the consistency proof (empty when the subtree is the whole tree)
      Throws:
      IllegalArgumentException - if [start, end) is not a valid subtree (Section 4.1), end > n, or entryHashes does not cover [0, n)

    • generateSubtreeConsistencyProof

      public static List<byte[]> generateSubtreeConsistencyProof(long start, long end, long n, MerkleTreeNodeSource nodes, MerkleTreeHash hash)
      Generates a subtree consistency proof SUBTREE_PROOF(start, end, D_n) for the subtree [start, end) in a storage-backed tree of size n; see generateSubtreeConsistencyProof(long, long, long, List, MerkleTreeHash).
      Parameters:
      start - subtree start index (inclusive)
      end - subtree end index (exclusive)
      n - full tree size (number of entries)
      nodes - source of full-subtree hashes for the tree; only nodes within [0, n) are requested
      hash - the Merkle tree hash implementation
      Returns:
      the node hashes forming the consistency proof (empty when the subtree is the whole tree)
      Throws:
      IllegalArgumentException - if [start, end) is not a valid subtree (Section 4.1), end > n, or nodes cannot supply a node

    • isFullSubtree

      public static boolean isFullSubtree(long start, long end)
      Whether [start, end) is a full subtree: its size is a power of two and start is a multiple of that size, so MTH(D[start:end]) is a single node of the tree.
      Parameters:
      start - subtree start (inclusive)
      end - subtree end (exclusive)
      Returns:
      true if the range is one node of the tree

    • isValidSubtree

      public static boolean isValidSubtree(long start, long end)
      Checks whether [start, end) is a valid subtree interval per Section 4.1: 0 <= start < end, and start is a multiple of BIT_CEIL(end - start).
      Parameters:
      start - subtree start (inclusive)
      end - subtree end (exclusive)
      Returns:
      true if the interval describes a valid subtree

    • findCoveringSubtrees

      public static List<long[]> findCoveringSubtrees(long start, long end)
      Finds the minimal set of subtrees that efficiently cover the interval [start, end). Returns a list of one or two (start, end) pairs.
      Parameters:
      start - start index of the interval (inclusive)
      end - end index of the interval (exclusive)
      Returns:
      list of one or two subtrees covering the interval (as long arrays of length 2)
      See Also: