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