org.bouncycastle.cert.plants

Class MerkleTreePrimitives

java.lang.Object

org.bouncycastle.cert.plants.MerkleTreePrimitives

public class MerkleTreePrimitives
extends java.lang.Object

Merkle Tree primitives for Merkle Tree Certificates (PLANTS). Implements subtree inclusion proofs, consistency proofs, 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:

draft-ietf-plants-merkle-tree-certs, Section 4

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	MerkleTreePrimitives.SubtreeInfo Simple container for a subtree interval (start inclusive, end exclusive).

Constructor Summary

Constructors

Constructor and Description
MerkleTreePrimitives()

Method Summary

Modifier and Type	Method and Description
static byte[]	evaluateSubtreeInclusionProof(long index, long start, long end, byte[] entryHash, java.util.List<byte[]> proof, MerkleTreeHash hash) Evaluates a subtree inclusion proof, returning the expected subtree hash.
static java.util.List<long[]>	findCoveringSubtrees(long start, long end) Finds the minimal set of subtrees that efficiently cover the interval [start, end).
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).
static boolean	verifySubtreeConsistencyProof(long start, long end, long n, byte[] subtreeHash, byte[] rootHash, java.util.List<byte[]> proof, MerkleTreeHash hash) Verifies a subtree consistency proof.
static boolean	verifySubtreeInclusionProof(long index, long start, long end, byte[] entryHash, byte[] subtreeHash, java.util.List<byte[]> proof, MerkleTreeHash hash) Verifies a subtree inclusion proof by comparing the evaluated hash with the given subtree hash.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MerkleTreePrimitives

public MerkleTreePrimitives()

Method Detail

evaluateSubtreeInclusionProof

public static byte[] evaluateSubtreeInclusionProof(long index,
                                                   long start,
                                                   long end,
                                                   byte[] entryHash,
                                                   java.util.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:

Section 4.3.2

verifySubtreeInclusionProof

public static boolean verifySubtreeInclusionProof(long index,
                                                  long start,
                                                  long end,
                                                  byte[] entryHash,
                                                  byte[] subtreeHash,
                                                  java.util.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,
                                                    java.util.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:

Section 4.4.3

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 java.util.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:

Section 4.5