Verify BLS multi-signature

[avivyossef29]

Hi,
I'm trying to build a circuit that, given BLS public keys and a message hash, verifies an aggregated signature. However, when I compile the circuit, it seems like I'm getting a trivial circuit with 0 constraints.

Do you have any suggestions on what might be going wrong?

type AggregateSignatureCircuit struct {
    PublicKeys   [n]bls12377.G2Jac `gnark:",public"` // Public Keys
    hashedMessage bls12377.G1Affine   `gnark:",public"` // The message to be verified
    Signature    bls12377.G1Affine   // Aggregated Signature
}

func (c *AggregateSignatureCircuit) Define(api frontend.API) error {

    var aggPublicKey bls12377.G2Jac
    set_to_unit_g2(&aggPublicKey)
    for _ , pk := range c.PublicKeys {
            aggPublicKey.AddAssign(&pk) // Perform elliptic curve point addition
    }
    var aggPublicKeyAffine bls12377.G2Affine
    aggPublicKeyAffine.FromJacobian(&aggPublicKey)

    left, _ := bls12377.Pair([]bls12377.G1Affine{c.Signature}, []bls12377.G2Affine{g2Jac})
    right, _ := bls12377.Pair([]bls12377.G1Affine{c.hashedMessage}, []bls12377.G2Affine{aggPublicKeyAffine})

    result := 0
    if left.Equal(&right){
        result = 1
    }
    api.AssertIsEqual(result, 1)

    return nil
}

func main() {
    // Instantiate the circuit
    var circuit AggregateSignatureCircuit
    p := profile.Start()
    log.Println("Compiling the circuit...")
    // Compile the circuit
    r1cs, err := frontend.Compile(ecc.BLS12_377.ScalarField(), r1cs.NewBuilder, &circuit)
    if err != nil {
        log.Fatal(err)
    }
    log.Println("Circuit compiled successfully!")
    p.Stop()
    fmt.Println(p.NbConstraints())
	fmt.Println(p.Top())

aviv@LT-avivy ~/workspace/gnark_signatures $go run main.go 17:28:05 INF gnark profiling enabled path=gnark.pprof 2024/08/31 17:28:05 Compiling the circuit... 17:28:05 INF compiling circuit 17:28:05 INF parsed circuit inputs nbPublic=0 nbSecret=0 2024/08/31 17:28:05 Result: 1 17:28:05 INF building constraint builder nbConstraints=0 2024/08/31 17:28:05 Circuit compiled successfully! 17:28:05 INF gnark profiling disabled path=gnark.pprof 0 Showing nodes accounting for 0, 0% of 0 total ----------------------------------------------------------+------------- flat flat% sum% cum cum% calls calls% + context

[ivokub]

When defining the circuits, one has to define all of the computations using the api object provided as an argument to Define method. This records the corresponding constraints which are then compiled into the argument what will later be proven.

We have written a set of gadgets which provide already defined sub-circuits one can use in their circuit. As an example on how to perform a pairing check and to compute the corresponding witness, see the Pairing on BN254 example. This example can then be modified to for using with BLS12-377 curve.

[avivyossef29]

Thanks very much for your help. I now understand better which type of element I should use as input for the circuit, and the pairing gadget is indeed what I need. I have two more quotations about it:

1. Is it possible to pass an array of fixed size as an input for the circuit( n is const )?

type AggregateSignatureCircuit struct {
    // Public Inputs
    PublicKeys   [n]sw_bls12381.G2 `gnark:",public"` // Public Keys
    hashedMessage sw_bls12381.G1  `gnark:",public"` // The message to be verified
    Signature    sw_bls12381.G1 `gnark:",public"` // Aggregated Signature
}

2. What is the proper way to aggregate an array of group elements inside the circuit? Is there also a gadget for it? Or a way to sum up 2 group elements?

[ivokub]

1. Yes, you can use an array. gnark should automatically allocate sufficient number of witness elements.
2. We have exposed addition for G1 elements in the algebra.Curve interface: https://pkg.go.dev/github.com/consensys/[email protected]/std/algebra#Curve. For G2 elements, we have the implementation, but it isn't exposed in an interface yet. I think we can possibly make the G2 methods public (scalarmul, add, neg, double), as imo we have them implemented anyway https://github.com/consensys/gnark/blob/v0.10.0/std/algebra/emulated/sw_bls12381/g2.go#L115-L178. Let me know if this would be useful and we can create a tracking issue for that.

[ivokub]

But until we have done that, I can only recommend for now vendoring gnark in your application and then adding public methods a la:

func (g2 G2) Add(P, Q *G2Affine) *G2Affine {
    return g2.add(P, Q)
}