VM: Implement Verkle Trie StateManager

[holgerd77]

Part of #1533 Towards branch: #verkle-stateless-demo

To be able to verify a state root from a "verkle" block we need to be able compute a new (verkle) state root by running all txs from a block in the VM (as we do now) and feeding the state changes to a verkle trie (instead of a merkle trie) which then updates along and at the end (of a block) - hopefully gets to a new state root which matches the verkle state root of the block.

For this to work we need a special VerkleStateManager which feeds account and contract changes to the (a) verkle trie. Base work on this has been done in #1548 where a BaseStateManager has been implemented taking out all non-backend (MPT) related functionality from both the DefaultStateManager and the backend Cache. So it should now be possible to only adopt the remaining functions in the DefaultStateManager to get this working.

To reduce on complexity this work should be done without considering any proof related functionality. So this is mainly to connect an appropriate form of WASM compilation of the rust-verkle library and call into specific functions like insert() or get() from the VerkleStateManager().

If the data backend (leveldb) is a problem on WASM compilation it is also possible to take a very simple backend as a data store (e.g. just some Rust dictionary or something which compiles easily to WASM) as some simplification. This doesn't need to store a lot of data for the demo, just some selected pre-state of a block and then the additions from the block transactions.

And, as a third simplification and a suggestion where/how to start: on a first round we can also ignore the state root itself (if we haven't e.g. a block with a verkle state root and a corresponding state test data setup available) and try to get e.g. mainnet addition of the genesis block and execution of block 1 running, ignoring the state root output (also ok to e.g. comment out the state root checks on a test run). This would already mean to have a lot going with the VM tx execution putting data into the verkle trie, being able to complete on a tx execution and - optimally - finishing up on the whole block. 🙂

Ok, so far as a first TODO write-up on the Verkle Trie demo network.

Ah, and added a new branch verkle-stateless-demo (with appropriate checks), work can be done towards this branch.

//cc @kevaundray

[holgerd77]

Had some back-and-forth exchange with Kev yesterday (thanks a lot for that!) which was super helpful and clarified a lot of things. Kev particularly gave feedback on the write-up from above and pointed out that the above would not be super statelessness-ly (lol 😜), which would mean to not use a Trie backend at all along execution. I will nevertheless keep this write-up from above and not modify or delete or anything, since the above coherently describes the statefull way of doing things and switching to a Verkle Trie, which at some point will also be on the plate.

The good thing is: the structure we have with the BaseStateManager will also work for the stateless way of things. Here is how we need to adopt (thanks again to Kev for the guidance here).

So Kev exposes a js_verify_update() function in his WASM build, here is the signature together with the comments on how to apply:

// The root is the root of the current trie
// The proof is proof of membership of all of the accessed values
// keys_values is a map from the key of the accessed value to a tuple
// the tuple contains the old value and the updated value
//
// This function returns the new root when all of the updated values are applied
#[wasm_bindgen]
pub fn js_verify_update(js_root: Uint8Array, js_proof: Uint8Array, js_key_values: &Map) -> JsValue {

This function takes in the original state root, the proof (from the block) and the old and new state values and gives us the new state root.

In our context this would mean: we start with a blank slate (no state at all) and get all the state values we need from the proof coming with a block (this will be a simple array or something as confirmed by Kev). We will then do the normal block execution. For this we need again a new state manager - let's call it StatelessVerkleStateManager now. This new state manager needs to be initialized with the old (pre-block-execution) state values mentioned above (so which are coming along with the block proof) so that these can be returned to the VM when e.g. StateManager.get() is called (by definition all state values needed should be coming along with the proof. If there is a get() on a non-existing value we should probably throw an "Account not available in proof" error or something). During VM execution we will then track - and collect - all state accesses (and there: the old + the new values).

Then - at the end of this run - we will have all our values together to feed into the js_verify_update() function. We have our old/original state root (kept somewhere I guess from before execution 🙂) which we can feed into js_root, we have the proof from the block which we can directly pass over to js_proof and we have our collected state key values map with the old and new state values which go into js_key_values. This will then give us the new state root which we can compare to the block state root.

Boom. Done. 🥳

There might be some caveats along the way (what happens with additional in-between getStateRoot() calls is one thing I can think of, several updates on the same state account might also be a bit tricky, but solvable).

Apart from these smaller things I guess we have everthing together now with no more major obstacles which need to be solved (this also solves the WASM backend build question). 😀

Really excited on this. 🙏

[acolytec3]

I've done some more exploratory work on this front in this branch in this subdirectory that should be usable as a basis for executing the proof validation.

https://github.com/ethereumjs/ethereumjs-monorepo/tree/verkle-experimentation/verkle

[acolytec3]

Further discussion on Discord confirms that the rust-verkle-wasm package does not yet support verkle proof verification and needs additional work to iron out inconsistencies between the rust and go implementations of the verkle trie/verkle proof concept so my above explorations are about as far as we can go until that is ironed out.

[gabrocheleau]

Repo from Guillaume that contains block example, along with a README detailing how the proof is serialized: https://github.com/gballet/verkle-block-sample

[holgerd77]

Outdated, will close.