how to implement msm for element exceeding MODULUS in ecc.BN254.ScalarField()

[xiangjianmeng]

The full example is the Unit test TestMsmSolve in https://github.com/xiangjianmeng/gnark-halo2-verify/tree/fix-compile

[ivokub]

Instead of using ToElement, you can provide the emulated elements as witness to the circuit and then initialize then during witness assignment using emulated.ValueOf.

So instead of:

type yourCircuit struct {
    X frontend.Variable
}

func (c *yourCircuit) Define(api frontend.API) error {
    xnna, err := ToElement(c.X)
    // xnna is type emulated.Element[emulated.BN254Fp]
   // ...
}

you could instead have

type nnaCircuit struct {
    X emulated.Element[emulated.BN254Fp]
}

func (c *nnaCircuit) Define(api frontend.API) error {
    // use c.X as emulated.Element[emulated.BN254Fp] directly
   // ...
}

This approach works similarly for providing the point directly as witness element, see for example https://github.com/Consensys/gnark/blob/master/std/algebra/emulated/sw_emulated/point_test.go#L622-L661

[xiangjianmeng]

One option to run Solidity test is by using the assert.Checkcircuit method:

package issue1186

import (
	"math/big"
	"testing"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark-crypto/ecc/bn254"
	"github.com/consensys/gnark-crypto/ecc/bn254/fp"
	"github.com/consensys/gnark/backend"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/std/algebra/emulated/sw_bn254"
	"github.com/consensys/gnark/std/algebra/emulated/sw_emulated"
	"github.com/consensys/gnark/std/math/emulated"
	"github.com/consensys/gnark/std/math/emulated/emparams"
	"github.com/consensys/gnark/test"
)

type TestBN254ScalarMul struct {
	Point  sw_bn254.G1Affine
	Scalar sw_bn254.Scalar
	Res    sw_bn254.G1Affine `gnark:",public"`
}

func (c *TestBN254ScalarMul) Define(api frontend.API) error {
	cr, err := sw_emulated.New[emparams.BN254Fp, emparams.BN254Fr](api, sw_emulated.GetBN254Params())
	if err != nil {
		return err
	}
	res := cr.ScalarMul(&c.Point, &c.Scalar)
	cr.AssertIsEqual(res, &c.Res)
	return nil
}

func TestMsmSolve(t *testing.T) {
	assert := test.NewAssert(t)
	x, _ := new(big.Int).SetString("1", 10)
	y, _ := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208581", 10)
	scalar, _ := new(big.Int).SetString("21147276235438245106538451154094232271190030085887596632745409482267565260819", 10)

	var point = bn254.G1Affine{
		X: *new(fp.Element).SetBigInt(x),
		Y: *new(fp.Element).SetBigInt(y),
	}
	assert.True(point.IsOnCurve())
	var res1 bn254.G1Affine
	res1.ScalarMultiplication(&point, scalar)

	witnessCircuit := TestBN254ScalarMul{
		Point: sw_bn254.G1Affine{
			X: emulated.ValueOf[emulated.BN254Fp](x),
			Y: emulated.ValueOf[emulated.BN254Fp](y),
		},
		Scalar: emulated.ValueOf[emulated.BN254Fr](scalar),
		Res: sw_bn254.G1Affine{
			X: emulated.ValueOf[emulated.BN254Fp](res1.X),
			Y: emulated.ValueOf[emulated.BN254Fp](res1.Y),
		},
	}
	circuit := TestBN254ScalarMul{}

	assert.CheckCircuit(&circuit, test.WithValidAssignment(&witnessCircuit), test.WithBackends(backend.GROTH16), test.WithCurves(ecc.BN254))
}

We don't run solidity checker by default, to ensure it is run, use the solccheck build tag:

go test -timeout 10m -tags solccheck,prover_checks -run ^TestMsmSolve$ github.com/consensys/gnark/examples/issue1186 -v -count=1

For this to work, you need to have an additional utility gnark-solidity-checker. We have it in a separate repository to avoid huge dependency list introduced by importing go-ethereum. See https://github.com/consensys/gnark-solidity-checker for how to install its dependencies and then run

go install github.com/consensys/gnark-solidity-checker@master

In that repository you can also see how to construct the inputs for the Groth16 verifier i.e. https://github.com/Consensys/gnark-solidity-checker/blob/main/cmd/templates.go#L72-L124. We don't have a good way to export the full proof as a byte slice yet as in PLONK solidity verifier, so you need to do it a bit manually, but hopefully the example is clear. We have an open issue for that #956.

Sorry for the difficult setup, we are now mostly focused on supporting PLONK Solidity verifier, but will try to improve Groth16 verifier also as it is still quite much used by the community.

