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