Pairing check failed when verifying multiple BN254 signatures

[matchv]

I wrote a Groth16 circuit to verify multiple BN254 signatures (2 signers, 2 messages) by pairing checks, but it fails, I checked your source code and it looks I'm invoking the methods correctly, can someone examine my code and advise what is wrong? Thanks a million for your help! @ivokub

import (
	"fmt"
	"github.com/consensys/gnark-crypto/ecc"
	bn254_ecc "github.com/consensys/gnark-crypto/ecc/bn254"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
	bn254 "github.com/consensys/gnark/std/algebra/emulated/sw_bn254"
	"log"
)

const (
	SignatureNum = 2
)

// Circuit Boneh-Lynn-Shacham (BLS) signature verification
// e(sig, g2) == e(hm, pk)
// where:
//   - Sig (in G1) the signature
//   - G2 (in G2) the public generator of G2
//   - Hm (in G1) the hashed-to-curve message
//   - Pk (in G2) the public key of the signer
type Circuit struct {
	Sig bn254.G1Affine
	G2  bn254.G2Affine
	Hm  [SignatureNum]bn254.G1Affine
	Pk  [SignatureNum]bn254.G2Affine
}

// Define e(sig,g2) == e(hm,pk)
func (circuit *Circuit) Define(api frontend.API) error {
	pair, _ := bn254.NewPairing(api)
	pl, _ := pair.Pair([]*bn254.G1Affine{&circuit.Sig}, []*bn254.G2Affine{&circuit.G2})

	var hm []*bn254.G1Affine
	for _, v := range circuit.Hm {
		hm = append(hm, &v)
	}

	var pk []*bn254.G2Affine
	for _, v := range circuit.Pk {
		pk = append(pk, &v)
	}

	pr, _ := pair.Pair(hm, pk)
	pair.AssertIsEqual(pl, pr)
	return nil
}

The error message is as below:

21:48:37 INF compiling circuit
21:48:37 INF parsed circuit inputs nbPublic=0 nbSecret=72
21:48:50 INF building constraint builder nbConstraints=3197563
21:55:20 ERR error="constraint #813096 is not satisfied: 1 ⋅ 50216813883093446111026597752582269792282218163144044314624 != 50216813883093446111058858168887955390270697232002773565745" nbConstraints=3197563
2023/11/05 21:55:20 Prove err: constraint #813096 is not satisfied: 1 ⋅ 50216813883093446111026597752582269792282218163144044314624 != 50216813883093446111058858168887955390270697232002773565745
panic: Prove err: constraint #813096 is not satisfied: 1 ⋅ 50216813883093446111026597752582269792282218163144044314624 != 50216813883093446111058858168887955390270697232002773565745

[gbotrel]

cc @yelhousni

[ivokub]

Can you provide full running example (with witness generation?).

Can you instead of:

	for _, v := range circuit.Hm {
		hm = append(hm, &v)
	}

try

	for i := range circuit.Hm {
		hm = append(hm, &circuit.Hm[i])
	}

and similarly for circuit.Pk part? See https://go.dev/blog/loopvar-preview

[yelhousni]

as @ivokub pointed the example does not have the witness.

[matchv]

Thanks @yelhousni The issue is actually an pointer to temporal variable as pointed out by @ivokub and earlier by @LautaroLasorsa via a private channel.

Now I can compile the multisig multi messages circuit of BLS12-381 without any error.

However, BN254 circuit compiles with the following error, I think it's worth to take a deeper look and suggest a fix:

17:58:29 INF compiling circuit
17:58:29 INF parsed circuit inputs nbPublic=0 nbSecret=72
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:29 ERR recomposing constant error="zero length slice input"
17:58:46 INF building constraint builder nbConstraints=3197683
18:01:22 DBG constraint system solver done nbConstraints=3197683 took=2036.489272
18:01:26 DBG prover done backend=groth16 curve=bn254 nbConstraints=3197683 took=3813.232215
18:01:26 DBG verifier done backend=groth16 curve=bn254 took=0.928572

Another thing is that 16 signer 16 messages circuits is already ~13 million gate size with 17 pairing checks, it is worth to explore the recursive proof with Nova or SuperNova type of primitives, there is a reinforced Groth16 for it if I remember correctly? But I guess that's a big directional decision you guys need to make.

[ivokub]

The recomposing constant error="zero length slice input" error is that during pairing computation with field emulation some intermediate values are 0. We have looked into optimising to omit these computations, but these would introduce some exceptional cases for some input parameters. We are instead going for a more generic implementation. But it would make sense to lessen the log severity (from ERR to WARN).

Actually, 13M gates for 17 pairing checks is quite a good result :) We have thought about other approaches (using folding etc.), but we are not sure of the benefits. Most importantly, they would decrease the current composability of the circuits we right now have in gnark.

But we are right now working on recursion topics (see #880) and just integrated GPU acceleration which could be helpful for proof aggregation and acceleration.