1package plonky2_verifier
 2
 3import (
 4	"fmt"
 5	. "gnark-plonky2-verifier/field"
 6)
 7
 8type ExponentiationGate struct {
 9	numPowerBits uint64
10}
11
12func NewExponentiationGate(numPowerBits uint64) *ExponentiationGate {
13	return &ExponentiationGate{
14		numPowerBits: numPowerBits,
15	}
16}
17
18func (g *ExponentiationGate) Id() string {
19	return fmt.Sprintf("ExponentiationGate { num_power_bits: %d }", g.numPowerBits)
20}
21
22func (g *ExponentiationGate) wireBase() uint64 {
23	return 0
24}
25
26// / The `i`th bit of the exponent, in little-endian order.
27func (g *ExponentiationGate) wirePowerBit(i uint64) uint64 {
28	if i >= g.numPowerBits {
29		panic("Invalid power bit index")
30	}
31	return 1 + i
32}
33
34func (g *ExponentiationGate) wireOutput() uint64 {
35	return 1 + g.numPowerBits
36}
37
38func (g *ExponentiationGate) wireIntermediateValue(i uint64) uint64 {
39	if i >= g.numPowerBits {
40		panic("Invalid intermediate value index")
41	}
42	return 2 + g.numPowerBits + i
43}
44
45func (g *ExponentiationGate) EvalUnfiltered(p *PlonkChip, vars EvaluationVars) []QuadraticExtension {
46	base := vars.localWires[g.wireBase()]
47
48	var powerBits []QuadraticExtension
49	for i := uint64(0); i < g.numPowerBits; i++ {
50		powerBits = append(powerBits, vars.localWires[g.wirePowerBit(i)])
51	}
52
53	var intermediateValues []QuadraticExtension
54	for i := uint64(0); i < g.numPowerBits; i++ {
55		intermediateValues = append(intermediateValues, vars.localWires[g.wireIntermediateValue(i)])
56	}
57
58	output := vars.localWires[g.wireOutput()]
59
60	var constraints []QuadraticExtension
61
62	for i := uint64(0); i < g.numPowerBits; i++ {
63		var prevIntermediateValue QuadraticExtension
64		if i == 0 {
65			prevIntermediateValue = p.qeAPI.ONE_QE
66		} else {
67			prevIntermediateValue = p.qeAPI.SquareExtension(intermediateValues[i-1])
68		}
69
70		// powerBits is in LE order, but we accumulate in BE order.
71		curBit := powerBits[g.numPowerBits-i-1]
72
73		// Do a polynomial representation of generaized select (where the selector variable doesn't have to be binary)
74		// if b { x } else { y }
75		// i.e. `bx - (by-y)`.
76		tmp := p.qeAPI.MulExtension(curBit, p.qeAPI.ONE_QE)
77		tmp = p.qeAPI.SubExtension(tmp, p.qeAPI.ONE_QE)
78		mulBy := p.qeAPI.MulExtension(curBit, base)
79		mulBy = p.qeAPI.SubExtension(mulBy, tmp)
80		intermediateValueDiff := p.qeAPI.MulExtension(prevIntermediateValue, mulBy)
81		intermediateValueDiff = p.qeAPI.SubExtension(intermediateValueDiff, intermediateValues[i])
82		constraints = append(constraints, intermediateValueDiff)
83	}
84
85	outputDiff := p.qeAPI.SubExtension(output, intermediateValues[g.numPowerBits-1])
86	constraints = append(constraints, outputDiff)
87
88	return constraints
89}