From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id CBF4EC016F for ; Mon, 11 May 2020 12:27:06 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id BA9558862C for ; Mon, 11 May 2020 12:27:06 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id gk0QLvNEn39r for ; Mon, 11 May 2020 12:27:04 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40130.protonmail.ch (mail-40130.protonmail.ch [185.70.40.130]) by hemlock.osuosl.org (Postfix) with ESMTPS id 5AA79884C9 for ; Mon, 11 May 2020 12:27:04 +0000 (UTC) Date: Mon, 11 May 2020 12:26:54 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1589200021; bh=AFImJhi6yjCsq06UCkkoMpekklL5zl6NLk/mDxw7JLM=; h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From; b=c5KdJTBTc222R8AvNyZ0HcTZ/jLgkIwx9kfs3uk73cho6dgwWB1Nz7/DPnjoaj0X/ 0lIbxXPYfdsmRhBV7RzlcKh2VK1zUqlk3g9+ACwuD4R6YMS84RB6aXylTBLq/CDcY9 Wx2ZHKDmZBvCGEke2L2BIEi5PNyBwd6mEwbkzPz8= To: Will Clark , Bitcoin Protocol Discussion From: Robin Linus Reply-To: Robin Linus Message-ID: 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 X-Mailman-Approved-At: Mon, 11 May 2020 12:32:35 +0000 Subject: Re: [bitcoin-dev] Compressed block headers X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 11 May 2020 12:27:07 -0000 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 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())` 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 <> 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 <> 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 <> format. > > - Subsequent compressed headers supplied to an already-connected client= (requesting compressed headers), SHOULD follow the compressed <> format. > > > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev