research-article

Proof-of-Stake Longest Chain Protocols: Security vs Predictability

Authors:

Sreeram Kannan,

Pramod Viswanath,

Ofer ZeitouniAuthors Info & Claims

ConsensusDay '22: Proceedings of the 2022 ACM Workshop on Developments in Consensus

Pages 29 - 42

https://doi.org/10.1145/3560829.3563559

Published: 07 November 2022 Publication History

Abstract

The Nakamoto longest chain protocol is remarkably simple and has been proven to provide security against any adversary with less than 50% of the total hashing power. Proof-of-stake (PoS) protocols are an energy efficient alternative; however existing protocols adopting Nakamoto's longest chain design achieve provable security only by allowing long-term predictability, subjecting the system to serious bribery attacks. In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamoto's PoW protocol can achieve security against any adversary with less than 1/(1+e) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols with a formal proof of their security against a 50% adversary, while only requiring short-term predictability.

Supplementary Material

MP4 File (ConsensusDay22-12.mp4)

Presentation video for "Proof-of-Stake Longest Chain Protocols: Security vs Predictability". In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamoto's PoW protocol can achieve security against any adversary with less than 1/(1 + e) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols with a formal proof of their security against a 50% adversary, while only requiring short-term predictability.

Download
37.33 MB

References

[1]

Badertscher, C., Gazi, P., Kiayias, A., Russell, A., and Zikas, V. Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (2018), ACM, pp. 913--930.

Digital Library

[2]

Bagaria, V., Dembo, A., Kannan, S., Oh, S., Tse, D., Viswanath, P., Wang, X., and Zeitouni, O. Proof-of-stake longest chain protocols: Security vs predictability. arXiv preprint arXiv:1910.02218 (2019).

[3]

Baudet, M., Ching, A., Chursin, A., Danezis, G., Garillot, F., Li, Z., Malkhi, D., Naor, O., Perelman, D., and Sonnino, A. State machine replication in the libra blockchain, 2018.

[4]

Bellare, M., and Miner, S. K. A forward-secure digital signature scheme. In Annual International Cryptology Conference (1999), Springer, pp. 431--448.

[5]

Bentov, I., Pass, R., and Shi, E. Snow white: Provably secure proofs of stake. IACR Cryptology ePrint Archive 2016 (2016), 919.

[6]

Brown-Cohen, J., Narayanan, A., Psomas, A., and Weinberg, S. M. Formal barriers to longest-chain proof-of-stake protocols. In Proceedings of the 2019 ACM Conference on Economics and Computation (2019), ACM, pp. 459--473.

Digital Library

[7]

Buterin, V., and Griffith, V. Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437 (2017).

[8]

Chen, J., and Micali, S. Algorand. arXiv preprint arXiv:1607.01341 (2016).

[9]

David, B., Gazi, P., Kiayias, A., and Russell, A. Ouroboros praos: An adaptively secure, semi-synchronous proof-of-stake blockchain. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2018), Springer, pp. 66--98.

[10]

Deb, S., Kannan, S., and Tse, D. Posat: proof-of-work availability and unpredictability, without the work. In International Conference on Financial Cryptography and Data Security (2021), Springer, pp. 104--128.

Digital Library

[11]

Dembo, A., Kannan, S., Tas, E. N., Tse, D., Viswanath, P., Wang, X., and Zeitouni, O. Everything is a race and nakamoto always wins. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (2020), pp. 859--878.

Digital Library

[12]

Dodis, Y., and Yampolskiy, A. A verifiable random function with short proofs and keys. In International Workshop on Public Key Cryptography (2005), Springer, pp. 416--431.

Digital Library

[13]

Fan, L., Katz, J., and Zhou, H.-S. A large-scale proof-of-stake blockchain in the open setting. Available online at http://www.fractalblock.com/assets/iching_consensus_protocol.pdf.

[14]

Fan, L., and Zhou, H.-S. A scalable proof-of-stake blockchain in the open setting (or, how to mimic nakamoto's design via proof-of-stake), 2018. Cryptology ePrint Archive, Report 2017/656, Version 20180425:201821.

[15]

Garay, J., Kiayias, A., and Leonardos, N. The bitcoin backbone protocol: Analysis and applications. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2015), Springer, pp. 281--310.

[16]

Gilad, Y., Hemo, R., Micali, S., Vlachos, G., and Zeldovich, N. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles (2017), ACM, pp. 51--68.

Digital Library

[17]

Hu, Y., and Shi, Z. Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees. The Annals of Probability 37, 2 (2009), 742--789.

[18]

