Reducing Blockchain Fees with R2-TFRM and On-Chain Randomness | HackerNoon

Table of Links

Abstract and 1. Introduction

2. Related Work

3. Preliminaries

   3.1 TFMs: Desirable Properties

   3.2 Groves’ Redistribution Mechanism (RM)

4. IDEAL-TFRM: Impossibility of Achieving Strictly Positive Redistribution Index

5. Transaction Fee Redistribution Mechanism (TFRM)

6. R-TFRM: A TFRM Robust to Miner Manipulation

   6.1 R-TFRM: Analyzing Impact of Miner Manipulation on Rebate and Miner Revenue

7. R2-TFRM: Robust and Rational TFRM

8. Conclusion and References

A. Proofs for Results from Section 4 and 5

B. Proofs for Results from Section 6

C. Proofs for Results from Section 7

R2-TFRM: ROBUST AND RATIONAL TFRM

R2 -TFRM: On-chain Randomness. As stated, each transaction receives a rebate with a probability 𝛼. Similar to other TFMs [8], we employ trusted on-chain randomness for this randomization. Researchers have proposed such trusted randomized protocols using various cryptographic primitives [3, 10]. Significantly, the miner of the block cannot exert any influence on this randomization.

Proof Sketch. We divide the proof into two parts.

R2 -TFRM: Analyzing Miner Manipulation. Like R-TFRM, R2 – TFRM also ensures strictly positive RRI even with miner manipulation as formally stated in Theorem 7.

Proof Sketch. The result follows from the similar result in Theorem 5 for R-TFRM and the fact that the miner has no control over the randomization in R2 -TFRM.

Discussion on TFRMs. Given that the current TFM literature assumes that users and miners are myopic, we believe that redistributing the surplus is more effective in reducing the net payments paid by the users. Another desirable property in TFMs is that of predictable transaction fees, i.e., reducing the volatility of the fees paid by the users. For instance, EIP-1559 [5] uses a deterministic function based on the previous block consumption to calculate a network-determined minimum threshold fee (called base fee) paid by each user. The users can also pay a priority fee over the base fee to incentivize the miners to include their transactions. The base fee aims to reduce the fee volatility and aims to arrive at a market clearing price. Crucially, this minimum threshold fee is burned – transferred to an unspendable address – implying that the miner does not receive this fee as revenue. We see that burning some fraction of the fee is necessary to guarantee such properties. In such mechanisms, the priority fee calculated post-burning can be further reduced by employing TFRMs.

8 CONCLUSION

In this paper, we argued the importance of minimizing user costs in a TFM. Our key idea is to employ a redistribution mechanism-based approach for determining the transaction fees, which we call the Transaction Fee Redistribution Mechanism (TFRM). Due to strategic miner manipulation, we first show that guaranteeing a strictly positive rebate in a TFRM and other desirable properties is impossible. Hence, we propose R-TFRM, which ensures strictly positive rebates even in the worst case but compromises on miner’s IR. However, we show that in R-TFRM, a strategic miner will never incur negative utility while still guaranteeing strictly positive rebates to the users. We also propose R2 -TFRM which uses blockchain’s inherent randomness to guarantee a strictly positive rebate to the users while also respecting the miner’s IR.

Future Work. Future directions can explore TFRMs with randomized rebate functions, which may likely satisfy stronger notions of IC and IR. Another approach may be to explore non-linear rebate functions, which may provide a better redistribution index on average. In addition, unlike this work, future work can also explore transactions with varying sizes.

REFERENCES

[1] Martin J Bailey. 1997. The Demand Revealing Process: To Distribute the Surplus. Public Choice 91, 2 (1997), 107–26. https://EconPapers.repec.org/RePEc:kap: pubcho✌️91:y:1997:i:2:p:107-26

[2] Soumya Basu, David Easley, Maureen O’Hara, and Emin Sirer. 2019. StableFees: A Predictable Fee Market for Cryptocurrencie. Available at SSRN 3318327 (2019).

[3] Adithya Bhat, Nibesh Shrestha, Zhongtang Luo, Aniket Kate, and Kartik Nayak. 2021. Randpiper–reconfiguration-friendly random beacons with quadratic communication. In ACM CCS. 3502–3524.

[4] Vitalik Buterin et al. 2014. A next-generation smart contract and decentralized application platform. White Paper 3, 37 (2014), 2–1.

[5] Vitalik Buterin, Eric Conner, Rick Dudley, Matthew Slipper, Ian Norden, and Abdelhamid Bakhta. 2019. EIP-1559: Fee market change for ETH 1.0 chain. eips.ethereum.org/EIPS/eip-1559.

[6] Ruggiero Cavallo. 2006. Optimal Decision-Making With Minimal Waste: Strategyproof Redistribution of VCG Payments. In Proc. of the 5th Int. Joint Conf. on Autonomous Agents and Multi Agent Systems (AAMAS’06). Hakodate, Japan, 882–889. http://econcs.seas.harvard.edu/files/econcs/files/cavallo-redis.pdf

[7] Ruggiero Cavallo. 2008. Efficiency and Redistribution in Dynamic Mechanism Design. In Proc. 9th ACM Conf. on Electronic Commerce (EC’08). Chicago, IL, 220–229. http://econcs.seas.harvard.edu/files/econcs/files/cavallo-ec08.pdf

[8] Hao Chung and Elaine Shi. 2023. Foundations of transaction fee mechanism design. In ACM-SIAM SODA. 3856–3899.

[9] Edward Clarke. 1971. Multipart pricing of public goods. Public Choice 11, 1 (1971), 17–33.

[10] Sourav Das, Vinith Krishnan, Irene Miriam Isaac, and Ling Ren. 2022. Spurt: Scalable distributed randomness beacon with transparent setup. In IEEE S&P.

[11] Geoffroy de Clippel, Victor Naroditskiy, Maria Polukarov, Amy Greenwald, and Nicholas R. Jennings. 2014. Destroy to save. Games and Economic Behavior 86, C (2014), 392–404.

[12] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. 2019. Optimal auctions through deep learning. In ICML. PMLR, 1706–1715.

[13] Boi Faltings. 2005. A Budget-balanced, Incentive-compatible Scheme for Social Choice. In Agent-Mediated Electronic Commerce VI. Theories for and Engineering of Distributed Mechanisms and Systems: AAMAS 2004 Workshop, AMEC 2004. 30–43.

[14] Matheus V. X. Ferreira, Daniel J. Moroz, David C. Parkes, and Mitchell Stern. 2021. Dynamic posted-price mechanisms for the blockchain transaction-fee market. In ACM Conference on Advances in Financial Technologies (AFT). 86–99.

[15] Theodore Groves. 1973. Incentives in Teams. Econometrica 41, 4 (1973), 617–31.

[16] Sujit Gujar and Y. Narahari. 2011. Redistribution Mechanisms for Assignment of Heterogeneous Objects. J. Artif. Int. Res. 41, 2 (May 2011), 24. [17] Mingyu Guo. 2012. Worst-case Optimal Redistribution of VCG Payments in Heterogeneous-item Auctions with Unit Demand. In AAMAS. 745–752.

[18] Mingyu Guo and Vincent Conitzer. 2007. Worst-case Optimal Redistribution of VCG Payments. In ACM EC. 30–39.

[19] Mingyu Guo and Vincent Conitzer. 2008. Better Redistribution with Inefficient Allocation in Multi-unit Auctions with Unit Demand. In ACM EC. 210–219.

[20] Mingyu Guo and Vincent Conitzer. 2009. Worst-case optimal redistribution of VCG payments in multi-unit auctions. Games and Economic Behavior 67, 1 (2009), 69–98.

[21] Jason D. Hartline and Tim Roughgarden. 2008. Optimal Mechanism Design and Money Burning. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (Victoria, British Columbia, Canada) (STOC ’08). ACM, New York, NY, USA, 75–84. https://doi.org/10.1145/1374376.1374390

[22] Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. 2020. Order-fairness for byzantine consensus. In Annual International Cryptology Conference (CRYPTO). 451–480.

[23] Klaus Kursawe. 2020. Wendy, the good little fairness widget: Achieving order fairness for blockchains. In ACM Conference on Advances in Financial Technologies (AFT). 25–36.

[24] Padala Manisha, CV Jawahar, and Sujit Gujar. 2018. Learning Optimal Redistribution Mechanisms Through Neural Networks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. 345– 353.

[25] Eric Maskin, J. J. Laffont, and J. J. Laffont. 1979. A Differential Approach to Expected Utility Maximizing Mechanisms. North Holland, 289-308.

[26] Johnnatan Messias, Mohamed Alzayat, Balakrishnan Chandrasekaran, and Krishna P Gummadi. 2020. On Blockchain Commit Times: An analysis of how miners choose Bitcoin transactions. In The Second International Workshop on Smart Data for Blockchain and Distributed Ledger (SDBD2020).

[27] Herve Moulin. 2009. Almost budget-balanced VCG mechanisms to assign multiple objects. Journal of Economic Theory 144, 1 (2009), 96–119.

[28] Roger B Myerson and Mark A Satterthwaite. 1983. Efficient mechanisms for bilateral trading. Journal of economic theory 29, 2 (1983), 265–281.

[29] Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review (2008), 21260.

[30] Ariel Orda and Ori Rottenstreich. 2021. Enforcing fairness in blockchain transaction ordering. Peer-to-peer Networking and Applications 14, 6 (2021), 3660–3673.

[31] David C. Parkes, Jayant R. Kalagnanam, and Marta Eso. 2001. Achieving BudgetBalance with Vickrey-Based Payment Schemes in Exchanges. In Proc. 17th International Joint Conference on Artificial Intelligence (IJCAI’01). 1161–1168. http://econcs.seas.harvard.edu/files/econcs/files/combexch01.pdf

[32] Ryan Porter and Yoav Shoham. 2003. On cheating in sealed-bid auctions. In Proceedings of the 4th ACM conference on Electronic commerce. 76–84.

[33] Tim Roughgarden. 2021. Transaction Fee Mechanism Design. In ACM Conference on Economics and Computation (ACM EC). 792.

[34] Shoeb Siddiqui, Ganesh Vanahalli, and Sujit Gujar. 2020. BitcoinF: Achieving Fairness For Bitcoin In Transaction Fee Only Model. In AAMAS. 2008–2010.

[35] Corwin Smith. 2023. PROOF-OF-STAKE REWARDS AND PENALTIES. ethereum.org/en/developers/docs/consensus-mechanisms/pos/rewards-andpenalties/. [Online].

[36] Andrea Tacchetti, DJ Strouse, Marta Garnelo, Thore Graepel, and Yoram Bachrach. 2019. A neural architecture for designing truthful and efficient auctions. arXiv preprint arXiv:1907.05181 (2019).

[37] W. Vickrey. 1961. Counterspeculation, Auctions, and Competitive Sealed Tenders. Journal of Finance 16, 1 (March 1961), 8–37.

[38] YCHARTS. 2022. Bitcoin Transactions Per Day. ycharts.com/indicators/bitcoin_ transactions_per_day.

[39] YCHARTS. 2022. Ethereum Transactions Per Day. ycharts.com/indicators/ ethereum_transactions_per_day.

[40] Zishuo Zhao, Xi Chen, and Yuan Zhou. 2022. Bayesian-Nash-IncentiveCompatible Mechanism for Blockchain Transaction Fee Allocation. In Crypto Economics Security Conference (CESC).