:::info
Authors:
(1) Yotam Gafni, Weizmann Institute ([email protected]);
(2) Aviv Yaish, The Hebrew University, Jerusalem ([email protected]).
:::
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
Abstract
Decentralized cryptocurrencies are payment systems that rely on aligning the incentives of users and miners to operate correctly and offer a high quality of service to users. Recent literature studies the mechanism design problem of the auction serving as a cryptocurrency’s transaction fee mechanism (TFM).
We find that a non-myopic modelling of miners falls close to another well-known problem: that of online buffer management for packet switching. The main difference is that unlike packets which are of a fixed size throughout their lifetime, in a financial environment, user preferences (and therefore revenue extraction) may be time-dependent. We study the competitive ratio guarantees given a certain discount rate, and show how existing methods from packet scheduling, which we call “the undiscounted case”, perform suboptimally in the more general discounted setting. Most notably, we find a novel, simple, memoryless, and optimal deterministic algorithm for the semi-myopic case, when the discount factor is up to ≈ 0.770018. We also present a randomized algorithm that achieves better performance than the best possible deterministic algorithm, for any discount rate.
1 Introduction
We study the problem of scheduling transactions with deadlines. In this problem, an algorithm is tasked with scheduling transactions, each represented by its deadline t, also known as its time to live (TTL), and its value ϕ, with the goal of maximizing the value of transactions that are scheduled before their TTL ends. The number of transactions which can be scheduled at any given time is limited and the algorithm is unaware of the future schedule of transactions.
This formulation can be applied to a variety of settings, where our main interest lies in a blockchain miner’s decision to allocate transactions to size limited blocks [Rou20], but a rich literature exists that studies this problem in the context of packet scheduling, ride-sharing, and so on. In the blockchain setting, a transaction’s value is the fee the miner can collect by allocating it, and its TTL is a user defined parameter that specifies the time window within which it can be included in a block, after which it expires and does not incur fees. Notably, Ethereum users can submit expiring transactions using service providers such as Flashbots [fla23], with certain blockchains supporting this functionality by default, like Zcash [Gra18].
Importantly, miners may have a preference to obtaining profits earlier rather than later, as these can be used to increase future profits, for example by depositing them as stake, or in other interestbearing instruments. This means that the value of transactions that are allocated in the future should be discounted. We show that solutions explored by previous literature, while enjoying good performance in the undiscounted case, need to be adapted, or will otherwise perform suboptimally in the discounted setting.
1.1 Our Approach
There are two aspects that require consideration when analyzing the decision-making problem for miners in TFMs. One, which is not discussed here, is that of strategic manipulations: either by the users (“shading” the transaction fees they bid), or by the miners, that may deviate from the intended allocation protocol. Though we do not explicitly incorporate the latter in the model, the implications of our results for this point are discussed in further detail in Section 5. The other uncertainty, which is the focus of this work, is miners’ limited knowledge of future transactions. We find that a competitive ratio analysis is a natural method to study this problem [BE05].
We consider a model where users have a single-minded value, composed of a fee they are willing to pay, and a deadline within which the transaction needs to be accepted to be valuable. Miners apply a discount rate to future revenue. Each transaction’s fee thus “decays” by a global discount factor λ < 1 at each time step until the transaction expires. This models the preference of a miner to receive revenue earlier rather than later, as dependent on the economy’s interest rate. Specifically in cryptocurrencies, miners may use “early” revenue to increase mining profits, for example by using it as stake in Proof-of-Stake (PoS) protocols, or to purchase additional mining equipment. Such considerations were not accounted for in the TFM literature thus far, but are common in the economic literature, in particular in the study of repeated auctions [DMSW21] and of the economic aspects of blockchains [SU19; PW21; YZ20; YTZ22]. Another discount factor we should consider is the miner ratio, as a miner may know with certainty that they will get the revenue of the upcoming transaction, but only have a probability α of mining any other future block. Interestingly, the miner ratio α, which is natural in blockchain settings, fits the notion of “present bias” as used in behavioral economics (see, e.g., [KOR16; OR15]). A present biased agent has a preference for utility in the current step, over future steps. Though our motivation is not behavioral, our analysis ends up being applicable for this possibility of present bias.
:::info
This paper is available on arxiv under CC BY 4.0 DEED license.
:::
