[bitcoin-dev] Chain width expansion

[bitcoin-dev] Chain width expansion

[Braydon Fuller]

Hi everyone,

We would like to share a paper for broad discussion, it is titled
"Bitcoin Chain Width Expansion Denial-of-Service Attacks".

From the abstract: The attacks leverage unprotected resources for a
denial-of-service by filling the disk and exhausting the CPU with
unnecessary header and block data. This forces the node to halt
operation. The attack difficulty ranges from difficult to easy. There
are currently limited guards for some of the attacks that require
checkpoints to be enabled. This paper describes a solution that does not
require enabling or maintaining checkpoints and provides improved security.

As the checkpoints in Bitcoin Core have not been maintained or updated
since mid 2014, this is especially relevant. Bitcoin Core implements
headers-first synchronization, since 2014, that provides the base for
the further improvements upon that design.

The paper is available at:
https://bcoin.io/papers/bitcoin-chain-expansion.pdf

The proposed solution has been implemented in Bcoin and is available at:
https://github.com/bcoin-org/bcoin/tree/chain-expansion

Best,
Braydon Fuller

Re: [bitcoin-dev] Chain width expansion

[David A. Harding]

On Thu, Oct 03, 2019 at 05:38:36PM -0700, Braydon Fuller via bitcoin-dev wrote:
> This paper describes a solution [to DoS attacks] that does not
> require enabling or maintaining checkpoints and provides improved security.
> [...] 
> The paper is available at:
> https://bcoin.io/papers/bitcoin-chain-expansion.pdf

Hi Braydon,

Thank you for researching this important issue.  An alternative solution
proposed some time ago (I believe originally by Gregory Maxwell) was a
soft fork to raise the minimum difficulty.  You can find discussion of
it in various old IRC conversations[1,2] as well as in related changes
to Bitcoin Core such as PR #9053 addining minimum chain work[3] and the
assumed-valid change added in Bitcoin Core 0.14.0[4].

[1] http://www.erisian.com.au/meetbot/bitcoin-core-dev/2016/bitcoin-core-dev.2016-10-27-19.01.log.html#l-121
[2] http://www.erisian.com.au/meetbot/bitcoin-core-dev/2017/bitcoin-core-dev.2017-03-02-19.01.log.html#l-57
[3] https://github.com/bitcoin/bitcoin/pull/9053/commits/fd46136dfaf68a7046cf7b8693824d73ac6b1caf
[4] https://bitcoincore.org/en/2017/03/08/release-0.14.0/#assumed-valid-blocks

The solutions proposed in section 4.2 and 4.3 of your paper have the
advantage of not requiring any consensus changes.  However, I find it
hard to analyze the full consequences of the throttling solution in
4.3 and the pruning solution in 4.2.  If we assume a node is on the
most-PoW valid chain and that a huge fork is unlikely, it seems fine.
But I worry that the mechanisms could also be used to keep a node that
synced to a long-but-lower-PoW chain on that false chain (or other false
chain) indefinitely even if it had connections to honest peers that
tried to tell it about the most-PoW chain.

For example, with your maximum throttle of 5 seconds between
`getheaders` requests and the `headers` P2P message maximum of 2,000
headers per instance, it would take about half an hour to get a full
chain worth of headers.  If a peer was disconnected before sending
enough headers to establish they were on the most-PoW chain, your
pruning solution would delete whatever progress was made, forcing the
next peer to start from genesis and taking them at least half an hour
too.  On frequently-suspended laptops or poor connections, it's possible
a node could be be operational for a long time before it kept the same
connection open for half an hour.  All that time, it would be on a
dishonest chain.

By comparison, I find it easy to analyze the effect of raising the
minimum difficulty.  It is a change to the consensus rules, so it's
something we should be careful about, but it's the kind of
basically-one-line change that I expect should be easy for a large
number of people to review directly.  Assuming the choice of a new
minimum (and what point in the chain to use it) is sane, I think it
would be easy to get acceptance, and I think it would further be easy
increase it again every five years or so as overall hashrate increases.

-Dave

Re: [bitcoin-dev] Chain width expansion

[Braydon Fuller]

On 10/4/19 1:20 AM, David A. Harding wrote:

