ReGenesis - resetting Ethereum to reduce the burden of large blockchain and state

@mandrigin has done an explainer for this post here: https://medium.com/@mandrigin/regenesis-explained-97540f457807

1 Like

Am I correct in thinking that the networking requirements will go up and down in a sawtooth fashion? That is, as the start of a new million blocks, nodes start with zero state. Transaction senders will need to send witnesses for all state. The network bandwidth to send blocks will be high. Over time, as more state is included, less and less state is needed. The bandwidth to send blocks will decrease. Then at the end of a million blocks, the nodes discard all of their state and start again.

1 Like

That seems correct indeed. It will be interesting to see if uncle rate is affected by this, though it probably won’t based on some previous experiments with CALLDATA size.

1 Like

The networking requirements be more even if a “moving window” state caching strategy was used. That is, nodes are expected to keep state for the past X blocks. Any state that hasn’t been touched in the past X blocks must have a witness for it.

1 Like

Yes, it is correct to expect that the traffic usage will go up after the reset and quickly level off after that. Good news is that we can backtest it.
And it is true that there is a similarity between ReGenesis and the “moving window” state caching strategy that I called “Semi-Stateless” in the past. The reason why ReGenesis might be preferable is because it is simpler and less error-prone to implement. Moving window state caching requires tracking for each state item when it was last touched. Evicting items very frequently (as frequently as every block) also adds non-negligible overhead. And all of that as consensus rules - I had not had a strong belief that this could ever be deployed.
With ReGenesis - the caching policy is very simple and blunt - which makes is more attractive at a cost of slight loss of elegance in the beginning of the reset cycle

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. :slight_smile: 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:

  1. The node deletes the aged database, which was formed one epoch ago.
  2. The node moves all current state into an aged database, which becomes read-only.
  3. The node creates a new current database.
  4. 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.

3 Likes

That is the current idea. Transactions with insufficient/invalid witnesses are included, but fail to make state transitions. However, the correct parts of the their witnesses are added to the active state

1 Like

