Bitcoin Forum

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

Methink these numbers are implausible.

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.

For rough estimates, 1 bitcoin Ghps = about 8TFLOPS. One bitcoinhash is ~4100 32 bit integer ops on ati 5/6xxx, and SP FLOPS on any recent arch = 2 * INTOPS.
so at 700Gh/s, about 5.6 PFLOPS or so.

Tianhe-1A has 4.7PFLOPS peak according to top500, so for peak values, yup, faster than worlds fastest known supercomputer.
That google number is from 2008, though 500k machines sounds awfully low. So... no clue.
For F@H ... Hard to compare, they don't have peak stats, guessing ~75% efficiency they're about 2x bitcoins current throughput.
Any multi-million-machine botnet? botnet wins.

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).

Wrong.

Hard to debate that.

Whatever is in the longest chain is the truth. Network clients won't (and can't) reject blocks that double-spend a transaction in one of the conflicting blocks.

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

It can't contain double-spends within itself, but it can double-spend transactions in conflicting chains. So you can double-spend from the perspective of a merchant if you have >50% of the network's computational power.

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.

That's what I thought.  So, at 50% of the mining power on the network, you would get on average every other block...if people were waiting on just one block for confirmation, it means that in order to double spend, you would have to be able to compute 2 blocks (containing your double spend) before the rest of the network is able to compute 2 blocks...you could do some double spending with that and undermine confidence in the network.  But, you still couldn't do it on any sufficiently long time horizon...if people waited even three or for blocks for confirmation, odds are pretty good that they would protected from double spends.  I wouldn't call that overthrowing the network (if it started happening, people would in fact start waiting longer for confirmations and that would quickly limit the theft a double spender could pull off), but it could certainly have a very detrimental affect on confidence in the system.  If the objective were to steal money, I don't think super computer would be an economical choice (the top 10 supercomputers are likely to cost far more than all the bitcoins in circulation).  But, maybe the economics are better for a botnet.  If the objective is to undermine the confidence in bitcoins, this attack could do a lot of damage and I think is the biggest threat that someone with a lot of mining power presents.

So, what does it mean exactly to "overthrow the bitcoin network"?

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.

And keep in mind this is 50% including yourself. You have to match 100% of the honest nodes.

I think it'll be impossible for US gov in one year.

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.

Don't forget that TOP500 refer to double precision numbers. So that 4.7 PFLOPS double precision is 9.4 PFLOPS single precision (these numbers x 2 (http://blog.zorinaq.com/?e=36)). The latter number is what should be compared to 8 TFLOPS (single precision) in your excercise.

Thanks for the correction, noted.

There is no need for such an imperfect comparison as FLOPs. I've calculated the Tianhe potential hashspeed by counting the GPUs and CPUs. It is roughly 850 Ghash/s.
http://bitcointalk.org/index.php?topic=4559.msg66931#msg66931
The Bitcoin total hashspeed is almost as high.

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   ;D