Bitcoin

The white paper at a glanceSearch on YouTubeBookmarkSaved

Satoshi Nakamoto published Bitcoin: A Peer-to-Peer Electronic Cash System in 2008. It is a reference text for the course. Its goal is online payments sent directly from one party to another without a financial institution.

IntroductionSearch on YouTubeBookmarkSaved

Internet commerce relies on financial institutions as trusted third parties. This trust-based model has weaknesses:

• Completely non-reversible transactions are not possible, because institutions must mediate disputes.
• Mediation increases transaction costs and limits the minimum practical transaction size. Small casual payments become impractical.
• Because reversal is possible, merchants must distrust customers and ask for more information than needed. A certain percentage of fraud is accepted as unavoidable.

The paper proposes an electronic payment system based on cryptographic proof instead of trust. Transactions that are computationally impractical to reverse protect sellers from fraud. Escrow can protect buyers. The double-spending problem is solved with a peer-to-peer distributed timestamp server that generates computational proof of the chronological order of transactions. The system is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.

TransactionsSearch on YouTubeBookmarkSaved

An electronic coin is defined as a chain of digital signatures.

Each owner transfers the coin to the next by:

1. Digitally signing a hash of the previous transaction and the public key of the next owner.
2. Adding these to the end of the coin.

A payee can verify the signatures to verify the chain of ownership.

The double-spending problemSearch on YouTubeBookmarkSaved

The payee cannot verify that a previous owner did not double-spend the coin. The usual fix is a trusted central authority, a mint, that checks every transaction. After each transaction the coin returns to the mint, which issues a new coin. Only coins issued directly by the mint are trusted. The problem: the fate of the whole money system depends on the company running the mint, just like a bank.

To work without a trusted party:

• Transactions must be publicly announced.
• Participants need a system to agree on a single history of the order in which transactions were received.
• The payee needs proof that, at the time of each transaction, the majority of nodes agreed it was the first received.

For Bitcoin, only the earliest transaction counts. Later attempts to double-spend are ignored.

Timestamp serverSearch on YouTubeBookmarkSaved

The solution begins with a timestamp server.

1. Take a hash of a block of items to be timestamped.
2. Widely publish the hash (like a newspaper or Usenet post).
3. The timestamp proves the data existed at that time, since it went into the hash.
4. Each timestamp includes the previous timestamp in its hash, forming a chain.

Each additional timestamp reinforces the ones before it.

Proof-of-workSearch on YouTubeBookmarkSaved

A distributed timestamp server on a peer-to-peer basis needs a proof-of-work system similar to Adam Back's Hashcash.

• Proof-of-work means scanning for a value that, when hashed (for example with SHA-256), gives a hash that begins with a number of zero bits.
• The average work required is exponential in the number of zero bits required.
• The result can be verified by executing a single hash.
• Bitcoin implements it by incrementing a nonce in the block until a value gives the block's hash the required zero bits.

Once CPU effort has been spent to satisfy the proof-of-work, the block cannot be changed without redoing the work. Later blocks are chained after it, so changing a block means redoing the work of that block and all blocks after it.

One-CPU-one-voteSearch on YouTubeBookmarkSaved

Proof-of-work also solves majority decision making.

• If the majority were based on one-IP-address-one-vote, anyone able to allocate many IPs could subvert it.
• Proof-of-work is essentially one-CPU-one-vote.
• The majority decision is the longest chain, which has the greatest proof-of-work effort invested in it.
• If a majority of CPU power is controlled by honest nodes, the honest chain grows fastest and outpaces any competing chain.

To modify a past block, an attacker must redo the proof-of-work of that block and all blocks after it, then catch up with and surpass the honest nodes. Section 11 shows the probability of a slower attacker catching up falls exponentially as more blocks are added.

DifficultySearch on YouTubeBookmarkSaved

To compensate for faster hardware and varying interest in running nodes, the proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour. If blocks are generated too fast, the difficulty increases.

NetworkSearch on YouTubeBookmarkSaved

The steps to run the network are:

1. New transactions are broadcast to all nodes.
2. Each node collects new transactions into a block.
3. Each node works on finding a difficult proof-of-work for its block.
4. When a node finds a proof-of-work, it broadcasts the block to all nodes.
5. Nodes accept the block only if all transactions in it are valid and not already spent.
6. Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash.

Further rules:

• Nodes always consider the longest chain to be the correct one and keep working on extending it.
• If two nodes broadcast different versions of the next block at the same time, some nodes receive one first. They work on the first one they received but save the other branch in case it becomes longer.
• The tie breaks when the next proof-of-work is found and one branch becomes longer. Nodes on the other branch switch to the longer one.
• New transaction broadcasts do not need to reach all nodes. Once they reach many nodes, they get into a block before long.
• Block broadcasts tolerate dropped messages. A node that misses a block requests it when it receives the next block and sees it missed one.

IncentiveSearch on YouTubeBookmarkSaved

• By convention, the first transaction in a block is a special transaction that starts a new coin owned by the block's creator. This is the coinbase transaction.
• This gives nodes an incentive to support the network. It also distributes coins into circulation, since there is no central authority to issue them.
• The steady addition of a constant amount of new coins is like gold miners spending resources to add gold to circulation. Here the resources are CPU time and electricity.
• The incentive can also be funded with transaction fees. If the output value of a transaction is less than its input value, the difference is a fee added to the block's incentive.
• Once a predetermined number of coins have entered circulation, the incentive can move entirely to transaction fees and be completely inflation free.

