refactor: std/math/nonnative -> std/math/emulated

[gbotrel]

This PR refactors std/math/nonnative -> std/math/emulated.

emulated.Field has no pointer receiver operations, and only usage is through NewField .
Emulated arithmetic is now parametrized with the emulated field constants; usage is changed to:

type Circuit struct {
	// Limbs of non-native elements X, Y and Res
	X, Y, Res emulated.Element[emulated.Secp256k1]
}

func (circuit *Circuit) Define(api frontend.API) error {
	// wrap API to work in SECP256k1 scalar field
	secp256k1, err := emulated.NewField[emulated.Secp256k1](api)
	if err != nil {
		return err
	}

	tmp := secp256k1.Mul(circuit.X, circuit.Y)
	secp256k1.AssertIsEqual(tmp, circuit.Res)
	return nil
}

// test file:
func TestEmulatedArithmetic(t *testing.T) {
	assert := test.NewAssert(t)
	std.RegisterHints()

	var circuit, witness Circuit

	witness.X.Assign("26959946673427741531515197488526605382048662297355296634326893985793")
	witness.Y.Assign("53919893346855483063030394977053210764097324594710593268653787971586")
	witness.Res.Assign("485279052387156144224396168012515269674445015885648619762653195154800")

	assert.ProverSucceeded(&circuit, &witness, test.WithCurves(ecc.BN254), test.WithBackends(backend.GROTH16), test.NoSerialization())
}

[gbotrel]

@ivokub I think we should look at merging this as is -- this PR doesn't do any algorithmic change on your work, just cosmetic / refactoring.
A future PR will be needed to improve perf 👍

Will also add a warning that this feature is "experimental".

[ivokub]

Suggested edit:

