Comment on page
Pipelined two-phase HotStuff Consensus
MonadBFT is a high-performance consensus mechanism for achieving agreement about the transaction ordering under partially synchronous conditions in the presence of Byzantine actors. It is a derivative of HotStuff with the improvement proposed in Jolteon/DiemBFT/Fast-HotStuff which is the reduction from three rounds to two rounds by utilizing quadratic communication complexity in the event of leader timeout.
MonadBFT is a pipelined two-phase BFT algorithm with optimistic responsiveness, and with linear communication overhead in the common case and quadratic communication in the case of a timeout. As in most BFT algorithms, communication proceeds in phases; at each phase, the leader sends a signed message to the voters, who send signed responses to the following leader. Pipelining allows the quorum certificate (QC) or timeout certificate (TC) for block
kto piggyback on the proposal for block
MonadBFT is a pipelined consensus mechanism that proceeds in rounds. The below description gives a high-level intuitive understanding of the protocol.
As is customary, let there be
n = 3f+1nodes, where
fis the max number of Byzantine nodes, i.e.
2f+1(i.e. 2/3) of the nodes are non-Byzantine. In the discussion below, let us also treat all nodes as having equal stake weight; in practice all thresholds can be expressed in terms of stake weight rather than in node count.
- In each round, the leader sends out a new block as well as either a QC or a TC (more on this shortly) for the previous round.
- Each validator reviews that block for adherence to protocol and, if they agree, send signed YES votes to the leader of the next round. That leader derives a QC (quorum certificate) by aggregating (via threshold signatures) YES votes from
2f+1validators. Note that communication in this case is linear: leader sends block to validators, validators send votes directly to next leader.
- Alternatively, if the validator does not receive a valid block within a pre-specified amount of time, it multicasts a signed timeout message to all of its peers. This timeout message also includes the highest QC that the validator has observed. If any validator accumulates
2f+1timeout messages, it assembles these (again via threshold signatures) into a TC (timeout certificate) which it then sends directly to the next leader.
- Each validator finalizes the block proposed in round
kupon receiving a QC for round
k+1(i.e. in the communication from the leader of round
- Alice, the leader of round
k, sends a new block to everyone (along with either a QC or TC for round
k-1; let's ignore that as it's not important).
2f+1validators vote YES on that block by sending their votes to Bob (leader of round
k+1), then the block in
k+1will include a QC for round
k. However, seeing the QC for round
kat this point is not enough for Valerie the validator to know that the block in round
khas been enshrined, since (for example) Bob could have been malicious and only sent the block to Valerie. All that Valerie can do is vote on block
k+1, sending her votes to Charlie (leader of round
2f+1validators vote YES on block
k+1, then Charlie publishes a QC for round
k+1as well as a block proposal for round
k+2. As soon as Valerie receives this block, she knows that the block from round
k(Alice's block) is finalized.
- Say that Bob had acted maliciously, either by sending an invalid block proposal at round
k+1, or by sending it to fewer than
2f+1validators. Then at least
f+1validators will timeout, then triggering the other non-Byzantine validators to timeout, leading to at least one of the validators to produce a TC for round
k+1. Then Charlie will publish the TC for round
k+1in his proposal (he will have to in order to make a proposal, because no QC will be available for round
- We refer to this commitment procedure as a 2-chain commit rule, because as soon as a validator sees 2 adjacent certified blocks
B', they can commit
Band all of its ancestors.
- Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. arXiv preprint arXiv:2106.10362, 2021.
Certificates (QCs and TCs) can be naively implemented as a vector of ECDSA signatures on the secp256k1 curve. These certificates are explicit and easy to construct and verify. However, the size of the certificate is linear with the number of signers. It poses a limit to scaling because the certificate is included in almost every consensus message, except vote message.
Pairing-based BLS signature on the BLS12-381 curve helps with solving the scaling issue. The signatures can be incrementally aggregated into one signature. Verifying the single valid aggregated signature provides proof that the stakes associated with the public keys have all signed on the message.
BLS signature is much slower than ECDSA signature. So for performance reasons, MonadBFT adopts a blended signature scheme where BLS signature is only used on aggregatable message types (votes and timeouts). Message integrity and authenticity is still provided by ECDSA signatures.