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/constraint/solver"
 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	solver.RegisterHint(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 := bits.ToBinary(api, x, bits.WithNbDigits(64))
104
105	// Those bits should compose back to x
106	reconstructedX := frontend.Variable(0)
107	c := uint64(1)
108	for i := 0; i < 64; i++ {
109		reconstructedX = api.Add(reconstructedX, api.Mul(bits[i], c))
110		c = c << 1
111		api.AssertIsBoolean(bits[i])
112	}
113	api.AssertIsEqual(x, reconstructedX)
114
115	mostSigBits32Sum := frontend.Variable(0)
116	for i := 32; i < 64; i++ {
117		mostSigBits32Sum = api.Add(mostSigBits32Sum, bits[i])
118	}
119
120	leastSigBits32Sum := frontend.Variable(0)
121	for i := 0; i < 32; i++ {
122		leastSigBits32Sum = api.Add(leastSigBits32Sum, bits[i])
123	}
124
125	// 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
126	// So in that case, we don't need to do any more checks.
127	// If mostSigBits32Sum == 32, then we need to check that x == 2^64 - 2^32 (max GL value)
128	shouldCheck := api.IsZero(api.Sub(mostSigBits32Sum, 32))
129	api.AssertIsEqual(
130		api.Select(
131			shouldCheck,
132			leastSigBits32Sum,
133			frontend.Variable(0),
134		),
135		frontend.Variable(0),
136	)
137}
138
139// Calculates operands[0] * operands[1] + operands[2]
140// This function assumes that all operands are within goldilocks, and will panic otherwise
141// It will ensure that the result is within goldilocks
142func GoldilocksMulAdd(api frontend.API, operand1, operand2, operand3 frontend.Variable) frontend.Variable {
143	result, err := api.Compiler().NewHint(GoldilocksMulAddHint, 2, operand1, operand2, operand3)
144	if err != nil {
145		panic(err)
146	}
147
148	quotient := result[0]
149	remainder := result[1]
150
151	// Verify the calculated value
152	lhs := api.Mul(operand1, operand2)
153	lhs = api.Add(lhs, operand3)
154	rhs := api.Add(api.Mul(quotient, GOLDILOCKS_MODULUS), remainder)
155	api.AssertIsEqual(lhs, rhs)
156
157	GoldilocksRangeCheck(api, quotient)
158	GoldilocksRangeCheck(api, remainder)
159
160	return remainder
161}
162
163func GoldilocksMulAddHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
164	if len(inputs) != 3 {
165		panic("GoldilocksMulAddHint expects 3 input operands")
166	}
167
168	for _, operand := range inputs {
169		if operand.Cmp(GOLDILOCKS_MODULUS) >= 0 {
170			panic(fmt.Sprintf("%s is not in the field", operand.String()))
171		}
172	}
173
174	product := new(big.Int).Mul(inputs[0], inputs[1])
175	sum := new(big.Int).Add(product, inputs[2])
176	quotient := new(big.Int).Div(sum, GOLDILOCKS_MODULUS)
177	remainder := new(big.Int).Rem(sum, GOLDILOCKS_MODULUS)
178
179	results[0] = quotient
180	results[1] = remainder
181
182	return nil
183}