In the Near NFT example, why are keys in the account_gives_access UnorderedMap hashed?
https://github.com/near-examples/NFT/blame/master/contracts/rust/src/lib.rs
pub struct NonFungibleTokenBasic {
pub token_to_account: UnorderedMap<TokenId, AccountId>,
pub account_gives_access: UnorderedMap<AccountIdHash, UnorderedSet<AccountIdHash>>,
pub owner_id: AccountId,
}
The UnorderedMap type uses a trie. An attacker could unbalance the trie by
repeatedly pushing keys onto the trie that push the depth of one side of the
trie deep. This would reduce performance of trie lookups on names beneath the
attacker's.
A mitigation to the attock is to store hashes of the keys. The hashes would be equally distributed among possible values. The attacker could still perform the attack, but generating specific hashes is hard, so some protocols say.
Another mitigation to the attack is to use a LookupMap, which uses an AVL
tree, which automatically rebalances its tree.
The attack isn't significantly threatening. The worst the attacker can do is punish a small range of key values, by repeatedly paying the storage costs to push an extremely limited range of key values farther down the trie. It therefore, probably isn't worth paying the cost to hash the keys.
However, for trees that store a large number of keys, hashing keys, or a LookupMap, may still be
worth considering, as an unbalanced trie is very likely to result.
To recap, we reviewed the comparison of cost between:
UnorderedMapLookupMap instead of an UnorderedMapthanks @MikePurvis for explanation.