1package gates
  2
  3import (
  4	"fmt"
  5	"regexp"
  6	"strconv"
  7
  8	"github.com/consensys/gnark/frontend"
  9	gl "github.com/succinctlabs/gnark-plonky2-verifier/goldilocks"
 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	base, hasBase := parameters["base"]
 27	if !hasBase {
 28		panic("Missing field base in ExponentiationGate")
 29	}
 30
 31	baseInt, err := strconv.Atoi(base)
 32	if err != nil {
 33		panic("Invalid base field in ExponentiationGate")
 34	}
 35
 36	if baseInt != gl.D {
 37		panic("Expected base field in ExponentiationGate to equal gl.D")
 38	}
 39
 40	return NewExponentiationGate(uint64(numPowerBitsInt))
 41}
 42
 43type ExponentiationGate struct {
 44	numPowerBits uint64
 45}
 46
 47func NewExponentiationGate(numPowerBits uint64) *ExponentiationGate {
 48	return &ExponentiationGate{
 49		numPowerBits: numPowerBits,
 50	}
 51}
 52
 53func (g *ExponentiationGate) Id() string {
 54	return fmt.Sprintf("ExponentiationGate { num_power_bits: %d }", g.numPowerBits)
 55}
 56
 57func (g *ExponentiationGate) wireBase() uint64 {
 58	return 0
 59}
 60
 61// / The `i`th bit of the exponent, in little-endian order.
 62func (g *ExponentiationGate) wirePowerBit(i uint64) uint64 {
 63	if i >= g.numPowerBits {
 64		panic("Invalid power bit index")
 65	}
 66	return 1 + i
 67}
 68
 69func (g *ExponentiationGate) wireOutput() uint64 {
 70	return 1 + g.numPowerBits
 71}
 72
 73func (g *ExponentiationGate) wireIntermediateValue(i uint64) uint64 {
 74	if i >= g.numPowerBits {
 75		panic("Invalid intermediate value index")
 76	}
 77	return 2 + g.numPowerBits + i
 78}
 79
 80func (g *ExponentiationGate) EvalUnfiltered(
 81	api frontend.API,
 82	glApi *gl.Chip,
 83	vars EvaluationVars,
 84) []gl.QuadraticExtensionVariable {
 85	base := vars.localWires[g.wireBase()]
 86
 87	var powerBits []gl.QuadraticExtensionVariable
 88	for i := uint64(0); i < g.numPowerBits; i++ {
 89		powerBits = append(powerBits, vars.localWires[g.wirePowerBit(i)])
 90	}
 91
 92	var intermediateValues []gl.QuadraticExtensionVariable
 93	for i := uint64(0); i < g.numPowerBits; i++ {
 94		intermediateValues = append(intermediateValues, vars.localWires[g.wireIntermediateValue(i)])
 95	}
 96
 97	output := vars.localWires[g.wireOutput()]
 98
 99	var constraints []gl.QuadraticExtensionVariable
100
101	for i := uint64(0); i < g.numPowerBits; i++ {
102		var prevIntermediateValue gl.QuadraticExtensionVariable
103		if i == 0 {
104			prevIntermediateValue = gl.OneExtension()
105		} else {
106			prevIntermediateValue = glApi.MulExtension(intermediateValues[i-1], intermediateValues[i-1])
107		}
108
109		// powerBits is in LE order, but we accumulate in BE order.
110		curBit := powerBits[g.numPowerBits-i-1]
111
112		// Do a polynomial representation of generaized select (where the selector variable doesn't have to be binary)
113		// if b { x } else { y }
114		// i.e. `bx - (by-y)`.
115		tmp := glApi.MulExtension(curBit, gl.OneExtension())
116		tmp = glApi.SubExtension(tmp, gl.OneExtension())
117		mulBy := glApi.MulExtension(curBit, base)
118		mulBy = glApi.SubExtension(mulBy, tmp)
119		intermediateValueDiff := glApi.MulExtension(prevIntermediateValue, mulBy)
120		intermediateValueDiff = glApi.SubExtension(intermediateValueDiff, intermediateValues[i])
121		constraints = append(constraints, intermediateValueDiff)
122	}
123
124	outputDiff := glApi.SubExtension(output, intermediateValues[g.numPowerBits-1])
125	constraints = append(constraints, outputDiff)
126
127	return constraints
128}