An Incentive Mechanism for Sustainable Blockchain Storage

We consider the set of miners as $\mathcal{M}=\{1,\cdots,M\}$.⁹⁹9We analyze the system in a quasi-static state [13][28][31]. That is to say, there are no users or miners joining or leaving the system. The normalized mining power (e.g., computing power in proof of work) of miner $m\in\mathcal{M}$ is $\alpha_{m}>0$, which represents the probability of miner $m$ successfully finding a block. We have $\sum_{m\in\mathcal{M}}\alpha_{m}=1$.

Each miner $m$ selects a set $\mathcal{X}_{m}^{k}\subseteq\mathcal{Q}^{k}$ of transactions from the transaction pool $\mathcal{Q}^{k}$. For the ease of analysis, we assume that a block can contain at most one transaction.¹⁰¹⁰10This assumption characterizes the reality of block size limit, which has been adopted in [13][14]. Blockchain platform IOTA adopts the one transaction per block rule [32]. Considering multiple transactions per block means that each miner’s strategy space becomes multi-dimensional, making the problem much more challenging to solve. We will relax this assumption in future work. Thus miner $m$’s strategy satisfies $|\mathcal{X}_{m}^{k}|\in\{0,1\}$. As transactions vary in both sizes and fees, we adopt a benign assumption where each miner either selects the highest fee-per-byte transaction from the transaction pool or selects no transaction, which is consistent with the empirical studies [23][33]. Existing fee recommendation softwares also follow this rule [34][35].

To simplify the description, we use $\mathcal{X}_{m}^{k}=\{(n,i)\}$ (or $\emptyset$) to represent that miner $m$ selects $tx_{n,i}$ (or no transaction) in round $k$.

Miners’ payoff functions: Miner $m$’s payoff depends on both the transaction fee and storage cost.¹¹¹¹11We do not consider the block reward and the cost of running the mining machine since they are not affected by each miner’s transaction selection. Besides, the transaction fees are the key to cover blockchain storage costs as the block reward gradually shrinks.

• •

  Transaction fee: For a transaction $tx_{n,i}$, its transaction fee is the product of the transaction size and fee-per-byte, i.e., $s_{n,i}\rho_{n,i}$. Only the miner who successfully finds a block receives the transaction fees from his selection. Thus miner $m$ will get the total transaction fees of $\sum_{(n,i)\in{\mathcal{X}_{m}^{k}}}{s_{n,i}\rho_{n,i}}$ with probability $\alpha_{m}$.

• •

  Storage cost: For analysis, we assume that all miners have homogeneous storage cost of $C_{s}$ per byte, representing that miners use similar storage technology. We will consider the impact of the heterogeneous storage costs numerically in Section VII-C. Storing a transaction $tx_{n,i}$ with size $s_{n,i}$ imposes a storage cost $s_{n,i}C_{s}$ to a miner. If any miner $j\in\mathcal{M}$ selects transaction $tx_{n,i}$ (i.e., $\mathcal{X}_{j}^{k}=\{(n,i)\}$) and successfully finds a block (with probability $\alpha_{j}$), all miners need to store that block and bear the storage costs $s_{n,i}C_{s}$ for the transaction $tx_{n,i}$ that miner $j$ selects [3]. Overall, miner $m$ will bear the storage costs of

  $$C^{k}(\mathcal{X}_{m}^{k},\bm{\mathcal{X}}_{-m}^{k})=\sum\limits_{j\in\mathcal{M}}\alpha_{j}\sum\limits_{(n,i)\in{\mathcal{X}_{j}^{k}}}s_{n,i}C_{s}$$

  (1)

  in round $k$,¹²¹²12We neglect the storage costs of non-transaction data since it is very small. For example, on June 2nd, 2020, the average block size of Bitcoin is 1.284 MB and non-transaction data in a block takes up less than 1 KB. https://www.blockchain.com/charts/avg-block-size. where $\bm{\mathcal{X}}_{-m}^{k}=(\mathcal{X}_{j}^{k},\forall j\in\mathcal{M},j\not=m)$ represents the strategies of all the miners other than $m$. Miner $m$’s storage costs in (1) reveals the negative externality in transaction selection: when a miner selects a transaction and finds a block, it imposes storage costs to all the other miners.

Combining the transaction fee and storage cost, miner $m$’s payoff in round $k$ is:

We formulate the round $k$ of mining as a non-cooperative game, where miners simultaneously select the transactions (to be included in his block) to maximize their own payoffs.

In Game 1, each miner tradeoffs between the transaction fee and storage cost to maximize his payoff, considering the strategies of other miners. Specifically, on the one hand, miner $m$ gets high revenue for selecting a high-fee transaction and finding a block. Meanwhile, for the highest-fee-per-byte transaction, if its fee is lower than its storage cost, a miner may still select it if all the other miners select it and he will eventually bear the storage cost of it.

We denote the set of users as $\mathcal{N}=\{1,\cdots,N\}$. Given two fee-per-byte choices $\overline{\rho}$ and $\underline{\rho}$ offered by the protocol designer, each user $n\in\mathcal{N}$ generates transactions at each choice following a Poisson process. The strategy of user $n$ is to set the transaction generation rates ${\bm{\lambda}_{n}}=(\lambda_{n1},\lambda_{n2})$, where $\lambda_{n1}$ and $\lambda_{n2}$ are the rates of user $n$ generating transactions at $\overline{\rho}$ and $\underline{\rho}$, respectively, satisfying the following constraints:

where $\mu$ is the system average block generation rate and each user’s maximum transaction generation rate is $\frac{\mu}{N}$. Constraint (5) ensures that it is feasible to include all generated transactions from all users in the blockchain (if the miners choose to do so in Stage III).

Here we define the waiting time of any transaction $tx_{n,i}$ as the time lapse between the generation time and the on-chain time.

• •

  Generation time of transaction $tx_{n,i}$ is denoted as $t^{\rm gen}_{n,i}$.

• •

  On-chain time: When a miner selects transaction $tx_{n,i}$ and finds a block in round $k(=1,2,\cdots)$, then round $k$ ends, and transaction $tx_{n,i}$ is included in the blockchain. Thus, round $k$’s ending time $t^{\rm end}(k)$ is the transaction on-chain time, i.e.,

  $$t^{\rm on}_{n,i}=\begin{cases}t^{\rm end}(k),&\text{if $tx_{n,i}$ is included in block $k$,}\\ \infty,&\text{if $tx_{n,i}$ is not included in any block.}\end{cases}$$

  (6)

• •

  Waiting time is the difference between the on-chain time minus and the generation time, i.e., $w_{n,i}=t^{\rm on}_{n,i}-t^{\rm gen}_{n,i}$. Waiting time $w_{n,i}$ is a random variable as the block generation is stochastic. The rate of transactions entering the transaction pool affects the waiting time $w_{n,i}$, thus it is a function of all users transaction generation rates, i.e., $\bm{\lambda}=(\bm{\lambda}_{n},\forall n\in\mathcal{N})$. We will compute the expectation of $w_{n,i}$ in Lemma 1 of Section V-B.

Negative externality in transaction generation: When user $n$ generates a transaction and miners include it in the blockchain, other transactions in the transaction pool have to wait. Thus, user $n$’s transactions increase the average waiting time of all the other users’ transactions. If a user maximizes his own payoff without considering the negative externality, all the other users will experience excessive waiting time. This motivates us to propose the waiting tax to let each user internalize such a negative externality.

User $n$’s surplus obtained from one transaction $tx_{n,i}$ depends on whether $tx_{n,i}$ is included in the blockchain.

• •

  If $tx_{n,i}$ is included in the blockchain: The surplus depends on the on-chain utility from one transaction, transaction fee, waiting time cost, and waiting tax.

  • –

    User $n$’s on-chain utility from $tx_{n,i}$: When $tx_{n,i}$ is included in the blockchain, user $n$ will obtain utility of $R_{n}$. For example, a user gets a certain level of utility when successfully purchasing a kitty in Ethereum-based game cryptokitties. To model the users’ heterogeneity of utilities, we consider two user types: with $N_{H}$ high-utility users (type-$H$) and $N_{L}=N-N_{H}$ low-utility users (type-$L$).¹³¹³13Two applications can capture heterogeneous users set transaction fee to compete for shorter waiting time. Thus, user $n$’s on-chain utility from one transaction is

    $$R_{n}=\begin{cases}R_{H},&\text{if user $n$ is type-$H$,}\\ R_{L},&\text{if user $n$ is type-$L$,}\\ \end{cases}\vspace{-1mm}$$

    (7)

    where $R_{H}\geqslant R_{L}$. Our model generalizes the homogeneous utility model in [13] and [14].

  • –

    Transaction fee of $tx_{n,i}$: User $n$ pays the transaction fee $f_{n,i}=s_{n,i}\rho_{n,i}$ to the miner who includes $tx_{n,i}$ in the blockchain. We model the size of any transaction follows an i.i.d. distribution with the expectation of $\bar{s}$. The fee-per-byte $\rho_{n,i}$ belongs to the protocol designer’s fee-per-byte choices, i.e., $\rho_{n,i}\in\{\overline{\rho},\underline{\rho}\}$.

  • –

    Waiting time cost of $tx_{n,i}$: The transaction waiting time $w_{n,i}(\bm{\lambda})$ imposes a cost to user $n$, which we assume to be a linear function with the impatience coefficient $\gamma$, i.e., $\gamma w_{n,i}(\bm{\lambda})$. A higher $\gamma$ means users are less patient.

  • –

    Waiting tax of $tx_{n,i}$: Since user $n$’s transaction generation increases the expected transaction waiting time of any other user $l\not=n$, we introduce the waiting tax $p_{nl}$ to internalize this negative externality. More specifically, user $n$ pays user $l$ the amount of $p_{nl}$ to compensate the waiting costs $n$ imposes. Depending on the types of users $n$ and $l$, the possible waiting tax has four different values $\bm{P}=(P_{HH},P_{HL},P_{LH},P_{LL})$:

    $$p_{nl}=\begin{cases}P_{HH},&\text{if both user $n$ and $l$ are type-$H$,}\\ P_{HL},&\text{if user $n$ is type-$H$ and user $l$ is type-$L$,}\\ P_{LH},&\text{if user $n$ is type-$L$ and user $l$ is type-$H$,}\\ P_{LL},&\text{if both user $n$ and $l$ are type-$L$.}\\ \end{cases}\vspace{-1mm}$$

    (8)

  To sum up, user $n$’s surplus when $tx_{n,i}$ is included in the blockchain is

  $$\theta_{n,i}(\bm{\lambda},\bm{\rho},\bm{P})=R_{n}-s_{n,i}\rho_{n,i}-\gamma w_{n,i}(\bm{\lambda})-\sum\limits_{l\in\mathcal{N},l\not=n}p_{nl}.\vspace{-1mm}$$

  (9)

• •

  If $tx_{n,i}$ is not included in the blockchain (i.e., not in any block), user $n$ will not get the transaction on-chain utility $R_{n}$, and he will not pay the fee $f_{n,i}$ or the waiting tax. However, user $n$ still experiences the (possibly infinite) waiting time to know that the transaction will not be included. In this case, user $n$’s surplus from transaction $tx_{n,i}$ is

  $$\theta_{n,i}(\bm{\lambda},\bm{\rho},\bm{P})=-\gamma w_{n,i}(\bm{\lambda}).\vspace{-2mm}$$

  (10)

To simplify the formulation, we define the indicator function to indicate whether $tx_{n,i}$ is included in the blockchain as follows

Hence user $n$’s surplus obtained from $tx_{n,i}$ can be written as

User $n$’s payoff is the summation of the surplus from all his transactions and the waiting tax paid to him by other users. For user $n$, we denote the number of all his generated transactions in time interval $[0,t]$ as $TX_{n}(t)$. His time-average payoff is

where $\mathbb{E}[\theta_{n,i}(\bm{\lambda},\bm{\rho},\bm{P})]$ is user $n$’s expected surplus from transaction $tx_{n,i}$. The expectation is taken in terms of random variables transaction size $s_{n,i}$ and waiting time $w_{n,i}$.

We formulate users’ transaction generation as a non-cooperative game, where users set transaction generation rates simultaneously to maximize their own payoffs.¹⁴¹⁴14Here we assume that each user does not consider the influence of his strategic decision on other users (i.e., each user is a price taker). This assumption holds for a blockchain system with many users.

In Game 2, each user faces a tradeoff between paying a high fee and suffering a high transaction waiting time. Since miners prefer to include transactions with high fees, user $n$ will experience a lower average waiting time by generating more high-fee transactions. However, if paying a high fee is too costly, user $n$ would be better off by generating more low-fee transactions and bearing a higher average waiting time.

According to miners’ equilibrium strategies in Stage III, the process of transaction arriving (i.e., users generating transactions) and leaving (i.e., miners including transactions in blockchain) is a two-class M/M/1 queue [37], where transactions with higher fee-per-byte has priority over transactions with lower fee-per-byte.

Based on the expected waiting time of two-class M/M/1 queue [37], we summarize user $n$’s time-average transaction waiting time in following Lemma 1.

For (14a) and (14b), they correspond to the case where miners (eventually) choose to include the transaction as the transaction’s fee-per-byte is higher than $C_{s}$. For (14c) and (14d), they correspond to the case where the transaction waiting time is infinity, as no miner chooses to include the transaction with fee-per-byte strictly lower than $C_{s}$.

