BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Christian Cachin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Recently, much work has been carried out to study simplicial interpretations of modal logic. While notions of (distributed) knowledge have been well investigated in this context, it has been open how to model belief in simplicial models. We introduce polychromatic simplicial complexes, which naturally impose a plausibility relation on states. From this, we can define various notions of belief.
A family of leaderless, decentralized consensus protocols, called Snow consensus was introduced in a recent whitepaper by Yin et al. These protocols address limitations of existing consensus methods, such as those using proof-of-work or quorums, by utilizing randomization and maintaining some level of resilience against Byzantine participants. Crucially, Snow consensus underpins the Avalanche blockchain, which provides a popular cryptocurrency and a platform for running smart contracts. Snow consensus algorithms are built on a natural, randomized routine, whereby participants continuously sample subsets of others and adopt an observed majority value until consensus is achieved. Additionally, Snow consensus defines conditions based on participants' local views and security parameters. These conditions indicate when a party can confidently finalize its local value, knowing it will be adopted by honest participants. Although Snow consensus algorithms can be formulated concisely, there is a complex interaction between randomization, adversarial influence, and security parameters, which requires a formal analysis of their security and liveness. Snow protocols form the foundation for Avalanche-type blockchains, and this work aims to increase our understanding of such protocols by providing insights into their liveness and safety characteristics. First, we analyze these Snow protocols in terms of latency and security. Second, we expose a design issue where the trade-off between these two is unfavorable. Third, we propose a modification of the original protocol where this trade-off is much more favorable.
Leader-based protocols for consensus, i.e., atomic broadcast, allow some processes to unilaterally affect the final order of transactions. This has become a problem for blockchain networks and decentralized finance because it facilitates front-running and other attacks. To address this, order fairness for payload messages has been introduced recently as a new safety property for atomic broadcast complementing traditional agreement and liveness. We relate order fairness to the standard validity notions for consensus protocols and highlight some limitations with the existing formalization. Based on this, we introduce a new differential order fairness property that fixes these issues. We also present the quick order-fair atomic broadcast protocol that guarantees payload message delivery in a differentially fair order and is much more efficient than existing order-fair consensus protocols. It works for asynchronous and for eventually synchronous networks with optimal resilience, tolerating corruptions of up to one third of the processes. Previous solutions required there to be less than one fourth of faults. Furthermore, our protocol incurs only quadratic cost, in terms of amortized message complexity per delivered payload.
Modern blockchains support a variety of distributed applications beyond cryptocurrencies, including smart contracts -- which let users execute arbitrary code in a distributed and decentralized fashion. Regardless of their intended application, blockchain platforms implicitly assume consensus for the correct execution of a smart contract, thus requiring that all transactions are totally ordered. It was only recently recognized that consensus is not necessary to prevent double-spending in a cryptocurrency (Guerraoui et al., PODC'19), contrary to common belief. This result suggests that current implementations may be sacrificing efficiency and scalability because they synchronize transactions much more tightly than actually needed. In this work, we study the synchronization requirements of Ethereum's ERC20 token contract, one of the most widely adopted smart contacts. Namely, we model a smart-contract token as a concurrent object and analyze its consensus number as a measure of synchronization power. We show that the richer set of methods supported by ERC20 tokens, compared to standard cryptocurrencies, results in strictly stronger synchronization requirements. More surprisingly, the synchronization power of ERC20 tokens depends on the object's state and can thus be modified by method invocations. To prove this result, we develop a dedicated framework to express how the object's state affects the needed synchronization level. Our findings indicate that ERC20 tokens, as well as other token standards, are more powerful and versatile than plain cryptocurrencies, and are subject to dynamic requirements. Developing specific synchronization protocols that exploit these dynamic requirements will pave the way towards more robust and scalable blockchain platforms.
Collecting anonymous opinions finds various applications ranging from simple whistleblowing, releasing secretive information, to complex forms of voting, where participants rank candidates by order of preferences. Unfortunately, as far as we know there is no efficient distributed solution to this problem. Previously, participants had to trust third parties, run expensive cryptographic protocols or sacrifice anonymity. In this paper, we propose a resilient-optimal solution to this problem called AVCP, which tolerates up to a third of Byzantine participants. AVCP combines traceable ring signatures to detect double votes with a reduction from vector consensus to binary consensus to ensure all valid votes are taken into account. We prove our algorithm correct and show that it preserves anonymity with at most a linear communication overhead and constant message overhead when compared to a recent consensus baseline. Finally, we demonstrate empirically that the protocol is practical by deploying it on 100 machines geo-distributed in 3 continents: America, Asia and Europe. Anonymous decisions are reached within 10 seconds with a conservative choice of traceable ring signatures.
Existing Byzantine fault-tolerant (BFT) consensus protocols address only threshold failures, where the participating nodes fail independently of each other, each one fails equally likely, and the protocol's guarantees follow from a simple bound on the number of faulty nodes. With the widespread deployment of Byzantine consensus in blockchains and distributed ledgers today, however, more sophisticated trust assumptions are needed. This paper presents the first implementation of BFT consensus with generalized quorums. It starts from a number of generalized trust structures motivated by practice and explores methods to specify and implement them efficiently. In particular, it expresses the trust assumption by a monotone Boolean formula (MBF) with threshold operators and by a monotone span program (MSP), a linear-algebraic model for computation. An implementation of HotStuff BFT consensus using these quorum systems is described as well and compared to the existing threshold model. Benchmarks with HotStuff running on up to 40 replicas demonstrate that the MBF specification incurs no significant slowdown, whereas the MSP expression affects latency and throughput noticeably due to the involved computations.
Cloud services have turned remote computation into a commodity and enable convenient online collaboration. However, they require that clients fully trust the service provider in terms of confidentiality, integrity, and availability. Towards reducing this dependency, this paper introduces a protocol for verification of integrity and consistency for cloud object storage (VICOS), which enables a group of mutually trusting clients to detect data-integrity and consistency violations for a cloud object-storage service. It aims at services where multiple clients cooperate on data stored remotely on a potentially misbehaving service. VICOS enforces the consistency notion of fork-linearizability, supports wait-free client semantics for most operations, and reduces the computation and communication overhead compared to previous protocols. VICOS is based in a generic way on any authenticated data structure. Moreover, its operations cover the hierarchical name space of a cloud object store, supporting a real-world interface and not only a simplistic abstraction. A prototype of VICOS that works with the key-value store interface of commodity cloud storage services has been implemented, and an evaluation demonstrates its advantage compared to existing systems.
Service replication distributes an application over many processes for tolerating faults, attacks, and misbehavior among a subset of the processes. The established state-machine replication paradigm inherently requires the application to be deterministic. This paper distinguishes three models for dealing with non-determinism in replicated services, where some processes are subject to faults and arbitrary behavior (so-called Byzantine faults): first, a modular approach that does not require any changes to the potentially non-deterministic application (and neither access to its internal data); second, a master-slave approach, in which ties are broken by a leader and the other processes validate the choices of the leader; and finally, a treatment of applications that use cryptography and secret keys. Cryptographic operations and secrets must be treated specially because they require strong randomness to satisfy their goals. The paper also introduces two new protocols. The first uses the modular approach for filtering out non-de\-ter\-min\-istic operations in an application. It ensures that all correct processes produce the same outputs and that their internal states do not diverge. The second protocol implements cryptographically secure randomness generation with a verifiable random function and is appropriate for certain security models. All protocols are described in a generic way and do not assume a particular implementation of the underlying consensus primitive.
Despite years of intensive research, Byzantine fault-tolerant (BFT) systems have not yet been adopted in practice. This is due to additional cost of BFT in terms of resources, protocol complexity and performance, compared with crash fault-tolerance (CFT). This overhead of BFT comes from the assumption of a powerful adversary that can fully control not only the Byzantine faulty machines, but at the same time also the message delivery schedule across the entire network, effectively inducing communication asynchrony and partitioning otherwise correct machines at will. To many practitioners, however, such strong attacks appear irrelevant. In this paper, we introduce cross fault tolerance or XFT, a novel approach to building reliable and secure distributed systems and apply it to the classical state-machine replication (SMR) problem. In short, an XFT SMR protocol provides the reliability guarantees of widely used asynchronous CFT SMR protocols such as Paxos and Raft, but also tolerates Byzantine faults in combination with network asynchrony, as long as a majority of replicas are correct and communicate synchronously. This allows the development of XFT systems at the price of CFT (already paid for in practice), yet with strictly stronger resilience than CFT --- sometimes even stronger than BFT itself. As a showcase for XFT, we present XPaxos, the first XFT SMR protocol, and deploy it in a geo-replicated setting. Although it offers much stronger resilience than CFT SMR at no extra resource cost, the performance of XPaxos matches that of the state-of-the-art CFT protocols.
The cost of Byzantine Fault Tolerant (BFT) storage is the main concern preventing its adoption in practice. This cost stems from the need to maintain at least 3t+1 replicas in different storage servers in the asynchronous model, so that t Byzantine replica faults can be tolerated. In this paper, we present MDStore, the first fully asynchronous read/write BFT storage protocol that reduces the number of data replicas to as few as 2t+1, maintaining 3t+1 replicas of metadata at (possibly) different servers. At the heart of MDStore store is its metadata service that is built upon a new abstraction we call timestamped storage. Timestamped storage both allows for conditional writes (facilitating the implementation of a metadata service) and has consensus number one (making it implementable wait-free in an asynchronous system despite faults). In addition to its low data replication factor, MDStore offers very strong guarantees implementing multi-writer multi-reader atomic wait-free semantics and tolerating any number of Byzantine readers and crash-faulty writers. We further show that MDStore data replication overhead is optimal; namely, we prove a lower bound of 2t+1 on the number of data replicas that applies even to crash-tolerant storage with a fault-free metadata service oracle. Finally, we prove that separating data from metadata for reducing the cost of BFT storage is not possible without cryptographic assumptions. However, our MDStore protocol uses only lightweight cryptographic hash functions.
Although many distributed storage protocols have been introduced, a solution that combines the strongest properties in terms of availability, consistency, fault-tolerance, storage complexity and the supported level of concurrency, has been elusive for a long time. Combining these properties is difficult, especially if the resulting solution is required to be efficient and incur low cost. We present AWE, the first erasure-coded distributed implementation of a multi-writer multi-reader read/write storage object that is, at the same time: (1) asynchronous, (2) wait-free, (3) atomic, (4) amnesic, (i.e., with data nodes storing a bounded number of values) and (5) Byzantine fault-tolerant (BFT) using the optimal number of nodes. Furthermore, AWE is efficient since it does not use public-key cryptography and requires data nodes that support only reads and writes, further reducing the cost of deployment and ownership of a distributed storage solution. Notably, AWE stores metadata separately from $k$-out-of-$n$ erasure-coded fragments. This enables AWE to be the first BFT protocol that uses as few as $2t+k$ data nodes to tolerate $t$ Byzantine nodes, for any $k \ge 1$.