What Is Bitcoin?

Decentralized digital commodity
Like Second Life L$ or WoW gold, but with no central issuer

Video by www.weusecoins.com, used under CC BY 3.0 License

Watch video.
Commodities are fungible, transferrable, and somewhat scarce.
Digital commodities can be transferred electronically.
Decentralized means no single party controls creation, allocation, or transfer of the commodity. Unlike dollars and WoW gold, there is no Board or company which can decide to create more.

Network

Each user has a local agent, named bitcoind
Agent has a GUI, manages the protocol, and holds your coins.
Agents talk to each other over the internet.

Sending

Users send payments to each other by giving address and value to agent
Addresses are cryptographic identifer of a public key, like 1K2CcfWYW5sBL2xSeQWXpcmjPCgoXdi36R
Agent sends signed messages to other agents, transferring coins.
Receiving user's agent informs them upon receipt of payment.

Goals of Decentralization

Security depends upon math, not people
No single party controls the money supply
Failure of a single company doesn't impact currency
Survive changes in use-case, behaviors of users
Avoid the perils of centralization:
- Single Point of Failure
- Power Corrupts

What's wrong with a centralized currency?
From a security point of view, we'd like the usual properties (like unforgeability, theft-proof) to be enforced by code and math, rather than depending upon the goodwill of people
From an economic point of view, some folks would like the total money supply to be predictable, as opposed to allowing a central bank to cause inflation by creating new money whenever they like.
Putting a lot of power in one place is an invitation to abuse. Spreading that power out among multiple users can fix that.
The most important thing a currency can do is to inspire confidence among its users. Bitcoin is testing a theory that more users will be willing to adopt a decentralized currency than one in which they have to trust a single person, company, or government.

Specifications: Transfer+Create

To specify a new money system, we need to describe how it is represented, how it gets transferred between parties, and how it's created in the first place.
Scarcity is one of the important properties, but there must be more than zero of it, so we must explain how it's created, and at what rate the money supply expands.
Expansion is a policy decision: it helps whoever gets the new money, it hurts everyone else a little bit, it's necessary (at least initially). So it must be managed.

Discrete-Coin Vs. Ledger

Digital money systems have traditionally fallen into roughly one of two categories
Discrete Coin: bank issues lots of coins for a few denominations, blinded, can recognize valid coins later
Ledger: bank tracks balance for each user, increments/decrements with each transfer

Evolving the Ledger into Bitcoin

one small step at a time

Despite having "coin" in the name, Bitcoin is more like a ledger system.
I'm going to explain how Bitcoin works by starting with a simple ledger system and making small incremental changes until we wind up with the actual Bitcoin protocol.

MMORPG Bucks

Imagine you're a programmer, tasked with creating the money system for the latest online game.
You'd start with a database, since everyone loves SQL. Each user would get an account, with a balance. The system must handle transactions that transfer money between accounts, create money (perhaps by buying it with dollars, or by raiding a dungeon), and destroy money (selling it for dollars, or buying a Vorpal Sword)
Your system maintains some invariants, like how transfers cannot create new money, and no account balance can go below zero.

MMORPG Authority

Users get access to facets with control over just their account
Bank controls creation of currency

From an authority-analysis point of view, each user gets control over a facet which allows them to send credits to someone else. Bank gets the authority to create new money.

What's Wrong With the Ledger

Bank can spend any user's money
- creates strong temptation for attackers
Bank can create new money without notice
- unpredictable inflation
Users cannot verify payments without bank
Bank is a SPoF

What's wrong with the ledger system? Specifically, what centralization are we trying to fix?
Since the bank has full control over the ledger, the bank (or an attacker who compromises it) can spend any user's money.
The bank can also create new money any time it likes, which makes it hard to predict inflation.
And since the only source of truth is in the bank's ledger, users cannot validate payments or even learn their current balance without talking to the bank. It is a fully online system, and bank downtime prevents anyone from using their money.
We're kind of used to these restrictions, but we can do better.

Accounts are Pubkeys

Ledger is Public

~~bank can spend money~~
bank can create money
~~need bank to verify payments~~
bank is SPOF
bank controls history

Replace accounts with pubkeys: each column of the ledger is associated with a specific public verifying key
now Alice authorizes a transfer to Bob with a signed message
bank publishes both the transfer messages and the ledger publically
everyone can verify the signature on each transfer message
everyone can audit the ledger and complain about violations
bank's job is to sequence transfers, reject underflows, publish log, manage expansion
at the same time, let's drop the ability to remove money from the system: total is monotonically increasing

Multiple Pseudonymous Pubkeys

