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