bug: In plonk recursion, if the inner /outer circuit both use BN254 curve, outer circuit prove fail

[readygo67]

Description

In plonk recursion, if the inner /outer circuit both use BN254 curve, outer circuit prove fail, the failure message is listed below. If inner/outer circuit use different curve, prove success.

--- FAIL: TestPlonkRecursion_BN254_BN254 (480.25s)
panic: proving failed: constraint #2636586 is not satisfied: qL⋅xa + qR⋅xb + qO⋅xc + qM⋅(xaxb) + qC != 0 → 220106753963271731408881313523923352097667345336741731604557425392465322162 + 8551063508961278228011123786217924674947456604674697466998842322786933956431 + 0 + 0 + 0 != 0 [recovered]
    panic: proving failed: constraint #2636586 is not satisfied: qL⋅xa + qR⋅xb + qO⋅xc + qM⋅(xaxb) + qC != 0 → 220106753963271731408881313523923352097667345336741731604557425392465322162 + 8551063508961278228011123786217924674947456604674697466998842322786933956431 + 0 + 0 + 0 != 0

Expected Behavior

Prove success

Actual Behavior

Prove failed with constraint is not satisfied.

Steps to Reproduce

1. Rename the "Example_emulated"(std/recursion/plonk/nonactive_doc_test.go) function to "TestPlonkRecursion_BN254_BN254"
2. replace "sw_bw6761" with "sw_bn254"
3. run "TestPlonkRecursion_BN254_BN254"

   
   // InnerCircuitNative is the definition of the inner circuit we want to
   // recursively verify inside an outer circuit. The circuit proves the knowledge
   // of a factorisation of a semiprime.
   type InnerCircuitNative struct {
   P, Q frontend.Variable
   N    frontend.Variable `gnark:",public"`
   }

func (c InnerCircuitNative) Define(api frontend.API) error { // prove that PQ == N res := api.Mul(c.P, c.Q) api.AssertIsEqual(res, c.N) // we must also enforce that P != 1 and Q != 1 api.AssertIsDifferent(c.P, 1) api.AssertIsDifferent(c.Q, 1) return nil }

// computeInnerProof computes the proof for the inner circuit we want to verify // recursively. In this example the PLONK keys are generated on the fly, but // in practice should be genrated once and using MPC. func computeInnerProof(field, outer *big.Int) (constraint.ConstraintSystem, native_plonk.VerifyingKey, witness.Witness, native_plonk.Proof) { innerCcs, err := frontend.Compile(field, scs.NewBuilder, &InnerCircuitNative{}) if err != nil { panic(err) } // NB! UNSAFE! Use MPC. srs, srsLagrange, err := unsafekzg.NewSRS(innerCcs) if err != nil { panic(err) }

innerPK, innerVK, err := native_plonk.Setup(innerCcs, srs, srsLagrange)
if err != nil {
    panic(err)
}

// inner proof
innerAssignment := &InnerCircuitNative{
    P: 3,
    Q: 5,
    N: 15,
}
innerWitness, err := frontend.NewWitness(innerAssignment, field)
if err != nil {
    panic(err)
}
innerProof, err := native_plonk.Prove(innerCcs, innerPK, innerWitness, plonk.GetNativeProverOptions(outer, field))
if err != nil {
    panic(err)
}
innerPubWitness, err := innerWitness.Public()
if err != nil {
    panic(err)
}
err = native_plonk.Verify(innerProof, innerVK, innerPubWitness, plonk.GetNativeVerifierOptions(outer, field))
if err != nil {
    panic(err)
}
return innerCcs, innerVK, innerPubWitness, innerProof

}

// OuterCircuit is the generic outer circuit which can verify PLONK proofs // using field emulation or 2-chains of curves. type OuterCircuit[FR emulated.FieldParams, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GtEl algebra.GtElementT] struct { Proof plonk.Proof[FR, G1El, G2El] VerifyingKey plonk.VerifyingKey[FR, G1El, G2El] gnark:"-" // constant verification key InnerWitness plonk.Witness[FR] gnark:",public" }

func (c *OuterCircuit[FR, G1El, G2El, GtEl]) Define(api frontend.API) error { verifier, err := plonk.NewVerifierFR, G1El, G2El, GtEl if err != nil { return fmt.Errorf("new verifier: %w", err) } err = verifier.AssertProof(c.VerifyingKey, c.Proof, c.InnerWitness) return err }

func TestPlonkRecursion_BN254_BN254(t *testing.T) { // compute the proof which we want to verify recursively innerCcs, innerVK, innerWitness, innerProof := computeInnerProof(ecc.BN254.ScalarField(), ecc.BN254.ScalarField())

// initialize the witness elements
circuitVk, err := plonk.ValueOfVerifyingKey[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](innerVK)
if err != nil {
    panic(err)
}
circuitWitness, err := plonk.ValueOfWitness[sw_bn254.ScalarField](innerWitness)
if err != nil {
    panic(err)
}
circuitProof, err := plonk.ValueOfProof[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](innerProof)
if err != nil {
    panic(err)
}

outerCircuit := &OuterCircuit[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{
    InnerWitness: plonk.PlaceholderWitness[sw_bn254.ScalarField](innerCcs),
    Proof:        plonk.PlaceholderProof[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](innerCcs),
    VerifyingKey: circuitVk,
}
outerAssignment := &OuterCircuit[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{
    InnerWitness: circuitWitness,
    Proof:        circuitProof,
}
// compile the outer circuit
ccs, err := frontend.Compile(ecc.BN254.ScalarField(), scs.NewBuilder, outerCircuit)
if err != nil {
    panic("compile failed: " + err.Error())
}

// NB! UNSAFE! Use MPC.
srs, srsLagrange, err := unsafekzg.NewSRS(ccs)
if err != nil {
    panic(err)
}

// create PLONK setup. NB! UNSAFE
pk, vk, err := native_plonk.Setup(ccs, srs, srsLagrange) // UNSAFE! Use MPC
if err != nil {
    panic("setup failed: " + err.Error())
}

// create prover witness from the assignment
secretWitness, err := frontend.NewWitness(outerAssignment, ecc.BN254.ScalarField())
if err != nil {
    panic("secret witness failed: " + err.Error())
}

// create public witness from the assignment
publicWitness, err := secretWitness.Public()
if err != nil {
    panic("public witness failed: " + err.Error())
}

// construct the PLONK proof of verifying PLONK proof in-circuit
outerProof, err := native_plonk.Prove(ccs, pk, secretWitness)
if err != nil {
    panic("proving failed: " + err.Error())
}

// verify the PLONK proof
err = native_plonk.Verify(outerProof, vk, publicWitness)
if err != nil {
    panic("circuit verification failed: " + err.Error())
}

}

## Context
<!--- How has this bug affected you? What were you trying to accomplish? -->

## Your Environment
<!--- Include as many relevant details about the environment you experienced the bug in -->
* gnark version: master + 5f1643d98071aabc5abbe89573e4c153cd1c6b0e
* gnark-crypto version used: v0.12.2-0.20231221171913-5d5eded6bb15
* go version (e.g. 1.20.6): v.14.1
* Operating System and version:  darwin/arm64

[ivokub]

I think this issue is that we currently do not support non-commitment version of the proofs to be verified in-circuit. It is related to some optimizations we have which use incomplete formulas and leading to unexpected results when one of the points in a multi-scalar multiplication is zero. In case we do not have commitments there is such an input (a polynomial commitment to the commitment wire).

I'll keep it open, rewording.

Thanks for reporting.

[ivokub]

@yelhousni confirmed that it was still about BN254-over-BN254 even when the circuit has a commitment. Will investigate.

[ivokub]

It was a problem with short-hash construction for recursion. It is fixed in https://github.com/Consensys/gnark/pull/1008.

Thanks for reporting.

[readygo67]

great work!