How POW solves double spending problem

In an online currency, spending a digital token twice is possible because the owner can either retain the spent token on his local account or produce a duplicate of the token before spending. Traditional solutions involve a centralized trusted party that decides which transaction arrives first. However, problems arise due to weaknesses of a centralized system such as single point of failure. Another problem of this system is the need of trust to the central authority for checking every transactions.

Bitcoin implements a decentralized system which nodes agree on a single chronology of transactions. Transactions received by nodes that are inconsistent with the transaction database (a chain of transactions) is considered invalid. Receivers of the coins can check the transaction database first if these coins are already spent, thus preventing double spending.

The global database is created by a chain of valid blocks (block chain), where each block contains the hash of the previous block, a random number (nonce) and a hash tree of all recent transactions. A node creates a potential block which can become a valid block and added to the block chain if the node finds a solution to a known difficult CPU intensive problem: finding the numerical hash value of the potential block that is lower than a defined target. Note that incrementing the nonce changes the value of each hash of the potential block. The potential block is hashed (i.e. a SHA-256 hash), each hash with varying nonce, by the node a million times per second until it finds a solution. Received transactions broadcast by the network are immediately included in the transaction hash tree of the node's working block. In addition to the changing nonce, new transactions also changes the hash value of the whole block.

When a solution is found, the node broadcast the block to the network. The block becomes a valid block and all nodes add the valid block into their block chain. Other nodes accepting the valid block give up their current working potential block and begin to work on a new potential block. The new potential block will contain the hash of the latest valid block of the block chain, the nonce, and recent transactions: 1.) transactions in its transaction pool (i.e. transactions in the transaction hash tree of their old potential block) that were not in the latest valid block and 2.) all newly received transactions before starting work.

Through the use of digital signatures in transactions, an attacker node can only manipulate his own transactions. The attacker can double spend her coins. To do this however, she must go back to the block where her transaction is included, change that transaction and solve again the proof-of-work of that block. Modifying the block changes the hash of the block and also hash of the succeeding blocks after. She must also redo all the blocks (from the block where her transaction is found) up to the top, including new blocks the network is adding. The attacker creates a new branch from the block chain. The rule is all nodes consider the longest block chain branch the valid block chain. If the attacker's branch catches up and became the longest, all nodes in the network would agree that this branch is the valid block chain.

The creation time of a new valid block is proportional to the CPU power of all the nodes working on it. Unless the CPU power of the attacker is greater than of the honest nodes, double spending is difficult and is very unlikely to happen. It is proven mathematically that an attacker winning the race of outpacing the block chain of honest nodes becomes exponentially hard as new valid blocks are appended to the block chain.