Support Variable-size Key Space for Sparse Merkle Trees

[bvrooman]

Problem:

Currently, Sparse Merkle Trees have a predefined key space of 32 bytes, with valid keys lying in the range of $[0, 2^{256})$.

This enables support for generating commitments, i.e. Merkle roots, to data sets with 32 byte keys, such as contract state and balances.

For smaller data sets, using Merkle Trees with a 32 byte key space is not optimal. This is because the relatively small data set size means that most keys in the key space will be empty. Additionally, this configuration still has the same tree height of 256, resulting in (at most) 256 hash operations per update.

Solution:

We can optimize our commitment generation to smaller data sets by supporting smaller key spaces.

The Sparse Merkle Tree and its nodes can be configured to use a variable-size key space, instead of a hardcoded 32 byte key space.

This requires that the hashing function return a value in the defined key-space. In order to support a variable-size key space S, we must be able to define a hashing function that supports returning a value within S. This can be achieved naively by simply truncating the results of a sha256 call to fit inside S.