Bitcoin has attracted a lot of interest recently, due to its recent high value. Here we give a quick overview of how it works.
In the bitcoin system, transactions are stored in a distributed e-ledger, the blockchain, which is hard to forge for reasons we'll explore shortly.
A bitcoin transaction consists essentially of a list of inputs, and a list of outputs. Each output defines an amount of bitcoin (BTC) in units of \(10^{-8}\) BTC, or Satoshi, after the alias Satoshi Nakamoto of the inventor of the bitcoin system, and a corresponding script – a short program in a custom Forth-like language – which typically serves to allocate the bitcoin value to a particular bitcoin address. Each input to a transaction contains a link to an output of a previous transaction, and has its own accompanying script. A transaction is only accepted as valid if, for every input, running the input script followed by the script of the linked output gives the result "true". Elaborate scripts can be used, but usually they follow a simple predefined form to prove that the author of the transaction is a legitimate recipient according to the bitcoin address specified in each of the references outputs. This proof comes by way of a digital signature using ECDSA, the elliptic curve digital signature algorithm. In fact, each bitcoin address is a one-way function of an ECDSA verification key (public key). Usually, the input script simply provides the ECDSA verification key, and a signature of transaction-related data under the corresponding signing key; the output script checks the signature, and that the verification key corresponds to the bitcoin address. Note that an output of a transaction can only be used once as an input to a subsequent transaction. Although referenced outputs are fully used up by the transaction, one of the transaction outputs can act as "change".
Transactions are listed in blocks of the blockchain. Each block consists of a short (80 byte) block header, followed by a list of valid transactions. The block header contains a cryptographic hash dervied (via a Merkle hash tree) from hashes of the transactions, a 32 bit "nonce", the current time, a difficulty target value, the hash of the previous block – hence "block chain", and a hash of all the other data in the block header. The nonce (and the hash on the transactions, via data in a special transaction) are constructed so that the block hash, computed by two applications of the SHA-256 hash function, satisifies a particular criterion: the 256-bit hash considered as a 256-bit integer should be \(\leq\) the difficulty target.
Computing valid blocks is a demanding task, requiring a search over many nonce values. The search for the next valid block is distributed over nodes in the bitcoin network (which makes a pool of new transactions available), and the difficulty target set by the system (every 2016 blocks, about 2 weeks) so that the expected time for search to succeed is about 10 mins.. When the search succeeds, the updated chain is communicated to other nodes, and the race starts to compute the next block. Nodes accept the longest chain as the valid one. Consequently it's hard to replace the blockchain with a forged alternative. The reward for taking part in the block searches is given in bitcoins. The first transaction in a new block is a special transaction with no input (replaced by a text field) and output including the reward amount. The reward was initially 50BTC, and halves every 210,000 blocks: it's curently 12.5 BTC – a consequence is that at most 210,000 × 50 × (1+1/2+1/4+…) = 21,000,000 BTC will ever be minted. Block "miners" are also rewarded with transaction fees: typically the total BTC value of transaction inputs exceeds the total value of outputs by a small amount, and this difference is claimed by the block miner in the output of the first block. The transactions fees are an incentive to include many transactions in a block.