> On Thu, Oct 03, 2019 at 05:38:36PM -0700, Braydon Fuller via bitcoin-dev wrote:
>> This paper describes a solution [to DoS attacks] that does not
>> require enabling or maintaining checkpoints and provides improved security.
>> [...] 
>> The paper is available at:
>> https://bcoin.io/papers/bitcoin-chain-expansion.pdf
> [..] But I worry that the mechanisms could also be used to keep a node that
> synced to a long-but-lower-PoW chain on that false chain (or other false
> chain) indefinitely even if it had connections to honest peers that
> tried to tell it about the most-PoW chain.

Here is an example: An attacker eclipses a target node during the
initial block download; all of the target's outgoing peers are the
attacker. The attacker has a low work chain that is sent to the target.
The total chainwork for the low work chain is 0x09104210421039 at a
height of 593,975. The target is now in the state of a fully validated
low work dishonest chain. The target node then connects to an honest
peer and learns about the honest chain. The chainwork of the honest
chain is 0x085b67d9e07a751e53679d68 at a height of 593,975. The first
69,500 headers of the honest chain would have a delay, however the
remaining 52,4475 would not be delayed. Given a maximum of 5 seconds,
this would be a total delay of only 157 seconds.

Re: [bitcoin-dev] Chain width expansion

[Braydon Fuller]

On 10/4/19 1:20 AM, David A. Harding wrote:

> On Thu, Oct 03, 2019 at 05:38:36PM -0700, Braydon Fuller via bitcoin-dev wrote:
>> This paper describes a solution [to DoS attacks] that does not
>> require enabling or maintaining checkpoints and provides improved security.
>> [...] 
>> The paper is available at:
>> https://bcoin.io/papers/bitcoin-chain-expansion.pdf
> Hi Braydon,
>
> Thank you for researching this important issue.  An alternative solution
> proposed some time ago (I believe originally by Gregory Maxwell) was a
> soft fork to raise the minimum difficulty.  You can find discussion of
> it in various old IRC conversations[1,2] as well as in related changes
> to Bitcoin Core such as PR #9053 addining minimum chain work[3] and the
> assumed-valid change added in Bitcoin Core 0.14.0[4].
>
> [1] http://www.erisian.com.au/meetbot/bitcoin-core-dev/2016/bitcoin-core-dev.2016-10-27-19.01.log.html#l-121
> [2] http://www.erisian.com.au/meetbot/bitcoin-core-dev/2017/bitcoin-core-dev.2017-03-02-19.01.log.html#l-57
> [3] https://github.com/bitcoin/bitcoin/pull/9053/commits/fd46136dfaf68a7046cf7b8693824d73ac6b1caf
> [4] https://bitcoincore.org/en/2017/03/08/release-0.14.0/#assumed-valid-blocks
>
Okay, here is an overview of what I have found for the minimum
difficulty proposal:

It describes having a new consensus rule to not fork or accept headers
prior to, or below, a minimum difficulty once the best chain work is
achieved at release time of the software. This would be instead of the
rule to not fork before the last checkpoint, as checkpoints are removed.

It has an advantage to the existing checkpoint solution as it does not
require checkpoints to be enabled. This is not a surprise as the
proposal was to remove checkpoints entirely. It would increase the cost
of the attack without checkpoints. Long header chains would need to be
built using this minimum difficulty, instead of the current lowest
difficulty of the genesis block. The exact cost of that is not yet
calculated.

There are a few caveats with the approach mentioned; nodes are
vulnerable if the initial loader peer is the attacker, it could leave
minority hashpower without an ability to softfork away during a
contentious hardfork, and requires period consensus changes to continue
to maintain:
  - Nodes are vulnerable during the initial sync when joining the
network until the minimum chainwork is achieved. This is possible if the
loader peer is the attacker. To mitigate this there would need to be a
minimum chainwork defined based on the current chainwork. However, such
could also be used to prevent nodes from joining the network as it's
rejecting rather that throttling.
  - A contentious hardfork could leave a minority hashpower without an
ability to softfork away without agreeing on a hardfork. This was the
reason why the minimum difficulty was about 10 devices instead of 10,000.
  - It's technically a consensus change each time the minimum difficulty
or best chainwork is updated. It is a similar consensus change as
maintaining the last checkpoint, as it's used to prevent forking prior
to the last checkpoint.

