What's the correct way to deal with domain fitting?

[zhiqiangxu]

    // generate random data
    // makes sure that each chunk of 64 bits fits in a fr modulus, otherwise there are bugs due to the padding (domain separation)
    // TODO since when using mimc the user should be aware of this fact (otherwise one can easily finds collision), I am not sure we should take care of that in the code
    var buf bytes.Buffer
    for i := 0; i < 10; i++ {
        var leaf fr.Element
        if _, err := leaf.SetRandom(); err != nil {
            t.Fatal(err)
        }
        b := leaf.Bytes()
        buf.Write(b[:])
    }

About the case discussed in the comment, say, if one wants to generate a merkle proof from some arbitrary bytes, but a chunk of them doesn't fit into a field element, what's the correct way to deal with it?

[ThomasPiellard]

Hi @zhiqiangxu , there is an issue related to it, see #319 . The issue is that for mimc a stream of bytes should be interpreted as a number written in basis r where r is the number of elements of the snark field, and each digit in this basis should be encrypted using the mimc permutation function. Currently we do not do this basis r decomposition, but we split the stream of bytes by chunks of 32bytes (for bn254) and encrypt each chunk.

[zhiqiangxu]

@ThomasPiellard You mentioned to decompose the []byte slice buffer in the "real" (=non snark) version of mimc in base p, is there an example how to do it?

I think there's no way to decompose 32bytes one-to-one to a number written in basis r unless |r| is exactly 2^256-1, which is not the case for most(all?) elliptic curves.

[ThomasPiellard]

What I meant was that the buffer stored in the digest object (in gnark-crypto) should be interpreted as a big.Int, call it a, and then a should be decomposed in basis r (= the snark field) so that a=a_0 + .. + a_n r^n. Then during the computation of the checksum, the encrypt function would take the a_i as inputs, instead of raw chunks of 32bytes.

Currently the buffer in the digest object is split in raw chunks of 32 bytes. Since r < 2^256, a collision happens for instance if you try to hash x and x+r such that x+r fits on 32 bytes (because in the encrypt function numbers are reduced modulo r).

[zhiqiangxu]

@ThomasPiellard Decompose is a very common operation to make use of commitment, so I created a PR for this: https://github.com/ConsenSys/gnark/pull/398

[zhiqiangxu]

@ThomasPiellard After a later think it seems there can still be conflict after decompose, because 00 and 000 decompose to the same result, unless we append a 1 to the front.