How to achieve a % b, where a, b are frontend.Variable

[drakstik]

Hi,

Does anyone know how to accomplish modulo operations (%) and still use the remainder in complex assertions?

I have looked at emulated (https://pkg.go.dev/github.com/consensys/gnark@v0.8.0/std/math/emulated) and I'm having issues understanding how I can use my result in complex assertions afterwards. I am able to get the remainder using emulated field elements, like so:

type ModuloFieldCircuit[T emulated.FieldParams] struct {
}

func (c *ModuloFieldCircuit[T]) Define(api frontend.API) error {
	
	return nil
}

func (c *ModuloFieldCircuit[T]) FrModulo(api frontend.API, a, b frontend.API) error {
	
	f, err := emulated.NewField[T](api)
	if err != nil {
		return fmt.Errorf("new field: %w", err)
	}

	elA := f.NewElement(a)
	elB := f.NewElement(b)

	// Compute quotient (a / b)
	q := f.Div(elA, elB)

	// Compute remainder: a - q * b
	qTimesN := f.Mul(q, elB)
	remainder := f.Sub(elA, qTimesN)
}

I was wondering maybe if there is a way to turn a *emulated.Element[T] into a frontend.Variable? The issue is that I am trying to do somewhat complex series of assertions with the remainder, but I have the remainder as a frontend.Variable (see func below).

This is how I am trying to use the remainder:

func WithinCropArea(api frontend.API, remainder, frCol frontend.Variable, cropArea Fr_SquareArea) frontend.Variable {
	//	true if col >= X0 && remainder >= Y0
	withinTopLeft := api.And(api.Or(
		api.IsZero(api.Cmp(frCol, cropArea.topLeft.X)),
		api.IsZero(api.Sub(api.Cmp(frCol, cropArea.topLeft.X), 1)),
	), api.Or(
		api.IsZero(api.Cmp(remainder, cropArea.topLeft.Y)),
		api.IsZero(api.Sub(api.Cmp(remainder, cropArea.topLeft.Y), 1)),
	))

	//	true if col <= X1 && remainder <= Y1
	withinBottomRight := api.And(api.Or(
		api.IsZero(api.Cmp(frCol, cropArea.bottomRight.X)),
		api.IsZero(api.Sub(api.Cmp(frCol, cropArea.topLeft.X), 1)),
	), api.Or(
		api.IsZero(api.Cmp(remainder, cropArea.topLeft.Y)),
		api.IsZero(api.Sub(api.Cmp(remainder, cropArea.topLeft.Y), 1)),
	))

	// true if currentIdx is within crop area
	withinCropArea := api.And(withinTopLeft, withinBottomRight)

	return withinCropArea
}

Thank you!

[ivokub]

What are the value ranges you are performing operations in? Keep in mind that frontend.Variable value are defined in a finite field defined by the elliptic curve used for generating the proof. For example when use use BN254 for generating the proof then the operations are in the scalar field of BN254, which is mod 21888242871839275222246405745257275088548364400416034343698204186575808495617.

If the operations you define are small (and in your example it seems they may be as you work with a grid and want to use it for the grid size?), then you can essentially compute using native arithmetic (as you never over or underflow).

There is a very similar discussion happening in #1361. You could for example do:

package smallmod

import (
	"errors"
	"fmt"
	"math/big"
	"testing"

	"github.com/consensys/gnark/constraint/solver"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/test"
)

func smallModHint(mod *big.Int, inputs []*big.Int, outputs []*big.Int) error {
	// computes a % r = b
	// inputs[0] = a -- input
	// inputs[1] = r -- modulus
	// outputs[0] = b -- remainder
	// outputs[1] = (a-b)/r -- quotient
	if len(outputs) != 2 {
		return errors.New("expected 2 outputs")
	}
	if len(inputs) != 2 {
		return errors.New("expected 2 inputs")
	}
	outputs[1].QuoRem(inputs[0], inputs[1], outputs[0])
	fmt.Println(outputs[0], outputs[1], inputs[0], inputs[1])
	return nil
}

func SmallMod(api frontend.API, a, r frontend.Variable) (quo, rem frontend.Variable) {
	res, err := api.Compiler().NewHint(smallModHint, 2, a, r)
	if err != nil {
		panic(err)
	}
	rem = res[0]
	quo = res[1]

	// to prevent against overflows, we assume that the inputs are small relative to the native field
	nbBits := api.Compiler().Field().BitLen()/2 - 2
	bound := new(big.Int).Lsh(big.NewInt(1), uint(nbBits))
	api.AssertIsLessOrEqual(rem, bound)
	api.AssertIsLessOrEqual(quo, bound)

	api.AssertIsEqual(a, api.Add(api.Mul(quo, r), rem))
	return
}

type Circuit struct {
	A, R frontend.Variable
}

func (c *Circuit) Define(api frontend.API) error {
	quo, rem := SmallMod(api, c.A, c.R)
	api.Println(c.A)
	api.Println(c.R)
	api.Println(quo)
	api.Println(rem)
	return nil
}

func TestSmallMod(t *testing.T) {
	assert := test.NewAssert(t)

	// hint needs to be provided manually to the solver. Otherwise it doesn't know how to compute the value
	solver.RegisterHint(smallModHint)

	assert.CheckCircuit(&Circuit{}, test.WithValidAssignment(&Circuit{A: 123000, R: 1000}))

}

[drakstik]

Thank you for your expeditious answer!

My "grid" is an [N*N]frontend.Variable which represents an image. Digital images are typically as high as 2048 × 1536 pixels, which would fit in a 2048 × 2048 image representation. Each pixel is a uint32 -> frontend.Variable representing RGB values. I'm still on a naïve approach, so I hope this works with those ranges.

I'll try this out and report back. Thanks again!

[drakstik]

I tried your proposed solution and it worked out! Thank you!