Package org.bitcoinj.core

Class PartialMerkleTree

  • public class PartialMerkleTree
extends java.lang.Object

    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.

    • Constructor Summary

      Constructors 
      Constructor Description
      PartialMerkleTree​(int origTxCount, java.util.List<Sha256Hash> hashes, byte[] bits)
      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.

    • Constructor Detail

      • PartialMerkleTree

        public PartialMerkleTree​(int origTxCount,
                         java.util.List<Sha256Hash> hashes,
                         byte[] bits)
        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 Detail

      • read

        public static PartialMerkleTree read​(java.nio.ByteBuffer payload)
                              throws java.nio.BufferUnderflowException,
                                     ProtocolException
        Deserialize a partial merkle tree from a given payload.
        Parameters:
        payload - payload to deserialize from
        Returns:
        read message
        Throws:
        java.nio.BufferUnderflowException - if the read message extends beyond the remaining bytes of the payload
        ProtocolException

      • buildFromLeaves

        public static PartialMerkleTree buildFromLeaves​(byte[] includeBits,
                                                java.util.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.

      • write

        public java.nio.ByteBuffer write​(java.nio.ByteBuffer buf)
                          throws java.nio.BufferOverflowException
        Write this partial merkle tree into the given buffer.
        Parameters:
        buf - buffer to write into
        Returns:
        the buffer
        Throws:
        java.nio.BufferOverflowException - if the partial merkle tree doesn't fit the remaining buffer

      • serialize

        public byte[] serialize()
        Allocates a byte array and writes this partial merkle tree into it.
        Returns:
        byte array containing the partial merkle tree

      • getMessageSize

        public int getMessageSize()
        Return the size of the serialized message. Note that if the message was deserialized from a payload, this size can differ from the size of the original payload.
        Returns:
        size of the serialized message in bytes

      • getTxnHashAndMerkleRoot

        public Sha256Hash getTxnHashAndMerkleRoot​(java.util.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​(java.lang.Object o)
        Overrides:
        equals in class java.lang.Object

      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object