BUIP038: (closed) Revert "sticky gate"

[dgenr8]

Proposer: Tom Harding
Submitted on: 11/27/2016
[edit: Sponsor: freetrader]

Summary:

The implementation of BUIP001's EB/AD emergent blocksize consensus has a "sticky gate" behavior. While not widely understood, the sticky gate has a significant effect on BU nodes' ability to resist attacks from a relatively small fraction of dedicated hashrate opposition.

This BUIP seeks to revert the "sticky gate" to resist this type of attack.

Rationale:

The sticky gate is triggered by local observation of an accept-depth (AD) override to an excessive block (EB). The "gate" opens when a count of AD blocks are mined on top of an excessive block; it lets those blocks through. The "sticky" part is that once opened, the gate sticks open for 144 blocks. During that time, BU allows any size block for 144 more blocks -- about one full day.

While the gate is fundamental to BU emergent consensus, it should not be sticky. Risk is introduced by the combination of published AD values and the daylong period devoid of blocksize checks, which present attacker a way to disrupt the BU chain.

Attacker's challenge is to create an excessive block, followed by AD confirming blocks, before honest BU nodes can create a competing chain of length AD+1. If an attacker can succeed in this, he has 144 blocks which are permitted to be any size at all.

Attacker then submits as many enormous blocks as possible, to make them a permanent part of the BU chain, straining all BU users, possibly fragmenting the chain and/or pushing some users off the network. Alternatively, he submits large blocks of various sizes, in an attempt to maximize fragmentation when nodes come back online after 144 blocks.

Attacker's likelihood of success during a single attempt to open the sticky gate depends on the hashrate fraction q (of total BU hashrate) that he dedicates to this purpose. The probability of success for AD=5 is as follows (review of this is very welcome):

AD=5
q P[success]
0.05 0.00000580135
0.10 0.000295706
0.15 0.00265686
0.20 0.0116542
0.25 0.0343275
0.30 0.0782248
0.35 0.148684
0.40 0.246502
0.45 0.366877
0.50 0.5
0.55 0.633123
0.60 0.753498

Attacker is free to make another attempt, as soon as one attempt fails. Such failure will take at most 11 blocks, so attacker can try approximately 13 times per day. Therefore an attacker with 20% hashrate has a worst-case success rate of approximately a 14% chance of successfully overwhelming AD=5 within one day. The risk introduced by the sticky gate is very high.

The goal of the sticky gate is to avoid nodes getting stuck when the network moves to a larger block size. But the risk is unacceptable. Instead of this automatic security reduction, regular nodes should consider a higher EB value than they might otherwise use. Miners should continue to immediately alert technical staff any time an invalid block with valid PoW is seen for any reason, not just excessive block size. Invalid blocks are very rare and always deserve close immediate attention.

Specification:
Revert to the behavior that is documented in BUIP001 and that was effective until March 8, 2016.

Implementation:

An implementation of the reversion is available in PR#169.

 

[Peter R]

I support this change.

The gate was originally made sticky to prevent miners with too low a block size limit from wasting hash power after accepting an excessive block but before they increase their block size limits. But based on the behaviour of viaBTC and the bitcoin.com mining pool, I think in practice miners will be very careful to choose the same limits, and so the benefit of the sticky gate will likely never be seen in practice. Having the gate close immediately instead eliminates the potential attack vector described above by @dgenr8.

 

[theZerg]

To review the process:

Since dgenr8 is not a member, a member needs to volunteer to represent this BUIP, and dgenr8 needs to agree with the choice because this member will be making the official decisions (if needed) to bring the BUIP to a vote, withdraw it, etc. Peter R perhaps you would be willing to sponsor it?

Once that happens, we enter a period (2 weeks I think) where I get to work with the author and sponsor to modify the BUIP. All modifications that I suggest are optional. But if I think that the modifications are not sufficient, I can propose a counter-BUIP and force the membership to choose between them.

I'll start with my comments before the sponsor is settled just to get things moving:

The intention of BUIP001 was to resist a chain but then to allow it to be evaluated when it becomes clear that significant hash power is behind it. Once a chain has significant hash power, the intention was never to cause the node/miner to be perpetually AD blocks behind the tip if that chain is the longest. However this situation can happen, if every block on the new chain exceeds the EB. This may seem unlikely, but would be possible given a very conservative block increase. For example, let's assume a 1MB EB. If there is a large backlog of transactions, miners might move to generating 1.1MB blocks and work off the backlog over a period of days rather than move to immediately generating a 4MB block, and then falling back to < 1MB.

