Multiple storage roots

[sorpaas]

In blockchains like Ethereum and Shasper, we need additional hashes of child storage root, for example:

• In Ethereum, each account holds a storage root field.
• In Shasper, there're no requirements now, but in the future we're likely having validators stored in a trie, and it would probably need to compute its own storage root hash.

In Substrate, currently it's only possible to fetch the toplevel storage hash, and subsequent storage maps are stored in the toplevel storage, so it's not yet possible to compute the above value using builtin intrinsics.

Below is a possible design I have in mind to add support to this. Basically, it uses a well known key prefix in the top level storage (let's call it sys:maps:) to store all child storage root hashes, and backend would commit multiple changesets of all toplevel and child storage.

• Add Ext::place_child_storage(storage_key: Vec<u8>, key: Vec<u8>, value: Option<Vec<u8>>), Ext::child_storage(storage_key: &[u8], key: &[u8]) -> Option<Vec<u8>> for writing and reading child storage.
• Add Ext::child_storage_root(storage_key: &[u8]) -> H256 for computing the child storage root.
• Add Ext::kill_child_storage(storage_key: &[u8]) for removing a child storage slot completely (it computes the ChangeSet needed to completely remove the child trie).
• Each child storage forms it's own backend transaction changeset. At the end of block execution, child storage changesets are applied first, and all changed child storage root are collected. They're inserted to toplevel storage using prefix :child_storage: before the toplevel storage is committed.
• Writing to toplevel storage keys of prefix :child_storage: is disallowed.

Several alternatives:

• Make toplevel storage solely used to store child storage roots, and the current toplevel storage as child storage with key &[]. However, this breaks existing Substrate deployments.
• For any blockchains that require child storage, instead of supporting it in the backend, treat runtime storage as a trie backend. However, this needs double trie hashing so it might be really slow.

Some unresolved issues:

• By generalizing the trie interface, it should be possible to support other trie formats. However, if some blockchains ever wanted to use multiple storage root formats for different parts of its state, then nothing we have works. Fortunately we don't have such blockchains at this moment.

[gavofyork]

looks good.

if some blockchains ever wanted to use multiple storage root formats for different parts of its state

chatting to @vbuterin i expect shasper to want to do this eventually, so we should probably include the option of parameterising each storage db by some means (not least trie type)

[sorpaas]

Right now multiple trie formats can be supported. However, another issue I'm facing at the moment is that it's not yet possible to support multiple hash formats -- the hash generic is set by hash_db::HashDB<H>, and it's not easy to freely change to other H without rewriting HashDB trait.

I don't think this is a huge issue, though -- most blockchains, even with multiple trie formats, will usually stick to one given hash format (ethereum -- keccak256, shasper -- blake2). This is also the case for UTXO.

Edit: found a way to solve this, described in paritytech/trie#2

[gavofyork]

is this still open @sorpaas ?

[sorpaas]

@gavofyork Yeah it's still open pending #1106.

[sorpaas]

The final task for this is to add a generic parameter to Client/Service that accepts a Trie trait which takes any possible trie implementation that can be plugged onto HashDB and PlainDB. I'll start to work on that soon. Note that this does mean that for the same wasm runtime, plugging onto different configs with different trie impls will give out different results for state transition.

[sorpaas]

Discussed with @gavofyork this morning. I think the conclusion is that a generic trie wouldn't really fit Substrate's philosophy, and we'd rather have fixed hash algorithm for tries we want to support. Our current implementation can already do that. So I think this issue can be closed.