Random oracles in constantinople: Practical asynchronous Byzantine agreement using cryptography

Christian Cachin, Klaus Kursawe, Victor Shoup

Research output: Contribution to journalArticlepeer-review


Byzantine agreement requires a set of parties in a distributed system to agree on a value even if some parties are maliciously misbehaving. A new protocol for Byzantine agreement in a completely asynchronous network is presented that makes use of new cryptographic protocols, specifically protocols for threshold signatures and coin-tossing. These cryptographic protocols have practical and provably secure implementations in the random oracle model. In particular, a coin-tossing protocol based on the Diffie-Hellman problem is presented and analyzed. The resulting asynchronous Byzantine agreement protocol is both practical and theoretically optimal because it tolerates the maximum number of corrupted parties, runs in constant expected rounds, has message and communication complexity close to the optimum, and uses a trusted dealer only once in a setup phase, after which it can process a virtually unlimited number of transactions.

Original languageEnglish (US)
Pages (from-to)219-246
Number of pages28
JournalJournal of Cryptology
Issue number3
StatePublished - Jul 2005

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Random oracles in constantinople: Practical asynchronous Byzantine agreement using cryptography'. Together they form a unique fingerprint.

Cite this