Collaborative Research: AF: Resource-Efficient Byzantine Protocols

Society depends on the performance and integrity of distributed networks that span the globe. Poorly performing or insecure distributed systems can threaten financial institutions, public well-being, and national security. This project will improve both the performance and security of modern distributed systems by addressing the fundamental Byzantine agreement (BA) problem, which lies at the core of many real-world applications. BA has the potential to benefit society by ensuring that distributed systems operate in a secure, reliable, correct, and efficient manner that can withstand attacks by even a large number of malicious agents. Although the BA problem is more than four decades old, the last several years have seen (1) new applications in areas such as blockchains, federated learning, distributed AI agents, wireless networks, and cryptography; and (2) new tools to solve BA more efficiently. This project will both develop new BA problem variants motivated by emerging applications and create new mathematical and algorithmic tools applicable to both classical and modern BA problems. The investigators will develop new Byzantine agreement protocols that are resource-efficient across various metrics, including time, communication, and energy cost. As part of this project, in person workshops will be organized jointly with staff from Sandia National Laboratories to train junior researchers in the area of cybersecurity, which is a critical national security requirement. The project will advance the state of the art in Byzantine computation via three main research goals. First, design efficient algorithms for BA in the classic model, aiming to minimize latency, communication, and energy cost. Second, solving BA in the smoothed analysis model: both smoothed analysis for node inputs and smoothed analysis to determine which nodes are controlled by the adversary; smoothed analysis generally yields more practical algorithms than those designed solely around worst-case guarantees. Third, solving BA in bounded degree networks, including those common in real-world networks such as wireless and blockchain networks. The BA algorithms will work in the full-information model: their correctness will not require cryptographic assumptions and will therefore have post-quantum security guarantees. Additionally, the BA algorithms will serve as building blocks for committee election and leader selection. To achieve these specific aims, the investigators plan to develop and refine new algorithmic tools, including statistical fraud detection and incorporate competitive resource analysis. The project team will also develop new lower bounds for these problems, based on techniques including bounding the number of individual coin flips needed and new applications of Von Neumann's minimax theorem. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.