Panic When Deleting Some Nonexistent Keys From Trie (GSR-10)

[danforbes]

Under some circumstances, deleting a key from a trie triggers a slice bounds out of range runtime panic, causing the Gossamer node to crash.

In particular, deleting a nonexistent key kx will raise a panic when the trie contains valid key k_y for which k_x is a prefix i.e. where bytes.HasPrefix(k_y, k_x) holds.

While this cannot be exploited by network messages from unauthenticated nodes, it may be readily possible for the runtime to trigger this crash; in particular via the ext_storage_clear and ext_default_child_storage_clear Host API functions, which may be possible for unprivileged users to execute in some runtimes. Malicious block proposers may also be able to directly exploit this.

Once a block contains such an operation, it becomes impossible for Gossamer nodes to execute the state transition
without crashing — resulting in repeated crashes and possibly a chain split until the issue is patched.

Consider interfacing with the maintainers of the Host Specification and reference implementation — to clarify and explicitly specify whether a compliant runtime should ever call ext_storage_clear and ext_default_child_storage_clear with nonexistent keys and, if so, what should occur.

If, under those circumstances, (*Trie).Delete() should be effectively a no-op, properly ensure that it can handle nonexistent key arguments without panicking.

Solutions could involve:
• Checking that the value length + 1 is within the bounds of the key slice i.e. that length < len(key).
• Handling the specific case where the parent key p.key is longer than the key argument.