This situation completely undermines the purpose of the EB/AD algorithm for miners. The purpose is to allow miners to have a preference, but at the same time limit their loss (amount of time spent mining a less-difficult fork) to a well defined number of blocks. This way they don't have to watch the blockchain 24x7.

And its awkward for full nodes since (for example) an exchange that normally required N confirmations now needs N+AD confirmations -- not just during the "fight" time, but potentially indefinitely.

This is why I added a fix to the code. So I believe that we should not revert this fix.

However, we can still handle the OP's original concern, which is that the "gate" is completely removed for 144 blocks after the EB is exceeded. [As an aside, I'd be interested to see a simulation of how much money on average an attacker loses when attempting this attack -- I originally dismissed the attack because it seems to be too costly for not much payoff.]

Instead, let me propose that we change the gate algorithm to be:
max(EB, 100kb + largest block in the last 144 (24 hours) on this chain)

The purpose of the additional 100k is to solve the same "trailing" issue if the largest block "creeps" up by a few bytes each time...


@dgenr8, what do you think about modifying your BUIP to fix both issues?

 

[dgenr8]

As I understand it, the worry that led to the sticky gate is that a majority of miners might increase the blocksize, and catch the rest of the miners and other uses by surprise.

Where was this issue discussed? What opinions or data were offered on how likely this scenario is to happen? Miners, particularly a mining majority, are the last people that want to see the chain fractured. BU is based on this premise.

How was it decided that a very substantial change to the consensus algorithm was required to address this worry? Why did it outweigh the risks?

During the discussions, did anyone ask whether BU could do a better job of alerting the operator, such as by adding contrib scripts to call pagers, etc? Or that an easy -- but manual -- mechanism could be added to consent to an EB increase to some recently observed value?

Since all of this is hypothetical, is it really the best option to add even more code now, in the form of an automatic EB increase? To try this overestimates the resources of the BU project.

What makes us think we can handle this additional complexity when we haven't sufficiently tested the already massive change represented by the EB/AD mechanism? For example, issue #170 shows that changing AD doesn't take effect immediately. Let's not automate changes to these parameters quite yet.

Regarding incentives, does anyone doubt that BU opponents would like to kill it, and may incur significant costs in an attempt to do so? Who is looking for the other vulnerabilities not yet found, and addressing them through code and policy simplification?

If the discussions I'm imaging did not in fact take place, then there is only one clear way forward. Revert the sticky gate and then discuss it properly, and even observe the operation of the basic EB/AD mechanism in the wild, before re-introducing it.

 

[freetrader]

I volunteer to sponsor this BUIP.

 

[awemany]

First of all, thanks @dgenr8 for the thorough review of BU's current consensus process. I think that the issue you raised is valid. (At the same time I can see @theZerg's argument that this attack is going to be expensive)

I do no understand your calculated values. Isn't the probability simply the same as launching an attack with the given hashrate for the number of blocks that equals the acceptance depth?

So, for example, for your q=10%, 5 blocks deep scenario, I'd expect P=0.0009137 as written in the original white paper?

I think you also have a great point on asking the 'where has the stickyness been decided'. Have we been informal here? My impression was that this was more or less part of BUIP1. But if there is unclarity here, we should definitely fix that ...

So @Peter R, without stickyness, you'd expect the miners to collectively agree at one point on 'EB2/AD0' all at once and thus setting the new consensus? Maybe we should ask the miners around here what they'd like, and why?

So the question is whether we want the stubbornness extended for many blocks, or just a dam breaking once if it is set once?

IIf the dam needs to be broken every time for every bigger block, is there anything currently in BU causing those who are stubborn to repeatedly accept the bigger chain in any way only tentatively, like they do if two chain tips arrive below and above excessive block size? Just making sure: In that scenario, full nodes who have EB1/AD6 settings (for example) and receive 1.5MB blocks with some <1MB blocks in between should behave just like they do now with all <1MB blocks, correct? Or should they somehow still prefer the smaller chain?

If I understand it correctly, @theZerg, you would make it 'enlargen the dam up to once per day, up to the value that broke it'?

My very personal preference would be 'break the dam once' until further manual reset of the settings and I think that most closely matches people's expectation. As in 'If I set EB1/AD6 and I get 6 2MB blocks in a row, increase my setting to EB2/AD6 implicitly'. The important parameter then becomes mainly AD and is the dial-in stubbornness in units of time resp. number of blocks I am opposed to bigger blocks ...