I think the solution proposed in the Bitcoin Chain Width Expansion paper
solves those issues by limiting chain width and throttling based on
chainwork, instead of rejecting blocks based on the minimum difficulty.

Re: [bitcoin-dev] Chain width expansion

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 2635 bytes --]

Are you assuming no network protocol changes?

At root, the requirement is that peers can prove their total chain POW.

Since each block has the height in the coinbase, a peer can send a short
proof of height for a disconnected header and could assert the POW for that
header.

Each peer could send the the N strongest headers (lowest digest/most POW)
for their main chain and prove the height of each one.

The total chain work can be estimated as N times the POW for the lowest in
the list.  This is an interesting property of how POW works.  The 10th best
POW block will have about 10% of the total POW.

The N blocks would be spread along the chain and the peer could ask for all
headers between any 2 of them and check the different in claimed POW.  If
dishonesty is discovered, the peer can be banned and all info from that
peer wiped.

You can apply the rule hierarchically.  The honest peers would have a much
higher POW chain.  You could ask the peer to give you the N strongest
headers between 2 headers that they gave for their best chain.  You can
check that their height is between the two limits.

The peer would effectively be proving their total POW recursively.

This would require a new set of messages so you can request info about the
best chain.

It also has the nice feature that it allows you to see if multiple peers
are on the same chain, since they will have the same best blocks.

The most elegant would be something like using SNARKS to directly prove
that your chain tip has a particular POW.  The download would go tip to
genesis, unlike now when it is in the other direction.

------------------------------------------------------------------------

In regard to your proposal, I think the key is to limit things by peer,
rather than globally.

The limit to header width should be split between peers.  If you have N
outgoing peers, they get 1/N of your header download resources each.

You store the current best/most POW header chain and at least one
alternative chain per outgoing peer.

You could still prune old chains based on POW, but the best chain and the
current chain for each outgoing peer should not be pruned.

The security assumption is that a node is connected to at least one honest
node.

If you split resources between all peers, then it prevents the dishonest
nodes from flooding and wiping out the progress for the honest peer.

- Message Limiting -

I have the same objection here.  The message limiting should be per peer.

An honest peer who has just been connected to shouldn't suffer a penalty.

Your point that it is only a few minutes anyway may make this point moot
though.

[-- Attachment #2: Type: text/html, Size: 3239 bytes --]

Re: [bitcoin-dev] Chain width expansion

[Braydon Fuller]

On 10/4/19 4:31 PM, Tier Nolan via bitcoin-dev wrote

> [..] At root, the requirement is that peers can prove their total chain POW. [...]
Indeed, it's currently necessary to receive all of the chain headers to
determine. It would be interesting to have a succinct chainwork proof
for all cases. Chainwork being a sum of the total proof-of-work in a
chain. Such proofs currently only require a few headers for common cases
and the other cases can be identified.
> In regard to your proposal, I think the key is to limit things by peer, rather than globally. [...]

Yeah, there should be enough width available for every active
connection, only one chain of headers is requested at a time per peer.
Peer based limiting is susceptible to Sybil attacks; A peer could
broadcast a few low-work header chains, reconnect and repeat ad nauseam.

The delay for the next set of headers is based on the chainwork of the
last received headers from the peer. The peer could change identity and
run into the same limit. The unrequested header rate is tracked per peer.

A header chain with more chainwork will be requested at a faster rate
than a header chain with less chainwork. The chainwork is compared to
the current fully validated chain. Honest peers with more chainwork will
have a time advantage over dishonest peers with less chainwork.

For example, let's assume a case that the initial chain of headers was
dishonest and with low chainwork. The initial block download retrieves
the header chain from a single loader peer first. Once recent time is
reached, header chains are downloaded from all outgoing peers. A single
honest peer will have an advantage over many dishonest peers. Thus, as
you have mentioned, there is a security assumption that there is at
least one connected honest node.

Re: [bitcoin-dev] Chain width expansion

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 6034 bytes --]

On Thu, Oct 10, 2019 at 5:20 PM Braydon Fuller via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>  It would be interesting to have a succinct chainwork proof
> for all cases. Chainwork being a sum of the total proof-of-work in a
> chain. Such proofs currently only require a few headers for common cases
> and the other cases can be identified.
>

I wonder if a "seed" based system would be useful.

A seed is defined as a header with a very low digest.

When a new peer connects, you ask him to send you the header with the
lowest digest on his main chain.

Chains ending at the strongest seeds are kept preferentially when
discarding chains.

This requires a way to download chains backwards, which the protocol
doesn't support at the moment.

The most chain work chain is overwhelmingly likely to contain the header
with the strongest digest.

This means that the honest peer's chain would be kept preferentially.

It also means that a node that is synced to the main chain can easily
discard noise from dishonest peers.  Before downloading, they could ask the
peer to provide a header with at least 1% of the POW of the best header on
the main chain starting at the fork point.  If they can't then their fork
probably has less POW than the main chain.


> A peer could
> broadcast a few low-work header chains, reconnect and repeat ad nauseam.
>

I meant connected peer rather than peer.  If a peer disconnects and then
reconnects as a new peer, then their allocation of bandwidth/RAM resets to
zero.

Each peer would be allocated a certain bandwidth per minute for headers as
in a token bucket system.   New peers would start with empty buckets.

If an active (outgoing) peer is building on a header chain, then that chain
is preferentially kept.  Essentially, the last chain that each outgoing
peer built on may not be discarded.

In retrospect, that works out as the same as throttling peer download, just
with a different method for throttling.

In your system, peers who extend the best chain don't get throttled, but
the other peers do (but with a gradual transition).

This could be accomplished by adding 80 bytes into the peers bucket if it
extends the main chain.


> For example, let's assume a case that the initial chain of headers was
> dishonest and with low chainwork. The initial block download retrieves
> the header chain from a single loader peer first. Once recent time is
> reached, header chains are downloaded from all outgoing peers.


The key it that it must not be possible to prevent a single honest peer
from making progress by flooding with other peers and getting the honest
peer's chain discarded.

I think parallel downloading would be better than focusing on one peer
initially.  Otherwise, a dishonest peer can slowly send their headers to
prevent moving to parallel mode.

Each connected peer is given a bandwidth and RAM allowance.  If a connected
peer forks off their own chain before reaching current time, then the fork
is just discarded.

The RAM allowance would be sufficient to hold one header per minute since
genesis.

The header chains are relatively small (50MB), so it is not unreasonable to
expect the honest peer to send the entire chain in one go.

I wonder if there is a formula that gives the minimum chain work required
to have a particular chain length by now.

1 minute per header would mean that the difficulty would increase every
adjustment, so it couldn't be maintained without an exponentially rising
total chain work.

On Sat, Oct 12, 2019 at 2:41 AM Braydon Fuller via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>   - Nodes are vulnerable during the initial sync when joining the
> network until the minimum chainwork is achieved.


Nodes should stay "headers-only" until they have hit the threshold.

It isn't really any different from a checkpoint anyway.

Download headers until you hit this header is about the same as download
headers until you hit this chain work.

It would be different if header chains were downloaded from the final
checkpoint backwards.

You would start at a final checkpoint and work backwards.  Each ancestor
header is committed to by the final checkpoint, so it would not be possible
a dishonest peer to fool the node during IBD.


> This is possible if the
> loader peer is the attacker. To mitigate this there would need to be a
> minimum chainwork defined based on the current chainwork. However, such
> could also be used to prevent nodes from joining the network as it's
> rejecting rather that throttling.
>

I think mixing two different concepts makes this problem more complex than
needed.

It looks like they are aiming for hard-coding

A) "The main chain has at least C chainwork"
B) "All blocks after A is satisfied have at least X POW"

To me, this is equivalent to a checkpoint, without it having it be called a
checkpoint.

The point about excluding checkpoints is that it means that (in theory) two
clients can't end up on incompatible forks due to different checkpoints.

The "checkpoint" is replaced by a statement by the dev team that

"There exists at least one valid chain with C chainwork"

which is equivalent to

"The longest valid chain has at least C chainwork"

Two client making those statements can't cause a permanent
incompatibility.  If they pick a different C, then eventually, once the
main chain has more than the larger chain work, they will agree again.

Checkpoints don't automatically heal.

Adding in a minimum POW requirement could break the requirement for that to
happen.

