emulated

package
v0.14.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 22, 2025 License: Apache-2.0 Imports: 21 Imported by: 138

Documentation

Overview

Package emulated implements operations over any modulus.

Non-native computation in circuit

Usually, the computations in a SNARK circuit are performed in the 'native' field of the curve. The native field is defined by the scalar field of the underlying curve. This package implements non-native arithmetic on top of the native field to emulate operations in any field and ring.

This package does this by splitting the element into smaller limbs. The parameters for splitting the limb and defining the modulus are stored in types implementing FieldParams type. The elements are parametrized by those types to make compile-time distinction between different emulated fields.

This package defines Element type which stores the element value in split limbs. On top of the Element instance, this package defines typical arithmetic as addition, multiplication and subtraction. If the modulus is a prime (i.e. defines a finite field), then inversion and division operations are also possible.

The results of the operations are not always reduced to be less than the modulus. For consecutive operations it is necessary to manually reduce the value using Field.Reduce method. The number of operations which can be performed without reduction depends when the operations result starts overflowing the limbs.

Element representation

We operate in the scalar field of the SNARK curve (native field). Denote the modulus of the native field as 'q'. Representing the modulus of the native field requires 'n' bits. We wish to emulate operations over modulus 'r'. Modulus r may or may not be a prime. If r is not prime, then we do not have inversion and division operations (the corresponding methods panic). Let the bitlength of r be 'm'. We note that r may be smaller, larger or equal to q.

To represent an element x ∈ N_r, we choose the limb width 'w' such that 

w ≤ (m-1)/2

and write its integer representation as 

x = ∑_{i=0}^k x_i 2^{w i}.

Here, the variable 'x_i' is the w bits of x starting from 2^{w i}, 'k' is the number of limbs and is computed as 

k = (n+w-1)/w,   // NB! integer division

and 'i' is the limb index. In this representation the element is represented in little-endian (least significant limbs first) order. We do not necessarily require that the limb values x_i are less than 2^w. This may happen if the limb values are obtained as a result of arithmetic operations between elements. If we know that the limb values do not overflow 2^w, then we say that the element is in normal form.

In the implementation, we have two functions for splitting an element into limbs and composing an element from limbs -- limbs.Decompose and limbs.Recompose. The limbs.Recompose function also accepts element in non-normal form.

Elements in non-normal form

When an element is initialized, the limbs are in normal form, i.e. the values of the limbs have bitwidth strictly less than w. As addition and multiplication are performed on limbs natively, then the bitwidths of the limbs of the result may be larger than w. We track the number of bits which may exceed the initial width of the limbs. We denote the number of such excess bits as 'f' and call it overflow. The total maximal bitwidth of the limbs is then 

w+f.

Keep in mind that parameter w is global for all emulated elements and f is individual for every individual element.

To compute the overflow for the operations, we consider the arithmetic operations which affect the overflow. In this implementation only addition is done natively (limb-wise addition). When adding two elements, the bitwidth of the result is up to one bit wider than the width of the widest element.

In the context of overflows, if the overflows of the addends are f_0 and f_1 then the overflow value f' for the sum is computed as 

f' = max(f_0, f_1)+1.

Multiplication

The complexity of native limb-wise multiplication is k^2. This translates directly to the complexity in the number of constraints in the constraint system.

For multiplication, we would instead use polynomial representation of the elements: 

x = ∑_{i=0}^k x_i 2^{w i}
y = ∑_{i=0}^k y_i 2^{w i}.

as 

x(X) = ∑_{i=0}^k x_i X^i
y(X) = ∑_{i=0}^k y_i X^i.

If the multiplication result modulo r is c, then the following holds: 

x * y = c + z*r.

We can check the correctness of the multiplication by checking the following identity at a random point: 

x(X) * y(X) = c(X) + z(X) * r(X) + (2^w' - X) e(X),

where e(X) is a polynomial used for carrying the overflows of the left- and right-hand side of the above equation.

This approach can be extended to the case when the left hand side is not a simple multiplication, but rather any evaluation of a multivariate polynomial. So in essence we can check the correctness of any polynomial evaluation modulo r: 

F(x_1, x_2, ..., x_n) = c + z*r

through the following identity: 

F(x_1(X), x_2(X), ..., x_n(X)) = c(X) + z(X) * r(X) + (2^w' - X) e(X).

Subtraction

We perform subtraction limb-wise between the elements x and y. However, we have to ensure than any limb in the result does not result in overflow, i.e. 

x_i ≥ y_i, ∀ 0≤i<k.

As this does not hold in general, then we need to pad x such that every limb x_i is strictly larger than y_i.

The additional padding 'u' has to be divisible by the emulated modulus r and every limb u_i must be larger than x_i-y_i. Let f' be the overflow of y. We first compute the limbs u'_i as 

u'_i = 1 << (w+f'), ∀ 0≤i<k.

Now, as u' is not divisible by r, we need to compensate for it: 

u'' = u' + regroup(r - (u' % r)),

where regroup() regroups the argument so that it is in normal form (i.e. first applies recompose() and then decompose() method).

We see that u” is now such that it is divisible by r and its every limb is larger than every limb of b. The subtraction is performed as 

z_i = x_i + u''_i - y_i, ∀ 0≤i<k.

Equality checking

Equality checking is performed using modular multiplication. To check that a, b are equal modulo r, we compute 

diff = b-a,

and enforce modular multiplication check using the techniques for modular multiplication: 

diff * 1 = 0 + k * r.

Bitwidth enforcement

When element is computed using hints, we need to ensure that every limb is not wider than k bits. For that, we perform bitwise decomposition of every limb and check that k lower bits are equal to the whole limb. We omit the bitwidth enforcement for multiplication as the correctness of the limbs is ensured using the corresponding system of linear equations.

Additionally, we apply bitwidth enforcement for elements initialized from integers.

Modular reduction

To reduce the integer value of element x to be less than the modulus, we compute the remainder x' of x modulo r using hint, enforce the bitwidth of x' and assert that 

x' == x

using element equality checking.

Values computed using hints

We additionally define functions for computing inverse of an element and ratio of two elements. Both function compute the actual value using hint and then assert the correctness of the operation using multiplication.

Constant values

The package currently does not explicitly differentiate between constant and variable elements. The builder may track some elements as being constants. Some operations have a fast track path for cases when all inputs are constants. There is Field.MulConst, which provides variable by constant multiplication.

Variable-modulus operations

The package also exposes methods for performing operations with variable modulus. The modulus is represented as an element and is not required to be prime. The methods for variable-modulus operations are Field.ModMul, Field.ModAdd, Field.ModExp and Field.ModAssertIsEqual. The modulus is passed as an argument to the operation.

The type parameter for the Field should be sufficiently big to allow to fit the inputs and the modulus. Recommended to use predefined emparams.Mod1e512 or emparams.Mod1e4096.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func DivHint 

func DivHint(mod *big.Int, inputs []*big.Int, outputs []*big.Int) error

DivHint computes the value z = x/y for inputs x and y and stores z in outputs.

func GetEffectiveFieldParams added in v0.13.0 

func GetEffectiveFieldParams[T FieldParams](field *big.Int) (nbLimbs, nbBits uint)

GetEffectiveFieldParams returns the number of limbs and bits per limb for a given field. If the field implements the DynamicFieldParams interface, then the number of limbs and bits per limb are computed dynamically based on the field size. Otherwise, the values are taken from the FieldParams interface.

func GetHints 

func GetHints() []solver.Hint

GetHints returns all hint functions used in the package.

func InverseHint 

func InverseHint(mod *big.Int, inputs []*big.Int, outputs []*big.Int) error

InverseHint computes the inverse x^-1 for the input x and stores it in outputs.

func NewVarGenericHint added in v0.14.0 

func NewVarGenericHint[T1, T2 FieldParams](
	api frontend.API,
	nbNativeOutputs, nbEmulated1Outputs, nbEmulated2Outputs int,
	nativeInputs []frontend.Variable,
	emulated1Inputs []*Element[T1],
	emulated2Inputs []*Element[T2],
	hf solver.Hint,
) (nativeOutputs []frontend.Variable, emulated1Outputs []*Element[T1], emulated2Outputs []*Element[T2], err error)

NewVarGenericHint allows to call a hint function operating over native and two emulated fields. It is useful in the context where the hint needs to get inputs from several different fields or return outputs in different fields.

The hint function hf received as an input wrapped inputs and it should unwrap it using UnwrapHintContext function. For example: 

func hint(mod *big.Int, inputs, outputs []*big.Int) error {
    return emulated.UnwrapHintContext(mod, inputs, outputs, func(hctx emulated.HintContext) error {
        // here we can access inputs and outputs for each field
        // and perform operations on them

        // to get the moduli for the fields we can do:
        moduli := hctx.Moduli()
        // now we can access inputs and outputs for each field
        nativeInputs, nativeOutputs := hctx.InputsOutputs(moduli[0])
        emulated1Inputs, emulated1Outputs := hctx.InputsOutputs(moduli[1])
        emulated2Inputs, emulated2Outputs := hctx.InputsOutputs(moduli[2])

        // now we perform operations on the inputs and outputs and then we set the outputs
        // using big.Int.Set method, e.g.:
        for i := range nativeOutputs {
            nativeOutputs[i].Set(nativeInputs[i].Mul(nativeInputs[i], big.NewInt(2)))
        }
        for i := range emulated1Outputs {
            emulated1Outputs[i].Set(emulated1Inputs[i].Mul(emulated1Inputs[i], big.NewInt(2)))
        }
        for i := range emulated2Outputs {
            emulated2Outputs[i].Set(emulated2Inputs[i].Mul(emulated2Inputs[i], big.NewInt(2)))
        }
        return nil
    })
}

func SqrtHint added in v0.9.0 

