Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases
This work addresses the problem of Sybil attack vulnerability in peer-to-peer databases for applications that can tolerate arbitrary Byzantine-faulty nodes, providing a new consistency model and algorithm.
This paper characterizes a category of database applications immune to Sybil attacks, which they call Byzantine Eventual Consistency (BEC). They introduce an algorithm based on Byzantine causal broadcast that guarantees BEC, proving its correctness and demonstrating near-optimal performance in a prototype.
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.