Package com.privatechain.crypto

Class MerkleTree

java.lang.Object
com.privatechain.crypto.MerkleTree
public final class MerkleTree extends Object
Builds a binary Merkle tree from a list of transaction IDs and exposes root computation, inclusion-proof generation, and proof verification.

A Merkle tree provides a compact cryptographic commitment to an ordered set of transactions. Given only the 32-byte root, any third party can verify that a specific transaction is included in the set without downloading all transactions (FR-CRYPTO-06, FR-CRYPTO-07).

Hash function

Each node stores SHA-256(left || right) (concatenation of lowercase hex strings). Leaf nodes store SHA-256(txId). This is consistent with the convention used in Bitcoin.

Odd-node handling

When a level has an odd number of nodes, the last node is duplicated (Bitcoin / BIP-34 convention) to form a complete binary tree.

Usage


 List<String> txIds = block.getTransactions()
                           .stream()
                           .map(tx -> tx.getId().toString())
                           .collect(Collectors.toList());

 String root  = MerkleTree.buildRoot(txIds);
 MerkleProof p = MerkleTree.getProof(txIds, targetTxId);
 boolean ok   = MerkleTree.verifyProof(p, root, targetTxId);
Since:
1.0.0
See Also:

  • Field Details

    • EMPTY_ROOT

      public static final String EMPTY_ROOT
      Canonical root returned when the transaction list is empty. This is the same 64-zero sentinel used for the genesis block's Merkle root.

  • Method Details

    • buildRoot

      public static String buildRoot(List<String> txIds)
      Builds the Merkle root of an ordered list of transaction IDs.

      Returns EMPTY_ROOT when the list is empty (genesis block behavior). The root changes deterministically if any transaction ID changes or the order changes, providing tamper evidence for the entire transaction set.

      Parameters:
      txIds - ordered list of transaction ID strings (non-null; may be empty)
      Returns:
      64-character lowercase hex Merkle root
      Throws:
      NullPointerException - if txIds is null or any element is null
      IllegalArgumentException - if any txId is blank

    • getProof

      public static MerkleTree.MerkleProof getProof(List<String> txIds, String targetTxId)
      Generates a Merkle inclusion proof for the given transaction ID.

      The proof is a list of (sibling hash, position) pairs that, together with the leaf hash of targetTxId, allow reconstruction of the Merkle root without knowing any other transaction in the block.

      Parameters:
      txIds - the complete, ordered list of transaction IDs in the block (non-null)
      targetTxId - the transaction ID for which to generate the proof (non-null, non-blank)
      Returns:
      a MerkleTree.MerkleProof containing the sibling path; never null
      Throws:
      NullPointerException - if txIds or targetTxId is null
      IllegalArgumentException - if targetTxId is blank or not found in txIds

    • verifyProof

      public static boolean verifyProof(MerkleTree.MerkleProof proof, String expectedRoot, String txId)
      Verifies that a MerkleTree.MerkleProof establishes inclusion of a transaction in a block whose Merkle root is expectedRoot.

      Only the proof and the expected root are required — no other transaction data is needed. This allows lightweight clients to verify inclusion without downloading the full block.

      Parameters:
      proof - the proof returned by getProof(java.util.List<java.lang.String>, java.lang.String) (non-null)
      expectedRoot - the Merkle root stored in the block header (non-null, non-blank)
      txId - the transaction ID whose inclusion is being proven (non-null, non-blank)
      Returns:
      true if the proof is valid and txId is in the block; false otherwise
      Throws:
      NullPointerException - if proof, expectedRoot, or txId is null
      IllegalArgumentException - if expectedRoot or txId is blank