zkvm: fees mechanism - Githubissues

Goal

Design the fee mechanism for ZkVM transactions to prioritize txs for acceptance in the mempool.

Checklist

[x] feerate math #399
[x] fee instruction spec #399
[x] fee instruction impl #399
[x] calculate feerate from Tx/VerifiedTx #399
[x] cloak with cleartext output w/o rangeproof (done by changing fee: #403)
[ ] fee API in accounts module
[ ] mempool datamodel for ordering txs by feerate
[ ] mempool: special treatment for "our" txs that are non-evictable
[ ] delayed low-fee parent buffer

Specification draft

Fees

Fees have a single designated flavor ID that makes them fungible across all transactions. We set the fee flavor ID = 0 encoded as ristretto255 scalar.

Fee is paid using a fee instruction (v q -- ø) that takes a Value v and an integer q. The instruction verifies that the value is an unblinded commitment to flavor=0 and a given quantity, removes the value from the stack, and adds a TxEntry::Fee(u64) entry to the TxLog.

Where the fees go is outside of the scope of this spec. They can be destroyed or claimed by the block validators, or distributed in some interesting manner.

When transaction is processed by the mempool, it computes its total tx fee by adding up all the Fee entries in the TxLog.

Fee rate

For each transaction, a fee rate is computed as tx fee divided by the size of the tx in bytes (<Tx as Encodable>::encoded_length()).

Fee rate is stored as a pair fee,size so that fee rates can be correctly combined:

Combine(fr1, fr2) = (fee1+fee2) / (size1+size2).

Effective fee rate

Effective fee rate of a transaction is a maximum between its own self feerate and total feerate.

Total feerate is a combination of self feerate and effective feerates of all children, each discounted by the number of unconfirmed parents.

When calculating contribution of the child's effective feerate to its parent, it is divided by a number of unconfirmed parents, so that recursive calculation does not over-account for the descendants that have multiple paths to a given ancestor. This discount does not have any effect if the child has all the unconfirmed inputs pointing to the same parent (common case). In an uncommon case of multiple unconfirmed parents: either parent's self feerate is higher than the total, so there is no effect from the discount; or it is the child-pays-for-parent situation and the contribution of the child is evenly split between all unconfirmed parents. This is unfair in case CPFP applies to one parent, but is not needed for another, but can be seen as a price to pay for forcing the nodes sort out subgraphs with low-fee parents. The general philosophy is: the more burden one tries to put on the network, the higher they have to pay.

Mempool priority

Transactions in mempool are ordered by their effective feerate (see above).

If the mempool is under its limit, transaction with any feerate is accepted.

If the mempool is at the limit, any new transaction must:

Have the effective feerate ≥ the lowest feerate.
Pay the absolute fee higher by the absolute effective fee of the to-be-evicted transaction.

The rule #2 is translated into having fee2 ≥ rate1 * (size1 + size2). In other words, the new transaction must pay the fee that would've gone unpaid by the evicted transaction.

Evicting subgraphs from mempool

When a transaction is evicted, all its descendants must be recursively evicted too. As a consequence, all the surviving ancestors' effective fee rates must be recalculated.

TBD: efficient traversal logic. Mark evicted nodes as to-be-evicted. Recalculate from the bottom-most children

Unconfirmed limit

Each transaction has an "unconfirmed depth". Children of confirmed transactions have depth 0. Children with unconfirmed inputs have the maximum depth among the parents, plus one.

Mempool policy includes the limit on unconfirmed children to minimize eviction overhead. The deeper the unconfirmed chains are, the more fragile they are causing more work to clean them up.

Low-fee parents

Each peer maintains a limited LRU buffer of low-fee transactions that are waiting for a higher-fee children. When a low-fee tx is received, it's validated against the mempool state, but not added to it.

If later a child arrives from the same peer that makes a sufficient effective feerate, then the subgraph is added to the mempool.

If a child also does not produce a sufficient effective feerate it's added to LRU buffer behind the parent (so the parent is not evicted before the child).

Transactions in the low-fee buffer are reported only to the peer that delivered them as to avoid duplicate relay, but not shared with other peers to keep things simple. In the future we may use a more elaborate reference-counting with a global cache of received transactions.

Orphan transactions

We are deliberately do not introduce a notion of out-of-order "orphan" txs. That is, children w/o parents where parents are relayed at some time later. This invites building a feedback loop when orphan pool is used to estimate feerate in a more precise way.

Instead, we abstract away out-of-order transmission as TCP packets do: we may have a buffer of out-of-order transactions somewhere, but only at a transport layer. At the node logic, all transactions are coming in proper order, so parents appear before children. This disallows ad-hoc shortcuts for handling CPFP, but forces the reasoning to be more straightforward.

Cloak with fee

We may extend the cloak gadget in the spacesuit library to accept cleartext qty and flavor for the fee output. This permits us to avoid wasting 64 bytes for encoding a pair of commitments for a fee when 8 bytes for u64 qty would suffice, eliminates one unnecessary rangeproof check (64 multipliers) and permits avoiding commitment check altogether inside the fee instruction.

Background

The question of fees was ignored up until this point. In principle, nodes may adopt arbitrary policies and accept unblinded payments to addresses. However, a designed flavor ID for fees and a designated fee mechanism would allow us to robustly implement prioritization as motivated below.

Knapsack problem

The decentralized network inherently needs to maintain some limit on amount of resources required from the peers to validate the blockchain. This means, that as usage grows, validators would (other things considered equal) select transactions that yield maximum profit. This is known as a knapsack problem, which is NP-hard. Transactions also depend on each other, so that a high-fee transaction may depend on a low-fee ancestor. Transaction can also be replaced (in other words, double-spent) in order to pay a higher fee and gain a higher priority. When choosing between two conflicting transactions we are actually choosing between two conflicting subgraphs. This adds another dimension of complexity: maximum independent-set problem, which is also NP-hard. See Joseph Bonneau's excellent article on the subject.

Since we cannot have an efficient perfect solution to the problem, we should choose a reasonable approximation that works well in common cases and has very low computation requirement.

Bumping priority

Sometimes transactions get stuck: the user agent (e.g. a wallet) makes a transaction that pays a lower fee than the majority of transactions, which makes transaction stay unusually longer in the mempool. In such case the transaction fee must be "bumped" in order to increase the priority of the transaction and get it finally published in a block.

Another situation is chained transactions. Suppose that a user agent has just one utxo, and so the two independent payments must be chained through the change output. In case the first transaction was of low-priority, while the second transaction is of high-priority, we need to make sure that the first one gets published as soon as we need the second one to.

There are two, not mutually exclusive, strategies to do so: Replace-by-Fee (RBF) and Child-Pays-For-Parent (CPFP).

RBF replaces an existing unconfirmed transaction with a conflicting one that pays a higher fee. This requires the network to relay and re-validate another transaction. Only one of the two is actually going to pay the fee, while the other will be rejected. For that reason, RBF replacement tx shall pay not only its own relay fee, but also cover the relay fee of the replaced transaction. This is needed so the user bears the cost of relaying of both transactions. (See also BIP125.)

CPFP keeps already relayed transactions untouched, but allows a descendant transaction to "cover up" for its ancestor(s). Meaning, if both the parent and a child are included, the overall fee rate will be higher than for the parent alone.

Note that both RBF and CPFP require virtually the same relay overhead, that mostly consists of re-done R1CS proof.

However, CPFP requires both txs to go into the block, eating from its size limit, while RBF does not. This is not a matter of traffic overhead, as both txs are usually already relayed anyway before block is ready, so they are not relayed twice. But from the perspective of the block signers, that is impossible to know.

Sequential payments

CPFP naturally enables to control priority when payments are chained (this is a common situation in Bitcoin and all account-based blockchains). Even if the parent was low-priority, if the child is high-priority, it can cover for the parent on the spot, w/o any extra overhead. The downside is that long chains/subgraphs of low-priority transactions with high-priority grand{^n}children make it harder to account for in mempool logic.

On the other hand, RBF permits compressing multiple payments in one tx: if another payment needs to be done, instead of chaining the transactions, user agent can replace the existing unconfirmed one, adding an additional output to it. This does not improve the relay traffic, but saves the block space: all payments that happen before the block is made effectively consume space for 1 payment. This seems like a win, but it is probably not: (1) the fees paid are not minimized as the final tx must pay the fees for all the previous ones, (2) for the final replacement to be successfully propagated, all prior versions would have to be widely propagated too (because you never know which one is the final one), which means the entire network would have to relay and validate all those transactions, regardless whether all of them or only one of them ends up in a block. Not using RBF and consuming the block space with all intermediate versions reflects the reality better.

Another downside of RBF: if the payment output is modified, the payment blinding factor must be re-communicated to the recipient (makes payment protocol more complicated); if the payment output is left alone, then the change output becomes clearly distinguishable (this is bad for privacy).

Zero-confirmation payments

Recent Bitcoin usage shows that without ubiquitous and well-capitalized payment channels network (lightning, or "layer two"), but well connected blockchain network ("base layer"), businesses are fine accepting zero-confirmation payments from non-RBF transactions. This goes in line with the general philosophy of blockchain design: all transaction are irreversible. Designing wallets to account for not just cancellation of incoming 0-conf payments, but non-guaranteed ability to replace its own transactions complicates things very much.

For this reason we tentatively assume that RBF is not worth supporting at all in order to simplify the logic of the wallet and mempools. The only thing that wallets need to support is re-filtering the mempool when a new block comes it, in order to kick out duplicate or conflicting txs.

Relaying CPFP

For CPFP to work successfully, one needs to make sure the parent transaction is not rejected by a node before learning about children that cover the required fees.

See the design discussion in Bitcoin on package relay and the proposed acceptance logic.

Note that Bitcoin's approach intentionally does not attempt to support RBF within CPFP package relay logic. No tx in a package is allowed to conflict with any mempool tx.

The basic idea is: the node may relay a package of transactions, that is judged as a whole when calculating a feerate. This allows including lower-fee parents with higher-fee children.

The PR 16401 works via relay of children as orphans first, and then when a parent is nearly rejected for low fee, it is checked if there are already known orphans that as-a-package make the parent worthy of inclusion. In order words, this does not employ any package-specific messages and assumes relaying of txs in random or at least high-feerate-first order (per my understanding).

Mempool eviction

When the mempool is full, it's lowest-feerate tx is evicted leaving space for the higher-feerate tx. Note that in case of CPFP/PDC, we only track those children with sufficient feerate and not their ancestors that have too low feerate on their own. When such child is evicted, all its insufficiently priced ancestors are evicted too.

This raises several questions:

What if the would-be-evicted set of transactions pays a higher absolute fee than the replacement?
The would-be-evicted set of transactions may have high relay cost (due to size), and if evicted, the replacement must justify such eviction by paying for that relay cost. In other words, the minimum required fee must be increased by the minimum relay feerate multiplied by the size of all evicted transactions.
What if some other transactions depend on some of the outputs that are evicted? This may lead to high-fee tx being evicted unless we do something smarter well before, when we group CPFP transactions.

stellar / slingshot

zkvm: fees mechanism #398