Longsightf reduce constraints and increase rounds

[HarryR]

Closes #21

This removes 2 unnecessary constraints from the LongsightF snark circuit and increases the number of rounds.

Currently the LongsightF322p5 circuit requires 904 constraints, however this could be reduced further to 644 (2 constraints per round) if only cubing is necessary in the round function as the security of a perfect bijection versus .. well, not having a bijection, is undetermined.

[HarryR]

There is a problems with the 322 round variant - the Solidity library is going to need ~10kb of storage for the constants.

I think it's best to avoid using the 322 round variant on-chain, and only use the 12 round variant for computing the Merkle tree.

[daira]

I believe 12-round MiMC is thoroughly broken in sections 3.1 to 3.3 of https://www.cosic.esat.kuleuven.be/publications/article-311.ps (it is called 𝓟𝓤𝓡𝓔 there).

[daira]

If the cost of storage for round constants is an issue, why not generate them programmatically? The library could do that by using one of the hashes that have an Ethereum precompile in counter mode, for example.

[HarryR]

If the cost of storage for round constants is an issue, why not generate them programmatically? The library could do that by using one of the hashes that have an Ethereum precompile in counter mode, for example.

Yes, this is a good solution, where the code becomes something like:

function LongsightF_round( uint256 x_L, uint256 x_R, uint32 i, uint32 n_rounds )
        internal pure returns (uint256 out_x_L, uint256 out_x_R)
    {
        uint256 t;
        uint256 j;
        uint256 C = keccak256(abi.encodePacked("LongsightF-ethsnarks-e5", n_rounds, i));

        t = addmod(x_L, C, curve_order);
        j = mulmod(t, t, curve_order);  // t^2
        j = mulmod(j, j, curve_order);  // t^4
        j = mulmod(j, t, curve_order);  // t^5

        out_x_L = addmod(x_R, j, curve_order);
        out_x_R = x_L;
    }

I will sort that out soon.

believe 12-round MiMC is thoroughly broken in sections 3.1 to 3.3 of

I'm not concerned about key recovery for the Merkle tree nodes above the leaf, as the leafs are public knowledge as are all of the nodes in the Merkle tree. However, I am concerned about collision resistance and malleability.

Finding a collision in the 12 (or even 322) round function and using it as last item in the Merkle tree proof path would permit an unlimited number of forgeries, each with the cost of finding a collision. Essentially a forgery of root = H(x, y) where either x and y can be chosen using the last address bit (left/right selector, for the path) and the other component is derived from evaluating your leaf input and N-1 randomly chosen proof path elements.

From the paper on sponge indifferentiability referenced in the MiMC paper for the MiMChash variant: https://keccak.team/files/SpongeIndifferentiability.pdf - see §2 pg5

Are LongsightF, MiMC and PURE collision resistant without a sponge construction? And if not, does LongsightF when used in the sponge construction introduce the collision resistant property?

Applying the sponge to LongsightF would be something like:

def LongsightF_sponge(x):
    j = 0
    rN, cN = x[0], 0
    for i in range(1, len(x)):
        rN, cN = LongsightF_round(rN, cN, j, 1) # absorb
        rN += x[i]
        j += 1
    for i in range(0, ...):
        rN, cN = LongsightF_round(rN, cN, j, 1) # buffer
        j += 1
    return rN

From §3.1 pg5/6 - where r (bitrate) is 254 or 253, the sponge inputs 2r-bit blocks, request length (n) is the same as r, and the capacity would be 2r ?

Then in §5

By generic attacks we mean here attacks such as those described in [9–11], that do not exploit specific properties of the transformation or permutation used but only properties of the construction.

Which leads me to believe that when the sponge is used where the bitrate (r) is the same size as the field element, and the output is the same size as r, we're back to relying on the collision resistance of the compression function (LongsightF); However, if the input is broken down into bits and fed into the sponge, then the rN variable is used as output, then this is where we start relying upon the properties of the sponge construction for collision resistance.

In that case, where the input is bits, it's only necessary to have a random-looking permutation, e.g. a UOWHF, say something like:

x_L, x_R = (x_R + C_n)^5, x_L

The problem is that using the sponge construction described above we end up with a larger number of constraints for a ~508bit, than for LongsightF with 322 rounds if each bit is absorbed one at a time, but with a larger number of bits being absorbed at a time (say, 2 or 4 for 508 bits, or 11, 22, 23 etc. for 506 bits) then this reduces significantly.

Interesting references:

• http://www.wisdom.weizmann.ac.il/~naor/PAPERS/uowhf_abs.html / http://www.wisdom.weizmann.ac.il/~naor/PAPERS/uowhf.pdf
• https://handouts.secappdev.org/handouts/2010/Bart%20Preneel/hash_functions_lo_res.pdf
• https://eprint.iacr.org/2017/486.pdf - focuses more on N-round commitment protocol

I need to think about this more, because I am very concerned about collision resistance because you can control the last xL or xR parameter of the merkle tree path.