EIP-5988 - Add Poseidon hash function precompile

Discussion about EIP-5988 - Add Poseidon hash function precompile.

This EIP introduces a new precompiled contract which implements the hash function used in the Poseidon cryptographic hashing algorithm, for the purpose of allowing interoperability between the EVM and ZK / Validity rollups, as well as introducing more flexible cryptographic hash primitives to the EVM.

1 Like

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:

  1. 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.
  2. Generate the values in real time.
  3. 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.

1 Like

Hi! Super important initiative, thanks @abdelhamidbakhta and @vbuterin for leading this.
A few comments, I’ll let David say more (and correct me where I err).

  1. Definitely in support of @vbuterin’s option 2, in our Poseidon we generate the round constants using SHA2. To allow a bit of wiggle room for others, suggest to allow any of SHA2, SHA3, Keccak and Blake. And the input should probably include all the parameters of that version: p (modulus), # full rounds, # partial rounds, etc.
  2. As part of our effort to include the Poseidon builtin in Cairo and StarkNet, we’ve contracted an independent expert evaluation of the security of the MDS matrices we use. David is checking efficiency compared to the MDS matrices @vbuterin mentioned. We’ll try to bring the crypto expert on board to also vet and opine on the various other constructions.
  3. We’ve also contracted an independent team to work on an efficient CPU implementation of (our version of) Poseidon, will try to also loop them in to help write the precompile in a super-efficient way.
    Will update on both 2, 3 once I get the relevant OKs from those teams.

Eli

1 Like

Update from @DavidLevitGurevich : The MDS matrix we use is
3 1 1
1 -1 1
1 1 -2

Multiplying by it requires no multiplications and only 8 additions/subtractions. According to our understanding, a single multiplication (modulo a 256 bit prime) costs ~7.5 additions, i.e., the matrix above will likely be faster to compute than anything which involves more than one multiplication and one addition.

BTW, I don’t have permissions to mention more than 2 handles in a post, because I’m new to the system. Can anyone pls grant me more permissions? @vbuterin @timbeiko (would add a few more names but, y’know, I’m not allowed :slight_smile: )

1 Like

That’s right.
Our plan for the future includes also higher dimension matrices, all of a similar form of small values on the diagonal and 1 in the other places.
The main advantage of these matrices is their CPU time, so I think they should be part of the precompile.
It’s important to mention that the independent expert advised us that these MDS matrices are secure as long as the round constants are not too small (we are fine because we use SHA256 to generate the round constants).

I’d like to address the concerns that @CPerezz CPerezz raised on the EIP page, so will first quote him, then answer:

I do have a couple of concerns with this EIP proposal:

  1. On which field is this going to be implemented? As there’s a lot of BLS and BN curves and you’ll need to have a pre-compile for each of them. Which seems unfeasible and not practical at all.
  2. The security parameters will change depending on the field on which you’re working with and the security of the curve, bit size etc…
  3. You can implement Poseidon with different Arity parameters. So basically there’s an infinite amount of permutations that can be added. And doesn’t make sense that this is enforced by a precompile as many companies or users might find the precompile worthless.

Responses:

  1. Suggest a small list of common fields (up to 5 or so should cover existing use cases), and then presumably new projects will opt for one of those. A different option is that the field be a parameter, but this this is unneeded
  2. Again, I’d go with a small selection of parameters that are either currently used. Notice that Poseidon, as a sponge construction, can be applied to different compression ratios
  3. Right, and we’ll curate a small reasonable number.

Can’t help here, sorry! @jpitts should be able to, though!

1 Like

Hmm, it does feel inelegant to make the Poseidon precompile dependent on other hash functions for round constant generation. It would basically mean that a Poseidon precompile call requires calling those other hash functions, which are expensive in SNARKs, and so it would require the precompile to have a high cost in the EVM, and possibly have a complicated caching mechanic to only charge that cost once.

Do you have any thoughts @elistark @abdelhamidbakhta on the possibility of using some simpler formula to generate round constants (like some bitwise thing as I mentioned)? Are there deep security concerns there that push strongly for round constants being fully “random”?

1 Like

I don’t see the problem here: E.g., in a recursive STARK setting in all but the top (Ethereum) layer we bake the round constants into the program/builtin. That’s already done, so no need to prove SHA2/3 using the STARK. On the top layer, i.e., on Ethereum, it should be part of the pricing of using the precompile: 3 gas * number of invocations of SHA2/3/Keccak (replace 3 by the correct gas cost of those hashes).
Notice that most often you’ll have many invocations of Poseidon in a call to this precompile, so the amortized gas of computing the constants once is negligible. E.g., verifying a STARK takes ~ 2000 hash calls, but the number of round constants is ~ 100 - @DavidLevitGurevich will know the exact number.
I’m not an expert on precompiles, but can’t a precompile generate constants to be stored in local memory and used by all calls to it inside a single transaction?

Why not use parameter set in a contract code? cost should be equivalent to EXTCODECOPY (2600/100 for warm/cold access)
it does require eip4758 (deactivate selfdestruct)