After discussing Bitcoin with a couple of friends yesterday, I was curious how much computational power is needed to fake transactions, and to double-spend money. From what I've read here, it also depends on the age of the transactions you want to fake.

Some facts (as of April 2011):

• The Bitcoin network currently has a processing power of ~10 PetaFLOP/s [1]
• The fastest supercomputer cluster has ~2,5 PetaFLOP/s [2]
  (it's located in China/Tianjin)
• The ten fastest super computers together have ~11 PetaFLOP/s [2]
• Google has a huge amount of "commodity hardware" (more than 500.000 PCs), which are estimated to have a total processing power of ~20-80 PetaFLOP/s [3]

To conclude:
The Bitcoin network has a processing power comparable to the ten fastest supercomputer clusters together. With a lot of money and coordination the network could be influenced, and transactions faked. Google would have to dedicate a big portion of its resources to do this. However, at any time a "good cluster" could save the network from being overthrown.

(please correct me if I'm wrong, or if I've misunderstood something  )

Sources:
[1] http://www.bitcoinwatch.com
[2] http://en.wikipedia.org/wiki/TOP500
[3] http://blogs.broughturner.com/communications/2008/05/google-surpasses-supercomputer-community-unnoticed.html

slush or deepbit could decide to be evil and run their own version of bitcoin.  But I imagine their bitcoin mining pool flock would fly to another pool if this was the case.

You're speaking of mining power, but that's not the whole story.  Power alone would not be sufficient to overthrow the network.  If you held 50% of the mining power (which would require that you double the current total power of the network), about every other block would be yours and you could slow down the rate at which transactions made it into the chain, you could try to double spend, but your direct peers would immediately reject blocks with double spends.  You could probably come up with some ways to create a DOS attack on the network.  But, I think enough people would recognize such chicanery and would take measures to isolate and remove the bad actor from the network. 

To take control over the block chain, you'd also need to control over 50% of the nodes on the p2p network that validate any blocks you create.  Your powerful hardware could also run a bunch of nodes, but I believe the client seeks diversity (in terms of ip addresses) in the nodes with which it will connect.  That would make it hard to overcome the validation that the p2p network performs.  You would need to double the number of clients *and* convince the rest of the network to connect up with them instead of others (so, you might need to arrange for a bunch of different IP address subnets).  A botnet could potentially accomplish this (a botnet for ip diversity in combination with some super computer miners might be a good way to go).  Or, you could also convince a bunch of people to run your special, hacked up client that changes the rules for block acceptance.  Or you could write a virus that targets the bitcoin executables to overwrite people's legit clients with your own hacked up version (that changes the rules for block acceptance).

Hard to debate that.

But the longest chain still has to be a valid chain correct (meaning, no double spends in that chain)?

I don't think what you're suggesting can even happen. A double-spend in 1 chain wouldn't occur because the transaction would get rejected immediately.

No. Even if the network gets one block between your two blocks, you refuse to build onto that block: you build only onto your blocks. Since you are a little faster than the real network, you can prevent all other blocks from appearing in your chain, which is the longest.

Ah, I see now.  If you compute the next two blocks faster than the rest of the network, the chances are still 50/50 whether you can compute the next block faster than the rest of the network.  But if you always build on your own blocks and not the shared blocks...on average, every other block created (by you or the network) will cause the entire network to oscillate between your block chain and the other block chain.

I was thinking the other day about the practice of encoding a block into the client (that basically fixates the chain as of some block in the recent past)...perhaps that should be codified in the client to happen in some way automatically...set a limit of say 60 blocks and make it so the client's will not accept any chain that alters a block that's more than 60 blocks old.  If someone were really paranoid about a transaction, they could wait 60 blocks (around 6 hours on average) for confirmation.  I'm guessing there's a downside to this, but I'm too exhausted to think through it at the moment.

Edit: One other thought...something like this might be useful for garnering transaction fees.  If you have this 60 block rule for firm embedding of the block chain...anyone needing rock solid confirmation within 6 hours would have an incentive to pay a fee with that transaction to ensure it gets included in the next block or two so they then only need to wait ~6 hours.  If they don't pay a fee and it takes a couple hours for the transaction to get into a block, they could be waiting 8 or more hours.

Thanks for the correction, noted.

The US is building a 20 petaflop machine at Oak Ridge:
http://www.techeye.net/hardware/us-titan-supercomputer-will-dwarf-chinas-tianhe-1a

But they made a classic newbie mistake of buying nVidia instead of ATI