September 2018 Reading List

[jalora]

September 2018

• [x] Byzantine General's Problem
• [x] Consensus Problem in Unreliable Distributed Systems
• [x] Byzantine Generals and Transaction Commit Protocols
• [ ] Early Stopping in Byzantine Agreement
• [ ] On the formalization of Nakamoto consensus

[jalora]

Byzantine General's Problem (Lamport et al (1982))

Problem statement: A commanding general must send an order to his n - 1 lieutenant generals s.t. the following interactive consistency conditions are met:

• IC1: All LOYAL lieutenants obey same order
• IC2: If commanding general is LOYAL, then all LOYAL lieutenants will obey the order he sends

Impossibility: Byz consensus cannot be achieved if 1/3 or more generals are traitors.

• Proof for 3-generals is derived in Pease et al (1980)
• 3-generals impossibility is extended to 3m or fewer generals (w/ m traitors) by allowing at most m generals to be simulated by each general in the 3-generals model. Essentially, transform m-generals problem to 3-generals problem.
• Turns out exact consensus is just as difficult as approximate consensus.

Byzantine Assumptions

• A1: Every message sent is delivered correctly
• A2: Receiver of message knows who sent it
• A3: Absence of message can be detected
• A4: Signed message assumptions
  • a) a loyal general's signature cannot be forged, and any altercation of the contents of the signed signature will be detected
  • b) Anyone can verify the authenticity of a general's signature

Proposed Algorithms (assuming at most m traitors)

Unsigned Messages: OM(m)

• This algorithm is robust for <1/3 traitors, since it allows traitors to lie about the message they pass (regardless if the message was passed from a loyal or traitorous general)

Algorithm

1. Commanding general sends messages to all lieutenants
2. Lieutenant i propagates received values to all other lieutenants (not including himself)
   • This message passing is recursive and is executed (n-1)...(n-m) times once algorithm unfolds
   • Number of messages sent = all unique ordering of n generals (P(n-1,m) = (n-1)!/(n-m-1)!) after m executions
3. Lieutenants execute the majority values received from all other lieutenants

Signed Messages: SM(m)

• Restrict traitorous general's ability to lie by introducing signed messages and imposing A4.
  • Note: Traitorous generals cannot forge loyal general's signature, but can forge a traitor's signature (allowing for collusion)
• Robust for m traitors and m+2 or more loyal generals

Algorithm

1. Commanding general sends messages to all lieutenants
2. For each lieutenant i
   • if message v is from commander, send to v:0:i to all other lieutenants, and set V_i = {v}
   • if message from another lieutenant (i.e. v:0:j_1:...:j_k), set V_i + {v} if {v} not in V_i
     • if k < m, send message v:0:j_1:...:j_k:i to all other lieutenants not in {j_1,...,j_k}
3. Each lieutenant i executes their order via choice(V_i)

Missing Communication Paths Cases

• Past algorithms assume a completely connected graph
• The results for OM(m) can be extended to 3m-regular graphs of generals
  • If there are 3m+1 generals, then this is basically a completely connected graph
• OM(m,p) (Extension of OM(m) to a p-regular graph):
  • Commander sends order to each lieutenant i
  • Lieutenant i propagates his values to all his neighbors, with each neighbor lieutenant j executing OM(m-1, p-1) (modified graph that removes original commander and makes lieutenant i the new commander)
  • Each lieutenant i executes the majority order
• SM(m) can be extended to allow for the least amount of connectivity
  • This requires that the subgraph of all loyal generals be connected
  • Connected graph = There exists a path between any two node (no single node is unreachable from any node in the graph)
• Modification to SM(m)
  • Commander only sends signed message to neighboring lieutenants
  • Lieutenant i sends signed message to only other neighboring lieutenants
• Thus SM(n-2), for any n generals, and any number m traitors, solves the BG problem if all loyal generals are connected.
  • More generally, if subgraph is not connected then SM(m+d-1) (where d is the furthest distance from a loyal general to another) still solves the BG problem

Discussion of Practicality of Assumptions

• Note that a solution to the BG problem only ensures that systems use the same input value. A faulty input device may potentially provide bad or meaningless values.
  • One way to address this is to introduce redundancy in the input devices
• A1 requires that every message from a non-adverserial system be delivered correctly. Communication system failures between two nodes is indistinguishable from the failure of a single processor
  • Hence, a communication failure can be part of the m adversaries
  • For weakly connected graphs, SM(m+d-1) handles this general case through m and d (if the communication path between non-adversarial systems are broken)