Just because B was met on the original main chain, a fork isn't required to
meet it.

  - It's technically a consensus change each time the minimum difficulty
> or best chainwork is updated. It is a similar consensus change as
> maintaining the last checkpoint, as it's used to prevent forking prior
> to the last checkpoint.
>

I agree on the min difficulty being a consensus change.

The minimum chain work is just the devs making a true statement and then
using it to optimize things.

[-- Attachment #2: Type: text/html, Size: 8514 bytes --]

Re: [bitcoin-dev] Chain width expansion

[Joachim Strömbergson]

[-- Attachment #1: Type: text/plain, Size: 7188 bytes --]

I like the backwards syncing idea. First you provide proof of your best block height via coinbase, then sync backwards. It solves lots of related problems. You know how much you can expect from the given peer.

On different note, one of the problems that I haven't seen mentioned here yet is the timewarp attack. It is relevant to some of the proposed solutions. It should be possible, IIRC, for a malicious node to generate much longer chain with superslow timestamp increase (~5 blocks in 1 second) without increasing difficulty (i.e. staying at min. diff.). This could produce chain that is ~2500 times longer than main chain without having multiple branches.

I also agree that there is no big difference between hash checkpoints and "min. diff. checkpoints".

Joachim

Sent with [ProtonMail](https://protonmail.com) Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Saturday, October 12, 2019 4:27 PM, Tier Nolan via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Thu, Oct 10, 2019 at 5:20 PM Braydon Fuller via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>>  It would be interesting to have a succinct chainwork proof
>> for all cases. Chainwork being a sum of the total proof-of-work in a
>> chain. Such proofs currently only require a few headers for common cases
>> and the other cases can be identified.
>
> I wonder if a "seed" based system would be useful.
>
> A seed is defined as a header with a very low digest.
>
> When a new peer connects, you ask him to send you the header with the lowest digest on his main chain.
>
> Chains ending at the strongest seeds are kept preferentially when discarding chains.
>
> This requires a way to download chains backwards, which the protocol doesn't support at the moment.
>
> The most chain work chain is overwhelmingly likely to contain the header with the strongest digest.
>
> This means that the honest peer's chain would be kept preferentially.
>
> It also means that a node that is synced to the main chain can easily discard noise from dishonest peers.  Before downloading, they could ask the peer to provide a header with at least 1% of the POW of the best header on the main chain starting at the fork point.  If they can't then their fork probably has less POW than the main chain.
>
>> A peer could
>> broadcast a few low-work header chains, reconnect and repeat ad nauseam.
>
> I meant connected peer rather than peer.  If a peer disconnects and then reconnects as a new peer, then their allocation of bandwidth/RAM resets to zero.
>
> Each peer would be allocated a certain bandwidth per minute for headers as in a token bucket system.   New peers would start with empty buckets.
>
> If an active (outgoing) peer is building on a header chain, then that chain is preferentially kept.  Essentially, the last chain that each outgoing peer built on may not be discarded.
>
> In retrospect, that works out as the same as throttling peer download, just with a different method for throttling.
>
> In your system, peers who extend the best chain don't get throttled, but the other peers do (but with a gradual transition).
>
> This could be accomplished by adding 80 bytes into the peers bucket if it extends the main chain.
>
>> For example, let's assume a case that the initial chain of headers was
>> dishonest and with low chainwork. The initial block download retrieves
>> the header chain from a single loader peer first. Once recent time is
>> reached, header chains are downloaded from all outgoing peers.
>
> The key it that it must not be possible to prevent a single honest peer from making progress by flooding with other peers and getting the honest peer's chain discarded.
>
> I think parallel downloading would be better than focusing on one peer initially.  Otherwise, a dishonest peer can slowly send their headers to prevent moving to parallel mode.
>
> Each connected peer is given a bandwidth and RAM allowance.  If a connected peer forks off their own chain before reaching current time, then the fork is just discarded.
>
> The RAM allowance would be sufficient to hold one header per minute since genesis.
>
> The header chains are relatively small (50MB), so it is not unreasonable to expect the honest peer to send the entire chain in one go.
>
> I wonder if there is a formula that gives the minimum chain work required to have a particular chain length by now.
>
> 1 minute per header would mean that the difficulty would increase every adjustment, so it couldn't be maintained without an exponentially rising total chain work.
>
> On Sat, Oct 12, 2019 at 2:41 AM Braydon Fuller via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>>   - Nodes are vulnerable during the initial sync when joining the
>> network until the minimum chainwork is achieved.
>
> Nodes should stay "headers-only" until they have hit the threshold.
>
> It isn't really any different from a checkpoint anyway.
>
> Download headers until you hit this header is about the same as download headers until you hit this chain work.
>
> It would be different if header chains were downloaded from the final checkpoint backwards.
>
> You would start at a final checkpoint and work backwards.  Each ancestor header is committed to by the final checkpoint, so it would not be possible a dishonest peer to fool the node during IBD.
>
>> This is possible if the
>> loader peer is the attacker. To mitigate this there would need to be a
>> minimum chainwork defined based on the current chainwork. However, such
>> could also be used to prevent nodes from joining the network as it's
>> rejecting rather that throttling.
>
> I think mixing two different concepts makes this problem more complex than needed.
>
> It looks like they are aiming for hard-coding
>
> A) "The main chain has at least C chainwork"
> B) "All blocks after A is satisfied have at least X POW"
>
> To me, this is equivalent to a checkpoint, without it having it be called a checkpoint.
>
> The point about excluding checkpoints is that it means that (in theory) two clients can't end up on incompatible forks due to different checkpoints.
>
> The "checkpoint" is replaced by a statement by the dev team that
>
> "There exists at least one valid chain with C chainwork"
>
> which is equivalent to
>
> "The longest valid chain has at least C chainwork"
>
> Two client making those statements can't cause a permanent incompatibility.  If they pick a different C, then eventually, once the main chain has more than the larger chain work, they will agree again.
>
> Checkpoints don't automatically heal.
>
> Adding in a minimum POW requirement could break the requirement for that to happen.
>
> Just because B was met on the original main chain, a fork isn't required to meet it.
>
>>   - It's technically a consensus change each time the minimum difficulty
>> or best chainwork is updated. It is a similar consensus change as
>> maintaining the last checkpoint, as it's used to prevent forking prior
>> to the last checkpoint.
>
> I agree on the min difficulty being a consensus change.
>
> The minimum chain work is just the devs making a true statement and then using it to optimize things.

[-- Attachment #2: Type: text/html, Size: 10569 bytes --]

Re: [bitcoin-dev] Chain width expansion

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 2381 bytes --]

On Sat, Oct 12, 2019 at 6:56 PM Joachim Strömbergson <
joachimstr@protonmail.com> wrote:

> I like the backwards syncing idea. First you provide proof of your best
> block height via coinbase, then sync backwards. It solves lots of related
> problems. You know how much you can expect from the given peer.
>

It shows you which nodes are on the same chain too.

If you have 8 peers and you ask the 8 of them for their 8 best, then they
should all agree on most of them.

You can then ask each of the 8 to start sending you headers backwards from
one of the 8 seeds.

They will all roughly split the chain into 8 equal pieces, though the split
will be based on work rather than header height.

If there is disagreement, you can give priority to the node(s) with the
lowest headers until they have completed their download.

It requires a network protocol change to allow reverse block downloads
though (and messages to indicate lowest headers etc.)

On different note, one of the problems that I haven't seen mentioned here
> yet is the timewarp attack. It is relevant to some of the proposed
> solutions. It should be possible, IIRC, for a malicious node to generate
> much longer chain with superslow timestamp increase (~5 blocks in 1 second)
> without increasing difficulty (i.e. staying at min. diff.). This could
> produce chain that is ~2500 times longer than main chain without having
> multiple branches.
>

That is a good point.  It answers my question about formula for maximum
number of blocks.

5 * 60 * 60 * 24 * 365 = 157,680,000

That's around 150 million blocks per year at that rate.

I assume the 5 per second limit is that it is greater that the median of
the last 11 rather than greater or equal?

The timewarp bug can be fixed by a basic soft fork.  You just need to limit
the maximum difference between the timestamp for the first header in a
period and the last header in the previous period.

An alternative would be to soft fork in a maximum block rate.  In addition
to the current rules, you could limit it to a maximum of 1 block every 2
mins.  That rule shouldn't activate normally.

   block.height <= (block.timestamp - genesis.timestamp) / (2 mins)

It could have some weird incentives if it actually activated though.
Miners would have to shutdown mining if they were finding blocks to fast.

[-- Attachment #2: Type: text/html, Size: 3138 bytes --]

Re: [bitcoin-dev] Chain width expansion

[Braydon Fuller]

On 10/12/19 1:46 PM, Tier Nolan via bitcoin-dev wrote:

> On Sat, Oct 12, 2019 at 6:56 PM Joachim Strömbergson <joachimstr@protonmail.com> wrote:
>> On different note, one of the problems that I haven't seen mentioned here
>> yet is the timewarp attack. It is relevant to some of the proposed
>> solutions. It should be possible, IIRC, for a malicious node to generate
>> much longer chain with superslow timestamp increase (~5 blocks in 1 second)
>> without increasing difficulty (i.e. staying at min. diff.). This could
>> produce chain that is ~2500 times longer than main chain without having
>> multiple branches.
>>
> [..]
>
> The timewarp bug can be fixed by a basic soft fork.  You just need to limit
> the maximum difference between the timestamp for the first header in a
> period and the last header in the previous period.

Yeah, that makes sense as it corrects the off-by-one error. I think this
solution has been included in a draft proposal "The Great Consensus
Cleanup". It would need to be effective for not only the main chain but
also for any future forked chain.

Re: [bitcoin-dev] Chain width expansion

[Braydon Fuller]

On 10/12/19 10:56 AM, Joachim Strömbergson via bitcoin-dev wrote:

> [...] First you provide proof of your best block height via coinbase [...]

So I don't think you can use the height in the coinbase for that
purpose, as it's not possible to validate it without the previous
headers. That's common for more than just the height.

> [...] to generate much longer chain with superslow timestamp increase (~5 blocks in 1 second) without increasing difficulty (i.e. staying at min. diff.). [...]

In that case, it would take about 7 minutes of block time seconds for
the next retarget period, every 2016 blocks, and the difficulty would
adjust. The difficulty would adjust in that case as if 2 weeks of blocks
had been mined in 7 minutes. For the difficulty to remain the same the
time between blocks needs to be 10 minutes.

Re: [bitcoin-dev] Chain width expansion

[Joachim Strömbergson]

> > [...] First you provide proof of your best block height via coinbase [...]
>
> So I don't think you can use the height in the coinbase for that
> purpose, as it's not possible to validate it without the previous
> headers. That's common for more than just the height.

You can fake it of course, but it means you are spending money for PoW and I can't see viable attack here. You can commit to either lower height than actual or higher height, if you are malicious. If it is lower, then your chain will look weaker with some heuristic based on PoW of the tip and the chain length. So you are not going to do that. It thus seem it only makes sense to commit to higher than actual height. OK, this could convince me to be interested in your chain over others. So let's say the real chain is 600k blocks, you claim 1m blocks, and you prove 1m height block to me. So I can ask you about

1) 2000 headers from the tip down
2) AND another proof of height for the block at 1m-2000.

To be able to provide that you need to have such a chain and you can reuse any real subchain from mainnet. It's still possible that you can deliver that, but not for high difficulty.

Now if time warp attack is blocked, you will have pretty hard time to create such a chain that would look strongest in cumulative work. I don't have actual numbers though, so I can't say this would mitigate everything.


> > [...] to generate much longer chain with superslow timestamp increase (~5 blocks in 1 second) without increasing difficulty (i.e. staying at min. diff.). [...]
>
> In that case, it would take about 7 minutes of block time seconds for
> the next retarget period, every 2016 blocks, and the difficulty would
> adjust. The difficulty would adjust in that case as if 2 weeks of blocks
> had been mined in 7 minutes. For the difficulty to remain the same the
> time between blocks needs to be 10 minutes.

This calculation does not apply under time warp attack. You can fake timestamps of all blocks except for those relevant to the retarget calculation. Those are only the first and the last block in the 2016 block window.

Re: [bitcoin-dev] Chain width expansion

[Braydon Fuller]

On 10/15/19 12:20 AM, Joachim Strömbergson wrote:

>>> [...] to generate much longer chain with superslow timestamp increase (~5 blocks in 1 second) without increasing difficulty (i.e. staying at min. diff.). [...]
>> In that case, it would take about 7 minutes of block time seconds for
>> the next retarget period, every 2016 blocks, and the difficulty would
>> adjust. The difficulty would adjust in that case as if 2 weeks of blocks
>> had been mined in 7 minutes. For the difficulty to remain the same the
>> time between blocks needs to be 10 minutes.
> This calculation does not apply under time warp attack. You can fake timestamps of all blocks except for those relevant to the retarget calculation. Those are only the first and the last block in the 2016 block window.

This must be in reference to the non-overlapping difficulty calculation
and off-by-one bug?

Re: [bitcoin-dev] Chain width expansion

[Joachim Strömbergson]

> > > > [...] to generate much longer chain with superslow timestamp increase (~5 blocks in 1 second) without increasing difficulty (i.e. staying at min. diff.). [...]
> > > > In that case, it would take about 7 minutes of block time seconds for
> > > > the next retarget period, every 2016 blocks, and the difficulty would
> > > > adjust. The difficulty would adjust in that case as if 2 weeks of blocks
> > > > had been mined in 7 minutes. For the difficulty to remain the same the
> > > > time between blocks needs to be 10 minutes.
> > > > This calculation does not apply under time warp attack. You can fake timestamps of all blocks except for those relevant to the retarget calculation. Those are only the first and the last block in the 2016 block window.
>
> This must be in reference to the non-overlapping difficulty calculation
> and off-by-one bug?

Indeed.

Re: [bitcoin-dev] Chain width expansion

[Braydon Fuller]

On 10/15/19 8:50 AM, Joachim Strömbergson wrote:

>>>>> [...] to generate much longer chain with superslow timestamp increase (~5 blocks in 1 second) without increasing difficulty (i.e. staying at min. diff.). [...]
>>>>> In that case, it would take about 7 minutes of block time seconds for
>>>>> the next retarget period, every 2016 blocks, and the difficulty would
>>>>> adjust. The difficulty would adjust in that case as if 2 weeks of blocks
>>>>> had been mined in 7 minutes. For the difficulty to remain the same the
>>>>> time between blocks needs to be 10 minutes.
>>>>> This calculation does not apply under time warp attack. You can fake timestamps of all blocks except for those relevant to the retarget calculation. Those are only the first and the last block in the 2016 block window.
>> This must be in reference to the non-overlapping difficulty calculation
>> and off-by-one bug?
> Indeed.
>
Yeah, limiting the width of the chain would not be effective unless the
timewarp off-by-one bug is resolved — the height can be extended instead.

