Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography

Christian Cachin Klaus Kursawe Victor Shoup

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


Byzantine agreement requires a set of parties in a distributed system to agree on a value even if some parties are corrupted. A new protocol for Byzantine agreement in a completely asynchronous network is presented that makes use of cryptography, specifically of threshold signatures and coin-tossing protocols. These cryptographic protocols have practical and provably secure implementations in the ``random oracle'' model. In particular, we present and analyze an implementation of the coin based on the Diffie-Hellman problem. The resulting asynchronous Byzantine agreement protocol is both practical and theoretically nearly optimal: - it withstands the maximum number of corrupted parties; - it runs in a constant expected number of rounds; - the number of messages is nearly optimal (to within a constant); - the total bit length of these messages is nearly optimal (to within a factor that depends only on a cryptographic security parameter); - it uses a trusted dealer only in a set-up phase, after which it can process an effectively unlimited number of transactions.