gnark-plonky2-verifier/poseidon/goldilocks.go
poseidon/goldilocks.goRaw
1package poseidon
2
3import (
4 "github.com/consensys/gnark/frontend"
5 gl "github.com/succinctlabs/gnark-plonky2-verifier/goldilocks"
6)
7
8const HALF_N_FULL_ROUNDS = 4
9const N_PARTIAL_ROUNDS = 22
10const MAX_WIDTH = 12
11const SPONGE_WIDTH = 12
12const SPONGE_RATE = 8
13
14type GoldilocksState = [SPONGE_WIDTH]gl.GoldilocksVariable
15type GoldilocksStateExtension = [SPONGE_WIDTH]gl.QuadraticExtensionVariable
16type GoldilocksHashOut = [4]gl.GoldilocksVariable
17
18type GoldilocksChip struct {
19 api frontend.API `gnark:"-"`
20 gl gl.GoldilocksApi `gnark:"-"`
21}
22
23func NewGoldilocksChip(api frontend.API) *GoldilocksChip {
24 return &GoldilocksChip{api: api, gl: *gl.NewGoldilocksApi(api)}
25}
26
27// The permutation function.
28// The input state MUST have all it's elements be within Goldilocks field (e.g. this function will not reduce the input elements).
29// The returned state's elements will all be within Goldilocks field.
30func (c *GoldilocksChip) Poseidon(input GoldilocksState) GoldilocksState {
31 state := input
32 roundCounter := 0
33 state = c.fullRounds(state, &roundCounter)
34 state = c.partialRounds(state, &roundCounter)
35 state = c.fullRounds(state, &roundCounter)
36 return state
37}
38
39// The input elements MUST have all it's elements be within Goldilocks field.
40// The returned slice's elements will all be within Goldilocks field.
41func (c *GoldilocksChip) HashNToMNoPad(input []gl.GoldilocksVariable, nbOutputs int) []gl.GoldilocksVariable {
42 var state GoldilocksState
43
44 for i := 0; i < SPONGE_WIDTH; i++ {
45 state[i] = gl.NewVariable(0)
46 }
47
48 for i := 0; i < len(input); i += SPONGE_RATE {
49 for j := 0; j < SPONGE_RATE; j++ {
50 if i+j < len(input) {
51 state[j] = input[i+j]
52 }
53 }
54 state = c.Poseidon(state)
55 }
56
57 var outputs []gl.GoldilocksVariable
58
59 for {
60 for i := 0; i < SPONGE_RATE; i++ {
61 outputs = append(outputs, state[i])
62 if len(outputs) == nbOutputs {
63 return outputs
64 }
65 }
66 state = c.Poseidon(state)
67 }
68}
69
70// The input elements can be outside of the Goldilocks field.
71// The returned slice's elements will all be within Goldilocks field.
72func (c *GoldilocksChip) HashNoPad(input []gl.GoldilocksVariable) GoldilocksHashOut {
73 var hash GoldilocksHashOut
74 inputVars := []gl.GoldilocksVariable{}
75
76 for i := 0; i < len(input); i++ {
77 inputVars = append(inputVars, c.gl.Reduce(input[i]))
78 }
79
80 outputVars := c.HashNToMNoPad(inputVars, 4)
81 for i := 0; i < 4; i++ {
82 hash[i] = outputVars[i]
83 }
84
85 return hash
86}
87
88func (c *GoldilocksChip) ToVec(hash GoldilocksHashOut) []gl.GoldilocksVariable {
89 return hash[:]
90}
91
92func (c *GoldilocksChip) fullRounds(state GoldilocksState, roundCounter *int) GoldilocksState {
93 for i := 0; i < HALF_N_FULL_ROUNDS; i++ {
94 state = c.constantLayer(state, roundCounter)
95 state = c.sBoxLayer(state)
96 state = c.mdsLayer(state)
97 *roundCounter += 1
98 }
99 return state
100}
101
102func (c *GoldilocksChip) partialRounds(state GoldilocksState, roundCounter *int) GoldilocksState {
103 state = c.partialFirstConstantLayer(state)
104 state = c.mdsPartialLayerInit(state)
105
106 for i := 0; i < N_PARTIAL_ROUNDS; i++ {
107 state[0] = c.sBoxMonomial(state[0])
108 state[0] = c.gl.Add(state[0], gl.NewVariable(FAST_PARTIAL_ROUND_CONSTANTS[i]))
109 state = c.mdsPartialLayerFast(state, i)
110 }
111
112 *roundCounter += N_PARTIAL_ROUNDS
113
114 return state
115}
116
117func (c *GoldilocksChip) constantLayer(state GoldilocksState, roundCounter *int) GoldilocksState {
118 for i := 0; i < 12; i++ {
119 if i < SPONGE_WIDTH {
120 roundConstant := ALL_ROUND_CONSTANTS[i+SPONGE_WIDTH*(*roundCounter)]
121 state[i] = c.gl.MulAdd(state[i], gl.NewVariable(1), gl.NewVariable(roundConstant))
122 }
123 }
124 return state
125}
126
127func (c *GoldilocksChip) ConstantLayerExtension(state GoldilocksStateExtension, roundCounter *int) GoldilocksStateExtension {
128 for i := 0; i < 12; i++ {
129 if i < SPONGE_WIDTH {
130 roundConstant := gl.NewVariable(ALL_ROUND_CONSTANTS[i+SPONGE_WIDTH*(*roundCounter)])
131 roundConstantQE := gl.NewQuadraticExtensionVariable(roundConstant, gl.Zero())
132 state[i] = c.gl.AddExtension(state[i], roundConstantQE)
133 }
134 }
135 return state
136}
137
138func (c *GoldilocksChip) sBoxMonomial(x gl.GoldilocksVariable) gl.GoldilocksVariable {
139 x2 := c.gl.MulNoReduce(x, x)
140 x3 := c.gl.MulNoReduce(x, x2)
141 x3 = c.gl.ReduceWithMaxBits(x3, 192)
142 x6 := c.gl.MulNoReduce(x3, x3)
143 x7 := c.gl.MulNoReduce(x, x6)
144 return c.gl.ReduceWithMaxBits(x7, 192)
145}
146
147func (c *GoldilocksChip) SBoxMonomialExtension(x gl.QuadraticExtensionVariable) gl.QuadraticExtensionVariable {
148 x2 := c.gl.MulExtension(x, x)
149 x4 := c.gl.MulExtension(x2, x2)
150 x3 := c.gl.MulExtension(x, x2)
151 return c.gl.MulExtension(x4, x3)
152}
153
154func (c *GoldilocksChip) sBoxLayer(state GoldilocksState) GoldilocksState {
155 for i := 0; i < 12; i++ {
156 if i < SPONGE_WIDTH {
157 state[i] = c.sBoxMonomial(state[i])
158 }
159 }
160 return state
161}
162
163func (c *GoldilocksChip) SBoxLayerExtension(state GoldilocksStateExtension) GoldilocksStateExtension {
164 for i := 0; i < 12; i++ {
165 if i < SPONGE_WIDTH {
166 state[i] = c.SBoxMonomialExtension(state[i])
167 }
168 }
169 return state
170}
171
172func (c *GoldilocksChip) mdsRowShf(r int, v [SPONGE_WIDTH]gl.GoldilocksVariable) gl.GoldilocksVariable {
173 res := gl.Zero()
174
175 for i := 0; i < 12; i++ {
176 if i < SPONGE_WIDTH {
177 res = c.gl.MulAddNoReduce(v[(i+r)%SPONGE_WIDTH], gl.NewVariable(MDS_MATRIX_CIRC_VARS[i]), res)
178 }
179 }
180
181 res = c.gl.MulAddNoReduce(v[r], gl.NewVariable(MDS_MATRIX_DIAG_VARS[r]), res)
182 return c.gl.Reduce(res)
183}
184
185func (c *GoldilocksChip) MdsRowShfExtension(r int, v [SPONGE_WIDTH]gl.QuadraticExtensionVariable) gl.QuadraticExtensionVariable {
186 res := gl.ZeroExtension()
187
188 for i := 0; i < 12; i++ {
189 if i < SPONGE_WIDTH {
190 matrixVal := gl.NewVariable(MDS_MATRIX_CIRC[i])
191 matrixValQE := gl.NewQuadraticExtensionVariable(matrixVal, gl.Zero())
192 res1 := c.gl.MulExtension(v[(i+r)%SPONGE_WIDTH], matrixValQE)
193 res = c.gl.AddExtension(res, res1)
194 }
195 }
196
197 matrixVal := gl.NewVariable(MDS_MATRIX_DIAG[r])
198 matrixValQE := gl.NewQuadraticExtensionVariable(matrixVal, gl.Zero())
199 res = c.gl.AddExtension(res, c.gl.MulExtension(v[r], matrixValQE))
200 return res
201}
202
203func (c *GoldilocksChip) mdsLayer(state_ GoldilocksState) GoldilocksState {
204 var result GoldilocksState
205 for i := 0; i < SPONGE_WIDTH; i++ {
206 result[i] = gl.NewVariable(0)
207 }
208
209 for r := 0; r < 12; r++ {
210 if r < SPONGE_WIDTH {
211 result[r] = c.mdsRowShf(r, state_)
212 }
213 }
214
215 return result
216}
217
218func (c *GoldilocksChip) MdsLayerExtension(state_ GoldilocksStateExtension) GoldilocksStateExtension {
219 var result GoldilocksStateExtension
220
221 for r := 0; r < 12; r++ {
222 if r < SPONGE_WIDTH {
223 sum := c.MdsRowShfExtension(r, state_)
224 result[r] = sum
225 }
226 }
227
228 return result
229}
230
231func (c *GoldilocksChip) partialFirstConstantLayer(state GoldilocksState) GoldilocksState {
232 for i := 0; i < 12; i++ {
233 if i < SPONGE_WIDTH {
234 state[i] = c.gl.Add(state[i], gl.NewVariable(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i]))
235 }
236 }
237 return state
238}
239
240func (c *GoldilocksChip) PartialFirstConstantLayerExtension(state GoldilocksStateExtension) GoldilocksStateExtension {
241 for i := 0; i < 12; i++ {
242 if i < SPONGE_WIDTH {
243 fastPartialRoundConstant := gl.NewVariable(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i])
244 fastPartialRoundConstantQE := gl.NewQuadraticExtensionVariable(fastPartialRoundConstant, gl.Zero())
245 state[i] = c.gl.AddExtension(state[i], fastPartialRoundConstantQE)
246 }
247 }
248 return state
249}
250
251func (c *GoldilocksChip) mdsPartialLayerInit(state GoldilocksState) GoldilocksState {
252 var result GoldilocksState
253 for i := 0; i < 12; i++ {
254 result[i] = gl.NewVariable(0)
255 }
256
257 result[0] = state[0]
258
259 for r := 1; r < 12; r++ {
260 if r < SPONGE_WIDTH {
261 for d := 1; d < 12; d++ {
262 if d < SPONGE_WIDTH {
263 t := FAST_PARTIAL_ROUND_INITIAL_MATRIX[r-1][d-1]
264 result[d] = c.gl.MulAddNoReduce(state[r], gl.NewVariable(t), result[d])
265 }
266 }
267 }
268 }
269
270 for i := 0; i < 12; i++ {
271 result[i] = c.gl.Reduce(result[i])
272 }
273
274 return result
275}
276
277func (c *GoldilocksChip) MdsPartialLayerInitExtension(state GoldilocksStateExtension) GoldilocksStateExtension {
278 var result GoldilocksStateExtension
279 for i := 0; i < 12; i++ {
280 result[i] = gl.ZeroExtension()
281 }
282
283 result[0] = state[0]
284
285 for r := 1; r < 12; r++ {
286 if r < SPONGE_WIDTH {
287 for d := 1; d < 12; d++ {
288 if d < SPONGE_WIDTH {
289 t := gl.NewVariable(FAST_PARTIAL_ROUND_INITIAL_MATRIX[r-1][d-1])
290 tQE := gl.NewQuadraticExtensionVariable(t, gl.Zero())
291 result[d] = c.gl.AddExtension(result[d], c.gl.MulExtension(state[r], tQE))
292 }
293 }
294 }
295 }
296
297 return result
298}
299
300func (c *GoldilocksChip) mdsPartialLayerFast(state GoldilocksState, r int) GoldilocksState {
301 dSum := gl.Zero()
302 for i := 1; i < 12; i++ {
303 if i < SPONGE_WIDTH {
304 t := FAST_PARTIAL_ROUND_W_HATS_VARS[r][i-1]
305 dSum = c.gl.MulAddNoReduce(state[i], gl.NewVariable(t), dSum)
306 }
307 }
308
309 d := c.gl.MulAddNoReduce(state[0], gl.NewVariable(MDS0TO0_VAR), dSum)
310 d = c.gl.Reduce(d)
311
312 var result GoldilocksState
313 for i := 0; i < SPONGE_WIDTH; i++ {
314 result[i] = gl.NewVariable(0)
315 }
316
317 result[0] = d
318
319 for i := 1; i < 12; i++ {
320 if i < SPONGE_WIDTH {
321 t := FAST_PARTIAL_ROUND_VS[r][i-1]
322 result[i] = c.gl.MulAddNoReduce(state[0], gl.NewVariable(t), state[i])
323 }
324 }
325
326 for i := 0; i < len(state); i++ {
327 result[i] = c.gl.Reduce(result[i])
328 }
329
330 return result
331}
332
333func (c *GoldilocksChip) MdsPartialLayerFastExtension(state GoldilocksStateExtension, r int) GoldilocksStateExtension {
334 s0 := state[0]
335 mds0to0 := gl.NewVariable(MDS0TO0)
336 mds0to0QE := gl.NewQuadraticExtensionVariable(mds0to0, gl.Zero())
337 d := c.gl.MulExtension(s0, mds0to0QE)
338 for i := 1; i < 12; i++ {
339 if i < SPONGE_WIDTH {
340 t := gl.NewVariable(FAST_PARTIAL_ROUND_W_HATS[r][i-1])
341 tQE := gl.NewQuadraticExtensionVariable(t, gl.Zero())
342 d = c.gl.AddExtension(d, c.gl.MulExtension(state[i], tQE))
343 }
344 }
345
346 var result GoldilocksStateExtension
347 result[0] = d
348 for i := 1; i < 12; i++ {
349 if i < SPONGE_WIDTH {
350 t := gl.NewVariable(FAST_PARTIAL_ROUND_VS[r][i-1])
351 tQE := gl.NewQuadraticExtensionVariable(t, gl.Zero())
352 result[i] = c.gl.AddExtension(c.gl.MulExtension(state[0], tQE), state[i])
353 }
354 }
355
356 return result
357}