reduced test time

Leave prover_test untouched
Update tables.md
2026-02-07 11:26:44 +01:00 · 2020-05-03 20:17:57 +02:00 · 2020-05-03 20:07:39 +02:00 · 2020-05-03 19:58:04 +02:00 · 2020-05-03 19:53:52 +02:00 · 2020-05-03 19:51:02 +02:00
4 changed files with 468 additions and 466 deletions
--- a/prover/gextra.go
+++ b/prover/gextra.go
@@ -1,19 +1,21 @@
 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]
@@ -21,7 +23,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, toaffine bool) {
+func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int){
   // EC table
   table := make([]*bn256.G1, 0)

@@ -29,18 +31,18 @@ func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int, toaffine bool) {
   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++
@@ -51,49 +53,34 @@ func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int, toaffine bool) {
      }
      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
   }
@@ -106,22 +93,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])
@@ -131,14 +118,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
   }
@@ -149,17 +136,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, false)
+     for i:=0; i<ntables-1; i++ {
+       table.NewTableG1( a[i*gsize:(i+1)*gsize], gsize)
       Q = table.MulTableG1(k[i*gsize:(i+1)*gsize], Q, gsize)
     }
-	table.NewTableG1(a[(ntables-1)*gsize:], gsize, false)
+     table.NewTableG1( a[(ntables-1)*gsize:], gsize)
     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
     }
@@ -175,34 +162,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, false)
-		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)
+     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, false)
+   table.NewTableG1( a[(ntables-1)*gsize:], gsize)
   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])
@@ -211,13 +198,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
   }
@@ -228,14 +215,16 @@ 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]
@@ -243,8 +232,7 @@ func (t TableG2) GetData() []*bn256.G2 {
 //  Table[3] = a[0]+a[1]
 //  .....
 //  Table[(1<<gsize)-1] = a[0]+a[1]+...+a[gsize-1]
-// TODO -> toaffine = True doesnt work. Problem with Marshal/Unmarshal
-func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int, toaffine bool) {
+func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int){
   // EC table
   table := make([]*bn256.G2, 0)

@@ -252,18 +240,18 @@ func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int, toaffine bool) {
   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++
@@ -274,42 +262,27 @@ func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int, toaffine bool) {
      }
      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])
@@ -329,22 +302,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])
@@ -354,13 +327,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
   }
@@ -371,17 +344,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, false)
+     for i:=0; i<ntables-1; i++ {
+       table.NewTableG2( a[i*gsize:(i+1)*gsize], gsize)
       Q = table.MulTableG2(k[i*gsize:(i+1)*gsize], Q, gsize)
     }
-	table.NewTableG2(a[(ntables-1)*gsize:], gsize, false)
+     table.NewTableG2( a[(ntables-1)*gsize:], gsize)
     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
     }
@@ -397,34 +370,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, false)
-		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)
+     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, false)
+   table.NewTableG2( a[(ntables-1)*gsize:], gsize)
   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])
@@ -433,23 +406,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
@@ -462,7 +435,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)
   }
--- a/prover/gextra_test.go
+++ b/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,13 +37,15 @@ 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
@@ -53,56 +55,57 @@ 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, true)
+        for i:=0; i<ntables-1; i++ {
+          table[i].NewTableG1( arrayG1[i*gsize:(i+1)*gsize], gsize)
        }
-		table[ntables-1].NewTableG1(arrayG1[(ntables-1)*gsize:], gsize, true)
+        table[ntables-1].NewTableG1( arrayG1[(ntables-1)*gsize:], gsize)

        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
@@ -112,50 +115,51 @@ 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, false)
+        for i:=0; i<ntables-1; i++ {
+          table[i].NewTableG2( arrayG2[i*gsize:(i+1)*gsize], gsize)
        }
-		table[ntables-1].NewTableG2(arrayG2[(ntables-1)*gsize:], gsize, false)
+        table[ntables-1].NewTableG2( arrayG2[(ntables-1)*gsize:], gsize)

        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")
        }
    }
--- a/prover/tables.md
+++ b/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 |
--- a/tables.md
+++ b/tables.md
@@ -0,0 +1,25 @@
+# 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 |
+
Author	SHA1	Message	Date
druiz0992	86621a0dbe	reduced test time	2020-05-03 20:17:57 +02:00
druiz0992	9ed6e14fad	Leave prover_test untouched	2020-05-03 20:07:39 +02:00
druiz0992	2d45cb7039	Update tables.md	2020-05-03 19:58:04 +02:00
druiz0992	68b0c2fb54	Fixed merge conflicts	2020-05-03 19:53:52 +02:00
druiz0992	e3b5f88660	Added G2 and included tables to prover	2020-05-03 19:51:02 +02:00
druiz0992	36b48215f0	Update tables.md	2020-05-03 03:39:22 +02:00
druiz0992	a110eb4ca1	Update tables.md	2020-05-03 03:32:23 +02:00
druiz0992	72913bc801	Added a description file	2020-05-03 03:30:52 +02:00
druiz0992	8c81f5041e	G1 Functionality to precomput G1 tables	2020-05-03 03:02:49 +02:00