Bogus locator in getheaders (test data wanted)

[gmaxwell]

Full nodes use getblock AFAIK to synch, as of getheaders

Getblock is only used on known header connected candidate best chains, for many years now. In other words nodes will never speculatively request blocks anymore, they only request blocks that would be the best chain per the headers assuming the blocks are valid. (moreover the behavior being discussed is the same for both messages).

[1714132165]

1714132165

[1714132165]

1714132165

[1714132165]

1714132165

[aliashraf]

A conclusive proposal for this issue:

1- I suggest that when there is no drawback, choosing more optimized code is best practice. For this case, improving the code can be done without such a draw back and is recommended.

2- The length of a legit block locator is always less than or equal to

L=10*ceil(log₂N)

where N is the max (feasible) block height for the chain. N can conventionally be computed like this:  

N = (timestamp_of_ genesis_block - current_system_clock) /1000/60/10 + 60480  

Here N is an upper bound for any suggested fork of blockchain (60480 is used for 30 consecutive difficulty adjustments, like 14 months)

My intuitive assumption is that no legit node will suggest/accept forks with a chain much longer than what 10 minutes block time imposes. Although the longest chain rule is to be used when nodes are deciding between forks, there should be an upper bound for circumstances in which this policy is applicable, and should be dropped when a suggested fork length exceeds that upper bound.

One may theoretically find it feasible to have a chain relatively  longer than expectation because difficulty adjustment may fail to stabilize network block production rate but it would be temporary and flow of mining power can not continue to grow exponentially.

IOW, each client should be able to calculate an upper bound for the number of blocks present in the chain they are committed to and hence an upper bound for the number of hashes present in sent/received block locators, regardless of how fair it has been bootstrapped.

3- Any client that sends unreasonable number of hashes in block locator should be considered an attack agent and treated properly. No honest client is allowed to accept/relay a fork with unreasonable height.

[gmaxwell]

My intuitive assumption is that no legit node will suggest/accept forks with a chain much longer than what 10 minutes block time imposes.

No existing software that I'm aware of meets your assumption, they absolutely will do so. It's not at all clear to me how one could go about constructing a rule to not do so that would be guaranteed to not create convergence failures at least in some maliciously created situations.

Although the longest chain rule is to be used when nodes are deciding between forks, there should be an upper bound for circumstances in which this policy is applicable, and should be dropped when a suggested fork length exceeds that upper bound.

I think you might have buried the headline a bit here: Your conclusive solution as suggested a reworking of the whole consensus algorithm to ignore its primary convergence criteria, and replace it with some kind of "ignore the longest chain under some circumstances" but you aren't even specifying which circumstances or the exact nature of the change... making it impossible to review in any detail.

I don't at doubt that _some_ reasonable ones could be cooked up...  but why would be worth the effort to review such a potentially risky change, when the thing being to fixd is merely "someone can use a lot of bandwidth to temporarily drive your CPU usage higher"?   -- especially when there are a lot of ways to do that, e.g. set a bloom filter to match almost nothing and scan a lot of blocks... that has very low bandwidth per CPU burned.

But also think your suggestion is overkill:  If instead there is a BIP that says that locators should never have more than 10+10*ceil(log2(expected blocks)), then the nodes creating locators can determine if their locators would be too big and instead make their points further apart to stay within the limit (and presumably one less than it, to deal with time-skew).  No change in consensus required, nodes can still accept all the blocks they want. If you are on some many-block crazy fork, you'll request a sparser locator, and as a result just waste a bit more bandwidth getting additional headers that you already know.  --- and that's what I was attempting to suggest upthread: that the safe change is to first get honest requesters to limit themselves; then later you can ignore requests that are too big.

[aliashraf]

My intuitive assumption is that no legit node will suggest/accept forks with a chain much longer than what 10 minutes block time imposes.

No existing software that I'm aware of meets your assumption, they absolutely will do so. It's not at all clear to me how one could go about constructing a rule to not do so that would be guaranteed to not create convergence failures at least in some maliciously created situations.

I'm aware that no bitcoin client has implemented such a criteria to be met by forks (being in reasonable thresholds of longitude), they should, imo.

Although the longest chain rule is to be used when nodes are deciding between forks, there should be an upper bound for circumstances in which this policy is applicable, and should be dropped when a suggested fork length exceeds that upper bound.

I think you might have buried the headline a bit here: Your conclusive solution as suggested a reworking of the whole consensus algorithm to ignore its primary convergence criteria, and replace it with some kind of "ignore the longest chain under some circumstances" but you aren't even specifying which circumstances or the exact nature of the change... making it impossible to review in any detail.

Obviously, the criteria is:
Any fork, being the longest chain or not, is not allowed to exceed a computable threshold in length such that it would compromise the block generation rate imposed by other consensus rules.

Specifically, expected number of blocks should always be less than normal_number_of_ blocks_for_This_Time + a_safe_threshold

I've already suggested:

N = (timestamp_of_ genesis_block - current_system_clock) /1000/60/10 + 60480

 
Here N is an upper bound for any suggested fork of blockchain (60480 is used for 30 consecutive difficulty adjustments, like 14 months)

So we have a solid definition, provably safe and helpful in mitigating the DoS vulnerability under consideration here. I'm trying to understand why should we hesitate or use a more conservative approach like what you suggest:

If instead there is a BIP that says that locators should never have more than 10+10*ceil(log2(expected blocks)), then the nodes creating locators can determine if their locators would be too big and instead make their points further apart to stay within the limit (and presumably one less than it, to deal with time-skew).  No change in consensus required, nodes can still accept all the blocks they want. If you are on some many-block crazy fork, you'll request a sparser locator, and as a result just waste a bit more bandwidth getting additional headers that you already know.  --- and that's what I was attempting to suggest upthread: that the safe change is to first get honest requesters to limit themselves; then later you can ignore requests that are too big.

If the block locator rule is applicable, then one should have already calculated the #expected_blocks and he is primarily capable to avoid chains exceeding that threshold.

I don't at doubt that _some_ reasonable ones could be cooked up...  but why would be worth the effort to review such a potentially risky change, when the thing being to fixd is merely "someone can use a lot of bandwidth to temporarily drive your CPU usage higher"?   -- especially when there are a lot of ways to do that, e.g. set a bloom filter to match almost nothing and scan a lot of blocks... that has very low bandwidth per CPU burned.

I think the importance of the proposed criteria is more than just dealing with this specific DoS threat. Don't you?

I mean, messing with the holly Longest Chain Rule and putting a cap on it, is very inspiring.

I see a lot of potentials here.  
For instance, one could investigate how it would help to resist long range and bootstrap attacks more efficiently or how narrow  the safe_threshold could be set, etc.

[gmaxwell]

Obviously, the criteria is:
Any fork, being the longest chain or not, is not allowed to exceed a computable threshold in length such that it would compromise the block generation rate imposed by other consensus rules.

Taken strictly that criteria is violated by the existing chain. In other words, if it were imposed previously the network would have already faulted. Block 0 is timestamp 2009-01-03 18:15:05, this was 3501 days ago, which implies ~504144 blocks. Yet we are on 535244.

Any increase in hashrate will result in that condition, implemented strictly, being violated because the difficulty adjustment is retrospective and only proportional (it includes no integral component).  If the condition is violated it can cause spontaneous consensus failure by forcing blocktimes against the maximum time skew and causing the network to break into islands based on small differences in their local clocks. You can add margin so that it hasn't failed _yet_ on the current chain but what reason do you have to expect that it wouldn't fail at some point in the future for any given selection of margin?  There is no amount which the chain is guaranteed by construction to not get ahead by. Quite the opposite, under the simple assumption that hashrate will increase over time the chain is guaranteed to get ahead.

So we have a solid definition, provably safe

As far as I can see your posts contain no such proof. In fact, the existing chain being well ahead of the metric now is concrete proof that some arbitrary safety margin values are not safe. What reason do you have to believe another arbitrary value is safe given that some are provably not, beyond "this setting hasn't failed with the historic chain yet"?

Had your same series of reasoning been followed in 2012-- and set a margin of 1000 blocks (or whatever was twice the adequate value at that point in time) then sometime in the next year after the hashrate grew tremendously the network would have spontaneously broken into multiple chains.

and helpful in mitigating the DoS vulnerability under consideration here

What DOS vulnerability? There isn't one as far as any measurements have thus far determined.  Changing unrelated consensus rules in ways which only seem to satisfy a "doesn't fail yet on the existing chain" level of proof to fix a maybe service could be denied here node behavior seems, frankly, absurd.  Additionally, it seems just kind of lazy to the point of reckless indifference:  "I can't be bothered to implement some P2P within the performance envelope I desire, though it clearly can be through purely local changes, so I'm going to insist that the core consensus algorithm be changed."

If your concern is that this might hold a lock too long (though measurement shows that a node keeps working fine even slamming 200k lookups on every network message, with the code previously posted on the thread) -- then just change the message handling to drop the blinking lock between groups of entries!   In what universe does it makes sense address a simple implementation programming question through speculative consensus rules with arbritary parameters that would provably have failed already for some choices of the arbitrary parameters?

I'm trying to understand why should we hesitate or use a more conservative approach like what you suggest

Because it's trivial to prove that its safe and doesn't require changes to the bitcoin consensus rules which might open the system up to attack or spontaneous failure and can't create new node isolation vulnerabilities, etc.  Why? because some of us don't think of Bitcoin as a pet science project, understand that its difficult to reason about the full extent of changes, and actually care if it survives.  If you share these positions your should reconsider your arguments, because I don't think they make sense in light of them.

[aliashraf]

Obviously, the criteria is:
Any fork, being the longest chain or not, is not allowed to exceed a computable threshold in length such that it would compromise the block generation rate imposed by other consensus rules.

Taken strictly that criteria is violated by the existing chain. In other words, if it were imposed previously the network would have already faulted. Block 0 is timestamp 2009-01-03 18:15:05, this was 3501 days ago, which implies ~504144 blocks. Yet we are on 535244.

According to my suggested threshold of 60480, it doesn't fail.

Any increase in hashrate will result in that condition, implemented strictly, being violated because the difficulty adjustment is retrospective and only proportional (it includes no integral component).  If the condition is violated it can cause spontaneous consensus failure by forcing blocktimes against the maximum time skew and causing the network to break into islands based on small differences in their local clocks. You can add margin so that it hasn't failed _yet_ on the current chain but what reason do you have to expect that it wouldn't fail at some point in the future for any given selection of margin?  There is no amount which the chain is guaranteed by construction to not get ahead by. Quite the opposite, under the simple assumption that hashrate will increase over time the chain is guaranteed to get ahead.

In the last decade, starting from zero and reaching to 45o000 penta hash, experiencing GPU and FPGA and ASIC one after another and we got just 35000 more blocks. In the next decade, with such a hash power as the inertia, we don't expect even half of such a deviation, and more importantly it won't be just a jump like in few days or weeks, it would be incremental and observable and a simple increase in the threshold would be enough to resolve the problems you are worried about.

So we have a solid definition, provably safe

As far as I can see your posts contain no such proof. In fact, the existing chain being well ahead of the metric now is concrete proof that some arbitrary safety margin values are not safe. What reason do you have to believe another arbitrary value is safe given that some are provably not, beyond "this setting hasn't failed with the historic chain yet"?

It takes some time for me to prepare a formal mathematical proof that there is always a safe threshold for a large enough duration of time.

Had your same series of reasoning been followed in 2012-- and set a margin of 1000 blocks (or whatever was twice the adequate value at that point in time) then sometime in the next year after the hashrate grew tremendously the network would have spontaneously broken into multiple chains.

The suggested threshold of 60480 is not calculated as a fraction of current block height, it is the number of blocks in 30 consecutive difficulty adjustments. So in 2012 I'd suggest the same threshold.

and helpful in mitigating the DoS vulnerability under consideration here

What DOS vulnerability? There isn't one as far as any measurements have thus far determined.  Changing unrelated consensus rules in ways which only seem to satisfy a "doesn't fail yet on the existing chain" level of proof to fix a maybe service could be denied here node behavior seems, frankly, absurd.  Additionally, it seems just kind of lazy to the point of reckless indifference:  "I can't be bothered to implement some P2P within the performance envelope I desire, though it clearly can be through purely local changes, so I'm going to insist that the core consensus algorithm be changed."

It is too much!  
No, it is not a lazy approach, whatever. It is about stopping clients from pretending to be honest and innocently following a bogus chain when they are attempting to query a hypothetical chain with one billion  height when we expect just 500-600 thousands. That simple.

In what universe does it makes sense address a simple implementation programming question through speculative consensus rules with arbritary parameters that would provably have failed already for some choices of the arbitrary parameters?

In my universe, every rule has a criteria to met and it is a loose definition to say: the longer chain is always the better chain. I'll set a criteria on this rule: as long as its height is not obviously bogus.  

... some of us don't think of Bitcoin as a pet science project, understand that its difficult to reason about the full extent of changes, and actually care if it survives.  If you share these positions your should reconsider your arguments, because I don't think they make sense in light of them.

