Remove unnecessary constraints from LongsightF R1CS + fix misunderstandings from paper

[HarryR]

As per Daira's comments on https://github.com/HarryR/ethsnarks/pull/12#discussion_r211918756

1. It's possible to reduce the number of constraints, Daira provided an example where exponent is 5 but uses two less constraints.

2. It's not necessary for the exponent to create a bijection when using MiMC in Feistel mode. See §5.3

So, if there's no need for a bijection, then the exponent could be reduced to 3. Which would reduce the number of constraints anyway?

Either way, the number of constraints can be reduced:

# This is using two more constraints than necessary. If I'm reading the API correctly, you can do:

t0 = C[i] + c_xL
r1cs_constraint(t0, t0, round_squares[j])             # t1 = (C[i] + c_xL)^2
r1cs_constraint(round_squares[j], round_squares[j], round_squares[j+1]) # t2 = t1^2 = (C[i] + c_xL)^4
r1cs_constraint(round_squares[j+1], t0, rounds[i] - c_xR)      # rounds[i] - c_xR = t4*(C[i] + c_xL)
                                                                        # i.e. rounds[i] = (C[i] + c_xL)^5 + c_xR
j += 2

Have confirmed this works as expected.

Awesome :D Thanks @daira - I will implement this shortly.

Changes necessary:

• the 3 in the round count calculation is not the exponent, it is cubing. change this back to static 3 rather than the exponent.
• there is no need for the exponent to satisfy gcd(p-1, e) == 1
• correct round count calculation asserts
• create round constants for C++ and Solidity implementation, have LongsightF322p5

This will result in 644 constraints for a full round of LongsightF. And for the merkle tree (r*29) >= 322, so if we use 12 rounds that should work.

Number of rounds for LongsightF:

>>> from py_ecc.bn128 import curve_order
>>> from math import log
>>> log(curve_order, 3) * 2
320.0033959662969
>>> int((log(curve_order, 3) + 1) * 2)
322

---

Another constraint can be removed by reducing the exponent to 4, there the constraints become:

t0 = C[i] + xL
r1cs_constraint(t0, t0, round_squares[i])             # t1 = (C[i] + c_xL)^2
r1cs_constraint(round_squares[i], round_squares[i], rounds[i] - c_xR)      # rounds[i] - c_xR = t1*t1
                                                                        # i.e. rounds[i] = (C[i] + c_xL)^4 + c_xR

or 3:

t0 = C[i] + xL
r1cs_constraint(t0, t0, round_squares[i])             # t1 = (C[i] + c_xL)^2
r1cs_constraint(round_squares[i], t0, rounds[i] - c_xR)      # rounds[i] - c_xR = t1*t1
                                                                        # i.e. rounds[i] = (C[i] + c_xL)^3 + c_xR

TODO for Harry, re-review MiMC paper in detail, analyse JK97 paper.

• https://eprint.iacr.org/2016/492.pdf
• https://link.springer.com/content/pdf/10.1007%2FBFb0052332.pdf

[daira]

Note that the MiMC paper only analyses exponents of the forms 2^t + 1 and 2^t - 1 (in section 5.3), and 4 is not of either of those forms.

[HarryR]

I have left it with an exponent of 5, because it's a bijection, and I think that property is useful, in the sense of 'dark magic serendipity'...