Document Open Access Logo

Security Analysis of Filecoin’s Expected Consensus in the Byzantine vs Honest Model

Authors Xuechao Wang , Sarah Azouvi , Marko Vukolić

PDF
Thumbnail PDF

File

LIPIcs.AFT.2023.5.pdf
  • Filesize: 1.11 MB
  • 21 pages

Document Identifiers

Author Details

Xuechao Wang
  • Thrust of Financial Technology, HKUST(GZ), Guangzhou, China
Sarah Azouvi
  • Protocol Labs, San Francisco, CA, USA
Marko Vukolić
  • Protocol Labs, San Francisco, CA, USA

Acknowledgements

The authors would like to thank Guy Goren for his suggestion of Consistent Broadcast as a mitigation to the n-split attack.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.AFT.2023.5

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).

Subject Classification

ACM Subject Classification
  • Security and privacy → Distributed systems security
Keywords
  • Decentralized storage
  • Consensus
  • Security analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Filecoin Spec. URL: https://spec.filecoin.io/.
  2. A Guide to Filecoin Storage Mining. https://filecoin.io/blog/posts/a-guide-to-filecoin-storage-mining/. Accessed: 2023-08-02.
  3. Coin Market Cap. URL: https://coinmarketcap.com/.
  4. Drand. https://drand.love/. Accessed: 2022-08-30.
  5. Filecoin Plus. URL: https://docs.filecoin.io/basics/how-storage-works/filecoin-plus/.
  6. Filfox - Filecoin Explorer. URL: https://filfox.info/en.
  7. FIP-0051: Improving EC security with Consistent Broadcast. URL: https://github.com/filecoin-project/FIPs/blob/master/FRCs/frc-0051.md.
  8. Sarah Azouvi and Marko Vukolić. Pikachu: Securing PoS blockchains from long-range attacks by checkpointing into Bitcoin PoW using Taproot. arXiv preprint arXiv:2208.05408, 2022. Google Scholar
  9. Christian Badertscher, Peter Gaži, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas. Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 913-930, 2018. Google Scholar
  10. Vivek Bagaria, Amir Dembo, Sreeram Kannan, Sewoong Oh, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni. Proof-of-stake longest chain protocols: Security vs predictability. arXiv preprint arXiv:1910.02218, 2019. Google Scholar
  11. Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. Prism: Deconstructing the blockchain to approach physical limits. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 585-602. ACM, 2019. Google Scholar
  12. Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM (JACM), 32(4):824-840, 1985. Google Scholar
  13. Bernardo David, Peter Gaži, Aggelos Kiayias, and Alexander Russell. Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 66-98. Springer, 2018. Google Scholar
  14. Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni. Everything is a race and Nakamoto always wins. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 859-878, 2020. Google Scholar
  15. William Feller. An introduction to probability theory and its applications. Technical report, Wiley series in probability and mathematical statistics, 3rd edn.(Wiley, New …, 1971. Google Scholar
  16. Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 281-310. Springer, 2015. Google Scholar
  17. Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling Byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51-68, 2017. Google Scholar
  18. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Dragos-Adrian Seredinschi, and Yann Vonlanthen. Scalable Byzantine reliable broadcast (extended version). arXiv preprint arXiv:1908.01738, 2019. Google Scholar
  19. Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Annual International Cryptology Conference, pages 357-388. Springer, 2017. Google Scholar
  20. Lucianna Kiffer, Rajmohan Rajaraman, and Abhi Shelat. A better method to analyze blockchain consistency. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 729-744, 2018. Google Scholar
  21. Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 120-130. IEEE, 1999. Google Scholar
  22. Satoshi Nakamoto and A Bitcoin. A peer-to-peer electronic cash system. Bitcoin.-URL: https://bitcoin. org/bitcoin. pdf, 4(2), 2008. Google Scholar
  23. Christopher Natoli and Vincent Gramoli. The balance attack against proof-of-work blockchains: The r3 testbed as an example. arXiv preprint arXiv:1612.09426, 2016. Google Scholar
  24. Rafael Pass, Lior Seeman, and Abhi Shelat. Analysis of the blockchain protocol in asynchronous networks. In Advances in Cryptology-EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30-May 4, 2017, Proceedings, Part II, pages 643-673. Springer, 2017. Google Scholar
  25. Rafael Pass and Elaine Shi. The sleepy model of consensus. In International Conference on the Theory and Application of Cryptology and Information Security, pages 380-409. Springer, 2017. Google Scholar
  26. Michael O Rabin. Transaction protection by beacons. Journal of Computer and System Sciences, 27(2):256-267, 1983. Google Scholar
  27. Ling Ren. Analysis of Nakamoto consensus. Cryptology ePrint Archive, 2019. Google Scholar
  28. Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transaction processing in bitcoin. In Financial Cryptography and Data Security: 19th International Conference, FC 2015, San Juan, Puerto Rico, January 26-30, 2015, Revised Selected Papers 19, pages 507-527. Springer, 2015. Google Scholar
  29. Xuechao Wang, Sarah Azouvi, and Marko Vukolić. Security analysis of filecoin’s expected consensus in the byzantine vs honest model. arXiv preprint arXiv:2308.06955, 2023. Google Scholar
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