Back to search

Rochester Institute of Technology

Efficient Synchronous Byzantine Consensus

Abstract

dc:description.abstract

With the emergence of decentralized technologies such as Blockchains, Byzantine consensus protocols have become a fundamental building block as they provide a consistent service despite some malicious and arbitrary process failures. While the Byzantine consensus problem has been extensively studied for over four decades under various settings, many challenges and open problems still exist. Improving the communication complexity and the latency or round complexity are the two key challenges in the design of efficient and scalable solutions for the Byzantine consensus problem. This thesis focuses on improving the communication complexity and the round complexity of the synchronous Byzantine consensus problem under various setup assumptions. In this thesis, I will first present OptSync, a new paradigm to achieve optimistic responsiveness that allows a consensus protocol to commit with the best-possible latency under all conditions. A lower bound that relates to the commit latencies for an optimistically responsive protocol and matching upper bound protocols with optimal commit latency under all conditions will be presented. Then, I will discuss consensus protocols in the absence of threshold setup; this setting supports efficient reconfiguration of participating parties. In this setting, I will present two efficient consensus protocols that incur quadratic communication per decision and optimistically responsive latency during optimistic conditions. Next, I will discuss the design of communication and round efficient protocols for distributed key generation (DKG). I will present a new framework to solve the DKG problem and present two new constructions following the framework. The first protocol incurs cubic communication in expectation and expected constant rounds, while the second protocol incurs cubic communication in the worst-case and linear round complexity. Improved constructions for several useful primitives such as gradecast and multi-valued validated Byzantine agreement will also be presented. Finally, I will present communication and round efficient protocols for parallel broadcast where all parties wish to broadcast their input. A generic reduction from parallel broadcast to graded parallel broadcast and validated Byzantine consensus will be presented along with improved constructions for gradecast with multiple grades and multi-valued validated Byzantine agreement.

Degree

thesis:*
Name thesis:degree_name
Computing and Information Sciences (Ph.D.)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science (GCCIS)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shrestha, Nibesh
Contributors dc:contributor
  • Pengcheng Shi

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/11516

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shrestha, Nibesh. Efficient Synchronous Byzantine Consensus. Dissertation thesis, https://repository.rit.edu/theses/11516