Implement storage trie version 1

[noot]

Task summary

Current storage trie is version 0, we need to upgrade to version 1 which has an updated header format which especially adds inlined hashes nodes.

Trie encoding/hashing functions might need to accept a v1 parameter or some other method for versioning the trie encoding

Discussions:

• https://github.com/paritytech/substrate/discussions/11607

Related Gossamer issues:

• #2374
• #2329 (good information in there!)

Related Gossamer PRs:

• #2369 (good information in there too!)
• #2477 (merge in feature branch later)

Related Rust code:

• Codec
• Node header
• Commit for inner hash in trie crate: https://github.com/paritytech/trie/commit/cbc0283ceb014ef29c5a6c6dbe22a66e8a712c48
• Substrate PR for trie upgrade: https://github.com/paritytech/substrate/pull/9732

Related documentation:

• State storage trie structure spec
• v1 trie diff

Other issues:

• https://github.com/ComposableFi/ibc-go/issues/6

WASM functions to implement:

• ext_storage_root_version_2
• ext_default_child_storage_root_version_2
• ext_trie_blake2_256_root_version_2
• ext_trie_blake2_256_ordered_root_version_2
• ext_trie_keccak_256_root_version_2
• ext_trie_keccak_256_ordered_root_version_2
• ext_trie_blake2_256_verify_proof_version_2
• ext_trie_keccak_256_verify_proof_version_2

Post-v1 things to do:

• https://github.com/ChainSafe/gossamer/pull/2747#discussion_r946246955
• https://github.com/ChainSafe/gossamer/pull/2736/files#r941466934

[blasrodri]

Hi! What's the status of this? Is there anything I can do to help out?

[qdm12]

Hello there, sorry I didn't notice the comment earlier. Status is still in progress (actively being worked on since May 2022 pretty much), it's taking a long time since this change impacts the entire codebase and there is a lot of code we had/have that cannot work with the v1 state trie (due to the higher dependency on disk). For example we need to implement #2838 first (which is also work in progress).

You can help out by letting us know what is the problem you are encountering. We checked 2 weeks ago and all runtimes still use v0 as their state trie (not v1), so my guess is you are using i.e. the proof verification function ext_trie_blake2_256_verify_proof_version_2 with the version argument set to 1 right? Or is it something else?

Thanks!