Compact Block Relay

  BIP: 152
  Layer: Peer Services
  Title: Compact Block Relay
  Authors: Matt Corallo 
  Comments-Summary: Unanimously Recommended for implementation
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0152
  Status: Deployed
  Type: Specification
  Assigned: 2016-04-27
  License: PD

Abstract

Compact blocks on the wire as a way to save bandwidth for nodes on the P2P network.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.

Motivation

Historically, the Bitcoin P2P protocol has not been very bandwidth efficient for block relay. Every transaction in a block is included when relayed, even though a large number of the transactions in a given block are already available to nodes before the block is relayed. This causes moderate inbound bandwidth spikes for nodes when receiving blocks, but can cause very significant outbound bandwidth spikes for some nodes which receive a block before their peers. When such spikes occur, buffer bloat can make consumer-grade internet connections temporarily unusable, and can delay the relay of blocks to remote peers who may choose to wait instead of redundantly requesting the same block from other, less congested, peers.

Thus, decreasing the bandwidth used during block relay is very useful for many individuals running nodes.

While the goal of this work is explicitly not to reduce block transfer latency, it does, as a side effect reduce block transfer latencies in some rather significant ways. Additionally, this work forms a foundation for future work explicitly targeting low-latency block transfer.

Specification for version 1

Intended Protocol Flow

The protocol is intended to be used in two ways, depending on the peers and bandwidth available, as discussed later. The "high-bandwidth" mode, which nodes may only enable for a few of their peers, is enabled by setting the first boolean to 1 in a sendcmpct message. In this mode, peers send new block announcements with the short transaction IDs already (via a cmpctblock message), possibly even before fully validating the block (as indicated by the grey box in the image above). In some cases no further round-trip is needed, and the receiver can reconstruct the block and process it as usual immediately. When some transactions were not available from local sources (ie mempool), a getblocktxn/blocktxn roundtrip is necessary, bringing the best-case latency to the same 1.5*RTT minimum time that nodes take today, though with significantly less bandwidth usage.

The "low-bandwidth" mode is enabled by setting the first boolean to 0 in a sendcmpct message. In this mode, peers send new block announcements with the usual inv/headers announcements (as per BIP130, and after fully validating the block). The receiving peer may then request the block using a MSG_CMPCT_BLOCK getdata request, which will receive a response of the header and short transaction IDs. In some cases no further round-trip is needed, and the receiver can reconstruct the block and process it as usual, taking the same 1.5*RTT minimum time that nodes take today, though with significantly less bandwidth usage. When some transactions were not available from local sources (ie mempool), a getblocktxn/blocktxn roundtrip is necessary, bringing the latency to at least 2.5*RTT in this case, again with significantly less bandwidth usage than today. Because TCP often exhibits worse transfer latency for larger data sizes (as a multiple of RTT), total latency is expected to be reduced even when the full 2.5*RTT transfer mechanism is used.

New data structures

Several new data structures are added to the P2P network to relay compact blocks: PrefilledTransaction, HeaderAndShortIDs, BlockTransactionsRequest, and BlockTransactions.

For the purposes of this section, CompactSize refers to the variable-length integer encoding used across the existing P2P protocol to encode array lengths, among other things, in 1, 3, 5 or 9 bytes. Only CompactSize encodings which are minimally-encoded (ie the shortest length possible) are used by this spec. Any other CompactSize encodings are left with undefined behavior.

Several uses of CompactSize below are "differentially encoded". For these, instead of using raw indexes, the number encoded is the difference between the current index and the previous index, minus one. For example, a first index of 0 implies a real index of 0, a second index of 0 thereafter refers to a real index of 1, etc.

PrefilledTransaction

A PrefilledTransaction structure is used in HeaderAndShortIDs to provide a list of a few transactions explicitly.

Field Name	Type	Size	Encoding	Purpose
index	CompactSize	1, 3 bytes	Compact Size, differentially encoded since the last PrefilledTransaction in a list	The index into the block at which this transaction is
tx	Transaction	variable	As encoded in "tx" messages sent in response to getdata MSG_TX	The transaction which is in the block at index index.

