1// This package implements efficient Golidlocks arithmetic operations within Gnark. We do not use
  2// the emulated field arithmetic API, because it is too slow for our purposes. Instead, we use
  3// an efficient reduction method that leverages the fact that the modulus is a simple
  4// linear combination of powers of two.
  5package goldilocks
  6
  7// In general, methods whose name do not contain `NoReduce` can be used without any extra mental
  8// overhead. These methods act exactly as you would expect a normal field would operate.
  9//
 10// However, if you want to aggressively optimize the number of constraints in your circuit, it can
 11// be very beneficial to use the no reduction methods and keep track of the maximum number of bits
 12// your computation uses.
 13
 14// This implementation is based on the following plonky2 implementation of Goldilocks
 15// Available here: https://github.com/0xPolygonZero/plonky2/blob/main/field/src/goldilocks_field.rs#L70
 16
 17import (
 18	"fmt"
 19	"math"
 20	"math/big"
 21	"os"
 22
 23	"github.com/consensys/gnark-crypto/field/goldilocks"
 24	"github.com/consensys/gnark/constraint/solver"
 25	"github.com/consensys/gnark/frontend"
 26	"github.com/consensys/gnark/std/math/emulated"
 27	"github.com/consensys/gnark/std/rangecheck"
 28)
 29
 30// The multiplicative group generator of the field.
 31var MULTIPLICATIVE_GROUP_GENERATOR goldilocks.Element = goldilocks.NewElement(7)
 32
 33// The two adicity of the field.
 34var TWO_ADICITY uint64 = 32
 35
 36// The power of two generator of the field.
 37var POWER_OF_TWO_GENERATOR goldilocks.Element = goldilocks.NewElement(1753635133440165772)
 38
 39// The modulus of the field.
 40var MODULUS *big.Int = emulated.Goldilocks{}.Modulus()
 41
 42// The number of bits to use for range checks on inner products of field elements.
 43var RANGE_CHECK_NB_BITS int = 140
 44
 45// Registers the hint functions with the solver.
 46func init() {
 47	solver.RegisterHint(MulAddHint)
 48	solver.RegisterHint(ReduceHint)
 49	solver.RegisterHint(InverseHint)
 50	solver.RegisterHint(SplitLimbsHint)
 51}
 52
 53// A type alias used to represent Goldilocks field elements.
 54type Variable struct {
 55	Limb frontend.Variable
 56}
 57
 58// Creates a new Goldilocks field element from an existing variable. Assumes that the element is
 59// already reduced.
 60func NewVariable(x frontend.Variable) Variable {
 61	return Variable{Limb: x}
 62}
 63
 64// The zero element in the Golidlocks field.
 65func Zero() Variable {
 66	return NewVariable(0)
 67}
 68
 69// The one element in the Goldilocks field.
 70func One() Variable {
 71	return NewVariable(1)
 72}
 73
 74// The negative one element in the Goldilocks field.
 75func NegOne() Variable {
 76	return NewVariable(MODULUS.Uint64() - 1)
 77}
 78
 79// The chip used for Goldilocks field operations.
 80type Chip struct {
 81	api          frontend.API
 82	rangeChecker frontend.Rangechecker
 83}
 84
 85// Creates a new Goldilocks Chip.
 86func New(api frontend.API) *Chip {
 87	use_bit_decomp := os.Getenv("USE_BIT_DECOMPOSITION_RANGE_CHECK")
 88
 89	var rangeChecker frontend.Rangechecker
 90
 91	// If USE_BIT_DECOMPOSITION_RANGE_CHECK is not set, then use the std.rangecheck New function
 92	if use_bit_decomp == "" {
 93		rangeChecker = rangecheck.New(api)
 94	} else {
 95		rangeChecker = bitDecompChecker{api: api}
 96	}
 97	return &Chip{api: api, rangeChecker: rangeChecker}
 98}
 99
