Allow users to add a tip to the transaction

[PhilippGackstatter]

We should enable users to set a tip on the transaction. Either an absolute value or a value relative to the fee computed in the epilogue.

I think we have the following pros and cons:

• A relative value may make it simpler for clients because they don't have to come up with an absolute tip value.
• A relative value would have to be taken out of the vault together with the computed fee (because we can only compute the absolute value when compute_fee has calculated the fee), which means after the auth procedure has been invoked and so it won't be committed to by the standard TransactionSummary - in the current model. This might allow a malicious remote prover to modify this value (assuming it is provided via the advice provider). We could fix that by adding the relative value to the summary and therefore the commitment the user signs.
• An absolute value doesn't require changes to the summary because we could remove it from the vault before the auth procedure is invoked and so its change would be part of the account vault delta by the time the tx summary is constructed.
• An argument in favor of absolute values is that in EIP-1559 it is possible to calculate the minimum tip that would incentivize miners to include transactions and so we should be able to calculate this as well, which would give clients a default value.
• An absolute value is (obviously) independent of the computed fee, which may be a good thing if the reference block is rather old and its base fees are outdated. If for whatever reason a newer ref block cannot be chosen, but a newer block header is known nonetheless, then an absolute value allows compensating for an outdated ref block.

Also for reference from #1673:

My initial thoughts that there would be a pay_tip (or something similar) procedure that would take an absolute amount (or, probably, a TIP_ASSET). The tip would be provided non-deterministically, and pay_tip would be called in the auth procedure before we generate a transaction summary (and so, it would be covered by the signature).
@bobbinth

Overall, I think I would agree and go with an absolute value, provided via the advice provider.

As mentioned by @bobbinth:

For network transactions, we'll need to come up with something else. Maybe here the tip could be proportional to the base fee, or maybe based on some other parameters (not sure what yet). In either case, there probably should be a mechanism for a network account to specify something like max_fee beyond which it is not willing to go.

Perhaps network accounts should be able to specify a relative value in their "configuration" (e.g. next to note script roots it is willing to accept). That would automate the interaction away for network accounts.

It would be nice if we had a single mechanism covering both local and network transactions. If we had only an absolute value mechanism in the tx kernel, then a way to automate this for the network transaction builder would be by dry-running the transaction, but that seems undesirable for efficiency reasons. cc @Mirko-von-Leipzig in case you have any thoughts.

Broken out of #1673

[bobbinth]

Overall, I favor the absolute value as well. On the philosophical level, the tip should be independent of the underlying resource usage because the base fee is supposed cover resource usage. The two main reasons to consider tips proportional to the base fee are:

