Transaction Collisions and the Effective tps of Inclusive BlockDAGs

What makes DAGs incredibly fast is the ability to parallelize: since blocks made in parallel are all considered valid (unlike in blockchains where all but one of them will be eventually orphaned), increasing parallel block rates does not harm security, thus removing a major obstacle to throughput (but one should be extremely careful not to enable new forms of attack, which is essentially what makes DAG consensus protocols so difficult to design).

One of the supposed benefits of the increased block-rates is the increased transaction throughput (another benefit, which I argue is actually the more significant one, is the greatly decreased confirmation times). On the surface it seems that if we make 600 blocks for every Bitcoin block then our transaction throughput is 600 times that of Bitcoins, but is it the case? Well, not quite…

The nuance is that parallel blocks are allowed to contain the same transaction, and it isn’t really fair to count the same transaction more than once. We really should compare in terms of effective tps, that is, how many unique transactions are included in an average block (or more accurately, on average, how many of the transactions in a block do not appear in a parallel block preceding it in the GHOSTDAG ordering).

This of course depends on how the transactions are selected. What makes this discussion both complex and worthwhile is that we can’t actually force miners to follow a particular selection rule. There is little we can do to prevent miners from selecting what transactions to include however they want.

One selection rule is the random selection rule, which, unsurprisingly, just means that miners choose which transaction to include at random. The purpose of this post is threefold:

1. Analyze the random selection rule and argue that it provides a very good effective tps (it actually provides the best effective tps theoretically possible in scenarios where miners can not coordinate their selection).
2. Argue why miners, even greedy miners seeking to increase their own profit, will not meaningfully deviate from the random selection rule (in particular, responding to the “attack” on GHOSTDAG proposed in (Peresini et. al., 2021, preprint)).
3. Propose two possible solutions we could employ in the (unlikely) scenario that we observe a low effective tps.

In some of the discussion, I’m afraid we need to use… math! I tried my best to give a short qualitative description before diving into calculations, so that the more greasy parts could be safely skipped.

Parallel Transaction are not the same as conflicting transactions

Before we dive in, there is a small distinction which has to be made, between parallel transaction and conflicting transactions.

A parallel transaction is when the same transaction appears in several parallel blocks, whereas a conflicting transaction is when two different transactions trying to spend the same UTXO appear in conflicting blocks. That is, the former scenario is honest whereas the latter is adversarial.

I am only bringing this up now to clarify that double spends are not the same as parallel transactions. That is, we do not care which of the blocks containing the transaction will eventually become the most precedent block, since all blocks spend the transaction to the same address, so we can safely add it to our UTXO after we have the guarantee that one of the parallel transactions will be included, regardless of the block it was taken from.

Starting with the Worst Case

The first insight is from a worst case analysis, in which we try to understand what is the lowest effective tps possible. That is, we ask ourselves what the effective tps would be if any two parallel blocks contain exactly the same transactions.

Say that on average, 10 blocks are created simultaneously (though in practice the DAG is typically much narrower than that, but that’s bound to increase once we increase the block rate), then even though we crank out one block per second, nine out of every ten blocks will not contain any new transactions.

This is rather bad, but not prohibitively bad. That is, even at 10% capacity, our network is competitive with any other PoW tech out there, and we still reap all other benefits such as blazing fast confirmation time.

However, the reality is much more bright than this worst case analysis, as I will explain in the rest of this text.

Random Selection in the Honest Scenario

The purpose of the current part is to understand the effective tps assuming all miners follow the random selection rule.

Random selection is, unsurprisingly, when miners choose which transactions to include completely at random. It is natural to ask why should the miners do that? and it is indeed a valid concern, which I thoroughly address in the next part of the post. But before that, we need to better understand the honest scenario.

Below, I analyze this scenario using an analytical tool called math. If you’re not into that kind of stuff, I’ll spoil that the upshot is that the effective tps is at least 62% of the optimal tps. If you want to know where this mysterious figure comes from, keep reading. Otherwise, you can skip to the next section.

A point of subtlety here is that the analysis is actually sensitive to how much transactions are currently in the mempool. Say a block can hold 100 transactions but the mempool only has 50 transactions in it. Then all parallel blocks will contain all 50 transactions regardless of the selection rule, and the “effective tps” will be very low in a very meaningless way.

To make life easier, we will calculate a slightly different quantity: say there are t transactions in the mempool, and k blocks are generated simultaneously, each containing l randomly selected transactions, then how many unique transactions are going to be included in these blocks?