func SqrtHint(mod *big.Int, inputs []*big.Int, outputs []*big.Int) error

SqrtHint compute square root of the input.

func UnwrapHint added in v0.9.0 

func UnwrapHint(nativeInputs, nativeOutputs []*big.Int, nonnativeHint solver.Hint) error

UnwrapHint unwraps the native inputs into nonnative inputs. Then it calls nonnativeHint function with nonnative inputs. After nonnativeHint returns, it decomposes the outputs into limbs.

func UnwrapHintContext added in v0.14.0 

func UnwrapHintContext(nativeMod *big.Int, nativeInputs, nativeOutputs []*big.Int, genericHint Hint) error

UnwrapHintContext unwraps the nativeInputs and nativeOutputs into HintContext for field-specific inputs/outputs and passes it as an argument to the genericHint function. It is expected that the caller has called either Field.NewHintGeneric or NewVarGenericHint which performs standard wrapping.

We also provide backwards compatibility with other hint calling and unwrapping functions. This means that when calling these functions, the native inputs can be unwrapped using this method. Otherwise, the caller can also call the backwards-compatible methods directly:

func UnwrapHintWithNativeInput added in v0.10.0 

func UnwrapHintWithNativeInput(nativeInputs, nativeOutputs []*big.Int, nonnativeHint solver.Hint) error

UnwrapHintWithNativeInput unwraps the native inputs into native inputs. Then it calls nonnativeHint function with native inputs. After nonnativeHint returns, it decomposes the outputs into limbs.

func UnwrapHintWithNativeOutput added in v0.10.0 

func UnwrapHintWithNativeOutput(nativeInputs, nativeOutputs []*big.Int, nonnativeHint solver.Hint) error

UnwrapHintWithNativeOutput unwraps the native inputs into nonnative inputs. Then it calls nonnativeHint function with nonnative inputs. After nonnativeHint returns, it returns native outputs as-is.

Types

type BLS12377Fp 

type BLS12377Fp = emparams.BLS12377Fp

type BLS12381Fp added in v0.9.0 

type BLS12381Fp = emparams.BLS12381Fp

type BLS12381Fr added in v0.9.0 

type BLS12381Fr = emparams.BLS12381Fr

type BN254Fp 

type BN254Fp = emparams.BN254Fp

type BN254Fr 

type BN254Fr = emparams.BN254Fr

type BW6761Fp added in v0.10.0 

type BW6761Fp = emparams.BW6761Fp

type BW6761Fr added in v0.10.0 

type BW6761Fr = emparams.BW6761Fr

type BabyBear added in v0.12.0 

type BabyBear = emparams.BabyBear

type DynamicFieldParams added in v0.13.0 

type DynamicFieldParams interface {
	FieldParams

	NbLimbsDynamic(field *big.Int) uint
	BitsPerLimbDynamic(field *big.Int) uint
}

DynamicFieldParams extends the FieldParams interface to allow for limb size and count depending on the native field size. If the field emulation parameters do not implement this interface, then the limb size and count are fixed to the values defined in the FieldParams interface.

The interface allows for optimized emulation in case the native field is large (more than 256 bits) and enables field emulation when the native field is small (less than 128 bits).

All defined parameters in the emparams package implement this interface.

type Element 

type Element[T FieldParams] struct {
	// Limbs is the decomposition of the integer value into limbs in the native
	// field. To enforce that the limbs are of expected width, use Pack...
	// methods on the Field. Uses little-endian (least significant limb first)
	// encoding.
	Limbs []frontend.Variable
	// contains filtered or unexported fields
}

Element defines an element in the ring of integers modulo n. The integer value of the element is split into limbs of nbBits lengths and represented as a slice of limbs. The type parameter defines the field this element belongs to.

func ValueOf 

func ValueOf[T FieldParams](constant interface{}) Element[T]

ValueOf returns an Element[T] from a constant value. This method is used for witness assignment. For in-circuit constant assignment use the Field.NewElement method.

The input is converted into limbs according to the parameters of the field and returned as a new Element. Note that it returns the value, not a reference, which is more convenient for witness assignment.

The method is asynchronous and the limb decomposition is done during witness parsing.

func (*Element[T]) Initialize added in v0.13.0 

func (e *Element[T]) Initialize(field *big.Int)

Initialize automatically initializes non-native element during circuit parsing and compilation. It allocates the limbs and sets the element to be automatically range-checked on first use.

The method has a side effect that when a circuit is parsed multiple times, then the subsequent calls to this method will not re-initialize the element. Thus any changes to the non-native element persist.

type Field 

type Field[T FieldParams] struct {
	// contains filtered or unexported fields
}

Field holds the configuration for non-native field operations. The field parameters (modulus, number of limbs) is given by FieldParams type parameter. If [FieldParams.IsPrime] is true, then allows inverse and division operations.

Example

Example of using Field instance. The witness elements must be Element type. 

package main

