2020/12/01 by Martin Kleppmann, Heidi Howard, Kleppmann, Martin +1 · 1 voice
Computer Science · #Cryptography and Data Security #Cryptography and Security (cs.CR) #Databases (cs.DB) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC) #cs.CR #cs.DB #cs.DC
paper · pdf · doi:10.48550/arxiv.2012.00472
arxiv created 2020/12/01 · openalex publication_date 2020/12/01 · arxiv published 2020/12/01 · arxiv updated 2020/12/02 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Sybil attacks, in which a large number of adversary-controlled nodes join a network, are a concern for many peer-to-peer database systems, necessitating expensive countermeasures such as proof-of-work. However, there is a category of database applications that are, by design, immune to Sybil attacks because they can tolerate arbitrary numbers of Byzantine-faulty nodes. In this paper, we characterize this category of applications using a consistency model we call Byzantine Eventual Consistency (BEC). We introduce an algorithm that guarantees BEC based on Byzantine causal broadcast, prove its correctness, and demonstrate near-optimal performance in a prototype implementation.