• It is not clear how to set absolute tip for network transactions. Though, maybe there is something that can be done here. If we are able to somehow estimate the level of network congestion (e.g., based on how base fee is going up), maybe account owners could use it to compute absolute tip for their applications.
• We may want to account for "fee drift". That is, we compute base at block $x$ but the transaction may get into the chain by block $x + n$, and by that time, the fee may have changed. If we really want to make sure our transaction makes it into the chain, we may want to set the fee at something like $1.1 \cdot computed\_fee$ (here the assumption is that the base fee cannot change by more than 1% and so, by paying 10% more we know that we'd satisfy the base fee of the next 10 blocks even in the worst case).

[Mirko-von-Leipzig]

If we had only an absolute value mechanism in the tx kernel, then a way to automate this for the network transaction builder would be by dry-running the transaction, but that seems undesirable for efficiency reasons. cc @Mirko-von-Leipzig in case you have any thoughts.

This seems like everyone would have to use this dry-running mechanism then? If so, we're forcing executing every tx ever at least twice twice which sounds bad.

Without knowing the internals I would want an api where the last thing I do is specify the tip. Basically execute the tx, be able to inspect the result, cost ito base computation units and then I can apply whatever fee formula I want.

[PhilippGackstatter]

Without knowing the internals I would want an api where the last thing I do is specify the tip. Basically execute the tx, be able to inspect the result, cost ito base computation units and then I can apply whatever fee formula I want.

That does seem ideal for maximum flexibility. The issue may be that the tx kernel does authentication and then fee computation/removal (and we can't change this). So if you inject the tip value non-deterministically after fee computation, it won't be covered by an account's auth procedure, where it can validate that what happened in the transaction is fine and generate a signature. Signatures are not important for network accounts afaict, but the account code should still be able to prevent the network tx builder from setting a $1000 tip. And if we inject the tip value non-deterministically after fee computation, then I think a malicious network transaction builder could do that. (Also depends on whether we want to build towards decentralized NTX building or not.) So I think we need a mechanism that allows the account to validate it, right?

With an absolute value, the tip asset would be removed by the time the auth procedure runs and so the account could validate that.
With a relative value, the account could check if the fraction is in it's acceptable range, e.g. between 1-3% of the computed fee.

If we are able to calculate a default tip, then an absolute value mechanism should also be fine, but I don't really know how to do that.

Otherwise, estimating the fee based on network congestion, as Bobbin suggested, may be an option, but it also sounds difficult to get right.

[Mirko-von-Leipzig]

Signatures are not important for network accounts afaict, but the account code should still be able to prevent the network tx builder from setting a $1000 tip. And if we inject the tip value non-deterministically after fee computation, then I think a malicious network transaction builder could do that. (Also depends on whether we want to build towards decentralized NTX building or not.) So I think we need a mechanism that allows the account to validate it, right?

Yes I was assuming there would be a separate procedure for inserting the tip which would still be validated by the account code. If you say this isn't possible then we don't really have any good options.

[bobbinth]

I think maybe to think this through we need to consider two use cases separately:

• For local transactions:
  • Specifying an absolute tip is pretty straight-forward (the user could do it directly based on observations of how congested the network is).
  • One question is how would the user to address "fee drift". But maybe this is separate from paying the tip.
• For network transactions
  • We can't trust the NTB to set the tip because NTB can be malicious. So, whether it is an absolute or a relative tip, it would need to be set by the code itself (most likely in the auth procedure).
  • So, the question is how would the an auth procedure define a tip for a transaction (e.g., it could be hard-coded, computed deterministically based on some inputs etc.)

The ideal approach would address all of the above - i.e., the local user can account for the "fee drift", and the developer of the network account could define the tip deterministically.

One potential way to estimate tip deterministically is based on how much recent transactions paid in tips. For example, if we tracked the min tip a transaction paid to get into a block in each block header, this could give some basis for estimating. Though, computing this min tip may not be trivial.

[PhilippGackstatter]

I thought a bit about what a batch prover needs as compensation.

From EIP-1559 Notes:

The tip has two functions: first, if there are suddenly far more transactions than expected, miners will include transactions with higher tips first, so the fee-based prioritization mechanism exists as a backup. Second, it compensates miners for uncle risk (the increased risk their block will not be included in the main chain because adding one more transaction will slow it down).

In our case, the question is whether we'll end up having "uncle batches" or not, e.g. if two batches include the same transaction, do they share the tip? It would certainly be easier without that, but I wonder if that wouldn't be a big unknown for batch provers. Basically, they can't easily predict whether their batch will be accepted entirely or if they'll lose out on all the work done.

Assuming we don't have these, applying this logic to batches then means that a tip should compensate a batch prover for the risk of including that transaction and loosing out on the entire batch's "tip revenue". That tip revenue can't be estimated though since tips are dynamic (in ETH this works because there is a static reward for blocks).

The risk depends on how much the tx slows the batch down. That slowdown should basically be proportional to the time it takes the batch to verify the transaction. In compute_fee we estimate that as being proportional to the number of cycles the transaction takes. So this is already captured in the computed fee, or in other words, it seems like the batch's reward should be proportional to the computed fee to compensate that risk. What that proportion is, is an open question, but perhaps it could be found empirically.

This makes me wonder if we could assign the batch prover a fraction of the computed fee as compensation (or reward / incentive) directly without having the user or network transaction builder estimate it somehow. (Technically, the computed fee captures other aspects of the transaction that don't concern the batch prover very much, like updating the nullifier and account tree or eventually the storage costs, but only making this based on the number of verification cycles would misalign incentives and may cause batch provers to preferably include transactions based on their cycles rather than on all aspects.)

The issue is that this would mean we don't burn the entire computed fee and as mentioned in the discussion the main problem with this was that if fees were not burnt but given to the batch or block producer it would allow them to costlessly simulate a first-price auction. The reason is that, to take ETH as the example, if the base_fee + user-defined tip goes to the miner, then users who aren't willing to pay the base fee b can pay it anyway, but tell the miner via a side-channel that they only want to pay b/2. The miner will include them in their block and refund them the difference off-chain. That way, they can effectively simulate a first-price auction and circumvent the protocol-enforced base fee.

I'm not completely convinced yet whether this applies or does not apply in our case. I think the batch kernel would have its own compute_fee implementation and calculate the transaction's required fee, i.e. the part that is entirely protocol-defined. Then it takes its protocol-defined share from that, e.g. 10% or something. Nothing about this can be influenced by the batch prover because it is batch kernel logic. Separately, it will take the transaction's optional tip to allow for prioritization.

As an example:

• A transaction has a computed fee of 100 and sets a tip of 10.
• The tx's ref block is older than the batch's and the base fee has gone up.
• The batch prover includes the transaction and computes the tx's computed fee to be 105 (due to a higher base fee) - leaving a tip of 5. So the tip happens to account for "fee drift".
• The batch prover takes 10% of 105 as its revenue plus the tip of 5.
• The remaining fee is burnt.

The fact that part of the fee is still burnt means the fees aren't fully recoverable and so the first price auction simulation concern does not apply, at least not in full, I think.

I'm not convinced that this is all correct tbh, but if it is then:

• This serves as an incentive for batch provers to include transactions.
• It would allow clients/wallets to default to a zero tip unless the network is congested or the ref block is too old, but both of these should be exceptions rather than the rule. Only then would a tip be needed to prioritize a transaction, but by default, batch prover's would already be incentivized to include transactions based on their assigned share.

---

If that is too complicated or doesn't work, then I would stick to a pay_tip procedure that allows transaction builders to specify an absolute value from the tx script rather than auth procedure (so that we don't have to include fee logic in standard auth account components).
Then as suggested, we include minimum accepted tip in block headers. We can output the tip of each transaction as part of FEE_ASSET (there is one unused 0 value) or in some other way, and include the min of all of those in the block header. If clients want to apply advanced logic, they can look at the past x block headers and take the average of that or something to that effect.