MIMC collision problem

[lightning-li]

MIMC is based on finite field, Suppose there is a uint256 number a, and the fr.Element modulus is q, then this equation will hold: MIMC(a) = MIMC(a + q). I want to use MIMC function in circuit:

import (
    "bytes"
    "crypto/rand"
    "fmt"
    "github.com/consensys/gnark-crypto/ecc"
    "github.com/consensys/gnark-crypto/hash"
    "github.com/consensys/gnark/frontend"
    "github.com/consensys/gnark/std/hash/mimc"
    "github.com/consensys/gnark/test"
    "math/big"
    "testing"
     mimc2 "github.com/consensys/gnark-crypto/ecc/bn254/fr/mimc"
    "github.com/consensys/gnark/backend"
)

type FooConstraint struct {
    A1 frontend.Variable
    A2 frontend.Variable
    A3 frontend.Variable
    A4 frontend.Variable
}

func CollectDataFromFoo(api frontend.API, foo FooConstraint,
                        hFunc *mimc.MiMC) {
    A1Bits := api.ToBinary(foo.A1, 64)
    A2Bits := api.ToBinary(foo.A2, 64)
    A3Bits := api.ToBinary(foo.A3, 64)
    A4Bits := api.ToBinary(foo.A4, 64)

    ABits := append(A1Bits, A2Bits...)
    ABits = append(ABits, A3Bits...)
    ABits = append(ABits, A4Bits...)
    A := api.FromBinary(ABits...)
    hFunc.Write(A)
}

func SetFooConstraints(a1 uint64, a2 uint64, a3 uint64, a4 uint64) (w FooConstraint) {
    w = FooConstraint{
        A1: a1,
        A2: a2,
        A3: a3,
        A4: a4,
    }
    return w
}
type MimcDemoCircuit struct {
    A            frontend.Variable
    FinalHash    frontend.Variable `gnark:",public"`
}

func (circuit MimcDemoCircuit) Define(api frontend.API) error {
    // mimc
    hFunc, err := mimc.NewMiMC(api)
    if err != nil {
        return err
    }
    CollectDataFromFoo(api, circuit.Foo, &hFunc)
    hash := hFunc.Sum()
    api.AssertIsEqual(hash, circuit.FinalHash)
    return nil
}

func Test4(t *testing.T) {
    var circuit, witness MimcDemoCircuit
    witness.Foo = SetFooConstraints(1, 1, 1, 1)
    hFunc := mimc2.NewMiMC()
    var buf bytes.Buffer

    // 2^192 + 2^128 + 2^64 + 1 + q
    // equal to FooConstraint {A1: 3486998266802970666, A2: 13281191951274694750, A3: 2896914383306846354, A4: 4891460686036598786}
    buf.Write(new(big.Int).SetUint64(3486998266802970666).Bytes())
    buf.Write(new(big.Int).SetUint64(13281191951274694750).Bytes())
    buf.Write(new(big.Int).SetUint64(2896914383306846354).Bytes())
    buf.Write(new(big.Int).SetUint64(4891460686036598786).Bytes())

    hFunc.Write(buf.Bytes())
    hashVal := hFunc.Sum(nil)
    witness.FinalHash = hashVal

    assert := test.NewAssert(t)
    assert.SolvingSucceeded(&circuit, &witness, test.WithBackends(backend.GROTH16), test.WithCurves(ecc.BN254), test.WithCompileOpts(frontend.IgnoreUnconstrainedInputs()))
}

This test passed, it shows that if prover provide verifier FooConstraint {A1: 3486998266802970666, A2: 13281191951274694750, A3: 2896914383306846354, A4: 4891460686036598786}, verifier use mimc calculate this hash, use it as circuit public input, the circuit verify can pass.

What should I do to make sure that verifier is convinced by the fact prover use FooConstraint {A1: 1, A2: 1, A3: 1, A4: 1} not FooConstraint {A1: 3486998266802970666, A2: 13281191951274694750, A3: 2896914383306846354, A4: 4891460686036598786} in circuit? One way I can think of is change CollectDataFromFoo to

func CollectDataFromFoo(api frontend.API, foo FooConstraint,
                        hFunc *mimc.MiMC) {
    A1Bits := api.ToBinary(foo.A1, 64)
    A2Bits := api.ToBinary(foo.A2, 64)
    A3Bits := api.ToBinary(foo.A3, 64)

    ABits := append(A1Bits, A2Bits...)
    ABits = append(ABits, A3Bits...)
    A := api.FromBinary(ABits...)
    hFunc.Write(A)

        A4Bits := api.ToBinary(foo.A4, 64)
        B := api.FromBinary(A4Bits...)
        hFunc.Write(B)
}

And Verifier use the same way to calculate mimc hash. Is this a recommend way? Is there a better way?

[yycen]

In the circuit, you truncate and pack A1..A4 into one element A1(64)||A2(64)||A3(64)||A4(64) why not write 4 elements into hash instead?

[lightning-li]

In the circuit, you truncate and pack A1..A4 into one element A1(64)||A2(64)||A3(64)||A4(64) why not write 4 elements into hash instead?

There are many elements needed to be hashed, I want to reduce the number of constraints in circuit, and the overhead for verifier (L1 smart contract) to generate the same hash

[ThomasPiellard]

Hi, so I think the solution to the issue is to decompose the []byte slice buffer in the "real" (=non snark) version of mimc in base p (so the slice is interpreted as a number a0 + a1*r + a2*r^2 + .. + an*r^n where r is the size of the snark field), and use as blocks the digits ai. The r-basis decomposition ensures there is a one-to-one correspondence between sequences of blocks and byte slices.

Currently the implementation in gnark-crypto does not do that, but rather decomposes the []byte slice as blocks of size 256bits for instance for bn254. It's a security bug as a matter of fact, I raised the corresponding issue in gnark-crypto.