You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Merkleize only hashes physically identical node layouts to the same value #95
So sharing is limited to subtries that were created in the same way, which dramatically limits its applicability because of the non-canonical nature of the heterogeneous node types.
This is actually a really tricky topic. If you recall, Remy's first Merkelizer, which was part of the first serialization module, did an exhaustive Merkelization on the logical trie. It was a disaster. Both for memory consumption and runtime performance.
There are all kinds of degenerate cases. For example, Individual 1-byte path tips ended up in their own nodes... What we really need is a good set of heuristics that are informed by, but not constrained by, the physical representation. The guiding idea being to re-express each subsection of a trie in its most optimal representation, and then Merkelize on those.
Certainly something to strive towards, but it's a somewhat big task. I guess with the clankers' help it's no bigger than many other tasks we've accomplished. But also not something that will be finished in an afternoon.
I already have a solution built on top of merkle-cata, not sure if I want to backport it or wait for merkle-cata to be merged or if I need to do work on merkle-cata.
that solution also involves formal verification of hashing protocol
Activity
luketpeterson commentedon Sep 9, 2026
This is actually a really tricky topic. If you recall, Remy's first Merkelizer, which was part of the first serialization module, did an exhaustive Merkelization on the logical trie. It was a disaster. Both for memory consumption and runtime performance.
There are all kinds of degenerate cases. For example, Individual 1-byte path tips ended up in their own nodes... What we really need is a good set of heuristics that are informed by, but not constrained by, the physical representation. The guiding idea being to re-express each subsection of a trie in its most optimal representation, and then Merkelize on those.
Certainly something to strive towards, but it's a somewhat big task. I guess with the clankers' help it's no bigger than many other tasks we've accomplished. But also not something that will be finished in an afternoon.
adamv-symbolica commentedon Sep 9, 2026
That's not the expectation I'm raising: the boundaries can be physical, but the physical layout should not dictate when they're equivalent. Related https://github.com/adamv-symbolica/PathMap/tree/merkle-cata
imlvts commentedon Sep 15, 2026
I already have a solution built on top of merkle-cata, not sure if I want to backport it or wait for merkle-cata to be merged or if I need to do work on merkle-cata.
that solution also involves formal verification of hashing protocol
Adam-Vandervorst commentedon Sep 15, 2026
Wait for merkle cata to be merged
imlvts commentedon Oct 6, 2026
Depends on #31