UTXO/coin-based blockchains with flexible scripting face an interesting challenge: how to charge users for sending non-trivially invalid transactions? By this I mean a transaction that is invalid, but takes a great deal of computation to show is invalid.
The problem and why it’s hard
The classic example is a coin locked by an expensive covenant that fails at the last moment. For example, imagine a coin locked by the following Melodeon covenant:
let x = 0 in
loop 10000 do
set! x = x + 1
with x == 9999
This covenant increments a variable x 10000 times, then succeeds iff x == 9999 — but x is actually 10000, so the covenant always fails. The problem here is that in general, you can only know this after wasting your time running the loop.
An attacker can then DoS the network by making a coin locked by a covenant like this, then spamming the network with transactions trying but failing to spend the covenant. Because the transactions are invalid, they never go through, so the attacker does not need to actually pay any network fees!
But wait — is this actually a serious problem? Can’t you DoS any node in any network with garbage data? For example, Ethereum nodes are just as vulnerable to volumetric DDoS that flood them with garbage network packets as any networked computer.
Unfortunately, the answer is yes — non-trivial invalid transactions are actually a serious problem for UTXO chains. The key concept here is griefing factor: what resources do the attacker need to waste in order to get the victim to waste a given amount of resources. In the case of a volumetric DDoS, the attacker needs to pay for every bit of bandwidth that (s)he wants the victim to waste, so the griefing factor is close to 1, a good outcome for the victim. But by sending these crafted expensive-to-reject transactions, an attacker can DoS a UTXO chain with an effectively unlimited griefing factor: crafting and spamming the transactions is basically free, while each one can waste as much computation as the attacker wishes.
The problem is hard because a UTXO-based transaction either goes through or doesn’t — “reverting” a transaction while still charging the sender doesn’t fit well with the model, first because the entire appeal of the model is that transactions are atomic and either go through or not, and more importantly because there’s no such thing as the “sender” as opposed to the “smart contract” being run, since all ownership is expressed through covenants. A solution that, say, allowed invalid transactions to go through but attempted to “charge the sender” by confiscating or taxing the coins that the transaction tried to spend would not work since it would allow any coin to be arbitrarily confiscated by anybody by simply sending a bad transaction that tries to spend it!
Cardano’s suboptimal solution
The biggest richly-scripted UTXO blockchain right now is certainly Cardano, and they have a fairly involved solution to this problem that uses “collateral UTXOs”. In short:
- Every transaction that executes arbitrary code must have, as input, keypair-owned “collateral” UTXOs to cover gas fees
- If the transaction does not validate, or if there’s not enough gas in the collateral UTXOs to validate the transaction, the transaction is still placed on the blockchain, but its effects are that the collateral UTXOs are confiscated
This fixes the problem by essentially reintroducing the concept of the “sender” of a transaction and charging them for failed transactions, mirroring the usual way of handling failed transactions in account-based blockchains.
But Cardano’s solution comes with several serious downsides:
- It requires a dichotomy between code-owned and keypair-owned UTXOs, analogous to the dichotomy between contract accounts and externally-owned accounts on Ethereum. Cardano already has this, but this is a distinction that Mel intentionally avoids to make nondefault cryptography, multisig, etc “first class”.
- Accidentally producing an invalid transaction due to e.g. buggy software can easily drain huge amounts of collateral. This seems to be a big enough problem that some people are developing even more complex solutions to mitigate the risk
- The whole mechanism is tricky to explain and give a good UX for
In general, collateral feels to me like an “un-UTXO-ish” hack that adds a lot of complexity and clearly cannot be used on Mel.
A better solution: anti-griefing proofs of sequential work
One observation is that the griefing problem described isn’t actually at the level of the core blockchain state-transition function (i.e. the “consensus-critical logic”) that defines what transactions are valid. Instead, it’s essentially a problem of griefing the peer-to-peer transaction gossip layer that deals with yet-to-be-confirmed transactions.
Thus, I think the best solution is in that layer. All we need to do is to fix the griefing factor so that these DoS attacks become analogous to volumetric DDoS. Here is a sketch of a solution that will probably be a TIP soon:
- There is a weight threshold set by each individual node and not part of the blockchain rules, that roughly corresponds to the cost of a transaction where propagation costs already dominate over validation costs.
- Transactions with below-threshold weights propagate normally.
- When propagating a transaction with an above-threshold weight, a node must attach a proof of sequential work with respect to the transaction hash, in an algorithm analogous to the MelPoW used in Melmint. This proves that after generating the transaction, the sender must have wasted a certain number of sequential hashes. How much work must be proved is indicated by a parameter communicated back through the P2P network, and would be proportionate to the weight of the transaction.
The last part fixes the griefing factor by forcing an invalid-transaction spammer to waste at least as much resources as he would waste at the node.
(Note that this system relies on Mel being able to compute the weight of a transaction statically without running it — another benefit of a bounded-loop VM rather than a pseudo-Turing-complete one)