State machine incomplete proof

[cheme]

Current state machine proving backend only get proof for state machine backend operation 'storage' and 'child_storage'.
This is problematic in case such as cumulus where we also need the proof of operation such as 'storage_root' or any possible operation done by a runtime.
I believe it is also an issue for light client 'RemoteCall' proof.

So, the idea here would be to extract the proof directly from the 'HashDB' used by the trie backend. That way all trie accessed data will be in proof.

I got a prototype working branch https://github.com/cheme/substrate/tree/full_proof (master...cheme:full_proof) used to assert this approach.
Still needed before making a PR :

• assert we can change the proof in all case and have a single implementation.
• get rid of this mutex (only use for some trait constraint but shouldn't be here

Another word on it:
the approach (getting value at hashdb level) is expecting trie crate to do its query in a optimal way: that is not querying non needed node info.
This is rather relevant for multiple implementation, but we can say that if trie crate queries non needed node, the proof check will fail.
For 'storage_root' operation there is no problem currently : it just does insert and remove operation for all the delta.
For iterator like operation a reexecution need to go into all queried value: it means:

• implementation cannot buff the whole trie.
• implementation cannot do read ahead of a few elements.

So current implementation of iterator_with_prefix is a bit off: it uses triedb iterator seek on the prefix (that is good), but the end iteration condition involve querying a first value that does not start with the prefix.
This is not optimal as a trie with prefix primitive (does not exist) would stop by itself without this last element query.
The impact of this is that 'clear_prefix' currently have an unexpected semantic: if a proof was produced by a optimal implementation, the optimal implementation will have to add some nodes to the proof to be compatible with current runtime extrinsic.

[cheme]

Related paritytech/trie#32

[rphmeier]

When I gathered data for witness sizes in Ethereum a few years ago, the best way to do it was also to gather the proof from the underlying HashDB. I wrote a special wrapper that kept a HashSet of all nodes that are read from the underlying DB. That branch is lost by now, but the general approach should still work.