How to aggregate multiple proofs into one proof by recursion? Am I right or completely wrong?

[oliverustc]

I try to aggregate multiple proofs into one by using the recursion package
I read the example code at https://pkg.go.dev/github.com/consensys/[email protected]/std/recursion/groth16
I try to aggregate 8 proof into 1 like a binary tree. This is my code :

type LeafCircuit struct {
	P, Q frontend.Variable
	N    frontend.Variable `gnark:",public"`
}

func (c *LeafCircuit) Define(api frontend.API) error {
	res := api.Mul(c.P, c.Q)
	api.AssertIsEqual(res, c.N)
	api.AssertIsDifferent(c.P, 1)
	api.AssertIsDifferent(c.Q, 1)
	return nil
}

func GenerateLeafProof(num int) {
	curve := ecc.BN254
	field := curve.ScalarField()
	outer := curve.ScalarField()
	leafCCS, _ := frontend.Compile(field, r1cs.NewBuilder, &LeafCircuit{})
	leafPK, leafVK, _ := groth16.Setup(leafCCS)
	WriteCCS(leafCCS, "output/layer_0_ccs")
	WritePK(leafPK, "output/layer_0_pk")
	WriteVK(leafVK, "output/layer_0_vk")
	for i := 0; i < num; i++ {
		p := utils.RandInt(0, 100)
		q := utils.RandInt(0, 100)
		leafAssignment := &LeafCircuit{
			P: p,
			Q: q,
			N: p * q,
		}
		leafWitness, _ := frontend.NewWitness(leafAssignment, field)
		leafProof, _ := groth16.Prove(leafCCS, leafPK, leafWitness, std_groth16.GetNativeProverOptions(outer, field))
		leafPubWitness, _ := leafWitness.Public()
		_ = groth16.Verify(leafProof, leafVK, leafPubWitness, std_groth16.GetNativeVerifierOptions(outer, field))
		WriteProof(leafProof, fmt.Sprintf("output/layer_0_proof_%d", i))
		WriteWitness(leafPubWitness, fmt.Sprintf("output/layer_0_witness_%d", i))
	}
}

type RecursionAggregate[FR emulated.FieldParams, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GtEl algebra.GtElementT] struct {
	LeftProof         std_groth16.Proof[G1El, G2El]
	LeftVerifyingKey  std_groth16.VerifyingKey[G1El, G2El, GtEl]
	LeftWitness       std_groth16.Witness[FR] `gnark:",public"`
	RightProof        std_groth16.Proof[G1El, G2El]
	RightVerifyingKey std_groth16.VerifyingKey[G1El, G2El, GtEl]
	RightWitness      std_groth16.Witness[FR] `gnark:",public"`
}

func (c *RecursionAggregate[FR, G1El, G2El, GtEl]) Define(api frontend.API) error {
	verifier, err := std_groth16.NewVerifier[FR, G1El, G2El, GtEl](api)
	if err != nil {
		return fmt.Errorf("new verifier: %w", err)
	}
	err = verifier.AssertProof(c.LeftVerifyingKey, c.LeftProof, c.LeftWitness)
	if err != nil {
		return err
	}
	err = verifier.AssertProof(c.RightVerifyingKey, c.RightProof, c.RightWitness)
	if err != nil {
		return err
	}
	return nil
}

