1package field
  2
  3import (
  4	"fmt"
  5	"math/big"
  6
  7	"github.com/consensys/gnark-crypto/ecc"
  8	"github.com/consensys/gnark-crypto/field/goldilocks"
  9	"github.com/consensys/gnark/backend/hint"
 10	"github.com/consensys/gnark/frontend"
 11	"github.com/consensys/gnark/std/math/bits"
 12	"github.com/consensys/gnark/std/math/emulated"
 13)
 14
 15type EmulatedField = emulated.Goldilocks
 16type F = *emulated.Element[EmulatedField]
 17type FieldAPI = *emulated.Field[emulated.Goldilocks]
 18
 19var TEST_CURVE = ecc.BN254
 20
 21func NewFieldAPI(api frontend.API) FieldAPI {
 22	fieldAPI, err := emulated.NewField[EmulatedField](api)
 23	if err != nil {
 24		panic(err)
 25	}
 26	return fieldAPI
 27}
 28
 29func NewFieldConst(x uint64) F {
 30	val := emulated.ValueOf[EmulatedField](x)
 31	return &val
 32}
 33
 34func NewFieldConstFromString(x string) F {
 35	val := emulated.ValueOf[EmulatedField](x)
 36	return &val
 37}
 38
 39var ONE_F = NewFieldConst(1)
 40var ZERO_F = NewFieldConst(0)
 41var NEG_ONE_F = NewFieldConst(EmulatedField{}.Modulus().Uint64() - 1)
 42
 43var GOLDILOCKS_MULTIPLICATIVE_GROUP_GENERATOR = goldilocks.NewElement(7)
 44var GOLDILOCKS_TWO_ADICITY = uint64(32)
 45var GOLDILOCKS_POWER_OF_TWO_GENERATOR = goldilocks.NewElement(1753635133440165772)
 46var GOLDILOCKS_MODULUS = EmulatedField{}.Modulus()
 47
 48func GoldilocksPrimitiveRootOfUnity(nLog uint64) goldilocks.Element {
 49	if nLog > GOLDILOCKS_TWO_ADICITY {
 50		panic("nLog is greater than GOLDILOCKS_TWO_ADICITY")
 51	}
 52
 53	res := goldilocks.NewElement(GOLDILOCKS_POWER_OF_TWO_GENERATOR.Uint64())
 54	for i := 0; i < int(GOLDILOCKS_TWO_ADICITY-nLog); i++ {
 55		res.Square(&res)
 56	}
 57
 58	return res
 59}
 60
 61func TwoAdicSubgroup(nLog uint64) []goldilocks.Element {
 62	if nLog > GOLDILOCKS_TWO_ADICITY {
 63		panic("nLog is greater than GOLDILOCKS_TWO_ADICITY")
 64	}
 65
 66	var res []goldilocks.Element
 67	rootOfUnity := GoldilocksPrimitiveRootOfUnity(nLog)
 68	res = append(res, goldilocks.NewElement(1))
 69
 70	for i := 0; i < (1 << nLog); i++ {
 71		lastElement := res[len(res)-1]
 72		res = append(res, *lastElement.Mul(&lastElement, &rootOfUnity))
 73	}
 74
 75	return res
 76}
 77
 78func IsZero(api frontend.API, fieldAPI *emulated.Field[emulated.Goldilocks], x F) frontend.Variable {
 79	reduced := fieldAPI.Reduce(x)
 80	limbs := reduced.Limbs
 81
 82	isZero := api.IsZero(limbs[0])
 83	for i := 1; i < len(limbs); i++ {
 84		isZero = api.Mul(isZero, api.IsZero(limbs[i]))
 85	}
 86
 87	return isZero
 88
 89}
 90
 91func init() {
 92	// register hints
 93	hint.Register(GoldilocksMulAddHint)
 94}
 95
 96func GoldilocksRangeCheck(api frontend.API, x frontend.Variable) {
 97	// Goldilocks' modulus is 2^64 - 2^32 + 1,
 98	// which is "1111111111111111111111111111111100000000000000000000000000000001' in big endian binary
 99	// This function will first verify that x is at most 64 bits wide.
100	// Then it checks that if the bits[0:31] (in big-endian) are all 1, then bits[32:64] are all zero
101
102	// First decompose x into 64 bits.  The bits will be in little-endian order.
103	bits, err := api.Compiler().NewHint(bits.NBits, 64, x)
104	if err != nil {
105		panic(err)
106	}
107
108	// Those bits should compose back to x
109	reconstructedX := frontend.Variable(0)
110	c := uint64(1)
111	for i := 0; i < 64; i++ {
112		reconstructedX = api.Add(reconstructedX, api.Mul(bits[i], c))
113		c = c << 1
114		api.AssertIsBoolean(bits[i])
115	}
116	api.AssertIsEqual(x, reconstructedX)
117
118	mostSigBits32Sum := frontend.Variable(0)
119	for i := 32; i < 64; i++ {
120		mostSigBits32Sum = api.Add(mostSigBits32Sum, bits[i])
121	}
122
123	leastSigBits32Sum := frontend.Variable(0)
124	for i := 0; i < 32; i++ {
125		leastSigBits32Sum = api.Add(leastSigBits32Sum, bits[i])
126	}
127
128	// If mostSigBits32Sum < 32, then we know that x < (2^63 + ... + 2^32 + 0 * 2^31 + ... + 0 * 2^0), which equals to 2^64 - 2^32
129	// So in that case, we don't need to do any more checks.
130	// If mostSigBits32Sum == 32, then we need to check that x == 2^64 - 2^32 (max GL value)
131	shouldCheck := api.IsZero(api.Sub(mostSigBits32Sum, 32))
132	api.AssertIsEqual(
133		api.Select(
134			shouldCheck,
135			leastSigBits32Sum,
136			frontend.Variable(0),
137		),
138		frontend.Variable(0),
139	)
140}
141
142// Calculates operands[0] * operands[1] + operands[2]
143// This function assumes that all operands are within goldilocks, and will panic otherwise
144// It will ensure that the result is within goldilocks
145func GoldilocksMulAdd(api frontend.API, operand1, operand2, operand3 frontend.Variable) frontend.Variable {
146	result, err := api.Compiler().NewHint(GoldilocksMulAddHint, 2, operand1, operand2, operand3)
147	if err != nil {
148		panic(err)
149	}
150
151	quotient := result[0]
152	remainder := result[1]
153
154	// Verify the calculated value
155	lhs := api.Mul(operand1, operand2)
156	lhs = api.Add(lhs, operand3)
157	rhs := api.Add(api.Mul(quotient, GOLDILOCKS_MODULUS), remainder)
158	api.AssertIsEqual(lhs, rhs)
159
160	GoldilocksRangeCheck(api, quotient)
161	GoldilocksRangeCheck(api, remainder)
162
163	return remainder
164}
165
166func GoldilocksMulAddHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
167	if len(inputs) != 3 {
168		return fmt.Errorf("GoldilocksMulAddHint expects 3 input operands")
169	}
170
171	for _, operand := range inputs {
172		if operand.Cmp(GOLDILOCKS_MODULUS) >= 0 {
173			return fmt.Errorf("%s is not in the field", operand.String())
174		}
175	}
176
177	product := new(big.Int).Mul(inputs[0], inputs[1])
178	sum := new(big.Int).Add(product, inputs[2])
179	quotient := new(big.Int).Div(sum, GOLDILOCKS_MODULUS)
180	remainder := new(big.Int).Rem(sum, GOLDILOCKS_MODULUS)
181
182	results[0] = quotient
183	results[1] = remainder
184
185	return nil
186}
187
188func GoldilocksReduce(api frontend.API, x frontend.Variable) frontend.Variable {
189	// Use gnark's emulated field library.
190	fieldAPI := NewFieldAPI(api)
191	element := fieldAPI.NewElement(x)
192	return fieldAPI.Reduce(element).Limbs[0]
193}