Rate limiting based on chainwork would slow down a timewarped low work
header chain. There would be a maximum rate at which the headers could
be sent. It would be around 32KB/s. It would take about a month to send
100GB.

Re: [bitcoin-dev] Chain width expansion

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 833 bytes --]

On Tue, Oct 15, 2019 at 7:29 AM Braydon Fuller via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> So I don't think you can use the height in the coinbase for that
> purpose, as it's not possible to validate it without the previous
> headers. That's common for more than just the height.
>

It is a property of blockchains that the lowest digest for a chain
represents the total chainwork.

Estimate total hash count = N * (2^256) / (Nth lowest (i.e. strongest)
digest over all headers)

To produce a fake set of 10 headers that give a higher work estimate than
the main chain would require around the same effort as went into the main
chain in the first place.  You might as well completely build an
alternative chain.

Working backwards for one of those headers, you have to follow the actual
chain back to genesis.

[-- Attachment #2: Type: text/html, Size: 1251 bytes --]

Re: [bitcoin-dev] Chain width expansion

[Braydon Fuller]

On 10/12/19 9:27 AM, Tier Nolan via bitcoin-dev wrote:

> [...]
>
> I think parallel downloading would be better than focusing on one peer
> initially.  Otherwise, a dishonest peer can slowly send their headers to
> prevent moving to parallel mode.
>
> [...]

As implemented, there is a timeout for that loader peer based on the
amount of time it should take to request all the headers. The time
period is defined as a base time plus the number of expected headers
times an expected amount of time per header. For example, the timeout
would be 25 minutes with a base time of 15 minutes, 1 millisecond per
header and an expected 600000 headers.