Pre-RFC: Replace state deposits with a new system

[rphmeier]

cc @jonasW3F - I am hoping you could have some insights here.

Every piece of state in Polkadot and its system parachains requires a refundable deposit. These deposits are currently configured statically. When deposits are too high, they act as a retardant on growth and usage. When deposits are too low, they increase the risk of the state filling up with junk.

The current system has a few drawbacks, which are the motivation for this discussion:

1. State on Polkadot has historically been mispriced relative to its abundance. The existential deposits pose a barrier to entry which has historically limited usage and the development of network effects. In 2021, the existential deposit exceeded a $50 USD value.
2. The current system requires lengthy governance processes and human intervention to alter the DOT value of deposits, making the price of state slow to adjust to new information.
3. There is no price discovery for state. When state is abundant, it should be cheap. When state is scarce, it should be expensive.

I have a couple of observations which circumscribe a solution:

1. Maximum state sizes are measured in billions of items. This means that the storage price per-item should be extremely low. Fees may not even be noticeable. As such, there isn't much need for them to be refundable. SSDs are improving in capacity rapidly, and prices should reflect this trend over time.
2. Polkadot should sell state cheaply unless it is filling up rapidly. When the state is empty (i.e. new state is abundant), the cost of new state items should be close to zero. However, it's also a bad idea to quickly sell off all the state: Polkadot should protect a scarce resource and provide some market pressure to limit excessive purchases. It can provide this market pressure by increasing the price of new state when it is being created rapidly.
3. State can be purchased back as needed. Rewarding users for freeing state only makes sense when there is state size pressure. When there is state size pressure, incentives to move away are beneficial. This does create an incentive for speculation on state, but that can be limited by (2).
4. State prices should be set according to their real value, not their nominal value in DOT. There needs to be a reasonable price discovery mechanism for the value of state in DOT to avoid state mispricings due to token volatility.

I'd appreciate input from economists and some help ironing this out into a full RFC.

[shawntabrizi]

Ideally, beyond just the economics of the deposit, we also would find a way to make integrating deposits into Polkadot development ergonomic and automatic:

paritytech/polkadot-sdk#328

A perfect system for me, is one where we just call the storage write operation, and the fee is automagically withdrawn or the transaction is reverted. Additionally, exposing these "hidden fees/deposits" somewhere so that wallets can expose those needs to the user.

Such a system could be used for all storage deposits across the pallets.

Obviously not looking to expand this RFC to something which cannot be spec-ed all at once, but things to keep in mind around this topic.

[rphmeier]

Yes, I hope that the eventual result of this RFC is to just make storage fees a normal fee and completely opaque to users. If the transaction results in the creation of new state items, the user is charged a fee at the end, and the transaction reverts if they don't have enough to cover it.

It has all the caveats of predicting fees and weights, but if we can set an upper bound on the maximum storage fee within e.g. 30s of the transaction being submitted, it should be easy enough to budget for within the transaction.

[xlc]

In Acala EVM, we charge/reserve a storage deposit for any (net) storage write in an EVM call. The SDK will estimate it and generate a storage limit and factor this into gas price. In the end, user sees a gas limit and a gas price. It ensures security without compromise UX.
It is currently possible to measure storage proof of a particular tx so I see no reason why we can't measure net storage write for a tx and charge fee based on it. We can easily create a signed ext to specify storage fee limit or just use existing tip for it.

[rphmeier]

I see no reason why we can't measure net storage write for a tx and charge fee based on it.

I completely agree. It's good to have some evidence that measuring this is simple in Substrate too. You should view this RFC as a way of determining how that storage fee is calculated.

[burdges]

In principle, one could run migrations which flushed old junk accounts into historical trees, so you could prove them somehow, but they do not occupy the current state per se. I've no idea if such flushing ever really makes sense, but..

You could've 4ish state trees representing different ranges of orders of magnitude for balances. At the smaller end, you pay more since the collator must fetch your account from somewhere slower, and the merkle proof gets bigger. It's just tiered service based upon balance.

Art NFTs could probably be optimized differently: One collection is one account, so all tx go through the account maintainer, who collects several of them, and then does a tx, but also takes DOT donations to do the tx sooner.

Also, there exists a probabalistic micro/macro-payment trick, so that many people could sign a non-micro payment to the collection maintainer, but the maintainer counts it only as a micro payment. In brief, places these into a Merkle tree, and the reveals the ones that some randomness says actually pay him.

