Master Thesis
Symmetric Gather?
Consensus protocols are at the core of blockchains and cryptocurrency networks; a lot of innovation has happened in the space during the recent years.
A gather protocol, first introduced by Canetti and Rabin [1], is designed to achieve a common set among processes in a system. Unlike similar protocols, such as agreement on a core set (ACS) [2], the gather protocol only requires agreement on a common core set among non-faulty parties [6]. In contrast, ACS requires full agreement on an identical output set for all parties. This distinction makes the gather protocol more efficient, as it operates in a constant number of rounds, while ACS typically incurs higher computational and communication costs due to the need for solving consensus. The gather protocol is an essential component of DAG-based consensus protocols like DAG-Rider [3] and Bullshark [4].
Canetti and Rabin [1] proved the correctness of their three-round gather implementation in the threshold setting using an elegant combinatorial proof. However, Villacis et al. [5] presented a counterexample for the same construction in the asymmetric setting. In this work, we will explore the gather problem in the generalized, symmetric trust model. Specifically, we aim to determine whether it is possible to maintain the three-round structure when using the generalized quorums proposed by Malkhi and Reiter [7]. If this is possible, we will develop a proof; otherwise, we will provide a counterexample and propose an alternative algorithm to address the problem.
References
[1] Fast Asynchronous Byzantine Agreement with Optimal Resilience
[2] Asynchronous secure computations with optimal resilience (extended abstract)
[4] Bullshark: DAG BFT Protocols Made Practical
[5] An Asymmetric DAG-based Consensus Protocol, in preparation.
[6] Living with Asynchrony: the Gather protocol