mirror of
https://github.com/arnaucube/go-circom-prover-verifier.git
synced 2026-02-07 11:26:44 +01:00
Compare commits
1 Commits
feature/ta
...
feature/ta
| Author | SHA1 | Date | |
|---|---|---|---|
|
423d5f0ce7 |
697
prover/gextra.go
697
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{
|
||||
data []*bn256.G1
|
||||
type TableG1 struct {
|
||||
data []*bn256.G1
|
||||
}
|
||||
|
||||
|
||||
func (t TableG1) GetData() []*bn256.G1 {
|
||||
return t.data
|
||||
return t.data
|
||||
}
|
||||
|
||||
|
||||
// Compute table of gsize elements as ::
|
||||
// Table[0] = Inf
|
||||
// Table[1] = a[0]
|
||||
@@ -23,191 +21,206 @@ 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){
|
||||
// EC table
|
||||
table := make([]*bn256.G1, 0)
|
||||
func (t *TableG1) NewTableG1(a []*bn256.G1, gsize int, toaffine bool) {
|
||||
// EC table
|
||||
table := make([]*bn256.G1, 0)
|
||||
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
a_ext := make([]*bn256.G1, 0)
|
||||
a_ext = append(a_ext, a...)
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
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)
|
||||
last_pow2 := 1
|
||||
nelems := 0
|
||||
for i :=1; i< 1<<gsize; i++ {
|
||||
elG1 := new(bn256.G1)
|
||||
// if power of 2
|
||||
if i & (i-1) == 0{
|
||||
last_pow2 = i
|
||||
elG1.Set(a_ext[nelems])
|
||||
nelems++
|
||||
} else {
|
||||
elG1.Add(table[last_pow2], table[i-last_pow2])
|
||||
// TODO bn256 doesn't export MakeAffine function. We need to fork repo
|
||||
//table[i].MakeAffine()
|
||||
}
|
||||
table = append(table, elG1)
|
||||
}
|
||||
t.data = table
|
||||
elG1 := new(bn256.G1).ScalarBaseMult(big.NewInt(0))
|
||||
table = append(table, elG1)
|
||||
last_pow2 := 1
|
||||
nelems := 0
|
||||
for i := 1; i < 1<<gsize; i++ {
|
||||
elG1 := new(bn256.G1)
|
||||
// if power of 2
|
||||
if i&(i-1) == 0 {
|
||||
last_pow2 = i
|
||||
elG1.Set(a_ext[nelems])
|
||||
nelems++
|
||||
} else {
|
||||
elG1.Add(table[last_pow2], table[i-last_pow2])
|
||||
// TODO bn256 doesn't export MakeAffine function. We need to fork repo
|
||||
//table[i].MakeAffine()
|
||||
}
|
||||
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...)
|
||||
// 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))
|
||||
}
|
||||
|
||||
Q := new(bn256.G1).ScalarBaseMult(big.NewInt(0))
|
||||
|
||||
msb := getMsb(k_ext)
|
||||
|
||||
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)
|
||||
if b != 0 {
|
||||
// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
|
||||
Q.Add(Q, t.data[b])
|
||||
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-- {
|
||||
// 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)
|
||||
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)
|
||||
} else {
|
||||
return Q
|
||||
}
|
||||
}
|
||||
if Q_prev != nil {
|
||||
return Q.Add(Q,Q_prev)
|
||||
} else {
|
||||
return Q
|
||||
}
|
||||
}
|
||||
|
||||
// Multiply scalar by precomputed table of G1 elements without intermediate doubling
|
||||
func MulTableNoDoubleG1(t []TableG1, k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
min_nelems := len(t) * gsize
|
||||
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))
|
||||
}
|
||||
// Init Adders
|
||||
nbitsQ := cryptoConstants.Q.BitLen()
|
||||
Q := make([]*bn256.G1,nbitsQ)
|
||||
|
||||
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 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])
|
||||
func MulTableNoDoubleG1(t []TableG1, k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
min_nelems := len(t) * gsize
|
||||
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))
|
||||
}
|
||||
}
|
||||
}
|
||||
// Init Adders
|
||||
nbitsQ := cryptoConstants.Q.BitLen()
|
||||
Q := make([]*bn256.G1, nbitsQ)
|
||||
|
||||
// Consolidate Addition
|
||||
R := new(bn256.G1).Set(Q[nbitsQ-1])
|
||||
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])
|
||||
}
|
||||
for i := 0; i < nbitsQ; i++ {
|
||||
Q[i] = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
|
||||
}
|
||||
|
||||
if Q_prev != nil {
|
||||
return R.Add(R,Q_prev)
|
||||
} else {
|
||||
return R
|
||||
}
|
||||
// Perform bitwise addition
|
||||
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)
|
||||
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])
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// Consolidate Addition
|
||||
R := new(bn256.G1).Set(Q[nbitsQ-1])
|
||||
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])
|
||||
}
|
||||
|
||||
if Q_prev != nil {
|
||||
return R.Add(R, Q_prev)
|
||||
} else {
|
||||
return R
|
||||
}
|
||||
}
|
||||
|
||||
// Compute tables within function. This solution should still be faster than std multiplication
|
||||
// for gsize = 7
|
||||
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))
|
||||
ntables := int((len(a) + gsize - 1) / gsize)
|
||||
table := TableG1{}
|
||||
Q := new(bn256.G1).ScalarBaseMult(new(big.Int))
|
||||
|
||||
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)
|
||||
Q = table.MulTableG1(k[(ntables-1)*gsize:], Q, 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, false)
|
||||
Q = table.MulTableG1(k[(ntables-1)*gsize:], Q, gsize)
|
||||
|
||||
if Q_prev != nil {
|
||||
return Q.Add(Q,Q_prev)
|
||||
} else {
|
||||
return Q
|
||||
}
|
||||
if Q_prev != nil {
|
||||
return Q.Add(Q, Q_prev)
|
||||
} else {
|
||||
return Q
|
||||
}
|
||||
}
|
||||
|
||||
// Multiply scalar by precomputed table of G1 elements without intermediate doubling
|
||||
func ScalarMultNoDoubleG1(a []*bn256.G1, k []*big.Int, Q_prev *bn256.G1, gsize int) *bn256.G1 {
|
||||
ntables := int((len(a) + gsize - 1) / gsize)
|
||||
table := TableG1{}
|
||||
ntables := int((len(a) + gsize - 1) / gsize)
|
||||
table := TableG1{}
|
||||
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
min_nelems := ntables * gsize
|
||||
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))
|
||||
}
|
||||
// Init Adders
|
||||
nbitsQ := cryptoConstants.Q.BitLen()
|
||||
Q := make([]*bn256.G1,nbitsQ)
|
||||
|
||||
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 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])
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
min_nelems := ntables * gsize
|
||||
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))
|
||||
}
|
||||
}
|
||||
}
|
||||
table.NewTableG1( a[(ntables-1)*gsize:], gsize)
|
||||
msb := getMsb(k_ext[(ntables-1)*gsize:])
|
||||
// Init Adders
|
||||
nbitsQ := cryptoConstants.Q.BitLen()
|
||||
Q := make([]*bn256.G1, nbitsQ)
|
||||
|
||||
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])
|
||||
}
|
||||
}
|
||||
for i := 0; i < nbitsQ; i++ {
|
||||
Q[i] = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
|
||||
}
|
||||
|
||||
// Consolidate Addition
|
||||
R := new(bn256.G1).Set(Q[nbitsQ-1])
|
||||
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])
|
||||
}
|
||||
if Q_prev != nil {
|
||||
return R.Add(R,Q_prev)
|
||||
} else {
|
||||
return R
|
||||
}
|
||||
// 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 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)
|
||||
msb := getMsb(k_ext[(ntables-1)*gsize:])
|
||||
|
||||
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])
|
||||
}
|
||||
}
|
||||
|
||||
// Consolidate Addition
|
||||
R := new(bn256.G1).Set(Q[nbitsQ-1])
|
||||
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])
|
||||
}
|
||||
if Q_prev != nil {
|
||||
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{
|
||||
data []*bn256.G2
|
||||
type TableG2 struct {
|
||||
data []*bn256.G2
|
||||
}
|
||||
|
||||
|
||||
func (t TableG2) GetData() []*bn256.G2 {
|
||||
return t.data
|
||||
return t.data
|
||||
}
|
||||
|
||||
|
||||
// Compute table of gsize elements as ::
|
||||
// Table[0] = Inf
|
||||
// Table[1] = a[0]
|
||||
@@ -232,212 +243,228 @@ 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){
|
||||
// EC table
|
||||
table := make([]*bn256.G2, 0)
|
||||
// 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)
|
||||
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
a_ext := make([]*bn256.G2, 0)
|
||||
a_ext = append(a_ext, a...)
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
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)
|
||||
last_pow2 := 1
|
||||
nelems := 0
|
||||
for i :=1; i< 1<<gsize; i++ {
|
||||
elG2 := new(bn256.G2)
|
||||
// if power of 2
|
||||
if i & (i-1) == 0{
|
||||
last_pow2 = i
|
||||
elG2.Set(a_ext[nelems])
|
||||
nelems++
|
||||
} else {
|
||||
elG2.Add(table[last_pow2], table[i-last_pow2])
|
||||
// TODO bn256 doesn't export MakeAffine function. We need to fork repo
|
||||
//table[i].MakeAffine()
|
||||
}
|
||||
table = append(table, elG2)
|
||||
}
|
||||
t.data = table
|
||||
elG2 := new(bn256.G2).ScalarBaseMult(big.NewInt(0))
|
||||
table = append(table, elG2)
|
||||
last_pow2 := 1
|
||||
nelems := 0
|
||||
for i := 1; i < 1<<gsize; i++ {
|
||||
elG2 := new(bn256.G2)
|
||||
// if power of 2
|
||||
if i&(i-1) == 0 {
|
||||
last_pow2 = i
|
||||
elG2.Set(a_ext[nelems])
|
||||
nelems++
|
||||
} else {
|
||||
elG2.Add(table[last_pow2], table[i-last_pow2])
|
||||
// TODO bn256 doesn't export MakeAffine function. We need to fork repo
|
||||
//table[i].MakeAffine()
|
||||
}
|
||||
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...)
|
||||
// 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))
|
||||
}
|
||||
|
||||
Q := new(bn256.G2).ScalarBaseMult(big.NewInt(0))
|
||||
|
||||
msb := getMsb(k_ext)
|
||||
|
||||
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)
|
||||
if b != 0 {
|
||||
// TODO. bn256 doesn't export mixed addition (Jacobian + Affine), which is more efficient.
|
||||
Q.Add(Q, t.data[b])
|
||||
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-- {
|
||||
// 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)
|
||||
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)
|
||||
} else {
|
||||
return Q
|
||||
}
|
||||
}
|
||||
if Q_prev != nil {
|
||||
return Q.Add(Q, Q_prev)
|
||||
} else {
|
||||
return Q
|
||||
}
|
||||
}
|
||||
|
||||
// Multiply scalar by precomputed table of G2 elements without intermediate doubling
|
||||
func MulTableNoDoubleG2(t []TableG2, k []*big.Int, Q_prev *bn256.G2, gsize int) *bn256.G2 {
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
min_nelems := len(t) * gsize
|
||||
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))
|
||||
}
|
||||
// Init Adders
|
||||
nbitsQ := cryptoConstants.Q.BitLen()
|
||||
Q := make([]*bn256.G2,nbitsQ)
|
||||
|
||||
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 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])
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
min_nelems := len(t) * gsize
|
||||
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))
|
||||
}
|
||||
}
|
||||
}
|
||||
// Init Adders
|
||||
nbitsQ := cryptoConstants.Q.BitLen()
|
||||
Q := make([]*bn256.G2, nbitsQ)
|
||||
|
||||
// Consolidate Addition
|
||||
R := new(bn256.G2).Set(Q[nbitsQ-1])
|
||||
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])
|
||||
}
|
||||
if Q_prev != nil {
|
||||
return R.Add(R,Q_prev)
|
||||
} else {
|
||||
return R
|
||||
}
|
||||
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 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])
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// Consolidate Addition
|
||||
R := new(bn256.G2).Set(Q[nbitsQ-1])
|
||||
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])
|
||||
}
|
||||
if Q_prev != nil {
|
||||
return R.Add(R, Q_prev)
|
||||
} else {
|
||||
return R
|
||||
}
|
||||
}
|
||||
|
||||
// Compute tables within function. This solution should still be faster than std multiplication
|
||||
// for gsize = 7
|
||||
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))
|
||||
ntables := int((len(a) + gsize - 1) / gsize)
|
||||
table := TableG2{}
|
||||
Q := new(bn256.G2).ScalarBaseMult(new(big.Int))
|
||||
|
||||
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)
|
||||
Q = table.MulTableG2(k[(ntables-1)*gsize:], Q, 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, false)
|
||||
Q = table.MulTableG2(k[(ntables-1)*gsize:], Q, gsize)
|
||||
|
||||
if Q_prev != nil {
|
||||
return Q.Add(Q,Q_prev)
|
||||
} else {
|
||||
return Q
|
||||
}
|
||||
if Q_prev != nil {
|
||||
return Q.Add(Q, Q_prev)
|
||||
} else {
|
||||
return Q
|
||||
}
|
||||
}
|
||||
|
||||
// Multiply scalar by precomputed table of G2 elements without intermediate doubling
|
||||
func ScalarMultNoDoubleG2(a []*bn256.G2, k []*big.Int, Q_prev *bn256.G2, gsize int) *bn256.G2 {
|
||||
ntables := int((len(a) + gsize - 1) / gsize)
|
||||
table := TableG2{}
|
||||
ntables := int((len(a) + gsize - 1) / gsize)
|
||||
table := TableG2{}
|
||||
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
min_nelems := ntables * gsize
|
||||
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))
|
||||
}
|
||||
// Init Adders
|
||||
nbitsQ := cryptoConstants.Q.BitLen()
|
||||
Q := make([]*bn256.G2,nbitsQ)
|
||||
|
||||
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 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])
|
||||
// We need at least gsize elements. If not enough, fill with 0
|
||||
min_nelems := ntables * gsize
|
||||
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))
|
||||
}
|
||||
}
|
||||
}
|
||||
table.NewTableG2( a[(ntables-1)*gsize:], gsize)
|
||||
msb := getMsb(k_ext[(ntables-1)*gsize:])
|
||||
// Init Adders
|
||||
nbitsQ := cryptoConstants.Q.BitLen()
|
||||
Q := make([]*bn256.G2, nbitsQ)
|
||||
|
||||
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])
|
||||
}
|
||||
}
|
||||
for i := 0; i < nbitsQ; i++ {
|
||||
Q[i] = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
|
||||
}
|
||||
|
||||
// Consolidate Addition
|
||||
R := new(bn256.G2).Set(Q[nbitsQ-1])
|
||||
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])
|
||||
}
|
||||
if Q_prev != nil {
|
||||
return R.Add(R,Q_prev)
|
||||
} else {
|
||||
return R
|
||||
}
|
||||
// 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 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)
|
||||
msb := getMsb(k_ext[(ntables-1)*gsize:])
|
||||
|
||||
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])
|
||||
}
|
||||
}
|
||||
|
||||
// Consolidate Addition
|
||||
R := new(bn256.G2).Set(Q[nbitsQ-1])
|
||||
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])
|
||||
}
|
||||
if Q_prev != nil {
|
||||
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{
|
||||
msb := 0
|
||||
func getMsb(k []*big.Int) int {
|
||||
msb := 0
|
||||
|
||||
for _, el := range(k){
|
||||
tmp_msb := el.BitLen()
|
||||
if tmp_msb > msb {
|
||||
msb = tmp_msb
|
||||
}
|
||||
}
|
||||
return msb
|
||||
for _, el := range k {
|
||||
tmp_msb := el.BitLen()
|
||||
if tmp_msb > msb {
|
||||
msb = tmp_msb
|
||||
}
|
||||
}
|
||||
return msb
|
||||
}
|
||||
|
||||
// Return ith bit in group of Big Integers
|
||||
func getBit(k []*big.Int, i int) uint {
|
||||
table_idx := uint(0)
|
||||
table_idx := uint(0)
|
||||
|
||||
for idx, el := range(k){
|
||||
b := el.Bit(i)
|
||||
table_idx += (b << idx)
|
||||
}
|
||||
return table_idx
|
||||
for idx, el := range k {
|
||||
b := el.Bit(i)
|
||||
table_idx += (b << idx)
|
||||
}
|
||||
return table_idx
|
||||
}
|
||||
|
||||
@@ -1,166 +1,162 @@
|
||||
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"
|
||||
"time"
|
||||
)
|
||||
|
||||
const (
|
||||
N1 = 5000
|
||||
N2 = 5000
|
||||
N1 = 5000
|
||||
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()
|
||||
p = append(p, pi)
|
||||
}
|
||||
|
||||
return p
|
||||
return p
|
||||
}
|
||||
|
||||
func randomG1Array(n int) []*bn256.G1 {
|
||||
arrayG1 := make([]*bn256.G1, n)
|
||||
arrayG1 := make([]*bn256.G1, n)
|
||||
|
||||
for i:=0; i<n; i++ {
|
||||
_, arrayG1[i], _ = bn256.RandomG1(rand.Reader)
|
||||
}
|
||||
return arrayG1
|
||||
for i := 0; i < n; i++ {
|
||||
_, arrayG1[i], _ = bn256.RandomG1(rand.Reader)
|
||||
}
|
||||
return arrayG1
|
||||
}
|
||||
|
||||
func randomG2Array(n int) []*bn256.G2 {
|
||||
arrayG2 := make([]*bn256.G2, n)
|
||||
arrayG2 := make([]*bn256.G2, n)
|
||||
|
||||
for i:=0; i<n; i++ {
|
||||
_, arrayG2[i], _ = bn256.RandomG2(rand.Reader)
|
||||
}
|
||||
return arrayG2
|
||||
for i := 0; i < n; i++ {
|
||||
_, arrayG2[i], _ = bn256.RandomG2(rand.Reader)
|
||||
}
|
||||
return arrayG2
|
||||
}
|
||||
|
||||
func TestTableG1(t *testing.T) {
|
||||
n := N1
|
||||
|
||||
// init scalar
|
||||
var arrayW = randomBigIntArray(n)
|
||||
// init G1 array
|
||||
var arrayG1 = randomG1Array(n)
|
||||
|
||||
func TestTableG1(t *testing.T){
|
||||
n := N1
|
||||
beforeT := time.Now()
|
||||
Q1 := new(bn256.G1).ScalarBaseMult(new(big.Int))
|
||||
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))
|
||||
|
||||
// init scalar
|
||||
var arrayW = randomBigIntArray(n)
|
||||
// init G1 array
|
||||
var arrayG1 = randomG1Array(n)
|
||||
for gsize := 2; gsize < 10; gsize++ {
|
||||
ntables := int((n + gsize - 1) / gsize)
|
||||
table := make([]TableG1, ntables)
|
||||
|
||||
beforeT := time.Now()
|
||||
Q1 := new(bn256.G1).ScalarBaseMult(new(big.Int))
|
||||
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 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, true)
|
||||
|
||||
for gsize:=2; gsize < 10; gsize++ {
|
||||
ntables := int((n + gsize - 1) / gsize)
|
||||
table := make([]TableG1, ntables)
|
||||
beforeT = time.Now()
|
||||
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))
|
||||
|
||||
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)
|
||||
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))
|
||||
|
||||
beforeT = time.Now()
|
||||
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))
|
||||
beforeT = time.Now()
|
||||
Q4 := MulTableNoDoubleG1(table, arrayW, nil, gsize)
|
||||
fmt.Printf("Gsize : %d, TMultNoDouble 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))
|
||||
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))
|
||||
|
||||
beforeT = time.Now()
|
||||
Q4 := MulTableNoDoubleG1(table, arrayW, nil, gsize)
|
||||
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))
|
||||
|
||||
|
||||
if bytes.Compare(Q1.Marshal(),Q2.Marshal()) != 0 {
|
||||
t.Error("Error in TMult")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(),Q3.Marshal()) != 0 {
|
||||
t.Error("Error in TMult with table comp")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(),Q4.Marshal()) != 0 {
|
||||
t.Error("Error in TMultNoDouble")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(),Q5.Marshal()) != 0 {
|
||||
t.Error("Error in TMultNoDoublee with table comp")
|
||||
}
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(), Q2.Marshal()) != 0 {
|
||||
t.Error("Error in TMult")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(), Q3.Marshal()) != 0 {
|
||||
t.Error("Error in TMult with table comp")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(), Q4.Marshal()) != 0 {
|
||||
t.Error("Error in TMultNoDouble")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(), Q5.Marshal()) != 0 {
|
||||
t.Error("Error in TMultNoDoublee with table comp")
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
func TestTableG2(t *testing.T){
|
||||
n := N2
|
||||
func TestTableG2(t *testing.T) {
|
||||
n := N2
|
||||
|
||||
// init scalar
|
||||
var arrayW = randomBigIntArray(n)
|
||||
// init G2 array
|
||||
var arrayG2 = randomG2Array(n)
|
||||
// init scalar
|
||||
var arrayW = randomBigIntArray(n)
|
||||
// init G2 array
|
||||
var arrayG2 = randomG2Array(n)
|
||||
|
||||
beforeT := time.Now()
|
||||
Q1 := new(bn256.G2).ScalarBaseMult(new(big.Int))
|
||||
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))
|
||||
beforeT := time.Now()
|
||||
Q1 := new(bn256.G2).ScalarBaseMult(new(big.Int))
|
||||
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++ {
|
||||
ntables := int((n + gsize - 1) / gsize)
|
||||
table := make([]TableG2, ntables)
|
||||
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)
|
||||
}
|
||||
table[ntables-1].NewTableG2( arrayG2[(ntables-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, 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 = table[ntables-1].MulTableG2(arrayW[(ntables-1)*gsize:], Q2, gsize)
|
||||
fmt.Printf("Gsize : %d, TMult time elapsed: %s\n", gsize,time.Since(beforeT))
|
||||
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 = table[ntables-1].MulTableG2(arrayW[(ntables-1)*gsize:], Q2, gsize)
|
||||
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))
|
||||
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))
|
||||
|
||||
beforeT = time.Now()
|
||||
Q4 := MulTableNoDoubleG2(table, arrayW, nil, gsize)
|
||||
fmt.Printf("Gsize : %d, TMultNoDouble time elapsed: %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))
|
||||
|
||||
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))
|
||||
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))
|
||||
|
||||
|
||||
if bytes.Compare(Q1.Marshal(),Q2.Marshal()) != 0 {
|
||||
t.Error("Error in TMult")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(),Q3.Marshal()) != 0 {
|
||||
t.Error("Error in TMult with table comp")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(),Q4.Marshal()) != 0 {
|
||||
t.Error("Error in TMultNoDouble")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(),Q5.Marshal()) != 0 {
|
||||
t.Error("Error in TMultNoDoublee with table comp")
|
||||
}
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(), Q2.Marshal()) != 0 {
|
||||
t.Error("Error in TMult")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(), Q3.Marshal()) != 0 {
|
||||
t.Error("Error in TMult with table comp")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(), Q4.Marshal()) != 0 {
|
||||
t.Error("Error in TMultNoDouble")
|
||||
}
|
||||
if bytes.Compare(Q1.Marshal(), Q5.Marshal()) != 0 {
|
||||
t.Error("Error in TMultNoDoublee with table comp")
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
@@ -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 |
|
||||
|
||||
25
tables.md
25
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 |
|
||||
|
||||
Reference in New Issue
Block a user