import (
	"fmt"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/constraint/solver"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
	"github.com/consensys/gnark/std/math/emulated"
)

type ExampleFieldCircuit[T emulated.FieldParams] struct {
	In1 emulated.Element[T]
	In2 emulated.Element[T]
	Res emulated.Element[T]
}

func (c *ExampleFieldCircuit[T]) Define(api frontend.API) error {
	f, err := emulated.NewField[T](api)
	if err != nil {
		return fmt.Errorf("new field: %w", err)
	}
	res := f.Mul(&c.In1, &c.In2) // non-reducing
	res = f.Reduce(res)
	f.AssertIsEqual(res, &c.Res)
	return nil
}

// Example of using [Field] instance. The witness elements must be [Element]
// type.
func main() {
	circuit := ExampleFieldCircuit[emulated.BN254Fp]{}
	witness := ExampleFieldCircuit[emulated.BN254Fp]{
		In1: emulated.ValueOf[emulated.BN254Fp](3),
		In2: emulated.ValueOf[emulated.BN254Fp](5),
		Res: emulated.ValueOf[emulated.BN254Fp](15),
	}
	ccs, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
	if err != nil {
		panic(err)
	}
	witnessData, err := frontend.NewWitness(&witness, ecc.BN254.ScalarField())
	if err != nil {
		panic(err)
	}
	publicWitnessData, err := witnessData.Public()
	if err != nil {
		panic(err)
	}
	pk, vk, err := groth16.Setup(ccs)
	if err != nil {
		panic(err)
	}
	proof, err := groth16.Prove(ccs, pk, witnessData, backend.WithSolverOptions(solver.WithHints(emulated.GetHints()...)))
	if err != nil {
		panic(err)
	}
	err = groth16.Verify(proof, vk, publicWitnessData)
	if err != nil {
		panic(err)
	}
	fmt.Println("done")
}

Output:

done

func NewField 

func NewField[T FieldParams](native frontend.API) (*Field[T], error)

NewField returns an object to be used in-circuit to perform emulated arithmetic over the field defined by type parameter FieldParams. The operations on this type are defined on Element.

func (*Field[T]) Add 

func (f *Field[T]) Add(a, b *Element[T]) *Element[T]

Add computes a+b and returns it. If the result wouldn't fit into Element, then first reduces the inputs (larger first) and tries again. Doesn't mutate inputs.

func (*Field[T]) AssertIsDifferent added in v0.13.0 

func (f *Field[T]) AssertIsDifferent(a, b *Element[T])

AssertIsDifferent asserts that a and b are different.

func (*Field[T]) AssertIsEqual 

func (f *Field[T]) AssertIsEqual(a, b *Element[T])

AssertIsEqual ensures that a is equal to b modulo the modulus.

func (*Field[T]) AssertIsInRange added in v0.9.0 

func (f *Field[T]) AssertIsInRange(a *Element[T])

AssertIsInRange ensures that a is less than the emulated modulus. When we call [Reduce] then we only ensure that the result is width-constrained, but not actually less than the modulus. This means that the actual value may be either x or x + p. For arithmetic it is sufficient, but for binary comparison it is not. For binary comparison the values have both to be below the modulus.

func (*Field[T]) AssertIsLessOrEqual 

func (f *Field[T]) AssertIsLessOrEqual(e, a *Element[T])

AssertIsLessOrEqual ensures that e is less or equal than a. For proper bitwise comparison first reduce the element using Field.ReduceStrict.

func (*Field[T]) Div 

func (f *Field[T]) Div(a, b *Element[T]) *Element[T]

Div computes a/b and returns it. It uses DivHint as a hint function.

func (*Field[T]) Eval added in v0.12.0 

func (f *Field[T]) Eval(at [][]*Element[T], coefs []int) *Element[T]

Eval evaluates the multivariate polynomial. The elements of the inner slices are multiplied together and then summed together with the corresponding coefficient.

NB! This is experimental API. It does not support negative coefficients. It does not check that computing the term wouldn't overflow the field.

For example, for computing the expression x^2 + 2xy + y^2 we would call 

f.Eval([][]*Element[T]{{x,x}, {x,y}, {y,y}}, []int{1, 2, 1})

The method returns the result of the evaluation.

To overcome the problem of not supporting negative coefficients, we can use a constant non-native element -1 as one of the inputs.

func (*Field[T]) Exp added in v0.10.0 

func (f *Field[T]) Exp(base, exp *Element[T]) *Element[T]

Exp computes base^exp modulo the field order. The returned Element has default number of limbs and zero overflow.

func (*Field[T]) FromBits 

func (f *Field[T]) FromBits(bs ...frontend.Variable) *Element[T]

FromBits returns a new Element given the bits is little-endian order.

func (*Field[T]) Inverse 

func (f *Field[T]) Inverse(a *Element[T]) *Element[T]

Inverse compute 1/a and returns it. It uses InverseHint.

func (*Field[T]) IsZero added in v0.9.0 

func (f *Field[T]) IsZero(a *Element[T]) frontend.Variable

IsZero returns a boolean indicating if the element is strictly zero. The method internally reduces the element and asserts that the value is less than the modulus.

func (*Field[T]) Lookup2 

func (f *Field[T]) Lookup2(b0, b1 frontend.Variable, a, b, c, d *Element[T]) *Element[T]

Lookup2 performs two-bit lookup between a, b, c, d based on lookup bits b1 and b2 such that:

  • if b0=0 and b1=0, sets to a,
  • if b0=1 and b1=0, sets to b,
  • if b0=0 and b1=1, sets to c,
  • if b0=1 and b1=1, sets to d.

The number of the limbs and overflow in the result is the maximum of the inputs'. If the inputs are very unbalanced, then reduce the result.

func (*Field[T]) ModAdd added in v0.10.0 

func (f *Field[T]) ModAdd(a, b *Element[T], modulus *Element[T]) *Element[T]

ModAdd computes a+b mod modulus. Instead of taking modulus as a constant parametrized by T, it is passed as an argument. This allows to use a variable modulus in the circuit. Type parameter T should be sufficiently big to fit a, b and modulus. Recommended to use emparams.Mod1e512 or emparams.Mod1e4096.

NB! circuit complexity depends on T rather on the actual length of the modulus.

func (*Field[T]) ModAssertIsEqual added in v0.10.0 

func (f *Field[T]) ModAssertIsEqual(a, b *Element[T], modulus *Element[T])

ModAssertIsEqual asserts equality of a and b mod modulus. Instead of taking modulus as a constant parametrized by T, it is passed as an argument. This allows to use a variable modulus in the circuit. Type parameter T should be sufficiently big to fit a, b and modulus. Recommended to use emparams.Mod1e512 or emparams.Mod1e4096.

NB! circuit complexity depends on T rather on the actual length of the modulus.

func (*Field[T]) ModExp added in v0.10.0 

func (f *Field[T]) ModExp(base, exp, modulus *Element[T]) *Element[T]

ModExp computes base^exp mod modulus. Instead of taking modulus as a constant parametrized by T, it is passed as an argument. This allows to use a variable modulus in the circuit. Type parameter T should be sufficiently big to fit base, exp and modulus. Recommended to use emparams.Mod1e512 or emparams.Mod1e4096.

NB! circuit complexity depends on T rather on the actual length of the modulus.

func (*Field[T]) ModMul added in v0.10.0 

func (f *Field[T]) ModMul(a, b *Element[T], modulus *Element[T]) *Element[T]

ModMul computes a*b mod modulus. Instead of taking modulus as a constant parametrized by T, it is passed as an argument. This allows to use a variable modulus in the circuit. Type parameter T should be sufficiently big to fit a, b and modulus. Recommended to use emparams.Mod1e512 or emparams.Mod1e4096.

NB! circuit complexity depends on T rather on the actual length of the modulus.

func (*Field[T]) Modulus 

func (f *Field[T]) Modulus() *Element[T]

Modulus returns the modulus of the emulated ring as a constant.

func (*Field[T]) Mul 

func (f *Field[T]) Mul(a, b *Element[T]) *Element[T]

Mul computes a*b and reduces it modulo the field order. The returned Element has default number of limbs and zero overflow. If the result wouldn't fit into Element, then locally reduces the inputs first. Doesn't mutate inputs.

For multiplying by a constant, use [Field[T].MulConst] method which is more efficient.

func (*Field[T]) MulConst 

func (f *Field[T]) MulConst(a *Element[T], c *big.Int) *Element[T]

MulConst multiplies a by a constant c and returns it. We assume that the input constant is "small", so that we can compute the product by multiplying all individual limbs with the constant. If it is not small, then use the general [Field[T].Mul] or [Field[T].MulMod] with creating new Element from the constant on-the-fly.

func (*Field[T]) MulMod 

func (f *Field[T]) MulMod(a, b *Element[T]) *Element[T]

MulMod computes a*b and reduces it modulo the field order. The returned Element has default number of limbs and zero overflow.

Equivalent to [Field[T].Mul], kept for backwards compatibility.

func (*Field[T]) MulNoReduce added in v0.10.0 

func (f *Field[T]) MulNoReduce(a, b *Element[T]) *Element[T]

MulNoReduce computes a*b and returns the result without reducing it modulo the field order. The number of limbs of the returned element depends on the number of limbs of the inputs.

func (*Field[T]) Mux added in v0.10.0 

func (f *Field[T]) Mux(sel frontend.Variable, inputs ...*Element[T]) *Element[T]

Mux selects element inputs[sel] and returns it. The number of the limbs and overflow in the result is the maximum of the inputs'. If the inputs are very unbalanced, then reduce the inputs before calling the method. It is most efficient for power of two lengths of the inputs, but works for any number of inputs.

func (*Field[T]) Neg 

func (f *Field[T]) Neg(a *Element[T]) *Element[T]