[kianenigma]

1. Indeed, this opens the door for things similar to https://gastoken.io/. I am not yet sure if this is good or bad in the grand scheme of things, but as you put it, you can now "speculate on state".
2. I think we can get 80% of the benefits that people end of the day want by doing the right 20% of the job: starting with 4, a reliable price oracle available to Polkadot Hub (RC + system chains). If we then still say that each byte costs $0.0001, I think most people will be pretty happy. Contrary, if we do all the other items you noted, but it is all denominated to the volatility of DOT, it is more likely that a big spike in the DOT price will worsen the UX. Further, things being denominated in DOT will attract more opportunistic activity such as the mentioned speculation, which I anticipate will still further worsen the price for the average user who just wants to use the system day to day.
3. It is also worth noting that the system configurations of Polkadot in AH is way more liberal than the RC. So as more functionality is moved there, everything will only ever improve.

[rphmeier]

I think we can get 80% of the benefits that people end of the day want by doing the right 20% of the job: starting with 4, a reliable price oracle available to Polkadot Hub (RC + system chains). If we then still say that each byte costs $0.0001, I think most people will be pretty happy.

Just to follow the logical conclusion here: $0.0001 is $100k per GB and $100M per TB. I do think the simple approach of setting state fees cheaply would be better than the current system for incentivizing growth. There would just be an overhanging risk of state buyout when valuable apps are built.

Contrary, if we do all the other items you noted, but it is all denominated to the volatility of DOT, it is more likely that a big spike in the DOT price will worsen the UX. Further, things being denominated in DOT will attract more opportunistic activity such as the mentioned speculation, which I anticipate will still further worsen the price for the average user who just wants to use the system day to day.

First, I don't think the incentives for speculation are actually very good, because getting paid involves a bunch of contingencies like the state actually filling up and the system having some capital to pay with.

Second, avoiding some volatility was the intention of observation (4). Prices should shift according to real value. I'm not sure how that mechanism should look.

[jonasW3F]

I've started to write down some ideas but it got longer and longer, so I probably just link a hackmd here instead of dumping some draft here.

My first intuition is to create a market that commoditizes the overall state and create some derivative in the form of "state credits". These can then be tradeable. This would have key benefit of being able to dynamically obtain a market price based on the demand and supply and it would retain the incentives to clean up the state if the opportunity costs of keeping it becomes too large. As others pointed out, that would potentially lead to "speculate on state", which I don't see as a big issue as it is abundant right now and might be for a long time. It could also be a viable strategy to buy state credits and then find ways to bring in more users, to essentially make a gain. I haven't thought it fully through and discuss some challenges in the document.

[rphmeier]

Thanks @jonasW3F

I'll add a little feedback to align on the problems worth solving. I'll bucket these into two categories: engineering concerns and cold-start concerns.

---

Engineering concerns:

It's better to minimize on-disk bookkeeping. If you have to annotate state items or accounts with credit or deposit amounts, this increases per-block I/O (reducing throughput) and reduces effective state capacity simultaneously. The ideal solution would not require additional space or time complexity for on-disk bookkeeping per state-item. Having bounded complexity for bookkeeping is more achievable, but I/O really shouldn't be logarithmic in the total number of state items unless you have a really tight practical bound on that.

Offering to have the ED or costs paid by others is interesting. I would hope that this could all be solved with the same machinery we already have for submitting transactions on behalf of other accounts. Simplicity makes a solution more achievable.

---

Cold-start concerns:

