I like it! It has some quirks to work out.
I think this slightly undersells the cost from the transaction sender’s point of view. 
Transactions that get mined as failing due to an insufficient witness would be a major annoyance.
State availability becomes consensus-critical
Miners need to be able to include a transaction that has an insufficient witness as failed, to collect the gas. If miners couldn’t include under-witnessed transactions, it would be easy to DoS nodes by forcing them to verify a flurry of 8 Mgas transactions that are missing one witnessed value, but only after successfully executing 7.9 Mgas.
Getting your transaction included as failed with a missing witness sounds pretty awkward/painful for transaction builders near the epoch boundary. You build the transaction based on the pre-ReGenesis state, then while the transaction is pending, all state disappears at the boundary.
As prevention, transaction senders could pay to include the witness when the current tip is a few blocks behind the epoch boundary, just in case it takes a while to get included. How many blocks behind the epoch should senders consider doing this? It depends on gas pricing, which might fluctuate after you send the transaction. Depending on the transaction, it might add significant cost to witness the transaction “just in case”. (Side note: this seems mostly fixed when transactions get an “expire by block number” field.)
In addition to gas cost, I can imagine this being quite a challenge for in-browser web3 clients to support. If your node doesn’t have the cold state, the web3 client has to notify you and/or help you build the state proof. It would be an absolute requirement for every web3 client to support this, because sending transactions at the epoch boundary would be impossible without it.
Rolling ReGenesis
One mitigation would be a “Rolling ReGenesis,” where we only drop state that’s been cold for one entire epoch. State would be split into an aged database and a current database.
All EVM reads would cascade, so they attempt to read from the current and then aged database. If it is necessary to read from the aged database, then the value gets copied into the current db.
At every block_num % EPOCH_LENGTH == 0:
- The node deletes the aged database, which was formed one epoch ago.
- The node moves all current state into an aged database, which becomes read-only.
- The node creates a new current database.
- All transactions must now include a witness for any state that is not in the current or aged database.
This should significantly reduce the impact on active contracts and accounts. An account that sends a transaction once every EPOCH_LENGTH blocks would not need to attach a witness for a simple payment transaction to an active account. When you interact with a contract, the relevant storage has often been read or written recently, too.
We can pick EPOCH_LENGTH such that it’s typically unnecessary to provide a witness at any block. I like 1M, but we should let mainnet backtests guide us. A nice target might be something like 99.9% of transactions not needing any witness.
Committing to dropped state
Another question is whether to include some commitment to which parts of the state are available, and how often. At one end, we could include a commitment at every header that describes the ranges of keys that are cold. At the other end, we could have it be entirely implicit.
I think this decision is independent from whether we use the original “clean slate” ReGenesis or the Rolling ReGenesis.
Explicit Approach
This helps quickly identify if nodes form different beliefs about which state is available. This seems like the safest route, but requires more coding and longer ACD discussions.
Some options:
- Add a new field to the header. For example, add a hash of an SSZ-encoded list of key prefixes.
- Force a custom storage value into a hard-coded account
Implicit Approach
Each node tracks its own state availability from block to block. Consensus errors might not cause a chain split immediately. The chain would only split when transactions touch the part of the state that nodes disagree on.
It weakens the verification that fast sync (or beam sync) can do. It’s not possible for these sync approaches to identify whether state is available by asking peers to prove a commitment. These sync methods would have to assume that witnesses are always sufficient (or insufficient, if the transaction fails due to a bad witness).
Further, ReGenesis makes it awkward for fast-syncing/beam-syncing nodes to know when they have finished backfilling all cold state. In the status quo: if a hash in the state trie is missing, that just means that you don’t have it yet. With ReGenesis, you might not have it yet, or it might be a pre-RG value. That means we probably want a new type of response to GetNodeData where a peer indicates that it is unavailable state. There is no way to prove the response is true in the implicit approach.
So it seems to be worth paying the technical costs of explicit commitments to state availability.
Ethereum Name Service
Some storage is read often, but rarely read on-chain. ENS comes to mind. So its registry would typically get forced into cold state, despite being actively used.
This would significantly decrease the benefit of using an ENS name. ENS is supposed to be easier and friendlier to folks new to Ethereum. With a ReGenesis-activated chain, an address publisher has to worry about how to help the noob find the cold state to look up an ENS name. That tips the balance in favor of just using the hex address, I think.
Maybe this is just an acceptable cost of ReGenesis, but it seems worth getting input from the ENS org.