Why does an adversary have to control 50% of the computing power to double spend?

Question

If transactions in a block are valid, in order to add that block in the block chain, a proof of work needs to be found. I have read the bitcoin paper by Satoshi.

If the difficulty of the proof of work requires say 2^52 computations (13 hex zeros) on an average, and since every node on the network is working independently, why can't the powerful adversary surpass the length of current block chain and present his version of block chain to the network? Specifically, why does the attacker have to control 1 percent or x percent of the network's computational power, when honest nodes on the network are not working in collaboration to find the proof of work?

If the adversary can find a proof of work quicker than the most powerful honest peer, he can compute a longer block chain and broadcast it to the network.

Let us assume that there are 2^20 nodes on the network, each computing 2^40 hashes per second on an average. Each node would then require 68 minutes to find a proof of work (trying 2^52 hashes). The total computing power of the network is number of nodes * computing power of each node = 2^20*2^40 = 2^60.

If the adversary operates at the speed of 2^45 hashes per second, he requires just 2^7 = 2 min to find a proof of work (2^52 hashes).

Now, the computing power of the network is 2^60, however each node is trying to find a proof of work independently. The computing power of adversary compared to the network is 32,000 times smaller. The amount of computing power controlled by the adversary is 1/32000 = 0.00001%, but still he can compute the longer block chain.

Please help, if I am assuming something wrong here. The honest nodes on the network do not work in collaboration. So attacker need not control 50% of computing power on the network and has to expend computing power just more than average computing power of the honest nodes.

Answer 1

There are two assumptions in your question that aren't completely correct.

1) Each node would then require 68 minutes to find a proof of work (trying 2^52 hashes).

The process of finding a new block is not a linear task of work that needs to be accumulated. Rather it is a random process. Instead of a pile of work you are going through that has a fixed size, you could think of it as a lottery: Each try can win, but in average it takes 2^52 tries to win. This distinction is very important, because…

2) The honest nodes on the network do not work in collaboration.

…it allows the network to collaborate without coordinating!
Every mining entity is trying to confirm a different block. This is so, because each is trying to claim the block reward for themselves, therefore at least one transaction, the coinbase transaction, must differ.¹
So, since we have established that we are looking at a random process, and everyone is working on different data, we realize that the honest nodes are not duplicating each other's work. Therefore, all the honest nodes are going through a lot more inputs together than the adversary, and in effect are collaborating at finding a new block.
As cpast has pointed out in the comments, it is also very important to realize that nobody loses progress by switching. Therefore, only the time that the block requires to propagate through the network is lost, and everybody will switch to the new block with the one just found as a parent as soon as they receive it. Finally, this means that we need to compare the mining power of the honest network with the adversary's mining power in order to see who can create the greater chain. And as you have said yourself, with your exemplary numbers the network is 2^15 times as powerful than the adversary.

¹ Also, they can be working of different sets of transactions, the transactions will be in a different order for different miners, the timestamp changes every second, and they add more random data to try different inputs.

Answer 2

Because it's irrelevant how long an individual honest node takes to mine a block. The honest nodes work independently, but if any of them mine a block they all move on to the next block. Nodes aren't all trying the same thing; each of the 2^20 honest nodes is looking at different hash values, so while an individual node only succeeds every 16 minutes on average, someone will get lucky and succeed after a minuscule fraction of a second (for instance, there's a 1/16 chance an honest miner succeeds in the first minute, so with 16 honest miners you'd expect someone to succeed then).