Re: [bitcoin-dev] Compressed block headers
I've been looking at using compressed block headers from the perspective of a node that wants to use SMS messages to sync block headers. I realized that it would be helpful if sendheaders2 took a parameter for how often to send compact blockheaders. For example, in the case of an SMS transport layer, it would make sense to request 4 headers at a time to optimally fill a 160 byte SMS message. Although using SMS messages would be about the most expensive way to receive block headers, it is also the most universally available to smartphone users, even where mobile data might be expensive or unavailable. If we assume an SMS costs a bulk sender 0.025 USD per SMS, then sending 4 at a time (4 x 39 + 1 byte < 160 byte max SMS) reduces costs 1/4 to 252 instead of 1008 messages at a total weekly cost of ~7 instead of 26 USD. Still not ideal, but a huge savings. Since you're proposing a new message anyway, it doesn't break compatibility to add a parameter for how often sendheaders2 chunks up recent headers. On Fri, May 8, 2020 at 3:34 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 > 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
Re: [bitcoin-dev] Compressed block headers
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 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())` so is redundant, presuming you have the > previous header in the chain. > > [cols=">,>,>,>"] > |=== > |Genesis
Re: [bitcoin-dev] Compressed block headers
Thanks for resurrecting this idea for discussion Will. I see three reasons for reducing block header bandwidth: 1. support for long range block header broadcast via alternative communication modalities like radio where every byte counts 2. where repurposed mobile devices with SPV wallets are used because metered bandwidth and hardware costs are high relative to income 3. full nodes could potentially support twice as many header only peers (is that a thing?) for better eclipse protection Nodes could also run an additional daemon (eg. electrs) that serves compressed block headers to light clients, but then it would be less likely to see widespread use to reduce bandwidth between full nodes. What are the negatives? - higher computation? probably minimal compared to serving the same uncompressed headers. - memory for caching the last few versions? bounded to last seven, so not too large. - complexity/bugs? minor and opt in for node operators, though you could argue the gain isn't worth any kind of change for nodes with high bandwidth connections. - use of low-bandwidth light clients should not be encouraged? that is a separate discussion, but I do not currently see any proposals to remove light client support. I'm curious what other people think. Are the motivations enough to justify a change to the protocol that produces a high percentage (but low absolute) bandwidth reduction for transmitting block headers? -- Richard On Fri, May 8, 2020 at 3:34 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 > 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
[bitcoin-dev] Compressed block headers
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 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())` 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
