Date: Mon, 11 May 2020 12:26:54 +0000
To: Will Clark <will8clark@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: Robin Linus <robinlinus@protonmail.com>
Reply-To: Robin Linus <robinlinus@protonmail.com>
Message-ID: <KGgPRvsU3ktiqmnrAqu4svH3mF8KR5sXLGDSCYf940WIuNTvaUAsYr040hmIS1GV3pRdRqDfWLHoxc2xFTyyOy8S8GVZWv5jolfSix64AxQ=@protonmail.com>
In-Reply-To: <40DB3DBE-A1C9-4D20-A3C7-F5660307D9D7@gmail.com>
References: <40DB3DBE-A1C9-4D20-A3C7-F5660307D9D7@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Compressed block headers
Precedence: list

Hi,

not sure if headergolf was mentioned yet. It's about very similar ideas: ht=
tps://github.com/alecalve/headergolf


=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 Original Me=
ssage =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90
On Friday, May 8, 2020 2:31 PM, Will Clark via bitcoin-dev <bitcoin-dev@lis=
ts.linuxfoundation.org> wrote:

> Hello list,
>
> I would like to propose a compressed block header scheme for IBD and bloc=
k announcements. This proposal is derivative of previous proposals found on=
 this list (see links in spec below) with some modifications and clarificat=
ions.
>
> The below specification (also found at https://github.com/willcl-ark/comp=
ressed-block-headers/blob/v1.0/compressed-block-headers.adoc ) details the =
compression recommended along with the generated bandwidth savings in the b=
est-case scenario.
>
> I look forward to any feedback anyone has to offer on the specification i=
tself, 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/0=
14876.html[bitcoin-dev: "Compressed" headers stream - 2017] (with resurrect=
ion https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/0=
15385.html[here])
> 2.  https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/01=
5851.html[bitcoin-dev: Optimized Header Sync]
>
>     '''
>
>     =3D=3D Motivation
>
>     Block headers as exchanged by nodes over the p2p network are currentl=
y 81 bytes each.
>
>     For low bandwidth nodes who are doing a headers-only sync, reducing t=
he size of the headers can provide a significant bandwidth saving. Also, no=
des can support more header-only peers for IBD and protection against eclip=
se 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 cer=
tain conditions.
>
> =3D=3D Proposed specification
>
> =3D=3D=3D block_header2 data type
>
> The following table illustrates the proposed `block_header2` data type sp=
ecification.
>
> [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 heade=
r 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 com=
pression, 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 m=
atch `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-de=
limiting.
> |7 |currently undefined
> |=3D=3D=3D
>
> This bitfield adds 1 byte for every block in the chain, for a current tot=
al increase of 629,474B.
>
> =3D=3D=3D=3D Version
>
> In most cases the Version field will be identical to one referenced in on=
e of the previous 7 unique versions, as indicated by bits 0,1,2 of the Bitf=
ield.
>
> To block 629,474 there were 616,137 blocks whose version was in the previ=
ous 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 t=
he 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 great=
er than the `MedianTimePast` of the previous 11 blocks. Therefore this can =
be safely represented as an offset from the previous headers' timestamp usi=
ng 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 calc=
ulated by the client from the timestamps of the previous 2015 blocks footno=
te:[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 31=
1 -- 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 p=
arsing of `block` messages footnote:[https://bitcoin.stackexchange.com/ques=
tions/2104/why-is-the-block-header-txn-count-field-always-zero]. Therefore =
this field and its associated byte can be removed for transmission of compa=
ct 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 heade=
r support, two query messages: `getheaders2` and `sendheaders2` and one res=
ponse: `headers2`.
>
> =3D=3D=3D=3D `getheaders2` -- Requesting compact headers
>
> The new p2p message required to request compact block headers would requi=
re 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 t=
o genesis block (dense to start, but then sparse)
> |32 |hash_stop |char[32] |hash of the last desired block header; set to z=
ero 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 `h=
eaders` messages, rather than via an `inv` of the new block hash and subseq=
uent `getheader` request and `headers` response (followed by a final `getda=
ta` to get the tip block itself, if desired). This is requested by transmit=
ting 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 mechanis=
m to support sending header updates using compact headers using a new messa=
ge.
>
> =3D=3D=3D=3D `headers2` -- Receiving compact headers
>
> A `headers2` message is returned in response to `getheaders2` or at new h=
eader announcement following a `sendheaders2` request. It contains both `le=
ngth` 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_h=
eader2 data type>> format
> |=3D=3D=3D
>
> =3D=3D=3D Implementation
>
> -   The first header in the first `block_header2[]` vector to a newly-con=
nected client MUST contain the full nBits`,`timestamp`,`version`and`prev_bl=
ock_hash`fields, along with a correctly populated`bitfield` byte.
>
> -   Subsequent headers in a contiguous vector SHOULD follow the compresse=
d <<block_header2 data type>> format.
>
> -   Subsequent compressed headers supplied to an already-connected client=
 (requesting compressed headers), SHOULD follow the compressed <<block_head=
er2 data type>> format.
>
>
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev