gnark-plonky2-verifier/poseidon/poseidon.go
poseidon/poseidon.goRaw
1package poseidon
2
3import (
4 . "gnark-plonky2-verifier/field"
5
6 "github.com/consensys/gnark/frontend"
7)
8
9const HALF_N_FULL_ROUNDS = 4
10const N_FULL_ROUNDS_TOTAL = 2 * HALF_N_FULL_ROUNDS
11const N_PARTIAL_ROUNDS = 22
12const N_ROUNDS = N_FULL_ROUNDS_TOTAL + N_PARTIAL_ROUNDS
13const MAX_WIDTH = 12
14const SPONGE_WIDTH = 12
15const SPONGE_RATE = 8
16
17type PoseidonState = [SPONGE_WIDTH]F
18type PoseidonStateExtension = [SPONGE_WIDTH]QuadraticExtension
19
20type PoseidonChip struct {
21 api frontend.API `gnark:"-"`
22 fieldAPI frontend.API `gnark:"-"`
23 qeAPI *QuadraticExtensionAPI `gnark:"-"`
24}
25
26func NewPoseidonChip(api frontend.API, fieldAPI frontend.API, qeAPI *QuadraticExtensionAPI) *PoseidonChip {
27 return &PoseidonChip{api: api, fieldAPI: fieldAPI, qeAPI: qeAPI}
28}
29
30func (c *PoseidonChip) Poseidon(input PoseidonState) PoseidonState {
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
39func (c *PoseidonChip) HashNToMNoPad(input []F, nbOutputs int) []F {
40 var state PoseidonState
41
42 for i := 0; i < SPONGE_WIDTH; i++ {
43 state[i] = ZERO_F
44 }
45
46 for i := 0; i < len(input); i += SPONGE_RATE {
47 for j := 0; j < SPONGE_RATE; j++ {
48 if i+j < len(input) {
49 state[j] = input[i+j]
50 }
51 }
52 state = c.Poseidon(state)
53 }
54
55 var outputs []F
56
57 for {
58 for i := 0; i < SPONGE_RATE; i++ {
59 outputs = append(outputs, state[i])
60 if len(outputs) == nbOutputs {
61 return outputs
62 }
63 }
64 state = c.Poseidon(state)
65 }
66}
67
68func (c *PoseidonChip) HashNoPad(input []F) Hash {
69 var hash Hash
70 copy(hash[:], c.HashNToMNoPad(input, 4))
71 return hash
72}
73
74func (c *PoseidonChip) FullRounds(state PoseidonState, roundCounter *int) PoseidonState {
75 for i := 0; i < HALF_N_FULL_ROUNDS; i++ {
76 state = c.ConstantLayer(state, roundCounter)
77 state = c.SBoxLayer(state)
78 state = c.MdsLayer(state)
79 *roundCounter += 1
80 }
81 return state
82}
83
84func (c *PoseidonChip) PartialRounds(state PoseidonState, roundCounter *int) PoseidonState {
85 state = c.PartialFirstConstantLayer(state)
86 state = c.MdsPartialLayerInit(state)
87
88 for i := 0; i < N_PARTIAL_ROUNDS; i++ {
89 state[0] = c.SBoxMonomial(state[0])
90 state[0] = c.fieldAPI.Add(state[0], FAST_PARTIAL_ROUND_CONSTANTS[i]).(F)
91 state = c.MdsPartialLayerFast(state, i)
92 }
93
94 *roundCounter += N_PARTIAL_ROUNDS
95
96 return state
97}
98
99func (c *PoseidonChip) ConstantLayer(state PoseidonState, roundCounter *int) PoseidonState {
100 for i := 0; i < 12; i++ {
101 if i < SPONGE_WIDTH {
102 roundConstant := NewFieldElement(ALL_ROUND_CONSTANTS[i+SPONGE_WIDTH*(*roundCounter)])
103 state[i] = c.fieldAPI.Add(state[i], roundConstant).(F)
104 }
105 }
106 return state
107}
108
109func (c *PoseidonChip) ConstantLayerExtension(state PoseidonStateExtension, roundCounter *int) PoseidonStateExtension {
110 for i := 0; i < 12; i++ {
111 if i < SPONGE_WIDTH {
112 roundConstant := c.qeAPI.FieldToQE(NewFieldElement(ALL_ROUND_CONSTANTS[i+SPONGE_WIDTH*(*roundCounter)]))
113 state[i] = c.qeAPI.AddExtension(state[i], roundConstant)
114 }
115 }
116 return state
117}
118
119func (c *PoseidonChip) SBoxMonomial(x F) F {
120 x2 := c.fieldAPI.Mul(x, x)
121 x4 := c.fieldAPI.Mul(x2, x2)
122 x3 := c.fieldAPI.Mul(x2, x)
123 return c.fieldAPI.Mul(x3, x4).(F)
124}
125
126func (c *PoseidonChip) SBoxMonomialExtension(x QuadraticExtension) QuadraticExtension {
127 x2 := c.qeAPI.MulExtension(x, x)
128 x4 := c.qeAPI.MulExtension(x2, x2)
129 x3 := c.qeAPI.MulExtension(x2, x)
130 return c.qeAPI.MulExtension(x3, x4)
131}
132
133func (c *PoseidonChip) SBoxLayer(state PoseidonState) PoseidonState {
134 for i := 0; i < 12; i++ {
135 if i < SPONGE_WIDTH {
136 state[i] = c.SBoxMonomial(state[i])
137 }
138 }
139 return state
140}
141
142func (c *PoseidonChip) SBoxLayerExtension(state PoseidonStateExtension) PoseidonStateExtension {
143 for i := 0; i < 12; i++ {
144 if i < SPONGE_WIDTH {
145 state[i] = c.SBoxMonomialExtension(state[i])
146 }
147 }
148 return state
149}
150
151func (c *PoseidonChip) MdsRowShf(r int, v [SPONGE_WIDTH]frontend.Variable) frontend.Variable {
152 res := frontend.Variable(0)
153
154 for i := 0; i < 12; i++ {
155 if i < SPONGE_WIDTH {
156 res1 := c.api.Mul(v[(i+r)%SPONGE_WIDTH], frontend.Variable(MDS_MATRIX_CIRC[i]))
157 res = c.api.Add(res, res1)
158 }
159 }
160
161 res = c.api.Add(res, c.api.Mul(v[r], MDS_MATRIX_DIAG[r]))
162 return res
163}
164
165func (c *PoseidonChip) MdsRowShfExtension(r int, v [SPONGE_WIDTH]QuadraticExtension) QuadraticExtension {
166 res := c.qeAPI.FieldToQE(NewFieldElement(0))
167
168 for i := 0; i < 12; i++ {
169 if i < SPONGE_WIDTH {
170 matrixVal := c.qeAPI.FieldToQE(NewFieldElement(MDS_MATRIX_CIRC[i]))
171 res1 := c.qeAPI.MulExtension(v[(i+r)%SPONGE_WIDTH], matrixVal)
172 res = c.qeAPI.AddExtension(res, res1)
173 }
174 }
175
176 matrixVal := c.qeAPI.FieldToQE(NewFieldElement(MDS_MATRIX_DIAG[r]))
177 res = c.qeAPI.AddExtension(res, c.qeAPI.MulExtension(v[r], matrixVal))
178 return res
179}
180
181func (c *PoseidonChip) MdsLayer(state_ PoseidonState) PoseidonState {
182 var result PoseidonState
183 for i := 0; i < SPONGE_WIDTH; i++ {
184 result[i] = NewFieldElement(0)
185 }
186
187 var state [SPONGE_WIDTH]frontend.Variable
188 for i := 0; i < SPONGE_WIDTH; i++ {
189 state[i] = c.api.FromBinary(c.fieldAPI.ToBinary(state_[i])...)
190 }
191
192 for r := 0; r < 12; r++ {
193 if r < SPONGE_WIDTH {
194 sum := c.MdsRowShf(r, state)
195 bits := c.api.ToBinary(sum)
196 result[r] = c.fieldAPI.FromBinary(bits).(F)
197 }
198 }
199
200 return result
201}
202
203func (c *PoseidonChip) MdsLayerExtension(state_ PoseidonStateExtension) PoseidonStateExtension {
204 var result PoseidonStateExtension
205
206 for r := 0; r < 12; r++ {
207 if r < SPONGE_WIDTH {
208 sum := c.MdsRowShfExtension(r, state_)
209 result[r] = sum
210 }
211 }
212
213 return result
214}
215
216func (c *PoseidonChip) PartialFirstConstantLayer(state PoseidonState) PoseidonState {
217 for i := 0; i < 12; i++ {
218 if i < SPONGE_WIDTH {
219 state[i] = c.fieldAPI.Add(state[i], NewFieldElement(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i])).(F)
220 }
221 }
222 return state
223}
224
225func (c *PoseidonChip) PartialFirstConstantLayerExtension(state PoseidonStateExtension) PoseidonStateExtension {
226 for i := 0; i < 12; i++ {
227 if i < SPONGE_WIDTH {
228 state[i] = c.qeAPI.AddExtension(state[i], c.qeAPI.FieldToQE(NewFieldElement(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i])))
229 }
230 }
231 return state
232}
233
234func (c *PoseidonChip) MdsPartialLayerInit(state PoseidonState) PoseidonState {
235 var result PoseidonState
236 for i := 0; i < 12; i++ {
237 result[i] = NewFieldElement(0)
238 }
239
240 result[0] = state[0]
241
242 for r := 1; r < 12; r++ {
243 if r < SPONGE_WIDTH {
244 for d := 1; d < 12; d++ {
245 if d < SPONGE_WIDTH {
246 t := NewFieldElement(FAST_PARTIAL_ROUND_INITIAL_MATRIX[r-1][d-1])
247 result[d] = c.fieldAPI.Add(result[d], c.fieldAPI.Mul(state[r], t)).(F)
248 }
249 }
250 }
251 }
252
253 return result
254}
255
256func (c *PoseidonChip) MdsPartialLayerInitExtension(state PoseidonStateExtension) PoseidonStateExtension {
257 var result PoseidonStateExtension
258 for i := 0; i < 12; i++ {
259 result[i] = c.qeAPI.FieldToQE(NewFieldElement(0))
260 }
261
262 result[0] = state[0]
263
264 for r := 1; r < 12; r++ {
265 if r < SPONGE_WIDTH {
266 for d := 1; d < 12; d++ {
267 if d < SPONGE_WIDTH {
268 t := c.qeAPI.FieldToQE(NewFieldElement(FAST_PARTIAL_ROUND_INITIAL_MATRIX[r-1][d-1]))
269 result[d] = c.qeAPI.AddExtension(result[d], c.qeAPI.MulExtension(state[r], t))
270 }
271 }
272 }
273 }
274
275 return result
276}
277
278func (c *PoseidonChip) MdsPartialLayerFast(state PoseidonState, r int) PoseidonState {
279 dSum := frontend.Variable(0)
280 for i := 1; i < 12; i++ {
281 if i < SPONGE_WIDTH {
282 t := frontend.Variable(FAST_PARTIAL_ROUND_W_HATS[r][i-1])
283 si := c.api.FromBinary(c.fieldAPI.ToBinary(state[i])...)
284 dSum = c.api.Add(dSum, c.api.Mul(si, t))
285 }
286 }
287
288 s0 := c.api.FromBinary(c.fieldAPI.ToBinary(state[0])...)
289 mds0to0 := frontend.Variable(MDS_MATRIX_CIRC[0] + MDS_MATRIX_DIAG[0])
290 dSum = c.api.Add(dSum, c.api.Mul(s0, mds0to0))
291 d := c.fieldAPI.FromBinary(c.api.ToBinary(dSum))
292
293 var result PoseidonState
294 for i := 0; i < SPONGE_WIDTH; i++ {
295 result[i] = NewFieldElement(0)
296 }
297
298 result[0] = d.(F)
299
300 for i := 1; i < 12; i++ {
301 if i < SPONGE_WIDTH {
302 t := NewFieldElement(FAST_PARTIAL_ROUND_VS[r][i-1])
303 result[i] = c.fieldAPI.Add(state[i], c.fieldAPI.Mul(state[0], t)).(F)
304 }
305 }
306
307 return result
308}
309
310func (c *PoseidonChip) MdsPartialLayerFastExtension(state PoseidonStateExtension, r int) PoseidonStateExtension {
311 s0 := state[0]
312 mds0to0 := c.qeAPI.FieldToQE(NewFieldElement(MDS_MATRIX_CIRC[0] + MDS_MATRIX_DIAG[0]))
313 d := c.qeAPI.AddExtension(s0, mds0to0)
314 for i := 1; i < 12; i++ {
315 if i < SPONGE_WIDTH {
316 t := c.qeAPI.FieldToQE(NewFieldElement(FAST_PARTIAL_ROUND_W_HATS[r][i-1]))
317 d = c.qeAPI.AddExtension(d, c.qeAPI.MulExtension(state[i], t))
318 }
319 }
320
321 var result PoseidonStateExtension
322 result[0] = d
323 for i := 1; i < 12; i++ {
324 if i < SPONGE_WIDTH {
325 t := c.qeAPI.FieldToQE(NewFieldElement(FAST_PARTIAL_ROUND_VS[r][i-1]))
326 result[i] = c.qeAPI.AddExtension(state[i], c.qeAPI.MulExtension(state[0], t))
327 }
328 }
329
330 return result
331}