Compare commits

...

4 Commits

Author SHA1 Message Date
arnaucube
5dd19b46dd Update BabyJubJub EdDSA to last circomlib version
- Update BabyJubJub EdDSA signature to last circomlib version (Poseidon
usage)
- Remove panic on hash error inside verification, to avoid panic due
field overflow of BabyJubJub signature verification
2020-12-02 19:57:27 +01:00
arnau
94e92e88fb Merge pull request #30 from iden3/feature/signaturecomp-scanner
Add scanner/valuer interface to babyjub.SignatureComp
2020-10-16 16:24:44 +02:00
Arnau B
5ef832f175 Add scanner/valuer interface to babyjub.SignatureComp 2020-10-16 16:22:18 +02:00
arnau
59d8c7a4ca Merge pull request #29 from iden3/feature/babyjubjub-optimization
- Add `add-2008-bbjlp` for point addition
- Add `goff` to BabyJubJub point addition

```
Benchmarks (On a Intel(R) Core(TM) i7-8705G CPU @ 3.10GHz, with 32 GB of RAM):

- Old (commit: e04ca5764a):
BenchmarkBabyjub/AddConst-8              1000000              1072 ns/op
BenchmarkBabyjub/AddRnd-8                  93417             12943 ns/op
BenchmarkBabyjub/MulRnd-8                    252           4797810 ns/op
BenchmarkBabyjub/Compress-8              7291580               166 ns/op
BenchmarkBabyjub/InCurve-8                611137              1999 ns/op
BenchmarkBabyjub/InSubGroup-8             615792              2021 ns/op
BenchmarkBabyjubEddsa/SignMimc7-8            126           9358542 ns/op
BenchmarkBabyjubEddsa/VerifyMimc7-8          124           9484005 ns/op
BenchmarkBabyjubEddsa/SignPoseidon-8                 126           9486484 ns/op
BenchmarkBabyjubEddsa/VerifyPoseidon-8               126           9622807 ns/op

- With new point addition algorithm (commit: aab1a681dd):
BenchmarkBabyjub/AddConst-8              1356836               881 ns/op
BenchmarkBabyjub/AddRnd-8                 274112              4220 ns/op
BenchmarkBabyjub/MulRnd-8                    492           2474412 ns/op
BenchmarkBabyjub/Compress-8              6964855               197 ns/op
BenchmarkBabyjub/InCurve-8                608169              2008 ns/op
BenchmarkBabyjub/InSubGroup-8             618772              1954 ns/op
BenchmarkBabyjubEddsa/SignMimc7-8            238           4962397 ns/op
BenchmarkBabyjubEddsa/VerifyMimc7-8          235           5234883 ns/op
BenchmarkBabyjubEddsa/SignPoseidon-8                 240           5028720 ns/op
BenchmarkBabyjubEddsa/VerifyPoseidon-8               243           5226654 ns/op

Point Addition: ~3x
Point scalar Mul: ~1.9x
Signature (poseidon): ~1.88x
Verification (poseidon): ~1.84x

- With new point addition algorithm & goff (current commit):
BenchmarkBabyjub/AddConst-8              3000531               400 ns/op
BenchmarkBabyjub/AddRnd-8                2770335               428 ns/op
BenchmarkBabyjub/MulRnd-8                   6636            175522 ns/op
BenchmarkBabyjub/Compress-8              7358768               180 ns/op
BenchmarkBabyjub/InCurve-8                539193              1950 ns/op
BenchmarkBabyjub/InSubGroup-8             601402              1958 ns/op
BenchmarkBabyjubEddsa/SignMimc7-8           2940            409487 ns/op
BenchmarkBabyjubEddsa/VerifyMimc7-8         2908            414407 ns/op
BenchmarkBabyjubEddsa/SignPoseidon-8                2395            493165 ns/op
BenchmarkBabyjubEddsa/VerifyPoseidon-8              2491            494849 ns/op

Point Addition: ~9.86x
Point scalar Mul: ~14x
Signature (poseidon): ~10.2x
Verification (poseidon): ~10.56x

---

Total improvement (from old to current):
Point Addition: ~30.24x
Point scalar Mul: ~27.33x
Signature (poseidon): ~19.24x
Verification (poseidon): ~19.44x
```
2020-09-13 20:05:04 +02:00
3 changed files with 40 additions and 10 deletions

View File

