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