Table of Links
Abstract and 1. Introduction
1.1 Our Approach
1.2 Our Results & Roadmap
1.3 Related Work
-
Model and Warmup and 2.1 Blockchain Model
2.2 The Miner
2.3 Game Model
2.4 Warm Up: The Greedy Allocation Function
-
The Deterministic Case and 3.1 Deterministic Upper Bound
3.2 The Immediacy-Biased Class Of Allocation Function
-
The Randomized Case
-
Discussion and References
- A. Missing Proofs for Sections 2, 3
- B. Missing Proofs for Section 4
- C. Glossary
5 Discussion
Present Bias. It is interesting to note that although we incorporate miners’ present biases into our model in the form of the miner ratio α, it does not appear explicitly in the results. Technically, this is because for all the upper bounds we can ignore the first transaction in building our adversarial sequences. For the greedy and ℓ-immediacy-biased algorithms, the case analyses consist of either 1-1 comparisons within the same step, or of chains where the algorithm has the earliest transaction at least as high as OPT. In the analysis of RMIXλ, it is because the potential function has value 0 at the first step. On a deeper level, this is because all our algorithms are variations on the greedy algorithm, and have a bias towards allocating heavy transactions earlier compared to algorithms that plan ahead. This is another aspect of designing good competitive ratio algorithms for present-biased agents that may complicate the generalization of results from the packet scheduling literature.
Memorylessness. We find that a simple memoryless algorithm achieves the deterministic upper bound in the semi-myopic case. We provide a tight characterization of this optimality, and so that algorithm cannot achieve optimality with larger values of λ. We know that for the undiscounted case, i.e., when λ = 1, there is an optimal deterministic algorithm [VCJS], although it is not memoryless. One interesting direction is to see whether this algorithm can be extended to lower λ values.
Heterogeneous Choice of Allocation Rules by Miners. Our assumption throughout the paper is that all miners follow a given allocation protocol. This is essential to the analysis: a miner assumes that even when they do not mine a certain block, and thus do not extract revenue at this step, the same allocation rule is still followed. This assumption is somewhat bolstered by our results, that find that the optimal semi-myopic algorithm does not depend on α, as long as α > 0. Thus, as long as all miners have α > 0, it seems reasonable that all will follow the same optimal rule, even if we do not implement ways of ‘punishing’ miners who deviate from the rule. However, if some of the miners are ‘atomic’ (have α = 0), then their optimal allocation rule is the greedy allocation, and then all bets are off w.r.t. what may be an equilibrium of the allocation rule. The same is true for the cases which are not semi-myopic.
Semi-myopic discounts. Most blockchains rely on mechanisms that have a relatively slow blockrate, e.g., Bitcoin’s mechanism has an average of one block per 10 minutes. Thus, the discount factors of the semi-myopic range may seem excessive. However, we believe that there are settings, such as long-term project management, where a company decides which projects to commit its resources to on a time-scale of months / years, that are perfectly aligned with our framework and the semi-myopic regime in particular. Moreover, there are alternative interpretations to the discount factor that make the semi-myopic range more lucrative: One example is where clients, on top of having a strict deadline after which they leave the system, may also become impatient and leave following a geometric (memoryless) process. Another interpretation, which is perhaps very relevant in the blockchain setting, is exactly the one we discussed regarding heterogeneous miners: λ can be interpreted as a rule-of-thumb discount that stems from the probability of having miners with different allocation rules decide the next block. On a technical note, we remark that we expect the level of complexity of algorithms that go beyond the semi-myopic range to be higher than our optimal ℓ-immediacy-biased algorithm. In a sense, aggressive discounts eliminate longer pathological examples, and so enable such a simple algorithm to be optimal.
General time-dependent models. While multiplicative discounting over time is a natural model which is very common in the economic literature, other time-dependent models can be of interest. It is interesting to consider the most general case, where a transaction can specify a perblock fee, and these may not even be monotonically decreasing, for example, if this is a delayed transaction. It is also interesting to consider personalized discount factors instead of a uniform global discount factor, that represent differential patience between clients/transactions.
References
BCJ11] Marcin Bienkowski, Marek Chrobak, and Łukasz Jeż. “Randomized competitive algorithms for online buffer management in the adaptive adversary model”. In: Theoretical Computer Science 412.39 (2011), pp. 5121–5131. issn: 0304-3975. doi: https: //doi.org/10.1016/j.tcs.2011.05.015. url: https://www.sciencedirect.com/ science/article/pii/S0304397511003975.
[BE05] Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge, United Kingdom: Cambridge University Press, 2005.
[BEOS19] Soumya Basu, David Easley, Maureen O’Hara, and Emin Gün Sirer. Towards a Functional Fee Market for Cryptocurrencies. 2019. doi: 10.48550/ARXIV.1901.06830. url: https://arxiv.org/abs/1901.06830.
[CCFJST06] Francis Y.L. Chin, Marek Chrobak, Stanley P.Y. Fung, Wojciech Jawor, Jiři Sgall, and Tomáš Tichý. “Online competitive algorithms for maximizing weighted throughput of unit jobs”. In: Journal of Discrete Algorithms 4.2 (2006), pp. 255–276. issn: 1570-8667. doi: https://doi.org/10.1016/j.jda.2005.03.005. url: https: //www.sciencedirect.com/science/article/pii/S1570866705000250.
[CS23] Hao Chung and Elaine Shi. “Foundations of Transaction Fee Mechanism Design”. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023, pp. 3856–3899. doi: 10.1137/1.9781611977554.ch150. eprint: https://epubs.siam.org/doi/pdf/10. 1137/1.9781611977554.ch150. url: https://epubs.siam.org/doi/abs/10.1137/ 1.9781611977554.ch150.
[DMSW21] Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang. Optimal Pricing Schemes for an Impatient Buyer. 2021. doi: 10.48550/ARXIV.2106.02149. url: https://arxiv.org/abs/2106.02149.
[DSSX21] John P Dickerson, Karthik A Sankararaman, Aravind Srinivasan, and Pan Xu. “Allocation problems in ride-sharing platforms: Online matching with offline reusable resources”. In: ACM Transactions on Economics and Computation (TEAC) 9.3 (2021), pp. 1–17.
[ES14] Ittay Eyal and Emin Gün Sirer. “Majority is not enough: Bitcoin mining is vulnerable”. In: International conference on financial cryptography and data security. Vol. 61. Springer. Association for Computing Machinery (ACM), 2014, pp. 436–454. doi: 10.1145/3212998.
[FGKK16] Amos Fiat, Kira Goldner, Anna R. Karlin, and Elias Koutsoupias. “The FedEx Problem”. In: Proceedings of the 2016 ACM Conference on Economics and Computation. EC ’16. Maastricht, The Netherlands: Association for Computing Machinery, 2016, pp. 21–22. isbn: 9781450339360. doi: 10.1145/2940716.2940752. url: https://doi.org/10.1145/2940716.2940752.
[fla23] flashbots. Private Transactions. 2023. url: https://web.archive.org/web/20230521052523/https://docs.flashbots.net/flashbots-auction/searchers/ advanced/private-transaction.
[FMN08] Amos Fiat, Yishay Mansour, and Uri Nadav. “Competitive Queue Management for Latency Sensitive Packets”. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’08. San Francisco, California: Society for Industrial and Applied Mathematics, 2008, pp. 228–237.
[FW21] Matheus V. X. Ferreira and S. Matthew Weinberg. “Proof-of-Stake Mining Games with Perfect Randomness”. In: Proceedings of the 22nd ACM Conference on Economics and Computation. EC ’21. Budapest, Hungary: Association for Computing Machinery, 2021, pp. 433–453. isbn: 9781450385541. doi: 10.1145/3465456. 3467636. url: https://doi.org/10.1145/3465456.3467636.
[Gra18] Jay Graber. ZIP 203: Transaction Expiry. 2018. url: https://web.archive.org/web/20210920064143/https://zips.z.cash/zip-0203.
[Haj01] Bruce Hajek. “On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time”. In: Proceedings of the 2001 Conference on Information Sciences and Systems. 2001.
[KOR16] Jon Kleinberg, Sigal Oren, and Manish Raghavan. “Planning Problems for Sophisticated Agents with Present Bias”. In: Proceedings of the 2016 ACM Conference on Economics and Computation. EC ’16. Maastricht, The Netherlands: Association for Computing Machinery, 2016, pp. 343–360. isbn: 9781450339360. doi: 10.1145/ 2940716.2940764. url: https://doi.org/10.1145/2940716.2940764.
[LLNZZZ22] Yulin Liu, Yuxuan Lu, Kartik Nayak, Fan Zhang, Luyao Zhang, and Yinhong Zhao. Empirical Analysis of EIP-1559: Transaction Fees, Waiting Time, and Consensus Security. 2022. doi: 10.48550/ARXIV.2201.05574. url: https://arxiv.org/abs/ 2201.05574.
[LSS05] Fei Li, Jay Sethuraman, and Clifford Stein. “An Optimal Online Algorithm for Packet Scheduling with Agreeable Deadlines”. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’05. Vancouver, British Columbia: Society for Industrial and Applied Mathematics, 2005, pp. 801–802. isbn: 0898715857.
[LSZ22] Ron Lavi, Or Sattath, and Aviv Zohar. “Redesigning Bitcoin’s Fee Market”. In: ACM Trans. Econ. Comput. 10.1 (2022). issn: 2167-8375. doi: 10.1145/3530799. url: https://doi.org/10.1145/3530799.
[MACG20] Johnnatan Messias, Mohamed Alzayat, Balakrishnan Chandrasekaran, and Krishna P Gummadi. On Blockchain Commit Times: An analysis of how miners choose Bitcoin transactions. Online, 2020.
[OR15] Ted O’Donoghue and Matthew Rabin. “Present Bias: Lessons Learned and To Be Learned”. In: The American Economic Review 105.5 (2015), pp. 273–279. issn: 00028282. url: http://www.jstor.org/stable/43821892 (visited on 07/05/2023).
[PORH22] Michael Pacheco, Gustavo A. Oliva, Gopi Krishnan Rajbahadur, and Ahmed E. Hassan. “Is My Transaction Done yet? An Empirical Study of Transaction Processing Times in the Ethereum Blockchain Platform”. In: ACM Trans. Softw. Eng. Methodol. To appear. (2022). issn: 1049-331X. doi: 10.1145/3549542. url: https://doi. org/10.1145/3549542.
[PW21] Julien Prat and Benjamin Walter. “An Equilibrium Model of the Market for Bitcoin Mining”. In: Journal of Political Economy 129.8 (2021), pp. 2415–2452. doi: 10 . 1086/714445. eprint: https://doi.org/10.1086/714445. url: https://doi.org/ 10.1086/714445.
[Rou20] Tim Roughgarden. “Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559”. In: CoRR abs/2012.00854 (2020). arXiv: 2012. 00854. url: https://arxiv.org/abs/2012.00854.
[Rou21] Tim Roughgarden. “Transaction fee mechanism design”. In: ACM SIGecom Exchanges 19.1 (2021), pp. 52–55.
[SC16] Sukhpal Singh and Inderveer Chana. “A survey on resource scheduling in cloud computing: Issues and challenges”. In: Journal of grid computing 14.2 (2016), pp. 217– 264.
[SU19] Linda Schilling and Harald Uhlig. “Some simple bitcoin economics”. In: Journal of Monetary Economics 106 (2019). Special conference issue: “Money Creation and Currency Competition” October 19-20, 2018 Sponsored by the Study Center Gerzensee and Swiss National Bank, pp. 16–26. issn: 0304-3932. doi: https://doi.org/10. 1016/j.jmoneco.2019.07.002. url: https://www.sciencedirect.com/science/article/pii/S0304393219301199.
[TE18] Itay Tsabary and Ittay Eyal. “The Gap Game”. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. CCS ’18. Toronto, Canada: Association for Computing Machinery, 2018, pp. 713–728. isbn: 9781450356930. doi: 10 . 1145 / 3243734 . 3243737. url: https://doi.org/10.1145/3243734.3243737.
[TFWM21] Kemal Turksonmez, Marcin Furtak, Mike P. Wittie, and David L. Millman. “Two Ways Gas Price Oracles Miss The Mark”. In: 2021 IEEE International Conference on Omni-Layer Intelligent Systems (COINS). Barcelona, Spain: IEEE, 2021, pp. 1–7. doi: 10.1109/COINS51742.2021.9524148.
[VCJS] Pavel Veselý, Marek Chrobak, Łukasz Jeż, and Jiři Sgall. “A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines”. In: Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 123–142. doi: 10.1137/1.9781611975482.9. eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.9. url: https://epubs.siam.org/doi/abs/10.1137/1.9781611975482.9.
[Ves21] Pavel Veselý. “Packet Scheduling: Plans, Monotonicity, and the Golden Ratio”. In: SIGACT News 52.2 (2021), pp. 72–84. issn: 0163-5700. doi: 10.1145 / 3471469.3471481. url: https://doi.org/10.1145/3471469.3471481.
[Yao18] Andrew Chi-Chih Yao. An Incentive Analysis of some Bitcoin Fee Designs. 2018. doi: 10.48550/ARXIV.1811.02351. url: https://arxiv.org/abs/1811.02351.
[YTZ22] Aviv Yaish, Saar Tochner, and Aviv Zohar. “Blockchain Stretching & Squeezing: Manipulating Time for Your Best Interest”. In: Proceedings of the 23rd ACM Conference on Economics and Computation. EC ’22. Boulder, CO, USA: Association for Computing Machinery, 2022, pp. 65–88. isbn: 9781450391504. doi: 10.1145/3490486. 3538250. url: https://doi.org/10.1145/3490486.3538250.
[YZ20] Aviv Yaish and Aviv Zohar. Correct Cryptocurrency ASIC Pricing – Are Miners Overpaying? 2020. eprint: 2002.11064.
:::info
Authors:
(1) Yotam Gafni, Weizmann Institute (yotam.gafni@gmail.com);
(2) Aviv Yaish, The Hebrew University, Jerusalem (aviv.yaish@mail.huji.ac.il).
:::
:::info
This paper is available on arxiv under CC BY 4.0 DEED license.
:::