So first, what is the probability that a particular transaction is contained in a particular block? Since the block contains l of the t transactions, the probability for that is l/t. Hence, the probability that this transaction is not contained in this block is (1-l/t). Since there are k independent blocks, the probability that the transaction will not be contained in any block is (1-l/t)^k. So the expected number of transactions not included in any block is t(1-l/t)^k.

Now, using the magic of either Taylor series or binomial expansion we find that (1-l/t)^k = 1-kl/t + O(1/t²). To obtain the expected number of excluded transactions, we multiply this expression by the number of transactions t to obtain t-kl+O(1/t). In other words, the number of excluded transactions is t-kl plus something that grows rapidly smaller as t increases.

Why is that interesting? Well, note that t-kl is the optimal number of excluded transactions: k blocks each containing l transactions can include at most kl unique transactions, excluding the remaining t-kl transactions.

We see that when the mempool is rather full, the random selection rule seems rather close to optimal. But that’s not a great surprise: it is obvious that the probability that two miners choose the same transaction decreases as the number of transactions increases.

What we did gain from the analysis is that we can see what happens when t is comparable to kl. That is, the size of the mempool is rather similar to the capacity of the next round of blocks. In the case t=kl we can just directly substitute: we calculated that the number of excluded transactions is t(1-l/t)^k, and after substituting we get kl(1-l/kl)^k=kl(1–1/k)^k, and now we note that (1–1/k)^k approaches 1/e as k grows (where e is Euler’s number). Moreover, the convergence is monotonically increasing, which gives an upper bound even for low values of k. So we get that the fraction of excluded transactions is at most 1/e. In other words, we include at least (1–1/e)~62% of transactions. Further analysis shows that this is actually a minimum. That is, for any t>kl we will include at least (1–1/e)kl transactions, and for any t<kl we will include at least (1–1/e)t transactions.

The upshot is that the random selection rule gives us an effective tps which decreases to 62% of the theoretical maximum as k goes to infinity. Even for huge values of k we don’t lose much at all. That ain’t half bad!

But What About Dishonest Miners?

This concern has come up a lot recently due to an alleged “transaction selection attack” on GHOSTDAG (Peresini et. al., 2021, preprint). This paper provides some empirical analysis of a known property of so called Inclusive protocols, pointed out in (Lewenberg-Sompolinsky-Zohar, FC’15). Namely that “the random selection rule is a weak equilibrium but not a strict equilibrium” (cf. chapter 4 therein).

This last statement is probably completely opaque to most readers, so let us unpack it slowly.

When we say that a particular strategy is a strict equilibrium, what we essentially mean is that it is optimal for all players: there is nothing to be gained by deviating from it.

A weak equilibrium is a more subtle notion. It essentially means that it might be beneficial to deviate from the equilibrium strategy, but as more players deviate from it, deviating becomes less beneficial. In particular, a weak equilibrium is still the optimal strategy for a myopic player. A myopic player is a player which has no knowledge and no assumptions about the other players. In particular, a myopic player does not assume that the other players are rational or that their utility is to maximize profit. As far as the myopic player is concerned, other players could be altruists trying to do what’s best for the network, or greedy miners trying to maximize profits, or chaos agents willing to lose money for the sake of decreasing effective tps and harming the network, or stupid players only including transactions whose hashes end with q or l for numerological considerations, or any other conceivable transaction selection strategy.

To provide some intuition to why that is the case, assume for simplicity we have exactly 101 computationally equal miners on our network, each of them is of one of two types: honest miners, which always select the transactions randomly, and maxi miners, which always select the highest fee transactions.

If 100 of the miners are honest and there is only one maxi miner, then it is not difficult to get convinced that the maxi miner has higher expected profit: since all other miners are random, the probability that the fee for a particular transaction included by the maxi miner will go to one of the honest miner is the same for all transactions. The expected profit is whereby proportional to the sum of fees paid by included transactions, which is obviously higher for the maxi miner over the random miners.

But what happens if there are 100 maxi miners, and only one honest miner? The analysis is a trickier, but the upshot is that since all maxi miners compete for the same transactions (hence, their expected profit one hundredth is the sum of highest fees), whereas the honest miner will probably include a completely different set of transactions (this is actually only true when assuming that the average transaction fee is not considerably lower than the highest transaction fees, but that’s actually a good thing, as it facilitates fees as incentives to mine blocks. I touch upon this in the next section).

Sure, miners can try to come up with all sorts of crazy strategies, but at the end of the day, either the dishonest miners all compete for the same transactions (whereby decreasing their profit), or each strategy preferred different transaction (whereby not harming the effective tps).

In summary, if all miners use a random selection rule, than a malicious miner could use this to gain some advantage, but in a small scale which does not affect the effective tps. Moreover, this kind of behavior is risky, since if other miners follow it, then all deviating miners are actually losing.

But Aren’t Fees Supposed to Incentivize Mining?

Kaspa is a deflationary coin, which means that at some point the block rewards will vanish and the main incentive for miners to keep mining will be the transaction fees. How does that work if they don’t get to select the fees? Why should users pay fees high enough to cover the cost of mining a block when they have the same chance to be included as anyone paying a fraction of that?

Well, recall that in the analysis above I did appeal to an implicit assumption: that the value of the low fee transaction is not that low. Let us try to quantify this with an example. Say that the average width of the graph is 10. That is, if all miners include a particular transaction, then the probability they would actually get the fee is 0.1. Assume for simplicity that a block can only carry one transaction, and say that there are two transactions in the mempool, one paying 4$ fee, and one paying 5$ fee. If all miners take the 5$ transaction then the expected gain of each miner is 0.5$. If one miner goes for the 4$ transaction and the rest go for the 5$ transaction, then the first miner has 4$ expected gain, and the rest have 0.55$ expected gain. Explicitly analyzing the optimal strategy for each miner is a nice exercise, but for our purposes it suffices to observe that it makes sense to give some probability to the cheapest transaction.

Now consider the case where the first transaction pays 100$ fee, and the other pays 1$ fee. If a miner competes for the high paying transaction, then they have an expected gain of 10$. That’s more then she would expect to gain from including the low paying transaction even if she know for certain that she is going to gain the fee. In other words, any strategy that gives any probability to the 1$ transaction is losing regardless of what the other miners are doing.

Now, the actual condition is a bit delicate. Say that the expected width is k, and that a block contains l transactions, then rational myopic miners would ignore any transaction whose fee is less than one kth of the fee of the lth highest fee. So, if a block contains, say, 5 transactions, and there are, say, 5 parallel blocks on average, and the transactions currently in the mempool have the following fees: 10,9,8,7,5,4,3,2,1,0.5, then miners would actually ignore the last transaction, as it becomes more profitable for them to randomly choose from the remaining transaction even if they know for certain they would get the fee for the 0.5$ transaction.

That is, supply and demand can still drive the transaction fee high enough to compensate miners for their work, and the rest of the analysis remains the same.

OK, But What if We Do Observe a Lot of Collisions?

Everything said so far is nice in theory. And theory is nice, as it makes our guesses much more educated. However, in real world situations we might find that it doesn’t exactly hold up. How might this happen? In many ways, each one sounds more outlandish than the other, but none impossible.

If in practice we see observe many transaction collisions, there are several ways we can go about reducing them. I will present the one I find most straightforward, and the one I find most beautiful.

The first approach is simply to bucket the transactions. Say we only allow blocks to include transactions whose hash has the same 5 last digits as the hash of the block. This will segment the transactions into 32 buckets, making collisions only possible for blocks selecting from the same bucket. Trying to “choose” a different bucket amounts to recomputing your nonce completely, thus wasting work. (The keen of eye might say something like “but how can the transactions depend on the hash of the header when the hash of the header depends on the transactions”, which is a indeed a sharp observation. One way to go about this is to prepare in advance a Merkle tree suitable for *all* buckets, but eventually only include transactions from a particular bucket (though this increases the length of Merkle proofs). Another approach is not to use the entire header but only a part of it (but this makes “bucket selection attacks” easier). There are several other approaches to this as well.)

The second approach is the monopolistic auction mechanism (Lavi-Sattath-Zohar, TAEC’22). In this mechanism, miners can include whatever transactions they want, but the fee for all transactions is the lowest fee among transactions included. The insight here is that, unless transaction prices are very spread, it is better for a miner to include more transactions, even if the fee they get for each transaction decreases. If a miner already has in her block 50 transactions where the lowest transaction is paying 1$ in fees, then she is better off including three more transaction which pay .98$: she loses a total of 1$ in fees for the original 50 transactions, but gains 2.96$ for the new transactions. The point it that in terms of maximal gains it doesn’t matter what actual transactions the miner decided to include beside the lowest paying ones, so it is rational for them to select the remaining transactions randomly to avoid collisions as best as possible. An analysis similar to above shows that the rational way to choose the lowest paying transaction to include is the same cut off as above: the lowest paying transaction whose fee as at least one kth of the lth highest paying transaction.