search

Consensys / gnark

gnark is a fast zk-SNARK library that offers a high-level API to design circuits. The library is open source and developed under the Apache 2.0 license
https://hackmd.io/@gnark
Apache License 2.0
1.44k stars 369 forks source link

Unexpected failure on emulated pairing check #807

Closed hussein-aitlahcen closed 1 year ago

hussein-aitlahcen commented 1 year ago

Hi,

I quickly hit an issue when trying to do many different pairing checks and can reproduce an issue where the addStep called in the miller loop is failing with something that look like a zero point addition:

                       fields_bn254.Ext2.AssertIsEqual
                                        e2.go:292
                                fields_bn254.Ext2.DivUnchecked
                                        e2.go:338
                                sw_bn254.Pairing.addStep
                                        pairing.go:583
                                sw_bn254.Pairing.MillerLoop
                                        pairing.go:353
                                sw_bn254.Pairing.Pair
                                        pairing.go:207

If I patch addStep with a variant similar to AddUnified the error disappear and the pairing check is passing. Is this a corner case we don't handle in gnark yet, i.e. can the miller loop hit zero point when doing the addition?

gbotrel commented 1 year ago

cc @yelhousni

yelhousni commented 1 year ago

cc @yelhousni

It seems I missed this issue too :) Will have a look!

yelhousni commented 1 year ago

What test vector did you use to hit this issue? in the error below addStep is used in the second iteration of the Miller loop to replace doubleAndAddStep(Qacc,-Q) (2Qacc-Q) by addStep(Qacc,Q) (Qacc+Q). At this iteration, Qacc=2Q so edge cases should not happen in the addition 2Q+Q (no need to use addUnifedStep). Maybe you provided a point Q=0?

hussein-aitlahcen commented 1 year ago

I no longer have the regression test (my bad really...). But I know we were on a pretty outdated develop commit prior to https://github.com/Consensys/gnark/pull/603. Maybe #603 solved it (I will see if I hit the issue again without the addStepUnified). I don't think we were having a zero point in Q as the pairing check would have failed in the end? Also I noticed the gnark-crypto pairing algorithm do use an addition that handle the zero case in the miller loop, that's why I went in this direction. I'll let you know anyway, thanks for the help!

yelhousni commented 1 year ago

closing this, but feel free to re-open if you find a regression test on master.