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
The current storage::HashMap implementation is rather simple.
It is basically a structure spanning a whole chunk of storage cells that indexes into those cells using a given hash function in an open addressing scheme.
This has several problems:
It is attackable since the real hashes are only 32-bit wide.
The hashmap is not aware of which storage cells or the whole chunk are actually in use and thus cannot do important clean-up operations that are required due to storage fees.
Due to the problem stated in 2. the hash map also cannot iterate over its elements.
We need an improved version of the storage::HashMap that fixes all of the above problems. The problems listed as 2. and 3. can easily fixed by introducing an internal storage::Vec that keeps track of all used keys of the hash map. This way the hash map keeps track of its keys and thus also track of its used storage cells since its can easily map from those keys to the actual cells.
The hard part is how we can fix 1 and we have not yet come up with a proper way of doing that. The real source of the problem lies in that our hashes are only 32-bit wide. An attacker can easily compute 32-bit hashes and attack the open addressing based probing of the hash map. Without fixing this the storage::HashMap can only be used in situations where callers cannot control the keys.
Maybe there exist some other probing mechanisms that are more robust against attacks than the currently used quadratic open addressing probing mechanism.
Proposal
structHashMap<K,V>{/// Vector storing the keys of the hash map.keys: storage::Vec<K>,/// The distributed values of the hash map.values: storage::SyncChunk<Entry<V>>,}structEntry<V>{/// Index of the hash maps `keys` array.key_id:u32,/// The actual value.value:V,}
The text was updated successfully, but these errors were encountered:
The current
storage::HashMap
implementation is rather simple.It is basically a structure spanning a whole chunk of storage cells that indexes into those cells using a given hash function in an open addressing scheme.
This has several problems:
We need an improved version of the
storage::HashMap
that fixes all of the above problems. The problems listed as 2. and 3. can easily fixed by introducing an internalstorage::Vec
that keeps track of all used keys of the hash map. This way the hash map keeps track of its keys and thus also track of its used storage cells since its can easily map from those keys to the actual cells.The hard part is how we can fix 1 and we have not yet come up with a proper way of doing that. The real source of the problem lies in that our hashes are only 32-bit wide. An attacker can easily compute 32-bit hashes and attack the open addressing based probing of the hash map. Without fixing this the
storage::HashMap
can only be used in situations where callers cannot control the keys.Maybe there exist some other probing mechanisms that are more robust against attacks than the currently used quadratic open addressing probing mechanism.
Proposal
The text was updated successfully, but these errors were encountered: