Re: [bitcoin-dev] Optimized Header Sync

2018-04-03 Thread Jim Posen via bitcoin-dev 
Thank you for your feedback AJ and Riccardo.

Nice observation about using nBits from every 2016th block as a short
specifier of chain work. You can get some savings from the 4 byte nBits
encoding over VLQ for total chain work as in my spec.

I tried it out on the current chain. At block height 516,387, there are 258
total checkpoints in the response payload with an interval of 2016. The
size of the checkpts message is:

- 9,304 bytes using hash + nBits
- 10,934 bytes using hash + chain work delta encoded as VLQ
- 11,030 bytes using hash + chain work total encoded as VLQ

The saving from using deltas instead of the total seems negligible to me
especially considering the additional computation it requires. Going from
total chain work as VLQ to nBits is a 16% savings in the size of a checkpts
message. According to some rather rough benchmarks, it takes ~3us to
generate the message with nBits versus ~105us to generate each message with
VLQ chain work (including block index lookups and serialization time).

The downside, however, is that the new P2P message would be tightly coupled
to a specific parameter in Bitcoin's consensus protocol, and one that is
changed in many alt chains. Also, it would require that checkpoints can
only be fetched at intervals of 2016, instead of intervals chosen by the
clients. Being able to specify the interval is a very nice property for
longer chains, where a client may select really large intervals, then
bisect that range even further to request a smaller PoW sample (eg. start
by fetching every 10,000th, then every 100th).

Personally, I strongly think using total chain work instead of nBits is the
right tradeoff and is worth the extra 1KB. I'm curious to hear others'
opinions. Note that the checkpoints message is only fetched once per peer
per download from genesis. Subsequent catchups only fetch checkpoints from
the locator fork point. I also don't find the caching argument compelling
-- the time to generate checkpts response messages is fast enough anyway.

I also finally got around to pulling numbers on the space savings from the
nVersion omission. As a reminder of how this works, three bits in the
encoding indicator represent a value 1-7 of the distance in block height
since another block with the same version. Looking at the current Bitcoin
main chain, this is a table of the occurrences of these values:

Height distance # of Blocks
1 469537
2 22301
3 8833
4 4368
5 2633
6 1630
7 1114
 8+ 5967
You can read this as "469,537 blocks have the same version as their
parent", "22,301 have the same version as their parent's parent", etc.
Given the information in this table, we may consider only allocating 2 bits
in the encoding header rather than 3.

On Fri, Mar 30, 2018 at 1:06 AM, Riccardo Casatta <
[email protected]> wrote:

> Yes, I think the checkpoints and the compressed headers streams should be
> handled in chunks of 2016 headers and queried by chunk number instead of
> height, falling back to current method if the chunk is not full yet.
>
> This is cache friendly and allows to avoid bit 0 and bit 1 in the bitfield
> (because they are always 1 after the first header in the chunk of 2016).
>
> 2018-03-30 8:14 GMT+02:00 Anthony Towns :
>
>> On Thu, Mar 29, 2018 at 05:50:30PM -0700, Jim Posen via bitcoin-dev wrote:
>> > Taken a step further though, I'm really interested in treating the
>> checkpoints
>> > as commitments to chain work [...]
>>
>> In that case, shouldn't the checkpoints just be every 2016 blocks and
>> include the corresponding bits value for that set of blocks?
>>
>> That way every node commits to (approximately) how much work their entire
>> chain has by sending something like 10kB of data (currently), and you
>> could verify the deltas in each node's chain's target by downloading the
>> 2016 headers between those checkpoints (~80kB with the proposed compact
>> encoding?) and checking the timestamps and proof of work match both the
>> old target and the new target from adjacent checkpoints.
>>
>> (That probably still works fine even if there's a hardfork that allows
>> difficulty to adjust more frequently: a bits value at block n*2016 will
>> still enforce *some* lower limit on how much work blocks n*2016+{1..2016}
>> will have to contribute; so will still allow you to estimate how much work
>> will have been done, it may just be less precise than the estimate you
>> could
>> generate now)
>>
>> Cheers,
>> aj
>>
>>
>
>
> --
> Riccardo Casatta - @RCasatta 
>
___
bitcoin-dev mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Optimized Header Sync

2018-04-01 Thread Riccardo Casatta via bitcoin-dev 
Yes, I think the checkpoints and the compressed headers streams should be
handled in chunks of 2016 headers and queried by chunk number instead of
height, falling back to current method if the chunk is not full yet.

This is cache friendly and allows to avoid bit 0 and bit 1 in the bitfield
(because they are always 1 after the first header in the chunk of 2016).

2018-03-30 8:14 GMT+02:00 Anthony Towns :

> On Thu, Mar 29, 2018 at 05:50:30PM -0700, Jim Posen via bitcoin-dev wrote:
> > Taken a step further though, I'm really interested in treating the
> checkpoints
> > as commitments to chain work [...]
>
> In that case, shouldn't the checkpoints just be every 2016 blocks and
> include the corresponding bits value for that set of blocks?
>
> That way every node commits to (approximately) how much work their entire
> chain has by sending something like 10kB of data (currently), and you
> could verify the deltas in each node's chain's target by downloading the
> 2016 headers between those checkpoints (~80kB with the proposed compact
> encoding?) and checking the timestamps and proof of work match both the
> old target and the new target from adjacent checkpoints.
>
> (That probably still works fine even if there's a hardfork that allows
> difficulty to adjust more frequently: a bits value at block n*2016 will
> still enforce *some* lower limit on how much work blocks n*2016+{1..2016}
> will have to contribute; so will still allow you to estimate how much work
> will have been done, it may just be less precise than the estimate you
> could
> generate now)
>
> Cheers,
> aj
>
>


-- 
Riccardo Casatta - @RCasatta 
___
bitcoin-dev mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Optimized Header Sync

2018-03-29 Thread Anthony Towns via bitcoin-dev 
On Thu, Mar 29, 2018 at 05:50:30PM -0700, Jim Posen via bitcoin-dev wrote:
> Taken a step further though, I'm really interested in treating the checkpoints
> as commitments to chain work [...]

In that case, shouldn't the checkpoints just be every 2016 blocks and
include the corresponding bits value for that set of blocks?

That way every node commits to (approximately) how much work their entire
chain has by sending something like 10kB of data (currently), and you
could verify the deltas in each node's chain's target by downloading the
2016 headers between those checkpoints (~80kB with the proposed compact
encoding?) and checking the timestamps and proof of work match both the
old target and the new target from adjacent checkpoints.

(That probably still works fine even if there's a hardfork that allows
difficulty to adjust more frequently: a bits value at block n*2016 will
still enforce *some* lower limit on how much work blocks n*2016+{1..2016}
will have to contribute; so will still allow you to estimate how much work
will have been done, it may just be less precise than the estimate you could
generate now)

Cheers,
aj

___
bitcoin-dev mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Optimized Header Sync

2018-03-29 Thread Jim Posen via bitcoin-dev 
Thanks for giving it a read and for sparking the discussion with your
observation about the 40% savings from dropping prev_hash!


> Thought this wasn't effective in case overt asic boost get widely adopted,
> but then I understood that at the moment only two bits of version get
> scrambled by that technique so this looks fine, maybe add a comment about
> this so the reader doesn't get the same initial doubt I got.
>

I still need to compute for historical blocks how many could have an
omitted version. Will post back with that when I get results. If overt ASIC
Boost made this less effective, that would be unfortunate, but so be it.


> My feeling is that encoding of the headers and checkpoints/parallel
> download are separate subjects for two BIPS.
> About the checkpoints I don't grasp why they are useful since an attacker
> could lie about them but maybe I am missing something...
>

Yeah, I guess the background wasn't explained in the BIP itself. After your
original post on the mailing list, there were suggestions that instead of
modifying the format of existing messages, it would be better do create a
new headers message. And as long as we're designing a new headers message,
we should change the semantics to allow parallel download. But if you want
to download from peers in parallel, you need to get a summary of the blocks
that they have. Hence the checkpoints message. So that is why both of these
messages are in the same BIP -- only together can they perform an efficient
sync.

Regarding the reliability of the checkpoints, I think it's strictly better
than what we have now. Let's say a node is connected to 6 honest peers and
2 malicious peers. Even if the node does not know which ones are good or
bad until it validates the headers, it sees that 6 of the peers are on the
same chain, and can download those headers in parallel from 6 different
sources. So that's already a win.

Taken a step further though, I'm really interested in treating the
checkpoints as commitments to chain work and using random sampling to
detect lying peers before downloading all of their headers. So imagine you
are connected to two peers, one good one bad, where the good one claims a
chain with X total work and the bad one claims a chain with Y total work.
To determine quickly which is correct, you can randomly sample ranges of
headers and check the proofs of work to see whether it matches what the
peer claimed. So basically you pick a checkpoint at random (weighted by the
work delta) which commits to a total amount of work from the last
checkpoint, then request all headers in between. If the peer responds with
headers with the correct start hash, end hash, and start height (from the
coinbase tx of the first header), then you can be somewhat more confident
their total PoW matches the claimed amount.

How many times do you need to sample? I don't know yet, but I've heard
Benedikt Bunz is exploring this question with his research on FlyClients
[1], which was an inspiration for this.


> Bitfield allows great savings, however the encoding depends on the headers
> height a client ask for, this cause a little computational burden on the
> node and the undesirable side effect of difficult caching. Variable length
> encoding cause caching difficulties too...
> A simpler approach could be to encode the headers in groups of 2016
> headers (the difficulty period) where the first header is complete and the
> others 2015 are missing the previous hash and the difficulty, this achieve
> comparable savings ~45%, allows better caching and has fixed length
> encoding. This could be useful for the node by caching headers on a single
> file on disk and simply stream out the relative range when requested or to
> serve the same encoded headers format in other context like http,
> leveraging http caching infrastructure.
>

I don't see too much of a problem with caching. Most node implementations I
know of keep all headers in memory anyway, often in contiguous segments of
RAM for historical headers, so it should be fairly inexpensive to serve
queries. Beyond that, the response for a particular query (start_height,
end_hash, encoding version) can be cached, so if some service wants to
precompute max size responses for all start_height multiples of 1,000, they
could cache those.

-Jim

[1] https://www.youtube.com/watch?time_continue=8400&v=BPNs9EVxWrA


> 2018-03-28 1:31 GMT+02:00 Jim Posen via bitcoin-dev  linuxfoundation.org>:
>
>> Based on some ideas that were thrown around in this thread (
>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
>> 2017-December/015385.html), I have been working on a P2P extension that
>> will allow faster header sync mechanisms. The one-sentence summary is that
>> by encoding headers more efficiently (eg. omitting prev_hash) and
>> downloading evenly spaced checkpoints throughout history (say every
>> 1,000th) from all peers first, we could speed up header sync, which would
>> be a huge improvement for light

Re: [bitcoin-dev] Optimized Header Sync

2018-03-29 Thread Riccardo Casatta via bitcoin-dev 
Hi Jim,

| version[i] = version[i - ((bit[3] << 2) + (bit[4] << 1) +
bit[5])]


Thought this wasn't effective in case overt asic boost get widely adopted,
but then I understood that at the moment only two bits of version get
scrambled by that technique so this looks fine, maybe add a comment about
this so the reader doesn't get the same initial doubt I got.

...downloading evenly spaced checkpoints throughout history (say every
> 1,000th) from all peers first...


My feeling is that encoding of the headers and checkpoints/parallel
download are separate subjects for two BIPS.
About the checkpoints I don't grasp why they are useful since an attacker
could lie about them but maybe I am missing something...

To take advantage of these possible savings, this document defines a
> variable-sized ''compressed encoding'' of block headers that occur in a
> range. Note that no savings are possible when serializing a single header;
> it should only be used for vectors of sequential headers. The full headers
> are reconstructed using data from previous headers in the range. The
> serialization begins with an ''encoding indicator'', which is a bitfield
> specifying how each field is serialized. The bits of the indicator have the
> following semantics:


Bitfield allows great savings, however the encoding depends on the headers
height a client ask for, this cause a little computational burden on the
node and the undesirable side effect of difficult caching. Variable length
encoding cause caching difficulties too...
A simpler approach could be to encode the headers in groups of 2016 headers
(the difficulty period) where the first header is complete and the others
2015 are missing the previous hash and the difficulty, this achieve
comparable savings ~45%, allows better caching and has fixed length
encoding. This could be useful for the node by caching headers on a single
file on disk and simply stream out the relative range when requested or to
serve the same encoded headers format in other context like http,
leveraging http caching infrastructure.



2018-03-28 1:31 GMT+02:00 Jim Posen via bitcoin-dev <
[email protected]>:

> Based on some ideas that were thrown around in this thread (https://lists.
> linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html), I
> have been working on a P2P extension that will allow faster header sync
> mechanisms. The one-sentence summary is that by encoding headers more
> efficiently (eg. omitting prev_hash) and downloading evenly spaced
> checkpoints throughout history (say every 1,000th) from all peers first, we
> could speed up header sync, which would be a huge improvement for light
> clients. Here is a draft of the BIP: https://github.com/jimpo/
> bips/blob/headers-sync/headersv2.mediawiki. The full text is below as
> well.
>
> I'd love to hear any feedback people have.
>
> --
>
> == Abstract ==
>
> This BIP describes a P2P network extension enabling faster, more reliable 
> methods for syncing the block header chain. New P2P messages are proposed as 
> more efficient replacements for getheaders and 
> headers during initial block download. The proposed header 
> download protocol reduces bandwidth usage by ~40%-50% and supports 
> downloading headers ranges from multiple peers in parallel, which is not 
> possible with the current mechanism. This also enables sync strategies with 
> better resistance to denial-of-service attacks.
>
> == Motivation ==
>
> Since 2015, optimized Bitcoin clients fetch all block headers before blocks 
> themselves in order to avoid downloading ones that are not part of the most 
> work chain. The protocol currently in use for fetching headers leaves room 
> for further optimization, specifically by compressing header data and 
> downloading more headers 
> simulaneouslyhttps://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html.
>  Any savings here should have a large impact given that both full nodes and 
> light clients must sync the header chain as a first step, and that the time 
> to validate and index the headers is negligible compared to the time spent 
> downloading them from the network. Furthermore, some current implementations 
> of headers syncing rely on preconfigured checkpoints to discourage attackers 
> attempting to fill up a victim's disk space with low-work headers. The 
> proposed messages enable sync strategies that are resilient against these 
> types of attacks. The P2P messages are designed to be flexible, supporting 
> multiple header sync strategies and leaving room for future innovations, 
> while also compact.
>
> == Definitions ==
>
> ''double-SHA256'' is a hash algorithm defined by two invocations of SHA-256: 
> double-SHA256(x) = SHA256(SHA256(x)).
>
> == Specification ==
>
> The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", 
> "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this

[bitcoin-dev] Optimized Header Sync

2018-03-27 Thread Jim Posen via bitcoin-dev 
Based on some ideas that were thrown around in this thread (
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html),
I have been working on a P2P extension that will allow faster header sync
mechanisms. The one-sentence summary is that by encoding headers more
efficiently (eg. omitting prev_hash) and downloading evenly spaced
checkpoints throughout history (say every 1,000th) from all peers first, we
could speed up header sync, which would be a huge improvement for light
clients. Here is a draft of the BIP:
https://github.com/jimpo/bips/blob/headers-sync/headersv2.mediawiki. The
full text is below as well.

I'd love to hear any feedback people have.

--

== Abstract ==

This BIP describes a P2P network extension enabling faster, more
reliable methods for syncing the block header chain. New P2P messages
are proposed as more efficient replacements for
getheaders and headers during initial block
download. The proposed header download protocol reduces bandwidth
usage by ~40%-50% and supports downloading headers ranges from
multiple peers in parallel, which is not possible with the current
mechanism. This also enables sync strategies with better resistance to
denial-of-service attacks.

== Motivation ==

Since 2015, optimized Bitcoin clients fetch all block headers before
blocks themselves in order to avoid downloading ones that are not part
of the most work chain. The protocol currently in use for fetching
headers leaves room for further optimization, specifically by
compressing header data and downloading more headers
simulaneouslyhttps://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html.
Any savings here should have a large impact given that both full nodes
and light clients must sync the header chain as a first step, and that
the time to validate and index the headers is negligible compared to
the time spent downloading them from the network. Furthermore, some
current implementations of headers syncing rely on preconfigured
checkpoints to discourage attackers attempting to fill up a victim's
disk space with low-work headers. The proposed messages enable sync
strategies that are resilient against these types of attacks. The P2P
messages are designed to be flexible, supporting multiple header sync
strategies and leaving room for future innovations, while also
compact.

== Definitions ==

''double-SHA256'' is a hash algorithm defined by two invocations of
SHA-256: double-SHA256(x) = SHA256(SHA256(x)).

== Specification ==

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.

=== New Structures ===

 Compressed Headers 

Bitcoin headers are serialized by default in 80 bytes as follows:

{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| version
| int32_t
| 4
| Block version information
|-
| prev_block
| uint256
| 32
| The hash of the previous block
|-
| merkle_root
| uint256
| 32
| The root hash of the transaction Merkle tree
|-
| timestamp
| uint32_t
| 4
| A Unix timestamp of the block creation time, as reported by the miner
|-
| bits
| uint32_t
| 4
| The calculated difficulty target for this block
|-
| nonce
| uint32_t
| 4
| A nonce that is set such that the header's hash matches the difficulty target
|}

When deserializing a correctly-formed sequence of block headers
encoded in this way, it can be noted that:

* The prev_block field should always match the double-SHA256 hash of
the previous header, making it redundant
* According to Bitcoin consensus rules, the bits field only changes
every 2016 blocks
* The version often matches that of a recent ancestor block
* The timestamp is often a small delta from the preceding header's timestamp

To take advantage of these possible savings, this document defines a
variable-sized ''compressed encoding'' of block headers that occur in
a range. Note that no savings are possible when serializing a single
header; it should only be used for vectors of sequential headers. The
full headers are reconstructed using data from previous headers in the
range. The serialization begins with an ''encoding indicator'', which
is a bitfield specifying how each field is serialized. The bits of the
indicator have the following semantics:

{| class="wikitable"
! Bit Index
! Reconstruction
! Description
|-
| 0
| prev_block[i] = DSHA256(header[i-1])
| The prev_block field is ommitted and assigned to the double-SHA256
hash of the previous uncompressed header.
|-
| 1
| nbits[i] = nbits[i-1]
| The nbits field is omitted and matches that of the previous header.
|-
| 2
| timestamp[i] = timestamp[i-1] + value
| The timestamp is replaced by a 2-byte signed short int, representing
an offset from the previous block's timestamp
|-
| 3
|
| Interpreted along with bits 4 & 5.
|-
| 4
|
| Interpreted along with bits 3 & 5.
|-