remove simple map usage for multistore roothash/proof creation

[colin-axner]

Summary

The root store hash is constructed from a simple tree of all its child stores. The generation of this hash and proof is quite cumbersome in my opinion. We should remove generic structure names in the generation of this hash/proof with more specific types which are done for only this purpose and thus can have great restriction/optimization (it is unclear if these generic types are reused for other purposes)

Problem Definition

The generation of the root hash does some unnecessary/complicated steps before asking tendermint to generate the root hash and proof.

Our top level commit, has a list of kvstores and the value of each kvstore is a hash of its contents (generated via iavl). We then call this function, converting the list of commit id's (which contains hashes) to a golang map. This step seems completely unnecessary (explained further). Then this is turned into a simple map, and turned back into a sorted list of byte slices. The sorting here is not by the value of the byte slice, but of the kv store keys before generating the byte slice

commit stores -> sorted array kvstore hashes -> turn into golang map -> turn into simple map -> turn into partially sorted array

NOTE: The value is prehashed before included in the root hash. Also note, the value is already a hash of the kvstore, so we have prehash(hash) which is used in constructing the root hash. The simple map implementation seems to indicate this is a potential caching optimization, but that is not the reasoning from a correctness standpoint and would break verification algorithms if removed (without also updating the ics23 spec)!

Also note that the []byte provided in [][]byte is not the hash of the kvstore but the leaf value which is len(key) + key + len(prehash(kvstore.hash)) + prehash(kvstore.hash), see ics23 prepareLeafData

The documentation is incorrect. The tendermint ics23 spec does not prehash the key

Proposal

A new structure can be used, but it should have a specific name like multistoreRoothashConstructor or something like that.

It should, take in a list of store infos (sort by key - maybe add a wrapper for store info or util func), it should then, construct a [][]byte array where each []byte is len(key) + key + len(prehash_value) + prehash(kvstore.hash). Then pass this into merkle.ProofsFromByteSlices

I highly recommend feeling comfortable with how the root hash is constructed before taking on this issue

[alexanderbez]

Prior to digging into this, we should be weary given that we're highly considering consolidating all stores into a single logical store. Wouldn't that make this current UX problem obsolete?

[colin-axner]

Yes it would, thanks for bringing that up. I'd guess in that case, a lot of this referenced code would be deleted

[tac0turtle]

@alexanderbez where does this issue stand with store/v2?

[alexanderbez]

Store v2 keep this logic unchanged (atm): RootStore -> CommitInfo -> maps.

When implementing Commit on the root.Store (which has a single SC tree btw), I did evaluate if/how we can improve & simplify the root hash construction. After looking at the code, I felt very very uncomfortable changing it as I don't completely understand the consequences.

I'm more than happy to simplify the code, but I feel that warrants a design conversation. I'll add this to the store v2 EPIC in any case 👍

@colin-axner would you have time to sync with me about this sometime soon?