func RecursionAggregateProof(leftIndex, rightIndex, depth int) {
	curve := ecc.BN254
	field := curve.ScalarField()
	newDepth := depth + 1
	var parentCCS constraint.ConstraintSystem
	var parentPK groth16.ProvingKey
	var parentVK groth16.VerifyingKey
	if !utils.CheckFileExists(fmt.Sprintf("output/layer_%d_vk", newDepth)) {
		logger.Info("parent layer_%d_vk not exists, compile and setup first", newDepth)
		childCCS := ReadCCS(curve, fmt.Sprintf("output/layer_%d_ccs", depth))
		ac := &RecursionAggregate[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{
			LeftWitness:       std_groth16.PlaceholderWitness[sw_bn254.ScalarField](childCCS),
			RightWitness:      std_groth16.PlaceholderWitness[sw_bn254.ScalarField](childCCS),
			LeftVerifyingKey:  std_groth16.PlaceholderVerifyingKey[sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl](childCCS),
			RightVerifyingKey: std_groth16.PlaceholderVerifyingKey[sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl](childCCS),
		}
		parentCCS, _ = frontend.Compile(field, r1cs.NewBuilder, ac)
		WriteCCS(parentCCS, fmt.Sprintf("output/layer_%d_ccs", newDepth))
		parentPK, parentVK, _ = groth16.Setup(parentCCS)
		WritePK(parentPK, fmt.Sprintf("output/layer_%d_pk", newDepth))
		WriteVK(parentVK, fmt.Sprintf("output/layer_%d_vk", newDepth))
	} else {
		parentCCS = ReadCCS(curve, fmt.Sprintf("output/layer_%d_ccs", newDepth))
		parentPK = ReadPK(curve, fmt.Sprintf("output/layer_%d_pk", newDepth))
		parentVK = ReadVK(curve, fmt.Sprintf("output/layer_%d_vk", newDepth))
	}
	childVK := ReadVK(curve, fmt.Sprintf("output/layer_%d_vk", depth))
	leftChildProof := ReadProof(curve, fmt.Sprintf("output/layer_%d_proof_%d", depth, leftIndex))
	rightChildProof := ReadProof(curve, fmt.Sprintf("output/layer_%d_proof_%d", depth, rightIndex))
	leftChildWitness := ReadWitness(curve, fmt.Sprintf("output/layer_%d_witness_%d", depth, leftIndex))
	rightChildWitness := ReadWitness(curve, fmt.Sprintf("output/layer_%d_witness_%d", depth, rightIndex))

	circuitChildVK, _ := std_groth16.ValueOfVerifyingKey[sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl](childVK)
	circuitLeftChildProof, _ := std_groth16.ValueOfProof[sw_bn254.G1Affine, sw_bn254.G2Affine](leftChildProof)
	circuitRightChildProof, _ := std_groth16.ValueOfProof[sw_bn254.G1Affine, sw_bn254.G2Affine](rightChildProof)
	circuitLeftChildWitness, _ := std_groth16.ValueOfWitness[sw_bn254.ScalarField](leftChildWitness)
	circuitRightChildWitness, _ := std_groth16.ValueOfWitness[sw_bn254.ScalarField](rightChildWitness)

	acAssign := &RecursionAggregate[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{
		LeftProof:         circuitLeftChildProof,
		LeftVerifyingKey:  circuitChildVK,
		LeftWitness:       circuitLeftChildWitness,
		RightProof:        circuitRightChildProof,
		RightVerifyingKey: circuitChildVK,
		RightWitness:      circuitRightChildWitness,
	}
	aggregateWitness, _ := frontend.NewWitness(acAssign, field)
	aggregateProof, _ := groth16.Prove(parentCCS, parentPK, aggregateWitness)
	aggregatePubWitness, _ := aggregateWitness.Public()
	_ = groth16.Verify(aggregateProof, parentVK, aggregatePubWitness)
	WriteProof(aggregateProof, fmt.Sprintf("output/layer_%d_proof_%d", newDepth, leftIndex))
	WriteWitness(aggregatePubWitness, fmt.Sprintf("output/layer_%d_witness_%d", newDepth, leftIndex))
}

func RecursionAggregateLeafProofs(indexList []int, depth int) {
	for i := 0; i < len(indexList); i += 2 {
		RecursionAggregateProof(indexList[i], indexList[i+1], depth)
	}
}

func main() {
	args := os.Args[1:]
	switch args[0] {
	case "genleaf":
		GenerateLeafProof(16)
	case "ra1":
		RecursionAggregateLeafProofs([]int{0, 1, 2, 3, 4, 5, 6, 7}, 0)
		RecursionAggregateLeafProofs([]int{0, 2, 4, 6}, 1)
		RecursionAggregateLeafProofs([]int{0, 4}, 2)
	case "ra2":
		RecursionAggregateLeafProofs([]int{8, 9, 10, 11, 12, 13, 14, 15}, 0)
		RecursionAggregateLeafProofs([]int{8, 10, 12, 14}, 1)
		RecursionAggregateLeafProofs([]int{8, 12}, 2)
	}
}

It works fine when aggregate the leaf proofs, when it runs the RecursionAggregateLeafProofs([]int{0, 2, 4, 6}, 1) ，the error is:

16:05:14 ERR parsing circuit error="define circuit: invalid number of commitments, got 0, expected 1"
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x168 pc=0xb1d78f]

goroutine 1 [running]:
main.WriteCCS({0x0, 0x0}, {0xc000b4e408, 0x12})
        /home/s/gnarkabc/examples/08-recursion-aggregate/io.go:24 +0x12f
main.RecursionAggregateProof(0x0, 0x2, 0x1)
        /home/s/gnarkabc/examples/08-recursion-aggregate/tree.go:109 +0x5ad
main.RecursionAggregateLeafProofs({0xc0009a7ee0, 0x4, 0xc0001dbee8?}, 0x1)
        /home/s/gnarkabc/examples/08-recursion-aggregate/tree.go:148 +0x3a
main.main()
        /home/s/gnarkabc/examples/08-recursion-aggregate/main.go:12 +0x13a

Now I am confused, Is it possible that my logic in trying to aggregate multiple proofs like this is completely wrong, and that my understanding of recursion is faulty. Or is it simply that my code is written incorrectly?

the WriteCCS and ReadCCS function is :

func WriteCCS(ccs constraint.ConstraintSystem, filePath string) {
	folderName := filePath[:strings.LastIndex(filePath, "/")]
	utils.EnsureDirExists(folderName)
	file, err := os.Create(filePath)
	if err != nil {
		logger.Error("failed to create file: %s", err.Error())
	}
	defer file.Close()
	size, err := ccs.WriteTo(file)
	if err != nil {
		logger.Error("failed to write ccs to file: %s", err.Error())
	}
	logger.Debug("write ccs to %s, size= %d", filePath, size)
}

func ReadCCS(curve ecc.ID, filePath string) constraint.ConstraintSystem {
	folderName := filePath[:strings.LastIndex(filePath, "/")]
	if !utils.CheckDirExists(folderName) {
		logger.Fatal("directory %s does not exist", folderName)
	}
	file, err := os.Open(filePath)
	if err != nil {
		logger.Fatal("open file failed: %v", err)
	}
	defer file.Close()
	ccs := groth16.NewCS(curve)
	size, err := ccs.ReadFrom(file)
	if err != nil {
		logger.Error("failed to read ccs from file: %s", err.Error())
	}
	logger.Debug("read ccs from %s, size= %d", filePath, size)
	return ccs
}

[ivokub]

In your case, you are recursively verifying different circuits (LeafCircuit and RecursionAggregate). In principle, gnark allows recursively verifying different circuits, but the shape of the circuits needs to be the same - namely the number of public witness and number of commitments used.

In current case, this doesn't hold:

• LeafCircuit - number of public inputs is 1 (LeafCircuit.N) and the number of commitments is 0 (this is a implicit property of the circuit, when complex computation a la non-native arithmetic/lookup tables etc. are used then gnark compiler automatically creates the commitment for efficient Fiat-Shamir compuation)
• RecursionAggregate - number of public inputs is 8 (I'm not fully sure, I didn't compile it and looking at source only) as the non-native input std_groth16.Witness internally works using non-native representation of the witness. And the number of commitments is 1 as the non-native recursive verifier automatically implies usage of commitment due to Fiat-Shamir heuristic.

Now, when you want to recursively either verify LeafCircuit or RecursionAggregate inside RecursionAggregate circuit depending on the depth of the tree, you get the error you're seeing.

In principle, it would be possible to make the circuits to have artificially the same shape by manually enforcing the commitments and using hash of the non-native inputs as public input, but it is somewhat complicated. Instead, if you would like to aggregate large number of proofs, I would rather recommend using different curves which are better compatible with each other. In your case it would mean that the LeafCircuit would be defined BLS12-377 curve and the aggregation circuit over BW6-761. In this case, you are able to aggregate hundreds of circuits. The resulting proof would be over BW6-761, which for example isn't compatible with Ethereum precompiles. But you could additionally verify the BW6-761 proof inside BN254 circuit and post that on Ethereum.

Let me know if the proposed approach would work. Theoretically it would be possible to make your approach also work, but I unfortunately don't have that much spare time to make the working example.

[doubiliu]

In your case, you are recursively verifying different circuits (LeafCircuit and RecursionAggregate). In principle, gnark allows recursively verifying different circuits, but the shape of the circuits needs to be the same - namely the number of public witness and number of commitments used.

In current case, this doesn't hold:

• LeafCircuit - number of public inputs is 1 (LeafCircuit.N) and the number of commitments is 0 (this is a implicit property of the circuit, when complex computation a la non-native arithmetic/lookup tables etc. are used then gnark compiler automatically creates the commitment for efficient Fiat-Shamir compuation)
• RecursionAggregate - number of public inputs is 8 (I'm not fully sure, I didn't compile it and looking at source only) as the non-native input std_groth16.Witness internally works using non-native representation of the witness. And the number of commitments is 1 as the non-native recursive verifier automatically implies usage of commitment due to Fiat-Shamir heuristic.

Now, when you want to recursively either verify LeafCircuit or RecursionAggregate inside RecursionAggregate circuit depending on the depth of the tree, you get the error you're seeing.

In principle, it would be possible to make the circuits to have artificially the same shape by manually enforcing the commitments and using hash of the non-native inputs as public input, but it is somewhat complicated. Instead, if you would like to aggregate large number of proofs, I would rather recommend using different curves which are better compatible with each other. In your case it would mean that the LeafCircuit would be defined BLS12-377 curve and the aggregation circuit over BW6-761. In this case, you are able to aggregate hundreds of circuits. The resulting proof would be over BW6-761, which for example isn't compatible with Ethereum precompiles. But you could additionally verify the BW6-761 proof inside BN254 circuit and post that on Ethereum.

Let me know if the proposed approach would work. Theoretically it would be possible to make your approach also work, but I unfortunately don't have that much spare time to make the working example.

I read the comments above. I would like to ask a question. If I recursively aggregate a proof of the same circuit logic, how can I set the public properties of the outermost data input.

For example

type OuterBatchCircuit[FR emulated.FieldParams, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GtEl algebra.GtElementT] struct {
	Proof        []stdgroth16.Proof[G1El, G2El]
	VerifyingKey []stdgroth16.VerifyingKey[G1El, G2El, GtEl]  pubilic?
	InnerWitness []stdgroth16.Witness[FR]    pubilic?
}

VerifyingKey and InnerWitness need to be public at the same time, right? Because if they are not be public at the same time, false circuit replacement can be used?

If I also want to reduce uploaded data, can I fix the value of VerifyingKey in the outer circuit and use a summary publichash=Hash(InnerWitness1,InnerWitness2) as public input