search

Consensys / quorum

A permissioned implementation of Ethereum supporting data privacy
https://www.goquorum.com/
GNU Lesser General Public License v3.0
4.67k stars 1.29k forks source link

What is the communication complexity of round-change in Quorum's QBFT implementation? #1473

Closed LeoHLee closed 2 years ago

LeoHLee commented 2 years ago

As stated in the Istanbul BFT paper, Istanbul BFT "has O(n^2) communication complexity during both normal case operation and round changes". The QBFT spec also states a "message complexity of O(n^2)".

But when I read the latest quorum code, I notice that each qbfttypes.RoundChange object, which will be encoded into RLP format and broadcast to all peers, contains a list of prepare message named as Justification. The list contains at least a quorum of prepare messages, which have a number of O(n). A quorum or O(n) validators need to broadcast ROUND-CHANGE to start the new round, and a message broadcast will be gossiped to O(n) validators. So I get a message complexity of O(n^3) here.

So what is the round-change complexibility of QBFT implemented in current version? How is O(n^2) achieved if it does?

baptiste-b-pegasys commented 2 years ago

Hello, Message complexity is o² in QBFT, but it is o³ in IBFT

image

image

The paper is more abstractive, so it could be that in theory it's o², but in the end in the implementation it is o³, then optimized to o².

LeoHLee commented 2 years ago

Hello, Message complexity is o² in QBFT, but it is o³ in IBFT

image

image

The paper is more abstractive, so it could be that in theory it's o², but in the end in the implementation it is o³, then optimized to o².

Thanks for the slides. According to my current understanding, in order for o² complexity, the list of PREPARE message should only be sent to next round's block proposer, which is the optimization of QBFT. But I fail to locate any targeted data sending in the code. So can I get a conclusion that the optimization is still in progress?