From: Will Clark <will8clark@gmail.com>
Content-Type: text/plain;
	charset=utf-8
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.80.23.2.2\))
Message-Id: <40DB3DBE-A1C9-4D20-A3C7-F5660307D9D7@gmail.com>
Date: Fri, 8 May 2020 13:31:06 +0100
To: bitcoin-dev@lists.linuxfoundation.org
Subject: [bitcoin-dev] Compressed block headers
Precedence: list

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/compresse=
d-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


=3D Compressed block headers
Will Clark <will8clark@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/0153=
85.html[here])

2. =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015851.=
html[bitcoin-dev: Optimized Header Sync]

'''

=3D=3D 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.

=3D=3D=3D Background

Currently headers are sent over the p2p network as a vector of =
`block_headers`, which are composed of the following sized fields:

[cols=3D"<,>"]
|=3D=3D=3D
|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
|=3D=3D=3D

Some fields can be removed completely, others can be compressed under =
certain conditions.

=3D=3D Proposed specification

=3D=3D=3D block_header2 data type

The following table illustrates the proposed `block_header2` data type =
specification.

[cols=3D"<,>,>"]
|=3D=3D=3D
|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
|=3D=3D=3D

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%.

=3D=3D=3D=3D 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-Dec=
ember/015397.html]. We propose the following amended bitfield meanings =
(bits re-ordered to match `headers2` field order):

[cols=3D"<,<"]
|=3D=3D=3D
|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
|=3D=3D=3D

This bitfield adds 1 byte for every block in the chain, for a current =
total increase of 629,474B.

=3D=3D=3D=3D 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=3D">,>,>,>"]
|=3D=3D=3D
|Genesis to block |Current (B) |Compressed (B) |Saving (%)

|629,474          |2,517,896   |53,352         |98
|=3D=3D=3D

=3D=3D=3D=3D 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=3D">,>,>,>"]
|=3D=3D=3D
|Genesis to block |Current (B) |Compressed (B) |Saving (%)

|629,474          |20,143,168  |0              |100
|=3D=3D=3D

=3D=3D=3D=3D Time

The timestamp (in seconds) is consensus bound, based both on the time in =
the previous
header: `MAX_FUTURE_BLOCK_TIME =3D 2 * 60 * 60 =3D 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=3D">,>,>,>"]
|=3D=3D=3D
|Genesis to block |Current (B) |Compressed (B) |Saving (%)

|629,474          |2,517,896   |1,258,952      |50
|=3D=3D=3D

=3D=3D=3D=3D 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=3D43692.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=3D">,>,>,>"]
|=3D=3D=3D
|Genesis to block |Current (B) |Compressed (B) |Saving (%)

|629,474          |2,517,896   |1,196          |99.6
|=3D=3D=3D

=3D=3D=3D=3D 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-bloc=
k-header-txn-count-field-always-zero]. Therefore this field and its =
associated byte can be removed for transmission of compact headers.

[cols=3D">,>,>,>"]
|=3D=3D=3D
|Genesis to block |Current (B) |Compressed (B) |Saving (%)

|629,474          |629,474     |0              |100
|=3D=3D=3D

=3D=3D=3D Service Bit

A new service bit would be required so that the nodes can advertise =
their ability to supply compact headers.

=3D=3D=3D 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`.

=3D=3D=3D=3D `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=3D">,<,<,<"]
|=3D=3D=3D
|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)
|=3D=3D=3D

=3D=3D=3D=3D `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 =E2=89=A5 70012 | Bitcoin Core version =E2=89=A5 =
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.

=3D=3D=3D=3D `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`:

|=3D=3D=3D
|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
|=3D=3D=3D

=3D=3D=3D 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.