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

[LeoHLee]

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]

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

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]

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

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?