Tree sharding to process updates in parallel

[musalbas]

At the moment, the tree can only safely handle one update at a time. It would be desirable to shard the tree into multiple subtrees and allow parallel updates to the subtrees.

[tac0turtle]

Does this get rid of atomic writes?

Does this have overlap with cosmos/cosmos-sdk#6370

[musalbas]

It shouldn't do if implemented correctly! See https://github.com/google/trillian/blob/v1.4.0/merkle/smt/writer.go#L37 for a sharded SMT implementation (but without the efficiency improvements of the Libra SMT).

[liamsi]

The SDK is about to remove / reduce (?) the multistore because it is not easy to implement this correctly I think. See specifically this comment: cosmos/cosmos-sdk#6370 (comment) (the problem is that the sub-trees are treated somewhat too independently and the abstractions did not make it easy that the writes were actually atomic).

IIUC, the code @musalbas posted is not about sharding into subtrees alá logical subtrees (like in the multistore) but rather about sharding into equal sized shards independent of any logical sub-trees (e.g. accounts, delegations, valsets etc would be logical sub-trees).

Either way, it is probably safe to say that this does not have the highest priority right now?

[musalbas]

It's not high priority, but it would be important for execution environments like Solana that support parallel transaction execution.

[universe2439]

Agree not high priority