Is there any true full example to extract the proof for plonk or groth16 and could be veified successfully? I haven't execute a successful verify on sepolia. I have to say that gnark have more effective proof generation but bad development experience. It's time to release well docs to help developers, please @ivokub

gnark-solidity-checker/blob/main/cmd/templates.go#L72-L124 is outdated. I read the proof which is generated by calling proof.WriteRawTo(fProof), it will report error "wrong proof size" just use the proof bytes by reading from the fProof.

Plonk :

  function Verify(bytes calldata proof, uint256[] calldata public_inputs) 
  public view returns(bool success)

Groth16 :

function verifyProof(
        uint256[8] calldata proof,
        uint256[2] calldata commitments,
        uint256[2] calldata commitmentPok,
        uint256[1] calldata input
    ) public view

[xiangjianmeng]

For plonk, what is the composition of proof according to the proof.json like below?

{
    "LRO": [
        {
            "X": "5068754427898724426029771455046457188163043055121832772770221235082819984145",
            "Y": "18851729387189152644467529618601227335279796824742946508690050081054226102983"
        },
        {
            "X": "14830782145735965492483076901946445558536609459415927456399517620548508053414",
            "Y": "15580827685522299527443199256811777558228241510091352199928951948219311809230"
        },
        {
            "X": "20594494328227607595227277976864288620450537011195542954724506488213030380987",
            "Y": "21480251863156438100534567622454859776300104255332187019007919748487243533849"
        }
    ],
    "Z": {
        "X": "15321297457799948729154487806218913299336728208571125433374617548944235581930",
        "Y": "13809380603813268219123049102850974226342616792071354973626608758561321419627"
    },
    "H": [
        {
            "X": "16176276968629495625692007549001937933181347638790225846976138172406778222543",
            "Y": "8861039016742063506250018132494519487179102555670085780539506821775718383008"
        },
        {
            "X": "12282798022621613299284252922570970414145292215383669402646936668971620962436",
            "Y": "9496235448710848146653846875929128122882849456068539133360230800683871502813"
        },
        {
            "X": "7221041329061370290158577346816658976376802272060036982397060850336836966856",
            "Y": "21145378127967707665842987755380450477663281999884742601933828927879224519235"
        }
    ],
    "Bsb22Commitments": [
        {
            "X": "21354011120776161635156329271440352425230842017783895232026276815627968366156",
            "Y": "2503995220519878249754218127162398876399673389617923656916128372470934830033"
        }
    ],
    "BatchedProof": {
        "H": {
            "X": "8154560379277721005888093297933697296100483428291290067382187887497900949045",
            "Y": "1225822929342849001212552850350154701241060330608523210882176298562927594823"
        },
        "ClaimedValues": [
            "7905947230610726753372030312970737991065038453366782965017362499127553795215",
            "3341094796214245229162044328578487915534594260089342557017923592429011680058",
            "9834495509219617880931409384233532181961783535047831432634981732996597028932",
            "17728278742384692498835662028399853678109881457279100381753119889118862150427",
            "19745499365358749352055224406866564404150967534154738557460409242825271859245",
            "374427416666498463335942982632679584718156791563566894712299048820142069677",
            "4768778765442065699146342285648850757587858299058723688296394791896390992872"
        ]
    },
    "ZShiftedOpening": {
        "H": {
            "X": "10209726027734299341457378937924842479106723123692305897524484255703264356979",
            "Y": "19861356696008529767058242788023540878864246417820538079012752037646254688413"
        },
        "ClaimedValue": "13020897359934297096469603196587540228161971757640581087425581381996022245852"
    }
}

[ivokub]

Indeed, our docs are not up-to-date and do not cover all the steps, particularly for the Solidity verifier. See issues:

• gnark docs need love #1183
• refactor: Groth16 Solidity verifier improvements #1094
• feat: allow marshalling into Solidity-compatible format from witness.Witness. #956

We are currently focusing on implementing full coverage for Linea L2 and have postponed working on non-related issues, but will get back soon.

For checking Groth16 proof in Solidity, can you also try when providing the Prove() function with backend.WithProverHashToFieldFunction(sha256.New()) option? The commitment computation is hard-coded with sha256 currently.

For checking PLONK proof in Solidity, the byte array can be obtained from the Proof object by calling MarshalSolidity() method. NB! to be able to call it you have to type assert that the proof object has the method:

proof, err := plonk.Prove(...)
solidityproofer, ok := proof.(interface{MarshalSolidity() []byte})
...
solidityproof := solidityproofer.MarshalSolidity()

[xiangjianmeng]

@ivokub Thanks a lot. Have the solidity verify contract been audited by any other auditing firm?

[ivokub]

PLONK contract has been audited. We'll publish it soon. Groth16 contract has been looked at, but imo we don't have an audit report for it.