HeaderAndShortIDs

A HeaderAndShortIDs structure is used to relay a block header, the short transactions IDs used for matching already-available transactions, and a select few transactions which we expect a peer may be missing.

Field Name	Type	Size	Encoding	Purpose
header	Block header	80 bytes	First 80 bytes of the block as defined by the encoding used by "block" messages	The header of the block being provided
nonce	uint64_t	8 bytes	Little Endian	A nonce for use in short transaction ID calculations
shortids_length	CompactSize	1 or 3 bytes	As used to encode array lengths elsewhere		The number of short transaction IDs in shortids (ie block tx count - prefilledtxn_length)
shortids	List of 6-byte integers	6*shortids_length bytes	Little Endian	The short transaction IDs calculated from the transactions which were not provided explicitly in prefilledtxn
prefilledtxn_length	CompactSize	1 or 3 bytes	As used to encode array lengths elsewhere		The number of prefilled transactions in prefilledtxn (ie block tx count - shortids_length)
prefilledtxn	List of PrefilledTransactions	variable size*prefilledtxn_length	As defined by PrefilledTransaction definition, above	Used to provide the coinbase transaction and a select few which we expect a peer may be missing

BlockTransactionsRequest

A BlockTransactionsRequest structure is used to list transaction indexes in a block being requested.

Field Name	Type	Size	Encoding	Purpose
blockhash	Binary blob	32 bytes	The output from a double-SHA256 of the block header, as used elsewhere	The blockhash of the block which the transactions being requested are in
indexes_length	CompactSize	1 or 3 bytes	As used to encode array lengths elsewhere		The number of transactions being requested
indexes	List of CompactSizes	1 or 3 bytes*indexes_length	Differentially encoded	The indexes of the transactions being requested in the block

BlockTransactions

A BlockTransactions structure is used to provide some of the transactions in a block, as requested.

Field Name	Type	Size	Encoding	Purpose
blockhash	Binary blob	32 bytes	The output from a double-SHA256 of the block header, as used elsewhere	The blockhash of the block which the transactions being provided are in
transactions_length	CompactSize	1 or 3 bytes	As used to encode array lengths elsewhere		The number of transactions provided
transactions	List of Transactions	variable	As encoded in "tx" messages in response to getdata MSG_TX	The transactions provided

Short transaction IDs

Short transaction IDs are used to represent a transaction without sending a full 256-bit hash. They are calculated by: # single-SHA256 hashing the block header with the nonce appended (in little-endian) # Running SipHash-2-4 with the input being the transaction ID and the keys (k0/k1) set to the first two little-endian 64-bit integers from the above hash, respectively. # Dropping the 2 most significant bytes from the SipHash output to make it 6 bytes.

New messages

A new inv type (MSG_CMPCT_BLOCK == 4) and several new protocol messages are added: sendcmpct, cmpctblock, getblocktxn, and blocktxn.

sendcmpct

# The sendcmpct message is defined as a message containing a 1-byte integer followed by a 8-byte integer where pchCommand == "sendcmpct". # The first integer SHALL be interpreted as a boolean (and MUST have a value of either 1 or 0) # The second integer SHALL be interpreted as a little-endian version number. Nodes sending a sendcmpct message MUST currently set this value to 1. # Upon receipt of a "sendcmpct" message with the first and second integers set to 1, the node SHOULD announce new blocks by sending a cmpctblock message. # Upon receipt of a "sendcmpct" message with the first integer set to 0, the node SHOULD NOT announce new blocks by sending a cmpctblock message, but SHOULD announce new blocks by sending invs or headers, as defined by BIP130. # Upon receipt of a "sendcmpct" message with the second integer set to something other than 1, nodes MUST treat the peer as if they had not received the message (as it indicates the peer will provide an unexpected encoding in cmpctblock, and/or other, messages). This allows future versions to send duplicate sendcmpct messages with different versions as a part of a version handshake for future versions. See Protocol Versioning section, below, for more info on the specifics of the version-negotiation mechanics. # Nodes SHOULD check for a protocol version of >= 70014 before sending sendcmpct messages. # Nodes MUST NOT send a request for a MSG_CMPCT_BLOCK object to a peer before having received a sendcmpct message from that peer. # Nodes MUST NOT request a MSG_CMPCT_BLOCK object before having sent all sendcmpct messages to that peer which they intend to send, as the peer cannot know what version protocol to use in the response.

