research-article

All You Need is DAG

Authors:

Eleftherios Kokoris-Kogias,

Alexander SpiegelmanAuthors Info & Claims

PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

Pages 165 - 175

https://doi.org/10.1145/3465084.3467905

Published: 23 July 2021 Publication History

Abstract

We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all values proposed by correct processes eventually get delivered. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication.

Supplementary Material

MP4 File (dag.mp4)

We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all values proposed by correct processes eventually get delivered. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication.

Download
15.38 MB

References

[1]

Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. 2019. Asymptotically Optimal Validated Asynchronous Byzantine Agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Toronto ON, Canada) (PODC '19). ACM, New York, NY, USA, 337--346. https://doi.org/10.1145/3293611.3331612

Digital Library

[2]

Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, et al. 2018. Hyperledger fabric: a distributed operating system for permissioned blockchains. In Proceedings of the Thirteenth EuroSys Conference. ACM, 30.

Digital Library

[3]

Leemon Baird. 2016. The swirlds hashgraph consensus algorithm: Fair, fast, Byzantine fault tolerance. Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep (2016).

[4]

Laasya Bangalore, Ashish Choudhury, and Arpita Patra. 2018. Almost-surely terminating asynchronous Byzantine agreement revisited. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. 295--304.

Digital Library

[5]

Shai Ben-David, Allan Borodin, Richard Karp, Gabor Tardos, and Avi Wigderson. 1994. On the power of randomization in on-line algorithms. Algorithmica, Vol. 11, 1 (1994), 2--14.

Digital Library

[6]

Michael Ben-Or and Ran El-Yaniv. 2003. Resilient-optimal interactive consistency in constant time. Distributed Computing, Vol. 16, 4 (2003), 249--262.

Digital Library

[7]

Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. 2020. Asynchronous Byzantine Agreement with Subquadratic Communication. In Theory of Cryptography Conference. Springer, 353--380.

[8]

Dan Boneh, Ben Lynn, and Hovav Shacham. 2001. Short signatures from the Weil pairing. In International conference on the theory and application of cryptology and information security. Springer, 514--532.

Digital Library

[9]

Edward Bortnikov, Maxim Gurevich, Idit Keidar, Gabriel Kliot, and Alexander Shraer. 2009. Brahms: Byzantine resilient random membership sampling. Computer Networks, Vol. 53, 13 (2009), 2340--2359.

Digital Library

[10]

Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. 2006. Randomized gossip algorithms. IEEE/ACM Transactions on Networking (TON), Vol. 14, SI (2006), 2508--2530.

Digital Library

[11]

Gabriel Bracha. 1987. Asynchronous Byzantine agreement protocols. Information and Computation, Vol. 75, 2 (1987), 130--143.

Digital Library

[12]

Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001. Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference. Springer, 524--541.

Digital Library

[13]

Christian Cachin, Klaus Kursawe, and Victor Shoup. 2005. Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. Journal of Cryptology, Vol. 18, 3 (2005), 219--246.

Digital Library

[14]

Christian Cachin and Stefano Tessaro. 2005. Asynchronous verifiable information dispersal. In 24th IEEE Symposium on Reliable Distributed Systems (SRDS'05). IEEE, 191--201.

Digital Library

[15]

Ran Canetti. 1996. Studies in secure multiparty computation and applications. Ph.D. Dissertation. Citeseer.

[16]

Ran Canetti and Tal Rabin. 1993. Fast asynchronous Byzantine agreement with optimal resilience. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. 42--51.

Digital Library

[17]

Miguel Castro, Barbara Liskov, et al. 1999. Practical Byzantine fault tolerance. In OSDI, Vol. 99. 173--186.

Digital Library

[18]

Gregory V Chockler, Nabil Huleihel, and Danny Dolev. 1998. An adaptive totally ordered multicast protocol that tolerates partitions. In Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing. 237--246.

Digital Library

[19]

Miguel Correia, Nuno Ferreira Neves, and Paulo Veríssimo. 2006. From consensus to atomic broadcast: Time-free Byzantine-resistant protocols without signatures. Comput. J., Vol. 49, 1 (2006), 82--96.

Digital Library

[20]

Danny Dolev and Eli Gafni. 2016. Some garbage in-some garbage out: Asynchronous t-Byzantine as asynchronous benign t-resilient system with fixed t-trojan-horse inputs. arXiv preprint arXiv:1607.01210 (2016).

[21]

Danny Dolev, Shlomo Kramer, and Dalia Malki. 1993. Early delivery totally ordered multicast in asynchronous environments. In FTCS-23 The Twenty-Third International Symposium on Fault-Tolerant Computing. IEEE, 544--553.

[22]

Assia Doudou, Benoit Garbinato, and Rachid Guerraoui. 2000. Abstractions for devising Byzantine-resilient state machine replication. In Proceedings 19th IEEE Symposium on Reliable Distributed Systems SRDS-2000. IEEE, 144--153.

[23]

Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), Vol. 32, 2 (1985), 374--382.

Digital Library

[24]

Adam Gkagol, Damian Lesniak, Damian Straszak, and Michal Swiketek. 2019. Aleph: Efficient atomic broadcast in asynchronous networks with Byzantine nodes. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies. 214--228.

Digital Library

[25]

Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. 2019. Scalable Byzantine Reliable Broadcast. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[26]

Bruce M Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani. 2010. Fast asynchronous Byzantine agreement and leader election with full information. ACM Transactions on Algorithms (TALG), Vol. 6, 4 (2010), 1--28.

Digital Library

[27]

Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vocking. 2000. Randomized rumor spreading. In Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE, 565--574.

[28]

Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. 2020. Order-fairness for Byzantine consensus. In Annual International Cryptology Conference. Springer, 451--480.

Digital Library

[29]

Kim Potter Kihlstrom, Louise E Moser, and P Michael Melliar-Smith. 2001. The SecureRing group communication system. ACM Transactions on Information and System Security (TISSEC), Vol. 4, 4 (2001), 371--406.

Digital Library

[30]

Eleftherios Kokoris Kogias, Dahlia Malkhi, and Alexander Spiegelman. 2020. Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 1751--1767.

Digital Library

[31]

Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. 2007. Zyzzyva: speculative Byzantine fault tolerance. In ACM SIGOPS Operating Systems Review, Vol. 41. ACM, 45--58.

Digital Library

[32]

Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. 2020. FairLedger: A Fair Blockchain Protocol for Financial Institutions. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Schloss Dagstuhl-Leibniz-Zentrum fur Informatik.

[33]

Beno^it Libert, Marc Joye, and Moti Yung. 2016. Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares. Theoretical Computer Science, Vol. 645 (2016), 1--24.

Digital Library

[34]

Julian Loss and Tal Moran. 2018. Combining Asynchronous and Synchronous Byzantine Agreement: The Best of Both Worlds. IACR Cryptol. ePrint Arch., Vol. 2018 (2018), 235.

[35]

Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang. 2020. Dumbo-mvba: Optimal multi-valued validated asynchronous Byzantine agreement, revisited. In Proceedings of the 39th Symposium on Principles of Distributed Computing. 129--138.

Digital Library

[36]

Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016. The honey badger of BFT protocols. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 31--42.

Digital Library

[37]

Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. Technical Report.

[38]

Arpita Patra, Ashish Choudhury, and C Pandu Rangan. 2014. Asynchronous Byzantine agreement with optimal resilience. Distributed computing, Vol. 27, 2 (2014), 111--146.

[39]

Michael O Rabin. 1983. Randomized Byzantine generals. In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). IEEE, 403--409.

