1package gates
  2
  3import (
  4	"fmt"
  5	"regexp"
  6	"strconv"
  7	"strings"
  8
  9	"github.com/consensys/gnark-crypto/field/goldilocks"
 10	"github.com/consensys/gnark/frontend"
 11	"github.com/succinctlabs/gnark-plonky2-verifier/field"
 12)
 13
 14var cosetInterpolationGateRegex = regexp.MustCompile(`CosetInterpolationGate { subgroup_bits: (?P<subgroupBits>[0-9]+), degree: (?P<degree>[0-9]+), barycentric_weights: \[(?P<barycentricWeights>[0-9, ]+)\], _phantom: PhantomData<plonky2_field::goldilocks_field::GoldilocksField> }<D=2>`)
 15
 16func deserializeCosetInterpolationGate(parameters map[string]string) Gate {
 17	// Has the format CosetInterpolationGate { subgroup_bits: 4, degree: 6, barycentric_weights: [17293822565076172801, 18374686475376656385, 18446744069413535745, 281474976645120, 17592186044416, 18446744069414584577, 18446744000695107601, 18446744065119617025, 1152921504338411520, 72057594037927936, 18446744069415632897, 18446462594437939201, 18446726477228539905, 18446744069414584065, 68719476720, 4294967296], _phantom: PhantomData<plonky2_field::goldilocks_field::GoldilocksField> }<D=2>
 18	subgroupBits, hasSubgroupBits := parameters["subgroupBits"]
 19	degree, hasDegree := parameters["degree"]
 20	barycentricWeights, hasBarycentricWeights := parameters["barycentricWeights"]
 21
 22	if !hasSubgroupBits || !hasDegree || !hasBarycentricWeights {
 23		panic("missing subgroupBits, degree or barycentricWeights in CosetInterpolationGate")
 24	}
 25
 26	subgroupBitsInt, err := strconv.ParseUint(subgroupBits, 10, 64)
 27	if err != nil {
 28		panic("invalid subgroupBits in CosetInterpolationGate")
 29	}
 30
 31	degreeInt, err := strconv.ParseUint(degree, 10, 64)
 32	if err != nil {
 33		panic("invalid degree in CosetInterpolationGate")
 34	}
 35
 36	barycentricWeightsStr := strings.Split(barycentricWeights, ",")
 37	barycentricWeightsInt := make([]goldilocks.Element, len(barycentricWeightsStr))
 38	for i, barycentricWeightStr := range barycentricWeightsStr {
 39		barycentricWeightStr = strings.TrimSpace(barycentricWeightStr)
 40		barycentricWeightInt, err := strconv.ParseUint(barycentricWeightStr, 10, 64)
 41		if err != nil {
 42			panic("invalid barycentricWeights in CosetInterpolationGate")
 43		}
 44		barycentricWeightsInt[i].SetUint64(barycentricWeightInt)
 45	}
 46
 47	return NewCosetInterpolationGate(subgroupBitsInt, degreeInt, barycentricWeightsInt)
 48}
 49
 50type CosetInterpolationGate struct {
 51	subgroupBits       uint64
 52	degree             uint64
 53	barycentricWeights []goldilocks.Element
 54}
 55
 56func NewCosetInterpolationGate(subgroupBits uint64, degree uint64, barycentricWeights []goldilocks.Element) *CosetInterpolationGate {
 57	return &CosetInterpolationGate{
 58		subgroupBits:       subgroupBits,
 59		degree:             degree,
 60		barycentricWeights: barycentricWeights,
 61	}
 62}
 63
 64func (g *CosetInterpolationGate) Id() string {
 65
 66	return fmt.Sprintf(
 67		"CosetInterpolationGate { subgroup_bits: %d, degree: %d, barycentric_weights: %s }",
 68		g.subgroupBits,
 69		g.degree,
 70		fmt.Sprint(g.barycentricWeights),
 71	)
 72}
 73
 74func (g *CosetInterpolationGate) numPoints() uint64 {
 75	return 1 << g.subgroupBits
 76}
 77
 78// Wire index of the coset shift.
 79func (g *CosetInterpolationGate) wireShift() uint64 {
 80	return 0
 81}
 82
 83func (g *CosetInterpolationGate) startValues() uint64 {
 84	return 1
 85}
 86
 87// Wire indices of the `i`th interpolant value.
 88func (g *CosetInterpolationGate) wiresValue(i uint64) Range {
 89	if i >= g.numPoints() {
 90		panic("Invalid point index")
 91	}
 92	start := g.startValues() + i*field.D
 93	return Range{start, start + field.D}
 94}
 95
 96func (g *CosetInterpolationGate) startEvaluationPoint() uint64 {
 97	return g.startValues() + g.numPoints()*field.D
 98}
 99
