1package plonk
  2
  3import (
  4	"github.com/consensys/gnark/frontend"
  5	gl "github.com/succinctlabs/gnark-plonky2-verifier/goldilocks"
  6	"github.com/succinctlabs/gnark-plonky2-verifier/plonk/gates"
  7	"github.com/succinctlabs/gnark-plonky2-verifier/poseidon"
  8	"github.com/succinctlabs/gnark-plonky2-verifier/types"
  9	"github.com/succinctlabs/gnark-plonky2-verifier/variables"
 10)
 11
 12type PlonkChip struct {
 13	api frontend.API `gnark:"-"`
 14
 15	commonData types.CommonCircuitData `gnark:"-"`
 16
 17	// These are global constant variables that we use in this Chip that we save here.
 18	// This avoids having to recreate them every time we use them.
 19	DEGREE        gl.Variable                   `gnark:"-"`
 20	DEGREE_BITS_F gl.Variable                   `gnark:"-"`
 21	DEGREE_QE     gl.QuadraticExtensionVariable `gnark:"-"`
 22	commonDataKIs []gl.Variable                 `gnark:"-"`
 23
 24	evaluateGatesChip *gates.EvaluateGatesChip
 25}
 26
 27func NewPlonkChip(api frontend.API, commonData types.CommonCircuitData) *PlonkChip {
 28	// Create the gates based on commonData GateIds
 29	createdGates := []gates.Gate{}
 30	for _, gateId := range commonData.GateIds {
 31		createdGates = append(createdGates, gates.GateInstanceFromId(gateId))
 32	}
 33
 34	evaluateGatesChip := gates.NewEvaluateGatesChip(
 35		api,
 36		createdGates,
 37		commonData.NumGateConstraints,
 38		commonData.SelectorsInfo,
 39	)
 40
 41	return &PlonkChip{
 42		api: api,
 43
 44		commonData: commonData,
 45
 46		DEGREE:        gl.NewVariable(1 << commonData.DegreeBits),
 47		DEGREE_BITS_F: gl.NewVariable(commonData.DegreeBits),
 48		DEGREE_QE:     gl.NewVariable(1 << commonData.DegreeBits).ToQuadraticExtension(),
 49		commonDataKIs: gl.Uint64ArrayToVariableArray(commonData.KIs),
 50
 51		evaluateGatesChip: evaluateGatesChip,
 52	}
 53}
 54
 55func (p *PlonkChip) expPowerOf2Extension(x gl.QuadraticExtensionVariable) gl.QuadraticExtensionVariable {
 56	glApi := gl.New(p.api)
 57	for i := uint64(0); i < p.commonData.DegreeBits; i++ {
 58		x = glApi.MulExtension(x, x)
 59	}
 60	return x
 61}
 62
 63func (p *PlonkChip) evalL0(x gl.QuadraticExtensionVariable, xPowN gl.QuadraticExtensionVariable) gl.QuadraticExtensionVariable {
 64	// L_0(x) = (x^n - 1) / (n * (x - 1))
 65	glApi := gl.New(p.api)
 66	evalZeroPoly := glApi.SubExtension(
 67		xPowN,
 68		gl.OneExtension(),
 69	)
 70	denominator := glApi.SubExtension(
 71		glApi.ScalarMulExtension(x, p.DEGREE),
 72		p.DEGREE_QE,
 73	)
 74
 75	quotient, hasQuotient := glApi.DivExtension(
 76		evalZeroPoly,
 77		denominator,
 78	)
 79
 80	p.api.AssertIsEqual(hasQuotient, frontend.Variable(1))
 81
 82	return quotient
 83}
 84
 85func (p *PlonkChip) checkPartialProducts(
 86	numerators []gl.QuadraticExtensionVariable,
 87	denominators []gl.QuadraticExtensionVariable,
 88	challengeNum uint64,
 89	openings variables.OpeningSet,
 90) []gl.QuadraticExtensionVariable {
 91	glApi := gl.New(p.api)
 92	numPartProds := p.commonData.NumPartialProducts
 93	quotDegreeFactor := p.commonData.QuotientDegreeFactor
 94
 95	productAccs := make([]gl.QuadraticExtensionVariable, 0, numPartProds+2)
 96	productAccs = append(productAccs, openings.PlonkZs[challengeNum])
 97	productAccs = append(productAccs, openings.PartialProducts[challengeNum*numPartProds:(challengeNum+1)*numPartProds]...)
 98	productAccs = append(productAccs, openings.PlonkZsNext[challengeNum])
 99
100	partialProductChecks := make([]gl.QuadraticExtensionVariable, 0, numPartProds)
101
102	for i := uint64(0); i <= numPartProds; i += 1 {
103		ppStartIdx := i * quotDegreeFactor
104		numeProduct := numerators[ppStartIdx]
105		denoProduct := denominators[ppStartIdx]
106		for j := uint64(1); j < quotDegreeFactor; j++ {
107			numeProduct = glApi.MulExtension(numeProduct, numerators[ppStartIdx+j])
108			denoProduct = glApi.MulExtension(denoProduct, denominators[ppStartIdx+j])
109		}
110
111		partialProductCheck := glApi.SubExtension(
112			glApi.MulExtension(productAccs[i], numeProduct),
113			glApi.MulExtension(productAccs[i+1], denoProduct),
114		)
115
116		partialProductChecks = append(partialProductChecks, partialProductCheck)
117	}
118	return partialProductChecks
119}
120
121func (p *PlonkChip) evalVanishingPoly(
122	vars gates.EvaluationVars,
123	proofChallenges variables.ProofChallenges,
124	openings variables.OpeningSet,
125	zetaPowN gl.QuadraticExtensionVariable,
126) []gl.QuadraticExtensionVariable {
127	glApi := gl.New(p.api)
128	constraintTerms := p.evaluateGatesChip.EvaluateGateConstraints(vars)
129
130	// Calculate the k[i] * x
131	sIDs := make([]gl.QuadraticExtensionVariable, p.commonData.Config.NumRoutedWires)
132
133	for i := uint64(0); i < p.commonData.Config.NumRoutedWires; i++ {
134		sIDs[i] = glApi.ScalarMulExtension(proofChallenges.PlonkZeta, p.commonDataKIs[i])
135	}
136
137	// Calculate L_0(zeta)
138	l0Zeta := p.evalL0(proofChallenges.PlonkZeta, zetaPowN)
139
140	vanishingZ1Terms := make([]gl.QuadraticExtensionVariable, 0, p.commonData.Config.NumChallenges)
141	vanishingPartialProductsTerms := make([]gl.QuadraticExtensionVariable, 0, p.commonData.Config.NumChallenges*p.commonData.NumPartialProducts)
142	for i := uint64(0); i < p.commonData.Config.NumChallenges; i++ {
143		// L_0(zeta) (Z(zeta) - 1) = 0
144		z1_term := glApi.MulExtension(
145			l0Zeta,
146			glApi.SubExtension(openings.PlonkZs[i], gl.OneExtension()))
147		vanishingZ1Terms = append(vanishingZ1Terms, z1_term)
148
149		numeratorValues := make([]gl.QuadraticExtensionVariable, 0, p.commonData.Config.NumRoutedWires)
150		denominatorValues := make([]gl.QuadraticExtensionVariable, 0, p.commonData.Config.NumRoutedWires)
151		for j := uint64(0); j < p.commonData.Config.NumRoutedWires; j++ {
152			// The numerator is `beta * s_id + wire_value + gamma`, and the denominator is
153			// `beta * s_sigma + wire_value + gamma`.
154			wireValuePlusGamma := glApi.AddExtension(
155				openings.Wires[j],
156				gl.NewQuadraticExtensionVariable(proofChallenges.PlonkGammas[i], gl.Zero()),
157			)
158
159			numerator := glApi.AddExtension(
160				glApi.MulExtension(
161					gl.NewQuadraticExtensionVariable(proofChallenges.PlonkBetas[i], gl.Zero()),
162					sIDs[j],
163				),
164				wireValuePlusGamma,
165			)
166
167			denominator := glApi.AddExtension(
168				glApi.MulExtension(
169					gl.NewQuadraticExtensionVariable(proofChallenges.PlonkBetas[i], gl.Zero()),
170					openings.PlonkSigmas[j],
171				),
172				wireValuePlusGamma,
173			)
174
175			numeratorValues = append(numeratorValues, numerator)
176			denominatorValues = append(denominatorValues, denominator)
177		}
178
179		vanishingPartialProductsTerms = append(
180			vanishingPartialProductsTerms,
181			p.checkPartialProducts(numeratorValues, denominatorValues, i, openings)...,
182		)
183	}
184
185	vanishingTerms := append(vanishingZ1Terms, vanishingPartialProductsTerms...)
186	vanishingTerms = append(vanishingTerms, constraintTerms...)
187
188	reducedValues := make([]gl.QuadraticExtensionVariable, p.commonData.Config.NumChallenges)
189	for i := uint64(0); i < p.commonData.Config.NumChallenges; i++ {
190		reducedValues[i] = gl.ZeroExtension()
191	}
192
193	// reverse iterate the vanishingPartialProductsTerms array
194	for i := len(vanishingTerms) - 1; i >= 0; i-- {
195		for j := uint64(0); j < p.commonData.Config.NumChallenges; j++ {
196			reducedValues[j] = glApi.AddExtension(
197				vanishingTerms[i],
198				glApi.ScalarMulExtension(
199					reducedValues[j],
200					proofChallenges.PlonkAlphas[j],
201				),
202			)
203		}
204	}
205
206	return reducedValues
207}
208
209func (p *PlonkChip) Verify(
210	proofChallenges variables.ProofChallenges,
211	openings variables.OpeningSet,
212	publicInputsHash poseidon.GoldilocksHashOut,
213) {
214	glApi := gl.New(p.api)
215
216	// Calculate zeta^n
217	zetaPowN := p.expPowerOf2Extension(proofChallenges.PlonkZeta)
218
219	localConstants := openings.Constants
220	localWires := openings.Wires
221	vars := gates.NewEvaluationVars(
222		localConstants,
223		localWires,
224		publicInputsHash,
225	)
226
227	vanishingPolysZeta := p.evalVanishingPoly(*vars, proofChallenges, openings, zetaPowN)
228
229	// Calculate Z(H)
230	zHZeta := glApi.SubExtension(zetaPowN, gl.OneExtension())
231
232	// `quotient_polys_zeta` holds `num_challenges * quotient_degree_factor` evaluations.
233	// Each chunk of `quotient_degree_factor` holds the evaluations of `t_0(zeta),...,t_{quotient_degree_factor-1}(zeta)`
234	// where the "real" quotient polynomial is `t(X) = t_0(X) + t_1(X)*X^n + t_2(X)*X^{2n} + ...`.
235	// So to reconstruct `t(zeta)` we can compute `reduce_with_powers(chunk, zeta^n)` for each
236	// `quotient_degree_factor`-sized chunk of the original evaluations.
237	for i := 0; i < len(vanishingPolysZeta); i++ {
238		quotientPolysStartIdx := i * int(p.commonData.QuotientDegreeFactor)
239		quotientPolysEndIdx := quotientPolysStartIdx + int(p.commonData.QuotientDegreeFactor)
240		prod := glApi.MulExtension(
241			zHZeta,
242			glApi.ReduceWithPowers(
243				openings.QuotientPolys[quotientPolysStartIdx:quotientPolysEndIdx],
244				zetaPowN,
245			),
246		)
247
248		glApi.AssertIsEqualExtension(vanishingPolysZeta[i], prod)
249	}
250}