func (*Field[T]) NewElement 

func (f *Field[T]) NewElement(v interface{}) *Element[T]

NewElement builds a new Element[T] from input v.

  • if v is a Element[T] or *Element[T] it clones it
  • if v is a constant this is equivalent to calling emulated.ValueOf[T]
  • if this methods interprets v as being the limbs (frontend.Variable or []frontend.Variable), it constructs a new Element[T] with v as limbs and constraints the limbs to the parameters of the Field[T].

func (*Field[T]) NewHint added in v0.9.0 

func (f *Field[T]) NewHint(hf solver.Hint, nbOutputs int, inputs ...*Element[T]) ([]*Element[T], error)

NewHint allows to call the emulation hint function hf on inputs, expecting nbOutputs results. This function splits internally the emulated element into limbs and passes these to the hint function. There is UnwrapHint function which performs corresponding recomposition of limbs into integer values (and vice verse for output).

The hint function for this method is defined as: 

func HintFn(mod *big.Int, inputs, outputs []*big.Int) error {
    return emulated.UnwrapHint(inputs, outputs, func(mod *big.Int, inputs, outputs []*big.Int) error { // NB we shadow initial input, output, mod to avoid accidental overwrite!
	    // here all inputs and outputs are modulo nonnative mod. we decompose them automatically
    })}

See the example for full written example.

Example

Example of using hints with emulated elements. 

package main

import (
	"fmt"
	"math/big"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
	"github.com/consensys/gnark/backend"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/constraint/solver"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
	"github.com/consensys/gnark/std/math/emulated"
)

// HintExample is a hint for field emulation which returns the division of the
// first and second input.
func HintExample(nativeMod *big.Int, nativeInputs, nativeOutputs []*big.Int) error {
	// nativeInputs are the limbs of the input non-native elements. We wrap the
	// actual hint function with [emulated.UnwrapHint] to get actual [*big.Int]
	// values of the non-native elements.
	return emulated.UnwrapHint(nativeInputs, nativeOutputs, func(mod *big.Int, inputs, outputs []*big.Int) error {
		// this hint computes the division of first and second input and returns it.
		nominator := inputs[0]
		denominator := inputs[1]
		res := new(big.Int).ModInverse(denominator, mod)
		if res == nil {
			return fmt.Errorf("no modular inverse")
		}
		res.Mul(res, nominator)
		res.Mod(res, mod)
		outputs[0].Set(res)
		return nil
	})
	// when the internal hint function returns, the UnwrapHint function
	// decomposes the non-native value into limbs.
}

type emulationHintCircuit[T emulated.FieldParams] struct {
	Nominator   emulated.Element[T]
	Denominator emulated.Element[T]
	Expected    emulated.Element[T]
}

func (c *emulationHintCircuit[T]) Define(api frontend.API) error {
	field, err := emulated.NewField[T](api)
	if err != nil {
		return err
	}
	res, err := field.NewHint(HintExample, 1, &c.Nominator, &c.Denominator)
	if err != nil {
		return err
	}
	m := field.Mul(res[0], &c.Denominator)
	field.AssertIsEqual(m, &c.Nominator)
	field.AssertIsEqual(res[0], &c.Expected)
	return nil
}

// Example of using hints with emulated elements.
func main() {
	var a, b, c fr.Element
	a.SetRandom()
	b.SetRandom()
	c.Div(&a, &b)

	circuit := emulationHintCircuit[emulated.BN254Fr]{}
	witness := emulationHintCircuit[emulated.BN254Fr]{
		Nominator:   emulated.ValueOf[emulated.BN254Fr](a),
		Denominator: emulated.ValueOf[emulated.BN254Fr](b),
		Expected:    emulated.ValueOf[emulated.BN254Fr](c),
	}
	ccs, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
	if err != nil {
		panic(err)
	}
	witnessData, err := frontend.NewWitness(&witness, ecc.BN254.ScalarField())
	if err != nil {
		panic(err)
	}
	publicWitnessData, err := witnessData.Public()
	if err != nil {
		panic(err)
	}
	pk, vk, err := groth16.Setup(ccs)
	if err != nil {
		panic(err)
	}
	proof, err := groth16.Prove(ccs, pk, witnessData, backend.WithSolverOptions(solver.WithHints(HintExample)))
	if err != nil {
		panic(err)
	}
	err = groth16.Verify(proof, vk, publicWitnessData)
	if err != nil {
		panic(err)
	}
	fmt.Println("done")
}

Output:

done

func (*Field[T]) NewHintGeneric added in v0.14.0 

func (f *Field[T]) NewHintGeneric(hf solver.Hint, nbNativeOutputs, nbEmulatedOutputs int, nativeInputs []frontend.Variable, nonNativeInputs []*Element[T]) ([]frontend.Variable, []*Element[T], error)

NewHintGeneric is a generic hint function which allows to call the hint function with mixed native and emulated inputs and outputs. It wraps everything so that it can be passed without overflowing the native field.

