search

Consensys / gnark

gnark is a fast zk-SNARK library that offers a high-level API to design circuits. The library is open source and developed under the Apache 2.0 license
https://hackmd.io/@gnark
Apache License 2.0
1.43k stars 369 forks source link

bug: cannot recursively create a witness (of inner circuit) in the production engine #1079

Closed weijiguo closed 8 months ago

weijiguo commented 8 months ago

Description

During recursive verification, sometimes we need to use the witness/public input values of the outer circuit to assemble a witness to be verified by the inner circuit. However, this does not work: the outer circuit cannot compile, reporting can't set fr.Element from type expr.Term

Codes below:

package main

import (
    "fmt"

    "github.com/consensys/gnark-crypto/ecc"
    "github.com/consensys/gnark/backend/plonk"
    cs "github.com/consensys/gnark/constraint/bn254"
    "github.com/consensys/gnark/frontend"
    "github.com/consensys/gnark/frontend/cs/scs"
    "github.com/consensys/gnark/std/algebra/emulated/sw_bn254"
    recursive_plonk "github.com/consensys/gnark/std/recursion/plonk"
    "github.com/consensys/gnark/test/unsafekzg"
)

type innerCircuit struct {
    X frontend.Variable
    Y frontend.Variable `gnark:",public"`
}

func (c *innerCircuit) Define(api frontend.API) error {
    api.AssertIsEqual(c.X, c.Y)
    return nil
}

type outerCircuit struct {
    VKey  recursive_plonk.VerifyingKey[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine]
    Proof recursive_plonk.Proof[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine]
    X     frontend.Variable
    Y     frontend.Variable
}

func (c *outerCircuit) Define(api frontend.API) error {
    w := innerCircuit{Y: c.Y}

    // recursively create the witness
    witness, err := frontend.NewWitness(&w, ecc.BN254.ScalarField())
    if err != nil {
        panic(err)
    }

    recursiveWitness, err := recursive_plonk.ValueOfWitness[sw_bn254.ScalarField](witness)
    if err != nil {
        panic(err)
    }

    verifier, err := recursive_plonk.NewVerifier[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl](api)
    if err != nil {
        panic(err)
    }

    return verifier.AssertProof(c.VKey, c.Proof, recursiveWitness)
}

func testBody() {
    inner := innerCircuit{}
    ccsInner, _ := frontend.Compile(ecc.BN254.ScalarField(), scs.NewBuilder, &inner)
    scsInner := ccsInner.(*cs.SparseR1CS)

    srs, srsLagrange, err := unsafekzg.NewSRS(scsInner, unsafekzg.WithFSCache())
    if err != nil {
        panic(err)
    }
    pkInner, vkInner, err := plonk.Setup(ccsInner, srs, srsLagrange)
    if err != nil {
        panic(err)
    }

    wInner := innerCircuit{X: 5, Y: 5}
    witnessInner, err := frontend.NewWitness(&wInner, ecc.BN254.ScalarField())
    if err != nil {
        panic(err)
    }

    proofInner, err := plonk.Prove(ccsInner, pkInner, witnessInner,
        recursive_plonk.GetNativeProverOptions(ecc.BN254.ScalarField(), ecc.BN254.ScalarField()))
    if err != nil {
        panic(err)
    }

    witnessInnerPublic, err := witnessInner.Public()
    if err != nil {
        panic(err)
    }
    err = plonk.Verify(proofInner, vkInner, witnessInnerPublic,
        recursive_plonk.GetNativeVerifierOptions(ecc.BN254.ScalarField(), ecc.BN254.ScalarField()))
    if err != nil {
        panic(err)
    }

    recursiveProof, err := recursive_plonk.ValueOfProof[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](proofInner)
    if err != nil {
        panic(err)
    }

    recursiveVK, err := recursive_plonk.ValueOfVerifyingKey[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](vkInner)
    if err != nil {
        panic(err)
    }

    outer := outerCircuit{
        VKey:  recursive_plonk.PlaceholderVerifyingKey[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](ccsInner),
        Proof: recursive_plonk.PlaceholderProof[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](ccsInner),
    }

    outerW := outerCircuit{
        VKey:  recursiveVK,
        Proof: recursiveProof,
        X:     5,
        Y:     5,
    }

    ccs, err := frontend.Compile(ecc.BN254.ScalarField(), scs.NewBuilder, &outer)
    if err != nil {
        panic(err)
    }
    pk, vk, err := plonk.Setup(ccs, srs, srsLagrange)

    fmt.Println("proving ...")
    outerWitess, err := frontend.NewWitness(&outerW, ecc.BN254.ScalarField())
    proof, err := plonk.Prove(ccs, pk, outerWitess,
        recursive_plonk.GetNativeProverOptions(ecc.BN254.ScalarField(), ecc.BN254.ScalarField()))
    if err != nil {
        panic(err)
    }

    fmt.Println("verifying ...")
    pubOuterWitness, err := outerWitess.Public()
    if err != nil {
        panic(err)
    }
    err = plonk.Verify(proof, vk, pubOuterWitness,
        recursive_plonk.GetNativeVerifierOptions(ecc.BN254.ScalarField(), ecc.BN254.ScalarField()))
    if err != nil {
        panic(err)
    }
}

func main() {
    testBody()
}

Expected Behavior

That running the test should pass the outer circuit proving and verification.

Actual Behavior

21:23:17 INF compiling circuit
21:23:17 INF parsed circuit inputs nbPublic=1 nbSecret=1
21:23:17 INF building constraint builder nbConstraints=1
21:23:17 WRN using kzg srs cache cacheDir=/Users/weiji/.gnark/kzg
21:23:17 DBG fetching SRS from mem cache curve=bn254 key=kzgsrs-bn254-5 package=kzgsrs size=5
21:23:17 DBG SRS not found in mem cache curve=bn254 package=kzgsrs size=5
21:23:17 DBG fetching SRS from fs cache cacheDir=/Users/weiji/.gnark/kzg curve=bn254 key=kzgsrs-bn254-5 package=kzgsrs size=5
21:23:17 DBG SRS found in fs cache curve=bn254 key=kzgsrs-bn254-5 package=kzgsrs size=5
21:23:17 DBG constraint system solver done nbConstraints=1 took=0.051
21:23:17 DBG prover done backend=plonk curve=bn254 nbConstraints=1 took=3.602667
21:23:17 DBG verifier done backend=plonk curve=bn254 took=2.45575
21:23:17 INF compiling circuit
ignoring uninitialized slice: VKey_CommitmentConstraintIndexes []frontend.Variable
21:23:17 INF parsed circuit inputs nbPublic=0 nbSecret=4447
ignoring uninitialized slice: VKey_CommitmentConstraintIndexes []frontend.Variable
ignoring uninitialized slice: VKey_CommitmentConstraintIndexes []frontend.Variable
21:23:17 ERR parsing circuit error="can't set fr.Element from type expr.Term\nfrontend.parseCircuit.func2\n\tcompile.go:118\nmain.(*outerCircuit).Define\n\trc.go:39\n"
panic: parse circuit: can't set fr.Element from type expr.Term
frontend.parseCircuit.func2
    compile.go:118
main.(*outerCircuit).Define
    rc.go:39

goroutine 1 [running]:
main.testBody()
    ......./example/rcd/rc.go:115 +0x864
main.main()
    ....../example/rcd/rc.go:140 +0x1c

Possible Fix

Maybe some data are kept during circuit parsing?

Steps to Reproduce

Run the above codes.

Context

We are trying to create a library called chainark, which could be used to prove a chain-like structure recursively, and provides a validity proof for each element in the chain, basing its validity on its valid linking to its predecessor and all the way back to the genesis element.

In this project, we need to assemble some witness values for the inner circuit within the Define() function of the outer circuit. And we encountered the reported issue. The above codes is much simplified just to illustrated the issue.

Your Environment

weijiguo commented 8 months ago

The lines that panic was trying to compile the outer circuit:

    ccs, err := frontend.Compile(ecc.BN254.ScalarField(), scs.NewBuilder, &outer)
    if err != nil {
        panic(err)
    }

Which was trying to recursively create another witness for inner circuit verification within the Define() function of the outer circuit:

    // recursively create the witness
    witness, err := frontend.NewWitness(&w, ecc.BN254.ScalarField())
    if err != nil {
        panic(err)
    }
ivokub commented 8 months ago

Have a look at the full written PLONK recursion example: https://pkg.go.dev/github.com/consensys/gnark@v0.9.2-0.20240311003704-732620b476b9/std/recursion/plonk#example-package-Emulated

For the inner circuit witness assignment, we need to use recursive_plonk.Witness (as you have in your example). However, we cannot call recursive_plonk.ValueOfWitness in circuit as it expects as an input actual values (not variables what the outer circuit has).

Rather, you should use recursive_plonk.Witness as a witness to the outer circuit and then assign it when creating outer circuit witness assignment. Full example:

package main

import (
    "fmt"
    "testing"

    "github.com/consensys/gnark-crypto/ecc"
    "github.com/consensys/gnark/backend/plonk"
    cs "github.com/consensys/gnark/constraint/bn254"
    "github.com/consensys/gnark/frontend"
    "github.com/consensys/gnark/frontend/cs/scs"
    "github.com/consensys/gnark/std/algebra/emulated/sw_bn254"
    recursive_plonk "github.com/consensys/gnark/std/recursion/plonk"
    "github.com/consensys/gnark/test/unsafekzg"
)