@@ -177,6 +177,24 @@ func (s *SignatureComp) Decompress() (*Signature, error) {
return new(Signature).Decompress(*s)
}
// Scan implements Scanner for database/sql.
func (s *SignatureComp) Scan(src interface{}) error {
srcB, ok := src.([]byte)
if !ok {
return fmt.Errorf("can't scan %T into Signature", src)
}
if len(srcB) != 64 {
return fmt.Errorf("can't scan []byte of len %d into Signature, want %d", len(srcB), 64)
}
copy(s[:], srcB[:])
return nil
}
// Value implements valuer for database/sql.
func (s SignatureComp) Value() (driver.Value, error) {
return s[:], nil
}
// Scan implements Scanner for database/sql.
func (s *Signature) Scan(src interface{}) error {
srcB, ok := src.([]byte)
@@ -229,7 +247,7 @@ func (p *PublicKey) VerifyMimc7(msg *big.Int, sig *Signature) bool {
hmInput := []*big.Int{sig.R8.X, sig.R8.Y, p.X, p.Y, msg}
hm, err := mimc7.Hash(hmInput, nil) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
if err != nil {
panic(err)
return false
}
left := NewPoint().Mul(sig.S, B8) // left = s * 8 * B
@@ -255,7 +273,7 @@ func (k *PrivateKey) SignPoseidon(msg *big.Int) *Signature {
R8 := NewPoint().Mul(r, B8) // R8 = r * 8 * B
A := k.Public().Point()
hmInput := []*big.Int{R8.X, R8.Y, A.X, A.Y, msg, big.NewInt(int64(0))}
hmInput := []*big.Int{R8.X, R8.Y, A.X, A.Y, msg}
hm, err := poseidon.Hash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
if err != nil {
panic(err)
@@ -272,10 +290,10 @@ func (k *PrivateKey) SignPoseidon(msg *big.Int) *Signature {
// VerifyPoseidon verifies the signature of a message encoded as a big.Int in Zq
// using blake-512 hash for buffer hashing and Poseidon for big.Int hashing.
func (p *PublicKey) VerifyPoseidon(msg *big.Int, sig *Signature) bool {
hmInput := []*big.Int{sig.R8.X, sig.R8.Y, p.X, p.Y, msg, big.NewInt(int64(0))}
hmInput := []*big.Int{sig.R8.X, sig.R8.Y, p.X, p.Y, msg}
hm, err := poseidon.Hash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
if err != nil {
panic(err)
return false
}
left := NewPoint().Mul(sig.S, B8) // left = s * 8 * B

View File

@@ -96,7 +96,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
"15383486972088797283337779941324724402501462225528836549661220478783371668959",
sig.R8.Y.String())
assert.Equal(t,
"1662463587877312619203503803508234533733252768380479199263194005796068211378",
"1398758333392199195742243841591064350253744445503462896781493968760929513778",
sig.S.String())
ok := pk.VerifyPoseidon(msg, sig)
@@ -108,7 +108,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
assert.Equal(t, ""+
"dfedb4315d3f2eb4de2d3c510d7a987dcab67089c8ace06308827bf5bcbe02a2"+
"b23a1f04909fc088dec7e4835d85a326f7c0d0b2a3d0232d84448ca7c9ebac03",
"32f16b0f2f4c4e1169aa59685637e1429b6581a9531d058d65f4ab224eab1703",
hex.EncodeToString(sigBuf[:]))
ok = pk.VerifyPoseidon(msg, sig2)
@@ -135,6 +135,17 @@ func TestCompressDecompress(t *testing.T) {
}
}
func TestSignatureCompScannerValuer(t *testing.T) {
privK := NewRandPrivKey()
var value driver.Valuer //nolint:gosimple this is done to ensure interface compability
value = privK.SignPoseidon(big.NewInt(674238462)).Compress()
scan := privK.SignPoseidon(big.NewInt(1)).Compress()
fromDB, err := value.Value()
assert.Nil(t, err)
assert.Nil(t, scan.Scan(fromDB))
assert.Equal(t, value, scan)
}
func TestSignatureScannerValuer(t *testing.T) {
privK := NewRandPrivKey()
var value driver.Valuer
@@ -142,8 +153,8 @@ func TestSignatureScannerValuer(t *testing.T) {
value = privK.SignPoseidon(big.NewInt(674238462))
scan = privK.SignPoseidon(big.NewInt(1))
fromDB, err := value.Value()
assert.NoError(t, err)
assert.NoError(t, scan.Scan(fromDB))
assert.Nil(t, err)
assert.Nil(t, scan.Scan(fromDB))
assert.Equal(t, value, scan)
}
@@ -157,8 +168,8 @@ func TestPubKeyScannerValuer(t *testing.T) {
value = pubKValue
scan = pubKScan
fromDB, err := value.Value()
assert.NoError(t, err)
assert.NoError(t, scan.Scan(fromDB))
assert.Nil(t, err)
assert.Nil(t, scan.Scan(fromDB))
assert.Equal(t, value, scan)
}

1
go.sum
View File

@@ -126,6 +126,7 @@ github.com/steakknife/bloomfilter v0.0.0-20180922174646-6819c0d2a570 h1:gIlAHnH1
github.com/steakknife/bloomfilter v0.0.0-20180922174646-6819c0d2a570/go.mod h1:8OR4w3TdeIHIh1g6EMY5p0gVNOovcWC+1vpc7naMuAw=
github.com/steakknife/hamming v0.0.0-20180906055917-c99c65617cd3 h1:njlZPzLwU639dk2kqnCPPv+wNjq7Xb6EfUxe/oX0/NM=
github.com/steakknife/hamming v0.0.0-20180906055917-c99c65617cd3/go.mod h1:hpGUWaI9xL8pRQCTXQgocU38Qw1g0Us7n5PxxTwTCYU=
github.com/stretchr/objx v0.1.0 h1:4G4v2dO3VZwixGIRoQ5Lfboy6nUhCyYzaqnIAPPhYs4=
github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
github.com/stretchr/testify v1.2.2/go.mod h1:a8OnRcib4nhh0OaRAV+Yts87kKdq0PP7pXfy6kDkUVs=
github.com/stretchr/testify v1.3.0 h1:TivCn/peBQ7UY8ooIcPgZFpTNSz0Q2U6UrFlUfqbe0Q=