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