Here we characterize the users’ equilibrium strategies. Similar to prior blockchain literature [13][1], we consider the symmetric Nash equilibrium (SNE) where the same type of users adopt the same strategy.

For the ease of exposition, we first define some terminology related to the users’ equilibrium.¹⁵¹⁵15There can be other SNE but we pay attention to the Pareto-dominant one, where each user achieves no smaller payoff compared to other possible SNEs [13][38].

At an equilibrium, each user $n$’s net transaction utility $h_{n}$ plays an important role in his transaction generation rate, which defined as follows

where $\mathcal{N}_{H}$ and $\mathcal{N}_{L}$ are the set of types $H$ and $L$ users, respectively.

Notice that $h_{H}$ may not be larger than $h_{L}$ due to the waiting time tax rate vector $(P_{HH},P_{HL},P_{LH},P_{LL})$. We define type-$B$ as the bigger net transaction utility user type (i.e., $B={\arg\max}_{l\in\{L,H\}}\hskip 2.84526pth_{l}$) and type-$S$ as the smaller net transaction utility user type (i.e., $S={\arg\min}_{l\in\{L,H\}}\hskip 2.84526pth_{l}$). We illustrate the connections between types $B$ and $S$ as well as types $H$ and $L$ in Table I.

Next, we characterize the types $B$ and $S$ users’ equilibrium strategies at the $\overline{\rho}$-SNE and $\underline{\rho}$-SNE in Proposition 1.

Here we explain the intuition of the $\rho$-SNE, where $\rho\in\{\overline{\rho},\underline{\rho}\}$. When both $h_{B}$ and $h_{S}$ are small (i.e., (16a) and (17a)), users do not generate transactions. When $h_{B}$ is large but $h_{S}$ is small (i.e., (16b) and (17b)), only type-$B$ users generate transactions. When both $h_{B}$ and $h_{S}$ are large (i.e., (16c) and (17c)), all users generate transactions.

Based on the equilibrium characterized in Proposition 1, we summarize users’ equilibria in Theorem 2.

Fig. 4 illustrates two SNEs in Theorem 2 against fee-per-byte choices $(\overline{\rho},\underline{\rho})$, which reflects users’ tradeoff between paying low fee and bearing low waiting time. When $\overline{\rho}$ is small, then $\Delta(h_{B},h_{S},\underline{\rho})>\bar{s}\overline{\rho}$ and a $\overline{\rho}$-SNE exists. In other words, all users choose high fee-per-byte $\overline{\rho}$, because $\overline{\rho}$ is not high enough and hence the consideration of low waiting time dominates the consideration of paying low fee. As $\overline{\rho}$ increases such that $\Delta(h_{B},h_{S},\underline{\rho})\leqslant\bar{s}\overline{\rho}$, the $\underline{\rho}$-SNE emerges where all users choose low fee-per-byte $\underline{\rho}$. This is because when $\overline{\rho}$ is high, the consideration of paying low fee dominates the consideration of low waiting time.

The protocol designer’s decision variables are the fee-per-byte choices $\bm{\rho}=(\overline{\rho},\underline{\rho})$ (with $\overline{\rho}>\underline{\rho}\geqslant 0$) and the waiting tax rate vector $\bm{P}=(P_{HH},P_{HL},P_{LH},P_{LL})$. The fee-per-byte choices encourages users to pay sufficient transaction fees to mitigate the negative externality in transaction selection in Stage III. The waiting tax rate vector let each user internalize the waiting time costs imposed on others, dealing with the negative externality in transaction generation in Stage II.

For any user $n$ with a positive transaction generation rate (i.e., $\lambda_{n1}+\lambda_{n2}>0$), the FWT mechanism aims at inducing an average fee-per-byte value that can cover the total storage cost per byte of all miners, that is

The social welfare equals the sum of users’ and miners’ time-average payoffs.

Based on miner $m$’s payoff $v_{m}^{k}$ in round $k$ in (2), the miner $m$’s time-average payoffs as

where $\bm{\mathcal{X}}=(\mathcal{X}_{m}^{k},\forall m,\forall k)$ is the strategy profile of all miners in Stage III and $\text{Round}(t)$ is the number of rounds completed in time interval $[0,t]$.

The social welfare is as follows

We formulate the FWT mechanism design problem in (24), which aims at maximizing the social welfare subject to sufficient transaction fee covering the storage cost.

It is very challenging to solve Problem (24), since it is coupled with the strategies of users in Stage II and miners in Stage III. Nevertheless, we can exploit the special property of the social welfare to derive the optimal solution in closed form.

The optimal solution to Problem (24) is as follows.