But I have not a very strong opinion on this.

 

[dgenr8]

Thank you @freetrader for sponsoring BUIP038.

@awemany If you're referring to bitcoin.pdf, the probabilities there are different. Satoshi was examining a double-spend attack by minority hashrate, so he calculated the probability of a minority chain ever catching up from being behind by different numbers of blocks N, allowing it to reverse transactions at that depth. The catch-up could happen at any time in the future.

In our case, the two chains start at the same block, and we want to know the probability that the minority chain reaches a certain depth N before the majority chain does. The payoff is that miners with AD <= N-1 will have opened their sticky gate and dropped all objections to blocksize for 144 blocks.

In a BU world, EB is the only thing restraining blocksize at all. Overcoming AD=5 one time is much, much easier for a minority than having to do it repeatedly. And the payoff is asymmetric because all limits are removed (they are not just doubled or something like that).

The rule newEB = max(oldEB, 100kb + largest block in the last 144 (24 hours) on this chain) would not work without further tweaking because the attacker could still make his triggering EB block enormous.

 

[awemany]

In our case, the two chains start at the same block, and we want to know the probability that the minority chain reaches a certain depth N before the majority chain does. The payoff is that miners with AD <= N-1 will have opened their sticky gate and dropped all objections to blocksize for 144 blocks.

@dgenr8: I am still confused about the math, but it is probably me who's wrong somewhere . I am wondering now what you mean with a 'single attempt' at opening the gate. I get numbers similar to (but not quite the same) as yours if I sum the binomial probability of drawing K...2K-1 items (K=acceptance depth) out of 2K-1 (number of blocks after such a 'single attempt' would be decided) blocks, with given excessive block probability. Is that what you have in mind? How did you calculate the numbers?

In a BU world, EB is the only thing restraining blocksize at all. Overcoming AD=5 one time is much, much easier for a minority than having to do it repeatedly. And the payoff is asymmetric because all limits are removed (they are not just doubled or something like that).

The rule newEB = max(oldEB, 100kb + largest block in the last 144 (24 hours) on this chain) would not work without further tweaking because the attacker could still make his triggering EB block enormous.

That's a very good point. In other words, any dependence of the gate width on the size of the excessive block can be gamed/set by the attacker.

 

[dgenr8]

@awemany The time to get N blocks is the sum of N exponentially distributed random variables. This sum follows an Erlang distribution. The attacker's distribution of times is Erlang[N,q/600] and for the honest hashers, Erlang[N,(1-q)/600]. The attackers win if their time is less than the honest hashers' time.

Actually calculating the probabilities requires numerically evaluating a double integral. But it's pretty easy to get software do it these days. I used Mathematica.

 

[awemany]

