com.google.bitcoin.core

Class PartialMerkleTree

java.lang.Object

com.google.bitcoin.core.Message

com.google.bitcoin.core.PartialMerkleTree

All Implemented Interfaces:

Serializable

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.

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class com.google.bitcoin.core.Message

Message.LazyParseException

Field Summary

Fields inherited from class com.google.bitcoin.core.Message

bytes, checksum, cursor, length, MAX_SIZE, offset, params, parsed, parseLazy, parseRetain, protocolVersion, recached, UNKNOWN_LENGTH

Constructor Summary

Constructors

Constructor and Description
PartialMerkleTree(NetworkParameters params, byte[] payloadBytes, int offset)

Method Summary

Methods

Modifier and Type	Method and Description
void	bitcoinSerializeToStream(OutputStream stream) Serializes this message to the provided stream.
Sha256Hash	getTxnHashAndMerkleRoot(List<Sha256Hash> matchedHashes) Extracts tx hashes that are in this merkle tree and returns the merkle root of this tree.
protected void	parseLite() Perform the most minimal parse possible to calculate the length of the message.

Methods inherited from class com.google.bitcoin.core.Message

adjustLength, bitcoinSerialize, bitcoinSerialize, ensureParsed, getHash, getMessageSize, getParams, isCached, isParsed, isRecached, maybeParse, unCache, unsafeBitcoinSerialize

Methods inherited from class java.lang.Object

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

Constructor Detail

PartialMerkleTree

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

Throws:

ProtocolException

Method Detail

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().

Throws:

IOException

parseLite

protected void parseLite()

Description copied from class: Message

Perform the most minimal parse possible to calculate the length of the message. This is only required for subclasses of ChildClass as root level messages will have their length passed into the constructor.

Implementations should adhere to the following contract: If parseLazy = true the 'length' field must be set before returning. If parseLazy = false the length field must be set either within the parseLite() method OR the parse() method. The overriding requirement is that length must be set to non UNKNOWN_MESSAGE value by the time the constructor exits.

Specified by:

parseLite in class Message

getTxnHashAndMerkleRoot

public Sha256Hash getTxnHashAndMerkleRoot(List<Sha256Hash> matchedHashes)
                                   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:

matchedHashes - A list which will contain the matched txn (will be cleared) Required to be a LinkedHashSet in order to retain order or transactions in the block

Returns:

the merkle root of this merkle tree

Throws:

ProtocolException - if this partial merkle tree is invalid

VerificationException