iiuc, say an account wants to send a txn after the first Regenesis (at block #13,000,001), then the block would need to include witness data of the account’s balance just prior to the Regenesis block (at block #13,000,000).

But say an account has been dormant for several generations (periods between Regenesis events, say 1 million blocks), and wants to send a tx at block #17million+. Wouldn’t the block need to have witness data in the form of exclusion proofs for all the intermediate generations: an exclusion proof for the 13th generation (blocks #13m-14m), and exclusion proofs for the 14th, 15th, and 16th?

2 Likes

I have not prototyped it yet, but I think the answer is no. And the reason is that in most cases, the witnesses provided with the transactions, will be partially correct. Which means that their computed root will definitely be incorrect, and a lot of intermediate hashes close to the top. But, as long as the leaves contain correct information, at some point on the path from the root to the leaf, the root of a subtree will be correct. And this will be detected when comparing the witness (recursively from the root) with the current active state. Obviously, any witness would need to be constructed based on the state snapshot which is at least as fresh as the latest ReGenesis event

You’re right, there’s no need for exclusion proofs. I had misunderstood the proposal. I was imagining that each Regenesis event would create a new (empty) state tree, i.e. every Regenesis block would have the null state root, and active accounts would be inserted into this new tree. Kind of like the “sleep + wake” ideas discussed in old threads.

But reading again, the Regenesis events only drop the “implicit state”. There’s no new state tree. And witness proofs are always generated for the state root in the previous block, the same as regular stateless blocks (rather than a “sleep + wake” system, which would need exclusion proofs for the dormant periods).

this requirement is much more relaxed in ReGenesis. Witness can be generated based on any state root from the latest ReGenesis event until now. Since witnesses are included with the transactions (unlike in Stateless Ethereum, where they are in blocks), we cannot expect them to be up-to-date and replaced every time a new block comes out. But when the system crosses ReGenesis event, some of the transactions may fail because of that

1 Like

Writing out some concerns with this approach that I mentioned in the discord chat:

Partial statelessness doesn’t actually give reasonable bounds on active state size unless we implement the same witness-bounding changes needed to enable full statelessness

Currently, the largest witness size that a block can have is if that block accesses the code of as many accounts as possible using code: (3500 witness bytes + 24000 code bytes) * (12500000 / 800) ~= 410 MB. If the attacker provides contract addresses as part of the transaction, this becomes a little bit less powerful (27500 * 12500000 / 1120 ~= 292 MB), but this then allows the attack to be performed using arbitrary already-existing contracts, removing the attacker’s setup costs.

I have published the above calculation many times, always in the context of showing why enabling statelessness requires radical gas cost changes, binary trees and code merklization. But the calculation is also relevant to computing upper bounds on the active state: if one block can add 292 MB to the active state, then 60 blocks can add 17.1 GB, and now we’re already above the size of many people’s RAM (and this doesn’t even include Merkle branches!).

Hence, assuming status quo gas costs, we can’t guarantee that active state will be in RAM unless we reset the active state many times a day (and it has to be a guarantee, because an attacker could first overfill the active state to above 16 GB and then keep attacking [in fact, the exact same attack] to cause lots of disk reads).

Now, let’s assume my favored bag of radical gas cost changes: 2000 gas SLOAD, 2400 gas calls (except self-calls and precompiles), replacing hexary trees with binary, and adding code Merklization, plus adding a charge per chunk of code accessed (say, 1000 gas per chunk). Witness size is now bounded above by 3 gas per byte (with the exception of Merkle tree attacks):

  • SLOAD: 2000 gas / 600 byte witness ~= 3.33 gas per byte
  • EXT* or CALL: 2500 gas / 800 byte witness ~= 3.12 gas per byte
  • Code accesses: 1000 gas / 320 byte witness ~= 3.12 gas per byte

Hence, total witness size is at most 4 MB for a 12.5m gas block. Now, let us re-run the numbers. It now takes ~4000 blocks to get up to 16 GB, meaning that even in a worst case attack scenario, it takes almost a day to get above RAM size; this seems reasonable, especially if the renewing period is variable, so ~12 hours is just a minimum and the average would be much longer.

But what this exercise tells us is that for both full statelessness and partial-statelessness (regenesis or otherwise), the witness size bounding triad (gas cost changes, binary tree, code merklization) is absolutely essential. So this is not an argument against regenesis, but it is an argument that we should continue and even further prioritize going full steam ahead on the triad.

(Note also that the triad, including the 4 MB magic number, is future-proof in an important way: witness compression is looking not too far off in the future, with Starkware recently announcing 10000 hashes per second on consumer desktop hardware using their proposed arithmetic hash function. Roughly, a 4 MB witness contains 4M/32 = 125000 hashes, so this witness would take ~12 seconds to generate. Hence, a single consumer desktop suffices to generate witnesses for all blocks in real time even in the worst case, and those proofs would be broadcasted to help clients that don’t want to download 600 kB average case 4 MB worst case per 13 seconds)

Challenges of handling transactions to inactive accounts

Suppose that there is a transaction which runs code as follows:

for i in range(1000000): z = z * z * z + i + block.number
w = call(sload(z % 1000000))
sstore(1000001, w)

Basically, the transaction does a lot of work, and then based on that work chooses a random address from a list, and calls that address, and stores the output in storage. The question is: what happens when that output may be inactive? There are a few possibilities:

  1. The entire transaction is invalid. This is unacceptable because it is a DoS risk
  2. The entire transaction reverts but still pays gas.
  3. The call reverts.

In case (2) and (3), whether or not an account is in the active state becomes part of the state. This means that we need to change or add new data structures to the state tree, so that someone downloading the state from the state root is able to get this information. This is not especially hard, we could just have an active state trie, and clients could represent it in some compact form, but it is extra complexity that would need to be implemented.

So this makes me wonder: why not take the 80/20 we were going for earlier, where miners are still required to store the full state (active and inactive included) and miners generate the witnesses for everyone else? It seems like the complexity would go down a lot, as miners can generate the witness for any transaction they receive no matter what it does without fear of DoS risk. Is there a reason why going that last 20% is a high priority?

2 Likes

After the ReGenesis hard-fork, transaction sender will need to pay for the size of the witness, so adding 292 Mb to the active state would cost 4.7 billion gas. So this calculation needs to be adjusted for that.

The transaction does not become invalid, but it consumes all the gas spent up to that point, and all its state changes (except for the deducing ETH to pay for gas) are cancelled. Across all of the execution frames. Anything activated by the tx witness stays in the active state.

But there is a DoS risk for miners to generate witnesses for all transactions, unless they can charge for the size of witnesses. We had this problem with Stateless Ethereum and block witnesses, and the solution was either repricing of opcodes, or oil/karma, both of which have downsides. That is why asking tx sender to construct and PAY for the witness simplifies the gas accounting for the witnesses

so adding 292 Mb to the active state would cost 4.7 billion gas

Oh wow, so you’re proposing the full 16 gas per byte? That’s definitely more extreme than my proposal (~3 gas per byte), though it certainly would provide even stronger guarantees (eg. it guarantees a minimum of at least ~3 days before active state reaches 16 GB). It would for example mean that accessing and fully reading a not-yet-read 24 kB contract would require 384k gas, which is much higher than current applications are expecting, though I do see how exempting recently-accessed accounts can mitigate the effect somewhat. I’ll need to think more about the effects of going all the way up to 16 gas/byte for accessing old state… it’s certainly interesting.

It’s also possible to combine the two: target 3 gas per byte for accessing any state, and 16 gas per byte for accessing old state; this way fully stateless clients could enjoy a size witness bound of ~4 MB, and clients that hold on to merkle branches after every regenesis phase could enjoy a stronger witness size bound of ~800 kB.

But there is a DoS risk for miners to generate witnesses for all transactions, unless they can charge for the size of witnesses.

Of course! This is why the witness size bounding triad (gas cost changes of some form, binary tree, code merklization) is essential. This is true in any proposal (I don’t think there’s any disagreement here?)

We had this problem with Stateless Ethereum and block witnesses, and the solution was either repricing of opcodes, or oil/karma, both of which have downsides.

But this proposal is de-facto repricing opcodes! I don’t think there’s actually much concrete difference between saying “CALL now costs 3000 gas” and “if you CALL you have to provide a witness, and to cover that witness you have to pay 3000 gas”; both are increasing the gas cost of a call, the difference mainly matters when looking at how this ends up treating sub-calls.

So I don’t see how any of the problems of any other gas repricing scheme actually get avoided. In particular, I think this proposal breaks meta-transactions, as a meta-transaction could try to access stale state and thereby burn the funds of whoever paid for gas to include it.

Also it seems to me that even if we want to charge for the witness per-byte, charging for the witness and requiring the transaction sender to construct the witness are completely orthogonal. You can have a system where the miner generates the witness and the transaction sender gets charged per-byte, and you can have a system where the transaction sender provides the witness and they pay 3000 gas per call. So I feel like the issues of (i) who should hold the state, and (ii) how we charge more gas for state accesses, should be considered separately; a per-witness-byte strategy for (ii) does not imply “tx sender makes witnesses” for (i) and similarly a higher gas cost for (ii) does not imply we can’t force the tx sender to make witnesses for (i).

1 Like

Though I would agree that these things may be equivalent in the end result they are achieving, they are different in what kind of changes to the live Ethereum need to be applied, and how, and in which order. A big part behind ReGenesis design is not about end-result, but also about the execution strategy. We have end-result focused design in Eth2, in Eth1 the operational aspect of “how to get there” is as important. We might be seeing this from very different perspectives though, since this is where experiences with the current system really matter, and not just the properties of the end result.

I am not sure you can get transaction sender pay for witness that the miner is constructing. This is because the miner’s action always happens AFTER the transaction sender’s action. So you either need to get tx sender to “sign a blank cheque” for the witness they are not even sure will be sufficient, or somehow modify the system to have tx sender’s requiring to sign (and pay) twice, once before the miner’s action, and another time - after the miner’s action - i don’t know how to do that

So you either need to get tx sender to “sign a blank cheque” for the witness they are not even sure will be sufficient

What’s wrong with this? Transaction senders already set gaslimits based on how many operations of what kind their transaction will include, and we know the theoretical limits for the witness size for a call (~8 kB theoretical max, ~4 kB practical max assuming computational bounds on address grinding, ~1 kB practical max if grinding is impossible eg. many contract storage cases).

1 Like

Ok, this comparison implies that there will be a deterministic procedure for generating the transaction witness that the miner must follow. I will think about it, thank you for the idea!

Isn’t the property that there exists exactly one (down to the byte) valid witness for a given set of keys in a given tree one of the desired properties of the binary tree + witness format that we’re going for already? eg. SSZ binary trees definitely have that property; it’s a good property to have because it makes preventing consensus failures much easier. Or is there something big that I’m missing that makes that very hard?

3 Likes

It exists if you specify exactly what is the active state and inactive state at the moment of creating the witness. When I was thinking of tx witness being created by transaction senders, it needed to be reasonably flexible about what snapshot of the active state they used (otherwise the transaction needed to be recreated after every block, which is impractical). If the witnesses for transactions are generated by the miners, then it is possible to establish a deterministic procedure of how tx witness is constructed as transaction’s execution goes on (because in this case, the active state is fixed). So yes, this could work. I have not thought about it from this angle before, so thank you for bringing this up

2 Likes

To add to the general discussion and connect it to the topic of stateless mining… If we achieve stateless mining, then ReGenesis may not be relevant depending on the migration strategy (discussed at the end of this comment).

The general direction I have seen, is we eventually want our execution layer to live on n-shards (EVM, EVM 2.0, Ewasm is still unsure). To continue to support n-shard execution and validator shuffling (along with increasing decentralization by making the burden to mine minimized), stateless mining would be a critical path in the future. To accomplish stateless mining, some semblance of a transaction-based witness approach (or access-list based) and DSA-free (SSA) would be needed.

  1. User submits a tx with the signed witnesses and an access list
  2. Miner still creates a multiproof from the combined witnesses and only needs to include the user signed witness in a block if the miner needs to apply attribution for a missing witness or an access-list, state access mismatch. Alternatively, the user may only need to include an access list (no witnesses) and the miner may request witnesses from a third party or state provider (this takes some of the burden off the user but could have other concerns).
  3. DSA-free approach enforces the validity of step 2) and protects the user from front-running or other issues. Additionally, a transaction can have an expiration period and therefore can still access a changed witness from the previous n-blocks which gets us quite close to DSA functionality and what we have today.

The main discussion I want to introduce here, is whether witness size reduction provided by ReGenesis is crucial enough for the short term and also for the health of full nodes (quicker setup)? If we are going to introduce stateless mining anyways on the roadmap, would this be extra throwaway work and prevent us from exploring state provider networks sooner (for miners or users)? Or will we likely never see a path for the original eth1 shard to migrate to stateless mining?

If we did migrate to DSA-free (or SSA), then it would require some extra complexity. For example, newly deployed contracts would only be DSA-free or there would be an n-block period of time until DSA is no longer supported. This seems tricky and may end up being better to keep the eth shard as DSA and subsequent shards as DSA-free. As a result, ReGenesis would still be beneficial to the original eth shard. Any thoughts on the general direction here?

1 Like