Abstract
In recent years, a new research area called order-fairness has emerged within State Machine Replication (SMR). Its goal is to prevent malicious processes from reordering transactions, ensuring that the SMR output reflects the local orderings observed by processes. One of the advanced approaches to addressing this challenge is fair separability, which is designed to mitigate cyclic dependencies present in transaction dependency graphs. However, in the existing implementation of fair separability, a transaction input by a Byzantine process can be output with only \(\mathcal {O}(1)\) resources, whereas outputting a transaction input by a correct process requires \(\mathcal {O}(n)\) resources. This vulnerability exposes the protocol to chain-quality attacks.
In this paper, we propose an implementation of fair separability where the cost of outputting transactions remains consistent for the inputs of all processes, which enhances resilience to chain-quality attacks.
Authors are listed alphabetically.
Z. Lu and P. Zarbafian—Led the effort with equal contributions.
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
References
Bracha, G.: Asynchronous byzantine agreement protocols. Inf. Comput. 75(2), 130–143 (1987)
Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 524–541. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_31
Cachin, C., Mićić, J., Steinhauer, N., Zanolini, L.: Quick order fairness. In: Eyal, I., Garay, J. (eds.) Financial Cryptography and Data Security, FC 2022, LNCS, vol. 13411, pp. 316–333 Springer, Cham (2022). https://doi.org/10.1007/978-3-031-18283-9_15
Daian, P., et al.: Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In: S &P, pp.910–927. IEEE (2020)
Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM (JACM) 35(2), 288–323 (1988)
Fitzi, M., Garay, J.A.: Efficient player-optimal protocols for strong and differential consensus. In: Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, pp. 211–220 (2003)
Gramoli, V., Lu, Z., Tang, Q. and Zarbafian, P.: AOAB: optimal and fair ordering of financial transactions. In: 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN (2024)
Gramoli, V., Lu, Z., Tang, Q., Zarbafian, P.: Optimal asynchronous byzantine consensus with fair separability. Cryptology ePrint Archive, Paper 2024/545 (2024). https://eprint.iacr.org/2024/545
Gueta, G.G., et al.: SBFT: a scalable and decentralized trust infrastructure. In: 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pp. 568–580. IEEE (2019)
Hadzilacos, V., Toueg, S.: Fault-tolerant broadcasts and related problems. In: Distributed systems (2nd ed.), pp. 97–145. ACM New York, NY, USA (1993)
Herlihy, M.P., and Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. (TOPLAS) 12(3), 463–492 (1990)
Kelkar, M., Deb, S., Long, S., Juels, A., Kannan, S.: Themis: fast, strong order-fairness in byzantine consensus. In: ConsensusDays 21 (2021)
Kelkar, M., Zhang, F., Goldfeder, S., Juels, A.: Order-fairness for byzantine consensus. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 451–480. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_16
Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.: Zyzzyva: speculative byzantine fault tolerance. ACM Trans. Comput. Syst. (TOCS) 27(4), 1–39 (2010)
Kursawe, K.: Wendy grows up: more order fairness. In: Bernhard, M., et al. (eds.) FC 2021. LNCS, vol. 12676, pp. 191–196. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-662-63958-0_17
Lamport, L., Shostak, R., Pease, M.: The Byzantine Generals Problem, pp. 203–226. Association for Computing Machinery (2019)
Liu, S., Viotti, P., Cachin, C., Quéma, V., Vukolić, M.: XFT: practical fault tolerance beyond crashes. In: Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI 2016, pp. 485–500, USA, USENIX Association (2016)
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system. Decentralized business review, p. 21260 (2008)
Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM (JACM) 27(2), 228–234 (1980)
Qin, K., Zhou, L., Gervais, A.: Quantifying blockchain extractable value: how dark is the forest? In: 2022 IEEE Symposium on Security and Privacy (SP), pp. 198–214 (2022)
Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. (CSUR) 22(4), 299–319 (1990)
Wood, G., et al.: Ethereum: a secure decentralised generalised transaction ledger. Ethereum Project Yellow Paper 151(2014), 1–32 (2014)
Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: HotStuff: BFT consensus with linearity and responsiveness. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 347–356 (2019)
Zarbafian, P., Gramoli, V.: Aion: secure transaction ordering using TEEs. In: Tsudik, G., Conti, M., Liang, K., Smaragdakis, G. (eds.) Computer Security - ESORICS 2023. ESORICS 2023. Lecture Notes in Computer Science, vol. 14347, pp. 332–350. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-51482-1_17
Zarbafian, P., Gramoli, V.: Lyra: fast and scalable resilience to reordering attacks in blockchains. In: 2023 IEEE International Parallel & Distributed Processing Symposium, IEEE (2023)
Zhang, Y., Setty, S., Chen, Q., Zhou, L., Alvisi, L.: Byzantine ordered consensus without byzantine oligarchy. In: OSDI, pp. 633–649 (2020)
Acknowledgments
This research is supported under Australian Research Council Future Fellowship funding scheme (project number 180100496) entitled “The Red Belly Blockchain: A Scalable Blockchain for Internet of Things”.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Gramoli, V., Lu, Z., Tang, Q., Zarbafian, P. (2024). Resilience to Chain-Quality Attacks in Fair Separability. In: Garcia-Alfaro, J., Kozik, R., Choraś, M., Katsikas, S. (eds) Computer Security – ESORICS 2024. ESORICS 2024. Lecture Notes in Computer Science, vol 14985. Springer, Cham. https://doi.org/10.1007/978-3-031-70903-6_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-70903-6_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-70902-9
Online ISBN: 978-3-031-70903-6
eBook Packages: Computer ScienceComputer Science (R0)