100// Wire indices of the point to evaluate the interpolant at.
101func (g *CosetInterpolationGate) wiresEvaluationPoint() Range {
102	start := g.startEvaluationPoint()
103	return Range{start, start + field.D}
104}
105
106func (g *CosetInterpolationGate) startEvaluationValue() uint64 {
107	return g.startEvaluationPoint() + field.D
108}
109
110// Wire indices of the interpolated value.
111func (g *CosetInterpolationGate) wiresEvaluationValue() Range {
112	start := g.startEvaluationValue()
113	return Range{start, start + field.D}
114}
115
116func (g *CosetInterpolationGate) startIntermediates() uint64 {
117	return g.startEvaluationValue() + field.D
118}
119
120func (g *CosetInterpolationGate) numIntermediates() uint64 {
121	return (g.numPoints() - 2) / (g.degree - 1)
122}
123
124// The wires corresponding to the i'th intermediate evaluation.
125func (g *CosetInterpolationGate) wiresIntermediateEval(i uint64) Range {
126	if i >= g.numIntermediates() {
127		panic("Invalid intermediate index")
128	}
129	start := g.startIntermediates() + field.D*i
130	return Range{start, start + field.D}
131}
132
133// The wires corresponding to the i'th intermediate product.
134func (g *CosetInterpolationGate) wiresIntermediateProd(i uint64) Range {
135	if i >= g.numIntermediates() {
136		panic("Invalid intermediate index")
137	}
138	start := g.startIntermediates() + field.D*(g.numIntermediates()+i)
139	return Range{start, start + field.D}
140}
141
142// Wire indices of the shifted point to evaluate the interpolant at.
143func (g *CosetInterpolationGate) wiresShiftedEvaluationPoint() Range {
144	start := g.startIntermediates() + field.D*2*g.numIntermediates()
145	return Range{start, start + field.D}
146}
147
148func (g *CosetInterpolationGate) EvalUnfiltered(api frontend.API, qeAPI *field.QuadraticExtensionAPI, vars EvaluationVars) []field.QuadraticExtension {
149	constraints := []field.QuadraticExtension{}
150
151	shift := vars.localWires[g.wireShift()]
152	evaluationPoint := vars.GetLocalExtAlgebra(g.wiresEvaluationPoint())
153	shiftedEvaluationPoint := vars.GetLocalExtAlgebra(g.wiresShiftedEvaluationPoint())
154
155	negShift := qeAPI.ScalarMulExtension(shift, field.NEG_ONE_F)
156
157	tmp := qeAPI.ScalarMulExtensionAlgebra(negShift, shiftedEvaluationPoint)
158	tmp = qeAPI.AddExtensionAlgebra(tmp, evaluationPoint)
159
160	for i := 0; i < field.D; i++ {
161		constraints = append(constraints, tmp[i])
162	}
163
164	domain := field.TwoAdicSubgroup(g.subgroupBits)
165	values := []field.QEAlgebra{}
166	for i := uint64(0); i < g.numPoints(); i++ {
167		values = append(values, vars.GetLocalExtAlgebra(g.wiresValue(i)))
168	}
169	weights := g.barycentricWeights
170
171	initialEval := qeAPI.ZERO_QE_ALGEBRA
172	initialProd := field.QEAlgebra{qeAPI.ONE_QE, qeAPI.ZERO_QE}
173	computedEval, computedProd := qeAPI.PartialInterpolateExtAlgebra(
174		domain[:g.degree],
175		values[:g.degree],
176		weights[:g.degree],
177		shiftedEvaluationPoint,
178		initialEval,
179		initialProd,
180	)
181
182	for i := uint64(0); i < g.numIntermediates(); i++ {
183		intermediateEval := vars.GetLocalExtAlgebra(g.wiresIntermediateEval(i))
184		intermediateProd := vars.GetLocalExtAlgebra(g.wiresIntermediateProd(i))
185
186		evalDiff := qeAPI.SubExtensionAlgebra(intermediateEval, computedEval)
187		for j := 0; j < field.D; j++ {
188			constraints = append(constraints, evalDiff[j])
189		}
190
191		prodDiff := qeAPI.SubExtensionAlgebra(intermediateProd, computedProd)
192		for j := 0; j < field.D; j++ {
193			constraints = append(constraints, prodDiff[j])
194		}
195
196		startIndex := 1 + (g.degree-1)*(i+1)
197		endIndex := startIndex + g.degree - 1
198		computedEval, computedProd = qeAPI.PartialInterpolateExtAlgebra(
199			domain[startIndex:endIndex],
200			values[startIndex:endIndex],
201			weights[startIndex:endIndex],
202			shiftedEvaluationPoint,
203			intermediateEval,
204			intermediateProd,
205		)
206	}
207
208	evaluationValue := vars.GetLocalExtAlgebra(g.wiresEvaluationValue())
209	evalDiff := qeAPI.SubExtensionAlgebra(evaluationValue, computedEval)
210	for j := 0; j < field.D; j++ {
211		constraints = append(constraints, evalDiff[j])
212	}
213
214	return constraints
215}