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	gl "github.com/succinctlabs/gnark-plonky2-verifier/goldilocks"
 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	if degreeInt < 2 {
 36		panic("degree must be at least 2 in CosetInterpolationGate")
 37	}
 38
 39	barycentricWeightsStr := strings.Split(barycentricWeights, ",")
 40	barycentricWeightsInt := make([]goldilocks.Element, len(barycentricWeightsStr))
 41	for i, barycentricWeightStr := range barycentricWeightsStr {
 42		barycentricWeightStr = strings.TrimSpace(barycentricWeightStr)
 43		barycentricWeightInt, err := strconv.ParseUint(barycentricWeightStr, 10, 64)
 44		if err != nil {
 45			panic("invalid barycentricWeights in CosetInterpolationGate")
 46		}
 47		barycentricWeightsInt[i].SetUint64(barycentricWeightInt)
 48	}
 49
 50	return NewCosetInterpolationGate(subgroupBitsInt, degreeInt, barycentricWeightsInt)
 51}
 52
 53type CosetInterpolationGate struct {
 54	subgroupBits       uint64
 55	degree             uint64
 56	barycentricWeights []goldilocks.Element
 57}
 58
 59func NewCosetInterpolationGate(subgroupBits uint64, degree uint64, barycentricWeights []goldilocks.Element) *CosetInterpolationGate {
 60	return &CosetInterpolationGate{
 61		subgroupBits:       subgroupBits,
 62		degree:             degree,
 63		barycentricWeights: barycentricWeights,
 64	}
 65}
 66
 67func (g *CosetInterpolationGate) Id() string {
 68
 69	return fmt.Sprintf(
 70		"CosetInterpolationGate { subgroup_bits: %d, degree: %d, barycentric_weights: %s }",
 71		g.subgroupBits,
 72		g.degree,
 73		fmt.Sprint(g.barycentricWeights),
 74	)
 75}
 76
 77func (g *CosetInterpolationGate) numPoints() uint64 {
 78	return 1 << g.subgroupBits
 79}
 80
 81// Wire index of the coset shift.
 82func (g *CosetInterpolationGate) wireShift() uint64 {
 83	return 0
 84}
 85
 86func (g *CosetInterpolationGate) startValues() uint64 {
 87	return 1
 88}
 89
 90// Wire indices of the `i`th interpolant value.
 91func (g *CosetInterpolationGate) wiresValue(i uint64) Range {
 92	if i >= g.numPoints() {
 93		panic("Invalid point index")
 94	}
 95	start := g.startValues() + i*gl.D
 96	return Range{start, start + gl.D}
 97}
 98
 99func (g *CosetInterpolationGate) startEvaluationPoint() uint64 {
100	return g.startValues() + g.numPoints()*gl.D
101}
102
103// Wire indices of the point to evaluate the interpolant at.
104func (g *CosetInterpolationGate) wiresEvaluationPoint() Range {
105	start := g.startEvaluationPoint()
106	return Range{start, start + gl.D}
107}
108
109func (g *CosetInterpolationGate) startEvaluationValue() uint64 {
110	return g.startEvaluationPoint() + gl.D
111}
112
113// Wire indices of the interpolated value.
114func (g *CosetInterpolationGate) wiresEvaluationValue() Range {
115	start := g.startEvaluationValue()
116	return Range{start, start + gl.D}
117}
118
119func (g *CosetInterpolationGate) startIntermediates() uint64 {
120	return g.startEvaluationValue() + gl.D
121}
122
123func (g *CosetInterpolationGate) numIntermediates() uint64 {
124	return (g.numPoints() - 2) / (g.degree - 1)
125}
126
127// The wires corresponding to the i'th intermediate evaluation.
128func (g *CosetInterpolationGate) wiresIntermediateEval(i uint64) Range {
129	if i >= g.numIntermediates() {
130		panic("Invalid intermediate index")
131	}
132	start := g.startIntermediates() + gl.D*i
133	return Range{start, start + gl.D}
134}
135
136// The wires corresponding to the i'th intermediate product.
137func (g *CosetInterpolationGate) wiresIntermediateProd(i uint64) Range {
138	if i >= g.numIntermediates() {
139		panic("Invalid intermediate index")
140	}
141	start := g.startIntermediates() + gl.D*(g.numIntermediates()+i)
142	return Range{start, start + gl.D}
143}
144
145// Wire indices of the shifted point to evaluate the interpolant at.
146func (g *CosetInterpolationGate) wiresShiftedEvaluationPoint() Range {
147	start := g.startIntermediates() + gl.D*2*g.numIntermediates()
148	return Range{start, start + gl.D}
149}
150
151func (g *CosetInterpolationGate) EvalUnfiltered(
152	api frontend.API,
153	glApi gl.Chip,
154	vars EvaluationVars,
155) []gl.QuadraticExtensionVariable {
156	constraints := []gl.QuadraticExtensionVariable{}
157
158	shift := vars.localWires[g.wireShift()]
159	evaluationPoint := vars.GetLocalExtAlgebra(g.wiresEvaluationPoint())
160	shiftedEvaluationPoint := vars.GetLocalExtAlgebra(g.wiresShiftedEvaluationPoint())
161
162	negShift := glApi.ScalarMulExtension(shift, gl.NegOne())
163
164	tmp := glApi.ScalarMulExtensionAlgebra(negShift, shiftedEvaluationPoint)
165	tmp = glApi.AddExtensionAlgebra(tmp, evaluationPoint)
166
167	for i := 0; i < gl.D; i++ {
168		constraints = append(constraints, tmp[i])
169	}
170
171	domain := gl.TwoAdicSubgroup(g.subgroupBits)
172	values := []gl.QuadraticExtensionAlgebraVariable{}
173	for i := uint64(0); i < g.numPoints(); i++ {
174		values = append(values, vars.GetLocalExtAlgebra(g.wiresValue(i)))
175	}
176	weights := g.barycentricWeights
177
178	initialEval := gl.ZeroExtensionAlgebra()
179	initialProd := gl.OneExtensionAlgebra()
180	computedEval, computedProd := glApi.PartialInterpolateExtAlgebra(
181		domain[:g.degree],
182		values[:g.degree],
183		weights[:g.degree],
184		shiftedEvaluationPoint,
185		initialEval,
186		initialProd,
187	)
188
189	for i := uint64(0); i < g.numIntermediates(); i++ {
190		intermediateEval := vars.GetLocalExtAlgebra(g.wiresIntermediateEval(i))
191		intermediateProd := vars.GetLocalExtAlgebra(g.wiresIntermediateProd(i))
192
193		evalDiff := glApi.SubExtensionAlgebra(intermediateEval, computedEval)
194		for j := 0; j < gl.D; j++ {
195			constraints = append(constraints, evalDiff[j])
196		}
197
198		prodDiff := glApi.SubExtensionAlgebra(intermediateProd, computedProd)
199		for j := 0; j < gl.D; j++ {
200			constraints = append(constraints, prodDiff[j])
201		}
202
203		startIndex := 1 + (g.degree-1)*(i+1)
204		endIndex := startIndex + g.degree - 1
205		if endIndex > g.numPoints() {
206			endIndex = g.numPoints()
207		}
208
209		computedEval, computedProd = glApi.PartialInterpolateExtAlgebra(
210			domain[startIndex:endIndex],
211			values[startIndex:endIndex],
212			weights[startIndex:endIndex],
213			shiftedEvaluationPoint,
214			intermediateEval,
215			intermediateProd,
216		)
217	}
218
219	evaluationValue := vars.GetLocalExtAlgebra(g.wiresEvaluationValue())
220	evalDiff := glApi.SubExtensionAlgebra(evaluationValue, computedEval)
221	for j := 0; j < gl.D; j++ {
222		constraints = append(constraints, evalDiff[j])
223	}
224
225	return constraints
226}