Add G1/G2 table calculation functionality

prover/gextra.go

@@ -1,21 +1,19 @@
 package prover
 
 import (
-        "math/big"
 	bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
 	cryptoConstants "github.com/iden3/go-iden3-crypto/constants"
+	"math/big"
 )
 
-type TableG1 struct{
+type TableG1 struct {
 	data []*bn256.G1
 }
 
-
 func (t TableG1) GetData() []*bn256.G1 {
 	return t.data
 }
 
-
 // Compute table of gsize elements as ::
 //  Table[0] = Inf
 //  Table[1] = a[0]
@@ -23,7 +21,7 @@ func (t TableG1) GetData() []*bn256.G1 {
 //  Table[3] = a[0]+a[1]
 //  .....
 //  Table[(1<<gsize)-1] = a[0]+a[1]+...+a[gsize-1]
-func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int){
+func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int, toaffine bool) {
 	// EC table
 	table := make([]*bn256.G1, 0)
 
@@ -31,18 +29,18 @@ func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int){
 	a_ext := make([]*bn256.G1, 0)
 	a_ext = append(a_ext, a...)
 
-   for i:=len(a); i<gsize; i++ {
-      a_ext = append(a_ext,new(bn256.G1).ScalarBaseMult(big.NewInt(0)))
+	for i := len(a); i < gsize; i++ {
+		a_ext = append(a_ext, new(bn256.G1).ScalarBaseMult(big.NewInt(0)))
 	}
 
 	elG1 := new(bn256.G1).ScalarBaseMult(big.NewInt(0))
-   table = append(table,elG1)
+	table = append(table, elG1)
 	last_pow2 := 1
 	nelems := 0
-   for i :=1; i< 1<<gsize; i++ {
+	for i := 1; i < 1<<gsize; i++ {
 		elG1 := new(bn256.G1)
 		// if power of 2
-      if i & (i-1) == 0{
+		if i&(i-1) == 0 {
 			last_pow2 = i
 			elG1.Set(a_ext[nelems])
 			nelems++
@@ -53,34 +51,49 @@ func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int){
 		}
 		table = append(table, elG1)
 	}
+	if toaffine {
+		for i := 0; i < len(table); i++ {
+			info := table[i].Marshal()
+			table[i].Unmarshal(info)
+		}
+	}
 	t.data = table
 }
 
+func (t TableG1) Marshal() []byte {
+	info := make([]byte, 0)
+	for _, el := range t.data {
+		info = append(info, el.Marshal()...)
+	}
+
+	return info
+}
+
 // Multiply scalar by precomputed table of G1 elements
 func (t *TableG1) MulTableG1(k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
 	// We need at least gsize elements. If not enough, fill with 0
 	k_ext := make([]*big.Int, 0)
 	k_ext = append(k_ext, k...)
 
-   for i:=len(k); i < gsize; i++ {
-      k_ext = append(k_ext,new(big.Int).SetUint64(0))
+	for i := len(k); i < gsize; i++ {
+		k_ext = append(k_ext, new(big.Int).SetUint64(0))
 	}
 
 	Q := new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 
 	msb := getMsb(k_ext)
 
-   for i := msb-1; i >= 0; i-- {
+	for i := msb - 1; i >= 0; i-- {
 		// TODO. bn256 doesn't export double operation. We will need to fork repo and export it
-	Q = new(bn256.G1).Add(Q,Q)
-        b := getBit(k_ext,i)
+		Q = new(bn256.G1).Add(Q, Q)
+		b := getBit(k_ext, i)
 		if b != 0 {
 			// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
 			Q.Add(Q, t.data[b])
 		}
 	}
 	if Q_prev != nil {
-     return Q.Add(Q,Q_prev)
+		return Q.Add(Q, Q_prev)
 	} else {
 		return Q
 	}
@@ -93,22 +106,22 @@ func MulTableNoDoubleG1(t []TableG1, k []*big.Int,  Q_prev *bn256.G1, gsize int)
 	k_ext := make([]*big.Int, 0)
 	k_ext = append(k_ext, k...)
 	for i := len(k); i < min_nelems; i++ {
-      k_ext = append(k_ext,new(big.Int).SetUint64(0))
+		k_ext = append(k_ext, new(big.Int).SetUint64(0))
 	}
 	// Init Adders
 	nbitsQ := cryptoConstants.Q.BitLen()
-   Q := make([]*bn256.G1,nbitsQ)
+	Q := make([]*bn256.G1, nbitsQ)
 
-   for i:=0; i< nbitsQ; i++ {
+	for i := 0; i < nbitsQ; i++ {
 		Q[i] = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 	}
 
 	// Perform bitwise addition
-   for j:=0; j < len(t); j++ {
-     msb := getMsb(k_ext[j*gsize:(j+1)*gsize])
+	for j := 0; j < len(t); j++ {
+		msb := getMsb(k_ext[j*gsize : (j+1)*gsize])
 
-     for i := msb-1; i >= 0; i-- {
-        b := getBit(k_ext[j*gsize:(j+1)*gsize],i)
+		for i := msb - 1; i >= 0; i-- {
+			b := getBit(k_ext[j*gsize:(j+1)*gsize], i)
 			if b != 0 {
 				// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
 				Q[i].Add(Q[i], t[j].data[b])
@@ -118,14 +131,14 @@ func MulTableNoDoubleG1(t []TableG1, k []*big.Int,  Q_prev *bn256.G1, gsize int)
 
 	// Consolidate Addition
 	R := new(bn256.G1).Set(Q[nbitsQ-1])
-   for i:=nbitsQ-1; i>0; i-- {
+	for i := nbitsQ - 1; i > 0; i-- {
 		// TODO. bn256 doesn't export double operation. We will need to fork repo and export it
-      R = new(bn256.G1).Add(R,R)
-      R.Add(R,Q[i-1])
+		R = new(bn256.G1).Add(R, R)
+		R.Add(R, Q[i-1])
 	}
 
 	if Q_prev != nil {
-      return R.Add(R,Q_prev)
+		return R.Add(R, Q_prev)
 	} else {
 		return R
 	}
@@ -136,17 +149,17 @@ func MulTableNoDoubleG1(t []TableG1, k []*big.Int,  Q_prev *bn256.G1, gsize int)
 func ScalarMultG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
 	ntables := int((len(a) + gsize - 1) / gsize)
 	table := TableG1{}
-     Q:= new(bn256.G1).ScalarBaseMult(new(big.Int))
+	Q := new(bn256.G1).ScalarBaseMult(new(big.Int))
 
-     for i:=0; i<ntables-1; i++ {
-       table.NewTableG1( a[i*gsize:(i+1)*gsize], gsize)
+	for i := 0; i < ntables-1; i++ {
+		table.NewTableG1(a[i*gsize:(i+1)*gsize], gsize, false)
 		Q = table.MulTableG1(k[i*gsize:(i+1)*gsize], Q, gsize)
 	}
-     table.NewTableG1( a[(ntables-1)*gsize:], gsize)
+	table.NewTableG1(a[(ntables-1)*gsize:], gsize, false)
 	Q = table.MulTableG1(k[(ntables-1)*gsize:], Q, gsize)
 
 	if Q_prev != nil {
-        return Q.Add(Q,Q_prev)
+		return Q.Add(Q, Q_prev)
 	} else {
 		return Q
 	}
@@ -162,34 +175,34 @@ func ScalarMultNoDoubleG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize i
 	k_ext := make([]*big.Int, 0)
 	k_ext = append(k_ext, k...)
 	for i := len(k); i < min_nelems; i++ {
-      k_ext = append(k_ext,new(big.Int).SetUint64(0))
+		k_ext = append(k_ext, new(big.Int).SetUint64(0))
 	}
 	// Init Adders
 	nbitsQ := cryptoConstants.Q.BitLen()
-   Q := make([]*bn256.G1,nbitsQ)
+	Q := make([]*bn256.G1, nbitsQ)
 
-   for i:=0; i< nbitsQ; i++ {
+	for i := 0; i < nbitsQ; i++ {
 		Q[i] = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 	}
 
 	// Perform bitwise addition
-   for j:=0; j < ntables-1; j++ {
-     table.NewTableG1( a[j*gsize:(j+1)*gsize], gsize)
-     msb := getMsb(k_ext[j*gsize:(j+1)*gsize])
+	for j := 0; j < ntables-1; j++ {
+		table.NewTableG1(a[j*gsize:(j+1)*gsize], gsize, false)
+		msb := getMsb(k_ext[j*gsize : (j+1)*gsize])
 
-     for i := msb-1; i >= 0; i-- {
-        b := getBit(k_ext[j*gsize:(j+1)*gsize],i)
+		for i := msb - 1; i >= 0; i-- {
+			b := getBit(k_ext[j*gsize:(j+1)*gsize], i)
 			if b != 0 {
 				// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
 				Q[i].Add(Q[i], table.data[b])
 			}
 		}
 	}
-   table.NewTableG1( a[(ntables-1)*gsize:], gsize)
+	table.NewTableG1(a[(ntables-1)*gsize:], gsize, false)
 	msb := getMsb(k_ext[(ntables-1)*gsize:])
 
-   for i := msb-1; i >= 0; i-- {
-     b := getBit(k_ext[(ntables-1)*gsize:],i)
+	for i := msb - 1; i >= 0; i-- {
+		b := getBit(k_ext[(ntables-1)*gsize:], i)
 		if b != 0 {
 			// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
 			Q[i].Add(Q[i], table.data[b])
@@ -198,13 +211,13 @@ func ScalarMultNoDoubleG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize i
 
 	// Consolidate Addition
 	R := new(bn256.G1).Set(Q[nbitsQ-1])
-   for i:=nbitsQ-1; i>0; i-- {
+	for i := nbitsQ - 1; i > 0; i-- {
 		// TODO. bn256 doesn't export double operation. We will need to fork repo and export it
-      R = new(bn256.G1).Add(R,R)
-      R.Add(R,Q[i-1])
+		R = new(bn256.G1).Add(R, R)
+		R.Add(R, Q[i-1])
 	}
 	if Q_prev != nil {
-     return R.Add(R,Q_prev)
+		return R.Add(R, Q_prev)
 	} else {
 		return R
 	}
@@ -215,16 +228,14 @@ func ScalarMultNoDoubleG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize i
 // TODO - How can avoid replicating code in G2?
 //G2
 
-type TableG2 struct{
+type TableG2 struct {
 	data []*bn256.G2
 }
 
-
 func (t TableG2) GetData() []*bn256.G2 {
 	return t.data
 }
 
-
 // Compute table of gsize elements as ::
 //  Table[0] = Inf
 //  Table[1] = a[0]
@@ -232,7 +243,8 @@ func (t TableG2) GetData() []*bn256.G2 {
 //  Table[3] = a[0]+a[1]
 //  .....
 //  Table[(1<<gsize)-1] = a[0]+a[1]+...+a[gsize-1]
-func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int){
+// TODO -> toaffine = True doesnt work. Problem with Marshal/Unmarshal
+func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int, toaffine bool) {
 	// EC table
 	table := make([]*bn256.G2, 0)
 
@@ -240,18 +252,18 @@ func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int){
 	a_ext := make([]*bn256.G2, 0)
 	a_ext = append(a_ext, a...)
 
-   for i:=len(a); i<gsize; i++ {
-      a_ext = append(a_ext,new(bn256.G2).ScalarBaseMult(big.NewInt(0)))
+	for i := len(a); i < gsize; i++ {
+		a_ext = append(a_ext, new(bn256.G2).ScalarBaseMult(big.NewInt(0)))
 	}
 
 	elG2 := new(bn256.G2).ScalarBaseMult(big.NewInt(0))
-   table = append(table,elG2)
+	table = append(table, elG2)
 	last_pow2 := 1
 	nelems := 0
-   for i :=1; i< 1<<gsize; i++ {
+	for i := 1; i < 1<<gsize; i++ {
 		elG2 := new(bn256.G2)
 		// if power of 2
-      if i & (i-1) == 0{
+		if i&(i-1) == 0 {
 			last_pow2 = i
 			elG2.Set(a_ext[nelems])
 			nelems++
@@ -262,27 +274,42 @@ func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int){
 		}
 		table = append(table, elG2)
 	}
+	if toaffine {
+		for i := 0; i < len(table); i++ {
+			info := table[i].Marshal()
+			table[i].Unmarshal(info)
+		}
+	}
 	t.data = table
 }
 
+func (t TableG2) Marshal() []byte {
+	info := make([]byte, 0)
+	for _, el := range t.data {
+		info = append(info, el.Marshal()...)
+	}
+
+	return info
+}
+
 // Multiply scalar by precomputed table of G2 elements
 func (t *TableG2) MulTableG2(k []*big.Int, Q_prev *bn256.G2, gsize int) *bn256.G2 {
 	// We need at least gsize elements. If not enough, fill with 0
 	k_ext := make([]*big.Int, 0)
 	k_ext = append(k_ext, k...)
 
-   for i:=len(k); i < gsize; i++ {
-      k_ext = append(k_ext,new(big.Int).SetUint64(0))
+	for i := len(k); i < gsize; i++ {
+		k_ext = append(k_ext, new(big.Int).SetUint64(0))
 	}
 
 	Q := new(bn256.G2).ScalarBaseMult(big.NewInt(0))
 
 	msb := getMsb(k_ext)
 
-   for i := msb-1; i >= 0; i-- {
+	for i := msb - 1; i >= 0; i-- {
 		// TODO. bn256 doesn't export double operation. We will need to fork repo and export it
-	Q = new(bn256.G2).Add(Q,Q)
-        b := getBit(k_ext,i)
+		Q = new(bn256.G2).Add(Q, Q)
+		b := getBit(k_ext, i)
 		if b != 0 {
 			// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
 			Q.Add(Q, t.data[b])
@@ -302,22 +329,22 @@ func MulTableNoDoubleG2(t []TableG2, k []*big.Int, Q_prev *bn256.G2, gsize int)
 	k_ext := make([]*big.Int, 0)
 	k_ext = append(k_ext, k...)
 	for i := len(k); i < min_nelems; i++ {
-      k_ext = append(k_ext,new(big.Int).SetUint64(0))
+		k_ext = append(k_ext, new(big.Int).SetUint64(0))
 	}
 	// Init Adders
 	nbitsQ := cryptoConstants.Q.BitLen()
-   Q := make([]*bn256.G2,nbitsQ)
+	Q := make([]*bn256.G2, nbitsQ)
 
-   for i:=0; i< nbitsQ; i++ {
+	for i := 0; i < nbitsQ; i++ {
 		Q[i] = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
 	}
 
 	// Perform bitwise addition
-   for j:=0; j < len(t); j++ {
-     msb := getMsb(k_ext[j*gsize:(j+1)*gsize])
+	for j := 0; j < len(t); j++ {
+		msb := getMsb(k_ext[j*gsize : (j+1)*gsize])
 
-     for i := msb-1; i >= 0; i-- {
-        b := getBit(k_ext[j*gsize:(j+1)*gsize],i)
+		for i := msb - 1; i >= 0; i-- {
+			b := getBit(k_ext[j*gsize:(j+1)*gsize], i)
 			if b != 0 {
 				// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
 				Q[i].Add(Q[i], t[j].data[b])
@@ -327,13 +354,13 @@ func MulTableNoDoubleG2(t []TableG2, k []*big.Int, Q_prev *bn256.G2, gsize int)
 
 	// Consolidate Addition
 	R := new(bn256.G2).Set(Q[nbitsQ-1])
-   for i:=nbitsQ-1; i>0; i-- {
+	for i := nbitsQ - 1; i > 0; i-- {
 		// TODO. bn256 doesn't export double operation. We will need to fork repo and export it
-      R = new(bn256.G2).Add(R,R)
-      R.Add(R,Q[i-1])
+		R = new(bn256.G2).Add(R, R)
+		R.Add(R, Q[i-1])
 	}
 	if Q_prev != nil {
-     return R.Add(R,Q_prev)
+		return R.Add(R, Q_prev)
 	} else {
 		return R
 	}
@@ -344,17 +371,17 @@ func MulTableNoDoubleG2(t []TableG2, k []*big.Int, Q_prev *bn256.G2, gsize int)
 func ScalarMultG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize int) *bn256.G2 {
 	ntables := int((len(a) + gsize - 1) / gsize)
 	table := TableG2{}
-     Q:= new(bn256.G2).ScalarBaseMult(new(big.Int))
+	Q := new(bn256.G2).ScalarBaseMult(new(big.Int))
 
-     for i:=0; i<ntables-1; i++ {
-       table.NewTableG2( a[i*gsize:(i+1)*gsize], gsize)
+	for i := 0; i < ntables-1; i++ {
+		table.NewTableG2(a[i*gsize:(i+1)*gsize], gsize, false)
 		Q = table.MulTableG2(k[i*gsize:(i+1)*gsize], Q, gsize)
 	}
-     table.NewTableG2( a[(ntables-1)*gsize:], gsize)
+	table.NewTableG2(a[(ntables-1)*gsize:], gsize, false)
 	Q = table.MulTableG2(k[(ntables-1)*gsize:], Q, gsize)
 
 	if Q_prev != nil {
-       return Q.Add(Q,Q_prev)
+		return Q.Add(Q, Q_prev)
 	} else {
 		return Q
 	}
@@ -370,34 +397,34 @@ func ScalarMultNoDoubleG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize i
 	k_ext := make([]*big.Int, 0)
 	k_ext = append(k_ext, k...)
 	for i := len(k); i < min_nelems; i++ {
-      k_ext = append(k_ext,new(big.Int).SetUint64(0))
+		k_ext = append(k_ext, new(big.Int).SetUint64(0))
 	}
 	// Init Adders
 	nbitsQ := cryptoConstants.Q.BitLen()
-   Q := make([]*bn256.G2,nbitsQ)
+	Q := make([]*bn256.G2, nbitsQ)
 
-   for i:=0; i< nbitsQ; i++ {
+	for i := 0; i < nbitsQ; i++ {
 		Q[i] = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
 	}
 
 	// Perform bitwise addition
-   for j:=0; j < ntables-1; j++ {
-     table.NewTableG2( a[j*gsize:(j+1)*gsize], gsize)
-     msb := getMsb(k_ext[j*gsize:(j+1)*gsize])
+	for j := 0; j < ntables-1; j++ {
+		table.NewTableG2(a[j*gsize:(j+1)*gsize], gsize, false)
+		msb := getMsb(k_ext[j*gsize : (j+1)*gsize])
 
-     for i := msb-1; i >= 0; i-- {
-        b := getBit(k_ext[j*gsize:(j+1)*gsize],i)
+		for i := msb - 1; i >= 0; i-- {
+			b := getBit(k_ext[j*gsize:(j+1)*gsize], i)
 			if b != 0 {
 				// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
 				Q[i].Add(Q[i], table.data[b])
 			}
 		}
 	}
-   table.NewTableG2( a[(ntables-1)*gsize:], gsize)
+	table.NewTableG2(a[(ntables-1)*gsize:], gsize, false)
 	msb := getMsb(k_ext[(ntables-1)*gsize:])
 
-   for i := msb-1; i >= 0; i-- {
-     b := getBit(k_ext[(ntables-1)*gsize:],i)
+	for i := msb - 1; i >= 0; i-- {
+		b := getBit(k_ext[(ntables-1)*gsize:], i)
 		if b != 0 {
 			// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
 			Q[i].Add(Q[i], table.data[b])
@@ -406,23 +433,23 @@ func ScalarMultNoDoubleG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize i
 
 	// Consolidate Addition
 	R := new(bn256.G2).Set(Q[nbitsQ-1])
-   for i:=nbitsQ-1; i>0; i-- {
+	for i := nbitsQ - 1; i > 0; i-- {
 		// TODO. bn256 doesn't export double operation. We will need to fork repo and export it
-      R = new(bn256.G2).Add(R,R)
-      R.Add(R,Q[i-1])
+		R = new(bn256.G2).Add(R, R)
+		R.Add(R, Q[i-1])
 	}
 	if Q_prev != nil {
-     return R.Add(R,Q_prev)
+		return R.Add(R, Q_prev)
 	} else {
 		return R
 	}
 }
 
 // Return most significant bit position in a group of Big Integers
-func getMsb(k []*big.Int) int{
+func getMsb(k []*big.Int) int {
 	msb := 0
 
-  for _, el := range(k){
+	for _, el := range k {
 		tmp_msb := el.BitLen()
 		if tmp_msb > msb {
 			msb = tmp_msb
@@ -435,7 +462,7 @@ func getMsb(k []*big.Int) int{
 func getBit(k []*big.Int, i int) uint {
 	table_idx := uint(0)
 
-   for idx, el := range(k){
+	for idx, el := range k {
 		b := el.Bit(i)
 		table_idx += (b << idx)
 	}

prover/gextra_test.go

@@ -1,13 +1,13 @@
 package prover
 
 import (
+	"bytes"
 	"crypto/rand"
+	"fmt"
+	bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
 	"math/big"
 	"testing"
-	bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
 	"time"
-        "bytes"
-        "fmt"
 )
 
 const (
@@ -15,7 +15,7 @@ const (
 	N2 = 5000
 )
 
-func randomBigIntArray(n int) []*big.Int{
+func randomBigIntArray(n int) []*big.Int {
 	var p []*big.Int
 	for i := 0; i < n; i++ {
 		pi := randBI()
@@ -28,7 +28,7 @@ func randomBigIntArray(n int) []*big.Int{
 func randomG1Array(n int) []*bn256.G1 {
 	arrayG1 := make([]*bn256.G1, n)
 
-     for i:=0; i<n; i++ {
+	for i := 0; i < n; i++ {
 		_, arrayG1[i], _ = bn256.RandomG1(rand.Reader)
 	}
 	return arrayG1
@@ -37,15 +37,13 @@ func randomG1Array(n int) []*bn256.G1 {
 func randomG2Array(n int) []*bn256.G2 {
 	arrayG2 := make([]*bn256.G2, n)
 
-     for i:=0; i<n; i++ {
+	for i := 0; i < n; i++ {
 		_, arrayG2[i], _ = bn256.RandomG2(rand.Reader)
 	}
 	return arrayG2
 }
 
-
-
-func TestTableG1(t *testing.T){
+func TestTableG1(t *testing.T) {
 	n := N1
 
 	// init scalar
@@ -55,57 +53,56 @@ func TestTableG1(t *testing.T){
 
 	beforeT := time.Now()
 	Q1 := new(bn256.G1).ScalarBaseMult(new(big.Int))
-     for i:=0; i < n; i++ {
+	for i := 0; i < n; i++ {
 		Q1.Add(Q1, new(bn256.G1).ScalarMult(arrayG1[i], arrayW[i]))
 	}
 	fmt.Println("Std. Mult. time elapsed:", time.Since(beforeT))
 
-     for gsize:=2; gsize < 10; gsize++ {
+	for gsize := 2; gsize < 10; gsize++ {
 		ntables := int((n + gsize - 1) / gsize)
 		table := make([]TableG1, ntables)
 
-        for i:=0; i<ntables-1; i++ {
-          table[i].NewTableG1( arrayG1[i*gsize:(i+1)*gsize], gsize)
+		for i := 0; i < ntables-1; i++ {
+			table[i].NewTableG1(arrayG1[i*gsize:(i+1)*gsize], gsize, true)
 		}
-        table[ntables-1].NewTableG1( arrayG1[(ntables-1)*gsize:], gsize)
+		table[ntables-1].NewTableG1(arrayG1[(ntables-1)*gsize:], gsize, true)
 
 		beforeT = time.Now()
-        Q2:= new(bn256.G1).ScalarBaseMult(new(big.Int))
-        for i:=0; i<ntables-1; i++ {
+		Q2 := new(bn256.G1).ScalarBaseMult(new(big.Int))
+		for i := 0; i < ntables-1; i++ {
 			Q2 = table[i].MulTableG1(arrayW[i*gsize:(i+1)*gsize], Q2, gsize)
 		}
 		Q2 = table[ntables-1].MulTableG1(arrayW[(ntables-1)*gsize:], Q2, gsize)
-        fmt.Printf("Gsize : %d, TMult time elapsed: %s\n", gsize,time.Since(beforeT))
+		fmt.Printf("Gsize : %d, TMult time elapsed: %s\n", gsize, time.Since(beforeT))
 
 		beforeT = time.Now()
 		Q3 := ScalarMultG1(arrayG1, arrayW, nil, gsize)
-        fmt.Printf("Gsize : %d, TMult time elapsed (inc table comp): %s\n", gsize,time.Since(beforeT))
+		fmt.Printf("Gsize : %d, TMult time elapsed (inc table comp): %s\n", gsize, time.Since(beforeT))
 
 		beforeT = time.Now()
 		Q4 := MulTableNoDoubleG1(table, arrayW, nil, gsize)
-        fmt.Printf("Gsize : %d, TMultNoDouble time elapsed: %s\n", gsize,time.Since(beforeT))
+		fmt.Printf("Gsize : %d, TMultNoDouble time elapsed: %s\n", gsize, time.Since(beforeT))
 
 		beforeT = time.Now()
 		Q5 := ScalarMultNoDoubleG1(arrayG1, arrayW, nil, gsize)
-        fmt.Printf("Gsize : %d, TMultNoDouble time elapsed (inc table comp): %s\n", gsize,time.Since(beforeT))
+		fmt.Printf("Gsize : %d, TMultNoDouble time elapsed (inc table comp): %s\n", gsize, time.Since(beforeT))
 
-
-        if bytes.Compare(Q1.Marshal(),Q2.Marshal()) != 0 {
+		if bytes.Compare(Q1.Marshal(), Q2.Marshal()) != 0 {
 			t.Error("Error in TMult")
 		}
-        if bytes.Compare(Q1.Marshal(),Q3.Marshal()) != 0 {
+		if bytes.Compare(Q1.Marshal(), Q3.Marshal()) != 0 {
 			t.Error("Error in  TMult with table comp")
 		}
-        if bytes.Compare(Q1.Marshal(),Q4.Marshal()) != 0 {
+		if bytes.Compare(Q1.Marshal(), Q4.Marshal()) != 0 {
 			t.Error("Error in  TMultNoDouble")
 		}
-        if bytes.Compare(Q1.Marshal(),Q5.Marshal()) != 0 {
+		if bytes.Compare(Q1.Marshal(), Q5.Marshal()) != 0 {
 			t.Error("Error in  TMultNoDoublee with table comp")
 		}
 	}
 }
 
-func TestTableG2(t *testing.T){
+func TestTableG2(t *testing.T) {
 	n := N2
 
 	// init scalar
@@ -115,51 +112,50 @@ func TestTableG2(t *testing.T){
 
 	beforeT := time.Now()
 	Q1 := new(bn256.G2).ScalarBaseMult(new(big.Int))
-     for i:=0; i < n; i++ {
+	for i := 0; i < n; i++ {
 		Q1.Add(Q1, new(bn256.G2).ScalarMult(arrayG2[i], arrayW[i]))
 	}
 	fmt.Println("Std. Mult. time elapsed:", time.Since(beforeT))
 
-     for gsize:=2; gsize < 10; gsize++ {
+	for gsize := 2; gsize < 10; gsize++ {
 		ntables := int((n + gsize - 1) / gsize)
 		table := make([]TableG2, ntables)
 
-        for i:=0; i<ntables-1; i++ {
-          table[i].NewTableG2( arrayG2[i*gsize:(i+1)*gsize], gsize)
+		for i := 0; i < ntables-1; i++ {
+			table[i].NewTableG2(arrayG2[i*gsize:(i+1)*gsize], gsize, false)
 		}
-        table[ntables-1].NewTableG2( arrayG2[(ntables-1)*gsize:], gsize)
+		table[ntables-1].NewTableG2(arrayG2[(ntables-1)*gsize:], gsize, false)
 
 		beforeT = time.Now()
-        Q2:= new(bn256.G2).ScalarBaseMult(new(big.Int))
-        for i:=0; i<ntables-1; i++ {
-           Q2 =table[i].MulTableG2(arrayW[i*gsize:(i+1)*gsize], Q2, gsize)
+		Q2 := new(bn256.G2).ScalarBaseMult(new(big.Int))
+		for i := 0; i < ntables-1; i++ {
+			Q2 = table[i].MulTableG2(arrayW[i*gsize:(i+1)*gsize], Q2, gsize)
 		}
 		Q2 = table[ntables-1].MulTableG2(arrayW[(ntables-1)*gsize:], Q2, gsize)
-        fmt.Printf("Gsize : %d, TMult time elapsed: %s\n", gsize,time.Since(beforeT))
+		fmt.Printf("Gsize : %d, TMult time elapsed: %s\n", gsize, time.Since(beforeT))
 
 		beforeT = time.Now()
 		Q3 := ScalarMultG2(arrayG2, arrayW, nil, gsize)
-        fmt.Printf("Gsize : %d, TMult time elapsed (inc table comp): %s\n", gsize,time.Since(beforeT))
+		fmt.Printf("Gsize : %d, TMult time elapsed (inc table comp): %s\n", gsize, time.Since(beforeT))
 
 		beforeT = time.Now()
 		Q4 := MulTableNoDoubleG2(table, arrayW, nil, gsize)
-        fmt.Printf("Gsize : %d, TMultNoDouble time elapsed: %s\n", gsize,time.Since(beforeT))
+		fmt.Printf("Gsize : %d, TMultNoDouble time elapsed: %s\n", gsize, time.Since(beforeT))
 
 		beforeT = time.Now()
 		Q5 := ScalarMultNoDoubleG2(arrayG2, arrayW, nil, gsize)
-        fmt.Printf("Gsize : %d, TMultNoDouble time elapsed (inc table comp): %s\n", gsize,time.Since(beforeT))
+		fmt.Printf("Gsize : %d, TMultNoDouble time elapsed (inc table comp): %s\n", gsize, time.Since(beforeT))
 
-
-        if bytes.Compare(Q1.Marshal(),Q2.Marshal()) != 0 {
+		if bytes.Compare(Q1.Marshal(), Q2.Marshal()) != 0 {
 			t.Error("Error in TMult")
 		}
-        if bytes.Compare(Q1.Marshal(),Q3.Marshal()) != 0 {
+		if bytes.Compare(Q1.Marshal(), Q3.Marshal()) != 0 {
 			t.Error("Error in  TMult with table comp")
 		}
-        if bytes.Compare(Q1.Marshal(),Q4.Marshal()) != 0 {
+		if bytes.Compare(Q1.Marshal(), Q4.Marshal()) != 0 {
 			t.Error("Error in  TMultNoDouble")
 		}
-        if bytes.Compare(Q1.Marshal(),Q5.Marshal()) != 0 {
+		if bytes.Compare(Q1.Marshal(), Q5.Marshal()) != 0 {
 			t.Error("Error in  TMultNoDoublee with table comp")
 		}
 	}

prover/tables.md

@@ -16,7 +16,7 @@ There may be some concern on the additional size of the tables since they need t
 
 
 | Algorithm (G1) | GS 2 | GS 3 | GS 4 | GS 5 | GS 6 | GS 7 | GS 8 | GS 9 | 
-|---|---|---|---|---|---|---|---|---|
+|---|---|---|--|---|---|---|---|---|
 | Naive | 6.63s | - | - | - | - | - |  - | - |
 | Strauss |  13.16s | 9.03s | 6.95s | 5.61s | 4.91s | 4.26s | 3.88s | 3.54 s |
 | Strauss + Table Computation | 16.13s | 11.32s | 8.47s | 7.10s | 6.2s | 5.94s | 6.01s | 6.69s |
@@ -26,7 +26,7 @@ There may be some concern on the additional size of the tables since they need t
 There are 5000 G2 Elliptical Curve Points, and the scalars are 254 bits (BN256 curve). 
 
 | Algorithm (G2) | GS 2 | GS 3 | GS 4 | GS 5 | GS 6 | GS 7 | GS 8 | GS 9 | 
-|---|---|---|---|---|---|---|---|---|
+|---|---|---|--|---|---|---|---|---|
 | Naive | 3.55s | | | | | | | |
 | Strauss |  3.55s | 2.54s | 1.96s | 1.58s |  1.38s | 1.20s | 1.03s | 937ms |
 | Strauss + Table Computation | 3.59s | 2.58s | 2.04s | 1.71s | 1.51s | 1.46s | 1.51s | 1.82s |

tables.md

@@ -1,25 +0,0 @@
-# Tables Pre-calculation
-The most time consuming part of a ZKSnark proof calculation is the scalar multiplication of elliptic curve points. Direct mechanism accumulates each multiplication. However, prover only needs the total accumulation.
-
-There are two potential improvements to the naive approach:
-
-1. Apply Strauss-Shamir method (https://stackoverflow.com/questions/50993471/ec-scalar-multiplication-with-strauss-shamir-method).
-2. Leave the doubling operation for the last step
-
-Both options can be combined. 
-
-In the following table, we show the results of using the naive method, Srauss-Shamir and Strauss-Shamir + No doubling. These last two options are repeated for different table grouping order.
-
-There are 5000 G1 Elliptical Curve Points, and the scalars are 254 bits (BN256 curve). 
-
-There may be some concern on the additional size of the tables since they need to be loaded into a smartphone during the proof, and the time required to load these tables may exceed the benefits. If this is a problem, another althernative is to compute the tables during the proof itself. Depending on the Group Size, timing may be better than the naive approach.
-
-
-| Algorithm | GS / Time |
-|---|---|---|
-| Naive | 6.63s | | | | | | | |
-| Strauss |  13.16s | 9.033s | 6.95s | 5.61s | 4.91s | 4.26s | 3.88s | 3.54 s | 1.44 s |
-| Strauss + Table Computation | 16.13s | 11.32s | 8.47s | 7.10s | 6.2s | 5.94s | 6.01s | 6.69s |
-| No Doubling | 3.74s | 3.00s | 2.38s | 1.96s | 1.79s | 1.54s | 1.50s | 1.44s|
-| No Doubling + Table Computation  | 6.83s | 5.1s | 4.16s | 3.52s| 3.22s | 3.21s | 3.57s | 4.56s |
-