Document Open Access Logo

Tenderbake - A Solution to Dynamic Repeated Consensus for Blockchains

Authors Lăcrămioara Aştefănoaei, Pierre Chambart, Antonella Del Pozzo, Thibault Rieutord, Sara Tucci-Piergiovanni, Eugen Zălinescu

PDF
Thumbnail PDF

File

OASIcs.FAB.2021.1.pdf
  • Filesize: 0.75 MB
  • 23 pages

Document Identifiers

Author Details

Lăcrămioara Aştefănoaei
  • Nomadic Labs, Paris, France
Pierre Chambart
  • Nomadic Labs, Paris, France
Antonella Del Pozzo
  • Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France
Thibault Rieutord
  • Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France
Sara Tucci-Piergiovanni
  • Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France
Eugen Zălinescu
  • Nomadic Labs, Paris, France

Acknowledgements

We thank Philippe Bidinger for feedback on a previous version of this paper.

Cite As Get BibTex

Lăcrămioara Aştefănoaei, Pierre Chambart, Antonella Del Pozzo, Thibault Rieutord, Sara Tucci-Piergiovanni, and Eugen Zălinescu. Tenderbake - A Solution to Dynamic Repeated Consensus for Blockchains. In 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021). Open Access Series in Informatics (OASIcs), Volume 92, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.FAB.2021.1

Abstract

First-generation blockchains provide probabilistic finality: a block can be revoked, albeit the probability decreases as the block "sinks" deeper into the chain. Recent proposals revisited committee-based BFT consensus to provide deterministic finality: as soon as a block is validated, it is never revoked. A distinguishing characteristic of these second-generation blockchains over classical BFT protocols is that committees change over time as the participation and the blockchain state evolve. In this paper, we push forward in this direction by proposing a formalization of the Dynamic Repeated Consensus problem and by providing generic procedures to solve it in the context of blockchains.
Our approach is modular in that one can plug in different synchronizers and single-shot consensus. To offer a complete solution, we provide a concrete instantiation, called {{Tenderbake}}, and present a blockchain synchronizer and a single-shot consensus algorithm, working in a Byzantine and partially synchronous system model with eventually synchronous clocks. In contrast to recent proposals, our methodology is driven by the need to bound the message buffers. This is essential in preventing spamming and run-time memory errors. Moreover, {{Tenderbake}} processes can synchronize with each other without exchanging messages, leveraging instead the information stored in the blockchain.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Blockchain
  • BFT-Consensus
  • Dynamic Repeated Consensus

Metrics

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

Related Versions

References

  1. Victor Allombert, Mathias Bourgoin, and Julien Tesson. Introduction to the Tezos Blockchain. In Proc. High Performance Computing and Simulation, 2019. Google Scholar
  2. Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni. Correctness of Tendermint-core blockchains. In Proc. Principles of Distributed Systems, 2018. Google Scholar
  3. Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara Tucci Piergiovanni. Dissecting Tendermint. In Proc. Networked Systems, 2019. Google Scholar
  4. Lăcrămioara Aştefănoaei, Pierre Chambart, Antonella Del Pozzo, Thibault Rieutord, Sara Tucci, and Eugen Zălinescu. Tenderbake - a solution to dynamic repeated consensus for blockchains, 2021. URL: http://arxiv.org/abs/2001.11965.
  5. Alysson Bessani, Eduardo Alchieri, João Sousa, André Oliveira, and Fernando Pedone. From byzantine replication to blockchain: Consensus is only the beginning. In Proc. International Conference on Dependable Systems and Networks, 2020. Google Scholar
  6. Manuel Bravo, Gregory V. Chockler, and Alexey Gotsman. Making byzantine consensus live. In Proc. International Symposium on Distributed Computing, 2020. Google Scholar
  7. Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT consensus. CoRR, 2018. URL: http://arxiv.org/abs/1807.04938.
  8. Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst., 2002. Google Scholar
  9. T.-H. Hubert Chan, Rafael Pass, and Elaine Shi. Pala: A simple partially synchronous blockchain. IACR Cryptol. ePrint Arch., 2018. Google Scholar
  10. Bernadette Charron-Bost and André Schiper. The heard-of model: computing in distributed systems with benign faults. Distributed Comput., 2009. Google Scholar
  11. Jing Chen and Silvio Micali. Algorand: A secure and efficient distributed ledger. Theor. Comput. Sci., 2019. Google Scholar
  12. T. Crain, V. Gramoli, M. Larrea, and M. Raynal. (Leader/ Randomization/ Signature)free Byzantine consensus for consortium blockchains. CoRR, 2017. Google Scholar
  13. Carole Delporte-Gallet, Stéphane Devismes, Hugues Fauconnier, Franck Petit, and Sam Toueg. With finite memory consensus is easier than reliable broadcast. In Proc. Principles of Distributed Systems, 2008. Google Scholar
  14. Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 1988. Google Scholar
  15. Michael J Fischer and Nancy A Lynch. A lower bound for the time to assure interactive consistency. Information processing letters, 1982. Google Scholar
  16. Eli Gafni. Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract). In Proc. ACM Symposium on Principles of Distributed Computing, 1998. Google Scholar
  17. J. A. Garay, A. Kiayias, and N. Leonardos. The bitcoin backbone protocol: Analysis and applications. In Proc. EUROCRYPT International Conference, 2015. Google Scholar
  18. L.M. Goodman. Tezos - a self-amending crypto-ledger, 2014. Google Scholar
  19. Timo Hanke, Mahnush Movahedi, and Dominic Williams. DFINITY technology overview series, consensus system. CoRR, 2018. Google Scholar
  20. Jae Kwon and Ethan Buchman. Cosmos: A Network of Distributed Ledgers. Google Scholar
  21. S. Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Google Scholar
  22. Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. Cogsworth: Byzantine view synchronization. CoRR, 2019. URL: http://arxiv.org/abs/1909.05204.
  23. Oded Naor and Idit Keidar. Expected linear round synchronization: The missing link for linear byzantine SMR. In Proc. International Symposium on Distributed Computing, 2020. Google Scholar
  24. Nomadic Labs. Analysis of Emmysuperscript+. https://blog.nomadic-labs.com/analysis-of-emmy.html, 2019.
  25. Rafael Pass and Elaine Shi. Rethinking large-scale consensus. IACR Cryptol. ePrint Arch., 2018. Google Scholar
  26. Roberto Saltini. Correctness analysis of IBFT. CoRR, 2019. Google Scholar
  27. Omid Shahmirzadi, Sergio Mena, and André Schiper. Relaxed atomic broadcast: State-machine replication using bounded memory. In Proc. IEEE International Symposium on Reliable Distributed Systems, 2009. Google Scholar
  28. The LibraBFT Team. State machine replication in the Libra blockchain, 2019. Google Scholar
  29. Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. HotStuff: BFT consensus with linearity and responsiveness. In Proc. ACM Symposium on Principles of Distributed Computing, 2019. 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