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