Summary

This DIP describes a major latency improvement - 2-chain commit rule instead of 3-chain - as described in DiemBFT-V4.

Abstract

Currently, DiemBFT inherits the 3-chain commit rules from HotStuff to achieve both communication efficiency and optimistic responsiveness during leader replacement. Two important observations led us to move to a 2-chain commit rule. First, during successful leader terms, a leader can be replaced with a 2-chain commit while maintaining the good properties of 3-chain commits. Second, if a leader term is unsuccessful, timeout messages and round synchronization in DiemBFT already incur a higher communication cost and a delay. Indeed, our research shows that we can use a 2-chain commit rule with a minor increase in communication overhead when validators time out of a consensus round.

We only discuss engineering impact and omit the theoretical analysis from this DIP. Readers are encouraged to read the full whitepaper.

Required Changes

Types

In order to provide safety under a 2-chain protocol, two new timeout related structs are added to represent the highest quorum certificate the validator node has when it times out of a round.

pub struct TwoChainTimeout {

/// Epoch number corresponds to the set of validators that are active for this round.

epoch: u64,

/// The consensus protocol executes proposals (blocks) in rounds, which monotonically increase per epoch.

round: Round,

/// The highest quorum cert the signer has seen.

quorum_cert: QuorumCert,

}

pub struct TwoChainTimeoutCertificate {

timeout: TwoChainTimeout,

signatures: BTreeMap<Author, (Round, Ed25519Signature)>,

}

The signature for TwoChainTimeout is done indirectly, on the derived struct TimeoutSigningRepr which uses the highest qc round instead of an actual QuorumCert in order to optimize the TwoChainTimeoutCertificate.

TwoChainTimeoutCertificate aggregates from 2f+1 TwoChainTimeout of the same epoch and round, it only carries a single quorum cert instead of 2f+1 as an optimization to save both bandwidth and verification cost. The single TwoChainTimeout is the one with the highest quorum cert among 2f+1.

pub struct TimeoutSigningRepr {

pub epoch: u64,

pub round: Round,

pub hqc_round: Round,

}

Rules

The Safety Rules code has been changed accordingly and the proofs of safety and liveness are in the whitepaper.

QC represents QuorumCertificate. TC represents TwoChainTimeoutCertificate.

Voting Rule:

1. block.round > last vote round
2. block.round == block.qc.round + 1 || (block.round == tc.round + 1 && block.qc.round >= tc.highest_hqc_round)

Timeout Rule:

1. round >= last vote round
2. (round == qc.round + 1 || round == tc.round + 1) && qc.round >= 1-chain round

Commit Rule:

• It's safe to commit block B if there exist a 2-chain B <- QC <- B' <- QC such that B'.round == B.round + 1.

Upgrade

Switching from existing DiemBFT to the new version requires reconfiguration. An on-chain consensus config will be added to support the transition from 3-chain to 2-chain at an epoch boundary. We also switch from BCS to a backward compatible wire protocol (JSON) to simplify migrating data structures.

Client

This change is client agnostic, other than an observable improvement in commit latency improvement due to that LedgerInfo which encapsulates the commit rule.

Acknowledgement

We thank the following people for reviewing earlier versions of DiemBFT-v4:

• Gregory Chockler
• Alexey Gotsman
• Rachid Guerraoui
• Kartik Nayak
• Ling Ren
• Ted Yin