The incentive also encourages nodes to stay honest. A greedy attacker who has more CPU power than all honest nodes must choose: defraud people by stealing back his payments, or use the power to generate new coins. He ought to find it more profitable to play by the rules, which give him more new coins than everyone else combined, than to undermine the system and the validity of his own wealth.

Reclaiming disk spaceSearch on YouTubeBookmarkSaved

Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space.

• Transactions are hashed in a Merkle tree. Only the root is included in the block's hash.
• Old blocks can be compacted by stubbing off branches of the tree. Interior hashes do not need to be stored.
• This does not break the block's hash, because the header only commits to the root.

Size estimate:

• A block header with no transactions is about 80 bytes.
• With a block every 10 minutes: $80 \text{ bytes} \times 6 \times 24 \times 365 = 4.2\text{ MB}$ per year.
• Computers in 2008 typically had 2 GB of RAM, and Moore's Law predicted growth of 1.2 GB per year, so storage is not a problem even if headers are kept in memory.

Simplified payment verificationSearch on YouTubeBookmarkSaved

Simplified Payment Verification (SPV) lets a user verify payments without running a full network node.

1. The user keeps only a copy of the block headers of the longest proof-of-work chain. He gets them by querying network nodes until convinced he has the longest chain.
2. He obtains the Merkle branch linking the transaction to the block it is timestamped in.
3. He cannot check the transaction himself, but by linking it to a place in the chain he sees that a network node accepted it.
4. Blocks added after it further confirm that the network accepted it.

Combining and splitting valueSearch on YouTubeBookmarkSaved

Handling every cent as a separate coin would be unwieldy. To allow value to be split and combined, a transaction contains multiple inputs and outputs.

• Normally there is either a single input from a larger previous transaction, or multiple inputs combining smaller amounts.
• There are at most two outputs: one for the payment, and one returning the change, if any, to the sender.

Fan-out, where a transaction depends on several transactions and those depend on many more, is not a problem. There is never a need to extract a complete standalone copy of a transaction's history.

PrivacySearch on YouTubeBookmarkSaved

The traditional banking model achieves privacy by limiting access to information to the parties involved and the trusted third party. Bitcoin must announce all transactions publicly, so privacy comes from a different place:

• Keep public keys anonymous. The public can see that someone is sending an amount to someone else, but without information linking the transaction to anyone.
• This is like the level of information released by stock exchanges: the time and size of individual trades (the "tape") is public, but not who the parties were.

As an additional firewall, a new key pair should be used for each transaction to keep them from being linked to a common owner.

Some linking is still unavoidable with multi-input transactions: they reveal that their inputs were owned by the same owner. The risk is that if the owner of one key is revealed, linking could reveal other transactions that belonged to the same owner.

Calculations: attacker success probabilitySearch on YouTubeBookmarkSaved

Scenario: an attacker tries to generate an alternate chain faster than the honest chain. Even if he succeeds, he cannot create value out of thin air or take money that never belonged to him. Nodes will not accept an invalid transaction. The attacker can only try to change one of his own transactions to take back money he recently spent.

The race between the honest chain and the attacker chain is a Binomial Random Walk. Success is the honest chain extending by one block (lead +1). Failure is the attacker extending by one block (gap −1). The chance of the attacker catching up from a deficit is like the Gambler's Ruin problem.

Catch-up probabilitySearch on YouTubeBookmarkSaved

• $p$ = probability an honest node finds the next block
• $q$ = probability the attacker finds the next block
• $q_z$ = probability the attacker ever catches up from $z$ blocks behind

How long should the recipient waitSearch on YouTubeBookmarkSaved

The recipient generates a new key pair and gives the public key to the sender shortly before signing. This stops the sender from preparing a chain of blocks ahead of time. Once the transaction is sent, the dishonest sender works in secret on a parallel chain with an alternate version of his transaction.

The recipient waits until the transaction is in a block and $z$ blocks have been linked after it. Assuming honest blocks took the average expected time, the attacker's progress follows a Poisson distribution with expected value:

Multiply the Poisson density for each amount of progress $k$ by the probability he can catch up from there:

Rearranged to avoid summing the infinite tail:

C code from the paperSearch on YouTubeBookmarkSaved

#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
    double p = 1.0 - q;
    double lambda = z * (q / p);
    double sum = 1.0;
    int i, k;
    for (k = 0; k <= z; k++)
    {
        double poisson = exp(-lambda);
        for (i = 1; i <= k; i++)
            poisson *= lambda / i;
        sum -= poisson * (1 - pow(q / p, z - k));
    }
    return sum;
}

ResultsSearch on YouTubeBookmarkSaved

The probability drops exponentially with $z$.

Blocks needed for $P < 0.1\%$:

ConclusionSearch on YouTubeBookmarkSaved

The paper proposes a system for electronic transactions without relying on trust.

• Coins made from digital signatures give strong control of ownership but cannot prevent double spending alone.
• A peer-to-peer network using proof-of-work records a public history of transactions. It quickly becomes computationally impractical for an attacker to change if honest nodes control most CPU power.
• The network is robust in its unstructured simplicity. Nodes work all at once with little coordination. They do not need to be identified, since messages are not routed to any particular place and only need best-effort delivery.
• Nodes can leave and rejoin, accepting the proof-of-work chain as proof of what happened while they were gone.
• They vote with their CPU power: they accept valid blocks by extending them and reject invalid ones by refusing to work on them.

Quick self-testSearch on YouTubeBookmarkSaved