Itkis, G., and Reyzin, L. Forward-secure signatures with optimal signing and verifying. In Annual International Cryptology Conference (2001), Springer, pp. 332-- 354.

[19]

Kiayias, A., Russell, A., David, B., and Oliynykov, R. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Annual International Cryptology Conference (2017), Springer, pp. 357--388.

[20]

Micali, S., Rabin, M., and Vadhan, S. Verifiable random functions. In 40th annual symposium on foundations of computer science (cat. No. 99CB37039) (1999), IEEE, pp. 120--130.

[21]

Micali, S., Rabin, M., and Vadhan, S. Verifiable random functions. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) (1999), IEEE, pp. 120--130.

[22]

Nakamoto, S. Bitcoin: A peer-to-peer electronic cash system.

[23]

Pass, R., Seeman, L., and Shelat, A. Analysis of the blockchain protocol in asynchronous networks. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2017).

[24]

Pass, R., and Shi, E. Fruitchains: A fair blockchain. In Proceedings of the ACM Symposium on Principles of Distributed Computing (2017), ACM.

Digital Library

[25]

Shi, Z. Branching Random Walks, vol. 2151 of Lecture Notes in Mathematics. Springer Verlag, New York NY, 2015.

[26]

Stütz, R., Gazi, P., Haslhofer, B., and Illum, J. Stake shift in major cryptocurrencies: An empirical study. arXiv preprint arXiv:2001.04187 (2020).

[27]

Wang, X. e. a. Proof-of-stake longest chain protocol revisited. arXiv preprint arXiv:1910.02218v2 (2018).

[28]

Yin, M., Malkhi, D., Reiter, M. K., Gueta, G. G., and Abraham, I. Hotstuff: B

Cited By

Ji P(2023)The Advance of Cryptocurrency Wallet with Digital SignatureHighlights in Science, Engineering and Technology10.54097/hset.v39i.671439(1098-1103)Online publication date: 1-Apr-2023
https://doi.org/10.54097/hset.v39i.6714
Huang MHan RDu ZFu YLiu L(2022)Reputation-based state machine replication2022 IEEE 21st International Symposium on Network Computing and Applications (NCA)10.1109/NCA57778.2022.10013518(225-234)Online publication date: 14-Dec-2022
https://doi.org/10.1109/NCA57778.2022.10013518

Index Terms

Proof-of-Stake Longest Chain Protocols: Security vs Predictability
1. Security and privacy
  1. Systems security
    1. Distributed systems security

Recommendations

Two More Attacks on Proof-of-Stake GHOST/Ethereum
ConsensusDay '22: Proceedings of the 2022 ACM Workshop on Developments in Consensus

Ethereum, the world's second largest cryptocurrency with a market capitalization exceeding 120 billion USD as of this writing, aims to switch from Proof-of-Work (PoW) to Proof-of-Stake (PoS) based consensus later in the year 2022 (`the Merge'). Yet, so ...
Everything is a Race and Nakamoto Always Wins
CCS '20: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the ...
Formal Barriers to Longest-Chain Proof-of-Stake Protocols
EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation

The security of most existing cryptocurrencies is based on a concept called Proof-of-Work, in which users must solve a computationally hard cryptopuzzle to authorize transactions ("one unit of computation, one vote''). This leads to enormous expenditure ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ConsensusDay '22: Proceedings of the 2022 ACM Workshop on Developments in Consensus

November 2022

84 pages

ISBN:9781450398794

DOI:10.1145/3560829

General Chairs:
Jorge M. Soares
Protocol Labs, Serbia
,
Dawn Song
UC Berkeley, USA
,
Marko Vukolić
Protocol Labs, Serbia

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '22

Sponsor:

SIGSAC

CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security

November 7, 2022

CA, Los Angeles, USA

Acceptance Rates

ConsensusDay '22 Paper Acceptance Rate 6 of 25 submissions, 24%;

Overall Acceptance Rate 6 of 25 submissions, 24%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
239
Total Downloads

Downloads (Last 12 months)87
Downloads (Last 6 weeks)13

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ji P(2023)The Advance of Cryptocurrency Wallet with Digital SignatureHighlights in Science, Engineering and Technology10.54097/hset.v39i.671439(1098-1103)Online publication date: 1-Apr-2023
https://doi.org/10.54097/hset.v39i.6714
Huang MHan RDu ZFu YLiu L(2022)Reputation-based state machine replication2022 IEEE 21st International Symposium on Network Computing and Applications (NCA)10.1109/NCA57778.2022.10013518(225-234)Online publication date: 14-Dec-2022
https://doi.org/10.1109/NCA57778.2022.10013518

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents