Transaction selection games in blockDAGs
Consider a blockDAG network which mines 1 block per second, and an individual Miner A within it. How will A know which transactions to embed in his next block? He can fill his block with the highest-fee-paying transactions — but then he risks these transactions duplicating the transactions that Miner B includes in his block, created at the same time in a different faction of the network. The miners may thus consider being less greedy, selecting lower-fee transactions, and avoiding duplications. This is like a game of Chicken (a.k.a. Hawk–Dove Game), in which avoiding collisions is in the best interest of both parties. If we implement the Nash equilibrium strategy in the default mining client of a blockDAG network, an individual miner will not benefit from deviating, applying a more “Hawkish” strategy, and attempting to collect the highest-fee transactions. In this post I discuss how this affects a blockDAG’s throughput and quality of service for transaction confirmation.
Background
Since blockDAGs can operate at very high block creation rates, multiple blocks may be created in parallel in the network. Recall from this introductory post that all blocks in a blockDAG are included in the ledger, without being orphaned, creating potential for a large throughput increase over Bitcoin. However, miners mining blocks in parallel to each other cannot directly coordinate with each other, and if they choose the same subset of transactions to include in their blocks, there would be many transaction collisions and throughput would be wasted (though confirmation times would still be significantly faster).
Incentives in transaction selection
The Inclusive Blockchain Protocols paper, presented at Financial Crypto 2015, highlights an important insight: miners are incentivized to avoid transaction collisions. A transaction fee is produced only once, and can be given only once (or split), even if the transaction is duplicated across multiple blocks. Assuming the winner is dictated by the ordering protocol applied on the DAG, each block has some probability of collecting the fee of a transaction embedded in it and some probability of losing it due to collisions. Miners are therefore incentivized to minimize collisions, increasing the DAG’s usage and throughput.
The Inclusive authors go further to model this dynamic as a game of transaction selection. In the game, each miner must strategically decide which transactions to include in his next block. Interestingly, choosing the highest-fee transaction does not usually maximize the miner’s profit. The matrix below describes a simple game, as an example. It specifies the expected payoffs in the game where two miners must choose one transaction for their next block, from a mempool of two transactions with different fees. Notice the resemblance to the game of Chicken, where if one player commits to the more rewarding choice, the other is incentivized to sway and choose the less rewarding choice.¹
A player adopts a mixed strategy if he defines a probability distribution that assigns a likelihood to each of his possible actions in a game; thus, in this game, a miner’s mixed strategy is a probability distribution that defines how miners choose transactions to include in their next block. This game is described in detail in the Inclusive paper, where several solution concepts are analyzed, including the well known Nash equilibrium concept (see section 4.3 in the paper). If Nash is played by all miners, then by definition no individual miner benefits from deviating. We can embed this strategy in our default mining client, which makes it easier to reason about how the equilibrium is reached.
Tradeoffs in transaction selection
The throughput of a blockDAG is highly dependent on the strategy profile in this transaction selection game. For example, if each miner always chooses the k highest-fee transactions with probability 1 (where k = number of transactions per block), then parallel blocks contain many collisions, as miners of these blocks choose the same subset of transactions from the mempool. In this case, the blockDAG would not enjoy any throughput improvement over a blockchain (though, again, confirmation times would still be much faster).
On the other hand, if each miner chooses transactions uniformly from the mempool (above some small fee threshold), then there are almost no collisions and throughput is optimized. However, transactions are served uniformly slowly, and those with higher fees aren’t prioritized.
More generally, the transaction selection strategy faces a tradeoff between high quality of service for confirmation times and high throughput. Furthermore, the chosen strategy depends on how cooperative miners are, and how much they expect to benefit from malicious deviation. For example, to achieve optimal throughput via the uniform selection strategy, miners have to almost entirely disregard fee differences, giving up on profit maximization.
The graph above depicts the confirmation times of two different transaction selection strategies, which differ in the weight they give to the value of the fee. The orange curve represents a strategy that prioritizes high-fee transactions by assigning them higher inclusion probability in the next block. Those that are willing to pay the high fees get confirmed fast, but there are more collisions and the fee threshold to be selected from the mempool is higher. The blue curve, in contrast, represents a more egalitarian strategy: it randomizes more uniformly over the mempool, assigns similar inclusion probability to transactions with medium-to-high fees, and therefore serves them roughly after the same waiting time. This more egalitarian strategy enjoys fewer collisions and higher throughput. However, urgent transactions can’t “buy” faster confirmation times with higher fees.
Fortunately, the Inclusive authors show that the tradeoff is not severe — their Nash equilibrium solution achieves both high throughput and high quality of service levels. This solution assigns high probability to high-fee transactions, but these transactions are not selected with complete certainty, as some weight is given to lower-fee transactions. The authors ran simulations comparing the throughput of a blockDAG protocol with the Nash strategy profile to that of a non-inclusive longest-chain protocol. Though it does not reach optimal usage, the blockDAG achieves high throughput (proportional to optimal throughput, in fact), while still maintaining the ability to prioritize high-fee-paying users.
Conclusion
Protocol scalability is often measured in terms of throughput (transactions per second) and latency (confirmation times). While blockDAG protocols can achieve significantly faster confirmation times than blockchains, they typically face a tradeoff between quality of service for confirmation times and throughput. The tradeoff a blockDAG protocol takes depends on the behavior of miners when selecting transactions from their mempool to include in their next block. This behavior induces a non-trivial transaction selection game, in which miners are often incentivized to avoid duplications (or “collisions”), as these lower the chances of winning the fees. Still, transactions with high fees are selected by many miners, regardless of the collision risk, which allows for decent quality of service. Fortunately, these incentives imply that miners would naturally contribute and work towards higher usage and throughput of the system, even when considering only their own interests.
_________________________________________________________________
Endnotes:
¹ However, there is an important difference from Chicken: here, if both players collide on the more rewarding choice, it is better (from their perspective) than the scenario where both sway — the social welfare (sum of players’ payoffs) of the bottom right cell is still higher than the upper left one. In Chicken, on the other hand, a collision is a disaster from the players’ perspective, and they would certainly prefer co-swaying over colliding.
