Search Results

Documents authored by Zanolini, Luca

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.17
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
DOI: 10.4230/LIPIcs.OPODIS.2022.19
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
DOI: 10.4230/LIPIcs.DISC.2021.44
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
DOI: 10.4230/LIPIcs.DISC.2021.51
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}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact