Byzantine Consensus under Static Peer Assumption

Created on Oct 6, 2023

Some notes for the book “Foundations of Distributed Consensus and Blockchains” by Elaine Shi

What is a Byzantine Fault?
- Crash Fault: Adversarial nodes do not send or receive any messages.
- Omission Fault: Adversarial nodes selectively choose to drop or let through each message sent or received.
- Byzantine Fault: Adversarial nodes can deviate from the protocol arbitrarily.
What is static assumption?
- Static: Participants in the consensus scenario are pre-defined. In the execution of a consensus protocol, the peers do not change.
- Dynamic: Nodes can join/leave the protocol freely.
Consensus Problems
- Byzantine Broadcast (BB) Protocol:
  - Consider a distributed network of n nodes numbered 1, 2, …, n respectively. There are f corrupt nodes, where f < n.
  - Node 1 is the sender of the network.
  - At the beginning of a protocol, the designated sender receives an input bit b in {0, 1}. All nodes (at least honest ones) run the same consensus protocol. At the end of the protocol, every node should output a bit.
    - Consistency: If two honest nodes output b and b' respectively, then b = b'.
    - Validity: If the sender is honest and receives the input bit b, then all honest nodes should output b.
- Byzantine Agreement (BA) Problem:
  - Consider a distributed network of n nodes numbered 1, 2, …, n respectively. There are f corrupt nodes, where f < n.
  - At the beginning of a protocol, every node receives an input b in {0,1}. All nodes (at least honest ones) run the same consensus protocol. At the end of the protocol, every node should output (agree on) a bit.
  - Properties:
    - Consistency: If two honest nodes output b1 and b2 respectively, then b1 = b2.
    - Validity: If all honest nodes receive the same input bit b, then all honest nodes must output b.
    - T-liveness: Every honest node must have produced an output after T rounds where T may be a function of n, the actual network delay ∆, and other parameters. (In sync, partial-sync network). For async network, all honest nodes output eventually (assuming that messages are delivered eventually).
  - Weak valid BA Protocol
    - Replace the original validity property with weak validity:
      - If all nodes are honest and they all receive the same input bit b, then they must all output b.
- State Machine Replication (SMR) Protocol:
  - The n nodes work together as a whole system, with each node maintaining an ever-growing, linearly-ordered sequence of transactions (aka. log, finalized log to be more accurate). The logs between replicas should achieve Consistency:
    - For Log_a from node a and Log_b from node b, Log_a should be the prefix (<=) of Log_b, or vice-versa.
  - Every honest node should achieve Liveness: If an honest node wants to add a new valid transaction tx to the system (its own log and other honest nodes’ logs) at time t, tx will be added to the system within a pre-defined delay T. (For example, in Bitcoin’s Nakamoto consensus protocol, T is about 60 min, or 6 block times.)
- Blockchain Protocol: SMR protocol + Byzantine fault tolerance.
Network Assumption
- Sync: Every node knows that for any message from node A to B, it takes at most ∆ time. (The network has a pre-defined max delay that every node knows.)
- Partial Sync: There are two different definitions for partial synchrony proposed in the paper “Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 1988.”
  - Unknown-Delta: The network has an unknown network delay ∆.
  - There exists a known ∆ < ∞ and an event called the Global Stabilization Time (GST) such that:
    - GST eventually happens after some finite time that can be chosen arbitrarily by the adversary.
    - A message sent by an honest node at time t is delivered to its recipient(s) by time ∆ + max(GST, t).
    - The network is in async mode before GST, and in sync mode with delay ∆ after GST. Honest nodes do not know the exact time of GST.
    - This two definition
- Async: The adversary can delay any message for an arbitrary, yet finite amount of time. However, it must eventually deliver every message sent by the honest nodes.
Other Considerations - PKI Setup: - Every node knows the public key of other nodes. - Every node can verify the message using modern cryptographic systems (e.g., ECDSA). - Security Model: - Deterministic Secure: The consensus protocol fulfills the security requirements (like validity/consistency) 100% of the time. - Probabilistic Secure: The consensus protocol fulfills the security requirements with a probability of 1-negl(λ), where λ is the security parameter.
BB + PKI Setup + Static Peers + Deterministic Security + Sync Network: Dolev-Strong Protocol
- BB Round Bound: This protocol proved that a deterministic protocol solving Byzantine Broadcast (allowing ideal signatures) must incur at least f + 1 rounds, where f < n and f is the number of bad nodes.
BB + No PKI + Static Peers + Sync network
- BB Lower Bound: “M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults” proves:
  - In a plain pairwise authenticated channel model without any setup assumptions (only secure communication channel) such as a PKI, Deterministic Byzantine Broadcast (BB) is impossible if at least n/3 nodes are corrupt.
  - Extension: For the probabilistic security model: there does not exist a protocol that achieves BB with a probability greater than 2/3 when f >= n/3 without PKI setup.
BB + No PKI + Static Peers + Probabilistic Security + Sync Network: There exists a BB protocol for f < n/3.
From BB to Blockchain Protocol:
- For any BB protocol under certain requirements, we can build a deterministic blockchain protocol under the same requirements as the BB.
  - We can achieve this by setting the round of the Blockchain protocol to execute the BB protocol + round-robin sender for each round.
  - This method is not efficient.
Blockchain + PKI + Static Peers + Probabilistic Security + Partial Sync: The Streamlet protocol achieves probabilistic security when f < n/3.
- In Streamlet:
  - Consistency holds regardless of the network delay.
  - Liveness is guaranteed when at least 5 honest nodes are elected as leaders in 5 consecutive epochs (which leads to probabilistic security).
No BB in Partial Sync Network with at Least 1 Bad Node
No BA in Partial Sync Network when f > n/3
- This means the Streamlet touches the f lower bound
- Extension: No BA in Sync Network when f > n/2
From BB to Weak Valid BA: If there is a deterministic R-round BB protocol that tolerates f corruptions, then there is a deterministic R-round weakly valid BA protocol also tolerating f corruptions.
FLP Impossibility: No Deterministic Weak BA in Async Network
- There does not exist a deterministic, asynchronous protocol that realizes weakly valid Byzantine Agreement in the presence of one crash fault.
- There exist randomized asynchronous consensus protocols that are secure in the presence of f < n/3 corruptions.
Summary
- Difficulty to build consensus protocol: BB > Blockchain > BA > Weak Valid BA
  - Any BB + round-robin sender => Blockchain
  - For a single round of a blockchain protocol, If the client who proposes a transaction can reach any honest node, and send the transaction to every honest node => BA