Add a function to check if a big int fits in the ZK field

[ed255]

Instead of doing

cryptoUtils.CheckBigIntArrayInField(bigInts, cryptoConstants.Q)

Just use the Q inside a util so that it looks like this:

cryptoUtils.CheckBigIntArrayInFieldFOO(bigInts)

Also, if it's not there, add a function for a single big int

[KimiWu123]

Hi @ed255 ,

I'm using circom/circomlib and golang to build my program. However, I got the error sometimes when I use mimc7.Hash

inputs values not inside Finite Field

I found it's due to CheckBigIntArrayInField as your description in this issue. I checked js and circom in circomlib, here and here. Don't see any similar checking.

Could I mod(constants.fqR.Q) before I hash them? Would it be the same output as circomlib (js or circom). If not, how could I use this to get the same result in circom circuit? Thanks.

[arnaucube]

Hi @KimiWu123 , the circomlib implementation assumes that the inputs are inside the finite field. In this go implementation we decided to check it inside the hash function, to avoid possible errors with inputs bigger than the finite field, that's why we added this CheckBigIntInField & CheckBigIntArrayInField. The current implementation is that the function needs to receive the Q element that defines the Finite Field (cryptoUtils.CheckBigIntArrayInField(bigInts, cryptoConstants.Q)), and what @ed255 is proposing in this issue is that the Q can be implicit in the cryptoUtils module, so to call this function would not require to pass the Q (cryptoUtils.CheckBigIntArrayInFieldFOO(bigInts)). The current implementation requires to pass the Q because this allows flexibility to use the functions in different Finite Fields, but this can be done also in a more abstract way, where first needs to initiate the instance of FiniteField (passing the desired Q), and then all the operations would be using that Q.

This was related to this issue. Now, regarding on what you are facing: In the circomlib implementation of MiMC7 there is no check that the inputs are inside the FiniteField, as this is assumed to be done before. So, if you pass an input over that field, will not give any error, but the output will not be the desired and will end up having collisions. The inputs should be inside the FiniteField, that's why in the Go implementation we added this check. If you apply a mod(Q) in the Go and Js implementations, then the output of the hash should be the same, as the mod forces the value to be inside the Finite Field. But this, depending on what you are building, can end up with collisions and errors in other parts of the program, as different 'inputs' end with same result. To put an example, taking the Finite Field over 21888242871839275222246405745257275088548364400416034343698204186575808495617, let's say that we want to do the MiMC7 one time for each one of the following inputs:

• 7
• 21888242871839275222246405745257275088548364400416034343698204186575808495624 (that is outside the Finite Field)

And to avoid putting an input outside the Finite Field, if we apply the mod(q) to the second value, to get a value inside the Finite Field, this will give the value 7 which is the first one, so if now we perform the hash, this two values will give the same output of the hash. That's why depending on what you are building this may be not a problem, but in general having collisions is not desirable.

Here is a small example that reproduces this in Go code:

package main

import (
    "fmt"
    "math/big"

    "github.com/iden3/go-iden3-crypto/constants"
    "github.com/iden3/go-iden3-crypto/mimc7"
)

func main() {
    // First hash: hashing number 7
    inputA, ok := new(big.Int).SetString("7", 10)
    if !ok {
        panic("error bigint to string")
    }
    bigArray1 := []*big.Int{inputA}

    h1, err := mimc7.Hash(bigArray1, nil)
    if err != nil {
        panic(err)
    }
    fmt.Println(h1)

    // Second hash: hashing number modulus((Q + 7 ), Q)
    inputB, ok := new(big.Int).SetString("21888242871839275222246405745257275088548364400416034343698204186575808495624", 10)
    if !ok {
        panic("error bigint to string")
    }
    // apply the modulus Q to the inputB, will end up giving inputA
    inputBp := new(big.Int).Mod(inputB, constants.Q)
    bigArray2 := []*big.Int{inputBp}

    h2, err := mimc7.Hash(bigArray2, nil)
    if err != nil {
        panic(err)
    }
    fmt.Println(h2)
}

> go run main.go
14919642846701603456380927009613522099009600532414275396430092075730357967797
14919642846701603456380927009613522099009600532414275396430092075730357967797

[KimiWu123]

Hi @arnaucube ,

I got it. Thanks for your detail explanation and sample. From you opinion, what is best solution for this kind of situation, input values are bigger than Finite Field? mod(Q) seems not good enough, how about bit shift? Shifting 3 bits, any big integer must be less than 21888242871839275222246405745257275088548364400416034343698204186575808495624.

In addition, where can I get prerequisite or some information like, **the circomlib implementation assumes that the inputs are inside the finite field**? I'm so frustrated when using circom, like this issue, #29. Thank you!

[arnaucube]

For the first question this will depend on the use case. For example in iden3 protocol we are using all the data that at some point will be hashed, putting it in format that fits inside a Finite Field element, then all the data that we hash with MiMC/Poseidon will not be outside the FiniteField. Depending on the use case having a collision with the hash may not be a problem, but usually it will be, so better if all the hash calls are for data that is inside the FiniteField.

About the second question, I'm not maintaining circom neither circomlib, but if you do a simple function that checks that the actual value is under the Q of the FiniteField, you will ensure that no collision happens when you pass the value to the MiMC hash function.

[KimiWu123]

Got it. Thanks a lot!