With this discussion I am interested in improving the cold-start situation for the Polkadot Hub or other chains in the ecosystem. That has to be balanced with the dual goal of bounding state sizes: if state growth is unsustainable, you have to reduce execution time (this is the real reason Ethereum's gas limit is low).

The main cold-start problem is to reduce complexity and cost for end-users and builders.

I'm somewhat wary of solutions that add more moving parts and derivatives. Like coretime, these kinds of derivatives need a certain market maturity in order to function well, and so they come with an accompanying cold-start problem.

As far as having storage costs paid for by others, this brings in another cold-start problem in the form of finding actors willing to pay those fees. A generalized first-party solution would be interesting.

---

State reclamation is not high-priority, in my view, because it only becomes relevant as the remaining state space approaches the rate of consumption. SSD $/GB is likely to outpace state growth in all but the most popular chains. In terms of roadmap planning, I think that we just need to have a credible commitment that the parts are in place to do this in the future. That's as simple as ensuring that the runtime can track the amount of freed storage space, and providing pressures against state growth acceleration. That one requirement sufficiently opens the design space for all kinds of payout schemes conditional on releasing occupied space, and would be credible.

I think at some point we should switch to something like fungible state credits that are issued when you clear a state item, but that's not a major concern until nearly full.

[rphmeier]

I'll devote this post to a sketch of how to implement this. Please read this as a rough idea.

A couple bits of on-chain state:

1. A State Growth Oracle (SGO). This indicates the current rate of state growth
2. A Target Growth Rate (TGR). This indicates the targeted rate of state growth. Configured by governance.
3. A State Fee Multiplier (M). A single value, which is adjusted according to the relationship between the SGO and TGR.

Every transaction will pay an additional fee for each state item created. This is automatically deducted from the sender's balance and the transaction fails if there is not enough to cover the amount.

The fee for creating a single state item will be M DOT. M is adjusted based on something like a PID controller using the SGO and TGR. We can add more complexity here. But whenever state is underpriced relative to demand, the multiplier M should rise to forestall it. The actual amount that a user pays to create a state item will be M plus the fee for the weight of compute and I/O needed to create the state item (fluctuates according to the market for execution weight).

About the SGO: Constant on-disk bookkeeping is key. You could use a weighted average for a sliding window of N blocks. You could also use something like a Merkle Mountain Range to do logarithmic-space bookkeeping for very long windows of blocks. Having a long enough time window to avoid sudden spikes in fees is beneficial.

There are other variables we can bring in, like the total state size and the expected state size at the given moment. That would allow fees to be more forgiving during surges when there is an overall "state surplus".

[jonasW3F]

I'm somewhat wary of solutions that add more moving parts and derivatives. Like coretime, these kinds of derivatives need a certain market maturity in order to function well, and so they come with an accompanying cold-start problem.

If we can properly integrate all mechanisms that are necessary, I'd be less concerned about a cold-start problem here. For example, we'd want an AMM on AH where the Treasury can function as LP to provide substantial market depth for state credits initially. We should also allocate a substantial share of the credits to already active participants in the network. With regard to end-users, the goal must be to hide the complexity introduced. The ideal situation would be that a non-power user performs their task (such as creating a new account) and the costs to acquire the necessary state credits are included in the transaction fee. If a user frees up the state, the transaction fee includes the revenue they receive from selling the state credit on the spot market. In other words, the market would have a lot of activity very quickly simply by the fact that every user in some way accesses state credits. Only power users would engage in actively transferring and trading state credits.

As far as having storage costs paid for by others, this brings in another cold-start problem in the form of finding actors willing to pay those fees. A generalized first-party solution would be interesting.

I also don't think this is a real problem, because first, we'd expect the prices to be very low in situations for quite some time and second, Treasury and governance might make direct allocations to players in the ecosystem that it regards as useful. Once these credits become worth more, it directly translates into the costs to acquiring new customers for projects wanting to onboard new users. Historically, start-ups plan to allocate substantial resources to acquire new users, allocating state credits would be just one minor point in their calculation.

It's better to minimize on-disk bookkeeping. If you have to annotate state items or accounts with credit or deposit amounts, this increases per-block I/O (reducing throughput) and reduces effective state capacity simultaneously. The ideal solution would not require additional space or time complexity for on-disk bookkeeping per state-item. Having bounded complexity for bookkeeping is more achievable, but I/O really shouldn't be logarithmic in the total number of state items unless you have a really tight practical bound on that.

This could be a real problem and evaluating the trade-off might make my proposal unfeasible. I guess using additional space in the face of such abundance might not be the biggest problem, but the impact on throughput and performance might be.

While I think a competitive market is the best way to determine the price and make resource allocation efficient, the overhead in developing such a solution, properly integrating it and the performance costs could very well make it more worthy to go for something simpler. The good thing, as you said, is that we can switch to a market solution once we exhaust state availability and we need to find ways to incentivize freeing up state.

I'll look into alternative ways of dynamic pricing.

[PolkadotDom]

I would think whatever is decided here would preferably be generalizable to other parameters across the system. We could then use it for the other x's/dx's we've thus far hardcoded, e.g. state usage ^, unstaking flux, vote delegation liquidity.

These types of ideas seem to be rolling in frequently now, so probably best to have a unified strategy/some small set of applicable strategies.