The main missing piece here seems to be the MDS matrix and the round constants. Since the precompile is intended to be arbitrary-size, we can’t just save the round constants in the precompile as we do with SHA256, RIPEMD160, etc, we have to generate them.
I see a few options:
- Add an extra global execution context variable which stores which state sizes and round counts have been used before, and the MDS and RC values for those state sizes using some standard algorithm. When using a new (state size, round count), generate new values and charge extra gas for this.
- Generate the values in real time.
- Pass the values in as inputs.
Option 1: cache constants in global context variable
(1) is in my view unlikely to pass, because it is a large increase in complexity, and it makes the precompile stateful (not a pure function), which is something that has not been done before.
Option 2: generate constants in real time
(2) is more viable than one might think, because the constants would only need to be calculated once but would be used for calculations ~64 times.
For example, the default MDS matrix used in many implementations is MDS[x][y] = 1/(2+x+y), which only requires N inversions (~= 3N field operations with Montgomery multi-inv), barely the cost of a single round. But this would require some tight coordination between the various Poseidon users, because it’s possible that some users (eg. Goldilocks field users) have very specific MDS values in mind that are well-optimized for their specific use case.
RC values are harder, because there are [width] of them per round. In existing implementations, eg. this one, the RC values are generated with a fairly complicated pseudo random number generator. We would have to agree on an algorithm for generating RC values that is very efficient but also generates good values. Would something like RC[i] = (i**3) ^ (i**5) where i = (round number) * width + index and ^ is binary xor work? No idea, need to ask the cryptanalysis experts.
Option 3: pass constants in as parameter
(3) has the challenge that there are a lot of constants. For the MDS matrix, it would work if we insist that the matrix must be a Toeplitz matrix, so MDS[x][y] = D[x+y] for some length 2n-1 D. For round constants, it would not work, and we would need to find easy real-time-generateable values like in the previous option.
The main benefit of allowing more arbitrary MDS values is that it would be more likely to satisfy the needs of specific teams that have specific algorithms that are highly optimized around particular prime fields. Because the round constant mixing step is relatively simpler, there is less need to optimize it, and so people would be more likely to simply accept whatever round constants we suggest as long as there is reason to believe that they are secure.