{"type":"rich","version":"1.0","author_name":"npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcu","author_url":"https://nostr.ae/npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcu","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2016-05-02\n📝 Original message:Hi all,\n\nThe following is a BIP-formatted design spec for compact block relay\ndesigned to limit on wire bytes during block relay. You can find the\nlatest version of this document at\nhttps://github.com/TheBlueMatt/bips/blob/master/bip-TODO.mediawiki.\n\nThere are several TODO items left on the document as indicated.\nAdditionally, the implementation linked at the bottom of the document\nhas a few remaining TODO items as well:\n\n * Only request compact-block-announcement from one or two peers at a\ntime, as the spec requires.\n * Request new blocks using MSG_CMPCT_BLOCK where appropriate.\n * Fill prefilledtxn with more than just the coinbase, as noted by the\nspec, up to 10K in transactions.\n\nLuke (CC'd): Can you assign a BIP number?\n\nThanks,\nMatt\n\n\u003cpre\u003e\n  BIP: TODO\n  Title: Compact block relay\n  Author: Matt Corallo \u003cbip at bluematt.me\u003e\n  Status: Draft\n  Type: Standards Track\n  Created: 2016-04-27\n\u003c/pre\u003e\n\n==Abstract==\n\nCompact blocks on the wire as a way to save bandwidth for nodes on the\nP2P network.\n\nThe key words \"MUST\", \"MUST NOT\", \"REQUIRED\", \"SHALL\", \"SHALL NOT\",\n\"SHOULD\", \"SHOULD NOT\", \"RECOMMENDED\", \"MAY\", and \"OPTIONAL\" in this\ndocument are to be interpreted as described in RFC 2119.\n\n==Motivation==\n\nHistorically, the Bitcoin P2P protocol has not been very bandwidth\nefficient for block relay. Every transaction in a block is included when\nrelayed, even though a large number of the transactions in a given block\nare already available to nodes before the block is relayed. This causes\nmoderate inbound bandwidth spikes for nodes when receiving blocks, but\ncan cause very significant outbound bandwidth spikes for some nodes\nwhich receive a block before their peers. When such spikes occur, buffer\nbloat can make consumer-grade internet connections temporarily unusable,\nand can delay the relay of blocks to remote peers who may choose to wait\ninstead of redundantly requesting the same block from other, less\ncongested, peers.\n\nThus, decreasing the bandwidth used during block relay is very useful\nfor many individuals running nodes.\n\nWhile the goal of this work is explicitly not to reduce block transfer\nlatency, it does, as a side effect reduce block transfer latencies in\nsome rather significant ways. Additionally, this work forms a foundation\nfor future work explicitly targeting low-latency block transfer.\n\n==Specification==\n\n===Intended Protocol Flow===\nTODO: Diagrams\n\nThe protocol is intended to be used in two ways, depending on the peers\nand bandwidth available, as discussed [[#Implementation_Details|later]].\nThe \"high-bandwidth\" mode, which nodes may only enable for a few of\ntheir peers, is enabled by setting the first boolean to 1 in a\n\"sendcmpct\" message. In this mode, peers send new block announcements\nwith the short transaction IDs already, possibly even before fully\nvalidating the block. In some cases no further round-trip is needed, and\nthe receiver can reconstruct the block and process it as usual\nimmediately. When some transactions were not available from local\nsources (ie mempool), a getblocktxn/blocktxn roundtrip is neccessary,\nbringing the best-case latency to the same 1.5*RTT minimum time that\nnodes take today, though with significantly less bandwidth usage.\n\nThe \"low-bandwidth\" mode is enabled by setting the first boolean to 0 in\na \"sendcmpct\" message. In this mode, peers send new block announcements\nwith the usual inv/headers announcements (as per BIP130, and after fully\nvalidating the block). The receiving peer may then request the block\nusing a MSG_CMPCT_BLOCK getdata reqeuest, which will receive a response\nof the header and short transaction IDs. In some cases no further\nround-trip is needed, and the receiver can reconstruct the block and\nprocess it as usual, taking the same 1.5*RTT minimum time that nodes\ntake today, though with significantly less bandwidth usage. When some\ntransactions were not available from local sources (ie mempool), a\ngetblocktxn/blocktxn roundtrip is neccessary, bringing the best-case\nlatency to 2.5*RTT, again with significantly less bandwidth usage than\ntoday. Because TCP often exhibits worse transfer latency for larger data\nsizes (as a multiple of RTT), total latency is expected to be reduced\neven when full the 2.5*RTT transfer mechanism is used.\n\n===New data structures===\nSeveral new data structures are added to the P2P network to relay\ncompact blocks: PrefilledTransaction, HeaderAndShortIDs,\nBlockTransactionsRequest, and BlockTransactions. Additionally, we\nintroduce a new variable-length integer encoding for use in these data\nstructures.\n\nFor the purposes of this section, CompactSize refers to the\nvariable-length integer encoding used across the existing P2P protocol\nto encode array lengths, among other things, in 1, 3, 5 or 9 bytes.\n\n====New VarInt====\nTODO: I just copied this out of the src...Something that is\nwiki-formatted and more descriptive should be used here isntead.\n\nVariable-length integers: bytes are a MSB base-128 encoding of the number.\nThe high bit in each byte signifies whether another digit follows. To make\nsure the encoding is one-to-one, one is subtracted from all but the last\ndigit.\nThus, the byte sequence a[] with length len, where all but the last byte\nhas bit 128 set, encodes the number:\n\n(a[len-1] \u0026 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] \u0026 0x7F)+1))\n\nProperties:\n* Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes)\n* Every integer has exactly one encoding\n* Encoding does not depend on size of original integer type\n* No redundancy: every (infinite) byte sequence corresponds to a list\n  of encoded integers.\n\n0:         [0x00]  256:        [0x81 0x00]\n1:         [0x01]  16383:      [0xFE 0x7F]\n127:       [0x7F]  16384:      [0xFF 0x00]\n128:  [0x80 0x00]  16511: [0x80 0xFF 0x7F]\n255:  [0x80 0x7F]  65535: [0x82 0xFD 0x7F]\n2^32:           [0x8E 0xFE 0xFE 0xFF 0x00]\n\nSeveral uses of New VarInts below are \"differentially encoded\". For\nthese, instead of using raw indexes, the number encoded is the\ndifference between the current index and the previous index, minus one.\nFor example, a first index of 0 implies a real index of 0, a second\nindex of 0 thereafter refers to a real index of 1, etc.\n\n====PrefilledTransaction====\nA PrefilledTransaction structure is used in HeaderAndShortIDs to provide\na list of a few transactions explicitly.\n\n{|\n|Field Name||Type||Size||Encoding||Purpose\n|-\n|index||New VarInt||1-3 bytes||[[#New_VarInt|New VarInt]],\ndifferentially encoded since the last PrefilledTransaction in a\nlist||The index into the block at which this transaction is\n|-\n|tx||Transaction||variable||As encoded in \"tx\" messages||The transaction\nwhich is in the block at index index.\n|}\n\n====HeaderAndShortIDs====\nA HeaderAndShortIDs structure is used to relay a block header, the short\ntransactions IDs used for matching already-available transactions, and a\nselect few transactions which we expect a peer may be missing.\n\n{|\n|Field Name||Type||Size||Encoding||Purpose\n|-\n|header||Block header||80 bytes||First 80 bytes of the block as defined\nby the encoding used by \"block\" messages||The header of the block being\nprovided\n|-\n|nonce||uint64_t||8 bytes||Little Endian||A nonce for use in short\ntransaction ID calculations\n|-\n|shortids_length||CompactSize||1, 3, 5, or 9 bytes||As used elsewhere to\nencode array lengths||The number of short transaction IDs in shortids\n|-\n|shortids||List of uint64_ts||8*shortids_length bytes||Little\nEndian||The short transaction IDs calculated from the transactions which\nwere not provided explicitly in prefilledtxn\n|-\n|prefilledtxn_length||CompactSize||1, 3, 5, or 9 bytes||As used\nelsewhere to encode array lengths||The number of prefilled transactions\nin prefilledtxn\n|-\n|prefilledtxn||List of PrefilledTransactions||variable\nsize*prefilledtxn_length||As defined by PrefilledTransaction definition,\nabove||Used to provide the coinbase transaction and a select few which\nwe expect a peer may be missing\n|}\n\n====BlockTransactionsRequest====\nA BlockTransactionsRequest structure is used to list transaction indexes\nin a block being requested.\n\n{|\n|Field Name||Type||Size||Encoding||Purpose\n|-\n|blockhash||Binary blob||32 bytes||The output from a double-SHA256 of\nthe block header, as used elsewhere||The blockhash of the block which\nthe transactions being requested are in\n|-\n|indexes_length||New VarInt||1-3 bytes||As defined in [[#New_VarInt|New\nVarInt]]||The number of transactions being requested\n|-\n|indexes||List of New VarInts||1-3 bytes*indexes_length||As defined in\n[[#New_VarInt|New VarInt]], differentially encoded||The indexes of the\ntransactions being requested in the block\n|}\n\n====BlockTransactions====\nA BlockTransactions structure is used to provide some of the\ntransactions in a block, as requested.\n\n{|\n|Field Name||Type||Size||Encoding||Purpose\n|-\n|blockhash||Binary blob||32 bytes||The output from a double-SHA256 of\nthe block header, as used elsewhere||The blockhash of the block which\nthe transactions being provided are in\n|-\n|transactions_length||New VarInt||1-3 bytes||As defined in\n[[#New_VarInt|New VarInt]]||The number of transactions provided\n|-\n|transactions||List of Transactions||variable||As encoded in \"tx\"\nmessages||The transactions provided\n|}\n\n====Short transaction IDs====\nShort transaction IDs are used to represent a transaction without\nsending a full 256-bit hash. They are calculated by:\n# single-SHA256 hashing the block header with the nonce appended (in\nlittle-endian)\n# XORing each 8-byte chunk of the double-SHA256 transaction hash with\neach corresponding 8-byte chunk of the hash from the previous step\n# Adding each of the XORed 8-byte chunks together (in little-endian)\niteratively to find the short transaction ID\n\n===New messages===\nA new inv type (MSG_CMPCT_BLOCK == 4) and several new protocol messages\nare added: sendcmpct, cmpctblock, getblocktxn, and blocktxn.\n\n====sendcmpct====\n# The sendcmpct message is defined as a message containing a 1-byte\ninteger followed by a 8-byte integer where pchCommand == \"sendcmpct\".\n# The first integer SHALL be interpreted as a boolean (and MUST have a\nvalue of either 1 or 0)\n# The second integer SHALL be interpreted as a little-endian version\nnumber. Nodes sending a sendcmpct message MUST currently set this value\nto 1.\n# Upon receipt of a \"sendcmpct\" message with the first and second\nintegers set to 1, the node SHOULD announce new blocks by sending a\ncmpctblock message.\n# Upon receipt of a \"sendcmpct\" message with the first integer set to 0,\nthe node SHOULD NOT announce new blocks by sending a cmpctblock message,\nbut SHOULD announce new blocks by sending invs or headers, as defined by\nBIP130.\n# Upon receipt of a \"sendcmpct\" message with the second integer set to\nsomething other than 1, nodes SHOULD treat the peer as if they had not\nreceived the message (as it indicates the peer will provide an\nunexpected encoding in cmpctblock, and/or other, messages)\n# Nodes SHOULD check for a protocol version of \u003e= 70014 before sending\nsendcmpct messages.\n# Nodes MUST NOT send a request for a MSG_CMPCT_BLOCK object to a peer\nbefore having received a sendcmpct message from that peer.\n\n====MSG_CMPCT_BLOCK====\n# getdata messages may now contain requests for MSG_CMPCT_BLOCK objects.\n# Upon receipt of a getdata containing a request for a MSG_CMPCT_BLOCK\nobject with the hash of a block which was recently announced and after\nhaving sent the requesting peer a sendcmpct message, nodes MUST respond\nwith a cmpctblock message containing appropriate data representing the\nblock being requested.\n# MSG_CMPCT_BLOCK inv objects MUST NOT appear anywhere except for in\ngetdata messages.\n\n====cmpctblock====\n# The cmpctblock message is defined as as a message containing a\nserialized HeaderAndShortIDs message and pchCommand == \"cmpctblock\".\n# Upon receipt of a cmpctblock message after sending a sendcmpct\nmessage, nodes SHOULD calculate the short transaction ID for each\nunconfirmed transaction they have available (ie in their mempool) and\ncompare each to each short transaction ID in the cmpctblock message.\n# After finding already-available transactions, nodes which do not have\nall transactions available to reconstruct the full block SHOULD request\nthe missing transactions using a getblocktxn message.\n# A node MUST NOT send a cmpctblock message unless they are able to\nrespond to a getblocktxn message which requests every transaction in the\nblock.\n# A node MUST NOT send a cmpctblock message without having validated\nthat the header properly commits to each transaction in the block, and\nproperly builds on top of the existing chain with a valid proof-of-work.\nA node MAY send a cmpctblock before validating that each transaction in\nthe block validly spends existing UTXO set entries.\n\n====getblocktxn====\n# The getblocktxn message is defined as as a message containing a\nserialized BlockTransactionsRequest message and pchCommand == \"getblocktxn\".\n# Upon receipt of a properly-formatted getblocktxnmessage, nodes which\nrecently provided the sender of such a message a cmpctblock for the\nblock hash identified in this message MUST respond with an appropriate\nblocktxn message. Such a blocktxn message MUST contain exactly and only\neach transaction which is present in the appropriate block at the index\nspecified in the getblocktxn indexes list, in the order requested.\n\n====blocktxn====\n# The blocktxn message is defined as as a message containing a\nserialized BlockTransactions message and pchCommand == \"blocktxn\".\n# Upon receipt of a properly-formatted requested blocktxn message, nodes\nSHOULD attempt to reconstruct the full block by:\n## Taking the prefilledtxn transactions from the original cmpctblock and\nplacing them in the marked positions.\n## For each short transaction ID from the original cmpctblock, in order,\nfind the corresponding transaction either from the blocktxn message or\nfrom other sources and place it in the first available position in the\nblock.\n# Once the block has been reconstructed, it shall be processed as\nnormal, keeping in mind that short transaction IDs are expected to\noccasionally collide, and that nodes MUST NOT be penalized for such\ncollisions, wherever they appear.\n\n===Implementation Notes===\n# For nodes which have sufficient inbound bandwidth, sending a sendcmpct\nmessage with the first integer set to 1 to up to three peers is\nRECOMMENDED. If possible, it is RECOMMENDED that those peers be selected\nbased on their past performance in providing blocks quickly. This will\nallow them to receive some blocks in only 0.5*RTT between them and the\nsending peer. It will also reduce their block transfer latency in other\ncases due to the smaller amount of data transmitted. Nodes MUST NOT send\nsuch sendcmpct messages to all peers, as it encourages wasting outbound\nbandwidth across the network.\n\n# All nodes SHOULD send a sendcmpct message to all appropriate peers.\nThis will reduce their outbound bandwidth usage by allowing their peers\nto request compact blocks instead of full blocks.\n\n# Nodes with limited inbound bandwidth SHOULD request blocks using\nMSG_CMPCT_BLOCK/getblocktxn requests, when possible. While this\nincreases worst-case message round-trips, it is expected to reduce\noverall transfer latency as TCP is more likely to exhibit poor\nthroughput on low-bandwidth nodes.\n\n# Nodes sending cmpctblock messages SHOULD make an attempt to not place\ntoo many transactions into prefilledtxn (ie should limit prefilledtxn to\nonly around 10KB of transactions). When in doubt, nodes SHOULD only\ninclude the coinbase transaction in prefilledtxn.\n\n# Nodes MAY pick one nonce per block they wish to send, and only build a\ncmpctblock message once for all peers which they wish to send a given\nblock to. Nodes SHOULD NOT use the same nonce across multiple different\nblocks.\n\n# Nodes MAY impose additional requirements on when they announce new\nblocks by sending cmpctblock messages. For example, nodes with limited\noutbound bandwidth MAY choose to announce new blocks using inv/header\nmessages (as per BIP130) to conserve outbound bandwidth.\n\n# Note that the MSG_CMPCT_BLOCK section does not require that nodes\nrespond to MSG_CMPCT_BLOCK getdata requests for blocks which they did\nnot recently announce. This allows nodes to calculate cmpctblock\nmessages at announce-time instead of at request-time. Thus, nodes MUST\nNOT request blocks using MSG_CMPCT_BLOCK getdatas unless it is in\nresponse to an inv/headers block announcement (as per BIP130), and MUST\nNOT request blocks using MSG_CMPCT_BLOCK getdatas in response to headers\nmessages which were, themselves, responses to getheaders requests.\n\n# While the current version sends transactions with the same encodings\nas is used in tx messages and elsewhere in the protocol, the version\nfield in sendcmpct is intended to allow this to change in the future.\nFor this reason, it is recommended that the code used to decode\nPrefilledTransaction and BlockTransactions messages be prepared to take\na different transaction encoding, if and when the version field in\nsendcmpct changes in a future BIP.\n\n==Justification==\n\n====Protocol design====\nThere have been many proposals to save wire bytes when relaying blocks.\nMany of them have a two-fold goal of reducing block relay time and thus\nrely on the use of significant processing power in order to avoid\nintroducing additional worst-case RTTs. Because this work is not focused\nprimarily on reducing block relay time, its design is much simpler (ie\ndoes not rely on set reconciliation protocols). Still, in testing at the\ntime of writing, nodes are able to relay blocks without the extra\ngetblocktxn/blocktxn RTT around 90% of the time. With a smart\ncompact-block-announcement policy, it is thus expected that this work\nmight allow blocks to be relayed between nodes in 0.5*RTT instead of\n1.5*RTT at least 75% of the time.\n\n====Use of New VarInts====\nBitcoin has long had a variable-length integer implementation (referred\nto as CompactSize in this document), making a second a strange protocol\nquirk. However, in this protocol most of our variable-length integers\nare between 0 and 2000. For both encodings, small numbers (\u003c100) are\nencoded as 1-byte. For numbers over 250, the CompactSize encoding begins\nto use 3 bytes instead of 1, whereas the New VarInt encoding uses 2.\nBecause the primary motivation for this work is to save bytes during\nblock relay, the extra byte of saving per transaction-difference is\nconsidered worth the extra design complexity.\n\n====Short transaction ID calculation====\nThe short transaction ID calculation is designed to take absolutely\nminimal processing time during block compaction to avoid introducing\nserious DoS vulnerabilities such as those introduced by the\nbloom-filtering in BIP 37. As such, it is possible for a node to\nconstruct one compact-block representation of a block for relay to\nmultiple peers. Additionally, only one cryptographic hash (2 SHA rounds)\nis used when calculating the short transaction IDs for an entire block.\n\nThe XOR-and-add method is used for calculating short transaction IDs\nprimarily because it is fast and is reasonably able to limit the ability\nof an attacker who does not know the block hash or nonce to cause\ncollisions in short transaction IDs. If an attacker were able to cause\nsuch collisions, filling mempools (and, thus, blocks) with them would\ncause poor network propagation of new (or non-attacker, in the case of a\nminer) blocks.\n\nThe 8-byte nonce in short transaction ID calculation is used to\nintroduce additional entropy on a per-node level. While the use of 8\nbytes is sufficient for an attacker to maliciously cause short\ntransaction ID collisions in their own block relay, this would have less\nof an effect than if such an attacker were relaying headers/invs and not\nresponding to requests for the full block.\n\n==Backward compatibility==\n\nOlder clients remain fully compatible and interoperable after this change.\n\n==Implementation==\n\nhttps://github.com/TheBlueMatt/bitcoin/tree/udp\n\n==Acknowledgements==\n\nThanks to Gregory Maxwell for the initial suggestion as well as a lot of\nback-and-forth design and significant testing.\n\n==Copyright==\n\nThis document is placed in the public domain."}