MSG_CMPCT_BLOCK

# getdata messages may now contain requests for MSG_CMPCT_BLOCK objects. # Upon receipt of a getdata containing a request for a MSG_CMPCT_BLOCK object with the hash of a block which was recently announced and is close to the tip of the best chain of the receiver and after having sent the requesting peer a sendcmpct message, nodes MUST respond with a cmpctblock message containing appropriate data representing the block being requested. # Upon receipt of a getdata containing a request for a MSG_CMPCT_BLOCK object for which a cmpctblock message is not sent in response, a block message containing the requested block in non-compact form MUST be sent. # MSG_CMPCT_BLOCK inv objects MUST NOT appear anywhere except for in getdata messages.

cmpctblock

# The cmpctblock message is defined as a message containing a serialized HeaderAndShortIDs message and pchCommand == "cmpctblock". # Upon receipt of a cmpctblock message after sending a sendcmpct message, nodes SHOULD calculate the short transaction ID for each unconfirmed transaction they have available (ie in their mempool) and compare each to each short transaction ID in the cmpctblock message. # After finding already-available transactions, nodes which do not have all transactions available to reconstruct the full block SHOULD request the missing transactions using a getblocktxn message. # A node MUST NOT send a cmpctblock message unless they are able to respond to a getblocktxn message which requests every transaction in the block. # A node MUST NOT send a cmpctblock message without having validated that the header properly commits to each transaction in the block, and properly builds on top of the existing, fully-validated chain with a valid proof-of-work either as a part of the current most-work valid chain, or building directly on top of it. A node MAY send a cmpctblock before validating that each transaction in the block validly spends existing UTXO set entries.

getblocktxn

# The getblocktxn message is defined as a message containing a serialized BlockTransactionsRequest message and pchCommand == "getblocktxn". # Upon receipt of a properly-formatted getblocktxn message, nodes which recently provided the sender of such a message a cmpctblock for the block hash identified in this message MUST respond with either an appropriate blocktxn message, or a full block message. A blocktxn response MUST contain exactly and only each transaction which is present in the appropriate block at the index specified in the getblocktxn indexes list, in the order requested.

blocktxn

# The blocktxn message is defined as a message containing a serialized BlockTransactions message and pchCommand == "blocktxn". # Upon receipt of a properly-formatted requested blocktxn message, nodes SHOULD attempt to reconstruct the full block by: ## Taking the prefilledtxn transactions from the original cmpctblock and placing them in the marked positions. ## For each short transaction ID from the original cmpctblock, in order, find the corresponding transaction either from the blocktxn message or from other sources and place it in the first available position in the block. # Once the block has been reconstructed, it shall be processed as normal, keeping in mind that short transaction IDs are expected to occasionally collide, and that nodes MUST NOT be penalized for such collisions, wherever they appear.

Protocol Versioning

# The protocol version negotiation allows two nodes to agree on the versions of compact blocks which they will exchange. As it is only in a single field, it does not allow a node to support a specific version in only one direction (sending or receiving). # Upon connection establishment, a node SHOULD send a burst of sendcmpct messages containing every version of compact block encodings for which they are willing to support sending cmpctblock and blocktxn messages, and receiving getblocktxn messages. These messages SHOULD be ordered in the order of the priority which the node wishes to receive cmpctblock/blocktxn messages, with the highest-priority version sendcmpct message sent first. # The encoding version used to send a cmpctblock or blocktxn message or to receive a getblocktxn message MUST be the second integer (version number) in the first sendcmpct message received for which a sendcmpct message with the same version number was sent. # Nodes MUST NOT send a sendcmpct message which contains a version number other than the version number which has been negotiated for receiving cmpctblock/blocktxn messages after sending a request for a MSG_CMPCT_BLOCK object, sending a cmpctblock, getblocktxn, blocktxn, or pong message. # As a node