Lecture 11: From Broadcast to Blockchains

In the Byzantine Broadcast problem:

• The commanding general, called the leader, is trying to send a message to attack or to retreat (or 0 or 1, or any other binary choice).
• The remaining generals, called parties or nodes, want to reach agreement on the strategy.

There are a total of \(n\) parties, including the leader.

Our goal is to design a protocol – that is, a method that each party can use to decide what messages to send and to whom – that protects the honest parties as follows.

• Termination: All honest parties eventually complete the protocol and output something (i.e., the protocol doesn’t go on forever).
• Validity: If the sender is honest and sends the bit \(b\), then all honest parties should output \(b\)
• Consistency: If two honest parties output \(b\) and \(b'\) respectively, then \(b = b'\).

So far, we have two protocols that provide Byzantine Broadcast in the synchronous setting: the Dolev-Strong protocol and the phase-king protocol.

Here’s a high-level description of how the phase-king protocol works:

• There are \(f+1\) different phases. In each phase, parties \(P_1, P_2, \ldots, P_{f+1}\) each take a turn being the “king.” (The first party \(P_1\) is the initial sender, and it doesn’t matter which other parties get to be the king as long as everyone agrees which party is #2, #3, and so on.)
• In each phase: the king sends a message to everyone. Then all parties use the Gradecast protocol to check whether they have reached consensus about the value.
• If a party ever receives a value with a grade of 2 (full confidence), then they become “stubborn” and keep this value forever. Otherwise, they remain open-minded to any value sent by the next king.

Both of these protocols achieve our security guarantees of termination, consistency, and validity. But they are admittedly slow to reach consensus.

Can we do better?

Theorem. [Dolev-Strong] No deterministic protocol (even with a PKI) can achieve Byzantine Broadcast in fewer than \(f + 1\) rounds.

We’re not going to prove this theorem formally. But why do you think it might be true?

This issue is easier to see in the phase-king protocol, where each party in turn acts as a “king” for a phase of 3 rounds.

• In the worst case, it could be the case that our adversary has corrupted the first \(f\) parties. As a result, we cannot be sure that we have learned anything until there is a phase that is led by an honest party.

• Even more nefariously: our adversary might wait until we decide upon an ordering of the parties, and then adaptively corrupt the first \(f\) parties in the ordered list.

The Dolev-Strong protocol has a similar issue, even though it does not follow the style of electing one leader per phase. And it turns out that every deterministic protocol suffers from the same fate.

But what if we consider a protocol that makes random choices? Can we do better? How could we even take advantage of randomness to foil the adversary?

In the physical world, a coin is a powerful object that provides some nice guarantees.

• Common view. Once the coin is flipped, everyone can agree on the result.
• Unpredictability. No coalition of \(f < n\) parties know what the result of the coin will be in advance.
• Unbiasedness. No coalition of \(f < n\) parties can influence the outcome of the coin. That is, they cannot bias the result away from a 50-50 chance of heads vs tails.

These properties are very cool! It would be great if we can build such a CommonCoin in the digital world.

If we could do this, it would solve many challenges involving agreement.

For instance: suppose you and your friends are talking on the telephone and trying to decide where to eat dinner. Each of you prefers a different restaurant, and you want to pick fairly between them. A CommonCoin protocol would let you “toss a coin” over the phone.

There is some good news and some bad news here.

We will discuss how to build a CommonCoin protocol next week. For now, let’s just assume that it exists. What can we do with a CommonCoin, beyond choosing a restaurant for dinner?

Recall that the phase-king protocol has the following structure.

• It proceeds in \(f+1\) phases, each of which contain 3 rounds.
• In each phase, one party is nominated as a “king” (or leader) and gets to broadcast a value \(b\). The parties adopt this value, unless they are already happy with a value sent in a previous phase (based on the Gradecast protocol).

This protocol satisfies:

• Validity because the designated sender gets to be the first king, and if they are honest then everyone will agree upon their value.
• Agreement because after \(f+1\) rounds it is guaranteed that there is an honest party.

Question. How can we improve upon this protocol using randomness?

Here is one option:

• The leader gets to act as the king in the first phase, as usual.
• In between phases, run the CommonCoin protocol to toss many coins, and use the sequence of heads/tails to elect a new king
• Then run an iteration of the normal phase-king protocol. The randomly-elected king gets to broadcast a value, and parties will adopt it unless they were already happy in a previous phase.

Question. How many phases of this protocol do we need to run, in order to be convinced that there has been one phase led by an honest party with overwhelming probability?

Let’s consider this question in the setting where \(f = \frac{n}{3} - 1\). That is, there are approximately \(2/3\) honest parties and \(1/3\) malicious parties.

This is a powerful observation!

For example: if we want to ensure that we reach agreement with \(n = 3\) million parties, then we have two options.

• To be 100% certain of reaching agreement, we must run phase-king for about \(\frac{n}{3} = 1\) million phases.
• To be 99.9999999999% certain of reaching agreement (i.e., up to 1 in a trillion error), we must run 26 phases.

Question. How are these problems related?

There are some similarities between the problems:

• Both broadcast and blockchains involve the dissemination of data.
• Both have some notion of consistency: the idea that all parties (eventually) know the data, and they know that everyone else (who is honest) knows the data too.
• Both protocols are built on top of a network with point-to-point connections; that is, it allows any party to send data to each other party.

But also, there are at least four differences between broadcast and blockchains.

One-shot vs long-running

• A Byzantine Broadcast is a one-shot protocol: the sender has data, the parties talk for some number of rounds/steps, and then it terminates.
• By contrast, a blockchain can add new content forever. Our goal is to guarantee that each atomic unit of data, which we call a transaction, is eventually known by everyone.

Computational power

• Byzantine Broadcast protocols do not require that much computational power. The most computationally intensive operation that some of them perform is a digital signature, but that can be done in less than 1 millisecond on a laptop.
• The Bitcoin protocol relies upon a proof of work puzzle to achieve eventual agreement. This puzzle consumes a lot of electricity in order to calculate about \(5.6 \cdot 10^{20}\) SHA-256 hash operations every second.

Time to finalize a transaction

• A Byzantine Broadcast protocol requires many rounds to reach consensus: \(f+1\) rounds for a 100% guarantee, or around 25 to 75 rounds for a probabilitic guarantee.
• Within the Bitcoin blockchain, most people consider a block to be finalized (probabilistically) after about 6 or so blocks have been created afterward.

Assumptions about the network

• A broadcast protocol might assume that the underlying network is synchronous (e.g., Dolev-Strong or phase-king), or it may be flexible enough to operate over an asynchronous network (which we will see next week).
• The Bitcoin protocol works even if the underlying network is asynchronous.

That said, there is nothing that stops us from designing a blockchain that relies upon the assumption of a synchronous network. Let’s do that now.

A blockchain has three types of data:

• A transaction is a single value. It could be a bit like 0 or 1, or a multi-bit message like “Alice pays Bob 1 coin, signed Alice.”
• A block is an unordered set of several messages, typically ones that are sent around the same time.
• A log is an ordered list of blocks. This chain is intended to be an append-only log; it only grows at the end, and never shrinks or changes in the middle.

Definition. Let’s define a blockchain protocol in the synchronous setting as any interactive protocol that distributes a log. It must satisfy the following two properties:

For now, let’s limit consider the easiest options of all design parameters:

Question. How might we do this?

Here is one way to build a blockchain, starting from any \(R\)-round Byzantine Broadcast protocol. We will say that the protocol proceeds in several “epochs,” each of which last for \(R\) rounds.

Epoch 1 (containing \(R\) rounds):

• Party 1 is chosen as the leader. This party collects any transactions that it has heard, and forms a block.
• All parties execute an \(R\)-round Byzantine Broadcast, with Party 1 as the designated sender.
• At the end of this epoch of \(R\) rounds: all honest parties have agreed upon some block, and furthermore if Party 1 is honest then the agreed-upon block will be the one that Party 1 chose. Honest parties add this block to their log.

Now repeat this cycle forever:

• In epoch 2 we elect Party 2 as the designated sender of an \(R\)-round Byzantine Broadcast protocol to add a block of their choice to the chain. In epoch 3 we elect Party 3 as the designated sender to propose a block to add, and so on.
• In epoch \(n+1\) we go back to the beginning and elect Party 1 as the designated sender. And so on.

Impressively, this simple construction works! You can instantiate it with Dolev-Strong if a PKI is available, with phase-king if there is no setup, or any other Byzantine Broadcast protocol that you want.

Theorem. Let BB denote any Byzantine Broadcast protocol in the synchronous setting, which can communicate messages from a particular set (e.g., one bit, or multi-bit messages) within \(R\) rounds for a network of \(n\) parties and tolerating up to \(f\) malicious parties.

Then, the above blockchain construction satisfies safety and liveness with \(\Delta = O(Rn)\), also for the same \(n\) and \(f\) and the same setup assumptions.

Proof of safety. This follows immediately from the consistency property of the underlying Byzantine Broadcast protocol.

• The broadcast protocol guarantees that at the end of each epoch, “all honest parties decide the same value” for the block to add to the log in that epoch.
• As a result, honest parties always have exactly the same log, because the protocol states that honest parties only append to the log at the end of each epoch.

Proof of liveness. To argue this claim, let’s think about how a transaction \(tx\) might be sent by someone in the world to one or more of the \(n\) parties in the permissioned blockchain.

• If a transaction \(tx\) is sent to a single honest party, then there are at most \(n\) epochs until that party becomes the designated sender and can add the transaction to a block that gets included in the log.

• If a transaction \(tx\) is sent to all parties, then there are at most \(f+1\) epochs until some honest party is nominated to the role of the designated sender. This party will include the transaction \(tx\) in its block (note: for now we are assuming that block sizes can be unbounded).

Since each epoch takes \(R\) rounds, and we typically think of \(f\) as being a constant fraction of \(n\): in either case it takes \(O(Rn)\) rounds to guarantee that a transaction gets added to the log.

On the one hand: this is an amazing theorem! It states that if we know how to build Byzantine Broadcast, then in some sense we have solved the problem of making a blockchain and therefore a financial transaction system.

Moreover:

• We were able to accomplish this goal without relying on energy-consuming computing power or needing massive economic incentives to keep the miners in line.
• By designing the system in a modular fashion, we can reuse components like Byzantine Broadcast in other situations that require resilient computing, such as fault-tolerant systems in airplanes, cars, power plants, and other critical infrastructure.

On the other hand: this blockchain protocol not that great for a few reasons.