05.1-istanbul-bft.md

Istanbul Byzantine Fault Tolerance Consensus Algorithm

• Assumes a partially synchronous communication model - there is a known upper bound on message delivery time, and the system is synchronous after that bound;
  • Safety does not depend on synchrony assumptions;
  • Liveness does depend on synchrony assumptions;
• Deterministic - the algorithm is deterministic, the leader is chosen deterministically, and the algorithm is guaranteed to terminate;
• Leader-based - the algorithm is leader-based, with the leader being chosen deterministically;
• Optimally Resilient - tolerates up to $f$ Byzantine nodes in a network of $n \geq 3f + 1$ nodes;
• During normal operation, IBFT achieves termination in three communication rounds and has a total communication complexity of $O(n^2)$;
• Quorum-based - the algorithm is quorum-based, with a quorum size of $⌊\frac{n + f}{2}⌋ + 1$.

Guarantees

• Agreement - if a correct process decides some value $v$, then no correct process decides a value $v'$ such that $v \neq v'$;
• Validity - given an externally provided predicate $\beta$, if a correct process decides a value $v'$, then $\beta(v')$ is true;
  • The predicate $\beta$ is provided by the application and is used to determine the validity of the decision, in the context of the application - e.g., in a blockchain, $\beta$ could be the validity of a block;
• Termination - all correct processes eventually decide a value.

---

Protocol Overview

Normal Case Operation

Start Consensus

• Each process calls the startConsensus function, which initializes the consensus state, receiving a value $v$ to propose;
• Each process $p_i$ contains:
  • $\lambda_{i}$ - the consensus instance number;
  • $r_{i}$ - the round number of the consensus instance;
  • $pr_{i}$ - the round at which the process has prepared a value; initially $pr_{i} = \bot$;
  • $pv_{i}$ - the value that the process has prepared; initially $pv_{i} = \bot$;
  • $inputValue_{i}$ - the value that the process received as input to the consensus instance, and will propose if it is the leader;
• If the process is the leader, it broadcasts PRE-PREPARE messages to all other processes, containing the value $v$;
• Each process starts a timer.

Pre-Prepare Phase

• Upon receiving a valid PRE-PREPARE message from the leader, and its justified:
  • Resets its timer;
  • Broadcasts a PREPARE message to all other processes.

Prepare Phase

• Upon receiving a quorum ($⌊\frac{n + f}{2}⌋ + 1$) of valid PREPARE messages:
  • Update $pr_{i}$ and $pv_{i}$;
  • Broadcasts a COMMIT message to all other processes.

Commit Phase

• Upon receiving a quorum ($⌊\frac{n + f}{2}⌋ + 1$) of valid COMMIT messages:
  • Stops the timer;
  • Decides the value $v$ with quorum $Q_{commit}$.

Round Changes (View Changes)

Timer Expiration

• If the timer expires:
  • The process increments the round number $r_{i}$;
  • Resets the timer;
  • Broadcasts a ROUND-CHANGE message to all other processes.

Round-Change Phase

• Upon receiving $f + 1$ valid ROUND-CHANGE messages:

  • Updates the round number $r_{i}$;
  • Resets the timer;
  • Broadcasts a ROUND-CHANGE message to all other processes.

• Upon receiving a quorum ($⌊\frac{n + f}{2}⌋ + 1$) of valid ROUND-CHANGE messages, and the process is the leader:

  • Get the highest prepared value $pv_{max}$, if any;
  • Broadcasts a PRE-PREPARE message to all other processes, starting a new round.

• Upon receiving a valid ROUND-CHANGE message for an instance already decided:

  • Broadcasts the $Q_{commit}$ to the process, so that it can decide the value.

Justifications

• A ROUND-CHANGE message is justified if:

  • There is no $pr_{i}$ and $pv_{i}$, meaning that the leader of the round has not prepared a value, or;
  • Received a quorum of PREPARE messages for the value $pv_{i}$ and round $pr_{i}$.

• A PRE_PREPARE message is justified if:

  • The round number is 1, or;
  • Received a quorum of ROUND_CHANGE messages for that round, and each of them is justified.

Note: For messages who need to be justified, the justification is piggybacked on the message itself.