feat: implement commitment verification in Groth16 in-circuit recursive verifier

[readygo67]

Description

If the inner circuit has non-empty CommitmentInfo, its vk will include CommitmentInfo(bn254/setup.go)

func Setup(r1cs *cs.R1CS, pk *ProvingKey, vk *VerifyingKey) error {
       ... ... 
	// get R1CS nb constraints, wires and public/private inputs
	nbWires := r1cs.NbInternalVariables + r1cs.GetNbPublicVariables() + r1cs.GetNbSecretVariables()

	commitmentInfo := r1cs.CommitmentInfo.(constraint.Groth16Commitments)
	commitmentWires := commitmentInfo.CommitmentIndexes()
	privateCommitted := commitmentInfo.GetPrivateCommitted()
	nbPrivateCommittedWires := internal.NbElements(privateCommitted) 

	// a commitment is itself defined by a hint so the prover considers it private
	// but the verifier will need to inject the value itself so on the groth16
	// level it must be considered public
	nbPublicWires := r1cs.GetNbPublicVariables() + len(commitmentInfo). //COUNT  commitmentInfo in
        .... ...
	vkK := make([]fr.Element, nbPublicWires)
        ... ... 
      	vk.G1.K = g1PointsAff[offset : offset+nbPublicWires]   //commitmentInfo is included into vk.G1.K
	offset += nbPublicWires

While in outer Circuit's solver (bn254/solver.go), the CommitmentInfo is not count in

func newSolver(cs *system, witness fr.Vector, opts ...csolver.Option) (*solver, error) {
	// parse options
	opt, err := csolver.NewConfig(opts...)
	if err != nil {
		return nil, err
	}

	// check witness size
	witnessOffset := 0
	if cs.Type == constraint.SystemR1CS {
		witnessOffset++
	}

	nbWires := len(cs.Public) + len(cs.Secret) + cs.NbInternalVariables. 
	expectedWitnessSize := len(cs.Public) - witnessOffset + len(cs.Secret) //DOES NOT count in the  CommitmentInfo

	if len(witness) != expectedWitnessSize {
		return nil, fmt.Errorf("invalid witness size, got %d, expected %d", len(witness), expectedWitnessSize)
	}

Steps to Reproduce

run TestRecursiveHashCircuit in std/recursion/std directory, it will fail with

"invalid witness size, got 512, expected 504"

package groth16_test

import (
	"crypto/sha256"
	"fmt"
	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/backend/witness"
	"github.com/consensys/gnark/constraint"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
	"github.com/consensys/gnark/std/algebra"
	"github.com/consensys/gnark/std/algebra/emulated/sw_bn254"
	"github.com/consensys/gnark/std/hash/sha2"
	"github.com/consensys/gnark/std/math/emulated"
	"github.com/consensys/gnark/std/math/uints"
	stdgroth16 "github.com/consensys/gnark/std/recursion/groth16"
	"github.com/consensys/gnark/test"
	"math/big"
	"testing"
)

type InnerHashCircuit struct {
	Input  []uints.U8
	Output [32]uints.U8 `gnark:",public"`
}

func (c *InnerHashCircuit) Define(api frontend.API) error {
	h, err := sha2.New(api)
	if err != nil {
		return fmt.Errorf("new sha2: %w", err)
	}
	h.Write(c.Input[:])
	res := h.Sum()
	if len(res) != len(c.Output) {
		return fmt.Errorf("wrong digest size")
	}
	uapi, err := uints.New[uints.U32](api)
	if err != nil {
		return fmt.Errorf("new uints api: %w", err)
	}
	for i := range res {
		uapi.ByteAssertEq(res[i], c.Output[i])
	}
	return nil
}

// OuterCircuit is the generic outer circuit which can verify Groth16 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        stdgroth16.Proof[G1El, G2El]
	VerifyingKey stdgroth16.VerifyingKey[G1El, G2El, GtEl]
	InnerWitness stdgroth16.Witness[FR]
}

func (c *OuterCircuit[FR, G1El, G2El, GtEl]) Define(api frontend.API) error {
	curve, err := algebra.GetCurve[FR, G1El](api)
	if err != nil {
		return fmt.Errorf("new curve: %w", err)
	}
	pairing, err := algebra.GetPairing[G1El, G2El, GtEl](api)
	if err != nil {
		return fmt.Errorf("get pairing: %w", err)
	}
	verifier := stdgroth16.NewVerifier(curve, pairing)
	err = verifier.AssertProof(c.VerifyingKey, c.Proof, c.InnerWitness)
	return err
}

func getInnerCircuit(field *big.Int, input []uints.U8, output [32]uints.U8) (constraint.ConstraintSystem, groth16.VerifyingKey, witness.Witness, groth16.Proof, error) {
	//make the compiler happy
	circuit := InnerHashCircuit{
		Input: make([]uints.U8, len(input)),
	}

	innerCcs, err := frontend.Compile(field, r1cs.NewBuilder, &circuit)
	if err != nil {
		return nil, nil, nil, nil, err
	}

	innerPK, innerVK, err := groth16.Setup(innerCcs)
	if err != nil {
		return nil, nil, nil, nil, err
	}

	// inner proof
	innerAssignment := &InnerHashCircuit{
		Input:  input,
		Output: output,
	}
	innerWitness, err := frontend.NewWitness(innerAssignment, field)
	if err != nil {
		return nil, nil, nil, nil, err
	}
	innerProof, err := groth16.Prove(innerCcs, innerPK, innerWitness)
	if err != nil {
		return nil, nil, nil, nil, err
	}
	innerPubWitness, err := innerWitness.Public()
	if err != nil {
		return nil, nil, nil, nil, err
	}
	err = groth16.Verify(innerProof, innerVK, innerPubWitness)
	if err != nil {
		return nil, nil, nil, nil, err
	}

	return innerCcs, innerVK, innerPubWitness, innerProof, nil
}

func TestRecursiveHashCircuit(t *testing.T) {
	assert := test.NewAssert(t)
	msg := []byte("hello, world")
	input := uints.NewU8Array(msg)
	digest := sha256.Sum256(msg)

	var output [32]uints.U8
	for i := range digest {
		output[i] = uints.NewU8(digest[i])
	}

	innerCcs, innerVK, innerPubWitness, innerProof, err := getInnerCircuit(ecc.BN254.ScalarField(), input, output)
	assert.NoError(err)
	// initialize the witness elements
	circuitVk, err := stdgroth16.ValueOfVerifyingKey[sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl](innerVK)
	assert.NoError(err)
	circuitPubWitness, err := stdgroth16.ValueOfWitness[sw_bn254.ScalarField](innerPubWitness)
	fmt.Printf("nbInnerPubWitness:%v, witness:%v\n", len(circuitPubWitness.Public), circuitPubWitness.Public)

	assert.NoError(err)
	circuitProof, err := stdgroth16.ValueOfProof[sw_bn254.G1Affine, sw_bn254.G2Affine](innerProof)
	assert.NoError(err)

	outerAssignment := &OuterCircuit[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{
		InnerWitness: circuitPubWitness,
		Proof:        circuitProof,
		VerifyingKey: circuitVk,
	}

	// the witness size depends on the number of public variables. We use the
	// compiled inner circuit to deduce the required size for the outer witness
	// using functions [stdgroth16.PlaceholderWitness] and
	// [stdgroth16.PlaceholderVerifyingKey]
	outerCircuit := &OuterCircuit[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{
		InnerWitness: stdgroth16.PlaceholderWitness[sw_bn254.ScalarField](innerCcs),
		VerifyingKey: stdgroth16.PlaceholderVerifyingKey[sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl](innerCcs),
	}

	// compile the outer circuit
	outerCcs, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, outerCircuit)
	// create prover witness from the assignment
	outerWitness, err := frontend.NewWitness(outerAssignment, ecc.BN254.ScalarField())

	assert.NoError(err)
	// create public witness from the assignment
	outerPublicWitness, err := outerWitness.Public()
	assert.NoError(err)

	// create Groth16 setup. NB! UNSAFE
	outerPk, outerVk, err := groth16.Setup(outerCcs) // UNSAFE! Use MPC
	assert.NoError(err)
	
	// construct the groth16 proof of verifying Groth16 proof in-circuit
	outerProof, err := groth16.Prove(outerCcs, outerPk, outerWitness)
	assert.NoError(err)

	// verify the Groth16 proof
	err = groth16.Verify(outerProof, outerVk, outerPublicWitness)
	assert.NoError(err)

}

Your Environment

• gnark version: master + commit 8f954aa
• gnark-crypto version: v0.12.2-0.20231221171913-5d5eded6bb15
• go version (e.g. 1.20.6): v.1.21.4
• Operating System and version: macos 14.1.1

[ivokub]

Yup, it is a more general issue - right now we do not support the commitment inside in-circuit verifier. It is good to have feature, but we haven't had time to implement yet. But the good news is that I have received feedback from a team that they are looking into implementing the feature. Hopefully it would be upstreamed.

[ivokub]

Implemented in #1057