contract: Migrate away from child tries

[athei]

We want to migrate away from child tries and use a prefix trie instead in order to be compatible with smoldot.

Background

Each contract stores the data it creates during its execution in something we call a child trie. It is a separate trie which is linked to the main trie by storing its merkle root there. The metadata of each contract (stored in the main trie) contains the trie_id which is used together with a separate set of host functions to interact with the child trie in question.

We do this in order to confine a contract to its own storage area. However, this is not the only nor most straightforward way of doing this. Instead, we could just use the trie_id as a prefix for all storage accesses made by the contract in question. This way contract data would live inside the main trie as all other data and we don't need this specialized set of host functions.

The reason why we originally used a child trie is because it allows for efficient calculation of the merkle root of said child trie. Something that was needed by a feature of pallet-contracts that was since removed (resurrecting a contract from a tomb stone).

Motivation

Child tries are a rather arcane feature. This can easily be concluded from the fact that they are only used by pallet-contracts and crowdloans (as far as I know). Using arcane features comes with risks. The main one being that it they are less tested. A while ago we encountered a bug in the new trie cache. It worked fine for the main trie but not child tries. Another risk is that alternate client implementations might not implement child tries. This is the reason why we want to migrate: It is the easiest path to be smoldot compatible and gain light client support for dry-runs.

The Plan

I think this should be fairly easy (still assigning medium because it requires a migration). We can keep all the logic of trie_id generation and so on. When storage is accessed is we use trie_id ++ blake_128_concat(key_from_contract) as a key into the main trie. The trie_id is already assumed to be collision free. This should should be equivalent to having a StorageMap per contract. This will allow us to iterate over all storage items under the prefix in case we need to delete a contract.

Open Questions

1. This will need a storage migrations. This migration will touch every storage item of every contract. Even doing it multi block might not be enough. The pallet is blocked during the migration. It could constitute an unacceptable long downtime. Needs more research into the expected downtime and if there are some tricks we can pull to make it more efficient.
2. Is allowing users to store a lot of keys under a fixed prefix bad for performance or even dangerous. Probably not because this is how storage maps work in FRAME and we generally don't limit the amount of storage that can be put into them AFAIK. Still, better double check implications.
3. Is there reason to believe that we might need to calculate the merkle root efficiently in the future? If yes, migrating away might be a mistake. That said, I believe that adding a new much simpler API that does just that without introducing a whole new class of tries would be way easier.

[xlc]

How about refactor pallet contracts in such way that the storages is abstracted and people can choose which implementation to use? So that a new chain could use the main trie and existing chain can still use the old child trie while figuring out the migration path.

[gavofyork]

Child tries and other such cryptographic data structures are only going to become more prevalent with paritytech/polkadot-sdk#245. Indeed, there's a long-term plan to move pallets and also, potentially, all storage maps over to their own child-trie.

Lumping everything into the main storage is definitely not a good plan, long-term.

[tomaka]

What's the problem with lumping everything into the main storage?

For context, I have opened #12461 in the past.
After trying hard (w3f/polkadot-spec#577, w3f/polkadot-spec#540, w3f/polkadot-spec#575), to me the way child tries are implemented at the moment makes absolutely no sense to me and is insanely complex to re-implement (because it's so illogical) unless you reproduce the exact same implementation details of Substrate.

It is clear (by looking at the code but also talking to people) that child tries is an incomplete feature that was abandoned half-way through and has later been hacked together in order to make it work in a clumsy way.

[athei]

Lumping everything into the main storage is definitely not a good plan, long-term.

Yes but I am looking for a short term solution here. We have some users who need light client support. The plan is to migrate to prefix trees now and then migrate again to whatever API comes out of paritytech/polkadot-sdk#245 in the future.

The only other quick solution is to implement child tries in smoldot which doesn't seem viable (see above).

[tomaka]

The only other quick solution is to implement child tries in smoldot which doesn't seem viable (see above).

I can definitely implement support for child tries in smoldot, but it's a big enough item that I don't want to work on it as a side project. I would include it in the treasury proposal that I'll submit in April, to be done in May/June.
I could also review a PR that adds support, but be warned that most of the work isn't really about writing the smoldot code but more about figuring out how Substrate behaves in the many corner cases that exist.

[athei]

Child tries are supported in smoldot now.