Skip to main content

MonadBFT

Summary​

MonadBFT is a consensus mechanism that supports high throughput, fast finality, and a large number of participants.

MonadBFT allows globally distributed nodes to reach agreement on a single ordering of transactions. Like other BFT algorithms, MonadBFT operates under the assumptions of partial synchrony and a maximum 33% Byzantine stake weight.

MonadBFT is a derivative of HotStuff with improvements proposed in Jolteon/DiemBFT/Fast-HotStuff, which include introducing a quadratic-complexity timeout mechanism that allows the protocol to reduce from three rounds to two, and pipelining block proposals with response certificates so that a new block can be proposed each round.

Some notable features of MonadBFT, described herein, include:

  • Linear communication overhead in the happy path
  • Quadratic communication overhead in the event of a timeout
  • Pipelining of block proposals with response certificates, thus allowing a new block to be proposed every round
  • 500 ms round times / block frequency
  • 1s finality

Quick facts​

Sybil resistance mechanismProof-of-Stake (PoS)
Min block time500 ms
Finality1 second
Delegation allowedYes

Consensus Protocol​

Path from proposal to finality for block N in MonadBFT in the happy path. Communication is linear, generally following the "fan out, fan in" pattern. Leaders directly message to validators; validators directly message to the next leader.

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+1 nodes, where f is 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+1 validators. 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+1 timeout 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 k upon receiving a QC for round k+1 (i.e. in the communication from the leader of round k+2). Specifically:
    • Alice, the leader of round k, sends a new block to everyone1.
    • If 2f+1 validators vote YES on that block by sending their votes to Bob (leader of round k+1), then the block in k+1 will include a QC for round k. However, seeing the QC for round k at this point is not enough for Valerie the validator to know that the block in round k has been enshrined, because (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 k+2).
    • If 2f+1 validators vote YES on block k+1, then Charlie publishes a QC for round k+1 as 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+1 validators. Then at least f+1 validators will timeout, 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+1 in his proposal - no QC will be available for inclusion.
    • We refer to this commitment procedure as a 2-chain commit rule, because as soon as a validator sees 2 adjacent certified blocks B and B', they can commit B and all of its ancestors.

Block proposals in MonadBFT are pipelined. Same diagram as the previous, but zoomed out to include one more round.

References:

BLS Multi-Signatures​

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.

Footnotes​

  1. The block is also sent with a QC or TC for round k-1, but this is irrelevant for this example. ↩