I just realised that my point 2 has already been considered of in the PDF too:
One strategy to protect against this would be to accept alerts from network nodes when they detect an invalid
block, prompting the user's software to download the full block and alerted transactions to confirm the inconsistency.
Another question, which I had forgot to ask: Could attacker nodes create new coins to spend? If a huge amount of CPU power was maintained, presumably the bad nodes could validate invalid Bitcoins (their own, cheaply minted)? Or would this be impossible, as even a thin client (the 'Simplified Payment Verification' clients, which haven't been programmed yet) would flag such coins as invalid?
The only way "new coins" are generated at the moment is through block generation. This is not a good way for an attacker to generate large amounts of BitCoins to use to defraud people. Under the current scheme you can't mint invalid BitCoins (barring software bugs) and under certain reasonable assumptions all BitCoin generation requires a similar amount of work.
There is an attack resembling what you have in mind however. The current scheme where the rate of block generation is only regulated by "difficulty" makes it possible. My proposed scheme outlined in
http://bitcointalk.org/index.php?topic=425.0 would make it effectively impossible. This is how it works....
The attacker can buy computer time from a botnet owner which provides access to a large amount of hash generation power or alternatively he has access to many HPC Amazon EC2 instances. The price of the computer processing is the power multiplied by the time.
The attacker also runs modified BitCoin software at a huge number of different IP addresses but because the software just acts like a network node and doesn't do any block generation it doesn't cost much to run.
He perhaps waits until the "difficulty" is lower than average and then generates a transaction which represents a huge transfer of bitcoins from one address to another. The originating address does not have the BitCoins but that doesn't matter. He then fires up his vast computing resources and generates enough sucessive hash blocks by himself to make the transaction go confirmed. He only transmits these hashblocks to merchants running the "Simplified Payment Verification" who only connect to IP addresses that he controls so the rest of the network doesn't even know anything is wrong. He does not forward network traffic which might alert the merchants to the fraud such as contradictory hashblocks. He then buys goods from those merchants using the credit implied by the transfer he's just rendered confirmed. He continues to generate enough hashblocks to render those transactions confirmed. The scammed merchant transfers the goods. The attacker shuts everything down and walks away with the goods.
ByteCoin