This operating point is by far the most popular today, being used in Bitcoin, Ethereum, Monero, and others. We discussed the drawbacks of this approach in detail in Section 7.3.1. To summarize, there are three main problems with this approach: (1) it incentivizes miners to create congestion, (2) transaction fees are unbounded, and (3) it is susceptible to strategic behavior. Because of these problems, which have been well-documented both theoretically and in practice, we do not view this operating point as viable for Unit-e.

Many of the problems from Section 7.3.1 arise because miners can substantially alter their transaction fee rewards by changing which transactions they include in each block. One way to address this problem is by decoupling the transaction fees in a given block from the reward collected by the block miner. If miners cannot significantly alter their rewards by optimizing the transactions in blocks, they are less incentivized to prioritize certain transactions over others.

This operating point is not widely used in live cryptocurrencies, with the exception of Cardano [100]. Nonetheless, the idea of (partially) decoupling a transaction’s fee from the miner of the block containing that transaction has been explored in several works, including inclusive blockchains [113], Fruitchains [137], and Ouroboros [101]. Many of the papers studying this idea are designed for the PoW setting. The basic idea is that the miner of a block does not necessarily reap all the transaction fees in that block, but shares them with other miners who have also contributed to network security and validation. There are many ways to implement such a directive; one explicit mechanism is proposed in Fruitchains, where transaction fees are split evenly over a sequence of consecutive blocks. A key property that Fruitchains exhibit is fairness, defined below.

Definition 7.3.1 ([137]). \(\quad\) Consider a Byzantine adversary that controls at most fraction \(β\) of compute power (stake); the remaining compute power (stake) is controlled by an honest party. A blockchain protocol is \(δ\)-approximately fair if there exists a time duration \(T_0\) such that for all \(T \geq T_{0}\), in the view of each honest player, the honest party is guaranteed to obtain at least fraction \((1−δ)(1−β)\) of blocks with overwhelming probability in every time window of duration \(T\).

Fairness is closely related to our notion of equitability from Section 7.2.3. A key difference is that equitability only makes sense for random processes with fixed mean over time (i.e., processes that are stationary up to order 1), whereas fairness encompasses general non-stationary stochastic processes.

Fruitchains proposes a mechanism where by instead of directly including transactions in blocks, miners mine a “fruit” for each transaction [137]. When a transaction first appears in the system, miners start solving a proof-of-work puzzle specific to that transaction, with a different hardness parameter from the main blockchain. This proof-of-work puzzle must include a pointer to a recent block within the previous \(T(κ)\) blocks, where κ is a security parameter, and \(T(κ)\) is a (pre-specified) polynomial function of the security parameter. A solution to this puzzle, concatenated with the puzzle itself, is called a fruit, and gets broadcast to the network. Regular block miners include fruits in their blocks, rather than plaintext transactions. Fruitchains satisfy the following key property:

Theorem 6 (Fairness, [137]). \(\quad\) For any constant \(0<\delta<1\), there exists a constant \(\mathrm{T}_{0} = \Theta \left(\frac {1} {\delta} \right)\) such that the Fruitchains protocol is \(\delta\)-approximately fair with respect to an adversary that controls at most \(β\) fraction of the computational power.

Notice that fairness holds even without considering incentive mechanisms. To obtain incentive-compatibility, Fruitchains makes a key design decision, which is to distribute rewards (block rewards and transaction fees) evenly to the \(T(k)\) block miners preceding each block. Suppose that within any stretch of \(T(k)\) transactions, the total reward from transaction fees and block rewards is \(V\). We say that honest mining is a \(\beta^{*}\)-coalition-safe \(\gamma\)-Nash equilibrium if, with overwhelming probability, no coalition of \(\beta<\beta^{*}\) can gain more than a multiplicative factor \((1 + \gamma)\) utility, regardless of the transactions being processed. Under this reward allocation scheme, Fruitchains satisfies the following property:

Remark 7.3.2 ([137]). \(\quad\) Consider a blockchain protocol that satisfies \(δ\)-approximate fairness with respect to \(β\) attackers. If rewards are allocated to the \(T(k)\) block miners preceding each block (including the block itself), honest behavior is a \(β\)-coalition-safe, \(3δ\)-Nash equilibrium.

This remark is straightforward to derive. Fairness implies that within each stretch of \(T(κ)\) blocks, the fraction of adversarial blocks is upper bounded by \(\beta (1 + \delta)\), so the adversary’s reward is upper bounded by \(\beta (1 + \delta) V\). By fairness, if the adversary had followed the honest protocol, it would be guaranteed to reap a reward of at least \((1 - \delta) \beta V\). Hence the adversary gains a factor of at most

\begin{equation} \frac {(1 + \delta)} {(1 - \delta)} \leq 1 + 3\delta \end{equation}

in rewards for \(\delta<\frac{1}{3}\). Notice that this result depends on two key components: first, the underlying blockchain protocol should be fair. Second, the reward allocation scheme should split rewards evenly among miners. By adopting a version of Fruitchains adapted to PoS (e.g., as proposed in Snow White [52] or Ouroboros [101]), we can obtain analogous results.

