DROPS

Document

DOI: 10.4230/LIPIcs.AFT.2023.10

FairPoS: Input Fairness in Permissionless Consensus

Authors: James Hsin-yu Chiang, Bernardo David, Ittay Eyal, and Tiantian Gong

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

Abstract

In permissionless consensus, the ordering of transactions or inputs in each block is freely determined by an anonymously elected block leader. A rational block leader will choose an ordering of inputs that maximizes financial gain; the emergence of automatic market makers in decentralized finance enables the block leader to front-run honest trade orders by injecting its own inputs prior to and after honest trades. Front-running is rampant in decentralized finance and reduces the utility of the system by extracting financial value from honest trades and increasing demand for block-space. Current proposals to prevent input order attacks by encrypting user inputs are not permissionless, as they rely on small static committees to perform distributed key generation and threshold decryption. Such committees require party authentication, knowledge of the number of participating parties or do not permit player replaceability and are therefore not permissionless. Moreover, alternative solutions based on sequencing inputs in order of their arrival cannot prevent front-running in an unauthenticated peer-2-peer network where message arrival is adversarially controlled. We present FairPoS, the first consensus protocol to achieve input fairness in the permissionless setting with security against adaptive adversaries in semi-synchronous networks. In FairPoS, the adversary cannot learn the plaintext of any client input before it is included in a block in the chain’s common-prefix. Thus, input ordering attacks that depend on observing pending client inputs in the clear are no longer possible. In FairPoS, this is achieved via Delay Encryption (DeFeo et al., EUROCRYPT 2021), a recent cryptographic primitive related to time-lock puzzles, allowing all client inputs in a given round to be encrypted under a key that can only be extracted after enough time has elapsed. In contrast to alternative approaches, the key extraction task in delay encryption can, in principle, be performed by any party in the permissionless setting and requires no distribution of secret key material amongst authenticated parties. However, key extraction requires highly specialized hardware in practice. Thus, FairPoS requires resource-rich staking parties to insert extracted keys into blocks, enabling light-clients to decrypt past inputs and relieving parties who join the execution from decrypting all inputs in the entire chain history. Realizing this in proof-of-stake is non-trivial; naive application of key extraction to proof-of-stake can result in chain stalls lasting the entire key extraction period. We overcome this challenge with a novel key extraction protocol, which tolerates adversarial delays in block delivery intended to prevent key extraction from completing on schedule. Critically, this also enables the adoption of a new longest-extendable-chain rule which allows FairPoS to achieve the same guarantees as Ouroborous Praos against an adaptive adversary.

Cite as

James Hsin-yu Chiang, Bernardo David, Ittay Eyal, and Tiantian Gong. FairPoS: Input Fairness in Permissionless Consensus. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chiang_et_al:LIPIcs.AFT.2023.10,
  author =	{Chiang, James Hsin-yu and David, Bernardo and Eyal, Ittay and Gong, Tiantian},
  title =	{{FairPoS: Input Fairness in Permissionless Consensus}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{10:1--10:23},
  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.10},
  URN =		{urn:nbn:de:0030-drops-191990},
  doi =		{10.4230/LIPIcs.AFT.2023.10},
  annote =	{Keywords: Front-running, Delay Encryption, Proof-of-Stake, Blockchain}
}

Document

DOI: 10.4230/LIPIcs.DISC.2023.1

Colordag: An Incentive-Compatible Blockchain

Authors: Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

We present Colordag, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than 1/2 of the mining power. We prove the correctness of Colordag even if there is an extremely powerful adversary who knows future actions of the scheduler: specifically, when agents will generate blocks and when messages will arrive. The state-of-the-art protocol, Fruitchain, is an ε-Nash equilibrium as long as all miners have less than 1/2 of the mining power. However, there is a simple deviation that guarantees that deviators are never worse off than they would be by following Fruitchain, and can sometimes do better. Thus, agents are motivated to deviate. Colordag implements a solution concept that we call ε-sure Nash equilibrium and does not suffer from this problem. Because it is an ε-sure Nash equilibrium, Colordag is an ε-Nash equilibrium and with probability 1-ε is a best response.

Cite as

Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern. Colordag: An Incentive-Compatible Blockchain. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2023.1,
  author =	{Abraham, Ittai and Dolev, Danny and Eyal, Ittay and Halpern, Joseph Y.},
  title =	{{Colordag: An Incentive-Compatible Blockchain}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.1},
  URN =		{urn:nbn:de:0030-drops-191272},
  doi =		{10.4230/LIPIcs.DISC.2023.1},
  annote =	{Keywords: Game theory, incentives, blockchain}
}

Document

DOI: 10.4230/LIPIcs.DISC.2023.31

Gorilla: Safe Permissionless Byzantine Consensus

Authors: Youer Pu, Ali Farahbakhsh, Lorenzo Alvisi, and Ittay Eyal

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

