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 randomAccessGateRegex = regexp.MustCompile("RandomAccessGate { bits: (?P<bits>[0-9]+), num_copies: (?P<numCopies>[0-9]+), num_extra_constants: (?P<numExtraConstants>[0-9]+), _phantom: PhantomData<plonky2_field::goldilocks_field::GoldilocksField> }<D=(?P<base>[0-9]+)>")
 13
 14func deserializeRandomAccessGate(parameters map[string]string) Gate {
 15	// Has the format "RandomAccessGate { bits: 2, num_copies: 13, num_extra_constants: 2, _phantom: PhantomData<plonky2_field::goldilocks_field::GoldilocksField> }<D=2>"
 16	bits, hasBits := parameters["bits"]
 17	numCopies, hasNumCopies := parameters["numCopies"]
 18	numExtraConstants, hasNumExtraConstants := parameters["numExtraConstants"]
 19
 20	if !hasBits || !hasNumCopies || !hasNumExtraConstants {
 21		panic("missing bits, numCopies, numExtraConstants or base in RandomAccessGate")
 22	}
 23
 24	bitsInt, err := strconv.ParseUint(bits, 10, 64)
 25	if err != nil {
 26		panic("invalid bits in RandomAccessGate")
 27	}
 28
 29	numCopiesInt, err := strconv.ParseUint(numCopies, 10, 64)
 30	if err != nil {
 31		panic("invalid numCopies in RandomAccessGate")
 32	}
 33
 34	numExtraConstantsInt, err := strconv.ParseUint(numExtraConstants, 10, 64)
 35	if err != nil {
 36		panic("invalid numExtraConstants in RandomAccessGate")
 37	}
 38
 39	base, hasBase := parameters["base"]
 40	if !hasBase {
 41		panic("Missing field base in RandomAccessGate")
 42	}
 43
 44	baseInt, err := strconv.Atoi(base)
 45	if err != nil {
 46		panic("Invalid base field in RandomAccessGate")
 47	}
 48
 49	if baseInt != gl.D {
 50		panic("Expected base field in RandomAccessGate to equal gl.D")
 51	}
 52
 53	return NewRandomAccessGate(bitsInt, numCopiesInt, numExtraConstantsInt)
 54}
 55
 56type RandomAccessGate struct {
 57	bits              uint64
 58	numCopies         uint64
 59	numExtraConstants uint64
 60}
 61
 62func NewRandomAccessGate(bits uint64, numCopies uint64, numExtraConstants uint64) *RandomAccessGate {
 63	return &RandomAccessGate{
 64		bits:              bits,
 65		numCopies:         numCopies,
 66		numExtraConstants: numExtraConstants,
 67	}
 68}
 69
 70func (g *RandomAccessGate) Id() string {
 71	return fmt.Sprintf("RandomAccessGate { bits: %d, num_copies: %d, num_extra_constants: %d }", g.bits, g.numCopies, g.numExtraConstants)
 72}
 73
 74func (g *RandomAccessGate) vecSize() uint64 {
 75	return 1 << g.bits
 76}
 77
 78func (g *RandomAccessGate) WireAccessIndex(copy uint64) uint64 {
 79	if copy >= g.numCopies {
 80		panic("RandomAccessGate.WireAccessIndex called with copy >= num_copies")
 81	}
 82	return (2 + g.vecSize()) * copy
 83}
 84
 85func (g *RandomAccessGate) WireClaimedElement(copy uint64) uint64 {
 86	if copy >= g.numCopies {
 87		panic("RandomAccessGate.WireClaimedElement called with copy >= num_copies")
 88	}
 89
 90	return (2+g.vecSize())*copy + 1
 91}
 92
 93func (g *RandomAccessGate) WireListItem(i uint64, copy uint64) uint64 {
 94	if i >= g.vecSize() {
 95		panic("RandomAccessGate.WireListItem called with i >= vec_size")
 96	}
 97	if copy >= g.numCopies {
 98		panic("RandomAccessGate.WireListItem called with copy >= num_copies")
 99	}
100
101	return (2+g.vecSize())*copy + 2 + i
102}
103
104func (g *RandomAccessGate) startExtraConstants() uint64 {
105	return (2 + g.vecSize()) * g.numCopies
106}
107
108func (g *RandomAccessGate) wireExtraConstant(i uint64) uint64 {
109	if i >= g.numExtraConstants {
110		panic("RandomAccessGate.wireExtraConstant called with i >= num_extra_constants")
111	}
112
113	return g.startExtraConstants() + i
114}
115
116func (g *RandomAccessGate) NumRoutedWires() uint64 {
117	return g.startExtraConstants() + g.numExtraConstants
118}
119
120func (g *RandomAccessGate) WireBit(i uint64, copy uint64) uint64 {
121	if i >= g.bits {
122		panic("RandomAccessGate.WireBit called with i >= bits")
123	}
124	if copy >= g.numCopies {
125		panic("RandomAccessGate.WireBit called with copy >= num_copies")
126	}
127
128	return g.NumRoutedWires() + copy*g.bits + i
129}
130
131func (g *RandomAccessGate) EvalUnfiltered(
132	api frontend.API,
133	glApi gl.Chip,
134	vars EvaluationVars,
135) []gl.QuadraticExtensionVariable {
136	two := gl.NewVariable(2).ToQuadraticExtension()
137	constraints := []gl.QuadraticExtensionVariable{}
138
139	for copy := uint64(0); copy < g.numCopies; copy++ {
140		accessIndex := vars.localWires[g.WireAccessIndex(copy)]
141		listItems := []gl.QuadraticExtensionVariable{}
142		for i := uint64(0); i < g.vecSize(); i++ {
143			listItems = append(listItems, vars.localWires[g.WireListItem(i, copy)])
144		}
145		claimedElement := vars.localWires[g.WireClaimedElement(copy)]
146		bits := []gl.QuadraticExtensionVariable{}
147		for i := uint64(0); i < g.bits; i++ {
148			bits = append(bits, vars.localWires[g.WireBit(i, copy)])
149		}
150
151		// Assert that each bit wire value is indeed boolean.
152		for _, b := range bits {
153			bSquared := glApi.MulExtension(b, b)
154			constraints = append(constraints, glApi.SubExtension(bSquared, b))
155		}
156
157		// Assert that the binary decomposition was correct.
158		reconstructedIndex := glApi.ReduceWithPowers(bits, two)
159		constraints = append(constraints, glApi.SubExtension(reconstructedIndex, accessIndex))
160
161		for _, b := range bits {
162			listItemsTmp := []gl.QuadraticExtensionVariable{}
163			for i := 0; i < len(listItems); i += 2 {
164				x := listItems[i]
165				y := listItems[i+1]
166
167				// This is computing `if b { x } else { y }`
168				// i.e. `x + b(y - x)`.
169				diff := glApi.SubExtension(y, x)
170				mul := glApi.MulExtension(b, diff)
171				add := glApi.AddExtension(x, mul)
172
173				listItemsTmp = append(listItemsTmp, add)
174			}
175			listItems = listItemsTmp
176		}
177
178		if len(listItems) != 1 {
179			panic("listItems(len) != 1")
180		}
181
182		constraints = append(constraints, glApi.SubExtension(listItems[0], claimedElement))
183	}
184
185	for i := uint64(0); i < g.numExtraConstants; i++ {
186		constraints = append(constraints, glApi.SubExtension(vars.localConstants[i], vars.localWires[g.wireExtraConstant(i)]))
187	}
188
189	return constraints
190}