~~bank can spend money~~
bank can create money
~~need bank to verify payments~~
bank is SPOF
bank controls history

Next, allow each user to have multiple keys, created on demand. Bitcoin user agents routinely manage hundreds of keys. These are small ECDSA keys, so the effort involved is trivial.
Carol's current balance equals the sum of all her keys
Balances can be split into different keys, or merged together.
Pubkeys are pseudonyms: nobody needs to know A is for Alice
This starts to help with anonymity: less obvious that A1 and A2 are related.

Transaction Log, not Balance Log

bank controls history
bank can create money

Having the bank publish both the transfer messages and the resulting balance sheet is redundant. So we'll make it only publish the transfers. We'll call them transactions.
Everyone will derive balances when necessary
Bank's job is to remember correct order of transactions, only permit valid ones, and manage expansion.
Rest of the world can validate signatures and transactions, prevent underflow, and determine balances.

Transaction Pipe

our network model has users who are sending signed transfer messages to the bank. The bank does some checking, establishes the ordering, then broadcasts the message stream to all users (including the original sender).
the bank also decides to give new money to certain people whenever it wants: we still don't have control over expansion.

Transactions

≥0 inputs, signature for each
≥1 outputs, recipient pubkey for each

Next, we enhance our transaction model.
Each transaction consumes some inputs, creates some outputs
each input points to some previous output
these outputs are first-order objects: we're not transferring credits from one column to another, we're consuming some outputs and creating new ones for different keys
The rule is: total outputs can't be larger than total inputs
Each output is "sent" to a pubkey: it's labeled with the pubkey that must be used to claim it
txn must be signed by keys for all inputs
produces DAG of txns, and set of unspent outputs
The transaction graph evolves over time

Evolution Of Transaction Graph

Let's look at a growing transaction graph, already in progress.
At any given time, there are a set of unspent outputs, each with a value denominated in BTC
I'm eliding the previous history to keep this simple: pretend there's a bunch of transactions above this line which results in just these three outputs.

Transaction Graph 1/6

Each transaction consumes some of those outputs, and produces new ones. The transaction must be signed by the key which owned the input. The outputs are labeled with the pubkey that will be needed to consume it.
This transaction transfers 12 credits from key B2 to key C1.
The old output is marked as being spent, and removed from the set of unspent outputs.

Transaction Graph 4/6

Since outputs must be consumed completely, to send less than the full amount, the "change" has to go back to the sender.
In this example, Alice is sending 10 credits to Bob. Since she only has one unspent output, and it's too big (20BTC), her client makes a transaction that splits it into two pieces, returning the remainder to her in a new key.
Most Bitcoin transactions create two outputs: the first transfers credit to the recipient, and the second sends the remainder back to a new key owned by the original sender.

Transaction Graph 5/6

There can be multiple unspent outputs for a given key. Each transaction references specific outputs, not just keys.
A user's balance is the sum of the values of all unspent outputs for all keys they control.
Transactions can create an arbitrary number of outputs..

Transaction Graph 6/6

..and consume an arbitrary number of inputs, either for consolidation, or to make a large payment by combining several smaller ones.
At each stage, the transaction log contains a set of unspent outputs. This set grows and shrinks over time.

Properties So Far

Needs: append-only ordered transaction log
Prevents: double-spends, underflow
Users submit signed transactions, bank publishes log
Recipients check log before delivering goods. Once in the log, double-spends will be rejected.
Bank still controls expansion, could publish different logs at different times or to different people

So, how far does this get us?
We rely upon the bank to provide all users with an append-only ordered transaction log. We need it to be ordered so we can resolve double-spends (define which one came first).
If everyone sees the same log, then double-spends and other validation failures are prevented.
The bank could still publish different logs to different people, so our next step is to decentralize the transaction log and remove our reliance on the central bank

Serialized Transactions

Now we need to decentralize this transaction log
First we need to be concrete about the transaction format.
Each transaction is serialized to a string and hashed to get a txnid. Txns reference each other by txnid and output number.
This forms a DAG of transactions.
Our goal is to have all users agree on the current txn graph. In particular, disagreements about which outputs have been consumed would allow double-spends.

Blocks

Aggregate txns into blocks. Every 10 minutes, take all the current valid transactions and bundle their serialized forms together into a block.
The rule is that each block may only contain valid transactions that reference an output in some previous block.
Each block is like a page of the ledger book.
You can imagine loose transactions like individual post-it notes with the transaction details, and every once in a while you paste them all into a new page of the book.

The Block Chain

