59 Search Results for "Cachin, Christian"


Volume

LIPIcs, Volume 46

19th International Conference on Principles of Distributed Systems (OPODIS 2015)

OPODIS 2015, December 14-17, 2015, Rennes, France

Editors: Emmanuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru

Document
Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks

Authors: Orestis Alpos, Ignacio Amores-Sesar, Christian Cachin, and Michelle Yeo

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead.

Cite as

Orestis Alpos, Ignacio Amores-Sesar, Christian Cachin, and Michelle Yeo. Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.OPODIS.2023.12,
  author =	{Alpos, Orestis and Amores-Sesar, Ignacio and Cachin, Christian and Yeo, Michelle},
  title =	{{Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.12},
  URN =		{urn:nbn:de:0030-drops-195029},
  doi =		{10.4230/LIPIcs.OPODIS.2023.12},
  annote =	{Keywords: Consensus, MEV, Byzantine behavior, Rational behavior}
}
Document
Pay Less for Your Privacy: Towards Cost-Effective On-Chain Mixers

Authors: Zhipeng Wang, Marko Cirkovic, Duc V. Le, William Knottenbelt, and Christian Cachin

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)


Abstract
On-chain mixers, such as Tornado Cash (TC), have become a popular privacy solution for many non-privacy-preserving blockchain users. These mixers enable users to deposit a fixed amount of coins and withdraw them to another address, while effectively reducing the linkability between these addresses and securely obscuring their transaction history. However, the high cost of interacting with existing on-chain mixer smart contracts prohibits standard users from using the mixer, mainly due to the use of computationally expensive cryptographic primitives. For instance, the deposit cost of TC on Ethereum is approximately 1.1M gas (i.e., 66 USD in June 2023), which is 53× higher than issuing a base transfer transaction. In this work, we introduce the Merkle Pyramid Builder approach, to incrementally build the Merkle tree in an on-chain mixer and update the tree per batch of deposits, which can therefore decrease the overall cost of using the mixer. Our evaluation results highlight the effectiveness of this approach, showcasing a significant reduction of up to 7× in the amortized cost of depositing compared to state-of-the-art on-chain mixers. Importantly, these improvements are achieved without compromising users' privacy. Furthermore, we propose the utilization of verifiable computations to shift the responsibility of Merkle tree updates from on-chain smart contracts to off-chain clients, which can further reduce deposit costs. Additionally, our analysis demonstrates that our designs ensure fairness by distributing Merkle tree update costs among clients over time.

Cite as

Zhipeng Wang, Marko Cirkovic, Duc V. Le, William Knottenbelt, and Christian Cachin. Pay Less for Your Privacy: Towards Cost-Effective On-Chain Mixers. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 16:1-16:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.AFT.2023.16,
  author =	{Wang, Zhipeng and Cirkovic, Marko and Le, Duc V. and Knottenbelt, William and Cachin, Christian},
  title =	{{Pay Less for Your Privacy: Towards Cost-Effective On-Chain Mixers}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{16:1--16:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.16},
  URN =		{urn:nbn:de:0030-drops-192050},
  doi =		{10.4230/LIPIcs.AFT.2023.16},
  annote =	{Keywords: Privacy, Blockchain, Mixers, Merkle Tree}
}
Document
Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast

Authors: Orestis Alpos, Christian Cachin, Simon Holmgaard Kamp, and Jesper Buus Nielsen

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)


Abstract
We present simple and practical protocols for generating randomness as used by asynchronous total-order broadcast. The protocols are secure in a proof-of-stake setting with dynamically changing stake. They can be plugged into existing protocols for asynchronous total-order broadcast and will turn these into asynchronous total-order broadcast with dynamic stake. Our contribution relies on two important techniques. The paper "Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography" [Cachin, Kursawe, and Shoup, PODC 2000] has influenced the design of practical total-order broadcast through its use of threshold cryptography. However, it needs a setup protocol to be efficient. In a proof-of-stake setting with dynamic stake this setup would have to be continually recomputed, making the protocol impractical. The work "Asynchronous Byzantine Agreement with Subquadratic Communication" [Blum, Katz, Liu-Zhang, and Loss, TCC 2020] showed how to use an initial setup for broadcast to asymptotically efficiently generate sub-sequent setups. The protocol, however, resorted to fully homomorphic encryption and was therefore not practically efficient. We adopt their approach to the proof-of-stake setting with dynamic stake, apply it to the Constantinople paper, and remove the need for fully homomorphic encryption. This results in simple and practical proof-of-stake protocols.

Cite as

