Potential bug in bitcoin: long-range attacks.

[jl2012]

I think it's more interesting than you make it out to be. Consider the fact that if you try to reorg the entire blockchain, you have 100% chance to eventually succeed, no matter how low your hashrate (assuming that the ratio between your hashrate and the network's has a positive lower bound).

Indeed, while I was well aware of growth making the historical hashing inconsequential (http://bitcoin.sipa.be/powdays-50k.png) and playing the reorg lottery I hadn't considered that particular possibility before reading that paper (thanks for the link). Though it does require also exponential growth, which is physically senseless in some sufficiently long run. It would probably be interesting to explore the probability distribution with a relaxed form of that assumption.

That's the beauty of it - the result doesn't require exponential growth (though it does help a bit). If the hashrate of attacker and network is fixed to eternity, the attacker still has a chance of 100% to succeed eventually. This is because the harmonic integral diverges (the cumulative PoW increases linearly, so his probability of success each day decreases inversely linearly. The sum of this goes to infinity and this can be translated to 100% probability of success).

A positive lower bound on the hashrate ratio is a sufficient (though not strictly necessary) condition for this guarantee.

I don't think this is really interesting as we won't have infinite time.

Could someone calculate the probability of A outpacing B in T years, given that:

• The hashrate ratio of A:B = 1:4
• B started mining 1 year before A

For T = 10^3, 10^6, and 10^9. I bet even with the 10^9 years the probability is still very tiny.

[Meni Rosenfeld]

I think it's more interesting than you make it out to be. Consider the fact that if you try to reorg the entire blockchain, you have 100% chance to eventually succeed, no matter how low your hashrate (assuming that the ratio between your hashrate and the network's has a positive lower bound).

Indeed, while I was well aware of growth making the historical hashing inconsequential (http://bitcoin.sipa.be/powdays-50k.png) and playing the reorg lottery I hadn't considered that particular possibility before reading that paper (thanks for the link). Though it does require also exponential growth, which is physically senseless in some sufficiently long run. It would probably be interesting to explore the probability distribution with a relaxed form of that assumption.

That's the beauty of it - the result doesn't require exponential growth (though it does help a bit). If the hashrate of attacker and network is fixed to eternity, the attacker still has a chance of 100% to succeed eventually. This is because the harmonic integral diverges (the cumulative PoW increases linearly, so his probability of success each day decreases inversely linearly. The sum of this goes to infinity and this can be translated to 100% probability of success).

A positive lower bound on the hashrate ratio is a sufficient (though not strictly necessary) condition for this guarantee.

I don't think this is really interesting as we won't have infinite time.

Could someone calculate the probability of A outpacing B in T years, given that:

• The hashrate ratio of A:B = 1:4
• B started mining 1 year before A

For T = 10^3, 10^6, and 10^9. I bet even with the 10^9 years the probability is still very tiny.

Actually, the probabilities for T = 10^3, 10^6, and 10^9 are 82.2%, 96.8%, 99.4%. Even for T=1 the probability is 15.9%.

I'm assuming of course the simplest case. In general, with a head start of S and a hashrate ratio of 1:H, the chance to succeed in time T is
1 - \exp ( - int_S^{S+T} 1/(Ht) dt )

Which can be reduced to
1 - (1 + T/S) ^ (-1/H)

[jl2012]

I think it's more interesting than you make it out to be. Consider the fact that if you try to reorg the entire blockchain, you have 100% chance to eventually succeed, no matter how low your hashrate (assuming that the ratio between your hashrate and the network's has a positive lower bound).

Indeed, while I was well aware of growth making the historical hashing inconsequential (http://bitcoin.sipa.be/powdays-50k.png) and playing the reorg lottery I hadn't considered that particular possibility before reading that paper (thanks for the link). Though it does require also exponential growth, which is physically senseless in some sufficiently long run. It would probably be interesting to explore the probability distribution with a relaxed form of that assumption.

That's the beauty of it - the result doesn't require exponential growth (though it does help a bit). If the hashrate of attacker and network is fixed to eternity, the attacker still has a chance of 100% to succeed eventually. This is because the harmonic integral diverges (the cumulative PoW increases linearly, so his probability of success each day decreases inversely linearly. The sum of this goes to infinity and this can be translated to 100% probability of success).

A positive lower bound on the hashrate ratio is a sufficient (though not strictly necessary) condition for this guarantee.

I don't think this is really interesting as we won't have infinite time.

Could someone calculate the probability of A outpacing B in T years, given that:

• The hashrate ratio of A:B = 1:4
• B started mining 1 year before A

For T = 10^3, 10^6, and 10^9. I bet even with the 10^9 years the probability is still very tiny.

Actually, the probabilities for T = 10^3, 10^6, and 10^9 are 82.2%, 96.8%, 99.4%. Even for T=1 the probability is 15.9%.

I'm assuming of course the simplest case. In general, with a head start of S and a hashrate ratio of 1:H, the chance to succeed in time T is
1 - \exp ( - int_S^{S+T} 1/(Ht) dt )

It sounds really unbelievable for T=1 the probability is 15.9%. To outpace B, A has to outpace the work done in the first year (which the expected time is 4 years), while at the same time B is still working 3 times faster than A.

Would you please present your integration in https://www.wolframalpha.com ? Thanks.

[ShadowOfHarbringer]

checkpoints.

Have nothing to do with this.  A general tip: if you are commenting on the security of Bitcoin and the word "checkpoint" comes to mind, you are probably confused.

This thread was answered completely and correctly in the very first response. This attack does not exist because Bitcoin chooses the chain with the most work, not the most blocks.

Now I am confused (apparently).

Weren't checkpoints supposed to contain hashes of specific blocks so it would be impossible to supply entire fake blockchain that is ahead of the real one ?

Didn't Satoshi implement checkpoints for such attack to be impossible ?

[telepatheic]

Now I am confused (apparently).

Weren't checkpoints supposed to contain hashes of specific blocks so it would be impossible to supply entire fake blockchain that is ahead of the real one ?

Didn't Satoshi implement checkpoints for such attack to be impossible ?

Checkpoints are intended to allow faster and less error prone catching up with the current chain. Without checkpoints, clients could waste days of CPU time verifying fake chains, only to find they have a lower cumulative difficulty. They also help estimate how much of the initial chain download has been verified.

Without checkpoints, clients would eventually converge upon the correct chain but if connected to many malicious nodes this would take much longer.

[Meni Rosenfeld]

I don't think this is really interesting as we won't have infinite time.

Could someone calculate the probability of A outpacing B in T years, given that:

• The hashrate ratio of A:B = 1:4
• B started mining 1 year before A

For T = 10^3, 10^6, and 10^9. I bet even with the 10^9 years the probability is still very tiny.

Actually, the probabilities for T = 10^3, 10^6, and 10^9 are 82.2%, 96.8%, 99.4%. Even for T=1 the probability is 15.9%.

I'm assuming of course the simplest case. In general, with a head start of S and a hashrate ratio of 1:H, the chance to succeed in time T is
1 - \exp ( - int_S^{S+T} 1/(Ht) dt )

It sounds really unbelievable for T=1 the probability is 15.9%. To outpace B, A has to outpace the work done in the first year (which the expected time is 4 years), while at the same time B is still working 3 times faster than A.

Would you please present your integration in https://www.wolframalpha.com ? Thanks.

Sure, http://www.wolframalpha.com/input/?i=1+-+Exp%28-Integrate%281%2F%284+t%29%2C+{t%2C+1%2C+2}%29%29

By the way, I've edited to add the simpler form of this expression, 1 - (1 + T/S) ^ (-1/H).

I parsed your scenario as Attacker:Honest = 1:4 and that the attacker never contributed to the honest network. If instead it's Attacker:Total = 1:4, so Attacker:Honest = 1:3 (but the attacker was honest in the first year), it's even higher, 17.0%.

It's actually quite intuitive. Suppose he tries a weaker strategy of trying throughout the year to find a single huge block that is equal to 2 years of the honest network's work. This is equal to 8 years of the attacker work, so the chance to find such a huge block in a year is 1/8 = 12.5%. But in his actual strategy he spends the first day trying to find a block equal to 1 year, in the second day a block equal to 1.03 years, and so on, so the probability is higher.

Needless to say, if instead of a huge block he tried to find several normal blocks, he would have no chance. The variance then is much lower so he can't luck out.

[ShadowOfHarbringer]

Now I am confused (apparently).

Weren't checkpoints supposed to contain hashes of specific blocks so it would be impossible to supply entire fake blockchain that is ahead of the real one ?

Didn't Satoshi implement checkpoints for such attack to be impossible ?

Checkpoints are intended to allow faster and less error prone catching up with the current chain. Without checkpoints, clients could waste days of CPU time verifying fake chains, only to find they have a lower cumulative difficulty. They also help estimate how much of the initial chain download has been verified.

Without checkpoints, clients would eventually converge upon the correct chain but if connected to many malicious nodes this would take much longer.

Well then, wouldn't it be possible to put in checkpoints containing parts (or hashes) of the historically valid chain, so it becomes impossible to supply a longer fake chain ?

[telepatheic]

Well then, wouldn't it be possible to put in checkpoints containing parts (or hashes) of the historically valid chain, so it becomes impossible to supply a longer fake chain ?

The checkpoints do contain the hashes see the source code https://github.com/bitcoin/bitcoin/blob/master/src/checkpoints.cpp Even with checkpoints you can still make longer fake chains (which fork after the last checkpoint) but they won't be the real chain because they will have lower cumulative difficulty.

[ShadowOfHarbringer]

Well then, wouldn't it be possible to put in checkpoints containing parts (or hashes) of the historically valid chain, so it becomes impossible to supply a longer fake chain ?

The checkpoints do contain the hashes see the source code https://github.com/bitcoin/bitcoin/blob/master/src/checkpoints.cpp Even with checkpoints you can still make longer fake chains (which fork after the last checkpoint) but they won't be the real chain because they will have lower cumulative difficulty.

Ah, so I was (partially) right after all.
Well, that's right - you can still make longer fake chains.

OK, nothing more for me to do here.

[jl2012]

I don't think this is really interesting as we won't have infinite time.

Could someone calculate the probability of A outpacing B in T years, given that:

• The hashrate ratio of A:B = 1:4
• B started mining 1 year before A

For T = 10^3, 10^6, and 10^9. I bet even with the 10^9 years the probability is still very tiny.

Actually, the probabilities for T = 10^3, 10^6, and 10^9 are 82.2%, 96.8%, 99.4%. Even for T=1 the probability is 15.9%.

I'm assuming of course the simplest case. In general, with a head start of S and a hashrate ratio of 1:H, the chance to succeed in time T is
1 - \exp ( - int_S^{S+T} 1/(Ht) dt )

It sounds really unbelievable for T=1 the probability is 15.9%. To outpace B, A has to outpace the work done in the first year (which the expected time is 4 years), while at the same time B is still working 3 times faster than A.

Would you please present your integration in https://www.wolframalpha.com ? Thanks.

Sure, http://www.wolframalpha.com/input/?i=1+-+Exp%28-Integrate%281%2F%284+t%29%2C+{t%2C+1%2C+2}%29%29

By the way, I've edited to add the simpler form of this expression, 1 - (1 + T/S) ^ (-1/H).

I parsed your scenario as Attacker:Honest = 1:4 and that the attacker never contributed to the honest network. If instead it's Attacker:Total = 1:4, so Attacker:Honest = 1:3 (but the attacker was honest in the first year), it's even higher, 17.0%.

It's actually quite intuitive. Suppose he tries a weaker strategy of trying throughout the year to find a single huge block that is equal to 2 years of the honest network's work. This is equal to 8 years of the attacker work, so the chance to find such a huge block in a year is 1/8 = 12.5%. But in his actual strategy he spends the first day trying to find a block equal to 1 year, in the second day a block equal to 1.03 years, and so on, so the probability is higher.

Needless to say, if instead of a huge block he tried to find several normal blocks, he would have no chance. The variance then is much lower so he can't luck out.

How about another scenario:

Hash rate A:B = 1:H . A is attacker, B is honest

A wants to outpace the latest X year's blocks. What is the probability for him to succeed in Y years? (A only wants to outpace the latest blocks. For example, with X=1, on 1 Jan 2014, A wants to mine a single block to outpace all the blocks since 1 Jan 2013; on 15 Jan 2014, the target will be the blocks since 15 Jan 2013). I think it's even easier, right?

[cr1776]

This isn't a bug because chains are selected in terms of cumulative difficulty not length of chain. Very quickly a node can distinguish the real chain from the fakes.

Then it is even easier to perform this attack, in theory.
All you would have to do is create a whole bunch of low-difficulty blocks with nearly the same timestamp, then after the "difficulty adjustment" in your branch of the blockchain would result in a super large difficulty. Solve that one block and the blockchain is broken.

Note cumulative, not last.

He's talking about cumulative, but that's irrelevant. The expected work required for that "super large difficulty block*" equals to the cumulative work of all blocks in the past 5 years

(*ignoring the 4x adjustment rule)

It doesn't seem like he is talking about cumulative difficulty given that he says mine a whole bunch of low-difficulty blocks with nearly the same timestamp and then have a super large difficulty adjustment.  The cumulative difficulty (e.g. the sum of the difficulty - each block weighted by difficulty) of his chain would be less than the real chain even with that last super large difficulty adjustment.  It appears from his description that he is relying upon the last super large difficulty increase to break the chain.  He might have the longest chain, but not the highest cumulative difficulty.

Regardless, there are numerous other issues with it, but the lack of cumulative difficulty being accounted for seems to be one.

[Meni Rosenfeld]

How about another scenario:

Hash rate A:B = 1:H . A is attacker, B is honest

A wants to outpace the latest X year's blocks. What is the probability for him to succeed in Y years? (A only wants to outpace the latest blocks. For example, with X=1, on 1 Jan 2014, A wants to mine a single block to outpace all the blocks since 1 Jan 2013; on 15 Jan 2014, the target will be the blocks since 15 Jan 2013). I think it's even easier, right?

Yes. The integral is then over the constant function 1/(HX) which gives a result of 1 - Exp (-Y/(HX)).

e.g., for X=1, Y=1, H=4 this gives 22.1%.

As a reminder, these calculations are for the case that everyone's hashrate is fixed. If it grows over time, the numbers will be different (in the attacker's favor).

[jl2012]

How about another scenario:

Hash rate A:B = 1:H . A is attacker, B is honest

A wants to outpace the latest X year's blocks. What is the probability for him to succeed in Y years? (A only wants to outpace the latest blocks. For example, with X=1, on 1 Jan 2014, A wants to mine a single block to outpace all the blocks since 1 Jan 2013; on 15 Jan 2014, the target will be the blocks since 15 Jan 2013). I think it's even easier, right?

Yes. The integral is then over the constant function 1/(HX) which gives a result of 1 - Exp (-Y/(HX)).

e.g., for X=1, Y=1, H=4 this gives 22.1%.

As a reminder, these calculations are for the case that everyone's hashrate is fixed. If it grows over time, the numbers will be different (in the attacker's favor).

Let say I have 1% of total hashrate (H=99), and want to outpace 1 day of blocks in 30 days (X=1, Y=30).

The probability is: 1-Exp(-30/99)=26.14%

and 97.5% in 1 year

The cost of this attack is about 1080BTC for 30 days or 13140BTC for 1 year, plus depreciation and electricity. It's expensive but still much cheaper than I thought.

[Meni Rosenfeld]

The cost of this attack is about 1080BTC for 30 days or 13140BTC for 1 year, plus depreciation and electricity.

It's not plus, it's either/or. If the alternatives you're comparing are attacking or not mining at all, the cost to attack is depreciation+electricity. If the alternatives are attacking or mining normally, the cost to attack is the lost mining revenue.

