"Compressed" headers stream
8 messages, 28 Aug to 4 Sep 2017. Started by Riccardo Casatta.
Riccardo Casatta (2), Greg Sanders (2), Peter Todd (2), Gregory Maxwell, Kalle Rosenbaum
Hi everyone,
the Bitcoin headers are probably the most condensed and important piece of data in the world, their demand is expected to grow.
When sending a stream of continuous block headers, a common case in IBD and in disconnected clients, I think there is a possible optimization of the transmitted data: The headers after the first could avoid transmitting the previous hash cause the receiver could compute it by double hashing the previous header (an operation he needs to do anyway to verify PoW). In a long stream, for example 2016 headers, the savings in bandwidth are about 32/80 ~= 40% without compressed headers 2016*80=161280 bytes with compressed headers 80+2015*48=96800 bytes
What do you think?
In OpenTimestamps calendars we are going to use this compression to give lite-client a reasonable secure proofs (a full node give higher security but isn't feasible in all situations, for example for in-browser verification) To speed up sync of a new client Electrum starts with the download of a file <https://headers.electrum.org/blockchain_headers> ~36MB containing the first 477637 headers. For this kind of clients could be useful a common http API with fixed position chunks to leverage http caching. For example /headers/2016/0 returns the headers from the genesis to the 2015 header included while /headers/2016/1 gives the headers from the 2016th to the 4031. Other endpoints could have chunks of 20160 blocks or 201600 such that with about 10 http requests a client could fast sync the headers
Is there any reason to believe that you need Bitcoin "full security" at all for timestamping?
On Mon, Aug 28, 2017 at 11:50 AM, Riccardo Casatta via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (43 lines)
> Hi everyone, > > the Bitcoin headers are probably the most condensed and important piece of > data in the world, their demand is expected to grow. > > When sending a stream of continuous block headers, a common case in IBD > and in disconnected clients, I think there is a possible optimization of > the transmitted data: > The headers after the first could avoid transmitting the previous hash > cause the receiver could compute it by double hashing the previous header > (an operation he needs to do anyway to verify PoW). > In a long stream, for example 2016 headers, the savings in bandwidth are > about 32/80 ~= 40% > without compressed headers 2016*80=161280 bytes > with compressed headers 80+2015*48=96800 bytes > > What do you think? > > > In OpenTimestamps calendars we are going to use this compression to give > lite-client a reasonable secure proofs (a full node give higher security > but isn't feasible in all situations, for example for in-browser > verification) > To speed up sync of a new client Electrum starts with the download of a > file <https://headers.electrum.org/blockchain_headers> ~36MB containing > the first 477637 headers. > For this kind of clients could be useful a common http API with fixed > position chunks to leverage http caching. For example /headers/2016/0 > returns the headers from the genesis to the 2015 header included while > /headers/2016/1 gives the headers from the 2016th to the 4031. > Other endpoints could have chunks of 20160 blocks or 201600 such that with > about 10 http requests a client could fast sync the headers > > > -- > Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta> > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > >
2017-08-28 18:13 GMT+02:00 Greg Sanders <gsanders87@gmail•com>:
Quoted text (3 lines)
> Is there any reason to believe that you need Bitcoin "full security" at > all for timestamping? >
This is a little bit out of the main topic of the email which is the savings in bandwidth in transmitting headers, any comment about that?
P.S. As a personal experience timestamping is nowadays used to prove date and integrity of private databases containing a lot of value, so yes, in that cases I will go with Bitcoin "full security"
Quoted text (48 lines)
> > On Mon, Aug 28, 2017 at 11:50 AM, Riccardo Casatta via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org> wrote: > >> Hi everyone, >> >> the Bitcoin headers are probably the most condensed and important piece >> of data in the world, their demand is expected to grow. >> >> When sending a stream of continuous block headers, a common case in IBD >> and in disconnected clients, I think there is a possible optimization of >> the transmitted data: >> The headers after the first could avoid transmitting the previous hash >> cause the receiver could compute it by double hashing the previous header >> (an operation he needs to do anyway to verify PoW). >> In a long stream, for example 2016 headers, the savings in bandwidth are >> about 32/80 ~= 40% >> without compressed headers 2016*80=161280 bytes >> with compressed headers 80+2015*48=96800 bytes >> >> What do you think? >> >> >> In OpenTimestamps calendars we are going to use this compression to give >> lite-client a reasonable secure proofs (a full node give higher security >> but isn't feasible in all situations, for example for in-browser >> verification) >> To speed up sync of a new client Electrum starts with the download of a >> file <https://headers.electrum.org/blockchain_headers> ~36MB containing >> the first 477637 headers. >> For this kind of clients could be useful a common http API with fixed >> position chunks to leverage http caching. For example /headers/2016/0 >> returns the headers from the genesis to the 2015 header included while >> /headers/2016/1 gives the headers from the 2016th to the 4031. >> Other endpoints could have chunks of 20160 blocks or 201600 such that >> with about 10 http requests a client could fast sync the headers >> >> >> -- >> Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta> >> >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation•org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> >> >
Well, if anything my question may bolster your use-case. If there's a heavier chain that is invalid, I kind of doubt it matters for timestamping reasons.
/digression
On Mon, Aug 28, 2017 at 12:25 PM, Riccardo Casatta < riccardo.casatta@gmail•com> wrote:
Quoted text (69 lines)
> > 2017-08-28 18:13 GMT+02:00 Greg Sanders <gsanders87@gmail•com>: > >> Is there any reason to believe that you need Bitcoin "full security" at >> all for timestamping? >> > > This is a little bit out of the main topic of the email which is the > savings in bandwidth in transmitting headers, any comment about that? > > > P.S. As a personal experience timestamping is nowadays used to prove date > and integrity of private databases containing a lot of value, so yes, in > that cases I will go with Bitcoin "full security" > > >> >> On Mon, Aug 28, 2017 at 11:50 AM, Riccardo Casatta via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation•org> wrote: >> >>> Hi everyone, >>> >>> the Bitcoin headers are probably the most condensed and important piece >>> of data in the world, their demand is expected to grow. >>> >>> When sending a stream of continuous block headers, a common case in IBD >>> and in disconnected clients, I think there is a possible optimization of >>> the transmitted data: >>> The headers after the first could avoid transmitting the previous hash >>> cause the receiver could compute it by double hashing the previous header >>> (an operation he needs to do anyway to verify PoW). >>> In a long stream, for example 2016 headers, the savings in bandwidth are >>> about 32/80 ~= 40% >>> without compressed headers 2016*80=161280 bytes >>> with compressed headers 80+2015*48=96800 bytes >>> >>> What do you think? >>> >>> >>> In OpenTimestamps calendars we are going to use this compression to give >>> lite-client a reasonable secure proofs (a full node give higher security >>> but isn't feasible in all situations, for example for in-browser >>> verification) >>> To speed up sync of a new client Electrum starts with the download of a >>> file <https://headers.electrum.org/blockchain_headers> ~36MB containing >>> the first 477637 headers. >>> For this kind of clients could be useful a common http API with fixed >>> position chunks to leverage http caching. For example /headers/2016/0 >>> returns the headers from the genesis to the 2015 header included while >>> /headers/2016/1 gives the headers from the 2016th to the 4031. >>> Other endpoints could have chunks of 20160 blocks or 201600 such that >>> with about 10 http requests a client could fast sync the headers >>> >>> >>> -- >>> Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta> >>> >>> _______________________________________________ >>> bitcoin-dev mailing list >>> bitcoin-dev@lists•linuxfoundation•org >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>> >>> >> > > > -- > Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta> >
On Mon, Aug 28, 2017 at 3:50 PM, Riccardo Casatta via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (17 lines)
> Hi everyone, > > the Bitcoin headers are probably the most condensed and important piece of > data in the world, their demand is expected to grow. > > When sending a stream of continuous block headers, a common case in IBD and > in disconnected clients, I think there is a possible optimization of the > transmitted data: > The headers after the first could avoid transmitting the previous hash cause > the receiver could compute it by double hashing the previous header (an > operation he needs to do anyway to verify PoW). > In a long stream, for example 2016 headers, the savings in bandwidth are > about 32/80 ~= 40% > without compressed headers 2016*80=161280 bytes > with compressed headers 80+2015*48=96800 bytes > > What do you think?
You are leaving a lot of bytes on the table.
The bits field can only change every 2016 blocks (4 bytes per header), the timestamp can not be less than the median of the last 11 and is usually only a small amount over the last one (saves 2 bytes per header), the block version is usually one of the last few (save 3 bytes per header).
But all these things improvements are just a constant factor. I think you want the compact SPV proofs described in the appendix of the sidechains whitepaper which creates log scaling proofs.
2017-08-28 19:12 GMT+02:00 Gregory Maxwell via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org>:
Quoted text (7 lines)
> > The bits field can only change every 2016 blocks (4 bytes per header), > the timestamp can not be less than the median of the last 11 and is > usually only a small amount over the last one (saves 2 bytes per > header), the block version is usually one of the last few (save 3 > bytes per header). >
... and I guess the nonce can be arbitrarily truncated as well, just brute force the missing bits :-P.
Quoted text (4 lines)
> But all these things improvements are just a constant factor. I think > you want the compact SPV proofs described in the appendix of the > sidechains whitepaper which creates log scaling proofs. >
I think that my blog post on compact spv proofs can be helpful also. It tries to make the pretty compact formulations in the sidechains paper a bit more graspable by normal people.
http://popeller.io/index.php/2016/09/15/compact-spv-proofs/
Kalle
On Mon, Aug 28, 2017 at 05:12:15PM +0000, Gregory Maxwell via bitcoin-dev wrote:
Quoted text (11 lines)
> You are leaving a lot of bytes on the table. > > The bits field can only change every 2016 blocks (4 bytes per header), > the timestamp can not be less than the median of the last 11 and is > usually only a small amount over the last one (saves 2 bytes per > header), the block version is usually one of the last few (save 3 > bytes per header). > > But all these things improvements are just a constant factor. I think > you want the compact SPV proofs described in the appendix of the > sidechains whitepaper which creates log scaling proofs.
Note that I'm already planning on OpenTimestamps having infrastructure for trusted validity attestations; log scaling proofs alone only prove total work, not validity. Timestamping has all kinds of very dubious security properties when done via proof-of-work, due to various ways that miners can get away with inaccurate block times. In particular, setting a block time backwards is something that miners can do, particularly with majority hashing power, which is the exact thing we're trying to prevent in a timestamp proof.
This all makes me dubious about risking further weakening of this already weak security with compact SPV proofs; we'd need a lot more analysis to understand what we're risking. Also note that we can ship a known-good sum-merkle-tree tip hash with the software, which further reduces initial download bandwidth needed to get the block headers on top of this obviously safe eliding of redundant hashes.
On Mon, Aug 28, 2017 at 12:26:48PM -0400, Greg Sanders via bitcoin-dev wrote:
Quoted text (3 lines)
> Well, if anything my question may bolster your use-case. If there's a > heavier chain that is invalid, I kind of doubt it matters for timestamping > reasons.
Timestamping can easily be *more* vulnerable to malicious miners than financial applications for a number of reasons, including the fact that there's no financial feedback loop of miners destroying the value of the coins they produce - timestamping is a non-financial piggy-back application that doesn't directly interact with the Bitcoin economy, beyond a trival number of timestamp transactions.