Doctoral Thesis: Improving Performance of Consensus Protocols

Jun Wan

Thesis Supervisor: Prof. Srini Devadas

Abstract

Designing an efficient solution for Byzantine broadcast (BB) is a central problem for many distributed computing and cryptographic tasks. An important challenge is to understand its round complexity and communication complexity. For round complexity, under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant rounds, regardless of the number of nodes n. However, whether we can match the expected constant round complexity in the corrupt majority setting remains unknown. We solve this long-standing question and achieve BB in expected constant rounds, even when 99% of the nodes are corrupted by a weakly adaptive adversary. Through a different solution, we also achieve BB in polylogarithmic rounds under dishonest majority and a strongly adaptive adversary.
For communication complexity, there have been many attempts to achieve sub-quadratic complexity in several directions, both in theory and practice, all with pros and cons. We initiate the study of another attempt: improving the amortized communication complexity of multi-shot Byzantine broadcast. Namely, we try to improve the average cost when we have sequential multiple broadcast instances. We aim to achieve optimal amortized linear complexity under an honest majority and a strongly adaptive adversary. Our core technique is to efficiently form a network for disseminating the sender’s message by keeping track of dishonest behaviors over multiple instances. We also generalize the technique for the dishonest majority to achieve amortized quadratic communication complexity.

Details

• Date: Tuesday, December 19
• Time: 1:30 pm - 3:00 pm
• Category: Thesis Defense
• Location: TBA

Additional Location Details:

Contact the doctoral candidate at junwan at mit dot edu, for the zoom link.