go-circom-prover-verifier/prover/gextra.go
prover/gextra.goRaw
1package prover
2
3import (
4 bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
5 cryptoConstants "github.com/iden3/go-iden3-crypto/constants"
6 "math/big"
7)
8
9type TableG1 struct {
10 data []*bn256.G1
11}
12
13func (t TableG1) GetData() []*bn256.G1 {
14 return t.data
15}
16
17// Compute table of gsize elements as ::
18// Table[0] = Inf
19// Table[1] = a[0]
20// Table[2] = a[1]
21// Table[3] = a[0]+a[1]
22// .....
23// Table[(1<<gsize)-1] = a[0]+a[1]+...+a[gsize-1]
24func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int, toaffine bool) {
25 // EC table
26 table := make([]*bn256.G1, 0)
27
28 // We need at least gsize elements. If not enough, fill with 0
29 a_ext := make([]*bn256.G1, 0)
30 a_ext = append(a_ext, a...)
31
32 for i := len(a); i < gsize; i++ {
33 a_ext = append(a_ext, new(bn256.G1).ScalarBaseMult(big.NewInt(0)))
34 }
35
36 elG1 := new(bn256.G1).ScalarBaseMult(big.NewInt(0))
37 table = append(table, elG1)
38 last_pow2 := 1
39 nelems := 0
40 for i := 1; i < 1<<gsize; i++ {
41 elG1 := new(bn256.G1)
42 // if power of 2
43 if i&(i-1) == 0 {
44 last_pow2 = i
45 elG1.Set(a_ext[nelems])
46 nelems++
47 } else {
48 elG1.Add(table[last_pow2], table[i-last_pow2])
49 // TODO bn256 doesn't export MakeAffine function. We need to fork repo
50 //table[i].MakeAffine()
51 }
52 table = append(table, elG1)
53 }
54 if toaffine {
55 for i := 0; i < len(table); i++ {
56 info := table[i].Marshal()
57 table[i].Unmarshal(info)
58 }
59 }
60 t.data = table
61}
62
63func (t TableG1) Marshal() []byte {
64 info := make([]byte, 0)
65 for _, el := range t.data {
66 info = append(info, el.Marshal()...)
67 }
68
69 return info
70}
71
72// Multiply scalar by precomputed table of G1 elements
73func (t *TableG1) MulTableG1(k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
74 // We need at least gsize elements. If not enough, fill with 0
75 k_ext := make([]*big.Int, 0)
76 k_ext = append(k_ext, k...)
77
78 for i := len(k); i < gsize; i++ {
79 k_ext = append(k_ext, new(big.Int).SetUint64(0))
80 }
81
82 Q := new(bn256.G1).ScalarBaseMult(big.NewInt(0))
83
84 msb := getMsb(k_ext)
85
86 for i := msb - 1; i >= 0; i-- {
87 // TODO. bn256 doesn't export double operation. We will need to fork repo and export it
88 Q = new(bn256.G1).Add(Q, Q)
89 b := getBit(k_ext, i)
90 if b != 0 {
91 // TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
92 Q.Add(Q, t.data[b])
93 }
94 }
95 if Q_prev != nil {
96 return Q.Add(Q, Q_prev)
97 } else {
98 return Q
99 }
100}
101
102// Multiply scalar by precomputed table of G1 elements without intermediate doubling
103func MulTableNoDoubleG1(t []TableG1, k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
104 // We need at least gsize elements. If not enough, fill with 0
105 min_nelems := len(t) * gsize
106 k_ext := make([]*big.Int, 0)
107 k_ext = append(k_ext, k...)
108 for i := len(k); i < min_nelems; i++ {
109 k_ext = append(k_ext, new(big.Int).SetUint64(0))
110 }
111 // Init Adders
112 nbitsQ := cryptoConstants.Q.BitLen()
113 Q := make([]*bn256.G1, nbitsQ)
114
115 for i := 0; i < nbitsQ; i++ {
116 Q[i] = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
117 }
118
119 // Perform bitwise addition
120 for j := 0; j < len(t); j++ {
121 msb := getMsb(k_ext[j*gsize : (j+1)*gsize])
122
123 for i := msb - 1; i >= 0; i-- {
124 b := getBit(k_ext[j*gsize:(j+1)*gsize], i)
125 if b != 0 {
126 // TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
127 Q[i].Add(Q[i], t[j].data[b])
128 }
129 }
130 }
131
132 // Consolidate Addition
133 R := new(bn256.G1).Set(Q[nbitsQ-1])
134 for i := nbitsQ - 1; i > 0; i-- {
135 // TODO. bn256 doesn't export double operation. We will need to fork repo and export it
136 R = new(bn256.G1).Add(R, R)
137 R.Add(R, Q[i-1])
138 }
139
140 if Q_prev != nil {
141 return R.Add(R, Q_prev)
142 } else {
143 return R
144 }
145}
146
147// Compute tables within function. This solution should still be faster than std multiplication
148// for gsize = 7
149func ScalarMultG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
150 ntables := int((len(a) + gsize - 1) / gsize)
151 table := TableG1{}
152 Q := new(bn256.G1).ScalarBaseMult(new(big.Int))
153
154 for i := 0; i < ntables-1; i++ {
155 table.NewTableG1(a[i*gsize:(i+1)*gsize], gsize, false)
156 Q = table.MulTableG1(k[i*gsize:(i+1)*gsize], Q, gsize)
157 }
158 table.NewTableG1(a[(ntables-1)*gsize:], gsize, false)
159 Q = table.MulTableG1(k[(ntables-1)*gsize:], Q, gsize)
160
161 if Q_prev != nil {
162 return Q.Add(Q, Q_prev)
163 } else {
164 return Q
165 }
166}
167
168// Multiply scalar by precomputed table of G1 elements without intermediate doubling
169func ScalarMultNoDoubleG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
170 ntables := int((len(a) + gsize - 1) / gsize)
171 table := TableG1{}
172
173 // We need at least gsize elements. If not enough, fill with 0
174 min_nelems := ntables * gsize
175 k_ext := make([]*big.Int, 0)
176 k_ext = append(k_ext, k...)
177 for i := len(k); i < min_nelems; i++ {
178 k_ext = append(k_ext, new(big.Int).SetUint64(0))
179 }
180 // Init Adders
181 nbitsQ := cryptoConstants.Q.BitLen()
182 Q := make([]*bn256.G1, nbitsQ)
183
184 for i := 0; i < nbitsQ; i++ {
185 Q[i] = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
186 }
187
188 // Perform bitwise addition
189 for j := 0; j < ntables-1; j++ {
190 table.NewTableG1(a[j*gsize:(j+1)*gsize], gsize, false)
191 msb := getMsb(k_ext[j*gsize : (j+1)*gsize])
192
193 for i := msb - 1; i >= 0; i-- {
194 b := getBit(k_ext[j*gsize:(j+1)*gsize], i)
195 if b != 0 {
196 // TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
197 Q[i].Add(Q[i], table.data[b])
198 }
199 }
200 }
201 table.NewTableG1(a[(ntables-1)*gsize:], gsize, false)
202 msb := getMsb(k_ext[(ntables-1)*gsize:])
203
204 for i := msb - 1; i >= 0; i-- {
205 b := getBit(k_ext[(ntables-1)*gsize:], i)
206 if b != 0 {
207 // TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
208 Q[i].Add(Q[i], table.data[b])
209 }
210 }
211
212 // Consolidate Addition
213 R := new(bn256.G1).Set(Q[nbitsQ-1])
214 for i := nbitsQ - 1; i > 0; i-- {
215 // TODO. bn256 doesn't export double operation. We will need to fork repo and export it
216 R = new(bn256.G1).Add(R, R)
217 R.Add(R, Q[i-1])
218 }
219 if Q_prev != nil {
220 return R.Add(R, Q_prev)
221 } else {
222 return R
223 }
224}
225
226/////
227
228// TODO - How can avoid replicating code in G2?
229//G2
230
231type TableG2 struct {
232 data []*bn256.G2
233}
234
235func (t TableG2) GetData() []*bn256.G2 {
236 return t.data
237}
238
239// Compute table of gsize elements as ::
240// Table[0] = Inf
241// Table[1] = a[0]
242// Table[2] = a[1]
243// Table[3] = a[0]+a[1]
244// .....
245// Table[(1<<gsize)-1] = a[0]+a[1]+...+a[gsize-1]
246// TODO -> toaffine = True doesnt work. Problem with Marshal/Unmarshal
247func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int, toaffine bool) {
248 // EC table
249 table := make([]*bn256.G2, 0)
250
251 // We need at least gsize elements. If not enough, fill with 0
252 a_ext := make([]*bn256.G2, 0)
253 a_ext = append(a_ext, a...)
254
255 for i := len(a); i < gsize; i++ {
256 a_ext = append(a_ext, new(bn256.G2).ScalarBaseMult(big.NewInt(0)))
257 }
258
259 elG2 := new(bn256.G2).ScalarBaseMult(big.NewInt(0))
260 table = append(table, elG2)
261 last_pow2 := 1
262 nelems := 0
263 for i := 1; i < 1<<gsize; i++ {
264 elG2 := new(bn256.G2)
265 // if power of 2
266 if i&(i-1) == 0 {
267 last_pow2 = i
268 elG2.Set(a_ext[nelems])
269 nelems++
270 } else {
271 elG2.Add(table[last_pow2], table[i-last_pow2])
272 // TODO bn256 doesn't export MakeAffine function. We need to fork repo
273 //table[i].MakeAffine()
274 }
275 table = append(table, elG2)
276 }
277 if toaffine {
278 for i := 0; i < len(table); i++ {
279 info := table[i].Marshal()
280 table[i].Unmarshal(info)
281 }
282 }
283 t.data = table
284}
285
286func (t TableG2) Marshal() []byte {
287 info := make([]byte, 0)
288 for _, el := range t.data {
289 info = append(info, el.Marshal()...)
290 }
291
292 return info
293}
294
295// Multiply scalar by precomputed table of G2 elements
296func (t *TableG2) MulTableG2(k []*big.Int, Q_prev *bn256.G2, gsize int) *bn256.G2 {
297 // We need at least gsize elements. If not enough, fill with 0
298 k_ext := make([]*big.Int, 0)
299 k_ext = append(k_ext, k...)
300
301 for i := len(k); i < gsize; i++ {
302 k_ext = append(k_ext, new(big.Int).SetUint64(0))
303 }
304
305 Q := new(bn256.G2).ScalarBaseMult(big.NewInt(0))
306
307 msb := getMsb(k_ext)
308
309 for i := msb - 1; i >= 0; i-- {
310 // TODO. bn256 doesn't export double operation. We will need to fork repo and export it
311 Q = new(bn256.G2).Add(Q, Q)
312 b := getBit(k_ext, i)
313 if b != 0 {
314 // TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
315 Q.Add(Q, t.data[b])
316 }
317 }
318 if Q_prev != nil {
319 return Q.Add(Q, Q_prev)
320 } else {
321 return Q
322 }
323}
324
325// Multiply scalar by precomputed table of G2 elements without intermediate doubling
326func MulTableNoDoubleG2(t []TableG2, k []*big.Int, Q_prev *bn256.G2, gsize int) *bn256.G2 {
327 // We need at least gsize elements. If not enough, fill with 0
328 min_nelems := len(t) * gsize
329 k_ext := make([]*big.Int, 0)
330 k_ext = append(k_ext, k...)
331 for i := len(k); i < min_nelems; i++ {
332 k_ext = append(k_ext, new(big.Int).SetUint64(0))
333 }
334 // Init Adders
335 nbitsQ := cryptoConstants.Q.BitLen()
336 Q := make([]*bn256.G2, nbitsQ)
337
338 for i := 0; i < nbitsQ; i++ {
339 Q[i] = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
340 }
341
342 // Perform bitwise addition
343 for j := 0; j < len(t); j++ {
344 msb := getMsb(k_ext[j*gsize : (j+1)*gsize])
345
346 for i := msb - 1; i >= 0; i-- {
347 b := getBit(k_ext[j*gsize:(j+1)*gsize], i)
348 if b != 0 {
349 // TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
350 Q[i].Add(Q[i], t[j].data[b])
351 }
352 }
353 }
354
355 // Consolidate Addition
356 R := new(bn256.G2).Set(Q[nbitsQ-1])
357 for i := nbitsQ - 1; i > 0; i-- {
358 // TODO. bn256 doesn't export double operation. We will need to fork repo and export it
359 R = new(bn256.G2).Add(R, R)
360 R.Add(R, Q[i-1])
361 }
362 if Q_prev != nil {
363 return R.Add(R, Q_prev)
364 } else {
365 return R
366 }
367}
368
369// Compute tables within function. This solution should still be faster than std multiplication
370// for gsize = 7
371func ScalarMultG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize int) *bn256.G2 {
372 ntables := int((len(a) + gsize - 1) / gsize)
373 table := TableG2{}
374 Q := new(bn256.G2).ScalarBaseMult(new(big.Int))
375
376 for i := 0; i < ntables-1; i++ {
377 table.NewTableG2(a[i*gsize:(i+1)*gsize], gsize, false)
378 Q = table.MulTableG2(k[i*gsize:(i+1)*gsize], Q, gsize)
379 }
380 table.NewTableG2(a[(ntables-1)*gsize:], gsize, false)
381 Q = table.MulTableG2(k[(ntables-1)*gsize:], Q, gsize)
382
383 if Q_prev != nil {
384 return Q.Add(Q, Q_prev)
385 } else {
386 return Q
387 }
388}
389
390// Multiply scalar by precomputed table of G2 elements without intermediate doubling
391func ScalarMultNoDoubleG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize int) *bn256.G2 {
392 ntables := int((len(a) + gsize - 1) / gsize)
393 table := TableG2{}
394
395 // We need at least gsize elements. If not enough, fill with 0
396 min_nelems := ntables * gsize
397 k_ext := make([]*big.Int, 0)
398 k_ext = append(k_ext, k...)
399 for i := len(k); i < min_nelems; i++ {
400 k_ext = append(k_ext, new(big.Int).SetUint64(0))
401 }
402 // Init Adders
403 nbitsQ := cryptoConstants.Q.BitLen()
404 Q := make([]*bn256.G2, nbitsQ)
405
406 for i := 0; i < nbitsQ; i++ {
407 Q[i] = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
408 }
409
410 // Perform bitwise addition
411 for j := 0; j < ntables-1; j++ {
412 table.NewTableG2(a[j*gsize:(j+1)*gsize], gsize, false)
413 msb := getMsb(k_ext[j*gsize : (j+1)*gsize])
414
415 for i := msb - 1; i >= 0; i-- {
416 b := getBit(k_ext[j*gsize:(j+1)*gsize], i)
417 if b != 0 {
418 // TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
419 Q[i].Add(Q[i], table.data[b])
420 }
421 }
422 }
423 table.NewTableG2(a[(ntables-1)*gsize:], gsize, false)
424 msb := getMsb(k_ext[(ntables-1)*gsize:])
425
426 for i := msb - 1; i >= 0; i-- {
427 b := getBit(k_ext[(ntables-1)*gsize:], i)
428 if b != 0 {
429 // TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
430 Q[i].Add(Q[i], table.data[b])
431 }
432 }
433
434 // Consolidate Addition
435 R := new(bn256.G2).Set(Q[nbitsQ-1])
436 for i := nbitsQ - 1; i > 0; i-- {
437 // TODO. bn256 doesn't export double operation. We will need to fork repo and export it
438 R = new(bn256.G2).Add(R, R)
439 R.Add(R, Q[i-1])
440 }
441 if Q_prev != nil {
442 return R.Add(R, Q_prev)
443 } else {
444 return R
445 }
446}
447
448// Return most significant bit position in a group of Big Integers
449func getMsb(k []*big.Int) int {
450 msb := 0
451
452 for _, el := range k {
453 tmp_msb := el.BitLen()
454 if tmp_msb > msb {
455 msb = tmp_msb
456 }
457 }
458 return msb
459}
460
461// Return ith bit in group of Big Integers
462func getBit(k []*big.Int, i int) uint {
463 table_idx := uint(0)
464
465 for idx, el := range k {
466 b := el.Bit(i)
467 table_idx += (b << idx)
468 }
469 return table_idx
470}