Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: ArcCsch on October 05, 2016, 03:54:29 PM



Title: A weakness in block chains?
Post by: ArcCsch on October 05, 2016, 03:54:29 PM
According to Bitcoin Wiki:
"Block chain length" is calculated from the combined difficulty of all the blocks, not just the number of blocks in the chain. The one that represents the most computation will win.

The worry addressed there was that an attacker reduces block difficulty, creating lots of new blocks.

There is, however, another concern, an attacker may increase block difficulty to just above that of the whole competing block chain.
Since PoW is added linearly to the 'true' chain, the attacker's probability rate of success is inversely proportional to the time.
Since the integral of 1/x diverges at infinity, any attacker, even with an arbitrarily small fraction of the total hash rate, will almost certainly eventually overtake the network.

Is this a problem?
Can this be prevented?
Are there any safeguards to prevent this?


Title: Re: A weakness in block chains?
Post by: achow101 on October 05, 2016, 04:01:57 PM
I'm having a hard time following what you are talking about. Can you provide an example?

In order to increase the difficulty, an attacker would need to be able to find blocks at a rate faster than a block every ten minutes. Thus they would need even more power than the network has at that time.


Title: Re: A weakness in block chains?
Post by: ArcCsch on October 05, 2016, 11:50:12 PM
Lets say that the current difficulty is X, being behind by N blocks (a total PoW of X*N), the attacker artificially sets (perhaps by messing with timestamps) the difficulty to X*N+d (with the smallest possible d), and continues raising the difficulty, to ensure that if a block is mined, it will surpass the main chain. As time goes on, the total main chain PoW=Sum(fork->leaf)[X] increases, and the attacker keeps increasing the set difficulty to Sum(fork->leaf)[X]+d to surpass the network with one block. If intuition does not fail me, this attack would almost certainly succeed.


Title: Re: A weakness in block chains?
Post by: achow101 on October 06, 2016, 12:17:00 AM
Lets say that the current difficulty is X, being behind by N blocks (a total PoW of X*N), the attacker artificially sets (perhaps by messing with timestamps) the difficulty to X*N+d (with the smallest possible d), and continues raising the difficulty, to ensure that if a block is mined, it will surpass the main chain. As time goes on, the total main chain PoW=Sum(fork->leaf)[X] increases, and the attacker keeps increasing the set difficulty to Sum(fork->leaf)[X]+d to surpass the network with one block. If intuition does not fail me, this attack would almost certainly succeed.
The attacker would have to be able to mine a lot of blocks. The difficulty only changes every 2016 blocks. Furthermore, the time used for calculating the two week period is actually the median of the last 11 blocks. So such an attack would require the attacker to be able to mine a lot of blocks within the retarget period. Furthermore, the time of the previous block does not affect the time of the next block, so the attacker would actually need to control the hash power of most of the network in order to shift the timestamps enough to affect the difficulty.


Title: Re: A weakness in block chains?
Post by: gmaxwell on October 06, 2016, 04:14:00 AM
Since the integral of 1/x diverges at infinity, any attacker, even with an arbitrarily small fraction of the total hash rate, will almost certainly eventually overtake the network.
Yup.  To be more specific:

An attacker with a constant fraction (like 0.01%) of the network hashpower, who starts attacks and keeps up their losing attack forever, constantly adjusting timestamps to make their difficulty go up as fast as possible,  _where the network hashrate (and the attacker's) increases exponentially_ overtakes with finite non-zero probability, and thus eventually overtakes.

This can be intuitively understood by observing that given exponential growth in rate the total work in history is just some large finite portion of the attacker's current hashrate... and the attacker has some low but finite odds of reaching any possible luck level.

If you do the math however, for any remotely reasonable choice of numbers the time the attacker must persist before they have a 50% chance of overtaking the results end up being insanely long, thousands and thousands of years-- to which you can reasonable answer "nodes shouldn't reorg a thousand years of blocks from their own timeline"-- making the attack pretty pointless. :) (just a brief dos attack on new systems joining the network-- until someone adds the one line of code blacklist to kill that specific attack chain. ... so N-thousand years of work that could have spent mining honestly, twarted by one line of code and achieving only an attack on a few new nodes joining the network).

