Multiplying a MiMC result fails after upgrading to 0.10.0

[secure12]

I have a circuit over BW6-761 which involves a part verifying this:

import (
  bls "github.com/consensys/gnark/std/algebra/native/sw_bls12377"
  "github.com/consensys/gnark/std/hash/mimc"
)

func (circuit *MyCircuit) Define(api frontend.API) error {
  m, _ := mimc.NewMiMC(api)
  preimage := circuit.H
  m.Write(preimage.X)
  m.Write(preimage.Y)
  preimage.ScalarMulBase(api, m.Sum())
  // not even asserting anything
  return nil
}

type MyCircuit struct {
  H bls.G1Affine
}

So H is a BLS12-377 G1 point.

After upgrading to 0.10.0, attempt to generate a proof with a valid witness gives the following error:

14:07:35 ERR error="constraint #1309 is not satisfied: qL⋅xa + qR⋅xb + qO⋅xc + qM⋅(xaxb) + qC != 0 → 2243532423002762739192056004629257692190643941628461340447015068082287571184 + 245951388471720416337462867129806383963203273194829779534164962454840822539647035183076162807325460984295687032279 + 0 + 0 + 0 != 0" nbConstraints=4123

Apparently, the problematic line is preimage.ScalarMulBase(api, m.Sum()), since the error was gone after removing it.

Is there any other changes in 0.10.0 that I should be aware of? Many thanks.

[ivokub]

Can you also provide the full test function with the witness assignment?

Could you try using algopts.WithCompleteArithmetic() option for the scalar-mul?

[secure12]

Here's a full example:

package main

import (
	"fmt"

	"github.com/consensys/gnark-crypto/ecc"
	bls12377 "github.com/consensys/gnark-crypto/ecc/bls12-377"
	bw6761kzg "github.com/consensys/gnark-crypto/ecc/bw6-761/kzg"
	"github.com/consensys/gnark-crypto/kzg"
	"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"
	bls "github.com/consensys/gnark/std/algebra/native/sw_bls12377"
	"github.com/consensys/gnark/std/hash/mimc"
	"github.com/consensys/gnark/test/unsafekzg"
)

func main() {
	ccs, err := compile()
	if err != nil {
		panic(err)
	}
	srs, lagrange, err := unsafekzg.NewSRS(ccs)
	if err != nil {
		panic(err)
	}
	pk, _, err := plonk.Setup(ccs, srs, lagrange)
	if err != nil {
		panic(err)
	}
	_, _, err = prove(&Input{
		H: &bls12377.G1Affine{},
	}, pk, srs, nil, ccs)
	if err != nil {
		panic(err)
	}
}

type C struct {
	H bls.G1Affine
}

func (circuit *C) Define(api frontend.API) error {
	mimcCircuit, err := mimc.NewMiMC(api)
	if err != nil {
		return err
	}
	carry := circuit.H

	mimcCircuit.Write(carry.X)
	mimcCircuit.Write(carry.Y)
	carry.ScalarMulBase(api, mimcCircuit.Sum()) // error
	return nil
}

type Input struct {
	H *bls12377.G1Affine
}

func compile() (constraint.ConstraintSystem, error) {
	return frontend.Compile(ecc.BW6_761.ScalarField(), scs.NewBuilder, &C{})
}

// `ccs` can be nil. It will be compiled in that case.
func setup(srs kzg.SRS, ccs constraint.ConstraintSystem, srsLagrange kzg.SRS) (plonk.ProvingKey, plonk.VerifyingKey, error) {
	if ccs == nil {
		var err error
		if ccs, err = compile(); err != nil {
			return nil, nil, fmt.Errorf("error compiling: %s", err)
		}
	}
	return plonk.Setup(ccs, srs, srsLagrange)
}

func prove(input *Input, pk plonk.ProvingKey, srs, srsLagrange kzg.SRS, ccs constraint.ConstraintSystem) (plonk.Proof, witness.Witness, error) {
	if ccs == nil {
		var err error
		if ccs, err = compile(); err != nil {
			return nil, nil, fmt.Errorf("error compiling: %s", err)
		}
	}
	if pk == nil {
		var err error
		pk, _, err = setup(srs, ccs, srsLagrange)
		if err != nil {
			return nil, nil, fmt.Errorf("error running setup: %s", err)
		}
	}

	var h bls.G1Affine
	h.Assign(input.H)

	assignment := C{
		H: h,
	}
	witness, err := frontend.NewWitness(&assignment, ecc.BW6_761.ScalarField())
	if err != nil {
		return nil, nil, fmt.Errorf("error creating new witness: %s", err)
	}
	proof, err := plonk.Prove(ccs, pk, witness)
	if err != nil {
		return nil, nil, fmt.Errorf("error proving: %s", err)
	}
	return proof, witness, nil
}

Is the problem that we now have to manually reduce the result of the BW6-761 MiMC after 0.10.0?

[secure12]

algopts.WithCompleteArithmetic() didn't help.

[ivokub]

Ah, I see now. Yes, the behaviour is changed a bit. This is the case of 2-chains where BLS12-377 points can be natively represented in BW6-761. But keep in mind that the scalars have to be in BLS12-377 scalar field but MiMC outputs scalars in BW6-761 scalar field. So the GLV decomposition check in scalar multiplication fails as it assumes that the given scalar doesn't overflow BLS12-377 scalar field.

The solution would be to use MiMC wrapper which outputs values in the requested target field. If you would rewrite the circuit as:

import (
	"github.com/consensys/gnark/std/math/emulated/emparams"
	"github.com/consensys/gnark/std/recursion"
)

// ...

func (circuit *C) Define(api frontend.API) error {
	shorthash, err := recursion.NewHash(api, emparams.BLS12377Fr{}.Modulus(), false)
	if err != nil {
		return err
	}
	carry := circuit.H

	shorthash.Write(carry.X)
	shorthash.Write(carry.Y)

	carry.ScalarMulBase(api, shorthash.Sum())
	return nil
}

then the test should work.

[secure12]

Thanks Ivo, that works. For future readers, your hashes outside the circuit will need to be replaced by recursion.NewShort().

Is there somewhere I can read more about the security of your short circuit hash implementation?

[ivokub]

Unfortunately there isn't a writeup on it, we only have the package documentation. Essentially we apply MiMC hash and cut off the excess to fit into the scalar field. It is defined in recursion package.