Each block is just a bunch of serialized transactions and a header. Again, we can serialize it to a string and hash it to get a blockid.
The header includes a copy of the previous block's id. Since these are cryptographic hashes, this forms the blocks into a strong chain.
Now if we can agree on the current block ID, we also agree on the full contents of the transaction log. It's computationally impossible to insert or remove a previous transaction, since that would change the hash
This mostly reduces the agreement problem down to agreeing on a single blockid.

Getting Closer

Broadcast channel of loose transactions and bound blocks
All nodes subscribe, validate transactions and blocks, maintain copy of block chain
All txns in the chain are valid and mutually consistent.
Still unspecified: how to agree upon current block, how to keep broadcast in sync, how to control expansion

So what do we have now: ..

Alternate History

Double-spend attack requires multiple views

So why do we need to agree on the current block?
To double his spending power, the attacker needs each recipient to see a different block chain: the conflicting transactions each appear in only one chain. Nobody (including Alice and Bob) would accept both transactions in the same chain.
The attacker needs to take delivery of whatever they're buying before the victim learns about the other history chain.
So we need some means of decide which chain is "correct", which both Alice and Bob can use to converge on a single history.
To agree on which block is current, imagine a voting protocol
Everybody performs the same computation, they accept each others results if they match.

Mining and Proof-Of-Work

Each block contains a large counter
BlockID must be close to zero
Hard to find (DF*2³² hashes), trivial to verify
Current Difficulty Factor is 19.3M (Jun-2013), requires 83¹⁵ hashes

Here's where it gets clever.
Each block header also contains a large counter, included in the hash.
We require the Block ID (hash of data) must be close to zero: a partial hash collision. Trivial to verify, requires predictable amount of work to generate.
Difficulty Factor controls how close it must be, which controls how much work is needed (on average) to find a block.
83 petahashes takes (thousands of GPUs/FPGAs/ASICs) an average of 10 minutes.
This process is called "mining": keep trying, maybe you get lucky.

Most Difficult Chain Wins

Rule Of Mining: accept the valid block chain with the most cumulative work.
Once accepted, miners work to extend that chain with another block.

Miners accept the valid block chain with the most work.
That means every transaction is valid, there are no double-spends, all the rules of the economy are being followed.
Bitcoin miners spend all day long incrementing counters and computing hashes, trying to find that partial collision, trying to extend the longest chain by one more block
The current block chain is about 243k blocks long, and contains nearly 1.5 zettahashes (10^21) of work.

Resolving Races 2/8

A race happens when two miners find a block at the same time, or at least outside of each others light cones: they find a block before hearing about the other's discovery
Since block discovery is a Poisson process parameterized by the number of hashes-per-second being generated, the chances of an accidental race are fairly low, and linear in the diameter of the network.

Resolving Races 5/8

Eventually, somebody will find the next block. The larger clique has a better chance, but it doesn't actually matter. The chances of hitting simultaneous discovery twice in a row are very low.
They broadcast their block to the network.

Double-Spending

A solitary attacker attempting to create an alternate chain faces an uphill battle.

Remember that to pull off a double-spend attack, the attacker needs to present multiple distinct valid block chain to his different victims.
This becomes impossibly hard when the majority of miners are working on the same chain.

Incentives For Mining

Why would anyone mine? It requires hardware and electricity.
Currency Expansion: how is BTC created in the first place?
Maybe these two are related..

So to maintain the integrity of the transaction log, we need lots of people to mine. But that costs real-world electricity. So we need to give them something as an incentive.
Also, we still haven't explained how to create BTC in the first place, and how to choose some fair way to distribute it.
(a side note: distribution doesn't need to be fair, by the Coase Theorem, but few people will use a system that feels unfair)
Since the only thing we have to offer is BTC, let's pay miners with bitcoins.

Block Reward

Valid blocks are allowed a single "coinbase" transaction: zero inputs, one output, 25 BTC
This is a "reward" for finding the block.

Bitcoin's rules state that each block is allowed to have one "coinbase" transaction: zero inputs, one output, for a specific quantity of BTC.
This is a "reward" for finding the block, currently 25BTC per block.
In exchange for doing f(DF) hashes, miners get (on average) 25BTC.
Rational participants compare expected future value of those BTC against costs and mine, or don't.

Ignore == Punish

Rules of the economy (valid transactions, etc) are enforced by miners
Miners don't want to build upon invalid blocks (those with invalid transactions)
.. because then other miners wouldn't build on their work
.. thus invalidating their reward
Game theory: payoff is better when you cooperate

So miners are incentivized to enforce the rules of the economy. Their reward is contingent upon other miners agreeing with their decisions. If they do it wrong, other miners will ignore their blocks, so the reward transaction won't be in the block chain that everyone else recognizes, so they won't be able to spend it in the future.
That means they're going to be very careful about the transactions they put in their blocks, and following the rules themselves: any violations will cost them the reward (and means they've wasted a lot of work)
Miners are effectively betting their CPU cycles that other miners will accept their decisions, and receiving BTC as a payoff. They maximize their chances by following the rules.
There's a lot of game theory going on here. Trying to break the rules will get you ignored. Following the same rules as everyone else will help you get blocks in the chain that everyone else follows.

Mine? Or Attack?

Attacker with <50% of total hashing power makes more BTC by mining honestly.
Cabal with >50% can cause double-spend
- but easy to detect: conflicting txns in alternate chains
- and members have local incentives to mine normally, so cabal may be unstable
- defectors will leave and become honest

Clever incentive alignment here. Do integrity-protection work, get paid in BTC.
Do it wrong (either accidentally or trying to cheat), and you've wasted CPU cycles.
Potential attackers are incentivized to follow the rules too.
A rational attacker deciding whether to spend their CPU time trying to build an alternate chain, or mining normally, will probably get a better average return by cooperating.

Coin Maturity

Attackers would need to out-pace the rest of network to produce alternate history
Transactions become more resistant to double-spending over time
Recipients can wait longer to reduce chances of rollback

The block chain causes an interesting side-effect that's fairly unique. Bitcoin transactions have a "maturity" that improves with age, like wine, cheese, and teenagers
Since the attacker's task of producing a longer block-chain with their alternate history gets linearly harder as more blocks are added to the real chain, the recipient can choose between attack resistance and settlement time.
if someone buys a sandwich from me, I could give it to them quickly
if they buy a car from me, I'm going to wait an hour or two for chain to grow, just like waiting for a check to clear

BTC Expansion Curve

Initial reward of 50BTC per block drops in half every four years (210000 blocks)
Total amount of BTC asymptotically approaches 21M over time.
Interesting from an economic/money-supply POV: fixed, predictable expansion, eventually 0%. This removes one variable that drives inflation.
Raises the question: what incentives do miners have when the reward goes away?

Transaction Fees

"fee": SUM(inputs) - SUM(outputs) > 0
Miner adds fees to their reward
Clients give fee for faster service

Transaction rules said that the outputs can't be *greater* than the inputs. It doesn't actually require them to be equal.
A txn is said to pay a fee when the outputs sum to *less* than the inputs
leftover goes to miner who finds the block
specifically: the rules say it's valid to have a reward transaction which includes the sum of the fees
in the long run, clients will need to provide a fee to get their txns published
choose tradeoff between small fee and quick service
market should stabilize upon an average fee that covers miner's expenses plus reasonable profit

Results

Consensus-based rule enforcement

impossible to steal
expensive to double-spend or create extra

New BTC allocated proportionally to work performed
Expansion of BTC supply pre-determined
No single party can change the rules

So that's the basics of bitcoin.
clients broadcast signed transactions
miners collect valid transactions into blocks, perform proof-of-work hashing on blocks to obtain BTC rewards.
the PoW on the block chain makes it expensive to create lengthy alternate history, so double-spends are not economical
What properties do we get from this?

Auto-Adjusting DF

More users == more hashing == faster block generation

but DF adjusts to maintain 10 minutes per block

Won't DF rise to infinity?

miners will stop when it becomes unprofitable
DF falls, becomes profitable again
equilibrium established

bitcoin.sipa.be

There are a lot of clever tricks lurking in the code.. here are some highlights.
valid-block-rule adjusts DF upon how quickly blocks are found, every 2016 blocks (2weeks), to bring back to 1/10min
In particular, miners only accept blocks that meet their current expectation of the DF, which is reset every 2016 blocks according to the timestamps inside the blocks.
There's an NTP-like protocol to deal with inaccurate local clocks.
DF/mining marker: eventually, an equilibrium will be established, between how efficiently miners can operate and how much reward they expect to receive. More miners, faster/cheaper hardware, software improvements, all get factored into the equilibrium point.

Practical Deployment Details

Mining: GPUs and FPGAs are now being replaced by ASICs
Mining pools provide more uniform returns
Mining Yield Calculator
Exchanges $ <-> BTC: mtgox.com
Network Monitoring Tools:
- bitcoinwatch.com
- blockexplorer.com

GPUs are about 10x more efficient than CPUs, in hashes-per-joule
FPGA 10x GPU, ASIC 5x-30x FPGA
current ASICs only yield about one block per month, GPUs one per year. Pools make the return more uniform.
4 largest pools provide about 75% of total hash power.
The largest exchange moves about $1M/day.
Paste 1K2CcfWYW5sBL2xSeQWXpcmjPCgoXdi36R into the blockexplorer to see a sample transaction.

Numbers

About 11.3M BTC in existence
1900 transactions per hour
Current DF: 19.3M
Network hashrate: 147TH/s (=6k FPGAs, 7.4MW)
Block chain is 243k blocks long
Cumulative work ~1.5e21 hashes
mtgox price is about $107/BTC

DF rises with popularity and technology steps
high-end FPGA is 25GHps, 1.3kW. If the whole network were made of this, we'd need 5800 of them, consuming 7.4MW (a bit more than the output of a diesel train, or half a millionth of worldwide energy usage (12852Mtoe, toe=41.868GJ, 17TW).
Block chain represents 1.5 zettahashes

Implementation Details

Client: C++, uses Boost, BerkeleyDB, wxWindows for GUI
IRC for address distribution, overlay network, log-structured flood
wallet.dat holds private keys
ECDSA in secp256k1, SHA256

Is it money?

it has similar properties
it can be used in similar ways
what is money, exactly?

Is It Anonymous?

Transaction contents are very public
Transaction source (IP addr) is mostly secret
Key ownership is secret, unless revealed by sender or recipient
Surprisingly similar to cash (serial numbers)

all transactions are public, but the relationship between keys and people is not always easy to determine
txns are flooded, so IP address is not too useful. Client could run over Tor.
if ATMs recorded serial numbers on bills emitted, and merchants recorded serial numbers and customer names, cash would be traceable too. They don't, so cash is generally anonymous.
paste this address into the block explorer to see a transaction in detail: 1K2CcfWYW5sBL2xSeQWXpcmjPCgoXdi36R

Long-Term Concerns

Scaling
- storage of block chain
- storage of unspent transactions
- transfer of txn/block stream
environmental impact of power use by mining
DoS attacks: on miners, pools, exchanges
price stability, legal attacks
secure key management, usability

Not-Really-Concerns

botnets: feels unfair, but contributes to stability
51% botnets: unlikely
small clients: can delegate block-chain checks fairly safely

There are some botnets, but as FPGA/ASICs take over, they become less interesting.
risky to operate: hot CPUs aren't stealthy

Thanks!

http://people.mozilla.com/~bwarner/bitcoin/

Bonus Features: Scripts

Transactions actually contain script pairs
written in non-Turing-complete stack-based language
input script ("signature") executed, leaves data on stack
then output script ("pubkey") runs, evaluates data, approve/reject
enables neat stuff: multiple signatures, threshold sigs, smart contracts

Scaling Through Specialization

Some scaling concerns can be resolved with specialized clients

regular users don't need to mine
.. or even know the entire block chain

Small clients: hold private keys, rely on others for txn info

BitcoinJS project has libraries

Banks: they hold everything, do all the work

Bitcoin: A Technical Introduction

What Is Bitcoin?

Network

Sending

Goals of Decentralization

Specifications: Transfer+Create

Discrete-Coin Vs. Ledger

Evolving the Ledger into Bitcoin

MMORPG Bucks

MMORPG Authority

What's Wrong With the Ledger

Centralized Ledger

Accounts are Pubkeys

Ledger is Public

Multiple Pseudonymous Pubkeys

Transaction Log, not Balance Log

Transaction Pipe

Transactions

Evolution Of Transaction Graph

Transaction Graph 1/6

Transaction Graph 2/6

Transaction Graph 3/6

Transaction Graph 4/6

Transaction Graph 5/6

Transaction Graph 6/6

Properties So Far

Serialized Transactions

Blocks

The Block Chain

Getting Closer

Alternate History

Mining and Proof-Of-Work

Most Difficult Chain Wins

Resolving Races 1/8

Resolving Races 2/8

Resolving Races 3/8

Resolving Races 4/8

Resolving Races 5/8

Resolving Races 6/8

Resolving Races 7/8

Resolving Races 8/8

Double-Spending

Incentives For Mining

Block Reward

Ignore == Punish

Mine? Or Attack?

Coin Maturity

BTC Expansion Curve

Transaction Fees

Results

Auto-Adjusting DF

Other Problems/Solutions

Practical Deployment Details

Numbers

Implementation Details

Is it money?

Is It Anonymous?

Long-Term Concerns

Not-Really-Concerns

Thanks!

Bonus Features: Scripts

Scaling Through Specialization