reduced test time

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{
    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)
 
@@ -51,24 +53,9 @@ 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
@@ -152,10 +139,10 @@ func ScalarMultG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize int) *bn2
      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)
+       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 {
@@ -187,7 +174,7 @@ func ScalarMultNoDoubleG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize i
 
    // Perform bitwise addition
    for j:=0; j < ntables-1; j++ {
-		table.NewTableG1(a[j*gsize:(j+1)*gsize], gsize, false)
+     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-- {
@@ -198,7 +185,7 @@ func ScalarMultNoDoubleG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize i
 	}
      }
    }
-	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-- {
@@ -232,10 +219,12 @@ 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){
-func (t *TableG2) NewTableG2(a []*bn256.G2, gsize int, toaffine bool) {
    // EC table
    table := make([]*bn256.G2, 0)
 
@@ -274,24 +262,9 @@ 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
@@ -374,10 +347,10 @@ func ScalarMultG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize int) *bn2
      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)
+       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 {
@@ -409,7 +382,7 @@ func ScalarMultNoDoubleG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize i
 
    // Perform bitwise addition
    for j:=0; j < ntables-1; j++ {
-		table.NewTableG2(a[j*gsize:(j+1)*gsize], gsize, false)
+     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-- {
@@ -420,7 +393,7 @@ func ScalarMultNoDoubleG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize i
 	}
      }
    }
-	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-- {
@@ -449,7 +422,7 @@ func ScalarMultNoDoubleG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize i
 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)
    }

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 (
@@ -43,6 +43,8 @@ func randomG2Array(n int) []*bn256.G2 {
      return arrayG2
 }
 
+
+
 func TestTableG1(t *testing.T){
      n     := N1
 
@@ -63,9 +65,9 @@ func TestTableG1(t *testing.T) {
         table := make([]TableG1, ntables)
 
         for i:=0; i<ntables-1; i++ {
-			table[i].NewTableG1(arrayG1[i*gsize:(i+1)*gsize], gsize, true)
+          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))
@@ -87,6 +89,7 @@ func TestTableG1(t *testing.T) {
         Q5 := ScalarMultNoDoubleG1(arrayG1, arrayW, nil, gsize)
         fmt.Printf("Gsize : %d, TMultNoDouble time elapsed (inc table comp): %s\n", gsize,time.Since(beforeT))
 
+
         if bytes.Compare(Q1.Marshal(),Q2.Marshal()) != 0 {
             t.Error("Error in TMult")
         }
@@ -122,9 +125,9 @@ func TestTableG2(t *testing.T) {
         table := make([]TableG2, ntables)
 
         for i:=0; i<ntables-1; i++ {
-			table[i].NewTableG2(arrayG2[i*gsize:(i+1)*gsize], gsize, false)
+          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))
@@ -146,6 +149,7 @@ func TestTableG2(t *testing.T) {
         Q5 := ScalarMultNoDoubleG2(arrayG2, arrayW, nil, gsize)
         fmt.Printf("Gsize : %d, TMultNoDouble time elapsed (inc table comp): %s\n", gsize,time.Since(beforeT))
 
+
         if bytes.Compare(Q1.Marshal(),Q2.Marshal()) != 0 {
             t.Error("Error in TMult")
         }

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

@@ -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 |
+