100// Adds two goldilocks field elements and returns a value within the goldilocks field.
101func (p *Chip) Add(a Variable, b Variable) Variable {
102	return p.MulAdd(a, NewVariable(1), b)
103}
104
105// Adds two goldilocks field elements and returns a value that may not be within the goldilocks field
106// (e.g. the sum is not reduced).
107func (p *Chip) AddNoReduce(a Variable, b Variable) Variable {
108	return NewVariable(p.api.Add(a.Limb, b.Limb))
109}
110
111// Subracts two goldilocks field elements and returns a value within the goldilocks field.
112func (p *Chip) Sub(a Variable, b Variable) Variable {
113	return p.MulAdd(b, NegOne(), a)
114}
115
116// Subracts two goldilocks field elements and returns a value that may not be within the goldilocks field
117// (e.g. the difference is not reduced).
118func (p *Chip) SubNoReduce(a Variable, b Variable) Variable {
119	return NewVariable(p.api.Add(a.Limb, p.api.Mul(b.Limb, NegOne().Limb)))
120}
121
122// Multiplies two goldilocks field elements and returns a value within the goldilocks field.
123func (p *Chip) Mul(a Variable, b Variable) Variable {
124	return p.MulAdd(a, b, Zero())
125}
126
127// Multiplies two goldilocks field elements and returns a value that may not be within the goldilocks field
128// (e.g. the product is not reduced).
129func (p *Chip) MulNoReduce(a Variable, b Variable) Variable {
130	return NewVariable(p.api.Mul(a.Limb, b.Limb))
131}
132
133// Multiplies two field elements and adds a field element (e.g. computes a * b + c).  The returned value
134// will be within the goldilocks field.
135func (p *Chip) MulAdd(a Variable, b Variable, c Variable) Variable {
136	result, err := p.api.Compiler().NewHint(MulAddHint, 2, a.Limb, b.Limb, c.Limb)
137	if err != nil {
138		panic(err)
139	}
140
141	quotient := NewVariable(result[0])
142	remainder := NewVariable(result[1])
143
144	cLimbCopy := p.api.Mul(c.Limb, 1)
145	lhs := p.api.MulAcc(cLimbCopy, a.Limb, b.Limb)
146	rhs := p.api.MulAcc(remainder.Limb, MODULUS, quotient.Limb)
147	p.api.AssertIsEqual(lhs, rhs)
148
149	p.RangeCheck(quotient)
150	p.RangeCheck(remainder)
151	return remainder
152}
153
154// Multiplies two field elements and adds a field element (e.g. computes a * b + c).  The returned value
155// may no be within the goldilocks field (e.g. the result is not reduced).
156func (p *Chip) MulAddNoReduce(a Variable, b Variable, c Variable) Variable {
157	cLimbCopy := p.api.Mul(c.Limb, 1)
158	return NewVariable(p.api.MulAcc(cLimbCopy, a.Limb, b.Limb))
159}
160
161// The hint used to compute MulAdd.
162func MulAddHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
163	if len(inputs) != 3 {
164		panic("MulAddHint expects 3 input operands")
165	}
166
167	for _, operand := range inputs {
168		if operand.Cmp(MODULUS) >= 0 {
169			panic(fmt.Sprintf("%s is not in the field", operand.String()))
170		}
171	}
172
173	product := new(big.Int).Mul(inputs[0], inputs[1])
174	sum := new(big.Int).Add(product, inputs[2])
175	quotient := new(big.Int).Div(sum, MODULUS)
176	remainder := new(big.Int).Rem(sum, MODULUS)
177
178	results[0] = quotient
179	results[1] = remainder
180
181	return nil
182}
183
184// Reduces a field element x such that x % MODULUS = y.
185func (p *Chip) Reduce(x Variable) Variable {
186	// Witness a `quotient` and `remainder` such that:
187	//
188	// 		MODULUS * quotient + remainder = x
189	//
190	// Must check that offset \in [0, MODULUS) and carry \in [0, 2^RANGE_CHECK_NB_BITS) to ensure
191	// that this computation does not overflow. We use 2^RANGE_CHECK_NB_BITS to reduce the cost of the range check
192	//
193	// In other words, we assume that we at most compute a a dot product with dimension at most RANGE_CHECK_NB_BITS - 128.
194	return p.ReduceWithMaxBits(x, uint64(RANGE_CHECK_NB_BITS))
195}
196
197// Reduces a field element x such that x % MODULUS = y.
198func (p *Chip) ReduceWithMaxBits(x Variable, maxNbBits uint64) Variable {
199	// Witness a `quotient` and `remainder` such that:
200	//
201	// 		MODULUS * quotient + remainder = x
202	//
203	// Must check that remainder \in [0, MODULUS) and quotient \in [0, 2^maxNbBits) to ensure that this
204	// computation does not overflow.
205
206	result, err := p.api.Compiler().NewHint(ReduceHint, 2, x.Limb)
207	if err != nil {
208		panic(err)
209	}
210
211	quotient := result[0]
212	p.rangeChecker.Check(quotient, int(maxNbBits))
213
214	remainder := NewVariable(result[1])
215	p.RangeCheck(remainder)
216
217	p.api.AssertIsEqual(x.Limb, p.api.Add(p.api.Mul(quotient, MODULUS), remainder.Limb))
218
219	return remainder
220}
221
222// The hint used to compute Reduce.
223func ReduceHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
224	if len(inputs) != 1 {
225		panic("ReduceHint expects 1 input operand")
226	}
227	input := inputs[0]
228	quotient := new(big.Int).Div(input, MODULUS)
229	remainder := new(big.Int).Rem(input, MODULUS)
230	results[0] = quotient
231	results[1] = remainder
232	return nil
233}
234
235// Computes the inverse of a field element x such that x * x^-1 = 1.
236func (p *Chip) Inverse(x Variable) (Variable, frontend.Variable) {
237	result, err := p.api.Compiler().NewHint(InverseHint, 1, x.Limb)
238	if err != nil {
239		panic(err)
240	}
241
242	inverse := NewVariable(result[0])
243	isZero := p.api.IsZero(x.Limb)
244	hasInv := p.api.Sub(1, isZero)
245	p.RangeCheck(inverse)
246
247	product := p.Mul(inverse, x)
248	productToCheck := p.api.Select(hasInv, product.Limb, frontend.Variable(1))
249	p.api.AssertIsEqual(productToCheck, frontend.Variable(1))
250
251	return inverse, hasInv
252}
253
254// The hint used to compute Inverse.
255func InverseHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
256	if len(inputs) != 1 {
257		panic("InverseHint expects 1 input operand")
258	}
259
260	input := inputs[0]
261	if input.Cmp(MODULUS) == 0 || input.Cmp(MODULUS) == 1 {
262		panic("Input is not in the field")
263	}
264
265	inputGl := goldilocks.NewElement(input.Uint64())
266	resultGl := goldilocks.NewElement(0)
267
268	// Will set resultGL if inputGL == 0
269	resultGl.Inverse(&inputGl)
270
271	result := big.NewInt(0)
272	results[0] = resultGl.BigInt(result)
273
274	return nil
275}
276
277// The hint used to split a GoldilocksVariable into 2 32 bit limbs.
278func SplitLimbsHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
279	if len(inputs) != 1 {
280		panic("SplitLimbsHint expects 1 input operand")
281	}
282
283	// The Goldilocks field element
284	input := inputs[0]
285
286	if input.Cmp(MODULUS) == 0 || input.Cmp(MODULUS) == 1 {
287		return fmt.Errorf("input is not in the field")
288	}
289
290	two_32 := big.NewInt(int64(math.Pow(2, 32)))
291
292	// The most significant bits
293	results[0] = new(big.Int).Quo(input, two_32)
294	// The least significant bits
295	results[1] = new(big.Int).Rem(input, two_32)
296
297	return nil
298}
299
300// Range checks a field element x to be less than the Golidlocks modulus 2 ^ 64 - 2 ^ 32 + 1.
301func (p *Chip) RangeCheck(x Variable) {
302	// The Goldilocks' modulus is 2^64 - 2^32 + 1, which is:
303	//
304	// 		1111111111111111111111111111111100000000000000000000000000000001
305	//
306	// in big endian binary. This function will first verify that x is at most 64 bits wide. Then it
307	// checks that if the bits[0:31] (in big-endian) are all 1, then bits[32:64] are all zero.
308
309	result, err := p.api.Compiler().NewHint(SplitLimbsHint, 2, x.Limb)
310	if err != nil {
311		panic(err)
312	}
313
314	// We check that this is a valid decomposition of the Goldilock's element and range-check each limb.
315	mostSigLimb := result[0]
316	leastSigLimb := result[1]
317	p.api.AssertIsEqual(
318		p.api.Add(
319			p.api.Mul(mostSigLimb, uint64(math.Pow(2, 32))),
320			leastSigLimb,
321		),
322		x.Limb,
323	)
324	p.rangeChecker.Check(mostSigLimb, 32)
325	p.rangeChecker.Check(leastSigLimb, 32)
326
327	// If the most significant bits are all 1, then we need to check that the least significant bits are all zero
328	// in order for element to be less than the Goldilock's modulus.
329	// Otherwise, we don't need to do any checks, since we already know that the element is less than the Goldilocks modulus.
330	shouldCheck := p.api.IsZero(p.api.Sub(mostSigLimb, uint64(math.Pow(2, 32))-1))
331	p.api.AssertIsEqual(
332		p.api.Select(
333			shouldCheck,
334			leastSigLimb,
335			frontend.Variable(0),
336		),
337		frontend.Variable(0),
338	)
339}
340
341// This function will assert that the field element x is less than 2^maxNbBits.
342func (p *Chip) RangeCheckWithMaxBits(x Variable, maxNbBits uint64) {
343	p.rangeChecker.Check(x.Limb, int(maxNbBits))
344}
345
346func (p *Chip) AssertIsEqual(x, y Variable) {
347	p.api.AssertIsEqual(x.Limb, y.Limb)
348}
349
350// Computes the n'th primitive root of unity for the Goldilocks field.
351func PrimitiveRootOfUnity(nLog uint64) goldilocks.Element {
352	if nLog > TWO_ADICITY {
353		panic("nLog is greater than TWO_ADICITY")
354	}
355	res := goldilocks.NewElement(POWER_OF_TWO_GENERATOR.Uint64())
356	for i := 0; i < int(TWO_ADICITY-nLog); i++ {
357		res.Square(&res)
358	}
359	return res
360}
361
362func TwoAdicSubgroup(nLog uint64) []goldilocks.Element {
363	if nLog > TWO_ADICITY {
364		panic("nLog is greater than GOLDILOCKS_TWO_ADICITY")
365	}
366
367	var res []goldilocks.Element
368	rootOfUnity := PrimitiveRootOfUnity(nLog)
369	res = append(res, goldilocks.NewElement(1))
370
371	for i := 0; i < (1<<nLog)-1; i++ {
372		lastElement := res[len(res)-1]
373		res = append(res, *lastElement.Mul(&lastElement, &rootOfUnity))
374	}
375
376	return res
377}