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

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.

• 2^12 is 4096, so each computer with 2^40 hashes per second would require 68 minutes, not 16. – Murch Feb 16 '15 at 7:36
• agreed, can you answer the question? – Curious Feb 16 '15 at 8:16
• Got a bit sidelined in between, but I just did. :) – Murch Feb 16 '15 at 8:25
• – Murch Feb 16 '15 at 8:47
• Misconception: "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." should be: "quicker than ALL honest peers combined." – Jannes Feb 16 '15 at 9:33

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.

• Is the probability of finding proof of work for any block, where each node is working on different block is equivalent to the probability of finding proof of work for the given block, each node working on same block but with different nonce? – Curious Feb 16 '15 at 8:35
• SHA-256 is a cryptographic hash algorithm. That means, that nobody can predict which inputs will lead to a successful hash. Especially, it is irrelevant how big the change is between two inputs, as their outputs are not in a recognizable relationship to each other. Therefor, it does not matter what is changed about the input as long as there is some change. So, as long as nobody is duplicating the same inputs, working on different blocks or different nonces is equivalent. – Murch Feb 16 '15 at 8:41
• Finally I got it. – Curious Feb 16 '15 at 8:46
• I've just discovered Princeton's online course "Intro to Crypto and Cryptocurrencies", which covers Cryptographic Hashfunctions and collisions in the first few minutes, it seems to be building up to proof of work, but I have to leave for work now. ;) – Murch Feb 17 '15 at 6:39

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

• but if a new block is mined successfully by some honest node, it is added to the block chain and therefore all honest nodes have to consider this by computing its hash and including in the. Therefore, for honest nodes proof of work starts from scratch again because of ordering of blocks in the block chain. The attacker on other hand, can mine say 5-6 blocks in 10 min and broadcast them to the network, thus forming the longer chain. – Curious Feb 16 '15 at 5:51
• But the honest chain gets another block mined in another fraction of a second. Every hash has the same probability of being valid, but the honest guys get 32,000 hashes to the bad guy's one. "Proof of work" isn't something you make progress towards and then have to start over, it's something where you're as likely to get a valid hash in minute 1 as in minute 60. – cpast Feb 16 '15 at 5:53
• Also, the attacker has to increase his blockchain when he mines a block; even if "start from scratch" was a thing, the attacker would also have to do so. – cpast Feb 16 '15 at 5:59
• I understand that every node on the network is not trying the same think. but say a honest node A, finds a proof of work for a block and broadcasts it to the network. If valid proof of work is found, all peers on the network confirm this by adding thatblock to the block chain. Since, blocks in the block chain are ordered, the peers have to include the hash of newly included block in their proof of work and the computation starts again from the scratch. Am I wrong? Further I am assuming that the attacker is working independently and mines 6 new blocks and broadcast them together on the network. – Curious Feb 16 '15 at 6:05
• Also, every block must be added once in 10 min on an average. Otherwise, difficulty of proof of work is increased. How come, fraction of second is enough to mine a block? – Curious Feb 16 '15 at 6:26