Digital Library

[40]

Michael K Reiter. 1994. Secure agreement protocols: Reliable and atomic group multicast in Rampart. In Proceedings of the 2nd ACM Conference on Computer and Communications Security. 68--80.

Digital Library

[41]

Adi Shamir. 1979. How to share a secret. Commun. ACM, Vol. 22, 11 (1979), 612--613.

Digital Library

[42]

Victor Shoup. 2000. Practical threshold signatures. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 207--220.

Digital Library

[43]

Maofan Yin, Dahlia Malkhi, MK Reiter and, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT consensus with linearity and responsiveness. In 38th ACM symposium on Principles of Distributed Computing (PODC'19).

Digital Library

Cited By

Zhang ZFeng KChen XLiu XSun H(2024)RHCA: Robust HCA via Consistent RevotingMathematics10.3390/math1204059312:4(593)Online publication date: 17-Feb-2024
https://doi.org/10.3390/math12040593
Wang HLi HFan PKang JDeng SZhu X(2024)PnV: An Efficient Parallel Consensus Protocol Integrating Proof and VotingApplied Sciences10.3390/app1408351014:8(3510)Online publication date: 22-Apr-2024
https://doi.org/10.3390/app14083510
Xu MGuo YLiu CHu QYu DXiong ZNiyato DCheng X(2024)Exploring Blockchain Technology through a Modular Lens: A SurveyACM Computing Surveys10.1145/365728856:9(1-39)Online publication date: 8-May-2024
https://dl.acm.org/doi/10.1145/3657288
Show More Cited By

Index Terms

All You Need is DAG
1. Security and privacy
  1. Cryptography
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network Conditions
Advances in Cryptology – ASIACRYPT 2021
Abstract
We study the problem of atomic broadcast—the underlying problem addressed by blockchain protocols—in the presence of a malicious adversary who corrupts some fraction of the n parties running the protocol. Existing protocols are either robust for ...
$_{}_{}$ $_{}_{}$ $_{}$ $_{}$ $_{}$ $_{}$
Handling message semantics with Generic Broadcast protocols

Message ordering is a fundamental abstraction in distributed systems. However, ordering guarantees are usually purely "syntactic," that is, message "semantics" is not taken into consideration despite the fact that in several cases semantic information ...
Low cost consensus-based Atomic Broadcast
PRDC '00: Proceedings of the 2000 Pacific Rim International Symposium on Dependable Computing

Atomic Broadcast (all processes deliver the same set of messages in the same order) is a very powerful communication primitive when one is interested in building fault-tolerant distributed systems. Moreover, it has been shown that Atomic Broadcast and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

July 2021

590 pages

ISBN:9781450385480

DOI:10.1145/3465084

General Chair:
Avery Miller
University of Manitoba, Canada
,
Program Chair:
Keren Censor-Hillel
Technion, Israel

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '21

Sponsor:

PODC '21: ACM Symposium on Principles of Distributed Computing

July 26 - 30, 2021

Virtual Event, Italy

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
854
Total Downloads

Downloads (Last 12 months)302
Downloads (Last 6 weeks)33

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang ZFeng KChen XLiu XSun H(2024)RHCA: Robust HCA via Consistent RevotingMathematics10.3390/math1204059312:4(593)Online publication date: 17-Feb-2024
https://doi.org/10.3390/math12040593
Wang HLi HFan PKang JDeng SZhu X(2024)PnV: An Efficient Parallel Consensus Protocol Integrating Proof and VotingApplied Sciences10.3390/app1408351014:8(3510)Online publication date: 22-Apr-2024
https://doi.org/10.3390/app14083510
Xu MGuo YLiu CHu QYu DXiong ZNiyato DCheng X(2024)Exploring Blockchain Technology through a Modular Lens: A SurveyACM Computing Surveys10.1145/365728856:9(1-39)Online publication date: 8-May-2024
https://dl.acm.org/doi/10.1145/3657288
Zhang GPan FMao YTijanic SDang’ana MMotepalli SZhang SJacobsen H(2024)Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus AlgorithmsACM Computing Surveys10.1145/363655356:5(1-41)Online publication date: 12-Jan-2024
https://dl.acm.org/doi/10.1145/3636553
Song MNguyen LKim SEom HSon YMencagli GDazzi PLowenthal DBadia R(2024)ScaleDFS: Accelerating Decentralized and Private File Sharing via Scaling Directed Acyclic Graph ProcessingProceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3625549.3658690(295-308)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3625549.3658690
Zhang SXiao JWu ECheng FLi BWang WJin H(2024)MorphDAG: A Workload-Aware Elastic DAG-Based BlockchainIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338274336:10(5249-5264)Online publication date: Oct-2024
https://doi.org/10.1109/TKDE.2024.3382743
Dai XZhang ZGuo ZDing CXiao JXie XHao RJin H(2024)Wahoo: A DAG-Based BFT Consensus With Low Latency and Low Communication OverheadIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340908219(7508-7522)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3409082
Guo HXu MZhang JLiu CRanjan RYu DCheng X(2024)BFT-DSN: A Byzantine Fault-Tolerant Decentralized Storage NetworkIEEE Transactions on Computers10.1109/TC.2024.336595373:5(1300-1312)Online publication date: 14-Feb-2024
https://dl.acm.org/doi/10.1109/TC.2024.3365953
Neu JSridhar SYang LTse D(2024)Optimal Flexible Consensus and its Application to Ethereum2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00135(3885-3903)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00135
Zhang YWang XHe X(2024)Nexus: Efficient and Conflict-Equivalent DAG-Based Permissioned Blockchain Sharding2024 IEEE/ACM 32nd International Symposium on Quality of Service (IWQoS)10.1109/IWQoS61813.2024.10682609(1-6)Online publication date: 19-Jun-2024
https://doi.org/10.1109/IWQoS61813.2024.10682609
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents