Paper 2000/034

Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography

Christian Cachin, Klaus Kursawe, and Victor Shoup

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, 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 nearly optimal because it tolerates the maximum number of corrupted parties, runs in constant expected time, has message and communication complexity close to the optimum, and uses a trusted dealer only in a setup phase, after which it can process a virtually unlimited number of transactions. The protocol is formulated as a transaction processing service in a cryptographic security model, which differs from the standard information-theoretic formalization and may be of independent interest.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Extended abstract appears in Proc. PODC 2000
Keywords
consensusByzantine faultsthreshold signaturescommon coindual-threshold schemes
Contact author(s)
cachin @ acm org
History
2000-08-15: revised
2000-07-16: received
See all versions
Short URL
https://ia.cr/2000/034
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/034,
      author = {Christian Cachin and Klaus Kursawe and Victor Shoup},
      title = {Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2000/034},
      year = {2000},
      note = {\url{https://eprint.iacr.org/2000/034}},
      url = {https://eprint.iacr.org/2000/034}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.