Lecture 2.1: Centralization vs Decentralization

Decentralization is not all-or-nothing

Email: decentralized protocol, but dominated by centralized webmail services.

Aspects of decentralization in Bitcoin

1. Who maintains the ledger?
2. Who has authority over which transactions are valid?
3. Who creates new bitcoins?
4. Who determines how the rules of the system change?
5. How do bitcoins acquire exchange value?

Beyond the protocol, we have exchanges, wallet software, service providers, etc.

• Peer-to-peer network

  • Open to anyone, low barrier to entry

• Mining

  • open to anyone, but inevitable concentration of power
  • often seen as undesirable

• Updates to software

  • Core developers trusted by community, have great power

Lecture 2.2: Distributed Consensus

Bitcoin's key challenge

Key technical challenge of decentralized e-cash: distributed consensus

or: how to decentralize ScroogeCoin?

Why consensus protocol?

Traditional motivation: reliability in distributed systems

Distributed key-value store enables various applications: DNS, public key directory, stock trades, etc. These are good targets for Altcoins!

Defining distributed consensus

• The protocol terminates and all correct nodes decide on the same value.
• This value must have been proposed by some correct node.

Bitcoin is a peer-to-peer system

• When Alice wants to pay Bob, she broadcasts the transaction to all Bitcoin nodes.
• Bob's computer is not in the picture.
• Bob could run a node to listen on the transactions being broadcast, but his listening is not necessary for him to recieve the funds.

How consensus could work in Bitcoin

At any given time:

• All nodes have a sequence of blocks of transactions they've reached consensus on
• Each node has a set of outstanding transactions it's heard about

Why consensus is hard

• Nodes may crash
• Nodes may be malicious
• Network is imperfect
  • Not all pairs of nodes connected
  • Faults in network
  • Latency: no notion of global time

Many impossibility results

• Byzantine generals problem
• Fischer-Lynch-Paterson (deterministic nodes): consensus impossible even with a single faulty node.

Some well-known protocols

Example: Paxos

• Never produces inconsistent result, but can (rarely) get stuck.

Understanding impossibility results

These results say more about the model than about the proble.

The models were developed to study systems like distributed databases.

Bitcoin consensus: theory and practice

• Bitcoin consensus works better in practice than in theory
• Theory is still catching up
• BUT theory is important, can help predict unforeseen attacks

Some things Bitcoin does differently

• Introduces incentives

  • Possible only because it's a currency!

• Embraces randomess

  • Does away with the notion of a specific end-point
  • Consensus happens over long time scales - about 1 hour

Lecture 2.3: Consensus without identity: the block chain

Why identity?

• Pragmatic: some protocols need node IDs
• Security: assume less than 50% malicious

Why don't Bitcoin nodes have identities?

• Identity is hard in P2P system - Sybil attack
• The Sybil attack in computer security is an attack wherein a reputation system is subverted by forging identities in peer-to-peer networks.
• Pseudonymity is a goal of Bitcoin

Weaker assumption: select random node

Analogy: lottery or raffle

When tracking and verifying identities is hard, we give prople tokens, tickets, etc.

Now we can pick a random ID and select that node.

Key idea: implicit consensus

• In each round, random node is picked
• This node proposes the next block in the chain
• Other nodes implicitly accept/reject this block
  • by either extending it
  • or ignoring it and extending chain from earlier block
• Every block contains hash of the block it extends

Consensus algorithm (simplified)

1. New transactions are broadcast to all nodes
2. Each node collects new transactions into a block
3. In each round a random node gets to broadcast its block
4. Other nodes accept the block only if all transactions in it are valid (unspent, valid signatures)
5. Nodes express their acceptance of the block by including its hash in the next block they create.

What can a malicious node do?

• Steal bitcoins of another address that it doesn't control

  • Not possible because digital signatures cannot be forged

• Deny service to a particular user by not including any transaction from the user in the block proposed by the node

  • Valid attack, but it's nothing more than a little annoyance. The user just has to wait for an honest node gets the chance to propose a block.

• Double-spending attack

Honest nodes will extend the longest valid branch.

Recap

• Protection against invalid transactions is cryptographic, but enforeced by consensus.
• Protection against double-spending is purely by consensus
• You're never 100% sure a transaction is in consensus branch. Guarantee is probailistic.

Lecture 2.4: Incentives and proof of work

Assumption of honesty is problematic

Can we give nodes incentives for behaving honestly?

Note: Penalizing is problematic because there is no identity system, so there is no way to go after dishonest actors and penalize them.

Everything so far is just a distributed consensus protocol. But now we utilize the fact that the currency has value.

Incentive 1: block reward

• Creator of block gets to
  • include special coin-creation transaction in the block
  • choose recipient address of this transaction
• Value is fixed: currently 25 BTC, halves every 4 years.
• Block creator gets to "collect" the reward only if the block ends up on long-term consensus branch!

There is a finite supply of bitcoins

Incentive 1: transaction fees

• Creator of transaction can choose to make output value less than input value
• Remainder is a transaction fee and goes to block creator
• Purely voluntary, like a tip

Remaining problems

1. How to pick a random node?
2. How to avoid a free-for-all due to rewards?
   • Everyone will start running nodes and will claim free bitcoins
3. How to prevent Sybil attacks?

Proof of work

To approximate selecting a random node:

• select nodes in proportion to a resource that no one can monopolize (we hope)
• In proportion to computing power: proof-of-work
• In proportion to ownership: proof-of-stake

Equivalent views of proof of work

1. Select nodes in proportion to computing power
2. Let nodes compete for right to create block
3. Make it moderately hard to create new identities

Hash puzzles

PoW property 1: difficult to compute

• As of Aug 2014: about $10^{20}$ hashes/block
• Only some nodes bother to compete - miners

PoW property 2: parameterizable cost

• Nodes automatically re-calculate the target every two weeks
• Goal: average time between blocks = 10 minutes
• Probability (miner wins next block) = fraction of global hash power controlled by the miner

Key security assumption

Attacks infeasible if majority of miners weighted by hash power follow the protocol.

Solving hash puzzles is probabilistic

PoW property 3: trivial to verify

• Nonce must be published as part of the block
• Other miners simply verify that

    H(nonce | prev_hash | tx | ... | tx) < target

Lecture 2.5: Putting it all together

Mining economics

Complications

• Fixed vs variable costs
• Reward depends on global hash rate
• Cost incurred in terms of dollars, but rewards are in bitcoins

Bitcoin has three types of consensus

• Value
• State
• Rules

Bitcoin is bootstrapped

What can a "51% attacker" do?

• Steal coins from existing address?

  • No, because you need to subvert the cryptography by forging digital signatures.
  • A 51% attacker could probably create the longest chain, but other honest actors can easily see that the signatures do not match.

• Supress some transactions?

  • From the blockchain => possible
  • From the P2P network => not possible; transactions still find a way to reach the other (honest) nodes

• Change the block reward?

  • No, because attacker doesn't control the copies of Bitcoin software run by honest nodes.

• Destroy confidence in Bitcoin?

  • It can very well materialize. Even an unsuccessful 51% attack can damage bitcoin.