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 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	return NewRandomAccessGate(bitsInt, numCopiesInt, numExtraConstantsInt)
 40}
 41
 42type RandomAccessGate struct {
 43	bits              uint64
 44	numCopies         uint64
 45	numExtraConstants uint64
 46}
 47
 48func NewRandomAccessGate(bits uint64, numCopies uint64, numExtraConstants uint64) *RandomAccessGate {
 49	return &RandomAccessGate{
 50		bits:              bits,
 51		numCopies:         numCopies,
 52		numExtraConstants: numExtraConstants,
 53	}
 54}
 55
 56func (g *RandomAccessGate) Id() string {
 57	return fmt.Sprintf("RandomAccessGate { bits: %d, num_copies: %d, num_extra_constants: %d }", g.bits, g.numCopies, g.numExtraConstants)
 58}
 59
 60func (g *RandomAccessGate) vecSize() uint64 {
 61	return 1 << g.bits
 62}
 63
 64func (g *RandomAccessGate) WireAccessIndex(copy uint64) uint64 {
 65	if copy >= g.numCopies {
 66		panic("RandomAccessGate.WireAccessIndex called with copy >= num_copies")
 67	}
 68	return (2 + g.vecSize()) * copy
 69}
 70
 71func (g *RandomAccessGate) WireClaimedElement(copy uint64) uint64 {
 72	if copy >= g.numCopies {
 73		panic("RandomAccessGate.WireClaimedElement called with copy >= num_copies")
 74	}
 75
 76	return (2+g.vecSize())*copy + 1
 77}
 78
 79func (g *RandomAccessGate) WireListItem(i uint64, copy uint64) uint64 {
 80	if i >= g.vecSize() {
 81		panic("RandomAccessGate.WireListItem called with i >= vec_size")
 82	}
 83	if copy >= g.numCopies {
 84		panic("RandomAccessGate.WireListItem called with copy >= num_copies")
 85	}
 86
 87	return (2+g.vecSize())*copy + 2 + i
 88}
 89
 90func (g *RandomAccessGate) startExtraConstants() uint64 {
 91	return (2 + g.vecSize()) * g.numCopies
 92}
 93
 94func (g *RandomAccessGate) wireExtraConstant(i uint64) uint64 {
 95	if i >= g.numExtraConstants {
 96		panic("RandomAccessGate.wireExtraConstant called with i >= num_extra_constants")
 97	}
 98
 99	return g.startExtraConstants() + i
100}
101
102func (g *RandomAccessGate) NumRoutedWires() uint64 {
103	return g.startExtraConstants() + g.numExtraConstants
104}
105
106func (g *RandomAccessGate) WireBit(i uint64, copy uint64) uint64 {
107	if i >= g.bits {
108		panic("RandomAccessGate.WireBit called with i >= bits")
109	}
110	if copy >= g.numCopies {
111		panic("RandomAccessGate.WireBit called with copy >= num_copies")
112	}
113
114	return g.NumRoutedWires() + copy*g.bits + i
115}
116
117func (g *RandomAccessGate) EvalUnfiltered(api frontend.API, qeAPI *field.QuadraticExtensionAPI, vars EvaluationVars) []field.QuadraticExtension {
118	two := field.QuadraticExtension{field.NewFieldElement(2), field.NewFieldElement(0)}
119	constraints := []field.QuadraticExtension{}
120
121	for copy := uint64(0); copy < g.numCopies; copy++ {
122		accessIndex := vars.localWires[g.WireAccessIndex(copy)]
123		listItems := []field.QuadraticExtension{}
124		for i := uint64(0); i < g.vecSize(); i++ {
125			listItems = append(listItems, vars.localWires[g.WireListItem(i, copy)])
126		}
127		claimedElement := vars.localWires[g.WireClaimedElement(copy)]
128		bits := []field.QuadraticExtension{}
129		for i := uint64(0); i < g.bits; i++ {
130			bits = append(bits, vars.localWires[g.WireBit(i, copy)])
131		}
132
133		// Assert that each bit wire value is indeed boolean.
134		for _, b := range bits {
135			bSquared := qeAPI.MulExtension(b, b)
136			constraints = append(constraints, qeAPI.SubExtension(bSquared, b))
137		}
138
139		// Assert that the binary decomposition was correct.
140		reconstructedIndex := qeAPI.ReduceWithPowers(bits, two)
141		constraints = append(constraints, qeAPI.SubExtension(reconstructedIndex, accessIndex))
142
143		for _, b := range bits {
144			listItemsTmp := []field.QuadraticExtension{}
145			for i := 0; i < len(listItems); i += 2 {
146				x := listItems[i]
147				y := listItems[i+1]
148
149				// This is computing `if b { x } else { y }`
150				// i.e. `bx - (by-y)`.
151				mul1 := qeAPI.MulExtension(b, x)
152				sub1 := qeAPI.SubExtension(mul1, x)
153
154				mul2 := qeAPI.MulExtension(b, y)
155				sub2 := qeAPI.SubExtension(mul2, sub1)
156
157				listItemsTmp = append(listItemsTmp, sub2)
158			}
159			listItems = listItemsTmp
160		}
161
162		if len(listItems) != 1 {
163			panic("listItems(len) != 1")
164		}
165
166		constraints = append(constraints, qeAPI.SubExtension(listItems[0], claimedElement))
167	}
168
169	for i := uint64(0); i < g.numExtraConstants; i++ {
170		constraints = append(constraints, qeAPI.SubExtension(vars.localConstants[i], vars.localWires[g.wireExtraConstant(i)]))
171	}
172
173	return constraints
174}