Hi, not sure if headergolf was mentioned yet. It's about very similar ideas: https://github.com/alecalve/headergolf
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Friday, May 8, 2020 2:31 PM, Will Clark via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote: > Hello list, > > I would like to propose a compressed block header scheme for IBD and block > announcements. This proposal is derivative of previous proposals found on > this list (see links in spec below) with some modifications and > clarifications. > > The below specification (also found at > https://github.com/willcl-ark/compressed-block-headers/blob/v1.0/compressed-block-headers.adoc > ) details the compression recommended along with the generated bandwidth > savings in the best-case scenario. > > I look forward to any feedback anyone has to offer on the specification > itself, as well as any additions or objections to the motivation. > > Cheers, > Will > > = Compressed block headers > Will Clark will8cl...@gmail.com > v1.0, May 2020: > :toc: preamble > :toclevels: 4 > > This work is a derivation of these mailing list posts: > > 1. > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014876.html[bitcoin-dev: > "Compressed" headers stream - 2017] (with resurrection > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html[here]) > 2. > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015851.html[bitcoin-dev: > Optimized Header Sync] > > ''' > > == Motivation > > Block headers as exchanged by nodes over the p2p network are currently 81 > bytes each. > > For low bandwidth nodes who are doing a headers-only sync, reducing the > size of the headers can provide a significant bandwidth saving. Also, nodes > can support more header-only peers for IBD and protection against eclipse > attacks if header bandwidth is reduced. > > === Background > > Currently headers are sent over the p2p network as a vector of > `block_headers`, which are composed of the following sized fields: > > [cols="<,>"] > > > |=== > |Field |Size > > |Version |4 bytes > |Previous block hash |32 bytes > |Merkle root hash |32 bytes > |Time |4 bytes > |nBits |4 bytes > |nonce |4 bytes > |txn_count |1 byte > |Total |81 bytes > |=== > > Some fields can be removed completely, others can be compressed under certain > conditions. > > == Proposed specification > > === block_header2 data type > > The following table illustrates the proposed `block_header2` data type > specification. > > [cols="<,>,>"] > |=== > |Field |Size |Compressed > > |Bitfield |1 byte | 1 byte > |Version |4 bytes |0 \| 4 bytes > |Previous block hash |32 bytes |0 \| 32 bytes > |Merkle root hash |32 bytes |32 bytes > |Time |4 bytes |2 \| 4 bytes > |nBits |4 bytes |0 \| 4 bytes > |nonce |4 bytes |4 bytes > |Total |81 bytes |range: 39 - 81 bytes > |=== > > This compression results in a maximum reduction from an 81 byte header to > best-case 39 byte header. With 629,474 blocks in the current blockchain, a > continuous header sync from genesis (requiring a single full 81 byte header > followed by only compressed `block_header2`) has been tested to have its > required bandwidth reduced from 50.98MB down to 25.86MB, a saving of 49%. > > ==== Bitfield > > To make parsing of header messages easier and further increase header > compression, a single byte bitfield was suggested by gmaxwell > footnote:[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015397.html]. > We propose the following amended bitfield meanings (bits re-ordered to match > `headers2` field order): > > [cols="<,<"] > |=== > |Bit |Meaning + field size to read > > |0 + > 1 + > 2 |version: same as the last distinct value 1st ... 7th (0 byte field) or a > new 32bit distinct value (4 byte field). > |3 |prev_block_hash: is omitted (0 byte field) or included (32 byte field) > |4 |timestamp: as small offset (2 byte field) or full (4 byte field). > |5 |nbits: same as last header (0 byte field) or new (4 byte field). > |6 |possibly to signal "more headers follow" to make the encoding > self-delimiting. > |7 |currently undefined > |=== > > This bitfield adds 1 byte for every block in the chain, for a current total > increase of 629,474B. > > ==== Version > > In most cases the Version field will be identical to one referenced in one of > the previous 7 unique versions, as indicated by bits 0,1,2 of the Bitfield. > > To block 629,474 there were 616,137 blocks whose version was in the previous > 7 distinct versions, and only 13,338 blocks whose version was not, this > includes any version bit manipulation done via overt ASIC boost. > > [cols=">,>,>,>"] > |=== > |Genesis to block |Current (B) |Compressed (B) |Saving (%) > > |629,474 |2,517,896 |53,352 |98 > |=== > > ==== Previous block hash > > The previous block hash will always be the > `SHA256(SHA256(<previous_header>))` so is redundant, presuming you have the > previous header in the chain. > > [cols=">,>,>,>"] > |=== > |Genesis to block |Current (B) |Compressed (B) |Saving (%) > > |629,474 |20,143,168 |0 |100 > |=== > > ==== Time > > The timestamp (in seconds) is consensus bound, based both on the time in the > previous > header: `MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60 = 7200`, and being greater than > the `MedianTimePast` of the previous 11 blocks. Therefore this can be safely > represented as an offset from the previous headers' timestamp using a 2 byte > `signed short int`. > > [cols=">,>,>,>"] > |=== > |Genesis to block |Current (B) |Compressed (B) |Saving (%) > > |629,474 |2,517,896 |1,258,952 |50 > |=== > > ==== nBits > > nBits currently changes once every 2016 blocks. It could be entirely > calculated by the client from the timestamps of the previous 2015 blocks > footnote:[2015 blocks are used in the adjustment calculation due to an > off-by-one error: > https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772";]. > > To simplify 'light' client implementations which would otherwise require > consensus-valid calculation of the adjustments, we propose to transmit this > according to the <<Bitfield>> specification above. > > To block 629,474 there have been 298 nBits adjustments (vs an expected 311 -- > there was none before block 32,256). > > [cols=">,>,>,>"] > |=== > |Genesis to block |Current (B) |Compressed (B) |Saving (%) > > |629,474 |2,517,896 |1,196 |99.6 > |=== > > ==== txn_count > > txn_count is included to make parsing of these messages compatible with > parsing of `block` messages > footnote:[https://bitcoin.stackexchange.com/questions/2104/why-is-the-block-header-txn-count-field-always-zero]. > Therefore this field and its associated byte can be removed for transmission > of compact headers. > > [cols=">,>,>,>"] > |=== > |Genesis to block |Current (B) |Compressed (B) |Saving (%) > > |629,474 |629,474 |0 |100 > |=== > > === Service Bit > > A new service bit would be required so that the nodes can advertise their > ability to supply compact headers. > > === P2P Messages > > Three new messages would be used by nodes that enable compact block header > support, two query messages: `getheaders2` and `sendheaders2` and one > response: `headers2`. > > ==== `getheaders2` -- Requesting compact headers > > The new p2p message required to request compact block headers would require > the same fields as the current `getheaders` message: > > [cols=">,<,<,<"] > |=== > |Field Size |Description |Data type |Comments > > |4 |version |uint32_t |the protocol version > |1+ |hash count |var_int |number of block locator hash entries > |32+ |block locator hashes |char[32] |block locator object; newest back to > genesis block (dense to start, but then sparse) > |32 |hash_stop |char[32] |hash of the last desired block header; set to zero > to get as many blocks as possible (2000) > |=== > > ==== `sendheaders2` -- Request compact header announcements > > Since > https://github.com/bitcoin/bips/blob/master/bip-0130.mediawiki[BIP-130], > nodes have been able to request to receive new headers directly in `headers` > messages, rather than via an `inv` of the new block hash and subsequent > `getheader` request and `headers` response (followed by a final `getdata` to > get the tip block itself, if desired). This is requested by transmitting an > empty `sendheaders` message after the version handshake is complete.] > > Upon receipt of this message, the node is permitted, but not required, to > preemptively announce new headers with the `headers2` message (instead of > `inv`). Preemptive header announcement is supported by the protocol version ≥ > 70012 | Bitcoin Core version ≥ 0.12.0. > > For the motivational use-case it makes sense to also update this mechanism to > support sending header updates using compact headers using a new message. > > ==== `headers2` -- Receiving compact headers > > A `headers2` message is returned in response to `getheaders2` or at new > header announcement following a `sendheaders2` request. It contains both > `length` and `headers` fields. The `headers` field contains a variable length > vector of `block_header2`: > > |=== > |Field Size |Description |Data type |Comments > > |1+ |length |var_int |Length of `headers` > |39-81x? |headers |block_header2[] |Compressed block headers in > <<block_header2 data type>> format > |=== > > === Implementation > > - The first header in the first `block_header2[]` vector to a > newly-connected client MUST contain the full > nBits`,`timestamp`,`version`and`prev_block_hash`fields, along with a > correctly populated`bitfield` byte. > > - Subsequent headers in a contiguous vector SHOULD follow the compressed > <<block_header2 data type>> format. > > - Subsequent compressed headers supplied to an already-connected client > (requesting compressed headers), SHOULD follow the compressed <<block_header2 > data type>> format. > > > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev _______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