I don't agree. I'll provide proof that there exists a safe threshold for a long enough period that the block chain won't break through it and it is getting smaller in  time because of the inertia of the installed hash power.

I suppose with such a proof, it is ok to put a cap on LCR, right?

[gmaxwell]

According to my suggested threshold of 60480, it doesn't fail.

No but it would fail the _existing_ chain with a threshold of more than half that one. So your adhoc rule doesn't even have a safety margin of 2 against the existing chain-- much less against what is reasonably possible.  If hashrate grows quickly this threshold will be exceeded.  There is no constant threshold where large hashrate growth cannot exceed it.

No, it is not a lazy approach, whatever.

I don't find 'whatever' to be much of an argument. It still sounds to me that you think the whole network should potentially dangerous changes to the consensus rules in order to avoid having to correctly process a megabyte of network data without undue load. How isn't that lazy?

[aliashraf]

According to my suggested threshold of 60480, it doesn't fail.

No but it would fail the _existing_ chain with a threshold of more than half that one. So your adhoc rule doesn't even have a safety margin of 2 against the existing chain-- much less against what is reasonably possible.  

Once it is going to be merged, we would adjust the threshold for current block height such that from that moment we would have the required 30 epochs (difficulty adjustments) ahead.

If hashrate grows quickly this threshold will be exceeded.  There is no constant threshold where large hashrate growth cannot exceed it.

You are wrong here. With just a minor tweak in the algorithm, it is provably safe even for much smaller thresholds. The only problem would be the bootstrap nightmare  for which I've proposed such a large window from the first place, buying time (like one year) for adjusting the parameter hardcoded in the source and promoting it. I'll thoroughly describe and demonstrate the validity of this claims within next few hours and after finishing my work.  

No, it is not a lazy approach, whatever.

I don't find 'whatever' to be much of an argument. It still sounds to me that you think the whole network should potentially dangerous changes to the consensus rules in order to avoid having to correctly process a megabyte of network data without undue load. How isn't that lazy?

As I see, you are super conservatist when it comes to messing with core algorithm. Good for you. I admit this is absolutely necessary most times but I afraid in this case it is not helping.

First of all, I'm not suggesting this change just for mitigating the weak (let's put it this way) DoS vulnerability that OP has pointed out. I'm now concerned more about much critical problems like malicious bootstrapping which you have used up-thread as a possibility for innocent clients who should not be isolated because of this, remember?

Plus, I'm confident this policy, putting a cap on LCR, is good design pattern and will help securing the network efficiently as a general improvement in modelling the integrity of the protocol and 'discovering' a critical relationship between the longest chain rule  and other components of the protocol.

Back to conservatism, your alternative proposal for mitigating the (weak) vulnerability under consideration is not inspiring at all. I think the price we should pay for bitcoin being an operational network has not to be that high to become superstitious about touching 'sensitive parts'.

Anyway, I'll submit a post covering both a more refined algorithm and a comprehensive proof of safety and applicability of it,  in few hours as I promised, and I suppose  it would be of much fun discussing it  

EDIT: I just realized it to be more appropriate to do it in a more formal way. My apologies for the delay and will do my best to compensate with a thoughtful article asap.

[Coinr8d]

I'm sorry I was not yet able to provide the data. It would take me little more time to get to this again, but I can see Greg published a proposal and also implemented a fix that was already merged into bitcoin core. Thus it feels not so important any more to provide the data as the problem, if there was one, has been solved.

Thank you Greg for your time you put into this.

I will thus only try to provide the data later if someone requests it again.

[aliashraf]

It is good to see, @gmaxwell has made something out of this discussion. He is of a pragmatist type. 

Noticing that the pull request is a bit confused about the block locator maximum size, I made a comment. I'm now busy solving a more general problem: What's the maximum feasible length of a blockchain at any specific time?

Although the existence of such a boundary is intuitively obvious, and I have already progressed a lot, the proof takes a bit more work to be formalized. 

[aliashraf]

I just published my work on blockchain height divergence issue on a separate thread. I hope it would help to have a relatively better understanding of the subject and problems like what we have been discussing here in this topic.  

[poblico]

I'm sorry I was not yet able to provide the data. It would take me little more time to get to this again, but I can see Greg published a proposal and also implemented a fix that was already merged into bitcoin core. Thus it feels not so important any more to provide the data as the problem, if there was one, has been solved.

Thank you Greg for your time you put into this.

I will thus only try to provide the data later if someone requests it again.

FYI this was fixed in this PR
https://github.com/bitcoin/bitcoin/pull/13907