Logo des Repositoriums

On CRDTs in Byzantine Environments

Vorschaubild nicht verfügbar

Volltext URI






ISSN der Zeitschrift



Gesellschaft für Informatik, Bonn


Conflict-free Replicated Data Types (CRDTs) allow updates to be applied to different replicas independently and concurrently, without the need for a remote conflict resolution. Thus, they provide a building block for scalability and performance of fault-tolerant distributed systems. Currently, CRDTs are typically used in a crash fault setting for global scale, partition-tolerant, highly available databases or collaborative applications. In this paper, we explore the use of CRDTs in Byzantine environments. This exploration is inspired by the popular Matrix messaging system: as recently shown, the underlying Matrix Event Graph replicated data type represents a CRDT that can very well deal with Byzantine behavior. This “Byzantine Tolerance” is due to mechanisms inherent in CRDTs and in the hash-based directed acyclic graph (HashDAG) data structure used in Matrix. These mechanisms restrict Byzantine behavior. We, therefore, discuss Byzantine behavior in a context of CRDTs, and how the notion of Byzantine tolerance relates to equivocation. We show that a subclass of CRDTs is equivocation-tolerant, i.e., without equivocation detection, prevention or remediation, this subclass still fulfills the CRDT properties, which leads to Byzantine tolerance. We conjecture that an operation-based Byzantine-tolerant CRDT design supporting non-commutative operations needs to be based on a HashDAG data structure. We close the paper with thoughts on chances and limits of this data type.


Jacob, Florian; Bayreuther, Saskia; Hartenstein, Hannes (2022): On CRDTs in Byzantine Environments. GI SICHERHEIT 2022. DOI: 10.18420/sicherheit2022_07. Gesellschaft für Informatik, Bonn. PISSN: 1617-5468. ISBN: 978-3-88579-717-3. pp. 113-126. Session 2. Karlsruhe. 5.-8. April 2022