  Miners in a blockchain system are suffering from ever-increasing storage
costs, which in general have not been properly compensated by the users'
transaction fees. This reduces the incentives for the miners' participation and
may jeopardize the blockchain security. We propose to mitigate this blockchain
insufficient fee issue through a Fee and Waiting Tax (FWT) mechanism, which
explicitly considers the two types of negative externalities in the system.
Specifically, we model the interactions between the protocol designer, users,
and miners as a three-stage Stackelberg game. By characterizing the equilibrium
of the game, we find that miners neglecting the negative externality in
transaction selection cause they are willing to accept insufficient-fee
transactions. This leads to the insufficient storage fee issue in the existing
protocol. Moreover, our proposed optimal FWT mechanism can motivate users to
pay sufficient transaction fees to cover the storage costs and achieve the
unconstrained social optimum. Numerical results show that the optimal FWT
mechanism guarantees sufficient transaction fees and achieves an average social
welfare improvement of 33.73\% or more over the existing protocol. Furthermore,
the optimal FWT mechanism achieves the maximum fairness index and performs well
even under heterogeneous-storage-cost miners.