Orestis Alpos, Christian Cachin, Simon Holmgaard Kamp, and Jesper Buus Nielsen. Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.AFT.2023.31,
  author =	{Alpos, Orestis and Cachin, Christian and Kamp, Simon Holmgaard and Nielsen, Jesper Buus},
  title =	{{Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.31},
  URN =		{urn:nbn:de:0030-drops-192203},
  doi =		{10.4230/LIPIcs.AFT.2023.31},
  annote =	{Keywords: Total-Order Broadcast, Atomic Broadcast, Proof of Stake, Random Beacon}
}
Document
Maximal Extractable Value (MEV) Protection on a DAG

Authors: Dahlia Malkhi and Pawel Szalachowski

Published in: OASIcs, Volume 110, 4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022)


Abstract
Many cryptocurrency platforms are vulnerable to Maximal Extractable Value (MEV) attacks [Daian et al., 2020], where a malicious consensus leader can inject transactions or change the order of user transactions to maximize its profit. A promising line of research in MEV mitigation is to enhance the Byzantine fault tolerance (BFT) consensus core of blockchains by new functionalities, like hiding transaction contents, such that malicious parties cannot analyze and exploit them until they are ordered. An orthogonal line of research demonstrates excellent performance for BFT protocols designed around Directed Acyclic Graphs (DAG). They provide high throughput by keeping high network utilization, decoupling transactions' dissemination from their metadata ordering, and encoding consensus logic efficiently over a DAG representing a causal ordering of disseminated messages. This paper explains how to combine these two advances. It introduces a DAG-based protocol called Fino, that integrates MEV-resistance features into DAG-based BFT without delaying the steady spreading of transactions by the DAG transport and with zero message overhead. The scheme operates without complex secret share verifiability or recoverability, and avoids costly threshold encryption.

Cite as

Dahlia Malkhi and Pawel Szalachowski. Maximal Extractable Value (MEV) Protection on a DAG. In 4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022). Open Access Series in Informatics (OASIcs), Volume 110, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{malkhi_et_al:OASIcs.Tokenomics.2022.6,
  author =	{Malkhi, Dahlia and Szalachowski, Pawel},
  title =	{{Maximal Extractable Value (MEV) Protection on a DAG}},
  booktitle =	{4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022)},
  pages =	{6:1--6:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-274-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{110},
  editor =	{Amoussou-Guenou, Yackolley and Kiayias, Aggelos and Verdier, Marianne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2022.6},
  URN =		{urn:nbn:de:0030-drops-184231},
  doi =		{10.4230/OASIcs.Tokenomics.2022.6},
  annote =	{Keywords: DAG, MEV, consensus, BFT}
}
Document
When Is Spring Coming? A Security Analysis of Avalanche Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Avalanche is a blockchain consensus protocol with exceptionally low latency and high throughput. This has swiftly established the corresponding token as a top-tier cryptocurrency. Avalanche achieves such remarkable metrics by substituting proof of work with a random sampling mechanism. The protocol also differs from Bitcoin, Ethereum, and many others by forming a directed acyclic graph (DAG) instead of a chain. It does not totally order all transactions, establishes a partial order among them, and accepts transactions in the DAG that satisfy specific properties. Such parallelism is widely regarded as a technique that increases the efficiency of consensus. Despite its success, Avalanche consensus lacks a complete abstract specification and a matching formal analysis. To address this drawback, this work provides first a detailed formulation of Avalanche through pseudocode. This includes features that are omitted from the original whitepaper or are only vaguely explained in the documentation. Second, the paper gives an analysis of the formal properties fulfilled by Avalanche in the sense of a generic broadcast protocol that only orders related transactions. Last but not least, the analysis reveals a vulnerability that affects the liveness of the protocol. A possible solution that addresses the problem is also proposed.

Cite as

Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi. When Is Spring Coming? A Security Analysis of Avalanche Consensus. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2022.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Tedeschi, Enrico},
  title =	{{When Is Spring Coming? A Security Analysis of Avalanche Consensus}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.10},
  URN =		{urn:nbn:de:0030-drops-176307},
  doi =		{10.4230/LIPIcs.OPODIS.2022.10},
  annote =	{Keywords: Avalanche, security analysis, generic broadcast}
}
Document
Quorum Systems in Permissionless Networks

Authors: Christian Cachin, Giuliano Losa, and Luca Zanolini

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Fail-prone systems, and their quorum systems, are useful tools for the design of distributed algorithms. However, fail-prone systems as studied so far require every process to know the full system membership in order to guarantee safety through globally intersecting quorums. Thus, they are of little help in an open, permissionless setting, where such knowledge may not be available. We propose to generalize the theory of fail-prone systems to make it applicable to permissionless systems. We do so by enabling processes not only to make assumptions about failures, but also to make assumptions about the assumptions of other processes. Thus, by transitivity, processes that do not even know of any common process may nevertheless have intersecting quorums and solve, for example, reliable broadcast. Our model generalizes existing models such as the classic fail-prone system model [Malkhi and Reiter, 1998] and the asymmetric fail-prone system model [Cachin and Tackmann, OPODIS 2019]. Moreover, it gives a characterization with standard formalism of the model used by the Stellar blockchain.

Cite as

Christian Cachin, Giuliano Losa, and Luca Zanolini. Quorum Systems in Permissionless Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.OPODIS.2022.17,
  author =	{Cachin, Christian and Losa, Giuliano and Zanolini, Luca},
  title =	{{Quorum Systems in Permissionless Networks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{17:1--17:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.17},
  URN =		{urn:nbn:de:0030-drops-176379},
  doi =		{10.4230/LIPIcs.OPODIS.2022.17},
  annote =	{Keywords: Permissionless systems, fail-prone system, quorum system}
}
Document
Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast

Authors: Sarah Azouvi, Christian Cachin, Duc V. Le, Marko Vukolić, and Luca Zanolini

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Blockchain protocols implement total-order broadcast in a permissionless setting, where processes can freely join and leave. In such a setting, to safeguard against Sybil attacks, correct processes rely on cryptographic proofs tied to a particular type of resource to make them eligible to order transactions. For example, in the case of Proof-of-Work (PoW), this resource is computation, and the proof is a solution to a computationally hard puzzle. Conversely, in Proof-of-Stake (PoS), the resource corresponds to the number of coins that every process in the system owns, and a secure lottery selects a process for participation proportionally to its coin holdings. Although many resource-based blockchain protocols are formally proven secure in the literature, the existing security proofs fail to demonstrate why particular types of resources cause the blockchain protocols to be vulnerable to distinct classes of attacks. For instance, PoS systems are more vulnerable to long-range attacks, where an adversary corrupts past processes to re-write the history, than PoW and Proof-of-Storage systems. Proof-of-Storage-based and PoS-based protocols are both more susceptible to private double-spending attacks than PoW-based protocols; in this case, an adversary mines its chain in secret without sharing its blocks with the rest of the processes until the end of the attack. In this paper, we formally characterize the properties of resources through an abstraction called resource allocator and give a framework for understanding longest-chain consensus protocols based on different underlying resources. In addition, we use this resource allocator to demonstrate security trade-offs between various resources focusing on well-known attacks (e.g., the long-range attack and nothing-at-stake attacks).

Cite as

Sarah Azouvi, Christian Cachin, Duc V. Le, Marko Vukolić, and Luca Zanolini. Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{azouvi_et_al:LIPIcs.OPODIS.2022.19,
  author =	{Azouvi, Sarah and Cachin, Christian and Le, Duc V. and Vukoli\'{c}, Marko and Zanolini, Luca},
  title =	{{Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{19:1--19:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.19},
  URN =		{urn:nbn:de:0030-drops-176398},
  doi =		{10.4230/LIPIcs.OPODIS.2022.19},
  annote =	{Keywords: blockchain, consensus, resource, broadcast}
}
Document
Brief Announcement
Brief Announcement: How to Trust Strangers - Composition of Byzantine Quorum Systems

Authors: Orestis Alpos, Christian Cachin, and Luca Zanolini

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


Abstract
Trust is the basis of any distributed, fault-tolerant, or secure system. A trust assumption specifies the failures that a system, such as a blockchain network, can tolerate and determines the conditions under which it operates correctly. In systems subject to Byzantine faults, the trust assumption is usually specified through sets of processes that may fail together. Trust has traditionally been symmetric, such that all processes in the system adhere to the same, global assumption about potential faults. Recently, asymmetric trust models have also been considered, especially in the context of blockchains, where every participant is free to choose who to trust. In both cases, it is an open question how to compose trust assumptions. Consider two or more systems, run by different and possibly disjoint sets of participants, with different assumptions about faults: how can they work together? This work answers this question for the first time and offers composition rules for symmetric and for asymmetric quorum systems. These rules are static and do not require interaction or agreement on the new trust assumption among the participants. Moreover, they ensure that if the original systems allow for running a particular protocol (guaranteeing consistency and availability), then so will the joint system. At the same time, the composed system tolerates as many faults as possible, subject to the underlying consistency and availability properties. Reaching consensus with asymmetric trust in the model of personal Byzantine quorum systems (Losa et al., DISC 2019) was shown to be impossible, if the trust assumptions of the processes diverge from each other. With asymmetric quorum systems, and by applying our composition rule, we show how consensus is actually possible, even with the combination of disjoint sets of processes.

Cite as

Orestis Alpos, Christian Cachin, and Luca Zanolini. Brief Announcement: How to Trust Strangers - Composition of Byzantine Quorum Systems. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 44:1-44:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.DISC.2021.44,
  author =	{Alpos, Orestis and Cachin, Christian and Zanolini, Luca},
  title =	{{Brief Announcement: How to Trust Strangers - Composition of Byzantine Quorum Systems}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{44:1--44:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.44},
  URN =		{urn:nbn:de:0030-drops-148468},
  doi =		{10.4230/LIPIcs.DISC.2021.44},
  annote =	{Keywords: Byzantine quorum systems, composition of quorum systems, trust models, asymmetric trust}
}
Document
Brief Announcement
Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus

Authors: Christian Cachin and Luca Zanolini

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


Abstract
Among asynchronous, randomized, and signature-free implementations of consensus, the protocols of Mostéfaoui et al. (PODC 2014 and JACM 2015) represent a landmark result, which has been extended later and taken up in practical systems. The protocols achieve optimal resilience and take, in expectation, only a constant expected number of rounds and have quadratic message complexity. Randomization is provided through a common-coin primitive. However, the first version of this simple and appealing protocol suffers from a little-known liveness issue due to asynchrony. The JACM 2015 version avoids the problem, but is considerably more complex. This work revisits the original protocol of PODC 2014 and points out in detail why it may not progress. A fix for the protocol is presented, which does not affect any of its properties, but lets it regain the original simplicity in asynchronous networks enhanced with a common-coin protocol.

Cite as

Christian Cachin and Luca Zanolini. Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 51:1-51:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.DISC.2021.51,
  author =	{Cachin, Christian and Zanolini, Luca},
  title =	{{Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{51:1--51:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.51},
  URN =		{urn:nbn:de:0030-drops-148535},
  doi =		{10.4230/LIPIcs.DISC.2021.51},
  annote =	{Keywords: Randomized consensus}
}
Document
Security Analysis of Ripple Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


Abstract
The Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has one of the highest cryptocurrency market capitalizations. The Ripple consensus protocol powers this network and is generally considered to a Byzantine fault-tolerant agreement protocol, which can reach consensus in the presence of faulty or malicious nodes. In contrast to traditional Byzantine agreement protocols, there is no global knowledge of all participating nodes in Ripple consensus; instead, each node declares a list of other nodes that it trusts and from which it considers votes. Previous work has brought up concerns about the liveness and safety of the consensus protocol under the general assumptions stated initially by Ripple, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper closes this gap and makes two contributions. It first provides a detailed, abstract description of the protocol, which has been derived from the source code. Second, the paper points out that the abstract protocol may violate safety and liveness in several simple executions under relatively benign network assumptions.

Cite as

Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić. Security Analysis of Ripple Consensus. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2020.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Mi\'{c}i\'{c}, Jovana},
  title =	{{Security Analysis of Ripple Consensus}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.10},
  URN =		{urn:nbn:de:0030-drops-134956},
  doi =		{10.4230/LIPIcs.OPODIS.2020.10},
  annote =	{Keywords: Ripple, Blockchain, Quorums, Consensus}
}
Document
Asymmetric Distributed Trust

Authors: Christian Cachin and Björn Tackmann

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)


Abstract
Quorum systems are a key abstraction in distributed fault-tolerant computing for capturing trust assumptions. They can be found at the core of many algorithms for implementing reliable broadcasts, shared memory, consensus and other problems. This paper introduces asymmetric Byzantine quorum systems that model subjective trust. Every process is free to choose which combinations of other processes it trusts and which ones it considers faulty. Asymmetric quorum systems strictly generalize standard Byzantine quorum systems, which have only one global trust assumption for all processes. This work also presents protocols that implement abstractions of shared memory and broadcast primitives with processes prone to Byzantine faults and asymmetric trust. The model and protocols pave the way for realizing more elaborate algorithms with asymmetric trust.

Cite as

Christian Cachin and Björn Tackmann. Asymmetric Distributed Trust. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.OPODIS.2019.7,
  author =	{Cachin, Christian and Tackmann, Bj\"{o}rn},
  title =	{{Asymmetric Distributed Trust}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.7},
  URN =		{urn:nbn:de:0030-drops-117933},
  doi =		{10.4230/LIPIcs.OPODIS.2019.7},
  annote =	{Keywords: Quorums, consensus, distributed trust, blockchains, cryptocurrencies}
}
Document
Brief Announcement
Brief Announcement: Asymmetric Distributed Trust

Authors: Christian Cachin and Björn Tackmann

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


Abstract
Quorum systems are a key abstraction in distributed fault-tolerant computing for capturing trust assumptions. They can be found at the core of many algorithms for implementing reliable broadcasts, shared memory, consensus and other problems. This paper introduces asymmetric Byzantine quorum systems that model subjective trust. Every process is free to choose which combinations of other processes it trusts and which ones it considers faulty. Asymmetric quorum systems strictly generalize standard Byzantine quorum systems, which have only one global trust assumption for all processes. This work also presents protocols that implement abstractions of shared memory and broadcast primitives with processes prone to Byzantine faults and asymmetric trust. The model and protocols pave the way for realizing more elaborate algorithms with asymmetric trust.

Cite as

Christian Cachin and Björn Tackmann. Brief Announcement: Asymmetric Distributed Trust. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 39:1-39:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.DISC.2019.39,
  author =	{Cachin, Christian and Tackmann, Bj\"{o}rn},
  title =	{{Brief Announcement: Asymmetric Distributed Trust}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{39:1--39:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.39},
  URN =		{urn:nbn:de:0030-drops-113460},
  doi =		{10.4230/LIPIcs.DISC.2019.39},
  annote =	{Keywords: Quorums, consensus, distributed trust, blockchains, cryptocurrencies}
}
Document
Keynote Talk
Blockchain Consensus Protocols in the Wild (Keynote Talk)

Authors: Christian Cachin and Marko Vukolic

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)


Abstract
A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks.

Cite as

Christian Cachin and Marko Vukolic. Blockchain Consensus Protocols in the Wild (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.DISC.2017.1,
  author =	{Cachin, Christian and Vukolic, Marko},
  title =	{{Blockchain Consensus Protocols in the Wild}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.1},
  URN =		{urn:nbn:de:0030-drops-80160},
  doi =		{10.4230/LIPIcs.DISC.2017.1},
  annote =	{Keywords: Permissioned blockchains, consensus, Byzantine fault-tolerance, snake oil, protocol analysis}
}
Document
Keynote Abstract
Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract)

Authors: Christian Cachin

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)


Abstract
A blockchain is a public ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Distributed protocols tolerating faults and adversarial attacks, coupled with cryptographic tools are needed for this. The recent interest in blockchains has revived research on consensus protocols, ranging from the proof-of-work method in Bitcoin's "mining" protocol to classical Byzantine agreement. Going far beyond its use in cryptocurrencies, blockchain is today viewed as a promising technology to simplify trusted exchanges of data and goods among companies. In this context, the Hyperledger Project has been established in early 2016 as an industry-wide collaborative effort to develop an open-source blockchain. This talk will present an overview of blockchain concepts, cryptographic building blocks and consensus mechanisms. It will also introduce Hyperledger Fabric, an implementation of blockchain technology intended for enterprise applications. Being one of the key partners in the Hyperledger Project, IBM is actively involved in the development of this blockchain platform.

Cite as

Christian Cachin. Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{cachin:LIPIcs.OPODIS.2016.2,
  author =	{Cachin, Christian},
  title =	{{Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.2},
  URN =		{urn:nbn:de:0030-drops-70719},
  doi =		{10.4230/LIPIcs.OPODIS.2016.2},
  annote =	{Keywords: consensus, cryptographic, distributed protocols}
}
  • Refine by Author
  • 18 Cachin, Christian
  • 4 Zanolini, Luca
  • 3 Alpos, Orestis
  • 3 Amores-Sesar, Ignacio
  • 3 Keidar, Idit
  • Show More...

  • Refine by Classification
  • 8 Software and its engineering → Distributed systems organizing principles
  • 8 Theory of computation → Cryptographic protocols
  • 2 Security and privacy → Distributed systems security
  • 1 Security and privacy → Pseudonymity, anonymity and untraceability
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 9 consensus
  • 5 Fault-tolerance
  • 5 distributed computing
  • 4 Consensus
  • 3 Blockchain
  • Show More...

  • Refine by Type
  • 58 document
  • 1 volume

  • Refine by Publication Year
  • 39 2016
  • 6 2023
  • 5 2007
  • 3 2017
  • 3 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail