Quote from: tromp on November 14, 2014, 03:34:13 PM

Quote from: Daedelus on November 13, 2014, 09:17:50 AM

Alice wants to attack the blockchain.
She owns private keys of 400 accounts totalling to 75% of the stake.
She is planning to rewrite the history from block 5'000.
Legit chain is at block 5'300 (less than 720).
Cumulative difficulty at block 5'000 is 8'000'000.
Cumulative difficulty at block 5'300 is 9'000'000.
How many SHA256 operations in average it's necessary to do to find a branch where cumulative difficulty at block 5'300 is at least 9'000'001?
Hint: Blocks from 5'000 to 5'300 were forged by 100% of the stake.
Without a detailed further explanation of the so called Nothing at Stake 'problem', further discussion is quite useless.

Well, first of all, if Alice has 75% of stake, then the simplest attack would be in the future:
just fork and keep both branches as equal in cumulative difficulty as possible, never letting
one get too far ahead of the other. Thus, there will never be consensus. In fact, for this attack,
one needs only 51%. Or even much less if other stakeholders work on both branches.

But for argument's sake, let's consider the original challenge. The math is pretty tricky, but let me
sketch the rough idea of an attack.

The regular history developed by picking, at each block, the minimum delay among the stakeholders.
This delay has some probability distribution and some expectation which is the average block interval.

If you reduce the stakeholders to 75%, then the distribution will shift to longer delays.
BUT, Alice is not limited to single-step extensions. She can compute a huge tree of all possible
k-step extensions. With 400 accounts, this tree will have 400^k leaves, and require roughly that
many SHA256 computations. But for large enough k, one would expect one of these leaves to have
a path with an unusually small sum of k delays, less than k times the average delay for all stakeholders.

The question is, how big a k do you need. And this obviously depends on both the number of accounts,
and percentage of stake held by Alice. For the given numbers, I expect a small k like 4 would suffice,
but this needs to be worked out in detail.

In that case, to cover 300 blocks, you'd need to compute 75 trees of 400^4 leaves each, for a rough
total of 75*400^4 = 1.92*10^12 SHA256s, well within the realms of feasibility.

For k larger than 6 this attack would become quite infeasible, but it's not clear to what percentage of stake
that corresponds, unless one goes through the math...

This doesn't make sense to me. All 400^k possibilities are very very likely to have less cumulative difficulty than the main chain, because 75% < 100%
The attack will probably fail. This attack does not make sense to me.

However, imagine she had 51% some 200 blocks ago, and sat on it, without staking. Then, she can stake them on a parallel, attack chain. The attack chain will have stake 51% > 49%, so it is very very likely to succeed just doing it the normal way, minimizing the delay, which requires only minimal hashrate. Be it 6, 200, or 720 blocks. This attack makes sense and does not need hashrate.