bls12_381 aggregate signature verified failed(wait long time but not returned)

[zhengjunhe]

I need to do the bls12_381 aggregate signature verification in my circuit,but it seems enter a dead loop as the unit test didn't finish after long time.The code is as below:

import (
	"fmt"
	bls12381 "github.com/consensys/gnark-crypto/ecc/bls12-381"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/std/algebra/emulated/sw_bls12381"
	"encoding/hex"
	"github.com/consensys/gnark-crypto/ecc"
	bls12381 "github.com/consensys/gnark-crypto/ecc/bls12-381"
	bls12381Fr "github.com/consensys/gnark-crypto/ecc/bls12-381/fr"
	"github.com/consensys/gnark/backend"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/test"
	"math/big"
	"testing"
)

type SyncCmtSigWitness struct {
	AggregatePublicKey [48]byte
	AggregateSignature [96]byte
	Msg                [32]byte
}

// C1 = e(H(m)*g2, Pk) = e(H(m)*g2, sk*g1) = e(g2, g1)^(H(m)*sk)
// C2 = e(sig*g2, g1) = e(sk*H(m)*g2, g1)  = e(g2, g1)^(H(m)*sk)
type BLS12_381Sig struct {
	PubKey  sw_bls12381.G1Affine
	Sig     sw_bls12381.G2Affine
	Hash2G2 sw_bls12381.G2Affine
	//Res   sw_bls12381.GTEl
}

var (
	dst      = []byte("BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_")
	g1GenAff bls12381.G1Affine
)

func init() {
	_, _, g1GenAff, _ = bls12381.Generators()
}

func (bls12_381Sig *BLS12_381Sig) FillWitness(sigWitness *SyncCmtSigWitness) error {
	var pk bls12381.G1Affine
	var sig bls12381.G2Affine
	if err := pk.Unmarshal(sigWitness.AggregatePublicKey[:]); nil != err {
		return err
	}
	if err := sig.Unmarshal(sigWitness.AggregateSignature[:]); nil != err {
		return err
	}
	hash2G2, err := bls12381.HashToG2(sigWitness.Msg[:], dst)
	if err != nil {
		return err
	}

	bls12_381Sig.PubKey = sw_bls12381.NewG1Affine(pk)
	bls12_381Sig.Sig = sw_bls12381.NewG2Affine(sig)
	bls12_381Sig.Hash2G2 = sw_bls12381.NewG2Affine(hash2G2)

	return nil
}

func (circuit *BLS12_381Sig) Define(api frontend.API) error {
	pairing, err := sw_bls12381.NewPairing(api)
	if err != nil {
		return fmt.Errorf("new pairing: %w", err)
	}
	pairing.AssertIsOnG1(&circuit.PubKey)
	pairing.AssertIsOnG2(&circuit.Sig)
	pairing.AssertIsOnG2(&circuit.Hash2G2)

	g1 := sw_bls12381.NewG1Affine(g1GenAff)

	// C1 = e(H(m)*g2, Pk) = e(H(m)*g2, sk*g1) = e(g2, g1)^(H(m)*sk)
	// C2 = e(sig*g2, g1) = e(sk*H(m)*g2, g1)  = e(g2, g1)^(H(m)*sk)
	c1, err := pairing.Pair([]*sw_bls12381.G1Affine{&circuit.PubKey}, []*sw_bls12381.G2Affine{&circuit.Hash2G2})
	if err != nil {
		return fmt.Errorf("pair: %w", err)
	}
	c2, err := pairing.Pair([]*sw_bls12381.G1Affine{&g1}, []*sw_bls12381.G2Affine{&circuit.Sig})
	if err != nil {
		return fmt.Errorf("pair: %w", err)
	}
	pairing.AssertIsEqual(c1, c2)
	return nil
}

func TestBLSigVerifyCheck(t *testing.T) {
	aggPubKey, _ := hex.DecodeString("0x95f8d7bda486e1f760ef8df189f44e7e6636a7fde8d5d988fdd6e878443df3a1886edd8304093b6d90751ba28b635f5a")
	sig, _ := hex.DecodeString("0x8faf83c4eb24d200f0075d20ef5cee393d8d04f6ba45838d419e317f12b52df3ebcb3a42b2358c9ab15fa1c5d6c2ed220e1d87d69a9b878a7ee546c5bfd16e36b42b1df5bfbe0361868cdaf76f9b4de026307c1fee4fec8c0baf64f24ee1691c")
	hash, _ := hex.DecodeString("0xc996098d8c719895033e85d27e6660bb0e22b97a5eca159b4d4a10502b238406")

	gnarkAssert := test.NewAssert(t)
	var witness4test BLS12_381Sig
	sigWitness := &SyncCmtSigWitness{
		AggregatePublicKey: [48]byte(aggPubKey),
		AggregateSignature: [96]byte(sig),
		Msg:                [32]byte(hash),
	}
	err := witness4test.FillWitness(sigWitness)
	gnarkAssert.NoError(err)
	gnarkAssert.ProverSucceeded(&BLS12_381Sig{}, &witness4test,
		test.WithCurves(ecc.BN254),
		test.WithCompileOpts(frontend.IgnoreUnconstrainedInputs()),
		test.WithBackends(backend.PLONK))
}

When I do the unit test via TestBLSigVerifyCheck, it didn't finish after long time. It's ok when do the test
replace: gnarkAssert.ProverSucceeded with
err = test.IsSolved(&BLS12_381Sig{}, &witness4test, ecc.BN254.ScalarField())

@ivokub, Coud you pls take a look at my problem?
Thanks in advance.

[yelhousni]

Maybe the number of SCS constraints of your circuit exceed the limit, which is ~67M for a BN254 PLONK. I'm not sure but the two Pair are almost 50M SCS. To optimize the constraints number you can instead verify that e(H(m)*g2, Pk)*e(sig*g2, -g1) == 1 using the optimized PairingCheck method, something like:

pairing.PairingCheck([]*sw_bls12381.G1Affine{&g1Neg, &circuit.PubKey}, []*sw_bls12381.G2Affine{&circuit.Sig, &circuit.Hash2G2})

[zhengjunhe]

@yelhousni,I tried the method pairing.PairingCheck.But the proof was't generated still and I did some simple debug.I checked that number of SCS constraints of my new circuit with pairing.PairingCheck is approximate 20M(exact is 21327024) and it's far from the max limit.I found that the proof generation failure now due to srs generation which is done by test.NewKZGSRS in my test suite.Howevet there are other problems in the following process in pairing.PairingCheck,but now the srs generation is really a problem and it make my development blocked.
I also notice that @ivokub mentioned that modular multiplication improvements is coming.But now,Is there any idea to help me generate proof of pairing.PairingCheck, it could help me move my circuit develop forward.

Thanks a lot.

[zhengjunhe]

New update:
I found that the failure of test.NewKZGSRS is caued by OOM，any My pc is 32G memory and 16 cores. I'll upgrade my computer resource to cloud service to re-test it.

[yelhousni]

I don't see the NewKZGSRS in the code you pasted above. Did you try using the NewSRS method of the kzg package from gnark-crypto?

import (
    "crypto/rand"
    "github.com/consensys/gnark-crypto/ecc"
    "github.com/consensys/gnark-crypto/ecc/bls12-381/kzg"
)
// ...
srs, _ := kzg.NewSRS(
    128, 
    rand.Int(rand.Reader, ecc.BLS12_381.ScalarField()),
)

[zhengjunhe]

As you know that srs needs to be created before seting up the pk and vk.As now it's just in my develop and test phase,I use the below code to genereate srs.
import (
"github.com/consensys/gnark/test"
)
srs, err := test.NewKZGSRS(ccs)

You can check the details of it.
BTW，ProverSucceeded also use test.NewKZGSRS(ccs) to setup srs.

[zhengjunhe]

Update:
I succeeded to generate srs via test.NewKZGSRS(ccs) in cloud computer service(64 core and 128G memory),and it took ~24 minutes.The pk file is so big that it's ~16G in size.And the proof and verification was also done successfully locally.I will check it in solidity contract later.
Thanks a lot.
@yelhousni and @ivokub