Lecture 4: Leader Election via Proof of Work

Announcements

Homework

  • Homework 1 has been posted on Piazza. It is due on Friday 2/3 on Gradescope.
  • Homework 2 will be posted later this week, and due Friday 2/10.

Office hours

  • Nicolas: Monday 1-3pm in CCDS room 1322
  • Mayank: Thursday 11:30am-1pm in CCDS room 1343
  • Office hours will be in a hybrid format

Review from last lecture

Internet-based money

Our starting point into cryptocurrencies is to build a digital version of a banking system, where people can transfer money to each other electronically over the Internet without the need for a single trusted banking authority.

It should be "secure" against "powerful adversaries."

(We will make more precise today both the security requirements and the kinds of adversaries that we can withstand.)

Alice Mallory Bob
Alice $\longrightarrow$ Mallory $\longrightarrow$ Bob

In the physical world, when Bob receives a check from Alice, he may be suspicious that Alice is trying to deceive him. He needs to be able to verify the following three properties.

  1. Alice properly signed the check

  2. Alice possesses $1 in her bank account

  3. Alice does not double spend the money by writing a check to someone else at the same time

For a digital monetary system:

  • A digital signature scheme (like RSA or ECDSA) can satisfy objective #1 because they are unforgeable.
  • To satisfy the other two objectives, it would help to have a digital ledger that is available to everyone.

19th century ledger

Source: Wikipedia

Imagine for the moment that there was a book where:

  • Anyone can read it at any time.
  • Anyone can append new information to the end of the book.
  • Everyone is assured that the book is append-only. That is, you believe that information can only be written at the end of the book, but nothing can ever be erased or overwritten.

If you had such a ledger, you could use it to:

  1. Record every account and its current balance.
  2. Record every financial transaction between two accounts.

bitcoin transaction

In fact, you don't even need to do both! One can be inferred from the other.

  1. The account model is what we are used to from the traditional banking system. In this approach, the bank maintains a list of every account and its current balance. When a transaction is submitted, the bank updates its record of accounts by debiting the sender and crediting the receiver.

  2. Most cryptocurrencies work in the other direction: they store a public ledger containing every financial transaction ever made. This is called the unspent transaction output model, or UTXO.

[Image source: Nakamoto whitepaper]

(Note: transactions are slightly more complicated than just a digital signature; they can involve more sophisticated computer scripts. We will return to this point in a future lecture.)

4.1 Participants in a Blockchain

The data structure for such a ledger is a blockchain. It is a sequence of blocks, which themselves contain several transactions.

If everyone acts honestly, the intention is that new blocks are only added to the end of the chain.

[Image source: Nakamoto whitepaper]

At a high level, there are three types of participants within Bitcoin.

  • A light client only needs to hold one or more secret keys for a digital signature scheme. (And optionally also a small amount of additional data, which we will discuss next time.)

    We consider the corresponding public key also to be the name of their bank account. These accounts might have money, if (1) someone else has sent money to this account within some transaction in the past and (2) no subsequent transaction has spent the money.

  • A node additionally stores the entire state of the blockchain. (Note: this can be large! The Bitcoin blockchain is currently 451 gigabytes in size.)

  • A miner additionally tries to write new blocks on the blockchain.

    We will explore the role of miners in more detail today.

Bitcoin needs miners: without them, no money transactions can ever be recorded.

So the system incentivizes people to become miners in two ways. If you create or mine a new block, then:

  1. You get to create new coins out of thin air. Specifically, you get 6.25 Bitcoins, which is worth about $140,000 at current exchange rates. (This is the only way that new currency gets introduced into circulation.)

  2. You receive the fees that people set aside for you within their transactions.

If all miners act honestly, then the ecosystem works well: people can conduct money transfers over the Internet, and the miners receive a reward for their efforts.

But what if miners are dishonest? What could go wrong?

4.2 Mining Attacks

Just to state upfront: a bad miner cannot directly create a new transaction to spend your money. Only you can do that, because it requires your secret key.

In more detail, thanks to existential unforgeability under a chosen message attack:

  • If your money hasn't been spent, the miner cannot sign a message to transfer it to themselves.
  • If your money has been spent, the miner cannot sign a new message to transfer it to themselves instead.

Recall that we will consider three categories of security concerns in this course.

  • Confidentiality: keeping data or people's identities hidden from others.
  • Integrity: preventing raw data or the data science results from being altered, or at least allowing for detection of tampering.
  • Availability: ensuring that data science is censorship-resistant.

Bitcoin doesn't provide any confidentiality guarantees: the whole world knows how much money is in each account, and perhaps might be able to link an account to a real-world identity. (More on this later.)

The other two security issues can be impacted by a malicious miner.

Here are 3 types of attacks that a malicious miner could perform. (Note: there are other possible attacks too.)

  • Censorship: The miner can refuse to post certain transactions. This would break our goal of allowing anyone to append new information to the end of the book.
  • Inconsistency: The miner can send different states of the blockchain to different nodes. This would break our goal of having a global ledger that anyone can read.
  • Double spending: The miner could go back in time and rewrite an earlier block. This would break our goal that the ledger is append-only.

[Image source: Bitcoin wiki]

As an example, suppose that Mallory pays Alice and subsequently Alice pays Carol. If a miner deletes the Mallory-to-Alice transaction, then the later transaction becomes invalid as well because Alice no longer has any money to spend.

Even worse, if Mallory is the miner, then Mallory could post a new transaction that pays the money to another account under her own control... perhaps her friend Bob, or perhaps another account held by herself). In this way, Mallory has reclaimed her previously-spent money to spend again in the future.

Thwarting mining attacks

Cryptocurrencies like Bitcoin have been carefully designed to ensure that censorship, inconsistency, and double spending attacks are practically infeasible to perform. (Note: these 3 attacks are actually related, but for the purposes of today's lecture we will treat them separately.)

Before we describe Bitcoin's strategies, let's discuss:

  • How does the traditional banking system prevent these attacks?
  • How would you design a payment system to prevent these attacks?

One possible option is to find a single person who the whole world trusts, and ask that person to be the sole miner in the scheme.

Sadly, we do not have such fully-trusted people. And even if we somehow found such a person, we might ask them to run everything for us, not just the banks. In political terms, this corresponds to a (benevolent?) dictatorship.

To extend the political analogy further, over the centuries humankind has designed democratic social structures in which we:

  • Impose limits on the power of any single actor, even the ones who seek power, and
  • Use elections to decide who gets to have (temporary, limited) power.

These political systems are often less efficient and nimble than a dictatorship might be, but they are more stable as a result.

Cryptocurrencies abide by these principles too! Let's see how.

4.3 Censorship Resistance via Leader Election

Let's see how Bitcoin thwarts these attacks, one at a time. For now, let's just assume that the miners all promise never to conduct a double-spend attack. (We'll fix this trust issue later.)

Bitcoin includes two components to thwart censorship:

  1. There is a connected network of Bitcoin nodes that gossip or broadcast any transaction they hear. This way, any sender can get their transactions heard by any node and miner who happen to be connected to the network right now.

    We will say more about broadcast protocols in future lectures. For now let's assume that this part works perfectly.

  1. There is a randomized election system (or in other words, a lottery) to choose the next miner. It doesn't matter (much) who wins the election; the important part is that the nodes have agreement on who has won.

    The upshot here is: each individual miner can still censor your transaction if they want. Nevertheless, as long as at least one miner is honest, then your transaction will eventually get put into a block.

    This is an example of an anytrust assumption; we will see more examples later in the semester.

The miner inserts their winning lottery ticket -- or more formally, the nonce -- into the block as well. Other miners and nodes will only consider a block to be valid if it includes a winning nonce.

Just like with the earlier political analogy: we have designed a cryptocurrency that is more stable, but at the expense of speed. Whereas you might assume that an Internet-based money scheme would be fast, instead this system is purposely slow. Within Bitcoin,

  • A new miner is elected approximately once every 10 minutes. (More precisely, the time to the next winner is determined by a Poisson random variable.)
  • Each miner can create a block that is about 2 megabytes in size. Each block can hold about 1600-2000 transactions.

In computer science terms: the throughput of this monetary system is low.

4.4 Consistency via Block Heights

This strategy also solves the problem of inconsistency, which was the fear that nodes might see different blockchains.

(Recall that we are assuming for the moment that miners will never go back and try to rewrite history.)

Even with this simplifying assumption in place, one concern is that two miners might win the lottery at (almost) the same time.

If this happens, they will produce blocks that are different -- they have different nonces, and they each pay the mining rewards and fees to themselves.

[Image source: Mango Research]

We can overcome this issue by using the peer-to-peer network to broadcast these blocks as well. Then we can impose a rule that all honest nodes should follow:

Always choose the largest* blockchain. As a tiebreaker, choose the chain that you heard first.

In Bitcoin terminology, each block contains a counter called its block height.

(*Note: we will make one small tweak to this rule in a few minutes.)

[Image source: Mango Research]

Once again, we have resolved an attack at the expense of speed. Let's look at the above picture in the following scenario: block A already exists, and now in th present it happens to be the case that two miners win the lottery at nearly the same time and post blocks B and B2.

Suppose also your transaction occurred in block B but not in block B2.

  • Since a temporary fork has occurred, you cannot yet be sure that the whole network will coalesce around the block containing your transaction.
  • You will need to wait a few minutes to see which block "wins" by being extended first through another randomized election. (That could potentially have its own fork, but it's unlikely that too many of them will occur in a row.)

In computer science terms: the latency of any individual transaction is high.

4.4 Preventing Double Spends via Proof of Work

The final -- and most insidious -- attack that we have to prevent is the double spend.

[Image source: Bitcoin wiki]

We will also solve this problem by intentionally imposing friction into the cryptocurrency. Specifically, we haven't discussed yet how miners win the election and get the right to create a new block.

Assume that there are more honest miners than dishonest miners. Our goal is to choose an election method that is fairly likely to elect an honest miner.

[Image source: Nakamoto whitepaper]

Here's how it works. Every miner collects all of the transactions from the peer-to-peer network, and forms a block. Then:

  1. The miner chooses the nonce value however it wants. (It can choose this at random, or make a counter, or anything it wants.)
  2. It runs a cryptographic hash like SHA-256 over the entire block.
  3. If the resulting hash digest starts with sufficiently many 0 bits, then the miner has won the election and quickly posts the result to the peer-to-peer network. Otherwise, it goes back to step #1 to try again.

Currently, the Bitcoin miners collectively perform about $295 \cdot 10^{18}$ hashes per second.

This corresponds to $177 \cdot 10^{21}$ hashes every 10 minutes. The difficulty level of Bitcoin is currently set to require this many hash computations in expectation, in order to produce a winning nonce.

[Image source: blockchain.info]

That's a lot of work! By means of comparison, your laptop's CPU can probably perform about a billion hashes per second. If you have a nice graphics card, that might be able to perform a few trillion hashes per second.

This effort by the miners is called a proof of work. Only after performing this work can a miner post a block.

The proof of work puzzle relies on the property that a hash function "looks random" even though it is public and deterministic.

If an adversary [Mallory] has not explicitly queried ... on some point $x$, then the value of $H(x)$ is completely random... at least as far as [Mallory] is concerned.

– Jon Katz and Yehuda Lindell, Introduction to Modern Cryptography

So if we ask the miners to find an input whose SHA-256 hash digest begins with several 0 bits, we believe that the miners cannot do anything more intelligent than just a guess-and-check approach.

This property of a hash function is called puzzle friendliness.

(Technically speaking: this property is a stronger requirement than collision resistance, but a weaker requirement than the random oracle assumption.)

Because the computational power in the world goes up over time, the difficulty of the puzzle must adjust over time. If miners start finding blocks faster than the desired 10 minute interval, then difficulty of finding a block increases.

As a result, we need to make a small change to the rule that honest nodes follow:

Always choose the blockchain with the most cumulative difficulty.

In general, this typically corresponds to the blockchain with the tallest height.

Relying on an honest majority

Bitcoin relies on the following assumption:

The majority of the computational power used for mining (at any given time) is controlled by honest miners.

If this assumption holds, then a leader election based on proof of work (eventually) stops double-spending attacks. That's because a dishonest miner cannot keep up with the raw computing power of the honest majority.

(Note that this assumption is weaker than the "anytrust" assumption that we discussed earlier.)

To see why this is the case, let's use the same picture as before, but now assume that:

  • The time in the present is actually after block D has been posted.
  • A dishonest miner wants to revoke a transaction that occurred in the past, in block B.

[Image source: Mango Research]

To do this, the miner will need to post many proofs of work in a row, very quickly. It needs to create $3 + N$ blocks faster than the real world produces $N$ blocks.

This is a Markov chain problem. [Image source: Nakamoto's whitepaper] calculates that even if a dishonest miner controls 10% of all the hash computing power on the blockchain, it will only have about a 1.3% chance of succeeding at this attack.

The attacker can increase its chance of success by buying or renting more computational power. In response, defenders can resist this attack by waiting for more blocks to be confirmed in the public, honest chain.

Suppose there is a transaction that pays you money, but you don't trust the sender and you want to be confident that the money is "safe" and cannot be taken away from you through a double spend attack. You want to be 99.9% confident that your money is safe (i.e., that a double-spend succeeds with only 0.1% probability).

The Nakamoto whitepaper includes the following table that shows how many blocks you need to see mined after your block, as a function of the dishonest miner's computational power.

Adversary's computational power # blocks required
10% 5
15% 8
20% 11
25% 15
30% 24
35% 41
40% 89
45% 340

There are two important takeaways from this table:

  1. The hash power required to execute a double-spend attack quickly becomes onerous enough to be not worth it, for all but the most expensive transactions. Even if the attacker controls even 10% of the Bitcoin network's computing power, executing a double spend attack will likely take more than one hour. By contrast, if the miner uses this hash power honestly to create new blocks, it could have earned (in expectation) tens of thousands of dollars in mining fees.

  2. On the other hand, if the attacker controls the majority of the hash power, then your money is never safe; even transactions made years ago could eventually be double-spent. This is called a 51% attack.

Summary

Let's state that a node considers a block to be finalized if it is at least $k$ blocks deep inside of the longest chain. We'll declare a transaction to be finalized if it is part of a finalized block. (The choice of $k$ here affects the probability of an erroneous decision.)

Overall, this proof of work construction achieves the following objectives.

  1. Liveness: Every transaction is eventually finalized by all honest nodes.
  2. Safety: Honest nodes do not finalize different blocks at the same height.

(Note that we have not yet provided any security guarantees to the light clients.)

In order to achieve these goals, Bitcoin is purposely designed to be:

  • Slow, in that transactions take awhile to become finalized.
  • Bounded, in that only a small number of transactions can be inserted in each block.
  • Computationally intensive, in order to distinguish the honest majority from the dishonest minority.

Over the next few weeks of this course, we will explore alternative ways to satisfy the liveness and safety goals with different tradeoffs.