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	return glApi.DivExtension(
 75		evalZeroPoly,
 76		denominator,
 77	)
 78}
 79
 80func (p *PlonkChip) checkPartialProducts(
 81	numerators []gl.QuadraticExtensionVariable,
 82	denominators []gl.QuadraticExtensionVariable,
 83	challengeNum uint64,
 84	openings variables.OpeningSet,
 85) []gl.QuadraticExtensionVariable {
 86	glApi := gl.New(p.api)
 87	numPartProds := p.commonData.NumPartialProducts
 88	quotDegreeFactor := p.commonData.QuotientDegreeFactor
 89
 90	productAccs := make([]gl.QuadraticExtensionVariable, 0, numPartProds+2)
 91	productAccs = append(productAccs, openings.PlonkZs[challengeNum])
 92	productAccs = append(productAccs, openings.PartialProducts[challengeNum*numPartProds:(challengeNum+1)*numPartProds]...)
 93	productAccs = append(productAccs, openings.PlonkZsNext[challengeNum])
 94
 95	partialProductChecks := make([]gl.QuadraticExtensionVariable, 0, numPartProds)
 96
 97	for i := uint64(0); i <= numPartProds; i += 1 {
 98		ppStartIdx := i * quotDegreeFactor
 99		numeProduct := numerators[ppStartIdx]
100		denoProduct := denominators[ppStartIdx]
101		for j := uint64(1); j < quotDegreeFactor; j++ {
102			numeProduct = glApi.MulExtension(numeProduct, numerators[ppStartIdx+j])
103			denoProduct = glApi.MulExtension(denoProduct, denominators[ppStartIdx+j])
104		}
105
106		partialProductCheck := glApi.SubExtension(
107			glApi.MulExtension(productAccs[i], numeProduct),
108			glApi.MulExtension(productAccs[i+1], denoProduct),
109		)
110
111		partialProductChecks = append(partialProductChecks, partialProductCheck)
112	}
113	return partialProductChecks
114}
115
116func (p *PlonkChip) evalVanishingPoly(
117	vars gates.EvaluationVars,
118	proofChallenges variables.ProofChallenges,
119	openings variables.OpeningSet,
120	zetaPowN gl.QuadraticExtensionVariable,
121) []gl.QuadraticExtensionVariable {
122	glApi := gl.New(p.api)
123	constraintTerms := p.evaluateGatesChip.EvaluateGateConstraints(vars)
124
125	// Calculate the k[i] * x
126	sIDs := make([]gl.QuadraticExtensionVariable, p.commonData.Config.NumRoutedWires)
127
128	for i := uint64(0); i < p.commonData.Config.NumRoutedWires; i++ {
129		sIDs[i] = glApi.ScalarMulExtension(proofChallenges.PlonkZeta, p.commonDataKIs[i])
130	}
131
132	// Calculate L_0(zeta)
133	l0Zeta := p.evalL0(proofChallenges.PlonkZeta, zetaPowN)
134
135	vanishingZ1Terms := make([]gl.QuadraticExtensionVariable, 0, p.commonData.Config.NumChallenges)
136	vanishingPartialProductsTerms := make([]gl.QuadraticExtensionVariable, 0, p.commonData.Config.NumChallenges*p.commonData.NumPartialProducts)
137	for i := uint64(0); i < p.commonData.Config.NumChallenges; i++ {
138		// L_0(zeta) (Z(zeta) - 1) = 0
139		z1_term := glApi.MulExtension(
140			l0Zeta,
141			glApi.SubExtension(openings.PlonkZs[i], gl.OneExtension()))
142		vanishingZ1Terms = append(vanishingZ1Terms, z1_term)
143
144		numeratorValues := make([]gl.QuadraticExtensionVariable, 0, p.commonData.Config.NumRoutedWires)
145		denominatorValues := make([]gl.QuadraticExtensionVariable, 0, p.commonData.Config.NumRoutedWires)
146		for j := uint64(0); j < p.commonData.Config.NumRoutedWires; j++ {
147			// The numerator is `beta * s_id + wire_value + gamma`, and the denominator is
148			// `beta * s_sigma + wire_value + gamma`.
149			wireValuePlusGamma := glApi.AddExtension(
150				openings.Wires[j],
151				gl.NewQuadraticExtensionVariable(proofChallenges.PlonkGammas[i], gl.Zero()),
152			)
153
154			numerator := glApi.AddExtension(
155				glApi.MulExtension(
156					gl.NewQuadraticExtensionVariable(proofChallenges.PlonkBetas[i], gl.Zero()),
157					sIDs[j],
158				),
159				wireValuePlusGamma,
160			)
161
162			denominator := glApi.AddExtension(
163				glApi.MulExtension(
164					gl.NewQuadraticExtensionVariable(proofChallenges.PlonkBetas[i], gl.Zero()),
165					openings.PlonkSigmas[j],
166				),
167				wireValuePlusGamma,
168			)
169
170			numeratorValues = append(numeratorValues, numerator)
171			denominatorValues = append(denominatorValues, denominator)
172		}
173
174		vanishingPartialProductsTerms = append(
175			vanishingPartialProductsTerms,
176			p.checkPartialProducts(numeratorValues, denominatorValues, i, openings)...,
177		)
178	}
179
180	vanishingTerms := append(vanishingZ1Terms, vanishingPartialProductsTerms...)
181	vanishingTerms = append(vanishingTerms, constraintTerms...)
182
183	reducedValues := make([]gl.QuadraticExtensionVariable, p.commonData.Config.NumChallenges)
184	for i := uint64(0); i < p.commonData.Config.NumChallenges; i++ {
185		reducedValues[i] = gl.ZeroExtension()
186	}
187
188	// reverse iterate the vanishingPartialProductsTerms array
189	for i := len(vanishingTerms) - 1; i >= 0; i-- {
190		for j := uint64(0); j < p.commonData.Config.NumChallenges; j++ {
191			reducedValues[j] = glApi.AddExtension(
192				vanishingTerms[i],
193				glApi.ScalarMulExtension(
194					reducedValues[j],
195					proofChallenges.PlonkAlphas[j],
196				),
197			)
198		}
199	}
200
201	return reducedValues
202}
203
204func (p *PlonkChip) Verify(
205	proofChallenges variables.ProofChallenges,
206	openings variables.OpeningSet,
207	publicInputsHash poseidon.GoldilocksHashOut,
208) {
209	glApi := gl.New(p.api)
210
211	// Calculate zeta^n
212	zetaPowN := p.expPowerOf2Extension(proofChallenges.PlonkZeta)
213
214	localConstants := openings.Constants
215	localWires := openings.Wires
216	vars := gates.NewEvaluationVars(
217		localConstants,
218		localWires,
219		publicInputsHash,
220	)
221
222	vanishingPolysZeta := p.evalVanishingPoly(*vars, proofChallenges, openings, zetaPowN)
223
224	// Calculate Z(H)
225	zHZeta := glApi.SubExtension(zetaPowN, gl.OneExtension())
226
227	// `quotient_polys_zeta` holds `num_challenges * quotient_degree_factor` evaluations.
228	// Each chunk of `quotient_degree_factor` holds the evaluations of `t_0(zeta),...,t_{quotient_degree_factor-1}(zeta)`
229	// where the "real" quotient polynomial is `t(X) = t_0(X) + t_1(X)*X^n + t_2(X)*X^{2n} + ...`.
230	// So to reconstruct `t(zeta)` we can compute `reduce_with_powers(chunk, zeta^n)` for each
231	// `quotient_degree_factor`-sized chunk of the original evaluations.
232	for i := 0; i < len(vanishingPolysZeta); i++ {
233		quotientPolysStartIdx := i * int(p.commonData.QuotientDegreeFactor)
234		quotientPolysEndIdx := quotientPolysStartIdx + int(p.commonData.QuotientDegreeFactor)
235		prod := glApi.MulExtension(
236			zHZeta,
237			glApi.ReduceWithPowers(
238				openings.QuotientPolys[quotientPolysStartIdx:quotientPolysEndIdx],
239				zetaPowN,
240			),
241		)
242
243		glApi.AssertIsEqualExtension(vanishingPolysZeta[i], prod)
244	}
245}