State Fees (formerly State rent) pre-EIP proposal version 3

storage-rent

#1

Version 3 is now up for discussion.
Main changes compared to version 2:

  • Replay protection for externally owned accounts changed from temporal to non-temporal to ensure that account nonces are never reused (reuse of nonces allow re-creation of contracts)
  • Lock-ups are replaced with rent prepayments. Prepayments provide protection from dust griefing vulnerability, though temporary rather than permanent. Prepayments cannot be released, which avoids issues of changing economics of some smart contracts, like DEXs
  • State counters are introduced to make the state size metrics trivially observable, as well as to provide future path for floating rent, if needed.
  • Transaction format is not modified
  • Functionally of gaslimit (field of a transaction) is extended so that gaslimit*gasprice limits prepayments
  • Floating rent and “clean” eviction of contracts are re-added for completeness as optional changes

https://github.com/ledgerwatch/eth_state/blob/master/State_Fees_3.pdf


State Rent proposal version 2 (rushed)
#2

Oops looks like I responded to the wrong topic here: State Rent proposal version 2 (rushed)

My comments on there still apply: is there a more detailed document somewhere where I can find the details of the current proposal? Via V3 I first need to look over the base version and then understand the changes made to it - this adds some overhead because I might have some problems with the original version but then find out that this is fixed in V3 =)


#3

Thank you for reading!
I am sorry for the overhead. I have been writing proposals in that form because it was easier to start with, and I expected them to be presented in this form to get feedback. But there were not sufficient opportunities to present (mostly because it was not a lot of time since it all started, and I am very limited in my ability to travel around the conferences). At some point - most probably with the version 4, I am planning to add a more detailed commentary paper.


#4

Allright I will stick with this version then!


#5

Why not move the entire current state off-chain, add stateless witnesses to blocks and implement state rent as something separate, for those that want on-chain state?

If state fees are implemented, I think new contracts will move to the stateless design with cache, rather than to the create2 subcontract variant to keep fees lower. If that’s correct, making the protocol stateless by default would end in a better place resources-wise, because protocol-level implementation would be faster and more space efficient.
Most importantly, it would require no contract migration - perfectly backwards compatible as far as current contracts and accounts are concerned, only nodes and wallets would have to change.

How - each mining node keeps 1 day’s worth of state changes. Each transaction includes needed state that’s older than 100 blocks from the tip at the generation time, as full branches from the state root from that block. Keeping 24 hours of state history allows mining node to solve state contention within those 24 hours. For this reason unconfirmed transactions would be unlikely to be confirmed after 24 hours, unless some node keeps older state, but I think that’s fine.
Needed state branches would be generated by miners, per block, connected to the state root of the ancestor block, potentially composing duplicated state from sent transactions (especially consecutive calls of the same contract in one block).

State rent would be added on top of that, with the difference being that on-chain state doesn’t have to be included in state branches, both in transactions and in blocks.


#6

Thank you!

I am currently developing a prototype (and it is kind of working, I am debugging around block 830’000 at the moment), that would calculate very accurately the witness overhead of this. Accurately because the prototype actually generates payload for witnesses and tries to execute the blocks only using transactions and the witnesses, and compares state and storage roots before and after the execution.

This would require a more complex prototype. However, this might also not solve one of the biggest problems with the large size (which straightforward witnesses do solve) - duration of the snapshot sync. With straightforward sync a node can start processing the blocks pretty much straight ahead.
Only including witnesses for things that are older than 100 blocks - this will require having snapshot sync that only syncs things modified in the last 100 blocks - but such snapshot is hard (or not possible) to verify (you would be at the mercy of your peers to tell you that the snapshot they gave you only contains recently changed items).

EDIT: It is definitely a great idea. Properly implementing it would require introducing a new state root in the blocks, which will correspond only to the items that have changed in the last 100 blocks. Then you can snapshot sync to that and start processing blocks with the trimmed stateless client.

One idea we heard (and we can check the viability using the data) is to introduce rent on accounts and code, but stateless clients on the contract storage. We shall see how much overhead that it.


#7

