Brief Announcement: Fair Ordering via Streaming Social Choice Theory
Pages 279 - 282
Abstract
How can we order transactions in a replicated state machine "fairly?" In the model of prior work [2, 8, 9, 13], each of n replicas observes transactions in a different order, and the system aggregates these observed orderings into a single order. We argue that this problem is best viewed through the lens of the classic preference aggregation problem of social choice theory, in which rankings on candidates are aggregated into an election result.
Two features make this problem novel and distinct. First, the number of transactions is unbounded, and an ordering must be defined over a countably infinite set. And second, decisions must be made quickly and with only partial information. Additionally, some faulty replicas might misreport their observations; the influence of faulty replicas on the output should be well understood.
Prior work studies a "γ-batch-order-fairness" property, which divides an ordering into contiguous batches. If a γ fraction of replicas receive a transaction τ before another transaction τ′, then τ′ cannot be in an earlier batch than τ. This definition holds vacuously, so we strengthen it to require that batches have minimal size, while accounting for faulty replicas.
This lens gives a protocol with both strictly stronger fairness and better liveness properties than prior work. We specifically adapt the Ranked Pairs [12] method to this streaming setting. This algorithm can be applied on top of any of the communication protocols (in various network models) of prior work for immediate liveness and fairness improvements. Prior work relies on a fixed choice of γ and a bound on the number of faulty replicas f, but we show that Ranked Pairs satisfies our definition for every ½ < γ ≤ 1 simultaneously and for any f, where fairness guarantees degrade as f increases.
References
[1]
Kenneth J Arrow. 1950. A difficulty in the concept of social welfare. Journal of political economy 58, 4 (1950), 328--346.
[2]
Christian Cachin, Jovana Mićić, Nathalie Steinhauer, and Luca Zanolini. 2022. Quick order fairness. In Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2--6, 2022, Revised Selected Papers. Springer, 316--333.
[3]
Josep M Colomer. 2013. Ramon Llull: from 'Ars electionis' to social choice theory. Social Choice and Welfare 40, 2 (2013), 317--328.
[4]
Marquis de Condorcet and Marquis de Caritat. 1785. An Essay on the Application of Analysis to the Probability of Decisions Rendered by a Plurality of Votes. Classics of social choice (1785), 91--112.
[5]
Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. 2020. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 910--927.
[6]
Xavier Défago, André Schiper, and Péter Urbán. 2004. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv. 36, 4 (dec 2004), 372--421.
[7]
Günter Hägele and Friedrich Pukelsheim. 2001. Lulls' writings on electoral sytems. (2001).
[8]
Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan. 2021. Themis: Fast, strong order-fairness in byzantine consensus. Cryptology ePrint Archive (2021).
[9]
Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. 2020. Order-fairness for byzantine consensus. In Advances in Cryptology-CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17--21, 2020, Proceedings, Part III 40. Springer, 451--480.
[10]
Ramon Llull and Jordi Gaya. 1978. Ars notatoria. Citema.
[11]
Geoffrey Ramseyer and Ashish Goel. 2023. Fair ordering via streaming social choice theory. arXiv preprint arXiv:2304.02730 (2023).
[12]
T Nicolaus Tideman. 1987. Independence of clones as a criterion for voting rules. Social Choice and Welfare 4, 3 (1987), 185--206.
[13]
Mohammad Amin Vafadar and Majid Khabbazian. 2023. Condorcet Attack Against Fair Transaction Ordering. In 5th Conference on Advances in Financial Technologies.
Index Terms
- Brief Announcement: Fair Ordering via Streaming Social Choice Theory
Recommendations
Brief Announcement: Asynchronous Secure Distributed Computing with Transferrable Non-equivocation Revisited
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed ComputingIn this paper, we consider two fundamental problems in secure distributed computing, namely Asynchronous Byzantine Agreement (ABA) and Asynchronous Secure Multi-party Computation (ASMPC). Our focus is on the honest majority setting, involving a set of n ...
Brief announcement: single-version permissive STM
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computingWe present a single-version STM that satisfies a practical notion of permissiveness: it never aborts read-only transactions, and it only aborts an update transaction due to another conflicting update transaction, thereby avoiding many spurious aborts. ...
Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computingFair exchange is one of the most fundamental problems in secure distributed computation. Alice has something that Bob wants, and Bob has something that Alice wants. A fair exchange protocol would guarantee that, even if one of them maliciously deviates ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
570 pages
ISBN:9798400706684
DOI:10.1145/3662158
- Chair:
- Ran Gelles,
- Proceedings Chair:
- Dennis Olivetti,
- Program Chair:
- Petr Kuznetsov
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 June 2024
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
Acceptance Rates
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 40Total Downloads
- Downloads (Last 12 months)40
- Downloads (Last 6 weeks)11
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in