Search Results

Documents authored by Vukolic, Marko

Document
DOI: 10.4230/LIPIcs.AFT.2023.5
Security Analysis of Filecoin’s Expected Consensus in the Byzantine vs Honest Model

Authors: Xuechao Wang, Sarah Azouvi, and Marko Vukolić

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

Abstract
Filecoin is the largest storage-based open-source blockchain, both by storage capacity (>11EiB) and market capitalization. This paper provides the first formal security analysis of Filecoin’s consensus (ordering) protocol, Expected Consensus (EC). Specifically, we show that EC is secure against an arbitrary adversary that controls a fraction β of the total storage for β m < 1- e^{-(1-β)m}, where m is a parameter that corresponds to the expected number of blocks per round, currently m = 5 in Filecoin. We then present an attack, the n-split attack, where an adversary splits the honest miners between multiple chains, and show that it is successful for β m ≥ 1- e^{-(1-β)m}, thus proving that β m = 1- e^{-(1-β)m} is the tight security threshold of EC. This corresponds roughly to an adversary with 20% of the total storage pledged to the chain. Finally, we propose two improvements to EC security that would increase this threshold. One of these two fixes is being implemented as a Filecoin Improvement Proposal (FIP).
Cite as

Xuechao Wang, Sarah Azouvi, and Marko Vukolić. Security Analysis of Filecoin’s Expected Consensus in the Byzantine vs Honest Model. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.AFT.2023.5,
  author =	{Wang, Xuechao and Azouvi, Sarah and Vukoli\'{c}, Marko},
  title =	{{Security Analysis of Filecoin’s Expected Consensus in the Byzantine vs Honest Model}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{5:1--5:21},
  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.5},
  URN =		{urn:nbn:de:0030-drops-191943},
  doi =		{10.4230/LIPIcs.AFT.2023.5},
  annote =	{Keywords: Decentralized storage, Consensus, Security analysis}
}
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
Keynote Talk
DOI: 10.4230/LIPIcs.DISC.2017.1
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
DOI: 10.4230/LIPIcs.OPODIS.2016.24
Non-Determinism in Byzantine Fault-Tolerant Replication

Authors: Christian Cachin, Simon Schubert, and Marko Vukolic

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

Abstract
Service replication distributes an application over many processes for tolerating faults, attacks, and misbehavior among a subset of the processes. With the recent interest in blockchain technologies, distributed execution of one logical application has become a prominent topic. 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, the modular case that does not require any changes to the potentially non-deterministic application (and neither access to its internal data); second, master-slave solutions, where ties are broken by a leader and the other processes validate the choices of the leader; and finally, 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. First, Protocol Sieve uses the modular approach and filters out non-deterministic operations in an application. It ensures that all correct processes produce the same outputs and that their internal states do not diverge. A second protocol, called Mastercrypt, implements cryptographically secure randomness generation with a verifiable random function and is appropriate for most situations in which cryptographic secrets are involved. All protocols are described in a generic way and do not assume a particular implementation of the underlying consensus primitive.
Cite as

Christian Cachin, Simon Schubert, and Marko Vukolic. Non-Determinism in Byzantine Fault-Tolerant Replication. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.OPODIS.2016.24,
  author =	{Cachin, Christian and Schubert, Simon and Vukolic, Marko},
  title =	{{Non-Determinism in Byzantine Fault-Tolerant Replication}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{24:1--24:16},
  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.24},
  URN =		{urn:nbn:de:0030-drops-70935},
  doi =		{10.4230/LIPIcs.OPODIS.2016.24},
  annote =	{Keywords: Blockchain, atomic broadcast, consensus, distributed cryptography, verifiable random functions}
}
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