Gas savings and specification of Mimc254 implementation

There are two distinct implementations of the MiMC hash function in the Mimc254 contract: _mimc and _mimcForTree. The main difference is that the latter one has hardcoded the exponent to be 7 while the former takes a 32-bit exponent as an argument and uses the _pow32 function for exponentiation. However, _mimc is only used in mimcBn254ForNote and mimcBn254ForRoute, where the exponent is always 7. Using the specialized variant in those functions as well could save gas.

It should also be considered whether the functions in the Mimc254 contract

1. may assume inputs are smaller than P,

2. could be passed inputs bigger than or equal to P, but it should revert if that happens, and

3. should handle inputs bigger than or equal to P by reducing them modulo P.

Option 3 would make the relevant MiMC functions into hash functions where it is easy to obtain second preimages. A hash function is second-preimage resistant if, given a, it is intractible to find a b != a such that hash(a) = hash(b), and with option 3, both a and a+P would yield the same hash. We thus recommend options 1 or 2 as well as documenting which behavior the functions should follow with comments. In the case of option 1, it would be the responsibility of caller functions to ensure only inputs smaller than P are passed.

The mimcBn254ForTree function has a line r = (((r + elem) % P) + h) % P; that would revert due to arithmetic overflow for some large values of elem (this variable is obtained from the arguments passed to the function). If elem can be assumed to be smaller than P at this point, then it would be more gas efficient to replace this line by r = (r + elem + h) % P;, reducing the number of reductions modulo P. This is as P < 2^256 / 3, so the addition of three summands that are smaller than P will not cause an arithmetic wraparound modulo 2^256.

There are also some further unnecessary reductions modulo P. For example, the value of r will already be reduced modulo P after the loops in the functions mimcBn254ForNote, mimcBn254ForTree, and mimcBn254ForRoute. Thus return r % P; could be replaced by return r. Similarly, the return value of _pow32 is already reduced mod P, so the line uint256 h = _pow32(t, _exp) % P; in _mimc could be uint256 h = _pow32(t, _exp);.

For such changes, we recommend adding comments to the code documenting why it is not necessary to reduce modulo P or why additions will not overflow.

In addition, the constant P is defined in the Mimc254 contract and redefined in the MerkleTreeOperator and BaseAssetManager contracts but not used there.

Singularity made the suggested changes in commits and .