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