Strategic Users in a Priority Queue with Bulk Service on Blockchains
arXiv:2606.01274v1 [q-fin.TR] 31 May 2026
Donghwa Seo∗ Samsung SDS
Kyoung-Kuk Kim† Korea Advanced Institute of Science and Technology
July 2025
Abstract This paper analyzes transaction fees on blockchains by considering that they form a priority queue and users play a queueing game. This modeling approach using M/GK /1 priority queue, we provide new insights into the dynamics governing transaction fees and its impact on user behavior. This work contributes to the literature in that we find semi-closed form expressions for steady-state quantities in the target queue and that the relationship between the delay cost of a user and the transaction fee (bid) is extended to the case of general block generation time. We apply our results to the Bitcoin network and simulate user responses under various scenarios. Cross-chain analysis across Bitcoin, Dogecoin, and Litecoin reveals similarities in normalized cost structures. Keywords: Queueing; Blockchain; Transaction fees; M/GK /1 queue; Prioritized queuing game
1
Introduction
The advent of blockchain technology has revolutionized decentralized systems, fostering the development of cryptocurrencies, decentralized exchanges, non-fungible tokens, and various decentralized applications. Public blockchains, in particular, offer distinct advantages: universal access, data integrity, decentralized operations, and transparent data that enhance trust. While such innovations ∗ †
Samsung SDS, Seoul, South Korea, E-mail: [email protected] Corresponding author, KAIST, College of Business, Seoul, South Korea, E-mail: [email protected]
1
and advantages are the core of a rapidly expanding industry, the focus of academic research has been more on system stability and system optimization. User interactions with blockchain services have been relatively less explored. From the users’ perspective in a public blockchain system, they experience a unique form of waiting. They broadcast transactions, hoping to be included in the next block. Since multiple transactions are processed in a new block, this procedure is akin to a queue served in bulk. Unlike fixed-price services, users bid for priority and transactions with higher bids (fees) are chosen earlier than transactions with lower bids. This real-time auction therefore incurs time-varying transaction costs because bids are relatively higher (lower) when trading intensity is higher (lower). Hence, the form of waiting of blockchain users can be thought of as a priority queue with bulk service. The study of blockchain queues but remains sparse. In this paper, we focus on Bitcoin, the representative cryptocurrency, and analyze user interactions with the blockchain via a queueing game approach. We aim to provide a better understanding of the transaction fee dynamics and users’ waiting costs, ultimately helping to resolve network congestion and to enhance network throughput. Our work was motivated by the emergence of BRC-20 in early 2023 which laid the technical foundation for non-fungible tokens to function on the Bitcoin network, enabling the development of associated applications. This expansion of functionality has led to increased network congestion and longer transaction queues. Our modeling approach is to see the blockchain queue as M/GK /1 queue. Transaction arrivals follow a Poisson process, block generation times have a general distribution with K transactions served in each block, and there is a single server. Based on the assumption that users make optimal bids associated with their waiting costs, we infer users’ cost structure from transaction data. For this, we extend the existing study on bulk queues and provide a new method of calculating expected waiting times and expected queue length. We believe that our results give new insights into users’ cost structure and strategic bidding behaviors. This also allows us to examine possible consequences of protocol changes or strategic actions of miners on user behaviors. For this purpose, we numerically test the effects of changes in the distribution of block generation time. Before we present our model in detail, the relevant literature is reviewed in the following paragraphs. Queueing approach. Bulk queues have been researched for many years, starting in the mid 20th century. Bailey [1954] studies the waiting time distribution of patients at a hospital where there is a maximum number that a medical consultant can see at a session. The service time distribution is modeled as χ2 distribution. Chaudhry and Templeton [1983] provide a comprehensive treatment of bulk queues, and their presentation of M/GK /1 is highly relevant to our model setup. There are more recent developments on bulk queues such as Claeys et al. [2013] or Banerjee et al. [2015]. Both papers look at batch arrivals and bulk services. The former focuses on the tail probabilities
2
of customer waiting whereas the latter is on steady state probabilities particularly when arrivals are Markovian and service times are of phase type. Such earlier papers on bulk queues have been applied to blockchains in recent years. Kawase and Kasahara [2017] and Kasahara and Kawahara [2019] present initial attempts to analyze transactionconfirmation time for Bitcoin and the impact of transaction fees. The authors use this same bulk queue model with Poisson arrivals and general service distribution. However, as pointed out in Li et al. [2018], their approach involves infinitely many unknown numbers so that actual implementation is restricted to the case of exponential service time. In order to circumvent this problem, Li et al. [2018] use a continuous time Markov process of GI/M/1 type. On the other hand, Queueing approach has been applied not only to transaction queues but also to blocks generated at blockchain nodes. Papadis et al. [2018] develop a stochastic model for such queues of minted blocks to study the impact of block dissemination delays. Transaction fees. The Bitcoin blockchain system rewards miners who successfully generate a new block with a fixed amount of Bitcoins. The total supply of Bitcoins is capped, and in the long run, the system will rely on transaction fees. For this reason, various aspects of fee dynamics and their implications have received increasing attention as the size of the network grows. Houy [2014] is an early work on transaction fees where the author considers a simple partial equilibrium model and a fee is viewed as the price for the block space. Möser and Böhme [2015] offer empirical aspects of transaction fees. They find that higher fees indeed result in faster confirmation and that impatient users offer higher fees. A more recent empirical work is Ilk et al. [2021]. This work specifies the inelastic nature of the demand curve of users whereas the supply (of block space) curve of miners is elastic to transaction fees. The recent literature on fees such as Lavi et al. [2022], Basu et al. [2023], Roughgarden [2024] reconsider transaction fee mechanisms. Game theoretic approach. To understand user behaviors on blockchains with transaction fees, game theoretic models have been employed to account for the prioritized mechanism in place. In fact, the strategic behavior of customers in queueing systems has been extensively studied in the context of congestion games or queueing games. Hassin and Haviv [2003] provide a comprehensive overview, detailing various models such as heterogeneous customers, competing servers, queues with reneging, and queues with priorities. More recent works include Dimitri [2019], Easley et al. [2019]. In Dimitri [2019], transaction fees are framed as a Nash equilibrium outcome of a congestion game, where the winning Bitcoin miner (who solves the puzzle) functions as an auctioneer. In Easley et al. [2019], users play the game of network participation and fee payment. By assuming that transactions flow in and flow out at fixed rates, the authors derive an equilibrium behavior of network participants and study the impact of microstructural features.
3
Huberman et al. [2021] is most relevant to our work. In their model, the transaction queue is represented as an M/MK /1 queue with fixed rates. This simplification gives us a closed form expression for the steady-state queue length distribution and expected waiting time. Here, the waiting time is computed for each user with delay cost or load parameter ρ. Based on this, users’ individual optimization leads to an equilibrium bidding strategy and to an equilibrium revenue for miners. We extend this framework to account for a general service time distribution. To do so, we develop a numerical procedure for computing the steady state distribution, addressing the issue identified by Li et al. [2018] mentioned above. Furthermore, we adopt the approach of Huberman et al. [2021] to infer the optimal bidding strategy and the hidden cost structure of users from transaction data. Our generalized model allows for comparisons of user behavior across different blockchains. This paper is structured as follows. Section 2 presents our model setup. In Section 3, we conduct the steady-state analysis of the transaction queue and compute relevant quantities such as expected queue length. Section 4 studies the optimal bidding strategy of individual users as a function of their delay costs so that we build a link between delay costs and transaction fees. In the section that follows, we consider the Bitcoin transaction data to infer users’ cost structure. Section 6 concludes the paper.
2
The Model
In a blockchain system with proof-of-work protocol, transaction requests are stored in the mempool, part of which are confirmed by the successful miner who generates a new block. Since users are impatient, their bids for transaction confirmation are positively associated with delay costs. This delay or waiting time of a user then depends on the level of congestion and the distribution of block generation time B. See Figure 1. Therefore, the final transaction fee collected by the winning miner is the outcome of individual user’s optimization based on the load parameter ρ, waiting cost ci with common distribution F , and block distribution FB . We note that the block distribution FB is also an outcome of collective operating decisions by miners. Since miners are motivated by economic rewards, they weigh rewards against costs and their strategic actions affect FB . For instance, Kim and Seo [2024] study a Nash equilibrium of miners’ actions and conclude that there is a possible mining gap, i.e. partial utilization of mining rigs, if the economic reward for mining is not sufficient. In our queueing theoretic analysis, we focus on the user side and treat the block distribution as given. However, we numerically test the impact of distributional changes of block generation time. Lastly, there is yet another important mechanism called difficulty adjustment in the system. This controls the winning probability so
4
Figure 1: Description of the system components and strategic decisions of users. as to make actual block generation times close to a certain target, i.e. 10 minutes for Bitcoin. Therefore, the combined effect of miners’ operating decisions, users’ bidding decisions, and the difficulty adjustment determines the transaction dynamics of a blockchain system. For our analysis, however, we assume fixed block distribution as well as fixed difficulty as we are interested in the steady-state analysis of the queue. To concentrate on the system’s fundamental dynamics, we make other assumptions as follows. First, transaction requests are uniform in size. Second, each block contains up to K transactions. Third, transaction arrivals follow a Poisson process with a fixed rate λ. Let us denote the mean block generation time by µ = E[B]. Then, we can define the load parameter by ρ = λµ/K. Fourth, ρ < 1 to make the queue stable in the long run. This allows us to see the queue as M/GK /1 as long as there is no delay in transaction propagation to the mempool. The queue size dynamics per se does not involve uers’ strategic actions as transactions are not treated differently. It is the fee dynamics where users’ delay cost structure, block distribution, and the load parameter ρ play together. For this, we make additional assumptions on the user side. Users are assumed to be aware of steady-state behaviors but they do not make real-time observations of the queue. Hence, optimal bidding decisions, bid bi by the i-th user, are made by considering the trade-off between the fee payment and the delay cost where this delay is the expected waiting time in the steady-state. In this setup, we closely follow Huberman et al. [2021]. Specifically, the utility of the i-th user is given by ui = −bi − ci Wi where Wi is the expected waiting time for a fee bi . A user exits the system if
5
the utility becomes excessively negative. Section 4 details the optimization of the user utility and finds the relationship between waiting cost and optimal bid.
3
Steady State Analysis
3.1
Limiting Distribution
This section analyzes a blockchain-inspired bulk service queue where transactions are processed in batches during block generation events. Unlike traditional bulk service queues, our model has no separate service station. Instead, up to K transactions from the mempool are processed instantaneously when a new block is created. Although the selection of transactions depends on transaction fees, the queue dynamics and queue length distributions do not depend on them. Hence, in this section, we aim to derive steady state equations for the limiting distribution of the queue length N (t) at time t. Since the service time distribution or block distribution FB is general, N (t) itself is not Markovian. However, by considering the time elapsed from the last block generation, say X(t), we have a Markovian random vector (N (t), X(t)) with the state space {(n, x)|n ∈ Z+ , x ≥ 0}. The dynamics of the system is visualized in Figure 2. At any point in time, there are three possible cases: no event, single transaction arrival, and block creation. Three sub-figures show how the state variables n and x change in each case. Figure 2a corresponds to the case of no event. The number in the queue stays the same but the time elapses by dt. On the other hand, if there is a transaction arrival prior to new block creation, then the time elapses by dt and the number in the queue increases by 1. Hence, the state variables n and x change simultaneously. Lastly, when there is a new block generated, the elapsed time falls from x to zero and the size of the queue in the mempool decreases by K at maximum. Let us first consider the embedded chain {Nk } defined by Nk = N (Tk −). Here, Tk is the generation time of the k-th block. Since arrivals are Markovian, {Nk } is a discrete-time Markov chain. It is a simple matter to check this process satisfies Nk = (Nk−1 − K)+ + Ak where Ak is the number of transaction arrivals between Tk−1 and Tk . Clearly, Ak is a Poisson random variable with mean λµ and it is independent of Nk−1 . The positive recurrence of {Nk } can be shown by the Foster-Lyapunov criterion. With a Lyapunov function specified by v(n) = n, the so called expected drift of v is ∆v(n) = E v(Nk ) − v(Nk−1 )|Nk−1 = n = λµ − min{K, n}. 6
(a) State variables increase in x with no block generation nor transaction arrival during (x, x + dt]
(b) State variables increase simultaneously with transaction arrival during (x, x + dt]
(c) State variables become (0, 0) or (n, 0) with block creation during (x, x + dt]
Figure 2: State transitions in the transaction queue where states are (number of transactions, elapsed time).
7
Due to our assumption that ρ = λµ/K < 1, we see ∆v(n) is negative for any n ≥ K. This negative drift outside a finite set ensures the positive recurrence of {Nk }. It is standard to argue that the process (N (t), X(t)) is also positive recurrent thanks to the fact that (N (t), X(t)) regenerates at Tk ’s in addition to the positive recurrence of {Nk }. Following Downton [1956], Chaudhry and Templeton [1983], we then derive differential equations that characterize stationary probabilities. For this, let us consider the density function πn (x) as the limit of πn (x, t) which is defined by πn (x, t)dx = P (N (t) = n, x < X(t) ≤ x + dx). Here πn (x, t)dx is the probability of having n in the system and the elapsed time since last block generation being in (x, x+dx]. From the Poisson arrival, we have the probaiblity λdx of new arrival as time elapses. We also have the probability η(x)dx of new block generation where η(x) is the conditional service rate or the hazard rate fB (x)/F̄B (x). Therefore, the likelihood πn (x + dx, t + dx) satisfies πn (x + dx, t + dx) = (1 − λdx)πn (x, t)(1 − η(x)dx) + λdx · πn−1 (x, t)(1 − η(x)dx) + o(dx) for n = 1, 2, . . .. Instead of solving this equation for (n, x, t), we are interested in limiting or equilibrium quantities as typically done in the analysis of queueing systems. Rearranging terms and given the existence of limiting distributions, we get dπn (x) = −(λ + η(x))πn (x) + λπn−1 (x). dx
(1)
For n = 0, we note that π0 (x + dx, t + dx) = (1 − λdx)π0 (x, t)(1 − η(x)dx) + o(dx) and this leads to dπ0 (x) = −(λ + η(x))π0 (x). dx
(2)
In addition to these differential equations, there are also boundary conditions for π0 (0) and πn (0) that are the limiting probabilities of π0 (0, t) and πn (0, t) right after new block generation. For the former, the event occurs whenever a new block is generated for the queue size less than or equal to K. Note that there is a possibility of an empty block. Hence, we have π0 (0) =
K Z ∞ X
πn (x)η(x)dx.
(3)
n=0 0
For the latter, the event of having n transactions in the queue at the time of block generation is relevant only when there are n + K transactions in the pre-completion queue. Therefore, Z ∞ πn (0) = πn+K (x)η(x)dx
(4)
0
for n = 1, 2, . . .. Lastly, the probability distribution {πn (x)} satisfies
P∞ R ∞ n=0 0
πn (x)dx = 1. Using
the above equations, we shall derive expressions for key performance metrics such as expected waiting time and expected queue length. For this, we calculate the probability generating function 8
Π(z; x) for the distribution {πn (x)} at elapsed time x. It is a variant of results found in Chapter 4 of Chaudhry and Templeton [1983]. We also notice that similar derivations are done in Kawase and Kasahara [2017] and Kasahara and Kawahara [2019]. The difference is that we have π0 (x) here because blocks are produced regardless of the presence of transaction requests.
Lemma 1 The probability generating function Π(z; x) =
∞ X
πn (x)z n for the queue length at elapsed
n=0
time x is given by Π(z; x) = Π(z; 0)F̄B (x)e−λ(1−z)x . PK
(z K −z n )
R∞
π (x)η(x)dx
n 0 with Π(1; 0) = µ−1 and β(t) is the Laplace transform Here, Π(z; 0) = n=0 z K −β(λ(1−z)) Z ∞ β(t) = e−tx fB (x)dx of the block generation time.
0
Proof: When we solve (2), we easily get π0 (x) = π0 (0)F̄B (x)e−λx . It is also easy to see that (1) yields −λx
πn (x) = e
Z x λs e F̄B (x) πn (0) + λ πn−1 (s)ds . 0 F̄B (s)
(5)
Then, we proceed as follows: Π(z; x) =
∞ X
πn (x)z n
n=0
! Z x λs ∞ X e πn−1 (s)ds z n = e F̄B (x) π0 (0) + πn (0) + λ F̄ (s) B 0 n=1 ! Z ∞ x λs X e zn = e−λx F̄B (x) Π(z; 0) + λz πn (s)ds . 0 F̄B (s) n=0 −λx
We used (5) in the second equality. In the third line of the equation, we replace πn (s) with the right hand side of (5) for n ≥ 1. For n = 0, the term is simply π0 (0)x. Then, we get Π(z; x) = e
−λx
F̄B (x) Π(z; 0) + λzxπ0 (0) + λz
∞ X
z
n=1 ∞ X
n
Z x
Z s πn (0) + λ
0
Z xZ s
0
! eλs1 πn−1 (s1 )ds1 ds F̄B (s1 ) !
eλs1 πn (s1 )ds1 ds F̄ (s ) 1 B 0 0 n=0 ! Z x Z sm−1 λsm ∞ m n X X e (λzx) + (λz)m+1 zn ··· πn (sm )dsm · · · ds = e−λx F̄B (x) Π(z; 0) n! F̄B (sm ) 0 0 n=0 n=0 = e−λx F̄B (x) Π(z; 0)(1 + λzx) + (λz)2
zn
= Π(z; 0)F̄B (x)e−λ(1−z)x . Here, the third equality is obtained by repeating the same argument. The last equality is then obtained by sending m to infinity. The convergence of the first term is trivial. The second term can
9
be shown to converge to zero by obtaining an upper bound as ∞ X
Z sm−1
Z x
eλsm πn (sm )dsm · · · ds F̄ (s ) m B 0 0 n=0 Z x Z sm−1 ∞ X eλs ≤ |λz|m+1 |z|n max ··· πn (sm )dsm · · · ds s∈[0,x] F̄B (s) 0 0 n=0 Z sm−2 Z ∞ Z x ∞ X eλs m+1 n πn (sm )dsm dsm−1 · · · ds ··· ≤ |λz| |z| max s∈[0,x] F̄B (s) 0 0 0 n=0 Z x Z sm−2 ∞ X eλs m+1 n ≤ |λz| |z| max ··· πn dsm−1 · · · ds s∈[0,x] F̄B (s) 0 0 n=0
|λz|m+1
≤ |λz|
|z|n
m+1
∞ X
···
eλs xm eλs xm πn = |λz|m+1 Π(|z|) max . s∈[0,x] F̄B (s) m! s∈[0,x] F̄B (s) m!
|z|n max
n=0
Here, πn =
R∞ 0
πn (x)dx and Π(z) is the probability generating function of {πn } which will be
formally introduced in the next subsection. It is clear that the right hand side converges to zero as m increases. As a consequence, the first claim in the statement of the lemma is proved. For the computation of Π(z; 0), we integrate Π(z; x) with respect to the hazard rate Z ∞ Z ∞ Π(z; x)η(x)dx = Π(z; 0) F̄B (x)e−λ(1−z)x η(x)dx 0 Z0 ∞ = Π(z; 0) e−λ(1−z)x fB (x)dx 0
= Π(z; 0)β(λ(1 − z)). On the other hand, the left hand side can also be written as Z ∞ Π(z; x)η(x)dx = 0
=
Z ∞X ∞ 0
n=0
K X
n
z
πn (x)η(x)dx + 0
=
=
=
=
n=0 K X n=0 K X n=0 K X n=0
z
n
∞ X
Z ∞
n=0 K X
πn (x)z n η(x)dx
Z ∞ πn (x)η(x)dx + z
K
z
Z ∞
πn (x)η(x)dx + z K
0
zn
Z ∞
∞ X n=1 ∞ X
Z ∞ πn (x)η(x)dx 0
n=K+1
0 n
z
n
z
n
Z ∞ πn+K (x)η(x)dx 0
z n πn (0)
n=1
πn (x)η(x)dx + z K Π(z; 0) − π0 (0)
0 n
z −z
K
Z ∞ 0
10
πn (x)η(x)dx + z K Π(z; 0).
Here, (4) is used in the fourth equality and (3) in the last equality. By equating the two expressions above, we obtain
R∞ z K − z n 0 πn (x)η(x)dx . z K − β(λ(1 − z))
PK Π(z; 0) =
n=0
It remains to show Π(1; 0) = µ−1 . The probability distribution {πn } satisfies
P∞
n=0 πn = 1.
Therefore, we have 1 = lim
z→1
∞ Z ∞ X
πn (x)z n dx
n=0 0 Z ∞
= lim
Π(z; x)dx
z→1 0
= Π(1; 0) lim
z→1
1 − β(λ(1 − z)) λ(1 − z)
= Π(1; 0)µ where the third equality uses the integration by parts and the last equality is obtained by L’Hôpital’s rule.
3.2
Expected Queue Length
The queue dynamics may be summarized by the queue length distribution and its mean. By integrating the limiting distribution with respect to the elapsed time, we get the probability of having n R∞ transactions in the mempool at equilibrium, i.e. πn := 0 πn (x)dx for n = 0, 1, . . .. The associated P n probability generation function is defined by Π(z) = ∞ n=0 πn z . Then, observe that ∞ Z ∞ X Π(z) = πn (x)z n dx n=0 Z ∞
0
Π(z; x)dx Z ∞ = Π(z; 0) F̄B (x)e−λ(1−z)x dx =
0
0
1 − β(λ(1 − z)) = Π(z; 0) . λ(1 − z) Here, it is implicitly assumed that the integral on the right hand side of the third equality is finite. One sufficient condition, for example, is lim inf x→∞ η(x) > 0 so that the last equality is valid for z < 1 + ε for some sufficiently small positive ε. The expected queue length is then computed by Π′ (1). Since the mean block generation time µ and the maximum capacity K are assumed to be fixed in the blockchain network, we view the expected queue length as a function of the load parameter ρ and write Q(ρ) = Π′ (1) 11
d 1 − β(λ(1 − z)) dz z=1 λ(1 − z) λ = Π′ (1; 0)µ + Π(1; 0) E B 2 2 2 ρK σ = Π′ (1; 0)µ + 1+ 2 2 µ = Π′ (1; 0)µ + Π(1; 0)
where σ 2 is the variance of the block generation time B and Π(1; 0) is given in Lemma 1. The lemma also shows Π(z; 0)D(z) =
K X
z
K
−z
n
Z ∞ πn (x)η(x)dx
(6)
0
n=0
where D(z) = z K − β(λ(1 − z)) for notational simplicity. By directly differentiating the both sides twice, then one readily obtains a closed form expression for Π′ (1; 0). Nevertheless, it involves the R∞ computation of 0 πn (x)η(x)dx for n = 0, 1, . . . , K − 1. It dates back to 50’s when those values are found by searching for roots of D(z) on and within the unit circle on the complex plane. See Bailey [1954]. However, as pointed out in Oblakova et al. [2019], it is not trivial to find such zeros without any closed-form expression. Approximate methods may pose a problem as the precision of such values has a high impact. In our case, the scale itself is a challenge as K is typically several thousands. Instead, we adopt the proposed method of Oblakova et al. [2019] who apply their idea to discrete-time queueing systems with traffic applications. Proposition 1 There exists a sufficiently small ε such that D(z) has no zero in the annulus {z ∈ C : 1 < |z| ≤ 1 + ε} whereas there are K − 1 solutions in {z ∈ C : |z| < 1}. With such ε, the expected queue length is then given by Z π ′ 1 D (z(φ)) z(φ) ρK σ2 Q(ρ) = dφ + 1+ 2 2π −π D(z(φ)) 1 − z(φ) 2 µ where z(φ) = (1 + ε)eiφ . Proof: For any z ∈ C on the circle of radius r > 1, say Sr , we observe Z ∞ Z ∞ −λ(1−z)x |β(λ(1 − z))| ≤ |e fB (x)|dx = e−λx(1−r cos φ) fB (x)dx 0
0
R∞ where z = reiφ . This is in turn less than or equal to 0 e−λx(1−r) fB (x)dx = β(λ(1 − r)). Using |z K | = rK on Sr , we have the relationship D(r) = rK − β(λ(1 − r)). Note that D(1) = 0 and D′ (1) = K − λµ = (1 − ρ)K. Since we assume that the system is not eplosive or ρ < 1, we have D′ (1) > 0 and thus D(r) > 0 for any r sufficiently close to 1. For such r, we have |β(λ(1−z))| < |z K | on Sr . Then, by Rouché’s Theorem (one version of which we cite below to make the presentation self-contained), we conclude z K and D(z) have the same number of zeros, i.e. K, inside Sr , counting multiplicities. 12
Lemma 2 (Rouché’s Theorem) Suppose two complex valued functions f and g are analytic inside some region U with a simple closed contour ∂U . If |g(z)| < |f (z)| on ∂U , then f and f + g have the same number of zeros inside U , counting multiplicities. Due to the analyticity of D(z), its zeros are isolated. In particular, there are finitely many zeros on the compact set {z ∈ C : 1 ≤ |z| ≤ r} for any r > 1. Thus by selecting a sufficiently small ε > 0, we can assure that any zero of D(z) on {z ∈ C : 1 ≤ |z| ≤ 1 + ε} has the radius 1. Clearly, D(1) = 0. For z ̸= 1 on the unit circle, we note Z ∞ e−λx(1−cos φ) fB (x)dx |β(λ(1 − z))| ≤ 0
is strictly less than |z K | = 1 with z = eiφ . Hence, z = 1 is the only solution of D(z) = 0 on the unit circle. Further, we already noted above that D′ (1) > 0. This implies that the multiplicity of z = 1 is 1. Consequently, there are K − 1 solutions to D(z) = 0 within the unit circle and a simple unique solution z = 1 on the unit circle. Now we are ready to apply the solution procedure proposed in Oblakova et al. [2019]. To be specific, let {zi }K−1 i=1 be the K − 1 roots of D(z) = 0 in the interior of the unit ball. We also define Pk R ∞ ak = n=0 0 πn (x)η(x)dx, the partial sum of the unknowns for k = 0, 1, . . . , K − 1. Then, it P n is easy to see that the right hand side of (6) is equal to (z − 1) K−1 n=0 an z . Since D(zi ) = 0 for i = 1, . . . , K − 1, it must be that K−1 X
n
an z = aK−1
n=0
K−1 Y
(z − zi ).
i=0
This expression further yields K−1
K−1
Y z−1 aK−1 Y aK−1 (1 − zi ) = (1 − zi ). z→1 D(z) (1 − ρ)K
Π(1; 0) = lim
i=0
i=0
Since Π(1; 0) = µ−1 from Lemma 1, we get aK−1 = µ−1 (1 − ρ)K
QK−1
−1 and finally, i=0 (1 − zi )
K−1
Π(z; 0) =
(1 − ρ)K(z − 1) Y z − zi . µ D(z) 1 − zi i=1
The computation of the expected queue length Q(ρ) requires Π′ (1; 0). For this, define h(z) = QK−1 z−zi i=1
1−zi for convenience, and observe
Π′ (1; 0) = =
(1 − ρ)K D(z) − (z − 1)D′ (z) 1 lim · h(1) + h′ (1) 2 z→1 µ D(z) µ " # K−1 ′ 1 D(z) − (z − 1)D (z) X 1 (1 − ρ)K lim + z→1 µ D(z)2 1 − zi i=1
13
=
=
" # K−1 D′′ (z) X 1 1 1 − lim ′ + µ 2 z→1 D (z) 1 − zi i=1 " # K−1 2 X 1 σ 1 1 Kρ2 1 + 2 − (K − 1) + . µ 2(1 − ρ) µ 1 − zi i=1
We utilize a lemma of Oblakova et al. [2019], which we state below for the reader’s convenience. Lemma 3 (Oblakova et al. [2019]) Consider a function F (z) that is analytic in a neighborhood D′ (z) of zi , where i = 0, · · · , K − 1. Then, the residue of the function F (z) at zi is equal to D(z) D′ (z) F (z)(z − zi ) = mzi F (zi ) z→zi D(z) lim
where mzi is the multiplicity of the root zi . Treating S1+ε as a closed curve with counterclockwise orientation, the Residue Theorem says that H ′ (z) 1 the contour integral S1+ε D D(z) 1−z dz is equal to 2πi times the sum of residues at zi ’s for i = 1, . . . , K − 1 as well as the residue at z = 1. Lemma 3 then implies I D′ (z) 1 1 dz = (residue at 1) + h′ (1). 2πi S1+ε D(z) 1 − z The residue at 1 is found by repeatedly applying L’Hôpital’s rule and given as follows: d D′ (z) 1 2 residue at 1 = lim (z − 1) z→1 dz D(z) 1 − z D′′ (1) = − ′ 2D (1) 1 σ2 2 = Kρ 1 + 2 − (K − 1) . 2(1 − ρ) µ Consequently, we obtain a succinct expression 1 Π (1; 0) = 2πiµ ′
D′ (z) 1 dz. S1+ε D(z) 1 − z
I
By re-writing z = (1 + ε)eiφ for −π < φ ≤ π, we get the desired result. The above proposition provides us with a numerical tool to evaluate the expected queue length when the block generation time is different from the benchmark Bitcon network. More specifically, we infer user behaviors or cost structure based on the Bitcoin network, and then utilize the result for optimal bidding strategies in other blockchain networks.
14
4
Strategic Bidding
The previous section on expected queue length does not distinguish transaction requests in the mempool. However, miners in the network naturally select transactions with highest possible fees to maximize rewards given the constraint on the block size. In this sense, users compete with each other to make their transactions complete. Each user must determine the level of bidding by gauging the delay cost and the level of congestion. For this purpose, we need a model for the user’s optimal decision. The main reference we follow is Huberman et al. [2021] in which the net reward for the i-th user with delay cost ci is given by Ri − bi − ci Wi where Ri is the willingness-to-pay, bi is the bid, and Wi is the expected waiting time of the user. Here ci is the cost per unit time until the user’s transaction goes through. Also, Ri is the benefit for the user in using the blockchain network over other alternatives that fulfill the same objective of the transaction. In Huberman et al. [2021], Ri is assumed to be either low or high value and it is not correlated with the cost ci . As such, this is non-essential for our purpose of studying the user behavior through bidding data, hence we only consider the utility of the form −bi − ci Wi . In this queueing game where higher priorities are earned by higher bids, the expected waiting time Wi is given by a function of the bid, say W(bi ). When the user decides the bid optimally, we can even further write bi as a function of ci , say bi = b(ci ) so that the net reward for the i-th user can be re-written as −b(ci ) − ci W(b(ci )). In addition, users are heterogeneous so that their delay costs c’s are assumed to have a cumulative distribution F with density f . Since it is natural to think of the optimal bidding at equilibrium as a strictly increasing and continuous function of c, this leads to the distribution of bids b’s, say G with density g. This means that P(c > ci ) = F̄ (ci ) whereas P(c > ci ) = P(b > b(ci )) = Ḡ(b(ci )). Here c, b are the random delay cost and equilibrium bid of the user population. When the i-th user arrives at the mempool with the equilibrium bid, the user sees the arrival rate of higher bids equal to λḠ(b(ci )) = λF̄ (ci ). For the rest of the paper, we assume that F and G are continuous and strictly increasing for analytical tractability. We in addition make a notational change. Since each user experiences different levels of congestion due to priority, we use ρ̄ = λµ/K the maximum possible load for the whole queue and leave ρ for the generic load parameter. If we define a function ρ(ci ) as the load parameter for the blockchain queue with arrival rate λF̄ (ci ), then ρ(ci ) = ρ̄F̄ (ci ) with state space [0, ρ̄]. Since this function is continuous and invertible, we can assign the i-th user the corresponding load parameter, say ρi = ρ(ci ). In other words, the priority of the i-th user in the original priority queue is represented by the load parameter ρi where a lower value means a higher priority. We also note that any randomly selected user has a load parameter ρ(c) for the random delay cost. This
15
implies that P(ρ(c) ≤ ρi ) = P(ρ(c) ≤ ρ(ci )) = P(c ≥ ci ) = F̄ (ci ) = ρi /ρ̄. In other words, ρ(c) has a uniform distribution on [0, ρ̄]. For our M/GK /1 queuing of transactions but with the load parameter ρi , the expected waiting time for any user with the load parameter between 0 and ρi is given as Q(ρi )/(λF̄ (ci )) by Little’s Law. Abusing notation, let us use W(ρ) for the expected waiting time that any user with paritcular priority ρ experiences. Since priorities are uniformly distributed and F̄ (ci ) = ρi /ρ̄, we obtain Z 1 ρi ρ̄Q(ρi ) Q(ρi ) = W(ρ)dρ. = λρi ρi 0 λF̄ (ci ) This implies that W(ρi ) = = = where I(ρi , φ) =
h
d D′ (z(φ)) dρi D(z(φ))
i
z(φ) 1−z(φ)
i d h ρ̄ Q(ρi ) dρi λ µ ′ Q (ρi ) K Z π µ σ2 µ 1+ 2 + I(ρi , φ)dφ 2 µ 2πK −π for notational simplicity. In our numeical implementation,
this function is calculated for a given block generation time distribution and enters into the above formula for numerical integration. Our ultimate goal is to understand uers’ optimal bidding strategy b. For the reader’s convenience, we summarize the procedure to arrive at the final expression of the function. First of all, recall that the user with delay cost ci has the utility −bi − ci W(bi ) where bi is the bid of the i-th user, not necessarily optimal. Then, the first order condition to maximize the utility gives us the relationship d 1 W=− . db b=b(ci ) ci
(7)
On the other hand, the relationship between b, ρ, F and G implies that d W = db b=b(ci )
d dρ W· dρ ρ=ρ(ci ) db b=b(ci ) d ρ̄f (ci ) = − W· ′ . dρ ρ=ρ(ci ) b (ci )
Consequently, the desired formula is obtained by Z ci d Wdc. b(ci ) = ρ̄ cf (c) dρ ρ=ρ(c) 0 Here, we assume b(0) = 0, i.e., zero bid when there is no impact of transaction delay. Integration by parts then yields Z ci b(ci ) = −ci W(ρ(ci )) +
W(ρ(c))dc 0
16
= −
µci 2πK
Z π I(ρ(ci ), φ)dφ + −π
µ 2πK
Z ci Z π I(ρ(c), φ)dφdc. 0
−π
Huberman et al. [2021] derive a closed-form expression for W, using an exponential distribution for the block generation time. In our case of general distribution, the computation of b is only slightly more involved but makes it possible to test various possibilities. For instance, the block generation time may have a very small variation with the target time 12 seconds as in the Ethereum network, or there may be a mining gap due to operating burden on miners as argued in Carlsten et al. [2016]. Please see Section 5 for details. Kim and Seo [2024] study the strategic behaviors of miners in a blockchain network with the proof-of-work consensus protocol. Miners are motivated to solve a complex puzzle for economic rewards consisting of block reward (e.g. 3.125 BTC at the time of this writing) and the accumulated fees for transactions in a new block. The next proposition guages this portion of economic incentives as a function of the elapsed time since the last block generation. We remind the reader that Π(z; x) is actually a function of the load parameter or priority level ρ. For the sake of simplicity, we define ξ(ρ) = Π′ (1; 0) and ξ(ρ; x) = Π′ (1; x). Proposition 2 The expected accumulated fee on the event that a block is generated by time x is given by
Z Z ρ̄K x ∞ b(c)f (c)dc × y F̄B (y)dy m(c (y))F̄B (y)dy + 2 µ 0 c∗ (y) 0 ρ̄ R ∞ R π ∗ where m(u) = 2πµ −π I(ρ(c), φ)b(c)f (c)dφdc and c (x) is a solution to ξ(ρ(c); x) = KfB (x), u Z x
∗
if exists; otherwise, c∗ (x) = 0. Proof: By definition, we have ξ(ρ) = Π′ (1; 0) =
1 2πµ
D′ (z) z dφ. −π D(z) 1 − z
Z π
Lemma 1 implies that ξ(ρ; x) = Π′ (1; 0)F̄B (x) + λxΠ(1; 0)F̄B (x) ρK = ξ(ρ)F̄B (x) + 2 xF̄B (x). µ This function represents the expected queue length of all the bids of the users whose delay costs are larger than or equal to c such that ρ(c) = ρ, i.e. ξ(ρ; x)dx = E[N ; x < X ≤ x + dx]. A miner is assumed to collect the best K bids in the mempool, and such bids are transaction requests with delay cost greater than or equal to c∗ or priority less than or equal to ρ∗ = ρ(c∗ ) where ξ(ρ∗ ; x) = KfB (x). We note that there might be no solution for given x if the maximum load parameter ρ̄ is small. In such a case, a miner would collect all of the existing bids and we set c∗ (x) = 0. 17
Now we observe that the expected number of bids with corresponding delay costs in (c, c + dc) when X ∈ (x, x + dx] is given by ξ(ρ(c + dc); x) − ξ(ρ(c); x) = ξ ′ (ρ(c); x)ρ′ (c)dc. Since all such bids are close to b(c), the expected fee for such bids is given by b(c)ξ ′ (ρ(c); x)ρ′ (c)dc. Consequently, Z ∞ R(x) = c∗ (x) Z ∞
b(c)ξ ′ (ρ(c); x)ρ̄f (c)dc
Z ∞ ρ̄K = b(c)ξ (ρ(c))ρ̄f (c)dc × F̄B (x) + 2 xF̄B (x) · b(c)f (c)dc. µ c∗ (x) c∗ (x) R∞ Note that m(c∗ (x)) = c∗ (x) b(c)ξ ′ (ρ(c))ρ̄f (c)dc. By integrating this quantity over the interval [0, x], ′
we get the desired result.
The function R(x) in the proof is the expected fees on the event X ∈ (x, x+dx]. The conditional expected fee given X = x is therefore obtained by dividing R(x) by fB (x). For instance, the amount of initial expected fees from which the total fees start to accumulate is m(c∗ (0))/fB (0). On the other hand, a simple upper bound of R(x) is given by R(0)F̄B (x) +
ρ̄K xF̄B (x)E[b]. µ2
Here we use the property that c∗ (x) is increasing in x. Therefore, the total expected fees until the new block generation is bounded above by Z ∞ Z ∞ ρ̄K σ2 ρ̄K R(0) F̄B (x)dx + 2 E[b] xF̄B (x)dx = R(0)µ + 1 + 2 E[b]. µ 2 µ 0 0 It is worth noting that this is close to the true value in Proposition 2 as K increases to infinity. Hence, we may use the bound as an approximation to the desired quantity as long as the service size K is large enough. For a last comment before we move onto numerical experiments, we see that the total expected fee for a miner for a large K consists of the R(0) part accumulated over the block generation time B and the expected bid E[b] part from the number of bids in the queue, i.e. Q(ρ̄).
5
Numerical Analysis
In this section, we apply theoretical results in previous sections to the Bitcoin network. We specifically target the derivation of users’ delay cost structure, and see how users would react to changes in block distribution. Furthermore, we test how such delay cost structures differ across chains. In doing so, the equation (7) is essential. We provide details in the following subsections. 18
5.1
Cost Distribution of Bitcoin Users
(a) Block time distribution
(b) Block time stability
(c) Fee distribution
Figure 3: Bitcoin network characteristics in 2023 We analyze Bitcoin network data from 2023 to understand the empirical characteristics of block generation and transaction processing. The network generated 53,852 blocks during this period, processing approximately 153.4 million transactions. The model parameter K is computed by dividing the block size by the average transaction size, and it is 2,922. For the parameter ρ̄, we divide the average number of transactions per block by K, and it is 0.97462. These values represent the actual throughput of the Bitcoin network and form the basis of our waiting cost analysis. The empirical analysis of the Bitcoin network is shown in Figure 3. The block time distribution in Figure 3a plots the empirical block generation intervals, where block time is calculated as ti − ti−1 for timestamp ti of block i. The straight dashed line represents the density of the exponential 19
distribution with mean 600 seconds in log scale. This theoretical model aligns well with the observed block time distribution. Figure 3b presents the moving average of block generation times using a window size of 2016 blocks, corresponding to Bitcoin’s difficulty adjustment period. The average annual block time has remained stable around 10 minutes throughout the year, so we set µ = 10 in our model. Figure 3c shows the smoothed probability density of logarithmic transaction fees per 1,000 weight unit (KWU) in USD. It exhibits two distinct peaks and this suggest the presence of user groups with different sensitivities to transaction costs.
(a) Cost-bid relationship
(b) Cost distribution
(c) Normalized cost distribution
Figure 4: The cost structure of Bitcoin users As explained at the beginning of this section, we directly estimate the bid-cost relationship using Equation (7). Recall W = W(ρi ) for the i-th user. Also recall that the load parameter ρi at equilibrium satisfies ρi = ρ(ci ) = ρ̄F̄ (ci ) = ρ̄Ḡ(b(ci )). Given the actual fees and their empirical distribution function, we can apply the finite difference method to the left hand side of (7) using 20
the formula of W by bumping bi (and thus ρi ) up and down. Figure 4a presents the empirical relationship between fees and costs. More specifically, blue dots are pairs of an actual fee and the corresponding cost estimate. In order to ensure the monotonicity of cost versus fee (or vice versa), we apply the cubic spline method by suitably discretizing the x-axis. The red curve in the figure shows the fitted curve. It clearly shows nonlinearity with costs sharply rising for larger fees. Figure 4b gives the empirical density of estimated costs. Note costs are in USD per KWU and per minute. Due to the bimodal feature of the fee distribution in Figure 3c, the cost distribution has two peaks as well at 10−4 and 10−2 approximately. To better reflect users’ waiting cost and to make the cross-chain analysis useful, we introduce the concept of normalized cost by taking into account transaction specific attributes. Each transaction request is assigned a weight which captures computational and storage requirements (other networks in our paper use the storage requirement only). The transfer amount of each request may impact the bid because users are presumably sensitive to the value of the transaction. Lastly, we also adjust costs by expected block time because block generation times are different across chains. As a result, we apply cnormalized =
expected block time × c. transfer amount × weight
This standardization measures the user cost per USD transferred per weight or size during a single block generation time. The resulting distribution in Figure 4c shows a markedly different pattern from the previous cost structure. The normalized cost distribution exhibits a unimodal shape with its peak near 0.1, spanning a wider range from -10 to 8 in log scale. This normalization demonstrates that the bimodality in the distribution of cost per KWU emerges from transaction-specific parameters rather than underlying user preferences.
(a) Total cost decomposition
(b) Cost ratio analysis
Figure 5: Analysis of total cost
21
Users’ total costs are composed of this explicit transaction fee and the expected waiting cost, that is, b + cW. As seen in Figure 5a, we see the relative contribution of fee and waiting cost to the total cost. When a user has a high cost greater than 100 USD/KWU·min, the waiting cost is a dominant factor whereas fees are dominant for low cost users (less than 0.01 USD/KWU·min). See Figure 5b. One possible explanation is that high cost users optimize their transaction requests by strategic bidding.
5.2
Optimal Response in Bidding
Having established the empirical cost structure F , we are now able to see how our model yields optimal bids if there is any change in block distribution FB . The baseline scenario of the Bitcoin network is that the block distribution is exponential with mean 10 minutes. Let us consider different block distributions with the same mean. More specifically, we use the gamma distribution Γ(α, α/10) parameterized by shape parameter α and rate parameter α/10. The mean stays at 10 but the variance 100/α. We choose three cases: high variance (α = 0.2, variance=500), moderate variance (α = 1 or exponential, variance=100), and low variance (α = 5, variance=20). The block distribution converges to a constant block distribution time as α → ∞, which is included as a limiting case. Figure 6 shows three computational results. From Figure 6a, we see optimal bidding strategies in terms of cost. The high variance case (α = 0.2) exhibits significantly higher bids across all cost levels, particularly for users with high delay costs. This suggests that the increased uncertainty in block generation time makes users bid higher to minimize the total cost. In the limiting case, users make the lowest and mostly constant bid at different cost levels. This is a predictable outcome because users can precisely predict transaction confirmation times in this extreme case. This decreasing pattern of variability in bidding as α increases is also found in the cumulative distribution of bids in Figure 6b. The observation that higher variability in B results in larger bids and thus to larger total costs is re-confirmed in the last panel. The analysis reveals that block time uncertainty significantly impacts optimal bidding strategies, with higher variance leading to more aggressive bidding behavior. However, it is also seen that such responses to variability in block distribution are disproportionate at different cost levels. In order to understand such patterns in response better, we examine two other scenarios. First, we examine the impact of mining delay, which might happen due to optimal strategic choices of miners [Carlsten et al., 2016, Kim and Seo, 2024]. Second, the impact of increased average block generation time is studied. This might occur due to difficulty attacks as seen in the Bitcoin vs Bitcoin Cash hash power competition or external shocks (e.g. mining restrictions in major mining regions).
22
(a) Cost-bid relationship
(b) Bid distribution
(c) Comparison of total costs
Figure 6: Impact of block time distribution on transaction costs The first scenario is implemented by imposing constant delays (baseline or no gap, 4 minutes, 8 minutes, and 10 minutes) in block generation. The results are shown in Figure 7. The left panel shows a systematic decline in bidding as the mining gap increases. With no mining gap, the expected fee per KWU is 2.87 USD, which drops to 0.61 USD with a 4-minute gap and further decreases to 0.033 USD with an 8-minute gap. This decline reflects the reduced willingness of users to pay high fees for static delays. The variance in bids is also significantly reduced as shown in the right panel. This indicates that mining gaps lead to more predictable and compressed fee markets, potentially harming the effectiveness of fee-based transaction prioritization. Considering that mining gaps may occur due to insufficient mining rewards, this reduced fee may exacerbate the situation. The second scenario is implemented by varying the mean parameter µ of the exponential distribution while maintaining its memoryless property. Figure 8 delivers the same information of 23
(a) Cost-bid relationship
(b) Bid distribution
Figure 7: Impact of mining gaps on transaction costs
(a) Cost-bid relationship
(b) Bid distribution
Figure 8: Impact of extended block times on transaction costs cost-bid relationship and bid distribution as in previous figures. The left panel demonstrates that longer block times lead to systematically higher optimal bids across all cost levels. As µ increases from 10 (baseline case) to 30 minutes, the mean bid rises from 2.45 USD to 732.93 USD. This substantial increase is in stark contrast of the significant decrease in the first scenario where users experience a fixed delay. The right panel can also be compared with Figure 7b. Optimal bidding becomes more homogeneous as the mean block generation time increases, and the coefficient of variation changes from 1.087 in the baseline case to 0.155 at µ = 30. These findings have implications for blockchain security and protocol design. Different block distributions have different impacts on optimal bidding. When there is a larger uncertainty or 24
larger mean waiting time, bid levels are higher. This could impose substantial costs on network users in terms of waiting time and transaction fee, potentially threatening the network’s utility as a payment system. When there is a mining gap, on the other hand, bid levels are lower but this might lead to insufficient economic rewards for miners. Lastly, the increased homogeneity in bidding behavior under large mining gaps or extended block generation times indicates a potential reduction in the fee market’s ability to effectively prioritize transactions based on urgency.
5.3
Cross Chain Analysis
(a) LTC block time distribution
(b) DOGE block time distribution
(c) Block time stability comparison
Figure 9: Block time characteristics across networks We extend our analysis to other major Proof-of-Work cryptocurrencies to examine how different network parameters affect fee market dynamics. We focus on Litecoin (LTC), and Dogecoin 25
(DOGE), analyzing their transaction data throughout the year 2023. These networks have different design parameters: LTC targets 2.5-minute blocks with K=1,384 and DOGE aims for 1-minute blocks with K=2,597. The corresponding utilization rates (ρ̄) are 0.2291 and 0.1076 respectively. The block time distributions (Figures 9a-9b) closely follow exponential distributions when normalized by their respective target times, confirming the memoryless property of the mining process across different networks. Figure 9c illustrates the stability of the average block time over the course of 2023. In contrast, Dogecoin consistently exhibits a deviation of approximately 7%. This is presumed to be due to the fact that the target block time is as short as one minute, and the physical network propagation time (approximately three seconds) has a greater impact.
(a) Fee ECDF comparison
(b) Fee density comparison
Figure 10: Fee distributions across networks The fee structures exhibit considerable heterogeneity across networks, stemming from their distinct transaction architectures and prioritization mechanisms. While Bitcoin employs weight units for transaction prioritization, Litecoin and Dogecoin utilize physical size. Despite these differences, fee per KB metrics are available across all networks, enabling cross-chain comparison as shown in Figure 10a. The empirical cumulative distribution functions and density plots reveal markedly different fee patterns across these networks. The density distributions demonstrate substantial divergence in fee structures, with no apparent commonalities across chains. Bitcoin exhibits a relatively concentrated distribution with a primary peak around 101 fee-per-KB, while Litecoin shows a bimodal pattern with peaks at approximately 10−3 and 10−2 . Dogecoin displays the most distinctive pattern with a sharp, concentrated peak at 10−2.5 . We apply the same procedure as done for the Bitcoin network to retrieve the hidden cost structure. The normalized cost distributions in Figure 11 reveal similarities in the underlying cost structures across networks, despite their different fee patterns. All three networks show a primary 26
Figure 11: Normalized cost structures across networks concentration of user activity around normalized costs of 10−1 to 101 , suggesting common patterns in user behavior when transaction-specific attributes are accounted for. While sharing fundamental similarities, each network exhibits distinctive characteristics in their detailed structure. Notably, Dogecoin displays an additional mode around 107 in the normalized cost distribution, attributable to its minimum fee requirements (0.01 DOGE dust limit, 0.001 DOGE/kB) that might affect smallvalue transactions. Litecoin similarly shows a secondary peak at higher cost levels, reflecting the impact of minimum fee constraints rather than queue congestion.
6
Conclusion
This paper has investigated transaction fees and their implications in decentralized networks, particularly Proof-of-Work based blockchain systems. Through our queueing based modeling and analysis, we conducted an analysis of a priority queue with bulk service and applied the result to understand strategic user behaviors in bidding transaction fees. Central to our investigation, more specifically, was the adoption of the M/GK /1 priority queue model to represent the blockchain queue. This study contributes to the literature on the queueing approach to blockchain systems in that, first, a concrete semi-closed form expressions for steady-state quantities such as expected queue length are presented and, second, the hidden delay cost structure of blockchain users is presented when the block generation time has a general distribution.
27
To be more specific, we find that estimating waiting time in steady-state distribution is instrumental in pinpointing optimal fees for users across various queue scenarios. Our analysis of normalized transaction costs across different blockchain networks reveals remarkably similar underlying cost structures, suggesting common patterns in user behavior despite varying network parameters and congestion levels. This finding provides empirical supports for our theoretical framework linking delay costs to optimal bidding strategies. Furthermore, our approach enables us to predict how users would react to a change in blockchain characteristics. We demonstrated that users would bid higher fees if there is a higher uncertainty in block generation time but bid less if there is a fixed gap in block generations. Nevertheless, this work has limitations. One such limitation is our model’s exclusion of posttransaction fee modification strategies like Child-Pays-for-Parent and Replace-by-Fee. These strategies allow users to elevate their transactions’ priority post submission, introducing additional layers of complexity to queue dynamics that our current model does not address. Notwithstanding these limitations, we believe this study advances our understanding of the intricate relationship between block generations, transaction fee dynamics, and the hidden delay cost structure of users. The insights from the study should be helpful for refining fee mechanisms and for enhancing efficiency and fairness on blockchains.
Acknowledgement This work was supported by the National Research Foundation of Korea (NRF) funded by the Korea Government (MSIT) under Grant RS-2023-00278082 and by the Institute of Information & Communications Technology Planning & Evaluation (IITP)-Global Data-X Leader HRD program grant funded by the Korea government (MSIT) (IITP-RS-2024-00440626).
Disclosure of Interest There are no relevant financial or non-financial competing interests to report.
Disclaimer The work of Donghwa Seo was completed prior to joining Samsung SDS. The views and conclusions expressed herein are those of the authors and do not necessarily reflect any policy or position of Samsung SDS.
28
References N. T. J. Bailey. On queueing processes with bulk service. Journal of the Royal Statistical Society: Series B (Methodological), 16(1):80–87, 1954. A. Banerjee, U. C. Gupta, and S. R. Chakravarthy. Analysis of a finite-buffer bulk-service queue with multiple servers and batch Markovian arrival process. Computers & Operations Research, 60:138–149, 2015. S. Basu, D. Easley, M. O’Hara, and E. G. Sirer. StableFees: A predictable fee market for cryptocurrencies. Management Science, 69(11):6508–6524, 2023. M. Carlsten, H. Kalodner, S. M. Weinberg, and A. Narayanan. On the instability of Bitcoin without the block reward. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 154—-167, 2016. M. L. Chaudhry and J. G. C. Templeton. A First Course in Bulk Queues. Wiley, 1983. D. Claeys, B. Steyaert, J. Walraevens, K. Laevens, and H. Bruneel. Tail probabilities of the delay in a batch-service queueing system with batch-size dependent service times and a timer mechanism. Computers & Operations Research, 40(5):1497–1505, 2013. N. Dimitri. Transaction fees, block size limit, and auctions in Bitcoin. Ledger, 4, 2019. F. Downton. On limiting distributions arising in bulk service queues. Journal of the Royal Statistical Society Series B: Statistical Methodology, 18(2):265–274, 1956. D. Easley, M. O’Hara, and S. Basu. From mining to markets: The evolution of bitcoin transaction fees. Journal of Financial Economics, 134(1):91–109, 2019. R. Hassin and M. Haviv. To Queue or Not To Queue: Equilibrium Behavior in Queueing Systems. Springer, 2003. N. Houy. The economics of Bitcoin transaction fees. 2014. Working Paper. G. Huberman, J. D. Leshno, and C. Moallemi. Monopoly without a monopolist: An economic analysis of the Bitcoin payment system. Review of Economic Studies, 88(6):3011–3040, 2021. N. Ilk, G. Shang, S. Fan, and J. L. Zhao. Stability of transaction fees in Bitcoin: A supply and demand perspective. MIS Quarterly, 45(2):563–592, 2021. S. Kasahara and J. Kawahara. Effect of Bitcoin fee on transaction-confirmation process. Journal of Industrial & Management Optimization, 15(1):365, 2019.
29
Y. Kawase and S. Kasahara. Transaction-confirmation time for Bitcoin: A queueing analytical approach to blockchain mechanism. In W. Yue, Q.-L. Li, S. Jin, and Z. Ma, editors, Queueing Theory and Network Applications, pages 75–88, 2017. K. Kim and D. Seo. Mind the gap in the mining game. 2024. Working Paper. R. Lavi, O. Sattath, and A. Zohar. Redesigning Bitcoin’s fee market. ACM Transactions on Economics and Computation, 10(1):Article 5, 2022. Q.-L. Li, J.-Y. Ma, and Y.-X. Chang. Blockchain queue theory. In X. Chen, A. Sen, W. W. Li, and M. T. Thai, editors, The 7th International Conference on Computational Data and Social Networks, pages 25–40, 2018. M. Möser and R. Böhme. Trends, tips, tolls: A longitudinal study of Bitcoin transaction fees. In International Conference on Financial Cryptography and Data Security, pages 19–33, 2015. A. Oblakova, A. Al Hanbali, R. J. Boucherie, J. C. W. van Ommeren, and W. H. M. Zijm. An exact root-free method for the expected queue length for a class of discrete-time queueing systems. Queueing Systems, 92:257–292, 2019. N. Papadis, S. Borst, A. Walid, M. Grissa, and L. Tassiulas. Stochastic models and wide-area network measurements for blockchain design and analysis. In IEEE Conference on Computer Communications, pages 2546–2554, 2018. T. Roughgarden. Transaction fee mechanism design. Journal of the ACM, 71(4):Article 30, 2024.
30