Source:Wikipedia
Homework
Office hours
We have spent the past few lectures discussing how to record transactions within a blockchain using bitcoin's proof of work.
As long as the majority of computational power is controlled by honest miners, then everybody's view of the blockchain is eventually consistent.
Overy simplifying bitcoin, we can summarize it in these main steps:
Mini goal: Can we build a blockchain with no proof of work? No miners? maybe not even a cryptocurrency?
We can abstract bitcoin further into two logical parts:
In this lecture, we are going to study Broadcast. We will later tackle leader elction in future lectures.
Source:Wikipedia
“Imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement.”
Suppose that there are n generals, and one of them is called the commanding general. The commanding general would like to propose an order that is either ATTACK or RETREAT to all generals, such that
commanding general’s order.
If the commanding general is honest then it's easy!
Assuming the messenger is intact, then the commanding parties can just follow the orders of the commanding General.
The problem becomes really hard when the commander is dishonest. The commanding general might send different orders to different generals!
We need a protocol that can handle a dishonest commander!
Let's turn back to computers now. Let's assume that attack and Retreat are encoded by 0 and 1 respectively. Furthermore, let's assume that the commander is called sender.
A Byzantine Broadcast (BB) protocol is supposed to satisfy the following two requirements (no matter how corrupt/malicious parties behave):
• Validity : If the sender is honest and sends the bit b, then all honest nodes should output b
• Consistency : If two honest nodes output b and b′ respectively, then b = b′.
If validity doesn't exist then consistency is trivially easy. Can you guess why?
Note that if the leader is malicious then it only matters that the parties are consistent. They can output anything as long as it's the same thing.
Note that although BB is defined for one bit, we can easily extended it to a k bit sized message by running the protocol k times.
We should ask ourselves questions about the model:
Can the messenger cheat? Can the messenger die (can we detect it)? How long does a messenger need to reach the other generals? Can the messenger reach all generals? How many generals do we have? How many traitors do we have? Can we restrict the type of cheating that generals do? Do we know who the bad generals are? Do the generals or the messengers have access to randomness?
Synchronous vs Asynchronous network. (assumptions about the messenger)
Synchronous network: We have an upper bound on the time it takes for a message to travel between two parties. The protcol is broken into rounds. If a message doesn't arrive in a specific round then the sender is assumed to be malicious (or byzantine).
Asynchronous network: We have no upper bound on the time it takes for a message to travel between parties. We cannot differentiate between honest slow senders and malicious parties that choose not to send any messages.
In both network types, if an honest party sends a message then the message is eventually received.
Static vs Adaptive adversary. (assumptions about the generals)
Static adversary: The attacker chooses what parties to corrupt at the start of the protocol. The attacker can no longer corrupt parties afterwards.
Adaptive adversary: The attacker can pick what parties to corrupt and when.
Honest vs Dishonest majority. (assumptions about the generals)
We assume that the total number of parties is $n$ and we use $f$ to denote the number of malicious parties.
Honest majority $n > 2f$: More than half the parties are honest.
Dishonest majority $f < n$: Most parties are malicious.
Authenticated pair wise channels: Every party is connected to every other party and no party can impersonate another.
Public key infrastructure (PKI): Every party knows the public key of every other party.
Deterministic vs Randomized protocols.
Deterministic protocol: The protocol runs in a deterministic way. The protcol will always have the same execution path given the same input.
Randomized protocol: The protocol has access to some randomness source that effects the state of the protocol. Every run would lead to a different execution path.
Dolev-Strong protocol solves the byzantine broadcast problem in the following settings:
This part of the lecture follows the notes from Decentralized Thoughts
Assume that all parties have ids from $1$ to $n$.
Furthermore, assume that the sender or the leader has $id = 1$. As a first attempt, let’s try to implement Broadcast for $f=1$ in $2$ rounds.
Reminder: A Byzantine Broadcast (BB) must satisfy the two properties
• Validity : If the sender is honest and sends the bit b, then all honest nodes should output b
• Consistency : If two honest nodes output b and b′ respectively, then b = b′.
Round 1: Leader (party 1) sends message <b, sign(b, 1)> to all parties
Round 2: If party $i$ receives <b, sign(b,1)> from leader, then add $b$ to $B_i$ and send <b, sign(b,1)> to all parties
End of round 2: If party $i$ receives <b, sign(b,1)> from anyone, then add $b$ to $B_i$
Decision rule: If the set $B_i$ contains only a single bit $b$, then output $b$. Otherwise, output a default bit $0$
Proof:
Validity: All honest party will see the same bit signed correctly from the dealer in round 1 and hence every party will send that one signed bit to every party in round 2. At the end of round 2 all honest parties will see the same bit with a valid signature from the dealer because nobody can forge the signature of the dealer.
Consistency: If the dealer tries to cheat and send two different messages to two difference honest parties, in round 2, those honest parties will send it to everyone else. Everyone would know that the dealer cheated. Hence all of them will default to a default bit 0.
The previous proof is wrong.
Here is a counter example that will break consistency:
The dealer doesn't send any messages in round 1. In round 2, the dealer sends a bit 1 only to some honest parties. Those honest parties will finish with bit 1 but others will finish with the default bit 0!
Round 1: Leader (party 1) sends message <b, sign(b, 1)> to all parties
Round 2: If party 𝑖 receives <b, sign(b,1)> from leader, then add 𝑏 to $𝐵_𝑖$
and send <b, sign(b,1)> to all parties
End of round 2: If party 𝑖 receives <b, sign(b,1), sign(b, j)> from any j, then add $𝑏$ to $𝐵_𝑖$
Decision rule: If the set $𝐵_𝑖$ contains only a single bit 𝑏, then output $𝑏$. Otherwise, output a default bit $0$
The main problem here is that honest parties have learned their value in the last round. They can't tell other honest parties about it because it was the last round! They can't send messages anymore! olev and Strong show a very elegant way to guarantee consistency even if the value decided is revealed in the last round. On the last round, a party would only accept if it sees $f+1$ signatures on it where the first signature must have came from the leader! The idea is if it sees $f+1$ distinct signatures, then surely one of them is from an honest party. That honest party would have made sure that everyone else saw that message.
// Leader (party 1) with input b
Round 1: send <b, sign(b,1)> to all parties.
// Party i in round j, 1 < j <= f+1
For a message m, arriving at the beginning of round j: if m has a bit $b$ and $j-1$ signatures from $j-1$ distinct parties, where the first signature is from the dealer, then add $b$ to $B_i$ send <b, sign(b,i)> to all parties
// Party i decision rule
Decision at the end of round $f+1$: If $B_i$ is of size exactly 1 then output B_i[0]. Otherwise output the default bit $0$
Assume we modify the protocol above but stop at f rounds instead of f+1 rounds, can you come up with an attack against it?
Assume that the input bit $b$ is 1. Just before round $f$ finishes all the malicious parties will send a different bit to one honest party $p_i$. This honest party would see it but it won't be able to send it to any party because the round has finished!! That honest party alone would finish with $0$ while every other honest party finishes with $1$.
Consistency: If an honest party receives a $k$ distinct signatures for a bit $b$ at the end of round $k$, where the first signature is from the leader, then it will send it to all honest parties in round $k+1$. This holds for all rounds except the last round, round $f+1$. But since the honest party can only receive f+1 distinct signatures for a given bit $b$ in round $f+1$ (and not send anything), and a there is least one signature from an honest party $h$, $h$ must have already sent $b$ along with the proper signatures to all other honest parties. Thus, every bit received by one honest party will be received by all other honest parties. Therefore, in case two different bits has been propagated to two different honest parties by a malicious dealer then all honest parties will detect it and default to the bit $0$.
