in BLS12377/BW6761 recursive circuit, 1 more public variable in inner circuit will cause extra 2678 constrains in outer circuit, is it reasonable?

[readygo67]

In the following demo circuits

• inner circuit, y = sum(x0,x1...., xn)
• outer circuit, verify the inner proof

I found that if inner circuit X's length increase 1, the outer circuit will increase 2678, is it reasonable?
run TestOuterCircuitConstrainNumber to get the relation.

import (
	"fmt"
	"github.com/consensys/gnark-crypto/ecc"
	native_plonk "github.com/consensys/gnark/backend/plonk"
	"github.com/consensys/gnark/backend/witness"
	"github.com/consensys/gnark/constraint"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/scs"
	"github.com/consensys/gnark/std/algebra"
	"github.com/consensys/gnark/std/algebra/native/sw_bls12377"
	"github.com/consensys/gnark/std/math/emulated"
	"github.com/consensys/gnark/std/recursion/plonk"
	"github.com/consensys/gnark/test"
	"github.com/consensys/gnark/test/unsafekzg"
	"math/big"
	"testing"
)

// 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 {
	// default uses variable name and secret visibility.
	X []frontend.Variable `gnark:",public"`
	Y frontend.Variable   `gnark:",public"`
}

// y = sum(x0, x1, x2, ...)
func (c *InnerCircuitNative) Define(api frontend.API) error {
	sum := frontend.Variable(0)
	for i := 0; i < len(c.X); i++ {
		sum = api.Add(sum, c.X[i])
	}
	api.AssertIsEqual(c.Y, sum)
	return nil
}

func computeInnerProof(field, outer *big.Int, n int) (constraint.ConstraintSystem, native_plonk.VerifyingKey, witness.Witness, native_plonk.Proof) {

	x := []uint64{}
	for j := 1; j <= n; j++ {
		x = append(x, uint64(j))
	}
	circuit := InnerCircuitNative{
		X: make([]frontend.Variable, len(x)),
	}

	xVar := make([]frontend.Variable, len(x))
	y := uint64(0)
	for i := 0; i < len(x); i++ {
		xVar[i] = x[i]
		y += x[i]
	}

	innerAssignment := &InnerCircuitNative{
		X: xVar,
		Y: y,
	}

	innerCcs, err := frontend.Compile(field, scs.NewBuilder, &circuit)
	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

	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
}

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.NewVerifier[FR, G1El, G2El, GtEl](api)
	if err != nil {
		return fmt.Errorf("new verifier: %w", err)
	}
	err = verifier.AssertProof(c.VerifyingKey, c.Proof, c.InnerWitness)
	return err
}

func TestOuterCircuitConstrainNumber(t *testing.T) {
	for i := 2; i <= 25000; i = i + 1000 {
		assert := test.NewAssert(t)
		innerField := ecc.BLS12_377.ScalarField()
		outer1Field := ecc.BW6_761.ScalarField()
		innerCcs, innerVK, _, _ := computeInnerProof(innerField, outer1Field, i)
		// initialize the witness elements
		circuit1Vk, err := plonk.ValueOfVerifyingKey[sw_bls12377.ScalarField, sw_bls12377.G1Affine, sw_bls12377.G2Affine](innerVK)
		assert.NoError(err)

		outer1Circuit := &OuterCircuit[sw_bls12377.ScalarField, sw_bls12377.G1Affine, sw_bls12377.G2Affine, sw_bls12377.GT]{
			InnerWitness: plonk.PlaceholderWitness[sw_bls12377.ScalarField](innerCcs),
			Proof:        plonk.PlaceholderProof[sw_bls12377.ScalarField, sw_bls12377.G1Affine, sw_bls12377.G2Affine](innerCcs),
			VerifyingKey: circuit1Vk,
		}

		// compile the outer circuit
		outer1CCS, err := frontend.Compile(outer1Field, scs.NewBuilder, outer1Circuit)
		if err != nil {
			panic("compile failed: " + err.Error())
		}
		fmt.Printf("nbPublicVariables:%v, nbConstraints:%v, publicWitness:%v\n", i, outer1CCS.GetNbConstraints(), outer1CCS.GetNbPublicVariables())
	}
}

=== RUN   TestOuterCircuitConstrainNumber
nbPublicVariables:2, nbConstraints:319533, publicWitness:12
nbPublicVariables:1002, nbConstraints:3242071, publicWitness:4012
nbPublicVariables:2002, nbConstraints:5920260, publicWitness:8012
nbPublicVariables:3002, nbConstraints:8598581, publicWitness:12012
nbPublicVariables:4002, nbConstraints:11276867, publicWitness:16012
nbPublicVariables:5002, nbConstraints:13953759, publicWitness:20012
nbPublicVariables:6002, nbConstraints:16631956, publicWitness:24012
nbPublicVariables:7002, nbConstraints:19310145, publicWitness:28012
nbPublicVariables:8002, nbConstraints:21988502, publicWitness:32012
nbPublicVariables:9002, nbConstraints:24667147, publicWitness:36012
nbPublicVariables:10002, nbConstraints:27344591, publicWitness:40012
nbPublicVariables:11002, nbConstraints:30021768, publicWitness:44012
nbPublicVariables:12002, nbConstraints:32700024, publicWitness:48012
nbPublicVariables:13002, nbConstraints:35378687, publicWitness:52012
nbPublicVariables:14002, nbConstraints:38056346, publicWitness:56012
nbPublicVariables:15002, nbConstraints:40734523, publicWitness:60012
nbPublicVariables:16002, nbConstraints:43412722, publicWitness:64012
nbPublicVariables:17002, nbConstraints:46090694, publicWitness:68012
nbPublicVariables:18002, nbConstraints:48768664, publicWitness:72012
nbPublicVariables:19002, nbConstraints:51446211, publicWitness:76012
nbPublicVariables:20002, nbConstraints:54124345, publicWitness:80012
nbPublicVariables:21002, nbConstraints:56802534, publicWitness:84012
nbPublicVariables:22002, nbConstraints:59480891, publicWitness:88012
nbPublicVariables:23002, nbConstraints:62159504, publicWitness:92012
nbPublicVariables:24002, nbConstraints:64836668, publicWitness:96012
--- PASS: TestOuterCircuitConstrainNumber (562.09s)
PASS

[readygo67]

move this issue to discussion

[ivokub]

There is definitely increase in the number of constraints:

• we have to range check the emulated elements which are provided as public witness to the inner circuit
• there is additional computation for every public input in the inner circuit: https://github.com/Consensys/gnark/blob/master/std/recursion/plonk/verifier.go#L855-L862

In general, it is best to reduce the number of public witness, a method to do this is to provide as a public witness hash of the wanted public witness H = hash(public witness1, ..., public witness_n) and then provide all public witness_1, ..., public_witness_n as a private witness and then assert in circuit that the hash is valid. This keeps the outer circuit constraint count static and increases the inner circuit size for the consistency check.

[readygo67]

Thanks for clear information.