type innerCircuit struct {
    X frontend.Variable
    Y frontend.Variable `gnark:",public"`
}

func (c *innerCircuit) Define(api frontend.API) error {
    api.AssertIsEqual(c.X, c.Y)
    return nil
}

type outerCircuit struct {
    VKey         recursive_plonk.VerifyingKey[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine]
    Proof        recursive_plonk.Proof[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine]
    InnerWitness recursive_plonk.Witness[sw_bn254.ScalarField]
}

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

    verifier, err := recursive_plonk.NewVerifier[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl](api)
    if err != nil {
        panic(err)
    }

    return verifier.AssertProof(c.VKey, c.Proof, c.InnerWitness, recursive_plonk.WithCompleteArithmetic())
}

func testBody() {
    inner := innerCircuit{}
    ccsInner, _ := frontend.Compile(ecc.BN254.ScalarField(), scs.NewBuilder, &inner)
    scsInner := ccsInner.(*cs.SparseR1CS)

    srs, srsLagrange, err := unsafekzg.NewSRS(scsInner, unsafekzg.WithFSCache())
    if err != nil {
        panic(err)
    }
    pkInner, vkInner, err := plonk.Setup(ccsInner, srs, srsLagrange)
    if err != nil {
        panic(err)
    }

    wInner := innerCircuit{X: 5, Y: 5}
    witnessInner, err := frontend.NewWitness(&wInner, ecc.BN254.ScalarField())
    if err != nil {
        panic(err)
    }

    proofInner, err := plonk.Prove(ccsInner, pkInner, witnessInner,
        recursive_plonk.GetNativeProverOptions(ecc.BN254.ScalarField(), ecc.BN254.ScalarField()))
    if err != nil {
        panic(err)
    }

    witnessInnerPublic, err := witnessInner.Public()
    if err != nil {
        panic(err)
    }
    err = plonk.Verify(proofInner, vkInner, witnessInnerPublic,
        recursive_plonk.GetNativeVerifierOptions(ecc.BN254.ScalarField(), ecc.BN254.ScalarField()))
    if err != nil {
        panic(err)
    }

    recursiveProof, err := recursive_plonk.ValueOfProof[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](proofInner)
    if err != nil {
        panic(err)
    }

    recursiveVK, err := recursive_plonk.ValueOfVerifyingKey[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](vkInner)
    if err != nil {
        panic(err)
    }

    outer := outerCircuit{
        VKey:         recursive_plonk.PlaceholderVerifyingKey[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](ccsInner),
        Proof:        recursive_plonk.PlaceholderProof[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine](ccsInner),
        InnerWitness: recursive_plonk.PlaceholderWitness[sw_bn254.ScalarField](ccsInner),
    }

    innerWitness, err := recursive_plonk.ValueOfWitness[sw_bn254.ScalarField](witnessInnerPublic)
    if err != nil {
        panic(err)
    }

    outerW := outerCircuit{
        VKey:         recursiveVK,
        Proof:        recursiveProof,
        InnerWitness: innerWitness,
    }

    ccs, err := frontend.Compile(ecc.BN254.ScalarField(), scs.NewBuilder, &outer)
    if err != nil {
        panic(err)
    }
    srs2, srsLagrange2, err := unsafekzg.NewSRS(ccs, unsafekzg.WithFSCache())
    if err != nil {
        panic(err)
    }
    pk, vk, err := plonk.Setup(ccs, srs2, srsLagrange2)
    if err != nil {
        panic(err)
    }

    fmt.Println("proving ...")
    outerWitess, err := frontend.NewWitness(&outerW, ecc.BN254.ScalarField())
    if err != nil {
        panic(err)
    }
    proof, err := plonk.Prove(ccs, pk, outerWitess,
        recursive_plonk.GetNativeProverOptions(ecc.BN254.ScalarField(), ecc.BN254.ScalarField()))
    if err != nil {
        panic(err)
    }

    fmt.Println("verifying ...")
    pubOuterWitness, err := outerWitess.Public()
    if err != nil {
        panic(err)
    }
    err = plonk.Verify(proof, vk, pubOuterWitness,
        recursive_plonk.GetNativeVerifierOptions(ecc.BN254.ScalarField(), ecc.BN254.ScalarField()))
    if err != nil {
        panic(err)
    }
}

func TestMain(t *testing.T) {
    testBody()
}

NB, the inner circuit is simple and brings out some edge cases which usually do not happen (for complex inner circuits, due to randomization). This requires using recursive_plonk.WithCompleteArithmetic() option. There were also a few other bugs, see diff vs your version.