Multi-pairing with provable pairing

[shramee]

Hi guys,

I think millerLoopAndFinalExpResult should do the most optimised circuit for (emulated?) Pairings.
I was wondering why this one doesn't support multiple pairings..?

i.e. Instead of,

func (pr Pairing) IsMillerLoopAndFinalExpOne(P *G1Affine, Q *G2Affine, previous *GTEl) frontend.Variable {

why don't we have P and Q as arrays in in the main pairing func?

func (pr Pairing) IsMillerLoopAndFinalExpOne(P []*G1Affine, Q []*G2Affine, previous *GTEl) frontend.Variable {

@yelhousni @ivokub

[ivokub]

Internally, in case of multi pairing check the algorithm is:

accumulator := Ext12.One()
for _, pairs := inputs {
    millerLoopResult := pairing.MillerLoop(pairs.P, pairs.Q)
    accumulator = Ext12.Mul(millerLoopResult, accumulator)
}
toTargetGroup := finalExp(accumulator)
Ext12.AssertIsOne(toTargetGroup)

the method IsMillerLoopAndFinalExpOne combines the last Miller loop computation, accumulator multiplication and final exp check as a single method. It is very specific to Linea use case and normally not needed elsewhere. There we want to have flexibility in the number of pairs we want to allow in pairing check and then we need to perform miller loops and finalexps separately.

For generic multi pairing check you should use PairingCheck method which is the full algorithm.

[yelhousni]

So there are two things:
1- In linea we need a fixed circuit for ECPair precompile regardless of the number of inputs. We cannot have this if we compute a multi-Miller loop. So the solution we ended up with is to have 2 fixed circuits. MillerLoopAndMul computes the Miller loop of 2 inputs and multiplies it by the previous ML result (1 for the first call). MillerLoopAndFinalExpCheck computes the Miller loop of 2 inputs and checks that the final exp is 1 using Novakovic-Eagen paper (+ including the squarings in the Miller loop).
2- Independently of Linea we can have a PairingCheck method that is similar to MillerLoopAndFinalExpCheck but for slices of points. The problem is you need to have all the (arbitrary number) of inputs in the hint. It's just an Go implementation detail that I haven't figured out yet. If you have an idea you're more that welcome to push a PR! I did a PR for DoublePairingCheck with just 4 inputs since it's the main use of pairings in protocols but it's still uses the old pairing Fpk tower.

[yelhousni]

Here you go for 2-
#1365

[shramee]

Sweet! The PR looks real nice!

[yelhousni]

@shramee I can't put you as a reviewer on the PR apparently but feel free to add your review if you want!

[shramee]

Thanks @yelhousni :D I've added it!