Bitcoin Transactions

We describe the simplest case of transactions in Bitcoin. Bitcoin defines a coin as a chain of transactions. When transferring coins from A to B, A gets a hash of the previous transaction. A generates a new asymmetric key pair. A digitally signs using her generated private key the hash of the current transaction. The transaction will now consist of the hash of the previous transaction, the digital signature, A's public key, the hash of B's public key (B's address) and the coins that will be sent. A broadcasts the transaction to other nodes.

All nodes receiving the transaction verifies the ownership of the coins in that transaction. A user only stores private keys in their wallet. However, the public key can be easily generated from the private key in an asymmetric key pair (but not vice versa). So B receiving the transaction generates all her public key. She hashes the each key and compares it to the address in the transaction. If one is equal, this means that she now owns the coins in that transaction.

The first transaction in a transaction chain is the generation transaction, which gives 50 Bitcoins to a node that solves a block. The generation transaction is also the first transaction in a valid block.

How POW solves the Byzantine Generals' Problem

TEMPLATE

How POW is a solution to synchronization and global view.

One would question how the system handles consistency of block chains (or the transactions database) of every node. Each of the nodes must have all the transactions in their block chains.

Transactions are publicly announced and are broadcast to the network. If two same transactions are propagated nearly the same time, nodes will only accept the first one that arrives and incorporate it in their potential block, rejecting the second transaction. Now if the two transactions are almost sent to the network at the same time, majority of the nodes would receive the first transaction while the remaining nodes would accept the second one. The first transaction will obviously have a huge advantage on being included on the valid block and the block chain first since the collective CPU power of the majority nodes is greater than the other nodes. Note that the time of finding a proof-of-work by solving a block is proportional to the CPU power of all the nodes working on it. When a proof-of-work is found, the valid block will be propagated to other nodes. Nodes will drop their current potential block, add the received valid block to their block chain and work on a new block. The second transaction after seeing that the first transaction is in the new block chain will be considered as invalid.

Blocks are created every 10 minutes. If the average time becomes shorter up to a certain threshold, the difficulty of creating a block doubles. Suppose two different blocks (with slightly different transactions) are solved and propagated throughout the network nearly at the same time. A node keeps them both but only the first one that arrives is accepted to the chain. The transactions in the second valid block which are not in the first block will be included into the new potential block.

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.

Proof-of-work (POW)

A proof-of-work is a technique that requires a client to give “evidence” that it spent some time doing a time consuming work, building its reputation as a valid client. It is originally used as a security measure to prevent denial of attacks and spam. The client is usually challenged by solving a feasible but computationally difficult problem. This requires a certain amount of time to have a solution depending on the client's CPU power. The solution to the problem serves as the proof-of-work. Bitcoin uses a proof-of-work technique to address fundamental problems of a fully decentralized peer-to-peer digital currency.