[jl2012]

The cost of this attack is about 1080BTC for 30 days or 13140BTC for 1 year, plus depreciation and electricity.

It's not plus, it's either/or. If the alternatives you're comparing are attacking or not mining at all, the cost to attack is depreciation+electricity. If the alternatives are attacking or mining normally, the cost to attack is the lost mining revenue.

Let's go back to the reality. Since there is a 4x difficulty adjustment rule, does it mean an attack of this kind won't be able to reverse more than 4 blocks?

[gmaxwell]

Let's go back to the reality. Since there is a 4x difficulty adjustment rule, does it mean an attack of this kind won't be able to reverse more than 4 blocks?

No, the idea is that they keep trying to mine blocks, each time specifying times needed to get the maximum possible ramp— mining 2016 blocks between each 4x difficulty change. The first are easy, obviously, but eventually they become very unlikely to ever get a block. The key point is that the last couple of their lucky steps are more apparent work than all the history, if you assume exponential growth. The key points that makes this unreal is that while the probablity tends to one— assuming the attacker keeps a fixed arbitrary ratio the the network and the network grows exponentially, its negligible over sane timeframes.

When talking about the compact SPV proofs for total chain work the same kind of variance problem arises, that is to say that while the _expected_ work to produce a compact SPV proof is the same as the expected work for the long sequence of normal difficulty blocks it replaces, the reduced sample count means that the probability of 'getting lucky' and being able to mine a compact proof with less work than it would have taken you to do regular blocks of the same difficulty is much higher.

It occurred to me that by requiring additional edges in the proof you can ask about the work over alternative confidence intervals (bounded by base difficulty), and not just the expected work. E.g. "I am 50% confident that this chain had at least work X". In effect you can trade off proof size for decreased variance. But for most of the interesting applications of compact SPV proofs variance 'attacks' were really only interesting right at the tip of the chain (e.g. making a lucky bogus block that has a skip 6 blocks back to where a transaction question was committed), and so it would be easy enough to just demand that your last couple links in the proof be regular difficulty.

I suspect there may actually be an improvement possible to this variance game by having miners commit to lower difficulty solutions and provide them according to some cut-and-choose, and allow for a test of two chains against each other not just in terms of expected work, but according (e.g. to x-percentile work). It would probably take a lot of work to figure out the details here, and maybe in the exponential growth forever assumption it still doesn't work out unless you toss scalability out the window by having to exponentially increase the data disclose along with the exponential increases in hashrate.

[Meni Rosenfeld]

The cost of this attack is about 1080BTC for 30 days or 13140BTC for 1 year, plus depreciation and electricity.

It's not plus, it's either/or. If the alternatives you're comparing are attacking or not mining at all, the cost to attack is depreciation+electricity. If the alternatives are attacking or mining normally, the cost to attack is the lost mining revenue.

Let's go back to the reality. Since there is a 4x difficulty adjustment rule, does it mean an attack of this kind won't be able to reverse more than 4 blocks?

...

See also Lear's linked paper, which discusses the modified strategy that deals with the 4x rule.