Abstract
This paper considers the classical state machine replication (SMR) problem in a distributed system model inspired by cross-chain exchanges. We propose a novel SMR protocol adapted for this model. Each state machine transition takes O(n) message delays, where n is the number of active participants, of which any number may be Byzantine. This protocol makes novel use of path signatures [8] to keep replicas consistent. This protocol design cleanly separates application logic from fault-tolerance, providing a systematic way to replace complex ad-hoc cross-chain protocols with a more principled approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
If all agents are Byzantine, then correctness becomes vacuous.
References
Buterin, V., Reijsbergen, D., Leonardos, S., Piliouras, G.: Incentives in Ethereum’s hybrid Casper protocol. Int. J. Netw. Manag. 30(5) (2020). https://doi.org/10.1002/nem.2098. https://onlinelibrary.wiley.com/doi/10.1002/nem.2098
Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI 1999, New Orleans, Louisiana, USA, pp. 173–186. USENIX Association, Berkeley (1999). https://dl.acm.org/citation.cfm?id=296806.296824. tex.acmid: 296824
Daian, P., et al.: Flash boys 2.0: frontrunning, transaction reordering, and consensus instability in decentralized exchanges. arXiv:1904.05234 [cs] (2019)
Ongaro, D., Ousterhout, J.: In search of an understandable consensus algorithm. In: 2014 USENIX Annual Technical Conference, pp. 305–319. USENIX Association, Philadelphia (2014). https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro
Distler, T.: Byzantine fault-tolerant state-machine replication from a systems perspective. ACM Comput. Surv. 54(1), 1–38 (2021). https://doi.org/10.1145/3436728
Eyal, I., Sirer, E.G.: Majority is not enough: bitcoin mining is vulnerable. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 436–454. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_28
Guerraoui, R., Kuznetsov, P., Monti, M., Pavlovic, M., Seredinschi, D.A., Vonlanthen, Y.: Scalable Byzantine reliable broadcast (extended version). arXiv:1908.01738 [cs] (2020). https://doi.org/10.4230/LIPIcs.DISC.2019.22
Herlihy, M.: Atomic cross-chain swaps. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, UK, pp. 245–254. ACM, New York (2018). https://doi.org/10.1145/3212734.3212736. tex.acmid: 3212736
Herlihy, M., Liskov, B., Shrira, L.: Cross-chain deals and adversarial commerce. Proc. VLDB Endow. 13(2), 100–113 (2019). https://doi.org/10.14778/3364324.3364326. https://arxiv.org/abs/1905.09743
Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst. 16(2), 133–169 (1998)
McMenamin, C., Daza, V., Pontecorvi, M.: Achieving state machine replication without honest players. arXiv:2012.10146 [cs] (2021)
Mendes, H., Tasson, C., Herlihy, M.: Distributed computability in Byzantine asynchronous systems. arXiv:1302.6224 [cs] (2014)
Miller, A., Bentov, I., Kumaresan, R., McCorry, P.: Sprites: payment channels that go faster than lightning. CoRR abs/1702.05812 (2017). http://arxiv.org/abs/1702.05812 tex.bibsource: dblp computer science bibliography. http://dblp.org/rec/bib/journals/corr/MillerBKM17
Moscibroda, T., Schmid, S., Wattenhofer, R.: When selfish meets evil: Byzantine players in a virus inoculation game. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, Colorado, USA, p. 35. ACM Press (2006). https://doi.org/10.1145/1146381.1146391
Nolan, T.: Atomic swaps using cut and choose (2016). https://bitcointalk.org/index.php?topic=1364951
Poon, J., Dryja, T.: The bitcoin lightning network: scalable off-chain instant payments (2016). https://lightning.network/lightning-network-paper.pdf
Robinson, P.: Survey of crosschain communications protocols. Computer Networks (2021). https://arxiv.org/pdf/2004.09494.pdf
Roughgarden, T.: Transaction fee mechanism design for the ethereum blockchain: an economic analysis of EIP-1559. arXiv:2012.00854 [cs, econ] (2020)
Xue, Y., Herlihy, M.: Cross-chain state machine replication (2022). https://doi.org/10.48550/ARXIV.2206.07042
Acknowledgement
This research is supported by NSF grant 5260383.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Xue, Y., Herlihy, M. (2022). Invited Paper: Cross-Chain State Machine Replication. In: Devismes, S., Petit, F., Altisen, K., Di Luna, G.A., Fernandez Anta, A. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2022. Lecture Notes in Computer Science, vol 13751. Springer, Cham. https://doi.org/10.1007/978-3-031-21017-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-031-21017-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21016-7
Online ISBN: 978-3-031-21017-4
eBook Packages: Computer ScienceComputer Science (R0)