In the hint function, the user should unwrap the inputs and outputs using UnwrapHintContext function.

The hint function hf is expected to be of type solver.Hint, but it should unwrap the inputs and outputs into HintContext type. As an example, the user could define the hint function as follows: 

func MyHintFn(mod *big.Int, inputs, outputs []*big.Int) error {
    return emulated.UnwrapHintContext(mod, inputs, outputs, func(hc emulated.HintContext) error {
         // here we can use hc to access inputs and outputs for the given field modulus
    })
}

func (*Field[T]) NewHintWithNativeInput added in v0.10.0 

func (f *Field[T]) NewHintWithNativeInput(hf solver.Hint, nbOutputs int, inputs ...frontend.Variable) ([]*Element[T], error)

NewHintWithNativeInput allows to call the emulation hint function hf on native inputs, expecting nbOutputs results. This function passes the native inputs to the hint function directly and reconstructs the outputs into non-native elements. There is UnwrapHintWithNativeInput function which performs corresponding recomposition of limbs into integer values (and vice verse for output).

This method is an alternation of frontend.API.NewHint method, which allows to pass native inputs to the hint function and returns nonnative outputs. This is useful when the inputs do not necessarily have to be emulated elements (e.g. indices) and allows to work between different fields.

The hint function for this method is defined as: 

func HintFn(nativeMod *big.Int, nativeInputs, nativeOutputs []*big.Int) error {
    return emulated.UnwrapHintWithNativeInput(nativeInputs, nativeOutputs, func(emulatedMod *big.Int, inputs, outputs []*big.Int) error {
        // in the function we have access to both native and nonnative modulus
    })}

func (*Field[T]) NewHintWithNativeOutput added in v0.10.0 

func (f *Field[T]) NewHintWithNativeOutput(hf solver.Hint, nbOutputs int, inputs ...*Element[T]) ([]frontend.Variable, error)

NewHintWithNativeOutput allows to call the emulation hint function hf on nonnative inputs, expecting nbOutputs results. This function splits internally the emulated element into limbs and passes these to the hint function. There is UnwrapHintWithNativeOutput function which performs corresponding recomposition of limbs into integer values (and vice verse for output).

This method is an alternation of frontend.API.NewHint method, which allows to pass nonnative inputs to the hint function and returns native outputs. This is useful when the outputs do not necessarily have to be emulated elements (e.g. bits) as it skips enforcing range checks on the outputs.

The hint function for this method is defined as: 

func HintFn(nativeMod *big.Int, inputs, outputs []*big.Int) error {
    return emulated.UnwrapHintWithNativeOutput(inputs, outputs, func(emulatedMod *big.Int, inputs, outputs []*big.Int) error {
        // in the function we have access to both native and nonnative modulus
    })}

func (*Field[T]) One 

func (f *Field[T]) One() *Element[T]

One returns one as a constant.

func (*Field[T]) Reduce 

func (f *Field[T]) Reduce(a *Element[T]) *Element[T]

ReduceWidth returns an element reduced by the modulus and constrained to have same length as the modulus. The output element has the same width as the modulus but may up to twice larger than the modulus).

Does not mutate the input.

In cases where the canonical representation of the element is required, use Field.ReduceStrict.

func (*Field[T]) ReduceStrict added in v0.11.0 

func (f *Field[T]) ReduceStrict(a *Element[T]) *Element[T]

ReduceStrict returns an element reduced by the modulus. The output element has the same width as the modulus and is guaranteed to be less than the modulus.

Does not mutate the input.

This method is useful when the canonical representation of the element is required. For example, when the element is used in bitwise operations. This means that the reduction is enforced even when the overflow of the element is 0, but it has not been strictly reduced before.

func (*Field[T]) Select 

func (f *Field[T]) Select(selector frontend.Variable, a, b *Element[T]) *Element[T]

Select sets e to a if selector == 1 and to b otherwise. Sets the number of limbs and overflow of the result to be the maximum of the limb lengths and overflows. If the inputs are strongly unbalanced, then it would better to reduce the result after the operation.

func (*Field[T]) Sqrt added in v0.9.0 

func (f *Field[T]) Sqrt(a *Element[T]) *Element[T]

Sqrt computes square root of a and returns it. It uses SqrtHint.

func (*Field[T]) Sub 

func (f *Field[T]) Sub(a, b *Element[T]) *Element[T]

Sub subtracts b from a and returns it. Reduces locally if wouldn't fit into Element. Doesn't mutate inputs.

func (*Field[T]) Sum added in v0.10.0 

func (f *Field[T]) Sum(inputs ...*Element[T]) *Element[T]

func (*Field[T]) ToBits 

func (f *Field[T]) ToBits(a *Element[T]) []frontend.Variable

ToBits returns the bit representation of the Element in little-endian (LSB first) order. The returned bits are constrained to be 0-1. The number of returned bits is nbLimbs*nbBits+overflow. To obtain the bits of the canonical representation of Element, use method Field.ToBitsCanonical.

