Most methods for Byzantine fault tolerance (BFT) in the partial synchrony setting divide the local state of the nodes into views, and the transition from one view to the next dictates a leader change. In order to provide liveness, all honest nodes need to stay in the same view for a sufficiently long time. This requires view synchronization, a requisite of BFT that we extract and formally define here. Existing approaches for Byzantine view synchronization incur quadratic communication (in nn, the number of parties). A cascade of O(n)O(n) view changes may thus result in O(n^3)O(n3) communication complexity.
This paper presents a new Byzantine view synchronization algorithm named Cogsworth, that has optimistically linear communication complexity and constant latency. Faced with benign failures, Cogsworth has expected linear communication and constant latency.
The result here serves as an important step towards reaching solutions that have overall quadratic communication, the known lower bound on Byzantine fault-tolerant consensus. Cogsworth is particularly useful for a family of BFT protocols that already exhibit linear communication under various circumstances, but suffer quadratic overhead due to view synchronization.
“This paper proposes Cogsworth, a specific module for consensus protocol to achieve view synchronization. Cogsworth offers good performance in the optimistic case.”
“The paper formally defines the view synchronization problem in BFT protocols in the partial synchrony setting, where view synchronization is the agreement among the participating nodes on who is the current leader of the protocol. Furthermore, the authors present a new view synchronization algorithm called Cogsworth, which has optimal linear communication complexity and expected quadratic communication complexity, which the authors compare to existing view synchronization algorithms. These other algorithms have generally worse attributes. They achieve this reduction in the optimal case of execution in the communication complexity by having the participants only send messages to the leader of the new view, and the leader of the new view uses threshold signature to verify to every node that it has been elected correctly.”
“The paper puts a focus on view change protocols that are used to transition from one view to the next. Since there is a large body of view-based SMR algorithms, this topic has a high relevance. In particular, the authors raise attention to the quadratic message complexity. To this end, they define the view synchronization problem formally (for the first time) and contribute a new algorithm, Cogsworth, that improves message complexity (at least for benign failures).”
“The paper proposes a Byzantine Fault Tolerance protocol which allows for State Machine Replication. It is a very simple protocol which makes use of iterated views and doubling the delay to allow parties to reach synchronized views and consensus and advance views in sync. Using a round-robin approach for leader election and a voting mechanism in which signatures are aggregated in a threshold manner, the paper borrows ideas from the evolving blockchain space to revisit this long-standing problem in the permissioned setting. Notably, they introduce the definition of two desired properties that were not identified previously, namely the property of view synchronization (in which infinite views are synchronized for long durations shared among honest parties and with an honest leader) and synchronization validity (in which views do not advance more quickly than requested). They also give two theoretical metrics of performance for SMR protocol, latency and communication complexity, which measure the delay until all parties reach a new view on average, and the number of messages needed to be exchanged per view on average. They prove that their protocol attains linear expected communication complexity in the optimistic setting where no byzantine behavior is exhibited.”
“The paper is well written and raises attention to a somewhat neglected topic, namely view synchronization.”
“The protocol works well in the optimistic setting, which is a setting relevant in the blockchain era… The use of threshold signatures is a novelty recently introduced in the field, and it clearly allows improving upon communication complexity. This is a nice instance of this.”
“Precise definitions for the formal description of view synchronization. Interesting idea to use threshold signatures for the view changes as well, not only the normal execution of a BFT protocol.”
“Clear explanations and proofs, [and the] algorithm is simple and elegant.”
“[Re:] ‘Whenever TC,v has been received...’ [the paper intentionally doesn’t] talk about signature validation for conciseness, but it is worth reminding the reader at this point that the validity of TC relies on the threshold of the signature being met.”
“[This paper is] missing a discussion of the trade offs and limitations of Cogsworth… In addition, an empirical evaluation would very likely contribute to this discussion as well.”
“Both alternative algorithms presented are based on PBFT, which is true in essence, but can be confusing for the reader (especially the paragraph from line 423). More distinction is necessary there. Later the broadcast protocol is mentioned to be based on the Bracha RBC protocol.”
“In general, it is a bit unclear what triggers a wish_to_advance call from the nodes… It is [also] unclear from the paper whether partial synchrony (mentioned in the abstract) is the same or not as eventual synchrony mentioned as the setting for the Cogsworth algorithm (Line 147).”
“It is unclear if Property 1 is either necessary or sufficient. It may not be necessary, because many blockchain protocols today do not guarantee that their participants ever reach a common view, but that they share a view prefix (c.f. Common Prefix property of Bitcoin Backbone). It may not be sufficient, because, while there may be an infinite number of long honestly led views shared by all parties, these long views may be very far apart. Consider motivating this property a bit better?”
“It is unclear why the protocol does not work against an adaptive adversary or in the knowledge of the Leader function.”
“Algorithm 1 [is a bit confusing re:] the assertions that you pose on the views. It seems that the protocol should only advance views forward only, and hence Leader(r) should only be able to propose a v after r. If so, in line 11 I would expect to see r <= v <= r + f + 1r≤v≤r+f+1 and similarly in line 18. On the other hand in line 8 and line 5 I would expect to see something like r <= v <= r + f + 1r≤v≤r+f+1.”
“The broadcast protocol based view synchronization does not seem that much worse, as it is only worse in the optimal case of Cogsworth, but not in the expected case, and has the same attributes in the worst case as well. Calling the Cogsworth protocol the missing link seems like an overstatement. Cogsworth seems very good in the practical sense where Byzantine failures are rare, but not that good in a heavily adversarial setting. The paper could emphasize that aspect more.”