1package plonky2_verifier
  2
  3import (
  4	"fmt"
  5	. "gnark-plonky2-verifier/field"
  6)
  7
  8type RandomAccessGate struct {
  9	bits              uint64
 10	numCopies         uint64
 11	numExtraConstants uint64
 12}
 13
 14func NewRandomAccessGate(bits uint64, numCopies uint64, numExtraConstants uint64) *RandomAccessGate {
 15	return &RandomAccessGate{
 16		bits:              bits,
 17		numCopies:         numCopies,
 18		numExtraConstants: numExtraConstants,
 19	}
 20}
 21
 22func (g *RandomAccessGate) Id() string {
 23	return fmt.Sprintf("RandomAccessGate { bits: %d, num_copies: %d, num_extra_constants: %d }", g.bits, g.numCopies, g.numExtraConstants)
 24}
 25
 26func (g *RandomAccessGate) vecSize() uint64 {
 27	return 1 << g.bits
 28}
 29
 30func (g *RandomAccessGate) WireAccessIndex(copy uint64) uint64 {
 31	if copy >= g.numCopies {
 32		panic("RandomAccessGate.WireAccessIndex called with copy >= num_copies")
 33	}
 34	return (2 + g.vecSize()) * copy
 35}
 36
 37func (g *RandomAccessGate) WireClaimedElement(copy uint64) uint64 {
 38	if copy >= g.numCopies {
 39		panic("RandomAccessGate.WireClaimedElement called with copy >= num_copies")
 40	}
 41
 42	return (2+g.vecSize())*copy + 1
 43}
 44
 45func (g *RandomAccessGate) WireListItem(i uint64, copy uint64) uint64 {
 46	if i >= g.vecSize() {
 47		panic("RandomAccessGate.WireListItem called with i >= vec_size")
 48	}
 49	if copy >= g.numCopies {
 50		panic("RandomAccessGate.WireListItem called with copy >= num_copies")
 51	}
 52
 53	return (2+g.vecSize())*copy + 2 + i
 54}
 55
 56func (g *RandomAccessGate) startExtraConstants() uint64 {
 57	return (2 + g.vecSize()) * g.numCopies
 58}
 59
 60func (g *RandomAccessGate) wireExtraConstant(i uint64) uint64 {
 61	if i >= g.numExtraConstants {
 62		panic("RandomAccessGate.wireExtraConstant called with i >= num_extra_constants")
 63	}
 64
 65	return g.startExtraConstants() + i
 66}
 67
 68func (g *RandomAccessGate) NumRoutedWires() uint64 {
 69	return g.startExtraConstants() + g.numExtraConstants
 70}
 71
 72func (g *RandomAccessGate) WireBit(i uint64, copy uint64) uint64 {
 73	if i >= g.bits {
 74		panic("RandomAccessGate.WireBit called with i >= bits")
 75	}
 76	if copy >= g.numCopies {
 77		panic("RandomAccessGate.WireBit called with copy >= num_copies")
 78	}
 79
 80	return g.NumRoutedWires() + copy*g.bits + i
 81}
 82
 83func (g *RandomAccessGate) EvalUnfiltered(p *PlonkChip, vars EvaluationVars) []QuadraticExtension {
 84	two := QuadraticExtension{NewFieldElement(2), NewFieldElement(0)}
 85	constraints := []QuadraticExtension{}
 86
 87	for copy := uint64(0); copy < g.numCopies; copy++ {
 88		accessIndex := vars.localWires[g.WireAccessIndex(copy)]
 89		listItems := []QuadraticExtension{}
 90		for i := uint64(0); i < g.vecSize(); i++ {
 91			listItems = append(listItems, vars.localWires[g.WireListItem(i, copy)])
 92		}
 93		claimedElement := vars.localWires[g.WireClaimedElement(copy)]
 94		bits := []QuadraticExtension{}
 95		for i := uint64(0); i < g.bits; i++ {
 96			bits = append(bits, vars.localWires[g.WireBit(i, copy)])
 97		}
 98
 99		// Assert that each bit wire value is indeed boolean.
100		for _, b := range bits {
101			bSquared := p.qeAPI.MulExtension(b, b)
102			constraints = append(constraints, p.qeAPI.SubExtension(bSquared, b))
103		}
104
105		// Assert that the binary decomposition was correct.
106		reconstructedIndex := p.qeAPI.ReduceWithPowers(bits, two)
107		constraints = append(constraints, p.qeAPI.SubExtension(reconstructedIndex, accessIndex))
108
109		for _, b := range bits {
110			listItemsTmp := []QuadraticExtension{}
111			for i := 0; i < len(listItems); i += 2 {
112				x := listItems[i]
113				y := listItems[i+1]
114
115				// This is computing `if b { x } else { y }`
116				// i.e. `bx - (by-y)`.
117				mul1 := p.qeAPI.MulExtension(b, x)
118				sub1 := p.qeAPI.SubExtension(mul1, x)
119
120				mul2 := p.qeAPI.MulExtension(b, y)
121				sub2 := p.qeAPI.SubExtension(mul2, sub1)
122
123				listItemsTmp = append(listItemsTmp, sub2)
124			}
125			listItems = listItemsTmp
126		}
127
128		if len(listItems) != 1 {
129			panic("listItems(len) != 1")
130		}
131
132		constraints = append(constraints, p.qeAPI.SubExtension(listItems[0], claimedElement))
133	}
134
135	for i := uint64(0); i < g.numExtraConstants; i++ {
136		constraints = append(constraints, p.qeAPI.SubExtension(vars.localConstants[i], vars.localWires[g.wireExtraConstant(i)]))
137	}
138
139	return constraints
140}