This also doesn't work if hashrate isn't growing exponentially (with any exponent) for everyone.  Moore's law is not a physical law, it's an observation. Hashrates will stop growing at some point or another. :)


Title: Re: A weakness in block chains?
Post by: Qunenin on October 06, 2016, 03:50:48 PM
According to Bitcoin Wiki:
"Block chain length" is calculated from the combined difficulty of all the blocks, not just the number of blocks in the chain. The one that represents the most computation will win.

The worry addressed there was that an attacker reduces block difficulty, creating lots of new blocks.

There is, however, another concern, an attacker may increase block difficulty to just above that of the whole competing block chain.
Since PoW is added linearly to the 'true' chain, the attacker's probability rate of success is inversely proportional to the time.
Since the integral of 1/x diverges at infinity, any attacker, even with an arbitrarily small fraction of the total hash rate, will almost certainly eventually overtake the network.

Is this a problem?
Can this be prevented?
Are there any safeguards to prevent this?


It is always going to come down to consensus rule.  For a new coin or one that has very few nodes, there can be issues, maybe.  For Bitcoin, you are simply never going to force an altered chain down its throat. 


Title: Re: A weakness in block chains?
Post by: skang on October 07, 2016, 05:51:47 AM
As gmaxwell explained, tldr, it can happen but the probability is too low.

Without doing the math, it looks as if the difficulty at which the attacker is trying to find one single block, such that it is more than the combined difficulties of bitcoin blocks upto that point, would be such a big number that it would be impossible to hit it now. Maybe on new chains. Well if the math turns out that this can be used to kill new chains then this is another attack method which atleast, out of future reference needs & social humor, people should give a name to, or guide to one existing.


Title: Re: A weakness in block chains?
Post by: gatra on October 08, 2016, 03:46:06 AM

If you do the math however, for any remotely reasonable choice of numbers the time the attacker must persist before they have a 50% chance of overtaking the results end up being insanely long, thousands and thousands of years--

but the chances of overtaking get lower as time goes by, so it will never get to 50% if you have less hashpower than the network


Title: Re: A weakness in block chains?
Post by: Oralmat on October 08, 2016, 03:24:41 PM
According to Bitcoin Wiki:
"Block chain length" is calculated from the combined difficulty of all the blocks, not just the number of blocks in the chain. The one that represents the most computation will win.

The worry addressed there was that an attacker reduces block difficulty, creating lots of new blocks.

There is, however, another concern, an attacker may increase block difficulty to just above that of the whole competing block chain.
Since PoW is added linearly to the 'true' chain, the attacker's probability rate of success is inversely proportional to the time.
Since the integral of 1/x diverges at infinity, any attacker, even with an arbitrarily small fraction of the total hash rate, will almost certainly eventually overtake the network.

Is this a problem?
Can this be prevented?
Are there any safeguards to prevent this?


It is always going to come down to consensus rule.  For a new coin or one that has very few nodes, there can be issues, maybe.  For Bitcoin, you are simply never going to force an altered chain down its throat. 

In a small isolated network, you can make it look like you did something, but connecting to the main chain is always going to beat you down, no matter what.


Title: Re: A weakness in block chains?
Post by: gatra on October 17, 2016, 02:27:08 AM

If you do the math however, for any remotely reasonable choice of numbers the time the attacker must persist before they have a 50% chance of overtaking the results end up being insanely long, thousands and thousands of years--

but the chances of overtaking get lower as time goes by, so it will never get to 50% if you have less hashpower than the network


Oh... I see it now, what I wrote there is not correct... you say that you can get to any % you want as long as you keep growing exponentially... I wouldn't worry about that though...