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