• A2 (without A4) requires communication over fixed communication lines. If A4 is valid, then A2 is not required since signatures provide the information required to determine the originator of the message.
• In A3, the absence of a message can only be detected if it fails to arrive within a fixed length of time. This requires:
  1. A maximum time for generating and transmitting a message, mu
  2. Sender's and receiver's clocks are synchronized to some max error tau
• Detecting absence of message: if T_ij in [T_0, T_0 + mu + tau] then "valid message", else "sender faulty" where T_i is time to generate and send message from system i to system j and T_0 is a universal time between i and j
  • Clocks must be periodically synchronized to prevent clocks from drifting arbitrarily (asynching)
• For problems requiring asynchronous clocks (i.e. messages are sent arbitrarily quickly), there exists no algorithm that can solve BG problem
• Construction of a signature that meets A4 is a cryptography problem!

[jalora]

Byzantine Generals and Transaction Commit Protocols - Lamport et al 1984

Overview: Show that the lower bound time complexity for a t-resilient crash consensus protocol is t+1 rounds. Detail protocol specifications and a BG algorithm that solves problem.

• Crash-failure: Process crashes and stays crashed for the rest of the protocol execution. Creates a weaker threat scenario than byzantine-failure.
• Proofs in this paper abstract the execution of a consensus algorithm by considering all possible executions of the protocol, called scenarios

Weak Byzantine General's Problem:

• WBG1: If no process fails and all processes initially choose the same action, then that is the final action taken by all processes.
• WBG2: Any two processes that do not fail take the same action

Crash-resilient Protocol Specifications

note:

• round = 1) send 2) receive
• [r+1] = 1...r+1
  1. A process need not crash up to any round r (Lemma 1)
  2. If a process does crash, it can crash before, during Defn 3, part 4, and after it sends its message.
  3. r-Regularity (Definition 5)
• Max amount of process that can crash for any round s in [r + 1] i.e. |CR[S](s)| <= s - 1
• Eliminates scenario where a process has already crashed prior to round 1
• r-Regularity implies that at most 1 process can fail per round (assuming continuous fault) at each round = this is k-fault.
• If non-continuous fault, then consensus achieved in f+1 = f-fault. e.g. CR[S](2) = 1, CR[S](3) = 1, CR[S](4) = 3 then it will resolve in round 2

Proof Sketch of Time Complexity Lower Bound

Theorem 1: There does not exist a t-crash resilient, t-round Weak Byzantine General's Algorithm.

• Assume there exists a t-crash resilient, t-round Weak Byzantine General's Algorithm.
• There exists scenarios where the initial private value assigned to each process differs & these scenarios execute w/ no crashes
  • there exists S^j s.t. Val_p[S^j] = {v: if p <= k, u: if p > j} and C[S^j] = {}
  • WBG1 guarantees that the public value chosen by S^0 = u and S^k = v, implying that there exists p s.t. S^{p-1} and S^p have different public values. (Contradiction Criteria)
• Lemma 1 part B and Lemma 3 guarantees that both S^{p-1} and S^p can continue their execution through round k and only have some process p fail during round 1. (note: S^{p-1} and S^p are 1-regular scenarios.)
• Since p is the only process that crashes in these two scenarios, by Lemma 2 part B, the execution should look the same for all non-crashed processes between S^{p-1} and S^p.
• Therefore, WBG2 guarantees that the public value of S^{p-1} and S^p must be the same (Contradiction).

See very sketch proof on page 26. Essentially, in the worst case, there exists no algorithm that can achieve consensus after t rounds in a t-crash protocol since only t processors (through which v passes through) out of the total k will be in consensus, while k-t pick different values.

BG Algorithm and Properties

• t-resilient algorithm is one that can handle worst case scenario where the value of commander is sent only to one other process in the next round. See page 26 for example.

**Round 1:** Process 1 sends value 'v' to all processes
**Round r, where 1 < r <= t+1:** Each process
1. If it received 'v' in {0, 1} from **any** process in r-1 then...
   - Choose 'v' as public value, i.e. V = {v}
   - send 'v' to all other processes
   - halt

2. if it received an "I don't know" from **every** other process then...
   - Choose 'null' as public value, i.e. V = {null}
   - send 'null' to all other processes
   - halt

3. Send an "I don't know" to all processes

• Note that in the worst case, it will take t+1 rounds to come to consensus, but it is possible for consensus to be achieved faster (e.g. v is sent to some process that doesn't fail in the next round)
• Require t+1 rounds because there must exist a round where no process fails s.t. v can be sent to all other processes.