Lately, there's been some interest in sparse Merkle trees (SMTs). I know Ethereum uses Patricia tries (PTs), but this thread seems to indicate that working with SMTs would yield similar performance, even better if constructed correctly.
I understand how generally SMTs work (one generates the hash of all possible inputs, and the tree is sparse because you don't actually store all empty keys and slots), but how is it going to work within the context of Ethereum and sharding?
one generates the hash of all possible inputs
Not quite (maybe you just didn't express yourself well). To create a SMT, one needs to generate all possible output of a hash function that will be used, and then each of the outputs becomes a leaf of the SMT. So if we use 256-bit hashing function (e.g. SHA-256), our SMT will contain 2^256 leafs.
All of this and more can be found here: https://github.com/pylls/gosmt (there's also a link to the original paper at the bottom).
SMTs can be used almost anywhere where we used (or planned to use) Merkle Patricia Tries so far. Ethereum's MPTs are quite complex to understand, implement and use, SMTs are way simpler and the efficiency is similar. IMO, it will be used mostly for state trees and Plasma chains.
Hope this helped. :)
