Missing information regarding child tries

[tomaka]

I have compiled a list of questions whose answer is unclear to me when it comes to child tries. These answers should IMO somehow be added to the specification.

1) What do ext_default_child_storage_get_version_1, ext_default_child_storage_read_version_1, and ext_default_child_storage_next_key return if the specified child trie doesn't exist? I suppose None but clarification is important, as panicking/erroring could also be a sensible option to me. Same remark for ext_default_child_storage_exists_version_1.

2) What happens if ext_default_child_storage_set_version_1 is called on a child trie that doesn't exist? I suppose that it "creates" it? (the definition of "creates" is ambiguous, see other questions below)

3) What happens if ext_default_child_storage_clear_version_1 is called on a child trie that doesn't exist? Is the call simply ignored?

4) What happens if ext_default_child_storage_clear_prefix is called on a child trie that doesn't exist? Is the call simply ignored?

5) Does ext_default_child_storage_storage_kill destroy the child trie entirely? If yes, this isn't mention in the spec.

6) Assuming that the answer to 5) is yes, is it correct that in the case of ext_default_child_storage_storage_kill_version_2 and ext_default_child_storage_storage_kill_version_3 the child trie is destroyed only if the limit is not reached?

7) Assuming that the answer to 5) is yes, does ext_default_child_storage_storage_kill also automatically erase the :child_storage:default: key in the main trie? In other words, if you call ext_default_child_storage_storage_kill("foo"); ext_storage_get_version_1(":child_storage:default:foo"), does ext_storage_get_version_1 return Some or None?

8) What happens if ext_default_child_storage_root is called on a child trie that doesn't exist? Does it create an empty trie and return an empty trie hash? Or does it instead error/panic?

9) What happens if you call ext_default_child_storage_set_version_1("foo", "bar"), then you don't call ext_default_child_storage_root, and then in the next block you call ext_default_child_storage_get_version_1("foo", "bar")? Does ext_default_child_storage_get_version_1 return Some or None?

10) What happens if you call ext_default_child_storage_root, then ext_default_child_storage_set_version_1("foo", "bar"), then you don't call ext_default_child_storage_root, and then in the next block you call ext_storage_get_version_1(":child_storage:default:foo")? Is the value returned by ext_storage_get_version_1 equal to the one that ext_default_child_storage_root returned?

11) Assuming that child trie "foo" doesn't exist yet, what happens if you call ext_default_child_storage_set_version_1("foo", "bar") then ext_default_child_storage_clear_version_1("foo", "bar"), then you don't call ext_default_child_storage_root, and in the next block you call ext_storage_get_version_1(":child_storage:default:foo")? Does ext_storage_get_version_1 return Some or None??

[tomaka]

To clarify, I'm primarily looking for answers to these questions because I'm implementing child tries in smoldot. Adding the answers to the spec would be a bonus. Having informal answers in an issue is better than no answers at all.

[tomaka]

cc @cheme @arkpar (not sure who to ping)

[cheme]

Thanks for opening the subject.

I may be repeating this point a bit in the reply, but generally I think a way to think about the default/current child trie is that any child trie storage key (the part to use to fetch/store root in the top storage) does exists. So there is not really an removed or non existing child trie, only empty ones (on empty state child_storage_root("foo") is the empty child trie root). For root storage, it implies that the empty child trie root is never written in the parent state, only root that differs from the empty one are written.

This design is certainly related to the fact that child trie where initially added to implement ethereum 2 contract storage (it works this way).

What do ext_default_child_storage_get_version_1, ext_default_child_storage_read_version_1, and ext_default_child_storage_next_key return if the specified child trie doesn't exist? I suppose None but clarification is important, as panicking/erroring could also be a sensible option to me. Same remark for ext_default_child_storage_exists_version_1.

It is None. Panicking, erroring would have been sensible if we didn't consider no root in top trie as an empty child trie. And to check if a child trie is empty, one should probably call get_key([]) and next_key([]) and verify both return None.

What happens if ext_default_child_storage_set_version_1 is called on a child trie that doesn't exist? I suppose that it "creates" it? (the definition of "creates" is ambiguous, see other questions below)

Yes it "creates" it, in the sense that it writes a first value in the trie, changing the root to non empty root and root will be written in the parent storage (effectively adding trie nodes in the top trie).

What happens if ext_default_child_storage_clear_version_1 is called on a child trie that doesn't exist? Is the call simply ignored?

Ignored (no return type to the host function), could use a return boolean to indicate if there was an actual state removal (then we probably want to return false if already removed in the same block) to allow runtime to apply different weights without having to call exists first.

What happens if ext_default_child_storage_clear_prefix is called on a child trie that doesn't exist? Is the call simply ignored?

