Asymptotically Optimal Validated Asynchronous Byzantine Agreement

Duke Privacy and Security Seminar
Speaker Name
Sravya Yandamuri
Date and Time
Talk will be virtual on Zoom

We provide a new protocol for Validated Asynchronous Byzantine Agreement in the authenticated setting. Validated (multi-valued) Asynchronous Byzantine Agreement is a key building block in constructing Atomic Broadcast and fault-tolerant state machine replication in the asynchronous setting. Our protocol has optimal resilience of f<n/3 Byzantine failures and asymptotically optimal expected O(1running time to reach agreement. Honest parties in our protocol send only an expected O(messages where each message contains a value and a constant number of signatures. Hence our total expected communication is O(words. The best previous result of Cachin et al. from 2001 solves Validated Byzantine Agreement with optimal resilience and O(1) expected time but with O(n^3) expected word communication . Our work addresses an open question of Cachin et al. from 2001 and improves the expected word communication from O(n^3) to asymptotically optimal O(n^2).

Short Biography

Sravya Yandamuri is a second year Duke CS Ph.D. student advised by Kartik Nayak. Her research interests include consensus protocols and blockchain.

Johes Bater