research-article

Open access

Making CRDTs Byzantine fault tolerant

Author:

Martin KleppmannAuthors Info & Claims

PaPoC '22: Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data

April 2022

Pages 8 - 15

https://doi.org/10.1145/3517209.3524042

Published: 05 April 2022 Publication History

Abstract

It is often claimed that Conflict-free Replicated Data Types (CRDTs) ensure consistency of replicated data in peer-to-peer systems. However, peer-to-peer systems usually consist of untrusted nodes that may deviate from the specified protocol (i.e. exhibit Byzantine faults), and most existing CRDT algorithms cannot guarantee consistency in the presence of such faults. This paper shows how to adapt existing non-Byzantine CRDT algorithms and make them Byzantine fault-tolerant. The proposed scheme can tolerate any number of Byzantine nodes (making it immune to Sybil attacks), guarantees Strong Eventual Consistency, and requires only modest changes to existing CRDT algorithms.

References

[1]

Paulo Sérgio Almeida, Ali Shoker, and Carlos Baquero. 2017. Delta state replicated data types. J. Parallel and Distrib. Comput. 111 (Aug. 2017), 162--173.

[2]

Peter Alvaro, Neil Conway, Joseph M. Hellerstein, and William R. Marczak. 2011. Consistency Analysis in Bloom: a CALM and Collected Approach. In 5th Biennial Conference on Innovative Data Systems Research (CIDR 2011).

[3]

Luc André, Stéphane Martin, Gérald Oster, and Claudia-Lavinia Ignat. 2013. Supporting adaptable granularity of changes for massive-scale collaborative editing. In 9th IEEE International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom 2013). ICST, 50--59.

[4]

Alex Auvolat and François Taïani. 2019. Merkle Search Trees: Efficient State-Based CRDTs in Open Networks. In 38th Symposium on Reliable Distributed Systems (SRDS 2019). IEEE, 221--230.

[5]

Leemon Baird. 2016. The Swirlds hashgraph consensus algorithm: Fair, fast, Byzantine fault tolerance. Technical Report TR-2016-01. Swirlds. https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf

[6]

Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis. 2019. SoK: Consensus in the Age of Blockchains. In 1st ACM Conference on Advances in Financial Technologies (AFT 2019). ACM, 183--198.

Digital Library

[7]

Juan Benet. 2014. IPFS - Content Addressed, Versioned, P2P File System. arXiv:1407.3561 [cs.NI] https://arxiv.org/abs/1407.3561

[8]

Alysson Bessani, João Sousa, and Eduardo E. P. Alchieri. 2014. State Machine Replication for the Masses with BFT-SMART. In 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2014). IEEE, 355--362.

Digital Library

[9]

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

Digital Library

[10]

John F. Buford and Heather Yu. 2010. Peer-to-Peer Networking and Applications: Synopsis and Research Directions. In Handbook of Peer-to-Peer Networking, Xuemin Shen, Heather Yu, John Buford, and Mursalin Akon (Eds.). Springer, 3--45.

[11]

Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. 2011. Introduction to Reliable and Secure Distributed Programming (second ed.). Springer.

[12]

Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001. Secure and Efficient Asynchronous Broadcast Protocols. In 21st Annual International Cryptology Conference (CRYPTO 2001). Springer, 524--541.

[13]

Scott Chacon and Ben Straub. 2014. Pro Git (second ed.). Apress. https://git-scm.com/book/en/v2

[14]

Hua Chai and Wenbing Zhao. 2014. Byzantine Fault Tolerance for Services with Commutative Operations. In 2014 IEEE International Conference on Services Computing (SCC 2014). IEEE, 219--226.

Digital Library

[15]

John R. Douceur. 2002. The Sybil Attack. In International Workshop on Peer-to-Peer Systems (IPTPS 2002). Springer, 251--260.

[16]

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the Presence of Partial Synchrony. J. ACM 35, 2 (April 1988), 288--323.

Digital Library

[17]

Victor B.F. Gomes, Martin Kleppmann, Dominic P. Mulligan, and Alastair R. Beresford. 2017. Verifying strong eventual consistency in distributed systems. Proceedings of the ACM on Programming Languages 1, OOPSLA (Oct. 2017).

Digital Library

[18]

Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh. 2021. Dynamic Byzantine Reliable Broadcast. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020, Vol. 184). Schloss Dagstuhl, 23:1--23:18.

[19]

