# Consensus mechanism

# Practical Byzantine Fault Tolerant

Practical Byzantine Fault Tolerant, in short PBFT, “presents a new, practical algorithm for state machine replication that tolerates Byzantine faults." [1] The Zarb consensus algorithm is highly inspired by Practical Byzantine Fault Tolerant (PBFT) algorithm.

# The algorithm

There are R=3f+1R = 3f+1 replicas. where ff is the maximum number of replicas that may be faulty or byzantine. For example, if there is one faulty replica, the resiliency of the algorithm is optimal if we have at least 3 non-faulty replicas. So the minimum number of replicas should be 3+1=43+1=4.

In each round, one replica is the proposer and the others are validators. The normal case operation of Zarb consensus algorithm includes these three steps: propose, prepare and precommit

# Propose phase

A proposer (PP) collects transactions and creates a proposal block. It signs and broadcasts a proposal message with block piggybacked to all the validators.

Proposal message has this form:

<<PROPOSAL,h,r,d>σp,B><<PROPOSAL,h,r,d>_{\sigma p}, B>

where:

  • BB is proposed block
  • dd is proposal's digest or hash
  • hh indicates the block height
  • rr is an assigned round number, which is zero for the first round

# Prepare phase

If validator ii accepts the proposal, it enters prepare phase and signs and broadcasts prepare message to all other validators. Otherwise, it does nothing.

Prepare message has this form:

<<PREPARE,h,r,d,i>σi><<PREPARE,h,r,d,i>_{\sigma i}>

If validator ii received 2f+12f+1 prepare messages from other validators (possibly including its own), it is prepared and enters to precommit phase.

# precommit phase

In precommit phase, validator ii signs and broadcasts precommit message to the other validators.

Precommit message has this form:

<<PRECOMMIT,h,r,d,i>σi><<PRECOMMIT,h,r,d,i>_{\sigma i}>

Each validator executes and commits block bb after receiving 2f+12f+1 precommit messages (possibly including its own) and becomes committed.

All the messages in the above steps are cryptographically signed and all replicas know the others’ public keys to verify signatures.

The picture below shows the operation of the algorithm in the normal case of no primary faults. Replica 0 is the proposer, replica 3 is faulty.

Normal execution

# Block announcement

Each validator that receives a valid proposal and with 2f+12f+1 precommit messages can make a certificate and broadcasts block_announce messages with the block and certificate piggybacked to the network.

<BLOCKANNOUNCE,h,r,B,C><BLOCK-ANNOUNCE,h,r,B,C>

where:

  • CC is the block certificate

Validators can move to the next height and clear the message logs after receiving valid block_announce message.

# Change proposer

The change-proposer protocol provides liveness by allowing the system to make progress when the proposer fails. change-proposers are triggered by timeouts that prevent validators from waiting indefinitely for the proposal to execute.

If the timer of validator expires in a round, the validator starts a change-proposer phase to move the system to round r+1r+1. It stops accepting messages (other than change-proposer and block-announce messages) and broadcasts a change-proposer message to all validators.

The change-proposer message has this form:

<<CHANGEPROPOSER,h,r,i>σi><<CHANGE-PROPOSER,h,r,i>_{\sigma i}>

If the proposer for round r+1r+1 receives 2f+12f+1 valid change-proposer messages for round rr from other validators, it goes to next round and broadcasts proposal message.

Proposer change


  1. Practical Byzantine Fault Tolerance (opens new window) ↩︎