net.corda.core.crypto / PartialMerkleTree

# PartialMerkleTree

`class PartialMerkleTree`

Building and verification of Partial Merkle Tree. Partial Merkle Tree is a minimal tree needed to check that a given set of leaves belongs to a full Merkle Tree.

Example of Merkle tree with 5 leaves.

h15 / \ h14 h55 / \ / \ h12 h34 h5->d(h5) / \ / \ / \ l1 l2 l3 l4 l5->d(l5)

l* denote hashes of leaves, h* - hashes of nodes below. h5->d(h5) denotes duplication of the left hand side node. These nodes are kept in a full tree as DuplicatedLeaf. When filtering the tree for l5, we dont want to keep both l5 and its duplicate (it can also be solved using null values in a tree, but this solution is clearer).

Example of Partial tree based on the tree above.

/ \ _ _ / \ / \ h12 _ _ d(h5) / \ / \ I3 l4 I5 d(l5)

We want to check l3 and l5 - now turned into IncudedLeaf (I3 and I5 above). To verify that these two leaves belong to the tree with a hash root h15 we need to provide a Merkle branch (or partial tree). In our case we need hashes: h12, l4, d(l5) and d(h5). Verification is done by hashing the partial tree to obtain the root and checking it against the obtained h15 hash. Additionally we store included hashes used in calculation and compare them to leaves hashes we got (there can be a difference in obtained leaves ordering - thats why its a set comparison not hashing leaves into a tree). If both equalities hold, we can assume that l3 and l5 belong to the transaction with root h15.

### Types

PartialTree | `sealed class PartialTree` The structure is a little different than that of Merkle Tree. Partial Tree might not be a full binary tree. Leaves represent either original Merkle tree leaves or cut subtree node with stored hash. We differentiate between the leaves that are included in a filtered transaction and leaves that just keep hashes needed for calculation. Reason for this approach: during verification its easier to extract hashes used as a base for this tree.

### Constructors

<init> | `PartialMerkleTree(root: PartialTree)` Building and verification of Partial Merkle Tree. Partial Merkle Tree is a minimal tree needed to check that a given set of leaves belongs to a full Merkle Tree.

### Properties

root | `val root: PartialTree`

### Functions

verify | `fun verify(merkleRootHash: SecureHash, hashesToCheck: List<SecureHash>): Boolean`

### Companion Object Functions

build | `fun build(merkleRoot: MerkleTree, includeHashes: List<SecureHash>): PartialMerkleTree`