@dgenr8: That approach makes sense.(In any case, you are right and I was wrong as this not the same as Satoshi's probabilities.)

But then I further thought a bit about the problem, and I still couldn't find anything wrong with doing my binomial approach as I described above.

Yesterday evening, I tried hard to find reasons why our numbers diverge but couldn't really find anything.

So that's why I tried your approach as well this morning. I get different numbers, but my numbers given your approach (double integral of Erlang functions) are the same as my numbers using a binomial approach.

See here, code included. Do you think this might be a numerical issue? Or am I doing something wrong here?

 

[dgenr8]

Nice!

AD=5 corresponds to N=6 (attacker has to mine the EB block itself, then 5 more). So our numbers match, and your approach must work too <grin>.

Take notice world. Around here, we like to verify all our claims with independent research using multiple approaches.

 

[awemany]

@dgenr8 : LOL. I thought I checked that, repeatedly so. Good catch. So we're on the same page. Great

 

[theZerg]

@dgenr8, there was quite a bit of discussion on this topic. But since this commit is so old it will be difficult to find it. Please remember how small the BU group was back then. I saw this as a bug fix to a vulnerability someone discovered in BUIP001. If the conversations around every bug fix needs to be documented, BU progress will slow dramatically.

Instead, the system, as defined by the Articles, gives the Developer the benefit of the doubt. And you noticing this commit and formally questioning it by issuing a BUIP is exactly how the process is defined in the Articles. If there are other concerns about the process, let us move them to another thread, and leave this one focused on this specific issue.

----- Specific responses:

> Since all of this is hypothetical, is it really the best option to add even more code now, in the
> form of an automatic EB increase? To try this overestimates the resources of the BU project.

The change I am proposing is quite simple. And the infrastructure to test it (excessive.py) is already there. The current 24 hour behavior is already being tested there, and to add this new effect is a few more LOC.

In the BUIP you say:
> If an attacker can succeed in this, he has 144 blocks which are permitted to be any size at all.

I disagree with your comment "any size at all". It would be better to say "...which are not artificially limited". The natural network limits which are shown in Peter R's fee market and my empty block paper would still limit block size.

So I question the effectiveness of this attack.

The attacker will spend a large amount of money (how much?) for the ability to issue spam blocks that will be extremely slow to propagate compared to thin blocks, especially since most of the transactions will not be already propagated -- he'll consume all "real" transactions very quickly and have to resort to self-generated spam. This large block may be beaten by siblings as per the "fee market" paper, or it will cause a set of subsequent empty blocks to be generated while the miners mine empty blocks during full block transmission and validation.

So the attacker will simply spend a huge amount of money to experimentally validate Peter R's and my papers.


Finally, presumably this has happened due to a somewhat contentious fork. What is happening to the attacker's fork while he is attacking the > 1MB fork? It is at a complete standstill, and it becomes clear that the BU fork has 100% hash power. How does the social effect of this compare to the social effect of the subsequent large block? This is important because the attack is one of perception: "look we forced the BU chain to handle a lot of spam".

Given your suggested 20% attack, on average how long will the 1MB fork have 0 blocks? How far ahead will the BU fork be when the attacker issues his huge block and sees it either ignored or accepted with a subsequent spate of empty blocks, reducing the average block size and proving to everyone the validity of our research?

I almost hope that an "attacker" tries this...

Perhaps a reasonable, zero development-effort outcome of this BUIP would be simply to recommend to miners a higher AD...

 

[awemany]

@dgenr8, there was quite a bit of discussion on this topic. But since this commit is so old it will be difficult to find it. Please remember how small the BU group was back then. I saw this as a bug fix to a vulnerability someone discovered in BUIP001. If the conversations around every bug fix needs to be documented, BU progress will slow dramatically.

Instead, the system, as defined by the Articles, gives the Developer the benefit of the doubt. And you noticing this commit and formally questioning it by issuing a BUIP is exactly how the process is defined in the Articles.

Agreed, and I think this makes a lot of sense (regarding the benefit of the doubt to the voted-in dev). Excellent point regarding this being part of the articles. I guess the correct mode of operation as per the articles here is to by now just discuss it as an issue/bug-report by dgenr8. As he in progress of making it a sponsored BUIP now, we'll have hopefully have a broader decision on this eventually.

We might want to later make the process more detailed when it is about our Core (no pun) defining features, such as BU's blocksize approach. But I agree that we probably right now don't have the manpower for that.

I think this sticky behavior also was an issue on github, or am I wrong there? I think that would help those who follow development through github.

I disagree with your comment "any size at all". It would be better to say "...which are not artificially limited". The natural network limits which are shown in Peter R's fee market and my empty block paper would still limit block size.

So I question the effectiveness of this attack.

I do as well. I think there's another, political/marketing layer involved in this, though. It might be easier to sell BU to small blockers if the gate wouldn't be sticky. Many people on reddit try to sell BU as a big blocks solution, but I have a suspicion that some small-blockers / bitgold-bugs are easier to convince of BU if we rather sell it as 'configure it as you wish' (which it is). OTOH, with AD999999, the sticky gate will never come into play anyways. Hard to say.

And given that @Peter R did a very nice medium post on the sticky gate, the process is now well documented and widely known, though.

Oh and for completeness, the expected attack cost in $ given the current block reward of 12.5BTC and a price of $738/BTC:

http://pastebin.com/aWqgQAbU

 

[dgenr8]

@theZerg I can't find any public discussion of the your original change at all, and have asked in multiple places. It would be really helpful if you provided a link.

You almost hope that an attacker tries this? Have you been observing the situation with ETH? If you are going to try a blockchain fork, can you afford to carelessly reduce security?

Bitcoin security builds from the continued addition of work with every block. For blocksize consensus, the stickiness reduces this security to only AD+1 blocks. Falling back on network limitations is very weak.

Since you and @awemany mentioned @Peter R, please note that he has supported this BUIP above. Miners should really be consulted as well. @Magma Hindenburg

Clicking the button on the PR I already prepared requires zero development.

 

[awemany]

I just did the cost calculation and edited by post above. Seeing the numbers I feel now that they are a tad bit too low to be comfortable. Remember that what some (myself included) call our enemies have $70e6 in funding, and 30% of hashpower (e.g. SegWit fraction so far) could mount an attack with a couple percent of that founding. Given that this could forge them a path where they could make lots and lots of more money, I feel a little uncomfortable. @solex: When is the next chance to vote on this BUIP?

Note that the spin from the Core team when the gate opens will be: See? BU has no blocksize limit now, you gave your soul to the devil...

 

[dgenr8]

@awemany "Attackers" in this scenario is not limited to those who wish to harm BU.

Stickiness changes the calculus of cooperating friendly miners, too:

When planning a blocksize increase, our numbers clearly show that less than 50% is required to increase the blocksize. 40% hashrate could do it in 3 attempts with 57% success (edited).

Does anybody really want that?

 

[awemany]

Fair point. I guess another thing that speaks against the gate is that just EB/AD is a more terse/lower-entropy/simpler/KISS-like approach and also easier to explain. I think I'll vote for your BUIP when it comes up for voting. Until then, it looks like you gotta sort this issue out with @theZerg. Please keep it friendly, both

(And yes, it is probably also a good idea to talk to the miners about this as well)

 

[freetrader]

I guess the correct mode of operation as per the articles here is to by now just discuss it as an issue/bug-report by dgenr8. As he in progress of making it a sponsored BUIP now, we'll have hopefully have a broader decision on this eventually.

My understanding is that dgenr8 has accepted that I formally sponsor the BUIP, so what we are discussing now is what @theZerg indicated in his original reply:

Once that happens, we enter a period (2 weeks I think) where I get to work with the author and sponsor to modify the BUIP. All modifications that I suggest are optional. But if I think that the modifications are not sufficient, I can propose a counter-BUIP and force the membership to choose between them.

I think that's very clear, and unless @dgenr8 withdraws this BUIP, the result will be determined by a vote, either on a modified form of this BUIP, or between this and a counter-BUIP proposed by @theZerg.
I am unclear on whether the process allows for other BUIPs to propose different adaptations and compete in a vote with the above, but given that the distinction between a reversion and a change is superficial, I guess others could propose BUIPs for modifications to the current state which are mutually exclusive but also up for vote.

So we are here to discuss proposed modifications to the original form of this BUIP, and the pros and cons of the reverted state, the current state and anything inbetween (some changes tbd).

 

[theZerg]

I just did the cost calculation and edited by post above. Seeing the numbers I feel now that they are a tad bit too low to be comfortable. Remember that what some (myself included) call our enemies have $70e6 in funding, and 30% of hashpower (e.g. SegWit fraction so far) could mount an attack with a couple percent of that founding. Given that this could forge them a path where they could make lots and lots of more money, I feel a little uncomfortable. @solex: When is the next chance to vote on this BUIP?

Note that the spin from the Core team when the gate opens will be: See? BU has no blocksize limit now, you gave your soul to the devil...

can you share your math?
[doublepost=1480535077][/doublepost]

@theZerg I can't find any public discussion of the your original change at all, and have asked in multiple places. It would be really helpful if you provided a link.

You almost hope that an attacker tries this? Have you been observing the situation with ETH? If you are going to try a blockchain fork, can you afford to carelessly reduce security?

Bitcoin security builds from the continued addition of work with every block. For blocksize consensus, the stickiness reduces this security to only AD+1 blocks. Falling back on network limitations is very weak.

Since you and @awemany mentioned @Peter R, please note that he has supported this BUIP above. Miners should really be consulted as well. @Magma Hindenburg

Clicking the button on the PR I already prepared requires zero development.

How does someone executing this attack result in a fork? BU will either incorporate the huge block into the blockchain, or orphan it.
[doublepost=1480535397][/doublepost]

@awemany "Attackers" in this scenario is not limited to those who wish to harm BU.

Stickiness changes the calculus of cooperating friendly miners, too:

When planning a blocksize increase, our numbers clearly show that less than 50% is required to increase the blocksize. 40% hashrate could do it in 12 blocks with 96.7% success.

Does anybody really want that?

In a network running BU this observation doesn't even make sense. You say "increase the blocksize", but there is no blocksize limit to increase.

Attackers could temporarily increase the typically accepted block size and drive a few large blocks onto the blockchain. But after a certain period, things will simply revert back to normal unless the attacker continues to waste his resources in this attack.

And then majority of nodes will simply increase their AD.