I am currently developing a prototype (and it is kind of working, I am debugging around block 830’000 at the moment), that would calculate very accurately the witness overhead of this

Interesting, do you have an estimate for how big it could be?

I meant that transactions - not in a block, but as sent to the mempool - include witnesses for a 100 block away - as a way to protect against orphans of recent blocks. It wouldn’t be a protocol rule, just a safe UX default, I guess it could be reduced to 10. Blocks would have only the most recent root.
You could generate a transaction with a witness from the tip and it could be included, assuming that block wasn’t orphaned.

this will require having snapshot sync

I don’t think snapshot sync is needed as far as pure stateless mode is concerned. Blocks would include the current state root, a new node could start validating straight away from the tip. You could start mining right away, after 10 blocks you could include transactions with witnesses from the last 10 blocks, after 1 hour from 1 hour etc.

Keeping 24 hours of state doesn’t have be enforced by the protocol - just as a node default. If some miner wants to only mine transactions that are at most 10 minutes old, at the cost of losing some fees, it’s his right.

It could be enforced in the way you described, but the only advantage I can see would be that new miners would be able to mine hours-old transactions instantly after fast syncing. If they want that, I think that could be better solved by off-chain protocols (eg. paid service that sells old state).

One idea we heard (and we can check the viability using the data) is to introduce rent on accounts and code, but stateless clients on the contract storage

It would solve what I think is the single biggest issue which is a free rider problem for token balances storage in current contracts.

I still think full stateless mode with on-chain state purely optional is a better way, for the state size too. Only contracts/accounts that are very heavily used would be on-chain. When some entity (eg. idex) would find out that witness fees in X days > state rent in X days, they would pay state rent for relevant contracts, saving block space for everyone that also uses them. A contract that’s only used once a year would be cheaper completely stateless.

Another argument is UX. Simple users wouldn’t even have to notice the change - as their wallet provider could provide witnesses for their accounts, at the cost of a slightly higher fees. Advanced users/developers would have the option to pay rent if they want.

It could be good to separate rent for code from contract storage rent. This way, most likely someone (eg. exchanges) would pay state rent for code of most used tokens as it would be relatively cheap and save them fees, but keeping contract storage stateless.

Potentially, optional on-chain storage could even come in a second fork after the stateless change, keeping everything fully stateless in the interim.


#8

Well, producing this estimate is the whole point of this prototype, so I will have data when it is done.

Verifying transaction against old state roots does not help anyone to execute them in the blocks - because they may have potentially touched different places in the state 100 blocks ago than now.

Generally, I would like this proposal (having stateless client with transactions dependent on old state roots) specified a bit more to analyse it properly. My current intuition is that it will not really work, but I do not want to spend too much time discovering exactly why, so I would appreciate some prior work on that.
In order to stay focused, I would also recommend keeping in mind the problems with the large state that we are trying to solve, as described here, here and here. For example, advanced sync protocol solves the first problem (failing sync), stateless client might solve the second and the forth problem (duration of the sync and state reads), and pre-warming the cache from the transaction pool may solve the third problem (slow block sealing).

Not only miners would like to be able to verify blocks as they come - some other nodes do too, otherwise the network would become a bunch of light clients connected to the miners.


#9

I’ll try to describe it in pseudocode. I was always bad at explaining my ideas.

Example execution:
A miner has all storage fields (key:value) that were touched in the last 1000 blocks in state dictionary.

In mempool, there are several transactions containing witnesses for blocks between X-500 and X-100 in transactionList. Each witness is a dictionary of (key:value) pairs - transactionWitnessList.

stateOldestBlock = currentBlockHeight-1000

For each block, the miner executes

newBlockWitness = {}
newBlock = Block()
newState = state.copy()
for transaction in transactionList:
  #ignore transactions we can't solve contentions for - state witness too old
  if transaction.witnessBlock < stateOldestBlock:
    continue
  for txStorageKey in transaction.transactionWitnessList:
    #add only storage fields that weren't updated after transaction's witness block
    #this solves contention
    if txStorageKey not in newState:
      newState[txStorageKey] = transaction.transactionWitnessList[txStorageKey]
   accessedStateFields, newState = newBlock.addAndExecute(transaction.txWithoutWitness, newState)
   #accessedStateFields is a list of (key:value) pairs of all storage fields that were accessed
   #during transaction execution
   for accessedKey in accessedStateFields:
     #this ensures only witnesses for state that existed in a previous block are added
     #as opposed to fields created in a new block
     if accessedKey in state:
       newBlockWitness[accessedKey] = state[accessedKey]
newBlock.addWitness(newBlockWitness)
state = newState
newBlock.send()
#prune state not accessed in the last 1000 blocks
state = removeFieldsThatWerentAccessedForNBlocks(state, 1000)
stateOldestBlock += 1

(details like checking nonces or rejecting transactions with incomplete witness not included)
So:

  • no state at all is required to verify blocks
  • state accessed in last N blocks is needed to include a transaction with a state root for a block of height N, which could be as short as 10 blocks, which should always fit in RAM. Ie. only validation of unconfirmed transactions needs some recent state.
  • no fast sync is needed at all (in the pure stateless mode)
  • memory/time needed for block sealing depends on how old transactions are allowed by the miner, which grows O(n lg n) where n is number of storage accesses during the allowed period

P.S. As for part 4 (parallel execution) I had similar ideas some time ago.


#10

I think you are good at explaining your ideas. Thank you for the pseudocode. However, I don’t think it goes deep enough to see the issues I am seeing. I suspect that if you go deeper into what “transactionWitnessList” actually contains, it is not just key:value pairs, but all the “surrounding” hashes, as you mentioned earlier yourself. These “surrounding” hashes would need to be updated even though the storage items that transaction is accessing did not change. If you mean that these would need to be verified against older roots, that is fine. But in order to actually verify the effect of this transaction on the “newState”, you would need to update the witness or have access to data “around” the path in the tree. What I am saying is that I do not think it is useful at all to the miner to have those proofs coming with the transactions - more likely than not, they will be mostly obsolete by the time transaction is included, even if transaction does not interfere with any items that were older than 100 block (which also needs to be investigated - how constrained this it).

Anyway, I do not think I will be able to implement this variant of stateless client, but I did implement the variant where block proofs are created by miners, and there are no transaction proofs (since I don’t think they can help the miner a lot). And this is what I am currently testing (it is just gone over 1.95m blocks).


#11

These “surrounding” hashes would need to be updated even though the storage items that transaction is accessing did not change.

Yes, but if the data is modified in the 1000 block period (or 24h etc), all new hashes are known from other transactions/blocks. Those hashes must be held by miners for 1000 blocks along with changed values, ie. all data needed to modify all accessed fields + value of them. This means the miner has all the hashes needed to change the tree with it, by combining a partially obsolete witness from an old unconfirmed transaction (within the 1000 block period) with data from the cache.

Note that this must be possible in the stateless model: if you have all the data needed to execute a transaction at block t, and save all state changes until block t+n, you must be able to generate a recent witness for your transaction. If that’s not possible, this means miners are executing transactions based on some data that’s not present in interim witnesses, ie. the model is not actually stateless.

As it must be possible, it can as well be done by miners.

What I am saying is that I do not think it is useful at all to the miner to have those proofs coming with the transactions

What if transaction is accessing two different fields, A and B. A is changed by a newer transaction and old witness is indeed obsolete, however B isn’t accessed by anyone else and is in a different tree node? Without a witness for B, the miner isn’t going to know the full path to it and its value.


#12

Would it be possible to write down the design rationale or requirements for this proposal?

The might be:

  • Avoid situations where a node does not get paid for cleaning up accounts risking a DoS attack.
  • Fee-rates need be flexible like any other operation as part of the block gaslimit.
  • Users should have guarantees about storage duration when paying fees.
  • Fees are fair over every byte of storage and not just accounts
  • Accounts don’t get deleted, but hibernated so that users are forever able to restore them.
  • Fees for any storage should be payable by any account
  • …

Did I miss anything?