Simply ignored (cost at storage key access in the top trie (and a change overlay access) to realize this is already an empty trie).

Does ext_default_child_storage_storage_kill destroy the child trie entirely? If yes, this isn't mention in the spec.

Since it emptied the child trie, and an empty child trie hash is not stored in parent state (top trie), it indeed remove the child trie root from the top trie.

Assuming that the answer to 5) is yes, is it correct that in the case of ext_default_child_storage_storage_kill_version_2 and ext_default_child_storage_storage_kill_version_3 the child trie is destroyed only if the limit is not reached?

The child trie hash is removed from the top trie when the child trie is empty. So yes, I think at least one of these host functions returns true when it is.

Assuming that the answer to 5) is yes, does ext_default_child_storage_storage_kill also automatically erase the :child_storage:default: key in the main trie? In other words, if you call ext_default_child_storage_storage_kill("foo"); ext_storage_get_version_1(":child_storage:default:foo"), does ext_storage_get_version_1 return Some or None?

So when the new child trie root is calculated (on call to storage root host function), which is something that is always done at the end of a block to get new state root, its new root is written in parent state or removed if the new root is the empty root (https://github.com/paritytech/substrate/blob/b72c475803947121b3b475eb33ba5fc48f1fe5b6/primitives/state-machine/src/backend.rs#L298). So yes, the rule of thumb is no empty child trie root stored in the top/parent trie (all missing root are considered as being empty root).

What happens if ext_default_child_storage_root is called on a child trie that doesn't exist? Does it create an empty trie and return an empty trie hash? Or does it instead error/panic?

it returns the empty root (thinking of all child trie as existing with an empty root), but do not add anything in parent trie (can remove the hash entry though). (https://github.com/paritytech/substrate/blob/b72c475803947121b3b475eb33ba5fc48f1fe5b6/primitives/state-machine/src/ext.rs#L616)

What happens if you call ext_default_child_storage_set_version_1("foo", "bar"), then you don't call ext_default_child_storage_root, and then in the next block you call ext_default_child_storage_get_version_1("foo", "bar")? Does ext_default_child_storage_get_version_1 return Some or None?

ext_default_child_storage_root is called by ext_storage_root on every touched child trie (something in the child trie overlay change). So it is guaranteed to be call at each blocks. So any change to a child storage are written to state (unless ext_storage_root is not call which does not make sense for a runtime).

So unless the transaction (same host function for transaction as the top trie) was reverted, the change on a previous block is always reflected in the next block.

Actually the host function could be removed if a runtime do not need to access the child trie root and just use child trie as a way to store content (and possibly only access child root from rpc).

What happens if you call ext_default_child_storage_root, then ext_default_child_storage_set_version_1("foo", "bar"), then you don't call ext_default_child_storage_root, and then in the next block you call ext_storage_get_version_1(":child_storage:default:foo")? Is the value returned by ext_storage_get_version_1 equal to the one that ext_default_child_storage_root returned?

So same as previous question, ext_default_child_storage_root is only expose to runtime that need to access the current child root value during a block processing.

Assuming that child trie "foo" doesn't exist yet, what happens if you call ext_default_child_storage_set_version_1("foo", "bar") then ext_default_child_storage_clear_version_1("foo", "bar"), then you don't call ext_default_child_storage_root, and in the next block you call ext_storage_get_version_1(":child_storage:default:foo")? Does ext_storage_get_version_1 return Some or None??

Set then remove add a child trie entry in the change overlay, but since it result in an empty child trie, nothing is written in the top trie.

[tomaka]

Thanks for the answer!

Another question, in reaction to this: is it correct that ext_default_child_storage_clear_prefix(child_trie, []) and ext_default_child_storage_storage_kill(child_trie) do exactly the same thing, then? Or is there a difference in behavior between these two functions?

[cheme]

Yes they clearly are redundant. (did make sense at some point because we did target a kill that is not deleting child entry one by one (or doing it asynchronously), to make the clear free of child trie accesses, but today the implementation is still removing every child trie item one by one as a clear prefix with no limit).

[tomaka]

(unless ext_storage_root is not call which does not make sense for a runtime)

It would still be nice to clarify what happens if ext_storage_root isn't called, for the sake of determinism. If it really doesn't make sense, another solution is to declare that it's illegal for a runtime to not call this function after having modified something.

[cheme]

For most runtime it is frame system finalize that calls it as storage root is part of the resulting header. Can think of a runtime that don't (pvf would need it though).

In this case, when ext storage root is not call directly by the runtime, the client code will call it (in native) to determine the next root and pass the payload of changed db data to store. (db payload is cached when call from runtime so when importing block there is need for this client native call for runtimes using frame system)