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