Document Open Access Logo

Designing Multidimensional Blockchain Fee Markets

Authors Theo Diamandis, Alex Evans, Tarun Chitra, Guillermo Angeris

PDF
Thumbnail PDF

File

LIPIcs.AFT.2023.4.pdf
  • Filesize: 0.83 MB
  • 23 pages

Document Identifiers

Author Details

Theo Diamandis
  • MIT CSAIL, Cambridge, MA, USA
Alex Evans
  • Bain Capital Crypto, San Francisco, CA, USA
Tarun Chitra
  • Gauntlet, New York, NY, USA
Guillermo Angeris
  • Bain Capital Crypto, San Francisco, CA, USA

Acknowledgements

We would like to thank John Adler, Vitalik Buterin, Dev Ojha, Kshitij Kulkarni, Matheus Ferreira, Barnabé Monnot, and Dinesh Pinto for helpful conversations, insights, and edits. We're especially appreciative to John Adler for bearing with us through many drafts of this work and consistently providing valuable feedback.

Cite AsGet BibTex

Theo Diamandis, Alex Evans, Tarun Chitra, and Guillermo Angeris. Designing Multidimensional Blockchain Fee Markets. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.AFT.2023.4

Abstract

Public blockchains implement a fee mechanism to allocate scarce computational resources across competing transactions. Most existing fee market designs utilize a joint, fungible unit of account (e.g., gas in Ethereum) to price otherwise non-fungible resources such as bandwidth, computation, and storage, by hardcoding their relative prices. Fixing the relative price of each resource in this way inhibits granular price discovery, limiting scalability and opening up the possibility of denial-of-service attacks. As a result, many prominent networks such as Ethereum and Solana have proposed multidimensional fee markets. In this paper, we provide a principled way to design fee markets that efficiently price multiple non-fungible resources. Starting from a loss function specified by the network designer, we show how to dynamically compute prices that align the network’s incentives (to minimize the loss) with those of the users and miners (to maximize their welfare), even as demand for these resources changes. We derive an EIP-1559-like mechanism from first principles as an example. Our pricing mechanism follows from a natural decomposition of the network designer’s problem into two parts that are related to each other via the resource prices. These results can be used to efficiently set fees in order to improve network performance.

Subject Classification

ACM Subject Classification
  • Theory of computation → Convex optimization
  • Information systems → Digital cash
  • Theory of computation → Algorithmic mechanism design
Keywords
  • Blockchains
  • transaction fees
  • convex optimization
  • mechanism design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. John Adler. Eip-2242: Transaction postdata, 2019. URL: https://eips.ethereum.org/EIPS/eip-2242.
  2. John Adler. Multi-threaded data availability on eth 1. Ethresearch, 2019. URL: https://ethresear.ch/t/multi-threaded-data-availability-on-eth-1/5899.
  3. John Adler. Accounts, strict access lists, and UTXOs - research / execution, 2020. URL: https://forum.celestia.org/t/accounts-strict-access-lists-and-utxos/37.
  4. John Adler. Wait, it’s all resource pricing? EthCC, 2021. URL: https://www.youtube.com/watch?v=YoWMLoeQGeI.
  5. John Adler. Always has been (or, wait, it’s all resource pricing? part 2). EthCC, 2022. URL: https://www.youtube.com/watch?v=Zq8uwpX39oI.
  6. Akshay Agrawal, Stephen Boyd, Deepak Narayanan, Fiodar Kazhamiaka, and Matei Zaharia. Allocation of fungible resources via a fast, scalable price discovery method. Mathematical Programming Computation, pages 1-30, 2022. Google Scholar
  7. Mustafa Al-Bassam. LazyLedger: A distributed data availability ledger with client-side smart contracts. CoRR, abs/1905.09274, 2019. URL: https://arxiv.org/abs/1905.09274.
  8. Mustafa Al-Bassam, Alberto Sonnino, and Vitalik Buterin. Fraud and data availability proofs: Maximising light client security and scaling blockchains with dishonest majorities, 2018. URL: https://doi.org/10.48550/ARXIV.1809.09044.
  9. Dimitri P Bertsekas. Nonlinear Programming. Athena Scientific, 3 edition, 1999. Google Scholar
  10. Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral Shah. Julia: A fresh approach to numerical computing. SIAM review, 59(1):65-98, 2017. Google Scholar
  11. Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. Google Scholar
  12. Vitalik Buterin. Eip 150: Gas cost changes for io-heavy operations, 2016. URL: https://eips.ethereum.org/EIPS/eip-150.
  13. Vitalik Buterin. Geth nodes under attack again, 2016. URL: https://www.reddit.com/r/ethereum/comments/55s085/geth_nodes_under_attack_again_we_are_actively/?st=itxh568s&sh=ee3628ea.
  14. Vitalik Buterin. Transaction spam attack: Next steps, 2016. URL: https://blog.ethereum.org/2016/09/22/transaction-spam-attack-next-steps/.
  15. Vitalik Buterin. Easy parallelizability issue #648 ethereum/EIPs, 2017. URL: https://github.com/ethereum/EIPs/issues/648.
  16. Vitalik Buterin. First and second-price auctions and improved transaction-fee markets, 2018. URL: https://ethresear.ch/t/first-and-second-price-auctions-and-improved-transaction-fee-markets/2410.
  17. Vitalik Buterin. An incomplete guide to rollups, 2021. URL: https://vitalik.ca/general/2021/01/05/rollup.html.
  18. Vitalik Buterin. Multidimensional eip 1559. Ethresearch, 2022. URL: https://ethresear.ch/t/multidimensional-eip-1559/11651.
  19. Vitalik Buterin. Proto-danksharding FAQ, 2022. URL: https://notes.ethereum.org/@vbuterin/proto_danksharding_faq.
  20. Vitalik Buterin. State of research: Increasing censorship resistance of transactions under proposer/builder separation (pbs), 2022. URL: https://notes.ethereum.org/@vbuterin/pbs_censorship_resistance.
  21. Vitalik Buterin, Eric Conner, Rick Dudley, Matthew Slipper, Ian Norden, and Abdelhamid Bakhta. Eip-1559: Fee market change for eth 1.0 chain, 2019. URL: https://eips.ethereum.org/EIPS/eip-1559.
  22. Vitalik Buterin and Martin Swende. Eip-2929: Gas cost increases for state access opcodes, 2020. URL: https://eips.ethereum.org/EIPS/eip-2929.
  23. Vitalik Buterin and Martin Swende. EIP-2930: Optional access lists, 2020. URL: https://eips.ethereum.org/EIPS/eip-2930.
  24. Yang Chen, Zhongxin Guo, Runhuai Li, Shuo Chen, Lidong Zhou, Yajin Zhou, and Xian Zhang. Forerunner: Constraint-based speculative transaction execution for ethereum (full version). In SOSP '21: ACM SIGOPS 28th Symposium on Operating Systems Principles, Virtual Event / Koblenz, Germany, October 26-29, 2021. ACM, 2021. URL: https://doi.org/10.1145/3477132.3483564.
  25. Hao Chung and Elaine Shi. Foundations of transaction fee mechanism design. arXiv preprint arXiv:2111.03151, 2021. Google Scholar
  26. Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In 2020 IEEE Symposium on Security and Privacy (SP), pages 910-927. IEEE, 2020. Google Scholar
  27. Theo Diamandis, Alex Evans, Tarun Chitra, and Guillermo Angeris. Dynamic pricing for non-fungible resources: Designing multidimensional blockchain fee markets. arXiv preprint arXiv:2208.07919, 2022. Google Scholar
  28. Iain Dunning, Joey Huchette, and Miles Lubin. Jump: A modeling language for mathematical optimization. SIAM review, 59(2):295-320, 2017. Google Scholar
  29. Ethereum. Gas and fees, 2022. URL: https://ethereum.org/en/developers/docs/gas/.
  30. Ethereum. Run a node, 2022. URL: https://ethereum.org/en/run-a-node/.
  31. Matheus Ferreira, Daniel Moroz, David Parkes, and Mitchell Stern. Dynamic posted-price mechanisms for the blockchain transaction-fee market. In Proceedings of the 3rd ACM conference on Advances in Financial Technologies, pages 86-99, 2021. Google Scholar
  32. John Forrest, Stefan Vigerske, Ted Ralphs, Lou Hafer, John Forrest, jpfasano, Haroldo Gambini Santos, Matthew Saltzman, Jan-Willem, Bjarni Kristjansson, h-i gassmann, Alan King, pobonomo, Samuel Brito, and to st. coin-or/clp: Release releases/1.17.7, January 2022. URL: https://doi.org/10.5281/zenodo.5839302.
  33. Rati Gelashvili, Alexander Spiegelman, Zhuolun Xiang, George Danezis, Zekun Li, Yu Xia, Runtian Zhou, and Dahlia Malkhi. Block-STM: Scaling blockchain execution by turning ordering curse to a performance blessing, 2022. URL: https://doi.org/10.48550/ARXIV.2203.06871.
  34. Sepp Hochreiter. The vanishing gradient problem during learning recurrent neural nets and problem solutions. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 6(02):107-116, 1998. Google Scholar
  35. Qi Huangfu and JA Julian Hall. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119-142, 2018. Google Scholar
  36. Frank Kelly. Charging and rate control for elastic traffic. European transactions on Telecommunications, 8(1):33-37, 1997. Google Scholar
  37. Kshitij Kulkarni, Theo Diamandis, and Tarun Chitra. Towards a theory of maximal extractable value i: Constant function market makers, 2022. URL: https://arxiv.org/abs/2207.11835.
  38. Fuel Labs. GitHub - FuelLabs/fuel-specs: Specifications for the fuel protocol and the FuelVM, a blazingly fast blockchain VM, 2022. URL: https://github.com/FuelLabs/fuel-specs.
  39. Stefanos Leonardos, Barnabé Monnot, Daniël Reijsbergen, Efstratios Skoulakis, and Georgios Piliouras. Dynamical analysis of the eip-1559 ethereum fee market. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pages 114-126, 2021. Google Scholar
  40. Stefanos Leonardos, Daniël Reijsbergen, Daniël Reijsbergen, Barnabé Monnot, and Georgios Piliouras. Optimality despite chaos in fee markets. arXiv preprint arXiv:2212.07175, 2022. Google Scholar
  41. Steven Low. A duality model of tcp and queue management algorithms. IEEE/ACM Transactions On Networking, 11(4):525-536, 2003. Google Scholar
  42. Steven Low and David Lapsley. Optimization flow control. i. basic algorithm and convergence. IEEE/ACM Transactions on networking, 7(6):861-874, 1999. Google Scholar
  43. Kamilla Nazirkhanova, Joachim Neu, and David Tse. Information dispersal with provable retrievability for rollups, 2021. URL: https://doi.org/10.48550/ARXIV.2111.12323.
  44. Daniel Perez and Benjamin Livshits. Broken metre: Attacking resource metering in evm. arXiv preprint arXiv:1909.07220, 2019. Google Scholar
  45. Polygon Team. Introducing avail by polygon‚ a robust general-purpose scalable data availability layer, 2021. URL: https://blog.polygon.technology/introducing-avail-by-polygon-a-robust-general-purpose-scalable-data-availability-layer/.
  46. Kaihua Qin, Liyi Zhou, and Arthur Gervais. Quantifying blockchain extractable value: How dark is the forest? arXiv preprint arXiv:2101.05511, 2021. Google Scholar
  47. Daniël Reijsbergen, Shyam Sridhar, Barnabé Monnot, Stefanos Leonardos, Stratis Skoulakis, and Georgios Piliouras. Transaction fees on a honeymoon: Ethereum’s eip-1559 one month later. In 2021 IEEE International Conference on Blockchain (Blockchain), pages 196-204. IEEE, 2021. Google Scholar
  48. Tim Roughgarden. Transaction fee mechanism design. SIGecom Exch., 19(1):52-55, 2021. URL: https://doi.org/10.1145/3476436.3476445.
  49. Vikram Saraph and Maurice Herlihy. An empirical study of speculative concurrency in ethereum smart contracts, 2019. URL: https://doi.org/10.48550/ARXIV.1901.01376.
  50. Naum Zuselevich Shor. Minimization methods for non-differentiable functions, volume 3. Springer Series in Computational Mathematics, 1985. Google Scholar
  51. Ertem Nusret Tas, Dionysis Zindros, Lei Yang, and David Tse. Light clients for lazy blockchains, 2022. _eprint: 2203.15968. Google Scholar
  52. Jeffrey Wilcke. The ethereum network is currently undergoing a DoS attack, 2016. URL: https://blog.ethereum.org/2016/09/22/ethereum-network-currently-undergoing-dos-attack/.
  53. Anatoly Yakovenko. Sealevel‚ parallel processing thousands of smart contracts, 2020. URL: https://medium.com/solana-labs/sealevel-parallel-processing-thousands-of-smart-contracts-d814b378192.
  54. Anatoly Yakovenko. Consider increasing fees for writable accounts issue #21883 solana-labs/solana, 2021. URL: https://github.com/solana-labs/solana/issues/21883.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact