Multiview: a new approach for PBFT implementation
Many well-known approaches to implementing the Proof of Stake consensus such as Tendermint , Hotstuff  and PBFT  are bi-modal: the protocol typically consists of a simple normal path where a leader makes proposals and everyone votes. When the normal path fails, the protocol switches to a much more complicated fall-back mode typically called a “view change”. In the view change phase, participants use the same communication process to reach an agreement on the new view before they can go back to the normal path of producing blocks.
Incognito’s BFT proposes a simpler approach. Instead of reaching an agreement on a single view, participants could see multiple views; the communication process for the view change in existing approaches is now used to propose the new block. Participants may have multiple different views, but when the majority (> ⅔ participants) commits a new block, this means that they have the same agreement on this view. If they continuously produce blocks on this view, i.e. this view dominant and achieves finality.
The number of malicious nodes in the network cannot simultaneously equal or exceed ⅓ of the overall nodes in the system in a given window of vulnerability.
Requirements for the nodes are that they are deterministic and start in the same state. The final result is that all honest nodes come to an agreement on the correct and longest chain.
Multiview PBFT details
Phases in Incognito’s Multiview PBFT
- Block Proposer broadcasts PROPOSE_MESSAGE and proposed block to Validators.
Validator broadcasts VOTE_MESSAGE and collects valid VOTE_MESSAGE(s).
- After bounded time T, if |VOTE_MESSAGE(s)| > ⅔ COMMITTEE_SIZE then continue to the commit phase.
- Otherwise, wait for the new propose phase.
- Validator combines VALIDATOR_SIGNATURE(s) and includes it in the block and COMMITS it to the chain. Then move to the new propose phase.
In a normal case, Incognito’s PBFT is quite similar to other PBFT protocols. A node is selected as a proposer which will propose a block; other committee members vote for the block to be appended to the chain. Proposers are selected in round-robin fashion based on their id in the committee.
If a normal case fails, due to:
- A byzantine proposer not proposing a new block, or proposing multiple blocks in a single round.
- Not collecting enough votes because vote messages are delayed.
Committee members would then see many different views. In order to restore the common view of all nodes, two general rules are applied:
- Do not try to propose many different blocks at the same height
- Follow the majority group
Vote rules & Propose rules
To achieve consensus without agreement on view change, nodes in Incognito’s committee have to use the following Vote rules and Propose rules
Two vote rules for:
- Branches with the same height
- Branches with different heights
Two Propose rules for:
- Branches with the same height
- Branches with different height
Lemma 1. (Finality 1) If two consecutive blocks B_(n) & B_(n+1) on the same branch are committed in two consecutive time slots, then block B_(n) is finality.
Proof. When block n is committed at time slot t, and block (n+1) is proposed at time slot (t+1), this implies that block (n+1) is proposed for the first time. This also implies that > 2/3 members received, agreed and voted for it. This means any further proposed block with height (n+1) will not get enough votes to commit, following Vote Rule 1. And following Vote Rule 2, no branch can grow any longer than the one with block n.
Lemma 2. (Finality 2) If two consecutive blocks B_(n) & B_(n+1) on the same branch are committed in time slots t and (t+2), where B_(n+1) is first proposed at time slot (t+1) then block B_(n) is finality.
Proof. Block (n+1) is committed at (t+2) with time slot (t+1), meaning that block (n+1) is first proposed at (t+1) because the block n is committed at t. This implies that block (n+1) with time slot (t+1) is the latest one, and > 2/3 members received, agreed and voted for it. This means any further proposed block (n+1) won’t get enough votes to commit, following Vote Rule 1. And following Vote Rule 2, no branch can grow any longer than this one.
Observation 1. If block bn is finality, then further blocks are appended to the branch containing bn, any other branch b’n is made obsolete. If a new block is successfully appended to another branch, say b’n, then more than ⅔ participants don’t agree bn is finality. This is a contradiction.
Theorem 1 (Consistency proof). Let chain ch := b1b2…bnbn+1 and chain ch’ = b’1b’2…b’nb’n+1
where bn+1 and b’n+1 are finality, and if bn+1 = b’n+1 then bi = b’i for i[n].
Proof. bn+1 and b’n+1 are finality, which means that bn and b’n are finality, if bn <> b’n, which either violates Observation 1 or the assumption that ⅔ participants are honest. 𑃰
Theorem 2 (Liveness proof). If some honest participant receives some transactions, this transaction will eventually be included in all honest participants’ finalized chains.
Observation 2. Proposer is selected in round-robin fashion. Any participant will eventually be a proposer. It can then include the transaction in proposed blocks.
Observation 3. If two blocks at the same height are committed, then the block proposed earlier must be committed later. Following Propose rule 1, nodes voted for the block with a smaller round only. If ⅔ nodes voted for the first proposed block, they won’t vote for the later one.
Consider the worst case scenario where two chains are growing to infinity. In order for this to happen, the following conditions must be satisfied:
- ⅔+1 weak participants don’t collect enough votes to commit any block, however they can vote for both chains as in Fig 1. The other ⅓ power participants could commit and propose new blocks.
- Proposers in group ⅓ power participants are divided into two groups, and are alternately selected to propose blocks on chain 1 and chain 2.
- When a participant proposes a block, the next proposer will not receive any message in this round, so it can propose a block on the other chain.
Let N be the number of participants. When network traffic is peaking, assume that the probability of successfully transmitting a message between two participants is 0.5. The probability of a participant not receiving any messages in one round is then (0.5N)2. This probability is negligible when N is large. Moreover, the probability of a participant not receiving any messages in x rounds is (0.5N)2x. This is exponentially decreased when the number of rounds is increasing. These conditions above are thus impossible to hold through many rounds. In order words, the liveness property is guaranteed.
Fig 1. Fork case
To summarize view change approach vs multiview approach,
- In the common case: a block is committed, View Change Approach (VCA) means finality, Multiview PBFT gets finality one block later.
- In the abnormal case: if there are 1/3 validators or more offline, both approaches fail to commit any new blocks.
- Network peaking: if more than ⅓ validators’ vote messages arrive late, in view change approach, participants repeatedly communicate to change to the new view, so no block can be committed. In a multiview approach, a block can be committed and appended to the chain.
The approach of multiview PBFT has a natural philosophy. The consensus respects the majority group, the powerful node - which can commit blocks during bursts of network traffic - can advance the chain to new height during heavy network traffic.
The multiview PBFT approach is simple but has many advantages:
- Avoids the overhead of synchronization when view-change condition is triggered.
- When a minor number of participants can commit a block, the view change approach will sync for the new view. A multiview approach has a chance to continuously append the new block to the chain as long as the next proposer can commit the latest block.