Document Open Access Logo

On Finality in Blockchains

Authors Emmanuelle Anceaume , Antonella Del Pozzo , Thibault Rieutord, Sara Tucci-Piergiovanni

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.6.pdf
  • Filesize: 0.81 MB
  • 19 pages

Document Identifiers

Author Details

Emmanuelle Anceaume
  • CNRS, Univ Rennes, Inria, IRISA, Rennes, France
Antonella Del Pozzo
  • CEA-List, Université Paris-Saclay, Palaiseau, France
Thibault Rieutord
  • CEA-List, Université Paris-Saclay, Palaiseau, France
Sara Tucci-Piergiovanni
  • CEA-List, Université Paris-Saclay, Palaiseau, France

Funding

This work was partially supported by the French ANR project ByBloS (ANR-20-CE25-0002) devoted to the modular design of building blocks for large-scale fault-tolerant multi-users applications.

Cite As Get BibTex

Emmanuelle Anceaume, Antonella Del Pozzo, Thibault Rieutord, and Sara Tucci-Piergiovanni. On Finality in Blockchains. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.6

Abstract

This paper focuses on blockchain finality, which refers to the time when it becomes impossible to remove a block that has previously been appended to the blockchain. Blockchain finality can be deterministic or probabilistic, immediate or eventual. To favor availability against consistency in the face of partitions, most blockchains only offer probabilistic eventual finality: blocks may be revoked after being appended to the blockchain, yet with decreasing probability as they sink deeper into the chain. Other blockchains favor consistency by leveraging the immediate finality of Consensus - a block appended is never revoked - at the cost of additional synchronization. 
The quest for "good" deterministic finality properties for blockchains is still in its infancy, though. Our motivation is to provide a thorough study of several possible deterministic finality properties and explore their solvability. This is achieved by introducing the notion of bounded revocation, which informally says that the number of blocks that can be revoked from the current blockchain is bounded. Based on the requirements we impose on this revocation number, we provide reductions between different forms of eventual finality, Consensus and Eventual Consensus. From these reductions, we show some related impossibility results in presence of Byzantine processes, and provide non-trivial results. In particular, we provide an algorithm that solves a weak form of eventual finality in an asynchronous system in presence of an unbounded number of Byzantine processes. We also provide an algorithm that solves eventual finality with a bounded revocation number in an eventually synchronous environment in presence of less than half of Byzantine processes. The simplicity of the arguments should better guide blockchain designs and link them to clear formal properties of finality.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Blockchain
  • consistency properties
  • Byzantine tolerant implementations

Metrics

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

References

  1. Emmanuelle Anceaume, Antonella Del Pozzo, Romaric Ludinard, Maria Potop-Butucaru, and Sara Tucci Piergiovanni. Blockchain abstract data type. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019. Google Scholar
  2. Elli Androulaki and et al. Hyperledger fabric: a distributed operating system for permissioned blockchains. In Proceedings of the European Conference on Computer Systems (EuroSys), 2018. Google Scholar
  3. Antonio Anta Fernández, Kishori Konwar, Chryssis Georgiou, and Nicolas Nicolaou. Formalizing and implementing distributed ledger objects. ACM SIGACT News, 49(2):58-76, 2018. Google Scholar
  4. Lăcrămioara Aştefanoaei, Pierre Chambart, Antonella Del Pozzo, Thibault Rieutord, Sara Tucci-Piergiovanni, and Eugen Zălinescu. Tenderbake - A solution to dynamic repeated consensus for blockchains. In Proceedings of the Fourth International Symposium of Foundations and Applications of Blockchain, 2021. Google Scholar
  5. Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. CoRR, 2017. URL: http://arxiv.org/abs/1710.09437.
  6. Benjamin Y Chan and Elaine Shi. Streamlet: Textbook streamlined blockchains. https://eprint.iacr.org/2020/088.pdf, 2020.
  7. Jing Chen and Silvio Micali. Algorand: A secure and efficient distributed ledger. Theor. Comput. Sci., 2019. Google Scholar
  8. Tyler Crain, Vincent Gramoli, Mikel Larrea, and Michel Raynal. (leader/randomization/ signature)-free byzantine consensus for consortium blockchains. CoRR, abs/1702.03068, 2017. URL: http://arxiv.org/abs/1702.03068.
  9. Swan Dubois, Rachid Guerraoui, Petr Kuznetsov, Franck Petit, and Pierre Sens. The weakest failure detector for eventual consistency. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2015. Google Scholar
  10. Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Proc. EUROCRYPT International Conference, 2015. Updated version 2020: https://eprint.iacr.org/2014/765.pdf. Google Scholar
  11. L.M. Goodman. Tezos - A self-amending crypto-ledger, 2014. Google Scholar
  12. Ian Grigg. EOS: An introduction. URL: https://whitepaperdatabase.com/eos-whitepaper/.
  13. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič, and Dragos-Adrian Seredinschi. The consensus number of a cryptocurrency. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), 2019. Google Scholar
  14. Maurice Herlihy. Blockchains and the future of distributed computing. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2017. Google Scholar
  15. Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Proceedings of the Advances in Cryptology, 2017. Google Scholar
  16. Artem Koltsov, Vitaly Cheremensky, and Stanislav Kapulkin. Casper White Paper. Google Scholar
  17. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 1982. Google Scholar
  18. B. Liskov and S. Zilles. Programming with abstract data types. ACM SIGLAN Notices, 9(4), 1974. Google Scholar
  19. Alexandre Maurer and Sébastien Tixeuil. On byzantine broadcast in loosely connected networks. In Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012. Google Scholar
  20. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. www.bitcoin.org, 2008. Google Scholar
  21. Rafael Pass, Lior Seeman, and Abhi Shelat. Analysis of the blockchain protocol in asynchronous networks. In Proceedings of the EUROCRYPT International Conference, 2017. Google Scholar
  22. Matthieu Perrin. Distributed Systems, Concurrency and Consistency. ISTE Press, Elsevier, 2017. Google Scholar
  23. Michel Raynal. Eventual leader service in unreliable asynchronous systems: Why? how? In Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA), 2007. Google Scholar
  24. Alistair Stewart. Poster: Grandpa finality gadget. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS '19, pages 2649-2651, 2019. Google Scholar
  25. Gavin Wood. Ethereum: A secure decentralised generalised transaction ledger. URL: http://gavwood.com/Paper.pdf.
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