The goal is to replace the current Merkle Patricia state tree (MPT), because the current MPT is *very* unfriendly to stateless clients: a worst-case stateless proof for an Ethereum block is ~300 MB (think: spam reads on 24kB contracts), and even the average case sucks because the tree is width-16. It's also very SNARK-unfriendly.
The alternative we've looked at so far is Verkle trees
vitalik.eth.limo/general/202β¦ , which use elliptic curves and IPA-based proofs; with verkle trees and associated gas cost changes (
eips.ethereum.org/EIPS/eip-4β¦ ) the theoretical worst-case proof size drops to ~32 bytes * depth 6 * 15789 accesses = 3 MB; the average case is a few hundred kB.
The other alternative is binary trees. But raw binary proofs are a little too large (average case ~1 MB, worst case ~12 MB), and so we want to wrap them in a STARK. But the challenge with STARKs historically has been proving time.
Recently,
@StarkWareLtd folks have had a series of breakthroughs proving over 500k hashes/sec on a high-end Macbook (!!), meaning that even in a theoretical worst case, they would be able to generate a STARK for a block stateless witness within one second. But this is based on the Poseidon hash function, which is relatively new and untested, and so many consider it too immature for L1 today.
The more conservative approach would be to use SHA256 (or rather, the SHA256 compression function), which is very safe, but also very complex, and much slower to prove (specifically, ~20-50x slower). But there has been work on improving modern proving systems even further, and it looks like proving "conservative" hash functions might be closer to viable than we thought!
Binius is particularly adaptable to this, because you can do all kinds of binary operations directly without needing lookup arguments, and there have recently been great improvements to its proof size (
irreducible.com/posts/better⦠), but there has been great process with circle STARKs too.
A totally different conservative approach that we started talking about last week, is using lattice-based hash functions, which Ajtai's is one example of. These are arithmetically simple, making them quite prover-friendly, but they also derive their security from lattice hardness assumptions. And it turns out that they are actually more compact than I expected: there's a "conservative" option that's a mere 64 bytes long (compared to 32 bytes for all the other hashes)
alonrosen.net/PAPERS/lattice⦠, and we're starting to explore more aggressive options that are 32 bytes long. These are very prover-friendly, my napkin estimate is that they are only ~2-4x worse than Poseidon.