Rewriting history needs to be expensive, not just difficult. If you decrease the cost of writing history, you decrease the penalty of participating in a minority chain.
I always understood the security of block-chains as a race between the good and the bad agents.
Both are extending their respective chains as fast as they can. A bad-agent, who wishes to double-spend has to rewrite history, and therefore has to start a few step behind the good agent. To succeed, the bad agent has to overtake the good agent.
Even if both have the same speed (i.e. 50% computational power each), the good agent will sill be a few steps ahead of the bad agent, and the system is secure. If the bad agent is faster(51%), then eventually it will overtake the good agent breaking security.
This is true even if the cost of computation is zero (e.g. the Govt. pays for all your computation cost). As long as the bad agent doesn't have 51% or more of the computational power, the system is secure.
An attacker does not have to wait in order to produce a parallel chain. He can mine his separate chain immediately after submitting the transaction.
Even with less than 50% hashrate, he is bound to find a few blocks in a row from time to time. Keep in mind that he can run the attack as often as he wants. This is why the recommendation is to wait for 6 blocks - it is very unlikely (not impossible) that somebody with a 20% hashrate ever finds 6 blocks in a row.
When an attack is successful, everybody will mine on the attackers chain - including the honest miners. The attackers chain is valid after all, it just has a different valid transaction set.
The significance of the 51% hashpower is that the attacker is guaranteed to succeed over a long-enough time horizon.
Reducing or removing the costs of mining a parallel chain (even for miners with 20% hashpower) reduces their cost to mine a parallel chain and weakens the security guarantee. If a miner can work on a side chain and get paid for protein folding at the same time, he can keep doing it without losing money on electricity. When he finally succeeds, he will also cash in the mining reward.
But I wonder why doesn't this problem also arise in the current Proof-of-Work system. A sufficiently well-funded group, with about 20% hash-rate can try to extend the current head of the blockchain by 6 fake blocks at every time. If they succeed, i.e. all 6 fake blocks are mined before the real network mines 6 real blocks, then they can publish their parallel chain with the fake transactions and it would be longer than the real chain.
This is equivalent to the expected number of coin tosses to get 6 consecutive heads, where the coin is heads with probability 1/5. Here, heads means that a fake block is mined before the corresponding real block is mined.
This number is less than 20000, which corresponds to about 6 months of time. This is expensive, but not infeasible. They just need to remain solvent until they succeed and then easily cover the costs.
Yup, this is indeed a weakness of the current PoW system.
People often misunderstand it to be completely secure if no attacker has more than 50% hashrate.
In reality (and as described in the whitepaper), the 51% limit is described as the state where no number of confirmations is sufficient.
If an attacker has less than 50% hashpower, you can plug in some numbers like hashpower and cost of attack and come up with a number of confirmations that is likely to be secure.