Nakamoto’s consensus protocol works in a permissionless model and tolerates Byzantine failures, but only offers probabilistic agreement. Recently, the Sandglass protocol has shown such weaker guarantees are not a necessary consequence of a permissionless model; yet, Sandglass only tolerates benign failures, and operates in an unconventional partially synchronous model. We present Gorilla Sandglass, the first Byzantine tolerant consensus protocol to guarantee, in the same synchronous model adopted by Nakamoto, deterministic agreement and termination with probability 1 in a permissionless setting. We prove the correctness of Gorilla by mapping executions that would violate agreement or termination in Gorilla to executions in Sandglass, where we know such violations are impossible. Establishing termination proves particularly interesting, as the mapping requires reasoning about infinite executions and their probabilities.

Cite as

Youer Pu, Ali Farahbakhsh, Lorenzo Alvisi, and Ittay Eyal. Gorilla: Safe Permissionless Byzantine Consensus. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{pu_et_al:LIPIcs.DISC.2023.31,
  author =	{Pu, Youer and Farahbakhsh, Ali and Alvisi, Lorenzo and Eyal, Ittay},
  title =	{{Gorilla: Safe Permissionless Byzantine Consensus}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.31},
  URN =		{urn:nbn:de:0030-drops-191579},
  doi =		{10.4230/LIPIcs.DISC.2023.31},
  annote =	{Keywords: Consensus, Permissionless, Blockchains, Byzantine fault tolerance, Deterministic Safety}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.33

Safe Permissionless Consensus

Authors: Youer Pu, Lorenzo Alvisi, and Ittay Eyal

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

Nakamoto’s consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This paper shows that, at least in a benign failure model, it is not. It presents Sandglass, the first permissionless consensus algorithm that guarantees deterministic agreement and termination with probability 1 under general omission failures. Like Nakamoto, Sandglass adopts a hybrid synchronous communication model, where, at all times, a majority of nodes (though their number is unknown) are correct and synchronously connected, and allows nodes to join and leave at any time.

Cite as

Youer Pu, Lorenzo Alvisi, and Ittay Eyal. Safe Permissionless Consensus. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{pu_et_al:LIPIcs.DISC.2022.33,
  author =	{Pu, Youer and Alvisi, Lorenzo and Eyal, Ittay},
  title =	{{Safe Permissionless Consensus}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.33},
  URN =		{urn:nbn:de:0030-drops-172246},
  doi =		{10.4230/LIPIcs.DISC.2022.33},
  annote =	{Keywords: Consensus, Permissionless, Nakamoto, Deterministic Safety}
}

Document

DOI: 10.4230/OASIcs.Tokenomics.2021.3

Tuning PoW with Hybrid Expenditure

Authors: Itay Tsabary, Alexander Spiegelman, and Ittay Eyal

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract

Proof of Work (PoW) is a Sybil-deterrence security mechanism. It introduces an external cost to system participation by requiring computational effort to perform actions. However, since its inception, a central challenge was to tune this cost. Initial designs for deterring spam email and DoS attacks applied overhead equally to honest participants and attackers. Requiring too little effort does not deter attacks, whereas too much encumbers honest participation. This might be the reason it was never widely adopted. Nakamoto overcame this trade-off in Bitcoin by distinguishing desired from malicious behavior and introducing internal rewards for the former. This mechanism gained popularity in securing permissionless cryptocurrencies, using virtual internally-minted tokens for rewards. However, in existing blockchain protocols the internal rewards directly compensate users for (almost) the same value of external expenses. Thus, as the token value soars, so does the PoW expenditure. Bitcoin PoW, for example, already expends as much electricity as Colombia or Switzerland. This amount of resource-guzzling is unsustainable, and hinders even wider adoption of these systems. As such, a prominent alternative named Proof of Stake (PoS) replaces the expenditure requirement with token possession. However, PoS is shun by many cryptocurrency projects, as it is only secure under qualitatively-different assumptions, and the resultant systems are not permissionless. In this work we present Hybrid Expenditure Blockchain (HEB), a novel PoW mechanism. HEB is a generalization of Nakamoto’s protocol that enables tuning the external expenditure by introducing a complementary internal-expenditure mechanism. Thus, for the first time, HEB decouples external expenditure from the reward value. We show a practical parameter choice by which HEB requires significantly less external consumption compare to Nakamoto’s protocol, its resilience against rational attackers is similar, and it retains the decentralized and permissionless nature of the system. Taking the Bitcoin ecosystem as an example, HEB cuts the electricity consumption by half.

Cite as

Itay Tsabary, Alexander Spiegelman, and Ittay Eyal. Tuning PoW with Hybrid Expenditure. In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{tsabary_et_al:OASIcs.Tokenomics.2021.3,
  author =	{Tsabary, Itay and Spiegelman, Alexander and Eyal, Ittay},
  title =	{{Tuning PoW with Hybrid Expenditure}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{3:1--3:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.3},
  URN =		{urn:nbn:de:0030-drops-159008},
  doi =		{10.4230/OASIcs.Tokenomics.2021.3},
  annote =	{Keywords: Blockchain, Proof of work, Cryptocurrency, Environmental impact}
}

Document

DOI: 10.4230/OASIcs.Tokenomics.2021.4

On Cryptocurrency Wallet Design

Authors: Ittay Eyal

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract

The security of cryptocurrency and decentralized blockchain-maintained assets relies on their owners safeguarding secrets, typically cryptographic keys. This applies equally to individuals keeping daily-spending amounts and to large asset management companies. Loss of keys and attackers gaining control of keys resulted in numerous losses of funds. The security of individual keys was widely studied with practical solutions available, from mnemonic phrases to dedicated hardware. There are also techniques for securing funds by requiring combinations of multiple keys. However, to the best of our knowledge, a crucial question was never addressed: How is wallet security affected by the number of keys, their types, and how they are combined? This is the focus of this work. We present a model where each key has certain probabilities for being safe, lost, leaked, or stolen (available only to an attacker). The number of possible wallets for a given number of keys is the Dedekind number, prohibiting an exhaustive search with many keys. Nonetheless, we bound optimal-wallet failure probabilities with an evolutionary algorithm. We evaluate the security (complement of failure probability) of wallets based on the number and types of keys used. Our analysis covers a wide range of settings and reveals several surprises. The failure probability general trend drops exponentially with the number of keys, but has a strong dependency on its parity. In many cases, but not always, heterogeneous keys (not all with the same fault probabilities) allow for superior wallets than homogeneous keys. Nonetheless, in the case of 3 keys, the common practice of requiring any pair is optimal in many settings. Our formulation of the problem and initial results reveal several open questions, from user studies of key fault probabilities to finding optimal wallets with very large numbers of keys. But they also have an immediate practical outcome, informing cryptocurrency users on optimal wallet design.

Cite as

Ittay Eyal. On Cryptocurrency Wallet Design. In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eyal:OASIcs.Tokenomics.2021.4,
  author =	{Eyal, Ittay},
  title =	{{On Cryptocurrency Wallet Design}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{4:1--4:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.4},
  URN =		{urn:nbn:de:0030-drops-159012},
  doi =		{10.4230/OASIcs.Tokenomics.2021.4},
  annote =	{Keywords: cryptocurrency, wallet, key-management, authentication}
}

Document

DOI: 10.4230/DagRep.8.11.21

Blockchain Security at Scale (Dagstuhl Seminar 18461)

Authors: Rainer Böhme, Joseph Bonneau, and Ittay Eyal

Published in: Dagstuhl Reports, Volume 8, Issue 11 (2019)

Abstract

38 researchers affiliated with over 25 different institutions in 7 countries met during Dagstuhl Seminar 18461 for discussing open problems regarding "Blockchain Security at Scale." The seminar was split into eight blocks of two presentations each. The mode for each talk was 15 minutes of blackboard-only presentation followed by 30 minutes of discussion. Discussions not fitting into this limit were resumed in smaller break-out groups. This report documents the scheduled talks as well as the improvised sessions for in-depth discussion.

Cite as

Rainer Böhme, Joseph Bonneau, and Ittay Eyal. Blockchain Security at Scale (Dagstuhl Seminar 18461). In Dagstuhl Reports, Volume 8, Issue 11, pp. 21-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{bohme_et_al:DagRep.8.11.21,
  author =	{B\"{o}hme, Rainer and Bonneau, Joseph and Eyal, Ittay},
  title =	{{Blockchain Security at Scale (Dagstuhl Seminar 18461)}},
  pages =	{21--34},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{11},
  editor =	{B\"{o}hme, Rainer and Bonneau, Joseph and Eyal, Ittay},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.11.21},
  URN =		{urn:nbn:de:0030-drops-103542},
  doi =		{10.4230/DagRep.8.11.21},
  annote =	{Keywords: Blockchain, Consensus, Cryptography, Distributed Systems, Game Theory, Scaling}
}

7 Search Results for "Eyal, Ittay"

FairPoS: Input Fairness in Permissionless Consensus

Abstract

Cite as

Colordag: An Incentive-Compatible Blockchain

Abstract

Cite as

Gorilla: Safe Permissionless Byzantine Consensus

Abstract

Cite as

Safe Permissionless Consensus

Abstract

Cite as

Tuning PoW with Hybrid Expenditure

Abstract

Cite as

On Cryptocurrency Wallet Design

Abstract

Cite as

Blockchain Security at Scale (Dagstuhl Seminar 18461)

Abstract

Cite as