ACP-83: Dynamic Multidimensional Fees for P-Chain and X-Chain

[avalanche-foundation-admin]

Introduce a dynamic and multidimensional fees scheme for both P-chain and X-chain. A dynamic fee scheme helps to preserve the stability of the chains as it provides an economic incentive for users to hold their transactions issuance in times of high load. A multidimensional fee scheme ensures that different resources consumed to process transactions, like bandwidth, chain state occupation and cpu to verify cryptographic signatures, are metered and priced differently, according to their different capacities. When network resources are independently metered, they can be granularly priced and thus optimally utilized by the network participants.

https://github.com/avalanche-foundation/ACPs/blob/main/ACPs/83-dynamic-multidimensional-fees/README.md

[aaronbuchwald]

Couple of thoughts on ACP-83:

Would it make more sense to replace UTXOReads and UTXOWrites with reads and writes? I don't think there's a direct need to specify the type of reads/writes? Just like the HyperSDK specifies the resource being used instead of what it's used for, I think it would make more sense to call the dimensions Reads and Writes rather than making it specific to UTXOs.

What is the research that indicates an exponential fee update rule provides greater stability?

How will block building work in the new paradigm? Assuming transactions are sorted by their priority fee, how should a VM handle the situation that one dimension is nearly full, such that the next transaction cannot be added even if there is room for more transactions along a different dimension?

What is the merit of deriving the complexity limits from the actual block history? Can we additionally measure or estimate a reasonable amount of each resource to consume per discrete time interval and place bounds accordingly? I think it would make more sense to estimate the actual target rate we want and adjust as needed to ensure it can appropriately handle the full block history.

With multiple dimensions, if one dimension changes it alters the fee paid by each transaction in the mempool and changes the amount leftover for the priority fee. How will the mempool maintain the ordering by priority fees?

[dhrubabasu]

Would it make more sense to replace UTXOReads and UTXOWrites with reads and writes? I don't think there's a direct need to specify the type of reads/writes? Just like the HyperSDK specifies the resource being used instead of what it's used for, I think it would make more sense to call the dimensions Reads and Writes rather than making it specific to UTXOs.

This change is coming with #93 (DBReads and DBWrites)

[dhrubabasu]

What is the merit of deriving the complexity limits from the actual block history? Can we additionally measure or estimate a reasonable amount of each resource to consume per discrete time interval and place bounds accordingly? I think it would make more sense to estimate the actual target rate we want and adjust as needed to ensure it can appropriately handle the full block history.

I'm a big fan of determining what limits we want for each dimension outside of the actual block history. Certain large transactions on the network have historically caused instability so I think we should not be looking to accommodate the entire full block history.

[aaronbuchwald]

As mentioned by @dhrubabasu today, we could also borrow from the ideas in https://amplab.cs.berkeley.edu/wp-content/uploads/2011/06/Dominant-Resource-Fairness-Fair-Allocation-of-Multiple-Resource-Types.pdf

[aaronbuchwald]

This was also referenced here: https://ethresear.ch/t/multidimensional-eip-1559/11651/5

[meaghanfitzgerald]

We have planned a meeting to discuss live this coming Wednesday at 15:30 UTC. See the announcement for more details: #96

[aaronbuchwald]

I think we should try to launch ACP-77 in the next upgrade prior to ACP-83 (at least the multidimensional fees component).

ACP-77 includes a new dynamic fee for the cost of keeping current subnet validator sets in memory. This fee was combined into ACP-77 to ensure that after ACP-77 launches, projects can launch onchain programs to manage their validator sets and do not need to handle a network upgrade that changes the validation flow shortly after.

Since it was clear that the continuous fee associated with storing subnet validator sets could change that interface depending on the implementation, it was important to spec it out fully and consider including it in ACP-77.

Now that it's spec'd out, I think there's a clearer separation between the dynamic fee for the continuous fee in ACP-77 and for general resources consumed at the time a block is processed (compute, read/write, bandwidth) and multidimensional fees. There's clearly more complexity coming from multidimensional fees and there's no urgent need to handle it in the next network upgrade.

Specifically, handling multidimensional fees turns block building into a knapsack problem. There are various approximations to handle this as mentioned above (#89 (comment)), but if we try to lump it into the next network upgrade, I'd estimate that it pushes back the timeline by > 1 month and would reduce confidence level in it significantly (assuming that we adapt an approximation algorithm not originally designed for a byzantine environment).

Luckily, the current design of ACP-83 makes it pretty clear that this won't cause any significant changes to P-Chain transaction formats, so anyone integrating post ACP-77 should not be impacted in a meaningful way. Specifically, ACP-83 proposes that the multidimensional fee payments come are paid in the same way that fees are paid now, where the total amount going towards the fee is simply sum(AVAX inputs) - sum(AVAX outputs). The difference goes toward the fee, which currently must be greater than or equal to the fixed fee required for the specified transaction. With multidimensional fees, the difference must be large enough to cover the current cost and amount of each resource consumed by the transaction. An alternative design would have transactions specify a maximum fee paid per each distinct resource. For example, txA will pay <= 30 nAVAX per unit of compute, <= 20 nAVAX per read, and <= 15 nAVAX per write. This would require changing transaction types and make handling the multidimensional fee upgrade more cumbersome for teams that integrate immediately after ACP-77.