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