Add a changes trie about rfcs

[burdges]

Ideally, we'll move accounts off the relay chain eventually, so then overall validators would no longer have special information about accounts changes, only about when parachains made blocks. It's maybe faster to querty parachain nodes to find out when the parachain made blocks.

Instead, you could've each account contain the tuple (my_parent,previous_parent) so that anytime you touch an account you set previous_parent = my_parent and set my_parent to be the block hash of the block upon which you're building. This still works on parachains. I think *_parents could be a block height, not a block hash.

It's also possible to update the account without touching these for specific common events, like rewards, but then instead users track their rewards blocks by tracking the validators they nominate in a similar manor.

[burdges]

Anyways, there are other reasons to have off-chain database maintained by collators but never tracked even by the parachain, or maybe tracked only by collators but never validated:

As an example, we know the current trie does many dumb things, like storing data in internal nodes, radix >2, etc. and stuff like Cosmos' somewhat flat trie is much better. If you've some new storage type without non-membership proofs, then accounts could be stored at random leaves in a flat depth binary merkle tree. We then have collators maintain a seperate non-merklized data structure of which account lives at which index. This could be more efficent than anything used by other chains.

As a similar optimization, collators could track account changes, either like this RFC discusses, or by storing history in this off-chain non-merklized data structure, or by having a seperate merklaized data structure for these (my_parent,previous_parent) entries, but which only collators track, not validators.

In what threat model do we prioritize users locating their account history quickly? It's a liveness concern so yes we could definitely leave this up to collators, but this requires off-chain data structures maintained by collators in parallel to the parablocks. It's does not require relay chain changes, but does require lite client changes.

[gavofyork]

So you'd only be able to query changes on and archive node (since full nodes would prune almost all changes up to finalisation)?

[tomaka]

So you'd only be able to query changes on and archive node (since full nodes would prune almost all changes up to finalisation)?

The changes trie in itself is not very useful if you then can't read the storage, so to me it makes sense that only archive nodes keep the full changes trie.

In #59 I suggest that full nodes should be able to serve the storage of the finalized block minus 16.
In my opinion something similar should be done for the changes trie.

---

After a quick discussion with @andresilva, it might be better to put the changes trie root in the MMR itself as a field of the leaves.