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
Abstract
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.