Package org.bitcoinj.core

Class PartialMerkleTree

java.lang.Object
org.bitcoinj.core.Message
org.bitcoinj.core.PartialMerkleTree
public class PartialMerkleTree extends Message

A data structure that contains proofs of block inclusion for one or more transactions, in an efficient manner.

The encoding works as follows: we traverse the tree in depth-first order, storing a bit for each traversed node, signifying whether the node is the parent of at least one matched leaf txid (or a matched txid itself). In case we are at the leaf level, or this bit is 0, its merkle node hash is stored, and its children are not explored further. Otherwise, no hash is stored, but we recurse into both (or the only) child branch. During decoding, the same depth-first traversal is performed, consuming bits and hashes as they were written during encoding.

The serialization is fixed and provides a hard guarantee about the encoded size, SIZE <= 10 + ceil(32.25*N) where N represents the number of leaf nodes of the partial tree. N itself is bounded by:

N <= total_transactions
N <= 1 + matched_transactions*tree_height

The serialization format:

  - uint32     total_transactions (4 bytes)
  - varint     number of hashes   (1-3 bytes)
  - uint256[]  hashes in depth-first order (<= 32*N bytes)
  - varint     number of bytes of flag bits (1-3 bytes)
  - byte[]     flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits)

The size constraints follow from this.

Instances of this class are not safe for use by multiple threads.

  • Constructor Details

    • PartialMerkleTree

      public PartialMerkleTree(NetworkParameters params, byte[] payloadBytes, int offset) throws ProtocolException
      Throws:
      ProtocolException

    • PartialMerkleTree

      public PartialMerkleTree(NetworkParameters params, byte[] bits, List<Sha256Hash> hashes, int origTxCount)
      Constructs a new PMT with the given bit set (little endian) and the raw list of hashes including internal hashes, taking ownership of the list.

  • Method Details

    • buildFromLeaves

      public static PartialMerkleTree buildFromLeaves(NetworkParameters params, byte[] includeBits, List<Sha256Hash> allLeafHashes)
      Calculates a PMT given the list of leaf hashes and which leaves need to be included. The relevant interior hashes are calculated and a new PMT returned.

    • bitcoinSerializeToStream

      public void bitcoinSerializeToStream(OutputStream stream) throws IOException
      Description copied from class: Message
      Serializes this message to the provided stream. If you just want the raw bytes use bitcoinSerialize().
      Overrides:
      bitcoinSerializeToStream in class Message
      Throws:
      IOException

    • parse

      protected void parse() throws ProtocolException
      Specified by:
      parse in class Message
      Throws:
      ProtocolException

    • getTxnHashAndMerkleRoot

      public Sha256Hash getTxnHashAndMerkleRoot(List<Sha256Hash> matchedHashesOut) throws VerificationException
      Extracts tx hashes that are in this merkle tree and returns the merkle root of this tree. The returned root should be checked against the merkle root contained in the block header for security.
      Parameters:
      matchedHashesOut - A list which will contain the matched txn (will be cleared).
      Returns:
      the merkle root of this merkle tree
      Throws:
      ProtocolException - if this partial merkle tree is invalid
      VerificationException

    • getTransactionCount

      public int getTransactionCount()

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object