There is a key downside to sharing transaction fees across a sequence of block proposers, while also allowing users to propose their own fees. Since miners do not collect all the transaction fees from a block, they are less incentivized to include transactions with higher fees first; this means that users have a much weaker incentive to propose fees above the minimum. A key question that must be answered is whether such a system can raise enough transaction fee revenue to pay for network security. At the moment, there is no research quantifying this question (as far as we know).

A third operating point is that transaction fees could be chosen purely algorithmically, but miners would still reap the full transaction fees of each block they mine. To the best of our knowledge, there are no cryptocurrencies or papers advocating for this approach. Nonetheless, there are related workflows in existing systems. For instance, the Bitcoin Core wallet has a slider that allows the user to choose a desired processing speed; the wallet then algorithmically chooses a fee based on the blockchain’s historical processing rates as a function of fees. Since the underlying blockchain is just Bitcoin, the miner that includes said transaction would reap the (algorithmically-chosen) fee.

The previous example belies a key point: our reason for exploring algorithmic fees in the first place is to prevent users from paying higher fees to enable faster transaction processing. This is the key source of congestion, as described in Section 7.3.1. A relevant question, then, is how an algorithm might choose a transaction fee.

Fundamentally, transaction fees pay for two properties: security and convenience. This cost can be broken down into the internal (computational and storage) cost of validating and storing transactions, and the external (communication, security) cost of coming to consensus with the rest of the network. Internal costs are primarily governed by transaction byte size; the larger the transaction, the more resources are required to store the transaction. External costs are more subtle to quantify. At first glance, these costs also seem to scale primarily with transaction byte size, since the consensus protocol does not explicitly differentiate between transactions and byte size determines communication cost. However, in practice, transaction value also plays an important role, for a few reasons.

1. Processing cost. \(\quad\) High-value transactions require better security; they are more appealing targets, and therefore bear a higher standard for validation and finalization. Since it is common practice to wait longer before considering a high-value transaction as confirmed, the network implicitly expends more effort to confirm high-value transactions.4

2. Security. \(\quad\) Taking a more global view, transaction fees in aggregate fund the security of the network as a whole. Since higher-value payments increase the need for security, they should also bear a larger burden in terms of paying for that increased security. User-proposed fees do not satisfy this requirement, because they are only tied to transaction value through the user’s preferences.

3. Economic fairness. \(\quad\) Finally, existing payment networks (e.g., credit cards) typically set fees as a fixed percentage of transaction value. If Unit-e’s fees are lower than those of traditional payment systems, then it is capturing a surplus for users. In order to distribute that surplus fairly among users, transaction fees should similarly be set as a percentage of transaction value.

These arguments collectively suggest that transaction fees should somehow scale with transaction value (not necessarily linearly). We therefore consider a fee mechanism that is programmatically determined. For each transaction, wallet software will evaluate a function \(w(·)\) that takes as inputs a number of features, including transaction value \(v\), transaction byte size \(b\), and possibly other parameters capturing the current level of network health \(h\). Including network health in the computation enables adaptive fees that respond to network conditions, such as congestion and/or gaps in security. Although we have not specified yet how w should be defined, it should satisfy a few basic properties:

• Boundedness: For all \(v, b, h \geq 0\),

where \(\underline{w}\) is a hard-coded lower bound on the transaction fee, chosen to make spamming attacks costly. Similarly, \(\overline{w}\) is an upper bound on the fee rate, or the amount of fees per unit transaction value. We expect to choose \(\overline{w}\) based on merchant feedback.

• Monotonicity (transaction value): For any \(v_{1} < v_{2}, b, \text { and } h\),

• Monotonicity (transaction byte size): For any \(b_{1}<b_{2}, v, \text { and } h\),

Many functions satisfy these broad requirements, with different tradeoffs. Consider the operating point where miners reap the full transaction fees of each block they mine; intuitively, for a given function w, the weaker its dependency on transaction value, the less congestion we expect to see. This is because of the arguments in Section 7.3.1; congestion is caused by miners choosing which transactions appear in each block. At the same time, weakening this dependency degrades the system’s security properties. A key research question is to analyze the effects of different transaction fee functions on the congestion-security tradeoff.

In summary, the approach of choosing transaction fees purely algorithmically has some attractive properties; primarily, transaction fee rates would no longer be unbounded. However, the core problem of congestion remains. High-fee transactions will still be processed earlier, which promotes a hierarchy among transactions, and raises questions of fairness to users.

The fourth operating point consists of choosing fees purely algorithmically, while also partially decoupling the allocation of transaction fees from the block(s) that included those transactions. This is the least well-understood among the four operating points, but it has some appealing properties. First, transaction fees can be bounded. Second, congestion can be reduced, by reducing the incentive for miners to strongly favor transactions with high fees. Third, unlike the operating point in Section 7.3.2.2 (user-selected fees, decoupled rewards), it does not matter that users are not incentivized to propose higher fees, since we can algorithmically choose fees that support network functionality. A key downside of this approach is complexity; analyzing the incentives of miners and the relation between the fee structure and network viability may be quite complicated if the transaction fee algorithm is complex. We view this as the main obstacle to this approach, and an important direction for future research and consideration in the transaction fee design of Unit-e.