EVM: Figure out a way to divide L1 fees between transactions

[eyusufatik]

Currently every transaction pays for its own state diff. So they cannot benefit from multiple transactions affecting the same slots reducing the cost for a single tx.

We need to figure out how to divide this among all txs in the same soft confirmation block.

Also when we write to DA, we benefit from this too, so users should benefit as well.

[kpp]

One thing I should mention is that everyone with priority fees pays fees for changing coinbase balance now. As it is said in https://github.com/chainwayxyz/secret-sovereign-sdk/issues/261 , we pay priority fee thus changing coinbase in every priority tx.

So we need an idea of cumulative diff with some parts being common (shared) among all txs like coinbase addr. Also keep in mind that if an acc A does 10 tx with a transfer to acc B this is an equivalent of doing 1 tx with 10 transfers from A to be inside (the result diff has to be the same).

If we end up with a cumulative diff per block of all tx, then the first tx is going to pay more for L1 diff (because they touch coinbase balance first).

Also imagine two calls from different accs to a big contract which affects a lot of data (creates a big diff). These accs participate in an auction with a priority fee as a bid. If only the first changer of the diff is going to pay for L1 fee then then winning acc is going to pay all L1 fee as well and the loser is going to make it free. In some scenarios that may affect the idea of auction at all because it can be way cheaper to lose the action and gain more than the winner. That can lead to an unfair economic game.

So there are several ways to resolve the issue:

0) Current state 1) Cumulative diff per caller 2) Unfair cumulative diff per block 3) Fair cumulative diff per block

===========================

0) Current state algo:

for each tx in block:
    diff = calc_kv_affected(tx)
    l1_fee = l1_fee_rate * size_of(diff)
    caller.balance -= l1_fee
    coinbase.balance += l1_fee

This has its own drawbacks:

a) 2 tx = [ A.transfer(B), B.transfer(C) ] will result in A and B paying same L1 fee which is fair. b) 10 tx with A.transfer(B) will result in 10 x L1 fee which is unfair for acc A but good for us (we benefit from it).

1) Cumulative diff per caller algo:

  kv_affected = {}
  for each tx made by caller:
     current_diff = calc_kv_affected(tx)
     actual_diff = current_diff \ kv_affected
     kv_affected += actual_diff
     l1_fee = l1_fee_rate * size_of(actual_diff)
     caller.balance -= l1_fee
     coinbase.balance += l1_fee

This case solves several issues:

a) 10 tx with A.transfer(B) will result in the same L1 fee as 1 tx with 10 A.transfer(B) inside 1 tx which is fair. b) 2 tx = [ A.transfer(B), B.transfer(C) ] will result in A and B paying same L1 fee which is fair. c) 10 tx with A.transfer(B) will end up with the first tx paying L1 fee and the rest are free.

The b) case is fair game for A and B however they end up paying for total 4 changes: (-A.balance), (+B.balance), (-B.balance), (+C.balance). So we end up with an extra diff for B thus we gain 1 free change = (4 calc changes) - (3 actual changes). This is good for us (we benefit from it).

2) Unfair cumulative diff per block algo:

  kv_affected = {}
  for each tx in block:
     current_diff = calc_kv_affected(tx)
     actual_diff = current_diff \ kv_affected
     kv_affected += actual_diff
     l1_fee = l1_fee_rate * size_of(actual_diff)
     caller.balance -= l1_fee
     coinbase.balance += l1_fee

a) 10 tx with A.transfer(B) will result in the same L1 fee as 1 tx with 10 A.transfer(B) inside which is fair. b) 2 tx = [ A.transfer(B), B.transfer(C) ] will result in A paying L1 fee more than B which is unfair. c) 10 tx with A.transfer(B) will end up with the first tx paying L1 fee and the rest are free.

With this solution we gain the correct (fair) amount of L1 fee but results an unfair game in case b).

3) Fair cumulative diff per block

This can be achieved in two ways. The first way is to run all txs twice: calc diff during the first run, the second run: don't calc diff but only insert L1 fee per caller in the first caller tx. The second way: run all tx once, calc diff per caller and insert a system tx in the end (or beginning of the block) with a big tx with L1 fees going to coinbase. Here is the algo how to calculate the diff:

  caller_changed: Map Address => (Set Key) = {}
  key_n_changed: Map Key => Int = {}
  reserved_l1_fee: Map Address => Int

  for each tx in block:
     current_diff = calc_kv_affected(tx)
     l1_fee = l1_fee_rate * size_of(current_diff)
     reserved_l1_fee[tx.caller] += l1_fee
     assert tx.caller.balance >= reserved_l1_fee[tx.caller]

     caller_ch = caller_changed[tx.caller]
     for key in current_diff
          if key not in caller_ch
              caller_ch.insert(key)
              key_n_changed[key] += 1

  diff_per_caller: Map Address => Float = {}
  for (caller, keys) in caller_changed
     for key in keys:
         key_weight = 1 / key_n_changed[n]
         diff_per_caller[caller] += key_weight * size_of_value(key)

Now there is a Map diff_per_caller with diff_size per caller divided between txs and callers inside block.

a) 10 tx with A.transfer(B) will result in the same L1 fee as 1 tx with 10 A.transfer(B) which is fair. b) 2 tx = [ A.transfer(B), B.transfer(C) ] will result in A paying L1 fee = 1 diff for A.balance and 1/2 B.balance, B paying L1 fee = 1/2 B.balance and 1 C.balance which is fair.

There is a drawback : the balance of the caller must exceed sum of l1_fees per tx as if they are executed 1 tx per block. This is a strong requirement because we need to make sure the caller can pay L1 fees for all of their txs in a block. This requirement can be relaxed by optimizing the algo to check if a caller is able to pay L1 fees as if the block contains only txs of that caller (see algo 1) Cumulative diff per caller).

[eyusufatik]

we can utilize a system transaction at the end of a block to this actually.

Or even better at the beginning of a new L1 block, along with set block hash system transactions. but that tx would be too big probably.

anyways, on the first case:

• CitreHandler keeps track of an in block "diffSize" and reimburses tx senders at the end of the block through a single tx over a smart contract.

[eyusufatik]

In a state diff rollup there is no "true" way to split L1 fee among transacters, so we'll have to make simulations and have a statistical system that lower costs for accounts optimistically.

This simulation can be done over Ethereum blocks for different range of heights, keeping track of the percentage of the nodes on the state tree that were updated more than once. Then we'd be able to apply a discount to all L1 fees paid by this percentage, making it cheaper for every transaction.

[kpp]

Stat was collected, the discount was applied