func (*Field[T]) ToBitsCanonical added in v0.11.0 

func (f *Field[T]) ToBitsCanonical(a *Element[T]) []frontend.Variable

ToBitsCanonical represents the unique bit representation in the canonical format (less that the modulus).

func (*Field[T]) Zero 

func (f *Field[T]) Zero() *Element[T]

Zero returns zero as a constant.

type FieldParams 

type FieldParams interface {
	NbLimbs() uint     // number of limbs to represent field element
	BitsPerLimb() uint // number of bits per limb. Top limb may contain less than limbSize bits.
	IsPrime() bool     // indicates if the modulus is prime
	Modulus() *big.Int // returns modulus. Do not modify.
}

FieldParams describes the emulated field characteristics. For a list of included built-in emulation params refer to the emparams package. For backwards compatibility, the current package contains the following parameters:

type Goldilocks 

type Goldilocks = emparams.Goldilocks

type Hint added in v0.14.0 

type Hint func(HintContext) error

Hint is a non-native hint function which takes a HintContext as an argument which allows to access inputs and outputs over different fields.

It is not directly passed as an argument to the hint calling methods which expect solver.Hint type. So, the user would have to define the hint function as solver.Hint and then use UnwrapHintContext to obtain the HintContext. It is due to the fact that we use native API hint calling mechanism which expects solver.Hint type.

For example, the user could define the hint function as follows: 

func MyHintFn(mod *big.Int, inputs, outputs []*big.Int) error { // this is [solver.Hint] type
    return emulated.UnwrapHintContext(mod, inputs, outputs, func(hc emulated.HintContext) error { // this is [Hint] type
        // here we can access inputs and outputs for the given field modulus
        // and perform the hint logic.
        // For example, we can access the native inputs and outputs as follows:
        nativeInputs, nativeOutputs := hc.InputsOutputs(mod)
        // and emulated inputs and outputs as follows:
        moduli := hc.Moduli()
        emulatedInputs, emulatedOutputs := hc.InputsOutputs(moduli[1]) // moduli[0] is the native field modulus
        // then we can perform the hint logic using nativeInputs, nativeOutputs,
        // emulatedInputs and emulatedOutputs.
        // Finally, we can assign the outputs using big.Int.Set method:
        for i, output := range nativeOutputs {
            output.Set(someValue) // someValue is the value we want to assign to the output
        }
        for i, output := range emulatedOutputs {
            output.Set(someEmulatedValue) // someEmulatedValue is the value we want to assign to the output
        }
        return nil
    })
}

type HintContext added in v0.14.0 

type HintContext []hintContextField

HintContext contains context for the emulated hint. It allows to access the inputs and outputs for the given field modulus (native and emulated).

func (HintContext) EmulatedModuli added in v0.14.0 

func (hi HintContext) EmulatedModuli() []*big.Int

EmulatedModuli returns all emulated moduli. Currently when calling Field.NewHintGeneric it has length 1 and when calling NewVarGenericHint it has length 2.

func (HintContext) InputsOutputs added in v0.14.0 

func (hi HintContext) InputsOutputs(field *big.Int) (inputs []*big.Int, outputs []*big.Int)

InputsOutputs returns the inputs and outputs for the given field. If there are no inputs for given field, then returns nil.

As we return reference to the inputs and outputs, it is expected that the hint does not modify the inputs and assigns values to the outputs using big.Int.Set method.

To access the native field inputs and outputs, use the HintContext.NativeInputsOutputs method to avoid disambiguation with when emulation is defined over same field as the native field.

func (HintContext) NativeInputsOutputs added in v0.14.0 

func (hi HintContext) NativeInputsOutputs() (inputs []*big.Int, outputs []*big.Int)

NativeInputsOutputs returns the inputs and outputs for the native field.

func (HintContext) NativeModulus added in v0.14.0 

func (hi HintContext) NativeModulus() *big.Int

NativeModulus returns the modulus of the native field.

type KoalaBear added in v0.12.0 

type KoalaBear = emparams.KoalaBear

type P256Fp added in v0.9.0 

type P256Fp = emparams.P256Fp

type P256Fr added in v0.9.0 

type P256Fr = emparams.P256Fr

type P384Fp added in v0.9.0 

type P384Fp = emparams.P384Fp

type P384Fr added in v0.9.0 

type P384Fr = emparams.P384Fr

type STARKCurveFp added in v0.12.0 

type STARKCurveFp = emparams.STARKCurveFp

type STARKCurveFr added in v0.12.0 

type STARKCurveFr = emparams.STARKCurveFr

type Secp256k1Fp 

type Secp256k1Fp = emparams.Secp256k1Fp

type Secp256k1Fr 

type Secp256k1Fr = emparams.Secp256k1Fr

Source Files

View all Source files

Directories

Path Synopsis
Package emparams contains emulation parameters for well known fields.
 Package emparams contains emulation parameters for well known fields.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.