search

ava-labs / hypersdk

Opinionated Framework for Building Hyper-Scalable Blockchains on Avalanche
Other
203 stars 112 forks source link

Hashed Trie - Optional Hashed State Wrapper #1274

Open aaronbuchwald opened 3 months ago

aaronbuchwald commented 3 months ago

Implement an optional state wrapper that hashes keys before inserting them into a trie structure to mitigate against trie depth attacks - similar to https://github.com/ethereum/go-ethereum/blob/941ae33d7e0b36afc2f8551884f555d963de7c6b/trie/secure_trie.go#L62

aaronbuchwald commented 3 weeks ago

If a malicious user/contract can write arbitrary keys, they can attempt to cluster inserted keys together to increase the depth of the trie. Hashing the keys provides a best effort to balance the trie and keep the average depth to O(log n).

Developers should consider hashing keys before inserting them into state depending on what workload they allow and to make sure that a malicious user or pathological case will not generate a trie with a much larger than expected depth.