1package gates
  2
  3import (
  4	"fmt"
  5	"regexp"
  6	"strconv"
  7
  8	"github.com/consensys/gnark/frontend"
  9	"github.com/succinctlabs/gnark-plonky2-verifier/field"
 10)
 11
 12var exponentiationGateRegex = regexp.MustCompile("ExponentiationGate { num_power_bits: (?P<numPowerBits>[0-9]+), _phantom: PhantomData<plonky2_field::goldilocks_field::GoldilocksField> }<D=(?P<base>[0-9]+)>")
 13
 14func deserializeExponentiationGate(parameters map[string]string) Gate {
 15	// Has the format "ExponentiationGate { num_power_bits: 67, _phantom: PhantomData<plonky2_field::goldilocks_field::GoldilocksField> }<D=2>"
 16	numPowerBits, hasNumPowerBits := parameters["numPowerBits"]
 17	if !hasNumPowerBits {
 18		panic("Missing field num_power_bits in ExponentiationGate")
 19	}
 20
 21	numPowerBitsInt, err := strconv.Atoi(numPowerBits)
 22	if err != nil {
 23		panic("Invalid num_power_bits field in ExponentiationGate")
 24	}
 25
 26	return NewExponentiationGate(uint64(numPowerBitsInt))
 27}
 28
 29type ExponentiationGate struct {
 30	numPowerBits uint64
 31}
 32
 33func NewExponentiationGate(numPowerBits uint64) *ExponentiationGate {
 34	return &ExponentiationGate{
 35		numPowerBits: numPowerBits,
 36	}
 37}
 38
 39func (g *ExponentiationGate) Id() string {
 40	return fmt.Sprintf("ExponentiationGate { num_power_bits: %d }", g.numPowerBits)
 41}
 42
 43func (g *ExponentiationGate) wireBase() uint64 {
 44	return 0
 45}
 46
 47// / The `i`th bit of the exponent, in little-endian order.
 48func (g *ExponentiationGate) wirePowerBit(i uint64) uint64 {
 49	if i >= g.numPowerBits {
 50		panic("Invalid power bit index")
 51	}
 52	return 1 + i
 53}
 54
 55func (g *ExponentiationGate) wireOutput() uint64 {
 56	return 1 + g.numPowerBits
 57}
 58
 59func (g *ExponentiationGate) wireIntermediateValue(i uint64) uint64 {
 60	if i >= g.numPowerBits {
 61		panic("Invalid intermediate value index")
 62	}
 63	return 2 + g.numPowerBits + i
 64}
 65
 66func (g *ExponentiationGate) EvalUnfiltered(api frontend.API, qeAPI *field.QuadraticExtensionAPI, vars EvaluationVars) []field.QuadraticExtension {
 67	base := vars.localWires[g.wireBase()]
 68
 69	var powerBits []field.QuadraticExtension
 70	for i := uint64(0); i < g.numPowerBits; i++ {
 71		powerBits = append(powerBits, vars.localWires[g.wirePowerBit(i)])
 72	}
 73
 74	var intermediateValues []field.QuadraticExtension
 75	for i := uint64(0); i < g.numPowerBits; i++ {
 76		intermediateValues = append(intermediateValues, vars.localWires[g.wireIntermediateValue(i)])
 77	}
 78
 79	output := vars.localWires[g.wireOutput()]
 80
 81	var constraints []field.QuadraticExtension
 82
 83	for i := uint64(0); i < g.numPowerBits; i++ {
 84		var prevIntermediateValue field.QuadraticExtension
 85		if i == 0 {
 86			prevIntermediateValue = qeAPI.ONE_QE
 87		} else {
 88			prevIntermediateValue = qeAPI.SquareExtension(intermediateValues[i-1])
 89		}
 90
 91		// powerBits is in LE order, but we accumulate in BE order.
 92		curBit := powerBits[g.numPowerBits-i-1]
 93
 94		// Do a polynomial representation of generaized select (where the selector variable doesn't have to be binary)
 95		// if b { x } else { y }
 96		// i.e. `bx - (by-y)`.
 97		tmp := qeAPI.MulExtension(curBit, qeAPI.ONE_QE)
 98		tmp = qeAPI.SubExtension(tmp, qeAPI.ONE_QE)
 99		mulBy := qeAPI.MulExtension(curBit, base)
100		mulBy = qeAPI.SubExtension(mulBy, tmp)
101		intermediateValueDiff := qeAPI.MulExtension(prevIntermediateValue, mulBy)
102		intermediateValueDiff = qeAPI.SubExtension(intermediateValueDiff, intermediateValues[i])
103		constraints = append(constraints, intermediateValueDiff)
104	}
105
106	outputDiff := qeAPI.SubExtension(output, intermediateValues[g.numPowerBits-1])
107	constraints = append(constraints, outputDiff)
108
109	return constraints
110}