diff --git a/std/math/emulated/hints.go b/std/math/emulated/hints.go
index da27bb1f..557b464a 100644
--- a/std/math/emulated/hints.go
+++ b/std/math/emulated/hints.go
@@ -12,10 +12,7 @@ import (
 // inside a func, then it becomes anonymous and hint identification is screwed.
 
 func init() {
-	hints := GetHints()
-	for _, h := range hints {
-		hint.Register(h)
-	}
+	hint.Register(GetHints()...)
 }
 
 // GetHints returns all hint functions used in the package.

[ivokub]

Suggested edit:

diff --git a/std/math/emulated/params.go b/std/math/emulated/params.go
index fce8a1c3..067b6c9f 100644
--- a/std/math/emulated/params.go
+++ b/std/math/emulated/params.go
@@ -51,7 +51,7 @@ func (fp BN254Fp) BitsPerLimb() uint { return 32 }
 func (fp BN254Fp) IsPrime() bool     { return true }
 func (fp BN254Fp) Modulus() *big.Int { return ecc.BN254.BaseField() }
 
-// BLS12377Fp provide type parametrization for emulated field on 8 limb of width 32bits
+// BLS12377Fp provide type parametrization for emulated field on 6 limb of width 64bits
 // for modulus 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
 type BLS12377Fp struct{}
 

[ivokub]

Suggested edit:

diff --git a/std/math/emulated/field.go b/std/math/emulated/field.go
index e3f1f533..5e2cdd6f 100644
--- a/std/math/emulated/field.go
+++ b/std/math/emulated/field.go
@@ -16,10 +16,6 @@ import (
 	"github.com/rs/zerolog"
 )
 
-type API interface {
-	frontend.API
-}
-
 // field defines the parameters of the emulated ring of integers modulo n. If
 // n is prime, then the ring is also a finite field where inverse and division
 // are allowed.

[ivokub]

Suggested edit:

diff --git a/std/math/emulated/field_test.go b/std/math/emulated/field_test.go
index 235a583c..06bece44 100644
--- a/std/math/emulated/field_test.go
+++ b/std/math/emulated/field_test.go
@@ -220,6 +220,7 @@ func (circuit *pairingBLS377) Define(api frontend.API) error {
 }
 
 func TestPairingBLS377(t *testing.T) {
+	t.Skip()
 	assert := test.NewAssert(t)
 
 	_, _, P, Q := bls12377.Generators()
diff --git a/std/math/emulated/pairing_test.go b/std/math/emulated/pairing_test.go
index cec46b2c..c7b722c1 100644
--- a/std/math/emulated/pairing_test.go
+++ b/std/math/emulated/pairing_test.go
@@ -20,6 +20,7 @@ func (circuit *mlBLS377) Define(api frontend.API) error {
 }
 
 func TestE12SquareBLS377(t *testing.T) {
+	t.Skip()
 	assert := test.NewAssert(t)
 
 	circuit := mlBLS377{

[ivokub]

Suggested edit:

diff --git a/std/math/emulated/element.go b/std/math/emulated/element.go
index 180b94dd..59747528 100644
--- a/std/math/emulated/element.go
+++ b/std/math/emulated/element.go
@@ -410,9 +410,6 @@ func (f *field[T]) assertIsEqual(a, b Element[T]) Element[T] {
 	// so essentially, we say "I know an element k such that k*p == diff"
 	// hence, diff == 0 mod p
 	p := f.Modulus()
-	// we compute k such that diff / p == k
-	// so essentially, we say "I know an element k such that k*p == diff"
-	// hence, diff == 0 mod p
 	k, err := f.computeQuoHint(diff)
 	if err != nil {
 		panic(fmt.Sprintf("hint error: %v", err))

[ivokub]

Suggested edit:

diff --git a/std/math/emulated/element.go b/std/math/emulated/element.go
index 180b94dd..78c48ced 100644
--- a/std/math/emulated/element.go
+++ b/std/math/emulated/element.go
@@ -551,10 +551,3 @@ func max[T constraints.Ordered](a, b T) T {
 	}
 	return b
 }
-
-func min[T constraints.Ordered](a, b T) T {
-	if a < b {
-		return a
-	}
-	return b
-}

[ivokub]

Suggested edit:

diff --git a/std/math/emulated/hints.go b/std/math/emulated/hints.go
index da27bb1f..4276771d 100644
--- a/std/math/emulated/hints.go
+++ b/std/math/emulated/hints.go
@@ -110,9 +110,7 @@ func RemHint(_ *big.Int, inputs []*big.Int, outputs []*big.Int) error {
 	if err != nil {
 		return err
 	}
-	for _, o := range outputs {
-		o.SetUint64(0)
-	}
+
 	r := new(big.Int)
 	r.Rem(x, y)
 	if err := decompose(r, nbBits, outputs); err != nil {

[ivokub]

Suggested edit:

diff --git a/std/math/emulated/field_test.go b/std/math/emulated/field_test.go
index 235a583c..991193f9 100644
--- a/std/math/emulated/field_test.go
+++ b/std/math/emulated/field_test.go
@@ -15,7 +15,6 @@ import (
 	"github.com/consensys/gnark/std/algebra/fields_bls12377"
 	"github.com/consensys/gnark/std/algebra/sw_bls12377"
 	"github.com/consensys/gnark/test"
-	"github.com/stretchr/testify/require"
 )
 
 func witnessData(q *big.Int) (X1, X2, X3, X4, X5, X6, Res *big.Int) {
@@ -170,7 +169,7 @@ func TestIntegrationApi(t *testing.T) {
 }
 
 func TestVarToElements(t *testing.T) {
-	assert := require.New(t)
+	assert := test.NewAssert(t)
 	_f, _ := NewField[BN254Fp](nil)
 
 	f := _f.(*field[BN254Fp])

[ivokub]

Looks good. Does it make sense to separate limb width into second type parameter (instead of embedding it in FieldParams)?

[gbotrel]

Looks good. Does it make sense to separate limb width into second type parameter (instead of embedding it in FieldParams)?

Well, I see the point. One one hand, it hurts readability, but IF we need to emulate same field with different parameters for limbs, it's cleaner.

I suspect circuit developer will have their own struct (fieldParams) anyhow to tune that depending on target...?

[ivokub]

Looks good. Does it make sense to separate limb width into second type parameter (instead of embedding it in FieldParams)?

Well, I see the point. One one hand, it hurts readability, but IF we need to emulate same field with different parameters for limbs, it's cleaner.

I suspect circuit developer will have their own struct (fieldParams) anyhow to tune that depending on target...?

I think the circuit developers would in general be interested in some standard fields (maybe one for every fp/fr in gnark-crypto), not really caring about rest (limb widths etc.). If there is some special use case, then the developer can define its own type with their own modulus and limb size.

I also think that we really cannot optimise easily th width as the final number of constraints depends on the non-native operations. (Probably to obtain a good heuristic we should just compile with different nbBits and find the value which minimises the number of constraints). So it would be good to have some sane defaults, for which the current ones make sense.