Peter H. Hochschild, Paul Turner, Jeffrey C. Mogul, Rama Govindaraju, Parthasarathy Ranganathan, David E. Culler, and Amin Vahdat. 2021. Cores that don't count. In Workshop on Hot Topics in Operating Systems (HotOS 2021). ACM, 9--16.

Digital Library

[20]

Florian Jacob, Saskia Bayreuther, and Hannes Hartenstein. 2021. On Conflict-Free Replicated Data Types and Equivocation in Byzantine Setups. arXiv:2109.10554 [cs.DC] https://arxiv.org/abs/2109.10554

[21]

Florian Jacob, Carolin Beer, Norbert Henze, and Hannes Hartenstein. 2021. Analysis of the Matrix Event Graph Replicated Data Type. IEEE Access 9 (Feb. 2021), 28317--28333.

[22]

Brent Byunghoon Kang, Robert Wilensky, and John Kubiatowicz. 2003. The hash history approach for reconciling mutual inconsistency. In 23rd International Conference on Distributed Computing Systems (ICDCS 2003). IEEE, 670--677.

[23]

Martin Kleppmann and Heidi Howard. 2020. Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases. arXiv:2012.00472 [cs.DS] https://arxiv.org/abs/2012.00472

[24]

Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558--565.

Digital Library

[25]

Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems 4, 3 (July 1982), 382--401.

Digital Library

[26]

João Leitão, José Pereira, and Luís Rodrigues. 2009. Gossip-Based Broadcast. In Handbook of Peer-to-Peer Networking. Springer, 831--860.

[27]

Albert van der Linde, João Leitão, and Nuno Preguiça. 2020. Practical Client-side Replication: Weak Consistency Semantics for Insecure Settings. Proceedings of the VLDB Endowment 13, 11 (July 2020), 2590--2605.

Digital Library

[28]

Xiao Lv, Fazhi He, Weiwei Cai, and Yuan Cheng. 2016. An efficient collaborative editing algorithm supporting string-based operations. In 20th IEEE International Conference on Computer Supported Cooperative Work in Design (CSCWD 2016). IEEE, 45--50.

[29]

Ralph C. Merkle. 1987. A Digital Signature Based on a Conventional Encryption Function. In A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology (CRYPTO 1987). Springer, 369--378.

[30]

Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/bitcoin.pdf

[31]

Brice Nédelec, Pascal Molli, and Achour Mostefaoui. 2016. CRATE: Writing Stories Together with our Browsers. In 25th International World Wide Web Conference (WWW 2016). ACM, 231--234.

Digital Library

[32]

Petru Nicolaescu, Kevin Jahns, Michael Derntl, and Ralf Klamma. 2016. Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types. In 19th International Conference on Supporting Group Work (GROUP 2016). ACM, 39--49.

Digital Library

[33]

Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine. 2006. Data consistency for P2P collaborative editing. In ACM Conference on Computer Supported Cooperative Work (CSCW 2006). ACM, 259--268.

Digital Library

[34]

D. Stott Parker Jr., Gerald J Popek, Gerard Rudisin, Allen Stoughton, Bruce J. Walker, Evelyn Walton, Johanna M. Chow, David Edwards, Stephen Kiser, and Charles Kline. 1983. Detection of Mutual Inconsistency in Distributed Systems. IEEE Transactions on Software Engineering SE-9, 3 (May 1983), 240--247.

Digital Library

[35]

Johan Pouwelse, Paweł Garbacki, Dick Epema, and Henk Sips. 2005. The BitTorrent P2P File-Sharing System: Measurements and Analysis. In 4th International Workshop on Peer-to-Peer Systems (IPTPS 2005). 205--216.

Digital Library

[36]

Nuno Preguiça, Joan Manuel Marques, Marc Shapiro, and Mihai Letia. 2009. A Commutative Replicated Data Type for Cooperative Editing. In 29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009). IEEE, 395--403.

Digital Library

[37]

Protocol Labs. [n.d.]. IPLD. https://ipld.io/

[38]

Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, and Joonwon Lee. 2011. Replicated abstract data types: Building blocks for collaborative applications. J. Parallel and Distrib. Comput. 71, 3 (March 2011), 354--368.

Digital Library

[39]

Héctor Sanjuán, Samuli Pöyhtäri, Pedro Teixeira, and Ioannis Psaras. 2020. Merkle-CRDTs: Merkle-DAGs meet CRDTs. arXiv:2004.00107 [cs.NI] https://arxiv.org/abs/2004.00107

[40]

Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. Conflict-Free Replicated Data Types. In 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011). Springer, 386--400.

[41]

Ali Shoker, Houssam Yactine, and Carlos Baquero. 2017. As Secure as Possible Eventual Consistency: Work in Progress. In 3rd International Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC 2017). ACM, Article 5.

Digital Library

[42]

Albert van der Linde, Pedro Fouto, João Leitão, Nuno Preguiça, Santiago Castiñeira, and Annette Bieniusa. 2017. Legion: Enriching Internet Services with Peer-to-Peer Interactions. In 26th International Conference on World Wide Web (WWW 2017). ACM, 283--292.

Digital Library

[43]

Stéphane Weiss, Pascal Urso, and Pascal Molli. 2007. Wooki: A P2P Wiki-Based Collaborative Writing Tool. In 8th International Conference on Web Information Systems Engineering (WISE 2007). Springer, 503--512.

[44]

Stéphane Weiss, Pascal Urso, and Pascal Molli. 2009. Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks. In 29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009). IEEE, 404--412.

Digital Library

[45]

Houssam Yactine, Ali Shoker, and Georges Younes. 2021. ASPAS: As Secure as Possible Available Systems. In 21st IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems (DAIS 2021). Springer, 57--73.

Digital Library

[46]

Wenbing Zhao and Mamdouh Babi. 2013. Byzantine fault tolerant collaborative editing. In IET International Conference on Information and Communications Technologies (IETICT 2013). Institution of Engineering and Technology, 233--240.

[47]

Wenbing Zhao, Mamdouh Babi, William Yang, Xiong Luo, Yueqin Zhu, Jack Yang, Chaomin Luo, and Mary Yang. 2016. Byzantine Fault Tolerance for Collaborative Editing with Commutative Operations. In IEEE International Conference on Electro Information Technology (EIT 2016). IEEE, 246--251.

Cited By

Renaux TVan den Vonder SDe Meuter W(2023)Secure RDTs: Enforcing Access Control Policies for Offline Available JSON DataProceedings of the ACM on Programming Languages10.1145/36228027:OOPSLA2(146-172)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622802
Jannes KBeni ELagaisse BJoosen W(2023)BeauForT: Robust Byzantine Fault Tolerance for Client-Centric Mobile Web ApplicationsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.324196334:4(1241-1252)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3241963

Index Terms

Making CRDTs Byzantine fault tolerant
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
      1. Peer-to-peer architectures
2. Security and privacy
  1. Systems security
    1. Distributed systems security

Recommendations

Secure replication for client-centric data stores
DICG '22: Proceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good

Decentralized, peer-to-peer systems using Conflict-free Replicated Data Types (CRDTs) can offer a more privacy-friendly alternative to centralized solutions that are often used by Big Tech. However, traditional CRDTs assume that all replicas are trusted,...
Read More
Composing and decomposing op-based CRDTs with semidirect products

Operation-based Conflict-free Replicated Data Types (CRDTs) are eventually consistent replicated data types that automatically resolve conflicts between concurrent operations. Op-based CRDTs must be designed differently for each data type, and current ...
Read More
Improving the Reactivity of Pure Operation-Based CRDTs
PaPoC '21: Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data

Modern distributed applications increasingly replicate data to guarantee both high availability of the system and an optimal user experience. Conflict-Free Replicated Data Types (CRDTs) are a family of data types specially designed for highly available ...
Read More

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PaPoC '22: Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data

April 2022

64 pages

ISBN:9781450392563

DOI:10.1145/3517209

Program Chairs:
Adriana Szekeres
VMware Research
,
KC Sivaramakrishnan
Indian Institute of Technology, Madras, India

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 April 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

EuroSys '22

Sponsor:

SIGOPS

EuroSys '22: Seventeenth European Conference on Computer Systems

April 5 - 8, 2022

Rennes, France

Acceptance Rates

Overall Acceptance Rate 34 of 47 submissions, 72%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
724
Total Downloads

Downloads (Last 12 months)370
Downloads (Last 6 weeks)36

Other Metrics

View Author Metrics

Citations

Cited By

Renaux TVan den Vonder SDe Meuter W(2023)Secure RDTs: Enforcing Access Control Policies for Offline Available JSON DataProceedings of the ACM on Programming Languages10.1145/36228027:OOPSLA2(146-172)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622802
Jannes KBeni ELagaisse BJoosen W(2023)BeauForT: Robust Byzantine Fault Tolerance for Client-Centric Mobile Web ApplicationsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.324196334:4(1241-1252)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3241963

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents