Compare commits

..

1 Commits

Author SHA1 Message Date
arnaucube
8a260d66d3 Add goff ff.Element to babyjubjub
WIP, at this moment still does not bring much optimization
2020-03-09 11:51:41 +01:00
22 changed files with 544 additions and 4452 deletions

View File

@@ -1,16 +0,0 @@
name: Lint
on: [ push, pull_request ]
jobs:
lint:
runs-on: ubuntu-latest
steps:
- name: Install Go
uses: actions/setup-go@v1
with:
go-version: 1.14.x
- name: Checkout code
uses: actions/checkout@v2
- name: Lint
run: |
curl -sSfL https://raw.githubusercontent.com/golangci/golangci-lint/master/install.sh | sh -s -- -b $(go env GOPATH)/bin v1.30.0
$(go env GOPATH)/bin/golangci-lint run --timeout=5m -c .golangci.yml

View File

@@ -1,28 +0,0 @@
on: [ push, pull_request ]
name: Test
jobs:
test:
strategy:
matrix:
go-version: [ 1.13.x, 1.14.x ]
goarch: [ "amd64", "386" ]
runs-on: ubuntu-latest
steps:
- name: Install Go
uses: actions/setup-go@v1
with:
go-version: ${{ matrix.go-version }}
env:
GOARCH: ${{ matrix.goarch }}
- name: Checkout code
uses: actions/checkout@v2
- uses: actions/cache@v1
with:
path: ~/go/pkg/mod
key: ${{ runner.os }}-go-${{ hashFiles('**/go.sum') }}
restore-keys: |
${{ runner.os }}-go-
- name: Test
env:
GOARCH: ${{ matrix.goarch }}
run: go test ./...

View File

@@ -1,17 +0,0 @@
issues:
max-same-issues: 0
exclude-use-default: false
linters:
enable:
- whitespace
- gosec
- gci
- misspell
- gomnd
- gofmt
- goimports
- lll
- golint
linters-settings:
lll:
line-length: 100

8
.travis.yml Normal file
View File

@@ -0,0 +1,8 @@
dist: xenial
language: go
go:
- "1.12"
env:
- GO111MODULE=on

View File

@@ -1,4 +1,4 @@
# go-iden3-crypto [![Go Report Card](https://goreportcard.com/badge/github.com/iden3/go-iden3-crypto)](https://goreportcard.com/report/github.com/iden3/go-iden3-crypto) [![Test Status](https://github.com/iden3/go-iden3-crypto/workflows/Test/badge.svg)](https://github.com/iden3/go-iden3-crypto/actions?query=workflow%3ATest) [![Lint Status](https://github.com/iden3/go-iden3-crypto/workflows/Lint/badge.svg)](https://github.com/iden3/go-iden3-crypto/actions?query=workflow%3ALint) [![GoDoc](https://godoc.org/github.com/iden3/go-iden3-crypto?status.svg)](https://godoc.org/github.com/iden3/go-iden3-crypto)
# go-iden3-crypto [![Go Report Card](https://goreportcard.com/badge/github.com/iden3/go-iden3-crypto)](https://goreportcard.com/report/github.com/iden3/go-iden3-crypto) [![Build Status](https://travis-ci.org/iden3/go-iden3-crypto.svg?branch=master)](https://travis-ci.org/iden3/go-iden3-crypto) [![GoDoc](https://godoc.org/github.com/iden3/go-iden3-crypto?status.svg)](https://godoc.org/github.com/iden3/go-iden3-crypto)
Go implementation of some cryptographic primitives (that fit inside the SNARK field) used in iden3

View File

@@ -10,16 +10,10 @@ import (
)
// A is one of the babyjub constants.
var A *big.Int
// Aff is A value in *ff.Element representation
var Aff *ff.Element
var A *ff.Element
// D is one of the babyjub constants.
var D *big.Int
// Dff is D value in *ff.Element representation
var Dff *ff.Element
var D *ff.Element
// Order of the babyjub curve.
var Order *big.Int
@@ -34,98 +28,52 @@ var B8 *Point
// init initializes global numbers and the subgroup base.
func init() {
A = utils.NewIntFromString("168700")
D = utils.NewIntFromString("168696")
Aff = ff.NewElement().SetBigInt(A)
Dff = ff.NewElement().SetBigInt(D)
A = ff.NewElement().SetString("168700")
D = ff.NewElement().SetString("168696")
Order = utils.NewIntFromString(
"21888242871839275222246405745257275088614511777268538073601725287587578984328")
SubOrder = new(big.Int).Rsh(Order, 3)
B8 = NewPoint()
B8.X = utils.NewIntFromString(
B8.X = ff.NewElement().SetString(
"5299619240641551281634865583518297030282874472190772894086521144482721001553")
B8.Y = utils.NewIntFromString(
B8.Y = ff.NewElement().SetString(
"16950150798460657717958625567821834550301663161624707787222815936182638968203")
}
// PointProjective is the Point representation in projective coordinates
type PointProjective struct {
X *ff.Element
Y *ff.Element
Z *ff.Element
}
// NewPointProjective creates a new Point in projective coordinates.
func NewPointProjective() *PointProjective {
return &PointProjective{X: ff.NewElement().SetZero(),
Y: ff.NewElement().SetOne(), Z: ff.NewElement().SetOne()}
}
// Affine returns the Point from the projective representation
func (p *PointProjective) Affine() *Point {
if p.Z.Equal(ff.NewElement().SetZero()) {
return &Point{
X: big.NewInt(0),
Y: big.NewInt(0),
}
}
zinv := ff.NewElement().Inverse(p.Z)
x := ff.NewElement().Mul(p.X, zinv)
y := ff.NewElement().Mul(p.Y, zinv)
xBig := big.NewInt(0)
x.ToBigIntRegular(xBig)
yBig := big.NewInt(0)
y.ToBigIntRegular(yBig)
return &Point{
X: xBig,
Y: yBig,
}
}
// Add computes the addition of two points in projective coordinates
// representation
func (p *PointProjective) Add(q *PointProjective, o *PointProjective) *PointProjective {
// add-2008-bbjlp
// https://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#doubling-dbl-2008-bbjlp
a := ff.NewElement().Mul(q.Z, o.Z)
b := ff.NewElement().Square(a)
c := ff.NewElement().Mul(q.X, o.X)
d := ff.NewElement().Mul(q.Y, o.Y)
e := ff.NewElement().Mul(Dff, c)
e.MulAssign(d)
f := ff.NewElement().Sub(b, e)
g := ff.NewElement().Add(b, e)
x1y1 := ff.NewElement().Add(q.X, q.Y)
x2y2 := ff.NewElement().Add(o.X, o.Y)
x3 := ff.NewElement().Mul(x1y1, x2y2)
x3.SubAssign(c)
x3.SubAssign(d)
x3.MulAssign(a)
x3.MulAssign(f)
ac := ff.NewElement().Mul(Aff, c)
y3 := ff.NewElement().Sub(d, ac)
y3.MulAssign(a)
y3.MulAssign(g)
z3 := ff.NewElement().Mul(f, g)
p.X = x3
p.Y = y3
p.Z = z3
return p
}
// Point represents a point of the babyjub curve.
type Point struct {
// PointBI represents a point of the babyjub curve.
type PointBI struct {
X *big.Int
Y *big.Int
}
// NewPoint creates a new Point.
type Point struct {
X *ff.Element
Y *ff.Element
}
func PointBIToPoint(p *PointBI) *Point {
return &Point{
X: ff.NewElement().SetBigInt(p.X),
Y: ff.NewElement().SetBigInt(p.Y),
}
}
func PointToPointBI(p *Point) *PointBI {
return &PointBI{
X: p.X.BigInt(),
Y: p.Y.BigInt(),
}
}
// NewPoint creates a new PointBI.
func NewPointBI() *PointBI {
return &PointBI{X: big.NewInt(0), Y: big.NewInt(1)}
}
func NewPoint() *Point {
return &Point{X: big.NewInt(0), Y: big.NewInt(1)}
return &Point{X: ff.NewElement().SetZero(), Y: ff.NewElement().SetOne()}
}
// Set copies a Point c into the Point p
@@ -135,56 +83,83 @@ func (p *Point) Set(c *Point) *Point {
return p
}
// Projective returns a PointProjective from the Point
func (p *Point) Projective() *PointProjective {
return &PointProjective{
X: ff.NewElement().SetBigInt(p.X),
Y: ff.NewElement().SetBigInt(p.Y),
Z: ff.NewElement().SetOne(),
}
func (p *Point) Equal(q *Point) bool {
// return p.X.Cmp(q.X) == 0 && p.Y.Cmp(q.Y) == 0
return p.X.Equal(q.X) && p.Y.Equal(q.Y)
}
// Mul multiplies the Point q by the scalar s and stores the result in p,
// Add adds Point a and b into res
func (res *Point) Add(a *Point, b *Point) *Point {
// x = (a.x * b.y + b.x * a.y) * (1 + D * a.x * b.x * a.y * b.y)^-1 mod q
x1a := ff.NewElement().Mul(a.X, b.Y)
x1b := ff.NewElement().Mul(b.X, a.Y)
x1a.Add(x1a, x1b) // x1a = a.x * b.y + b.x * a.y
x2 := ff.NewElement().Set(D)
x2.Mul(x2, a.X)
x2.Mul(x2, b.X)
x2.Mul(x2, a.Y)
x2.Mul(x2, b.Y)
x2.Add(ff.NewElement().SetOne(), x2)
x2.Inverse(x2) // x2 = (1 + D * a.x * b.x * a.y * b.y)^-1
// y = (a.y * b.y - A * a.x * b.x) * (1 - D * a.x * b.x * a.y * b.y)^-1 mod q
y1a := ff.NewElement().Mul(a.Y, b.Y)
y1b := ff.NewElement().Set(A)
y1b.Mul(y1b, a.X)
y1b.Mul(y1b, b.X)
y1a.Sub(y1a, y1b) // y1a = a.y * b.y - A * a.x * b.x
y2 := ff.NewElement().Set(D)
y2.Mul(y2, a.X)
y2.Mul(y2, b.X)
y2.Mul(y2, a.Y)
y2.Mul(y2, b.Y)
y2.Sub(ff.NewElement().SetOne(), y2)
y2.Inverse(y2) // y2 = (1 - D * a.x * b.x * a.y * b.y)^-1
res.X = x1a.Mul(x1a, x2)
res.Y = y1a.Mul(y1a, y2)
return res
}
// Mul multiplies the Point p by the scalar s and stores the result in res,
// which is also returned.
func (p *Point) Mul(s *big.Int, q *Point) *Point {
resProj := &PointProjective{
X: ff.NewElement().SetZero(),
Y: ff.NewElement().SetOne(),
Z: ff.NewElement().SetOne(),
}
exp := q.Projective()
func (res *Point) Mul(s *big.Int, p *Point) *Point {
res.X = ff.NewElement().SetZero()
res.Y = ff.NewElement().SetOne()
exp := NewPoint().Set(p)
for i := 0; i < s.BitLen(); i++ {
if s.Bit(i) == 1 {
resProj.Add(resProj, exp)
res.Add(res, exp)
}
exp = exp.Add(exp, exp)
exp.Add(exp, exp)
}
p = resProj.Affine()
return p
return res
}
// InCurve returns true when the Point p is in the babyjub curve.
func (p *Point) InCurve() bool {
x2 := new(big.Int).Set(p.X)
x2 := ff.NewElement().Set(p.X)
x2.Mul(x2, x2)
x2.Mod(x2, constants.Q)
y2 := new(big.Int).Set(p.Y)
y2 := ff.NewElement().Set(p.Y)
y2.Mul(y2, y2)
y2.Mod(y2, constants.Q)
a := new(big.Int).Mul(A, x2)
a := ff.NewElement().Mul(A, x2)
a.Add(a, y2)
a.Mod(a, constants.Q)
b := new(big.Int).Set(D)
b := ff.NewElement().Set(D)
b.Mul(b, x2)
b.Mul(b, y2)
b.Add(constants.One, b)
b.Mod(b, constants.Q)
b.Add(ff.NewElement().SetOne(), b)
return a.Cmp(b) == 0
return a.Equal(b)
}
// InSubGroup returns true when the Point p is in the subgroup of the babyjub
@@ -194,90 +169,73 @@ func (p *Point) InSubGroup() bool {
return false
}
res := NewPoint().Mul(SubOrder, p)
return (res.X.Cmp(constants.Zero) == 0) && (res.Y.Cmp(constants.One) == 0)
return res.X.Equal(ff.NewElement().SetZero()) && res.Y.Equal(ff.NewElement().SetOne())
}
// PointCoordSign returns the sign of the curve point coordinate. It returns
// false if the sign is positive and false if the sign is negative.
func PointCoordSign(c *big.Int) bool {
return c.Cmp(new(big.Int).Rsh(constants.Q, 1)) == 1
if c.Cmp(new(big.Int).Rsh(constants.Q, 1)) == 1 {
return true
}
return false
}
// PackSignY packs the given sign and the coordinate Y of a point into a 32
// byte array. This method does not check that the values belong to a valid
// Point in the curve.
func PackSignY(sign bool, y *big.Int) [32]byte {
leBuf := utils.BigIntLEBytes(y)
func PackPoint(ay *big.Int, sign bool) [32]byte {
leBuf := utils.BigIntLEBytes(ay)
if sign {
leBuf[31] = leBuf[31] | 0x80 //nolint:gomnd
leBuf[31] = leBuf[31] | 0x80
}
return leBuf
}
// UnpackSignY returns the sign and coordinate Y from a given compressed point.
// This method does not check that the Point belongs to the BabyJubJub curve,
// thus does not return error in such case. This method is intended to obtain
// the sign and the Y coordinate without checking if the point belongs to the
// curve, if the objective is to uncompress a point, Decompress method should
// be used instead.
func UnpackSignY(leBuf [32]byte) (bool, *big.Int) {
sign := false
y := big.NewInt(0)
if (leBuf[31] & 0x80) != 0x00 { //nolint:gomnd
sign = true
leBuf[31] = leBuf[31] & 0x7F //nolint:gomnd
}
utils.SetBigIntFromLEBytes(y, leBuf[:])
return sign, y
}
// Compress the point into a 32 byte array that contains the y coordinate in
// little endian and the sign of the x coordinate.
func (p *Point) Compress() [32]byte {
sign := PointCoordSign(p.X)
return PackSignY(sign, p.Y)
pBI := PointToPointBI(p)
sign := PointCoordSign(pBI.X)
return PackPoint(pBI.Y, sign)
}
// Decompress a compressed Point into p, and also returns the decompressed
// Point. Returns error if the compressed Point is invalid.
func (p *Point) Decompress(leBuf [32]byte) (*Point, error) {
var sign bool
sign, p.Y = UnpackSignY(leBuf)
return PointFromSignAndY(sign, p.Y)
}
// PointFromSignAndY returns a Point from a Sign and the Y coordinate
func PointFromSignAndY(sign bool, y *big.Int) (*Point, error) {
var p Point
p.X = big.NewInt(0)
p.Y = y
if p.Y.Cmp(constants.Q) >= 0 {
sign := false
if (leBuf[31] & 0x80) != 0x00 {
sign = true
leBuf[31] = leBuf[31] & 0x7F
}
y := big.NewInt(0)
utils.SetBigIntFromLEBytes(y, leBuf[:])
if y.Cmp(constants.Q) >= 0 {
return nil, fmt.Errorf("p.y >= Q")
}
p.Y = ff.NewElement().SetBigInt(y)
y2 := new(big.Int).Mul(p.Y, p.Y)
y2.Mod(y2, constants.Q)
xa := big.NewInt(1)
y2 := ff.NewElement().Mul(p.Y, p.Y)
xa := ff.NewElement().SetOne()
xa.Sub(xa, y2) // xa == 1 - y^2
xb := new(big.Int).Mul(D, y2)
xb.Mod(xb, constants.Q)
xb := ff.NewElement().Mul(D, y2)
xb.Sub(A, xb) // xb = A - d * y^2
if xb.Cmp(big.NewInt(0)) == 0 {
if xb.Equal(ff.NewElement().SetZero()) {
return nil, fmt.Errorf("division by 0")
}
xb.ModInverse(xb, constants.Q)
xb.Inverse(xb)
p.X.Mul(xa, xb) // xa / xb
p.X.Mod(p.X, constants.Q)
noSqrt := p.X.ModSqrt(p.X, constants.Q)
q := PointToPointBI(p)
noSqrt := q.X.ModSqrt(q.X, constants.Q)
if noSqrt == nil {
return nil, fmt.Errorf("x is not a square mod q")
}
if (sign && !PointCoordSign(p.X)) || (!sign && PointCoordSign(p.X)) {
p.X.Mul(p.X, constants.MinusOne)
if (sign && !PointCoordSign(q.X)) || (!sign && PointCoordSign(q.X)) {
q.X.Mul(q.X, constants.MinusOne)
}
p.X.Mod(p.X, constants.Q)
q.X.Mod(q.X, constants.Q)
return &p, nil
p = PointBIToPoint(q)
return p, nil
}

View File

@@ -7,34 +7,42 @@ import (
"testing"
"github.com/iden3/go-iden3-crypto/constants"
"github.com/iden3/go-iden3-crypto/ff"
"github.com/iden3/go-iden3-crypto/utils"
"github.com/stretchr/testify/assert"
)
func TestAdd1(t *testing.T) {
a := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
b := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
func zero() *ff.Element {
return ff.NewElement().SetZero()
}
func one() *ff.Element {
return ff.NewElement().SetOne()
}
c := NewPoint().Projective().Add(a.Projective(), b.Projective())
func TestAdd1(t *testing.T) {
a := &Point{X: zero(), Y: one()}
b := &Point{X: zero(), Y: one()}
c := NewPoint().Add(a, b)
// fmt.Printf("%v = 2 * %v", *c, *a)
assert.Equal(t, "0", c.X.String())
assert.Equal(t, "1", c.Y.String())
}
func TestAdd2(t *testing.T) {
aX := utils.NewIntFromString(
aX := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
aY := utils.NewIntFromString(
aY := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
a := &Point{X: aX, Y: aY}
bX := utils.NewIntFromString(
bX := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
bY := utils.NewIntFromString(
bY := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
b := &Point{X: bX, Y: bY}
c := NewPoint().Projective().Add(a.Projective(), b.Projective()).Affine()
c := NewPoint().Add(a, b)
// fmt.Printf("%v = 2 * %v", *c, *a)
assert.Equal(t,
"6890855772600357754907169075114257697580319025794532037257385534741338397365",
@@ -42,34 +50,22 @@ func TestAdd2(t *testing.T) {
assert.Equal(t,
"4338620300185947561074059802482547481416142213883829469920100239455078257889",
c.Y.String())
d := NewPointProjective().Add(c.Projective(), c.Projective()).Affine()
assert.Equal(t,
"2f6458832049e917c95867185a96621336df33e13c98e81d1ef4928cdbb77772",
hex.EncodeToString(d.X.Bytes()))
// Projective
aP := a.Projective()
bP := b.Projective()
cP := NewPointProjective().Add(aP, bP)
c2 := cP.Affine()
assert.Equal(t, c, c2)
}
func TestAdd3(t *testing.T) {
aX := utils.NewIntFromString(
aX := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
aY := utils.NewIntFromString(
aY := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
a := &Point{X: aX, Y: aY}
bX := utils.NewIntFromString(
bX := ff.NewElement().SetString(
"16540640123574156134436876038791482806971768689494387082833631921987005038935")
bY := utils.NewIntFromString(
bY := ff.NewElement().SetString(
"20819045374670962167435360035096875258406992893633759881276124905556507972311")
b := &Point{X: bX, Y: bY}
c := NewPoint().Projective().Add(a.Projective(), b.Projective()).Affine()
c := NewPoint().Add(a, b)
// fmt.Printf("%v = 2 * %v", *c, *a)
assert.Equal(t,
"7916061937171219682591368294088513039687205273691143098332585753343424131937",
@@ -80,19 +76,19 @@ func TestAdd3(t *testing.T) {
}
func TestAdd4(t *testing.T) {
aX := utils.NewIntFromString(
aX := ff.NewElement().SetString(
"0")
aY := utils.NewIntFromString(
aY := ff.NewElement().SetString(
"1")
a := &Point{X: aX, Y: aY}
bX := utils.NewIntFromString(
bX := ff.NewElement().SetString(
"16540640123574156134436876038791482806971768689494387082833631921987005038935")
bY := utils.NewIntFromString(
bY := ff.NewElement().SetString(
"20819045374670962167435360035096875258406992893633759881276124905556507972311")
b := &Point{X: bX, Y: bY}
c := NewPoint().Projective().Add(a.Projective(), b.Projective()).Affine()
c := NewPoint().Add(a, b)
// fmt.Printf("%v = 2 * %v", *c, *a)
assert.Equal(t,
"16540640123574156134436876038791482806971768689494387082833631921987005038935",
@@ -103,25 +99,25 @@ func TestAdd4(t *testing.T) {
}
func TestInCurve1(t *testing.T) {
p := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
p := &Point{X: zero(), Y: one()}
assert.Equal(t, true, p.InCurve())
}
func TestInCurve2(t *testing.T) {
p := &Point{X: big.NewInt(1), Y: big.NewInt(0)}
p := &Point{X: one(), Y: zero()}
assert.Equal(t, false, p.InCurve())
}
func TestMul0(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
p := &Point{X: x, Y: y}
s := utils.NewIntFromString("3")
r2 := NewPoint().Projective().Add(p.Projective(), p.Projective()).Affine()
r2 = NewPoint().Projective().Add(r2.Projective(), p.Projective()).Affine()
r2 := NewPoint().Add(p, p)
r2 = NewPoint().Add(r2, p)
r := NewPoint().Mul(s, p)
assert.Equal(t, r2.X.String(), r.X.String())
assert.Equal(t, r2.Y.String(), r.Y.String())
@@ -135,9 +131,9 @@ func TestMul0(t *testing.T) {
}
func TestMul1(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
p := &Point{X: x, Y: y}
s := utils.NewIntFromString(
@@ -152,9 +148,9 @@ func TestMul1(t *testing.T) {
}
func TestMul2(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"6890855772600357754907169075114257697580319025794532037257385534741338397365")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"4338620300185947561074059802482547481416142213883829469920100239455078257889")
p := &Point{X: x, Y: y}
s := utils.NewIntFromString(
@@ -169,86 +165,50 @@ func TestMul2(t *testing.T) {
}
func TestInCurve3(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
p := &Point{X: x, Y: y}
assert.Equal(t, true, p.InCurve())
}
func TestInCurve4(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"6890855772600357754907169075114257697580319025794532037257385534741338397365")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"4338620300185947561074059802482547481416142213883829469920100239455078257889")
p := &Point{X: x, Y: y}
assert.Equal(t, true, p.InCurve())
}
func TestInSubGroup1(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
p := &Point{X: x, Y: y}
assert.Equal(t, true, p.InSubGroup())
}
func TestInSubGroup2(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"6890855772600357754907169075114257697580319025794532037257385534741338397365")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"4338620300185947561074059802482547481416142213883829469920100239455078257889")
p := &Point{X: x, Y: y}
assert.Equal(t, true, p.InSubGroup())
}
func TestPointFromSignAndy(t *testing.T) {
x := utils.NewIntFromString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
y := utils.NewIntFromString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
p := &Point{X: x, Y: y}
sign := PointCoordSign(p.X)
p2, err := PointFromSignAndY(sign, p.Y)
assert.Equal(t, nil, err)
assert.Equal(t, p.X.String(), p2.X.String())
assert.Equal(t, p.Y.String(), p2.Y.String())
}
func TestPackAndUnpackSignY(t *testing.T) {
x := utils.NewIntFromString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
y := utils.NewIntFromString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
p := &Point{X: x, Y: y}
pComp := p.Compress()
s, y := UnpackSignY(pComp)
pComp2 := PackSignY(s, y)
assert.Equal(t, pComp, pComp2)
emptyPointComp := [32]byte{}
s, y = UnpackSignY(emptyPointComp)
pComp2 = PackSignY(s, y)
assert.Equal(t, emptyPointComp, pComp2)
}
func TestCompressDecompress1(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
p := &Point{X: x, Y: y}
buf := p.Compress()
assert.Equal(t,
"53b81ed5bffe9545b54016234682e7b2f699bd42a5e9eae27ff4051bc698ce85",
hex.EncodeToString(buf[:]))
assert.Equal(t, "53b81ed5bffe9545b54016234682e7b2f699bd42a5e9eae27ff4051bc698ce85", hex.EncodeToString(buf[:]))
p2, err := NewPoint().Decompress(buf)
assert.Equal(t, nil, err)
@@ -257,16 +217,14 @@ func TestCompressDecompress1(t *testing.T) {
}
func TestCompressDecompress2(t *testing.T) {
x := utils.NewIntFromString(
x := ff.NewElement().SetString(
"6890855772600357754907169075114257697580319025794532037257385534741338397365")
y := utils.NewIntFromString(
y := ff.NewElement().SetString(
"4338620300185947561074059802482547481416142213883829469920100239455078257889")
p := &Point{X: x, Y: y}
buf := p.Compress()
assert.Equal(t,
"e114eb17eddf794f063a68fecac515e3620e131976108555735c8b0773929709",
hex.EncodeToString(buf[:]))
assert.Equal(t, "e114eb17eddf794f063a68fecac515e3620e131976108555735c8b0773929709", hex.EncodeToString(buf[:]))
p2, err := NewPoint().Decompress(buf)
assert.Equal(t, nil, err)
@@ -280,34 +238,32 @@ func TestCompressDecompressRnd(t *testing.T) {
buf := p1.Compress()
p2, err := NewPoint().Decompress(buf)
assert.Equal(t, nil, err)
assert.Equal(t, p1.X.Bytes(), p2.X.Bytes())
assert.Equal(t, p1.Y.Bytes(), p2.Y.Bytes())
// assert.Equal(t, p1, p2)
assert.True(t, p1.Equal(p2))
}
}
func BenchmarkBabyjub(b *testing.B) {
const n = 256
rnd := rand.New(rand.NewSource(42)) //nolint:gosec
rnd := rand.New(rand.NewSource(42))
var badpoints [n]*Point
for i := 0; i < n; i++ {
x := new(big.Int).Rand(rnd, constants.Q)
y := new(big.Int).Rand(rnd, constants.Q)
x := ff.NewElement().SetRandom()
y := ff.NewElement().SetRandom()
badpoints[i] = &Point{X: x, Y: y}
}
var points [n]*Point
var pointsProj [n]*PointProjective
baseX := utils.NewIntFromString(
baseX := ff.NewElement().SetString(
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
baseY := utils.NewIntFromString(
baseY := ff.NewElement().SetString(
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
base := &Point{X: baseX, Y: baseY}
for i := 0; i < n; i++ {
s := new(big.Int).Rand(rnd, constants.Q)
points[i] = NewPoint().Mul(s, base)
pointsProj[i] = NewPoint().Mul(s, base).Projective()
}
var scalars [n]*big.Int
@@ -316,21 +272,19 @@ func BenchmarkBabyjub(b *testing.B) {
}
b.Run("AddConst", func(b *testing.B) {
p0 := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
p1 := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
p0Proj := p0.Projective()
p1Proj := p1.Projective()
p0 := &Point{X: zero(), Y: one()}
p1 := &Point{X: zero(), Y: one()}
p2 := NewPoint().Projective()
p2 := NewPoint()
for i := 0; i < b.N; i++ {
p2.Add(p0Proj, p1Proj)
p2.Add(p0, p1)
}
})
b.Run("AddRnd", func(b *testing.B) {
res := NewPoint().Projective()
res := NewPoint()
for i := 0; i < b.N; i++ {
res.Add(pointsProj[i%(n/2)], pointsProj[i%(n/2)+1])
res.Add(points[i%(n/2)], points[i%(n/2)+1])
}
})

View File

@@ -1,16 +1,13 @@
// Package babyjub eddsa implements the EdDSA over the BabyJubJub curve
//nolint:gomnd
package babyjub
import (
"crypto/rand"
"database/sql/driver"
"fmt"
"math/big"
"github.com/iden3/go-iden3-crypto/mimc7"
"github.com/iden3/go-iden3-crypto/poseidon"
"github.com/iden3/go-iden3-crypto/utils"
"math/big"
)
// pruneBuffer prunes the buffer during key generation according to RFC 8032.
@@ -39,13 +36,6 @@ func NewRandPrivKey() PrivateKey {
// Scalar converts a private key into the scalar value s following the EdDSA
// standard, and using blake-512 hash.
func (k *PrivateKey) Scalar() *PrivKeyScalar {
s := SkToBigInt(k)
return NewPrivKeyScalar(s)
}
// SkToBigInt converts a private key into the *big.Int value following the
// EdDSA standard, and using blake-512 hash
func SkToBigInt(k *PrivateKey) *big.Int {
sBuf := Blake512(k[:])
sBuf32 := [32]byte{}
copy(sBuf32[:], sBuf[:32])
@@ -53,10 +43,10 @@ func SkToBigInt(k *PrivateKey) *big.Int {
s := new(big.Int)
utils.SetBigIntFromLEBytes(s, sBuf32[:])
s.Rsh(s, 3)
return s
return NewPrivKeyScalar(s)
}
// Public returns the public key corresponding to a private key.
// Pub returns the public key corresponding to a private key.
func (k *PrivateKey) Public() *PublicKey {
return k.Scalar().Public()
}
@@ -70,8 +60,8 @@ func NewPrivKeyScalar(s *big.Int) *PrivKeyScalar {
return &sk
}
// Public returns the public key corresponding to the scalar value s of a
// private key.
// Pub returns the public key corresponding to the scalar value s of a private
// key.
func (s *PrivKeyScalar) Public() *PublicKey {
p := NewPoint().Mul((*big.Int)(s), B8)
pk := PublicKey(*p)
@@ -86,19 +76,16 @@ func (s *PrivKeyScalar) BigInt() *big.Int {
// PublicKey represents an EdDSA public key, which is a curve point.
type PublicKey Point
// MarshalText implements the marshaler for PublicKey
func (pk PublicKey) MarshalText() ([]byte, error) {
pkc := pk.Compress()
return utils.Hex(pkc[:]).MarshalText()
}
// String returns the string representation of the PublicKey
func (pk PublicKey) String() string {
pkc := pk.Compress()
return utils.Hex(pkc[:]).String()
}
// UnmarshalText implements the unmarshaler for the PublicKey
func (pk *PublicKey) UnmarshalText(h []byte) error {
var pkc PublicKeyComp
if err := utils.HexDecodeInto(pkc[:], h); err != nil {
@@ -113,35 +100,24 @@ func (pk *PublicKey) UnmarshalText(h []byte) error {
}
// Point returns the Point corresponding to a PublicKey.
func (pk *PublicKey) Point() *Point {
return (*Point)(pk)
func (p *PublicKey) Point() *Point {
return (*Point)(p)
}
// PublicKeyComp represents a compressed EdDSA Public key; it's a compressed curve
// point.
type PublicKeyComp [32]byte
// MarshalText implements the marshaler for the PublicKeyComp
func (pkComp PublicKeyComp) MarshalText() ([]byte, error) {
return utils.Hex(pkComp[:]).MarshalText()
func (buf PublicKeyComp) MarshalText() ([]byte, error) { return utils.Hex(buf[:]).MarshalText() }
func (buf PublicKeyComp) String() string { return utils.Hex(buf[:]).String() }
func (buf *PublicKeyComp) UnmarshalText(h []byte) error { return utils.HexDecodeInto(buf[:], h) }
func (p *PublicKey) Compress() PublicKeyComp {
return PublicKeyComp((*Point)(p).Compress())
}
// String returns the string representation of the PublicKeyComp
func (pkComp PublicKeyComp) String() string { return utils.Hex(pkComp[:]).String() }
// UnmarshalText implements the unmarshaler for the PublicKeyComp
func (pkComp *PublicKeyComp) UnmarshalText(h []byte) error {
return utils.HexDecodeInto(pkComp[:], h)
}
// Compress returns the PublicKeyCompr for the given PublicKey
func (pk *PublicKey) Compress() PublicKeyComp {
return PublicKeyComp((*Point)(pk).Compress())
}
// Decompress returns the PublicKey for the given PublicKeyComp
func (pkComp *PublicKeyComp) Decompress() (*PublicKey, error) {
point, err := NewPoint().Decompress(*pkComp)
func (p *PublicKeyComp) Decompress() (*PublicKey, error) {
point, err := NewPoint().Decompress(*p)
if err != nil {
return nil, err
}
@@ -158,18 +134,9 @@ type Signature struct {
// SignatureComp represents a compressed EdDSA signature.
type SignatureComp [64]byte
// MarshalText implements the marshaler for the SignatureComp
func (sComp SignatureComp) MarshalText() ([]byte, error) {
return utils.Hex(sComp[:]).MarshalText()
}
// String returns the string representation of the SignatureComp
func (sComp SignatureComp) String() string { return utils.Hex(sComp[:]).String() }
// UnmarshalText implements the unmarshaler for the SignatureComp
func (sComp *SignatureComp) UnmarshalText(h []byte) error {
return utils.HexDecodeInto(sComp[:], h)
}
func (buf SignatureComp) MarshalText() ([]byte, error) { return utils.Hex(buf[:]).MarshalText() }
func (buf SignatureComp) String() string { return utils.Hex(buf[:]).String() }
func (buf *SignatureComp) UnmarshalText(h []byte) error { return utils.HexDecodeInto(buf[:], h) }
// Compress an EdDSA signature by concatenating the compression of
// the point R8 and the Little-Endian encoding of S.
@@ -197,47 +164,8 @@ func (s *Signature) Decompress(buf [64]byte) (*Signature, error) {
// Decompress a compressed signature. Returns error if the Point decompression
// fails.
func (sComp *SignatureComp) Decompress() (*Signature, error) {
return new(Signature).Decompress(*sComp)
}
// Scan implements Scanner for database/sql.
func (sComp *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(sComp[:], srcB[:])
return nil
}
// Value implements valuer for database/sql.
func (sComp SignatureComp) Value() (driver.Value, error) {
return sComp[:], nil
}
// Scan implements Scanner for database/sql.
func (s *Signature) 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)
}
buf := [64]byte{}
copy(buf[:], srcB[:])
_, err := s.Decompress(buf)
return err
}
// Value implements valuer for database/sql.
func (s Signature) Value() (driver.Value, error) {
comp := s.Compress()
return comp[:], nil
func (s *SignatureComp) Decompress() (*Signature, error) {
return new(Signature).Decompress(*s)
}
// SignMimc7 signs a message encoded as a big.Int in Zq using blake-512 hash
@@ -252,7 +180,7 @@ func (k *PrivateKey) SignMimc7(msg *big.Int) *Signature {
r.Mod(r, SubOrder)
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}
hmInput := []*big.Int{R8.X.BigInt(), R8.Y.BigInt(), A.X.BigInt(), A.Y.BigInt(), 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)
@@ -267,21 +195,19 @@ func (k *PrivateKey) SignMimc7(msg *big.Int) *Signature {
// VerifyMimc7 verifies the signature of a message encoded as a big.Int in Zq
// using blake-512 hash for buffer hashing and mimc7 for big.Int hashing.
func (pk *PublicKey) VerifyMimc7(msg *big.Int, sig *Signature) bool {
hmInput := []*big.Int{sig.R8.X, sig.R8.Y, pk.X, pk.Y, msg}
func (p *PublicKey) VerifyMimc7(msg *big.Int, sig *Signature) bool {
hmInput := []*big.Int{sig.R8.X.BigInt(), sig.R8.Y.BigInt(), p.X.BigInt(), p.Y.BigInt(), msg}
hm, err := mimc7.Hash(hmInput, nil) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
if err != nil {
return false
panic(err)
}
left := NewPoint().Mul(sig.S, B8) // left = s * 8 * B
r1 := big.NewInt(8)
r1.Mul(r1, hm)
right := NewPoint().Mul(r1, pk.Point())
rightProj := right.Projective()
rightProj.Add(sig.R8.Projective(), rightProj) // right = 8 * R + 8 * hm * A
right = rightProj.Affine()
return (left.X.Cmp(right.X) == 0) && (left.Y.Cmp(right.Y) == 0)
right := NewPoint().Mul(r1, p.Point())
right.Add(sig.R8, right) // right = 8 * R + 8 * hm * A
return left.X.Equal(right.X) && left.Y.Equal(right.Y)
}
// SignPoseidon signs a message encoded as a big.Int in Zq using blake-512 hash
@@ -297,8 +223,8 @@ 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}
hm, err := poseidon.Hash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
hmInput := [poseidon.T]*big.Int{R8.X.BigInt(), R8.Y.BigInt(), A.X.BigInt(), A.Y.BigInt(), msg, big.NewInt(int64(0))}
hm, err := poseidon.PoseidonHash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
if err != nil {
panic(err)
}
@@ -313,62 +239,17 @@ 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 (pk *PublicKey) VerifyPoseidon(msg *big.Int, sig *Signature) bool {
hmInput := []*big.Int{sig.R8.X, sig.R8.Y, pk.X, pk.Y, msg}
hm, err := poseidon.Hash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
func (p *PublicKey) VerifyPoseidon(msg *big.Int, sig *Signature) bool {
hmInput := [poseidon.T]*big.Int{sig.R8.X.BigInt(), sig.R8.Y.BigInt(), p.X.BigInt(), p.Y.BigInt(), msg, big.NewInt(int64(0))}
hm, err := poseidon.PoseidonHash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
if err != nil {
return false
panic(err)
}
left := NewPoint().Mul(sig.S, B8) // left = s * 8 * B
r1 := big.NewInt(8)
r1.Mul(r1, hm)
right := NewPoint().Mul(r1, pk.Point())
rightProj := right.Projective()
rightProj.Add(sig.R8.Projective(), rightProj) // right = 8 * R + 8 * hm * A
right = rightProj.Affine()
return (left.X.Cmp(right.X) == 0) && (left.Y.Cmp(right.Y) == 0)
}
// Scan implements Scanner for database/sql.
func (pk *PublicKey) Scan(src interface{}) error {
srcB, ok := src.([]byte)
if !ok {
return fmt.Errorf("can't scan %T into PublicKey", src)
}
if len(srcB) != 32 {
return fmt.Errorf("can't scan []byte of len %d into PublicKey, want %d", len(srcB), 32)
}
var comp PublicKeyComp
copy(comp[:], srcB)
decomp, err := comp.Decompress()
if err != nil {
return err
}
*pk = *decomp
return nil
}
// Value implements valuer for database/sql.
func (pk PublicKey) Value() (driver.Value, error) {
comp := pk.Compress()
return comp[:], nil
}
// Scan implements Scanner for database/sql.
func (pkComp *PublicKeyComp) Scan(src interface{}) error {
srcB, ok := src.([]byte)
if !ok {
return fmt.Errorf("can't scan %T into PublicKeyComp", src)
}
if len(srcB) != 32 {
return fmt.Errorf("can't scan []byte of len %d into PublicKeyComp, want %d", len(srcB), 32)
}
copy(pkComp[:], srcB)
return nil
}
// Value implements valuer for database/sql.
func (pkComp PublicKeyComp) Value() (driver.Value, error) {
return pkComp[:], nil
right := NewPoint().Mul(r1, p.Point())
right.Add(sig.R8, right) // right = 8 * R + 8 * hm * A
return left.X.Equal(right.X) && left.Y.Equal(right.Y)
}

View File

@@ -1,8 +1,7 @@
package babyjub
import (
"database/sql"
"database/sql/driver"
"crypto/rand"
"encoding/hex"
"fmt"
"math/big"
@@ -11,24 +10,34 @@ import (
"github.com/iden3/go-iden3-crypto/constants"
"github.com/iden3/go-iden3-crypto/utils"
"github.com/stretchr/testify/assert"
"github.com/stretchr/testify/require"
)
func genInputs() (*PrivateKey, *big.Int) {
k := NewRandPrivKey()
fmt.Println("k", hex.EncodeToString(k[:]))
msgBuf := [32]byte{}
rand.Read(msgBuf[:])
msg := utils.SetBigIntFromLEBytes(new(big.Int), msgBuf[:])
msg.Mod(msg, constants.Q)
fmt.Println("msg", msg)
return &k, msg
}
func TestPublicKey(t *testing.T) {
var k PrivateKey
for i := 0; i < 32; i++ {
k[i] = byte(i)
for i := 0; i < 256; i++ {
hex.Decode(k[:], []byte{byte(i)})
}
pk := k.Public()
assert.True(t, pk.X.Cmp(constants.Q) == -1)
assert.True(t, pk.Y.Cmp(constants.Q) == -1)
assert.True(t, pk.X.BigInt().Cmp(constants.Q) == -1)
assert.True(t, pk.Y.BigInt().Cmp(constants.Q) == -1)
}
func TestSignVerifyMimc7(t *testing.T) {
var k PrivateKey
_, err := hex.Decode(k[:],
[]byte("0001020304050607080900010203040506070809000102030405060708090001"))
require.Nil(t, err)
hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
msgBuf, err := hex.DecodeString("00010203040506070809")
if err != nil {
panic(err)
@@ -72,9 +81,7 @@ func TestSignVerifyMimc7(t *testing.T) {
func TestSignVerifyPoseidon(t *testing.T) {
var k PrivateKey
_, err := hex.Decode(k[:],
[]byte("0001020304050607080900010203040506070809000102030405060708090001"))
require.Nil(t, err)
hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
msgBuf, err := hex.DecodeString("00010203040506070809")
if err != nil {
panic(err)
@@ -97,7 +104,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
"15383486972088797283337779941324724402501462225528836549661220478783371668959",
sig.R8.Y.String())
assert.Equal(t,
"1672775540645840396591609181675628451599263765380031905495115170613215233181",
"248298168863866362217836334079793350221620631973732197668910946177382043688",
sig.S.String())
ok := pk.VerifyPoseidon(msg, sig)
@@ -109,7 +116,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
assert.Equal(t, ""+
"dfedb4315d3f2eb4de2d3c510d7a987dcab67089c8ace06308827bf5bcbe02a2"+
"9d043ece562a8f82bfc0adb640c0107a7d3a27c1c7c1a6179a0da73de5c1b203",
"28506bce274aa1b3f7e7c2fd7e4fe09bff8f9aa37a42def7994e98f322888c00",
hex.EncodeToString(sigBuf[:]))
ok = pk.VerifyPoseidon(msg, sig2)
@@ -118,9 +125,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
func TestCompressDecompress(t *testing.T) {
var k PrivateKey
_, err := hex.Decode(k[:],
[]byte("0001020304050607080900010203040506070809000102030405060708090001"))
require.Nil(t, err)
hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
pk := k.Public()
for i := 0; i < 64; i++ {
msgBuf, err := hex.DecodeString(fmt.Sprintf("000102030405060708%02d", i))
@@ -137,64 +142,9 @@ func TestCompressDecompress(t *testing.T) {
}
}
func TestSignatureCompScannerValuer(t *testing.T) {
privK := NewRandPrivKey()
var value driver.Valuer //nolint:gosimple this is done to ensure interface compatibility
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
var scan sql.Scanner
value = privK.SignPoseidon(big.NewInt(674238462))
scan = privK.SignPoseidon(big.NewInt(1))
fromDB, err := value.Value()
assert.Nil(t, err)
assert.Nil(t, scan.Scan(fromDB))
assert.Equal(t, value, scan)
}
func TestPublicKeyScannerValuer(t *testing.T) {
privKValue := NewRandPrivKey()
pubKValue := privKValue.Public()
privKScan := NewRandPrivKey()
pubKScan := privKScan.Public()
var value driver.Valuer
var scan sql.Scanner
value = pubKValue
scan = pubKScan
fromDB, err := value.Value()
assert.Nil(t, err)
assert.Nil(t, scan.Scan(fromDB))
assert.Equal(t, value, scan)
}
func TestPublicKeyCompScannerValuer(t *testing.T) {
privKValue := NewRandPrivKey()
pubKCompValue := privKValue.Public().Compress()
privKScan := NewRandPrivKey()
pubKCompScan := privKScan.Public().Compress()
var value driver.Valuer
var scan sql.Scanner
value = &pubKCompValue
scan = &pubKCompScan
fromDB, err := value.Value()
assert.Nil(t, err)
assert.Nil(t, scan.Scan(fromDB))
assert.Equal(t, value, scan)
}
func BenchmarkBabyjubEddsa(b *testing.B) {
var k PrivateKey
_, err := hex.Decode(k[:],
[]byte("0001020304050607080900010203040506070809000102030405060708090001"))
require.Nil(b, err)
hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
pk := k.Public()
const n = 256

View File

@@ -1,20 +1,13 @@
package babyjub
import (
"github.com/dchest/blake512"
"github.com/dchest/blake512" // I have personally reviewed that this module doesn't do anything suspicious
)
// Note on dchest/blake512: This specific blake512 module is compatible with
// the version of Blake512 used at circomlib, and this module has been reviewed
// to don't be doing do anything suspicious.
// Blake512 performs the blake-512 hash over the buffer m. Note that this is
// the original blake from the SHA3 competition and not the new blake2 version.
func Blake512(m []byte) []byte {
h := blake512.New()
_, err := h.Write(m[:])
if err != nil {
panic(err)
}
h.Write(m[:])
return h.Sum(nil)
}

View File

@@ -3,10 +3,13 @@ package constants
import (
"fmt"
"math/big"
"github.com/iden3/go-iden3-crypto/ff"
)
// Q is the order of the integer field (Zq) that fits inside the SNARK.
var Q *big.Int
var QE *ff.Element
// Zero is 0.
var Zero *big.Int

View File

@@ -513,33 +513,15 @@ func (z *Element) String() string {
// ToBigInt returns z as a big.Int in Montgomery form
func (z *Element) ToBigInt(res *big.Int) *big.Int {
if bits.UintSize == 64 {
bits := (*[4]big.Word)(unsafe.Pointer(z))
return res.SetBits(bits[:])
} else {
var bits [8]big.Word
for i := 0; i < len(z); i++ {
bits[i*2] = big.Word(z[i])
bits[i*2+1] = big.Word(z[i] >> 32)
}
return res.SetBits(bits[:])
}
bits := (*[4]big.Word)(unsafe.Pointer(z))
return res.SetBits(bits[:])
}
// ToBigIntRegular returns z as a big.Int in regular form
func (z Element) ToBigIntRegular(res *big.Int) *big.Int {
z.FromMont()
if bits.UintSize == 64 {
bits := (*[4]big.Word)(unsafe.Pointer(&z))
return res.SetBits(bits[:])
} else {
var bits [8]big.Word
for i := 0; i < len(z); i++ {
bits[i*2] = big.Word(z[i])
bits[i*2+1] = big.Word(z[i] >> 32)
}
return res.SetBits(bits[:])
}
bits := (*[4]big.Word)(unsafe.Pointer(&z))
return res.SetBits(bits[:])
}
// SetBigInt sets z to v (regular form) and returns z in Montgomery form
@@ -566,18 +548,8 @@ func (z *Element) SetBigInt(v *big.Int) *Element {
}
// v should
vBits := vv.Bits()
if bits.UintSize == 64 {
for i := 0; i < len(vBits); i++ {
z[i] = uint64(vBits[i])
}
} else {
for i := 0; i < len(vBits); i++ {
if i%2 == 0 {
z[i/2] = uint64(vBits[i])
} else {
z[i/2] |= uint64(vBits[i]) << 32
}
}
for i := 0; i < len(vBits); i++ {
z[i] = uint64(vBits[i])
}
return z.ToMont()
}

View File

@@ -1,6 +1,13 @@
package ff
// NewElement returns a new empty *Element
import "math/big"
func NewElement() *Element {
return &Element{}
}
func (e *Element) BigInt() *big.Int {
b := big.NewInt(0)
e.ToBigIntRegular(b)
return b
}

7
go.mod
View File

@@ -4,8 +4,7 @@ go 1.12
require (
github.com/dchest/blake512 v1.0.0
github.com/ethereum/go-ethereum v1.9.12
github.com/stretchr/testify v1.4.0
golang.org/x/crypto v0.0.0-20200311171314-f7b00557c8c4
golang.org/x/sys v0.0.0-20200323222414-85ca7c5b95cd // indirect
github.com/ethereum/go-ethereum v1.8.27
github.com/stretchr/testify v1.3.0
golang.org/x/crypto v0.0.0-20190621222207-cc06ce4a13d4
)

163
go.sum
View File

@@ -1,173 +1,20 @@
github.com/Azure/azure-pipeline-go v0.2.1/go.mod h1:UGSo8XybXnIGZ3epmeBw7Jdz+HiUVpqIlpz/HKHylF4=
github.com/Azure/azure-pipeline-go v0.2.2/go.mod h1:4rQ/NZncSvGqNkkOsNpOU1tgoNuIlp9AfUH5G1tvCHc=
github.com/Azure/azure-storage-blob-go v0.7.0/go.mod h1:f9YQKtsG1nMisotuTPpO0tjNuEjKRYAcJU8/ydDI++4=
github.com/Azure/go-autorest/autorest v0.9.0/go.mod h1:xyHB1BMZT0cuDHU7I0+g046+BFDTQ8rEZB0s4Yfa6bI=
github.com/Azure/go-autorest/autorest/adal v0.5.0/go.mod h1:8Z9fGy2MpX0PvDjB1pEgQTmVqjGhiHBW7RJJEciWzS0=
github.com/Azure/go-autorest/autorest/adal v0.8.0/go.mod h1:Z6vX6WXXuyieHAXwMj0S6HY6e6wcHn37qQMBQlvY3lc=
github.com/Azure/go-autorest/autorest/date v0.1.0/go.mod h1:plvfp3oPSKwf2DNjlBjWF/7vwR+cUD/ELuzDCXwHUVA=
github.com/Azure/go-autorest/autorest/date v0.2.0/go.mod h1:vcORJHLJEh643/Ioh9+vPmf1Ij9AEBM5FuBIXLmIy0g=
github.com/Azure/go-autorest/autorest/mocks v0.1.0/go.mod h1:OTyCOPRA2IgIlWxVYxBee2F5Gr4kF2zd2J5cFRaIDN0=
github.com/Azure/go-autorest/autorest/mocks v0.2.0/go.mod h1:OTyCOPRA2IgIlWxVYxBee2F5Gr4kF2zd2J5cFRaIDN0=
github.com/Azure/go-autorest/autorest/mocks v0.3.0/go.mod h1:a8FDP3DYzQ4RYfVAxAN3SVSiiO77gL2j2ronKKP0syM=
github.com/Azure/go-autorest/logger v0.1.0/go.mod h1:oExouG+K6PryycPJfVSxi/koC6LSNgds39diKLz7Vrc=
github.com/Azure/go-autorest/tracing v0.5.0/go.mod h1:r/s2XiOKccPW3HrqB+W0TQzfbtp2fGCgRFtBroKn4Dk=
github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU=
github.com/OneOfOne/xxhash v1.2.2/go.mod h1:HSdplMjZKSmBqAxg5vPj2TmRDmfkzw+cTzAElWljhcU=
github.com/OneOfOne/xxhash v1.2.5/go.mod h1:eZbhyaAYD41SGSSsnmcpxVoRiQ/MPUTjUdIIOT9Um7Q=
github.com/StackExchange/wmi v0.0.0-20180116203802-5d049714c4a6 h1:fLjPD/aNc3UIOA6tDi6QXUemppXK3P9BI7mr2hd6gx8=
github.com/StackExchange/wmi v0.0.0-20180116203802-5d049714c4a6/go.mod h1:3eOhrUMpNV+6aFIbp5/iudMxNCF27Vw2OZgy4xEx0Fg=
github.com/VictoriaMetrics/fastcache v1.5.3 h1:2odJnXLbFZcoV9KYtQ+7TH1UOq3dn3AssMgieaezkR4=
github.com/VictoriaMetrics/fastcache v1.5.3/go.mod h1:+jv9Ckb+za/P1ZRg/sulP5Ni1v49daAVERr0H3CuscE=
github.com/alecthomas/template v0.0.0-20160405071501-a0175ee3bccc/go.mod h1:LOuyumcjzFXgccqObfd/Ljyb9UuFJ6TxHnclSeseNhc=
github.com/alecthomas/units v0.0.0-20151022065526-2efee857e7cf/go.mod h1:ybxpYRFXyAe+OPACYpWeL0wqObRcbAqCMya13uyzqw0=
github.com/allegro/bigcache v1.2.1-0.20190218064605-e24eb225f156/go.mod h1:Cb/ax3seSYIx7SuZdm2G2xzfwmv3TPSk2ucNfQESPXM=
github.com/aristanetworks/goarista v0.0.0-20170210015632-ea17b1a17847 h1:rtI0fD4oG/8eVokGVPYJEW1F88p1ZNgXiEIs9thEE4A=
github.com/aristanetworks/goarista v0.0.0-20170210015632-ea17b1a17847/go.mod h1:D/tb0zPVXnP7fmsLZjtdUhSsumbK/ij54UXjjVgMGxQ=
github.com/aws/aws-sdk-go v1.25.48/go.mod h1:KmX6BPdI08NWTb3/sm4ZGu5ShLoqVDhKgpiN924inxo=
github.com/beorn7/perks v0.0.0-20180321164747-3a771d992973/go.mod h1:Dwedo/Wpr24TaqPxmxbtue+5NUziq4I4S80YR8gNf3Q=
github.com/btcsuite/btcd v0.0.0-20171128150713-2e60448ffcc6 h1:Eey/GGQ/E5Xp1P2Lyx1qj007hLZfbi0+CoVeJruGCtI=
github.com/btcsuite/btcd v0.0.0-20171128150713-2e60448ffcc6/go.mod h1:Dmm/EzmjnCiweXmzRIAiUWCInVmPgjkzgv5k4tVyXiQ=
github.com/cespare/cp v0.1.0/go.mod h1:SOGHArjBr4JWaSDEVpWpo/hNg6RoKrls6Oh40hiwW+s=
github.com/cespare/xxhash v1.1.0 h1:a6HrQnmkObjyL+Gs60czilIUGqrzKutQD6XZog3p+ko=
github.com/cespare/xxhash v1.1.0/go.mod h1:XrSqR1VqqWfGrhpAt58auRo0WTKS1nRRg3ghfAqPWnc=
github.com/cespare/xxhash/v2 v2.0.1-0.20190104013014-3767db7a7e18/go.mod h1:HD5P3vAIAh+Y2GAxg0PrPN1P8WkepXGpjbUPDHJqqKM=
github.com/cespare/xxhash/v2 v2.1.1 h1:6MnRN8NT7+YBpUIWxHtefFZOKTAPgGjpQSxqLNn0+qY=
github.com/cespare/xxhash/v2 v2.1.1/go.mod h1:VGX0DQ3Q6kWi7AoAeZDth3/j3BFtOZR5XLFGgcrjCOs=
github.com/cloudflare/cloudflare-go v0.10.2-0.20190916151808-a80f83b9add9/go.mod h1:1MxXX1Ux4x6mqPmjkUgTP1CdXIBXKX7T+Jk9Gxrmx+U=
github.com/cpuguy83/go-md2man/v2 v2.0.0-20190314233015-f79a8a8ca69d/go.mod h1:maD7wRr/U5Z6m/iR4s+kqSMx2CaBsrgA7czyZG/E6dU=
github.com/davecgh/go-spew v1.1.0 h1:ZDRjVQ15GmhC3fiQ8ni8+OwkZQO4DARzQgrnXU1Liz8=
github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
github.com/dchest/blake512 v1.0.0 h1:oDFEQFIqFSeuA34xLtXZ/rWxCXdSjirjzPhey5EUvmA=
github.com/dchest/blake512 v1.0.0/go.mod h1:FV1x7xPPLWukZlpDpWQ88rF/SFwZ5qbskrzhLMB92JI=
github.com/deckarep/golang-set v0.0.0-20180603214616-504e848d77ea/go.mod h1:93vsz/8Wt4joVM7c2AVqh+YRMiUSc14yDtF28KmMOgQ=
github.com/dgrijalva/jwt-go v3.2.0+incompatible/go.mod h1:E3ru+11k8xSBh+hMPgOLZmtrrCbhqsmaPHjLKYnJCaQ=
github.com/dgryski/go-sip13 v0.0.0-20181026042036-e10d5fee7954/go.mod h1:vAd38F8PWV+bWy6jNmig1y/TA+kYO4g3RSRF0IAv0no=
github.com/dlclark/regexp2 v1.2.0/go.mod h1:2pZnwuY/m+8K6iRw6wQdMtk+rH5tNGR1i55kozfMjCc=
github.com/docker/docker v1.4.2-0.20180625184442-8e610b2b55bf/go.mod h1:eEKB0N0r5NX/I1kEveEz05bcu8tLC/8azJZsviup8Sk=
github.com/dop251/goja v0.0.0-20200219165308-d1232e640a87/go.mod h1:Mw6PkjjMXWbTj+nnj4s3QPXq1jaT0s5pC0iFD4+BOAA=
github.com/edsrzf/mmap-go v0.0.0-20160512033002-935e0e8a636c/go.mod h1:YO35OhQPt3KJa3ryjFM5Bs14WD66h8eGKpfaBNrHW5M=
github.com/elastic/gosigar v0.8.1-0.20180330100440-37f05ff46ffa h1:XKAhUk/dtp+CV0VO6mhG2V7jA9vbcGcnYF/Ay9NjZrY=
github.com/elastic/gosigar v0.8.1-0.20180330100440-37f05ff46ffa/go.mod h1:cdorVVzy1fhmEqmtgqkoE3bYtCfSCkVyjTyCIo22xvs=
github.com/ethereum/go-ethereum v1.9.12 h1:EPtimwsp/KGDSiXcNunzsI4kefdsMHZGJntKx3fvbaI=
github.com/ethereum/go-ethereum v1.9.12/go.mod h1:PvsVkQmhZFx92Y+h2ylythYlheEDt/uBgFbl61Js/jo=
github.com/fatih/color v1.3.0/go.mod h1:Zm6kSWBoL9eyXnKyktHP6abPY2pDugNf5KwzbycvMj4=
github.com/fjl/memsize v0.0.0-20180418122429-ca190fb6ffbc/go.mod h1:VvhXpOYNQvB+uIk2RvXzuaQtkQJzzIx6lSBe1xv7hi0=
github.com/fsnotify/fsnotify v1.4.7/go.mod h1:jwhsz4b93w/PPRr/qN1Yymfu8t87LnFCMoQvtojpjFo=
github.com/gballet/go-libpcsclite v0.0.0-20190607065134-2772fd86a8ff/go.mod h1:x7DCsMOv1taUwEWCzT4cmDeAkigA5/QCwUodaVOe8Ww=
github.com/go-kit/kit v0.8.0/go.mod h1:xBxKIO96dXMWWy0MnWVtmwkA9/13aqxPnvrjFYMA2as=
github.com/go-logfmt/logfmt v0.3.0/go.mod h1:Qt1PoO58o5twSAckw1HlFXLmHsOX5/0LbT9GBnD5lWE=
github.com/go-ole/go-ole v1.2.1 h1:2lOsA72HgjxAuMlKpFiCbHTvu44PIVkZ5hqm3RSdI/E=
github.com/go-ole/go-ole v1.2.1/go.mod h1:7FAglXiTm7HKlQRDeOQ6ZNUHidzCWXuZWq/1dTyBNF8=
github.com/go-sourcemap/sourcemap v2.1.2+incompatible/go.mod h1:F8jJfvm2KbVjc5NqelyYJmf/v5J0dwNLS2mL4sNA1Jg=
github.com/go-stack/stack v1.8.0 h1:5SgMzNM5HxrEjV0ww2lTmX6E2Izsfxas4+YHWRs3Lsk=
github.com/go-stack/stack v1.8.0/go.mod h1:v0f6uXyyMGvRgIKkXu+yp6POWl0qKG85gN/melR3HDY=
github.com/gogo/protobuf v1.1.1/go.mod h1:r8qH/GZQm5c6nD/R0oafs1akxWv10x8SbQlK7atdtwQ=
github.com/golang/protobuf v1.2.0/go.mod h1:6lQm79b+lXiMfvg/cZm0SGofjICqVBUtrP5yJMmIC1U=
github.com/golang/protobuf v1.3.2-0.20190517061210-b285ee9cfc6c/go.mod h1:6lQm79b+lXiMfvg/cZm0SGofjICqVBUtrP5yJMmIC1U=
github.com/golang/snappy v0.0.1 h1:Qgr9rKW7uDUkrbSmQeiDsGa8SjGyCOGtuasMWwvp2P4=
github.com/golang/snappy v0.0.1/go.mod h1:/XxbfmMg8lxefKM7IXC3fBNl/7bRcc72aCRzEWrmP2Q=
github.com/google/go-cmp v0.3.1/go.mod h1:8QqcDgzrUqlUb/G2PQTWiueGozuR1884gddMywk6iLU=
github.com/gorilla/websocket v1.4.1-0.20190629185528-ae1634f6a989/go.mod h1:E7qHFY5m1UJ88s3WnNqhKjPHQ0heANvMoAMk2YaljkQ=
github.com/graph-gophers/graphql-go v0.0.0-20191115155744-f33e81362277/go.mod h1:9CQHMSxwO4MprSdzoIEobiHpoLtHm77vfxsvsIN5Vuc=
github.com/hashicorp/golang-lru v0.0.0-20160813221303-0a025b7e63ad/go.mod h1:/m3WP610KZHVQ1SGc6re/UDhFvYD7pJ4Ao+sR/qLZy8=
github.com/hpcloud/tail v1.0.0/go.mod h1:ab1qPbhIpdTxEkNHXyeSf5vhxWSCs/tWer42PpOxQnU=
github.com/huin/goupnp v0.0.0-20161224104101-679507af18f3/go.mod h1:MZ2ZmwcBpvOoJ22IJsc7va19ZwoheaBk43rKg12SKag=
github.com/influxdata/influxdb v1.2.3-0.20180221223340-01288bdb0883/go.mod h1:qZna6X/4elxqT3yI9iZYdZrWWdeFOOprn86kgg4+IzY=
github.com/jackpal/go-nat-pmp v1.0.2-0.20160603034137-1fa385a6f458/go.mod h1:QPH045xvCAeXUZOxsnwmrtiCoxIr9eob+4orBN1SBKc=
github.com/jmespath/go-jmespath v0.0.0-20180206201540-c2b33e8439af/go.mod h1:Nht3zPeWKUH0NzdCt2Blrr5ys8VGpn0CEB0cQHVjt7k=
github.com/julienschmidt/httprouter v1.1.1-0.20170430222011-975b5c4c7c21/go.mod h1:SYymIcj16QtmaHHD7aYtjjsJG7VTCxuUUipMqKk8s4w=
github.com/karalabe/usb v0.0.0-20190919080040-51dc0efba356/go.mod h1:Od972xHfMJowv7NGVDiWVxk2zxnWgjLlJzE+F4F7AGU=
github.com/kr/logfmt v0.0.0-20140226030751-b84e30acd515/go.mod h1:+0opPa2QZZtGFBFZlji/RkVcI2GknAs/DXo4wKdlNEc=
github.com/kr/pretty v0.1.0 h1:L/CwN0zerZDmRFUapSPitk6f+Q3+0za1rQkzVuMiMFI=
github.com/kr/pretty v0.1.0/go.mod h1:dAy3ld7l9f0ibDNOQOHHMYYIIbhfbHSm3C4ZsoJORNo=
github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
github.com/kr/text v0.1.0 h1:45sCR5RtlFHMR4UwH9sdQ5TC8v0qDQCHnXt+kaKSTVE=
github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
github.com/kylelemons/godebug v1.1.0/go.mod h1:9/0rRGxNHcop5bhtWyNeEfOS8JIWk580+fNqagV/RAw=
github.com/mattn/go-colorable v0.1.0/go.mod h1:9vuHe8Xs5qXnSaW/c/ABM9alt+Vo+STaOChaDxuIBZU=
github.com/mattn/go-ieproxy v0.0.0-20190610004146-91bb50d98149/go.mod h1:31jz6HNzdxOmlERGGEc4v/dMssOfmp2p5bT/okiKFFc=
github.com/mattn/go-ieproxy v0.0.0-20190702010315-6dee0af9227d/go.mod h1:31jz6HNzdxOmlERGGEc4v/dMssOfmp2p5bT/okiKFFc=
github.com/mattn/go-isatty v0.0.5-0.20180830101745-3fb116b82035/go.mod h1:M+lRXTBqGeGNdLjl/ufCoiOlB5xdOkqRJdNxMWT7Zi4=
github.com/mattn/go-runewidth v0.0.3/go.mod h1:LwmH8dsx7+W8Uxz3IHJYH5QSwggIsqBzpuz5H//U1FU=
github.com/mattn/go-runewidth v0.0.4/go.mod h1:LwmH8dsx7+W8Uxz3IHJYH5QSwggIsqBzpuz5H//U1FU=
github.com/matttproud/golang_protobuf_extensions v1.0.1/go.mod h1:D8He9yQNgCq6Z5Ld7szi9bcBfOoFv/3dc6xSMkL2PC0=
github.com/naoina/go-stringutil v0.1.0/go.mod h1:XJ2SJL9jCtBh+P9q5btrd/Ylo8XwT/h1USek5+NqSA0=
github.com/naoina/toml v0.1.2-0.20170918210437-9fafd6967416/go.mod h1:NBIhNtsFMo3G2szEBne+bO4gS192HuIYRqfvOWb4i1E=
github.com/oklog/ulid v1.3.1/go.mod h1:CirwcVhetQ6Lv90oh/F+FBtV6XMibvdAFo93nm5qn4U=
github.com/olekukonko/tablewriter v0.0.1/go.mod h1:vsDQFd/mU46D+Z4whnwzcISnGGzXWMclvtLoiIKAKIo=
github.com/olekukonko/tablewriter v0.0.2-0.20190409134802-7e037d187b0c/go.mod h1:vsDQFd/mU46D+Z4whnwzcISnGGzXWMclvtLoiIKAKIo=
github.com/onsi/ginkgo v1.6.0/go.mod h1:lLunBs/Ym6LB5Z9jYTR76FiuTmxDTDusOGeTQH+WWjE=
github.com/onsi/ginkgo v1.7.0/go.mod h1:lLunBs/Ym6LB5Z9jYTR76FiuTmxDTDusOGeTQH+WWjE=
github.com/onsi/gomega v1.4.3/go.mod h1:ex+gbHU/CVuBBDIJjb2X0qEXbFg53c61hWP/1CpauHY=
github.com/opentracing/opentracing-go v1.1.0/go.mod h1:UkNAQd3GIcIGf0SeVgPpRdFStlNbqXla1AfSYxPUl2o=
github.com/pborman/uuid v0.0.0-20170112150404-1b00554d8222/go.mod h1:VyrYX9gd7irzKovcSS6BIIEwPRkP2Wm2m9ufcdFSJ34=
github.com/peterh/liner v1.1.1-0.20190123174540-a2c9a5303de7/go.mod h1:CRroGNssyjTd/qIG2FyxByd2S8JEAZXBl4qUrZf8GS0=
github.com/pkg/errors v0.8.0/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
github.com/pkg/errors v0.8.1 h1:iURUrRGxPUNPdy5/HRSm+Yj6okJ6UtLINN0Q9M4+h3I=
github.com/pkg/errors v0.8.1/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
github.com/ethereum/go-ethereum v1.8.27 h1:d+gkiLaBDk5fn3Pe/xNVaMrB/ozI+AUB2IlVBp29IrY=
github.com/ethereum/go-ethereum v1.8.27/go.mod h1:PwpWDrCLZrV+tfrhqqF6kPknbISMHaJv9Ln3kPCZLwY=
github.com/iden3/go-iden3 v0.0.5 h1:NV6HXnLmp+1YmKd2FmymzU6OAP77q1WWDcB/B+BUL9g=
github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
github.com/prometheus/client_golang v0.9.1/go.mod h1:7SWBe2y4D6OKWSNQJUaRYU/AaXPKyh/dDVn+NZz0KFw=
github.com/prometheus/client_model v0.0.0-20180712105110-5c3871d89910/go.mod h1:MbSGuTsp3dbXC40dX6PRTWyKYBIrTGTE9sqQNg2J8bo=
github.com/prometheus/common v0.0.0-20181113130724-41aa239b4cce/go.mod h1:daVV7qP5qjZbuso7PdcryaAu0sAZbrN9i7WWcTMWvro=
github.com/prometheus/procfs v0.0.0-20181005140218-185b4288413d/go.mod h1:c3At6R/oaqEKCNdg8wHV1ftS6bRYblBhIjjI8uT2IGk=
github.com/prometheus/tsdb v0.6.2-0.20190402121629-4f204dcbc150/go.mod h1:qhTCs0VvXwvX/y3TZrWD7rabWM+ijKTux40TwIPHuXU=
github.com/rjeczalik/notify v0.9.1/go.mod h1:rKwnCoCGeuQnwBtTSPL9Dad03Vh2n40ePRrjvIXnJho=
github.com/rs/cors v0.0.0-20160617231935-a62a804a8a00/go.mod h1:gFx+x8UowdsKA9AchylcLynDq+nNFfI8FkUZdN/jGCU=
github.com/rs/xhandler v0.0.0-20160618193221-ed27b6fd6521/go.mod h1:RvLn4FgxWubrpZHtQLnOf6EwhN2hEMusxZOhcW9H3UQ=
github.com/russross/blackfriday/v2 v2.0.1/go.mod h1:+Rmxgy9KzJVeS9/2gXHxylqXiyQDYRxCVz55jmeOWTM=
github.com/shurcooL/sanitized_anchor_name v1.0.0/go.mod h1:1NzhyTcUVG4SuEtjjoZeVRXNmyL/1OwPU0+IJeTBvfc=
github.com/spaolacci/murmur3 v0.0.0-20180118202830-f09979ecbc72/go.mod h1:JwIasOWyU6f++ZhiEuf87xNszmSA2myDM2Kzu9HwQUA=
github.com/spaolacci/murmur3 v1.0.1-0.20190317074736-539464a789e9/go.mod h1:JwIasOWyU6f++ZhiEuf87xNszmSA2myDM2Kzu9HwQUA=
github.com/status-im/keycard-go v0.0.0-20190316090335-8537d3370df4/go.mod h1:RZLeN1LMWmRsyYjvAu+I6Dm9QmlDaIIt+Y+4Kd7Tp+Q=
github.com/steakknife/bloomfilter v0.0.0-20180922174646-6819c0d2a570 h1:gIlAHnH1vJb5vwEjIp5kBj/eu99p/bl0Ay2goiPe5xE=
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=
github.com/stretchr/testify v1.3.0/go.mod h1:M5WIy9Dh21IEIfnGCwXGc5bZfKNJtfHm1UVUgZn+9EI=
github.com/stretchr/testify v1.4.0 h1:2E4SXV/wtOkTonXsotYi4li6zVWxYlZuYNCXe9XRJyk=
github.com/stretchr/testify v1.4.0/go.mod h1:j7eGeouHqKxXV5pUuKE4zz7dFj8WfuZ+81PSLYec5m4=
github.com/syndtr/goleveldb v1.0.1-0.20190923125748-758128399b1d/go.mod h1:9OrXJhf154huy1nPWmuSrkgjPUtUNhA+Zmy+6AESzuA=
github.com/tyler-smith/go-bip39 v1.0.1-0.20181017060643-dbb3b84ba2ef/go.mod h1:sJ5fKU0s6JVwZjjcUEX2zFOnvq0ASQ2K9Zr6cf67kNs=
github.com/urfave/cli v1.22.1/go.mod h1:Gos4lmkARVdJ6EkW0WaNv/tZAAMe9V7XWyB60NtXRu0=
github.com/wsddn/go-ecdh v0.0.0-20161211032359-48726bab9208/go.mod h1:IotVbo4F+mw0EzQ08zFqg7pK3FebNXpaMsRy2RT+Ees=
golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
golang.org/x/crypto v0.0.0-20200311171314-f7b00557c8c4 h1:QmwruyY+bKbDDL0BaglrbZABEali68eoMFhTZpCjYVA=
golang.org/x/crypto v0.0.0-20200311171314-f7b00557c8c4/go.mod h1:LzIPMQfyMNhhGPhUkYOs5KpL4U8rLKemX1yGLhDgUto=
golang.org/x/net v0.0.0-20180906233101-161cd47e91fd/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
golang.org/x/crypto v0.0.0-20190621222207-cc06ce4a13d4 h1:ydJNl0ENAG67pFbB+9tfhiL2pYqLhfoaZFw/cjLhY4A=
golang.org/x/crypto v0.0.0-20190621222207-cc06ce4a13d4/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
golang.org/x/net v0.0.0-20200301022130-244492dfa37a/go.mod h1:z5CRVTTTmAJ677TzLLGU+0bjPO0LkuOLi4/5GtJWs/s=
golang.org/x/sync v0.0.0-20180314180146-1d60e4601c6f/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
golang.org/x/sync v0.0.0-20181108010431-42b317875d0f/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
golang.org/x/sys v0.0.0-20180909124046-d0be0721c37e/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
golang.org/x/sys v0.0.0-20181107165924-66b7b1311ac8/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
golang.org/x/sys v0.0.0-20190412213103-97732733099d h1:+R4KGOnez64A81RvjARKc4UT5/tI9ujCIVX+P5KiHuI=
golang.org/x/sys v0.0.0-20190412213103-97732733099d/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
golang.org/x/sys v0.0.0-20200302150141-5c8b2ff67527 h1:uYVVQ9WP/Ds2ROhcaGPeIdVq0RIXVLwsHlnvJ+cT1So=
golang.org/x/sys v0.0.0-20200302150141-5c8b2ff67527/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
golang.org/x/sys v0.0.0-20200323222414-85ca7c5b95cd h1:xhmwyvizuTgC2qz7ZlMluP20uW+C3Rm0FD/WLDX8884=
golang.org/x/sys v0.0.0-20200323222414-85ca7c5b95cd/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
golang.org/x/text v0.3.2/go.mod h1:bEr9sfX3Q8Zfm5fL9x+3itogRgK3+ptLWKqgva+5dAk=
golang.org/x/time v0.0.0-20190308202827-9d24e82272b4/go.mod h1:tRJNPiyCQ0inRvYxbN9jk5I+vvW/OXSQhTDSoE431IQ=
golang.org/x/tools v0.0.0-20180917221912-90fa682c2a6e/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
gopkg.in/alecthomas/kingpin.v2 v2.2.6/go.mod h1:FMv+mEhP44yOT+4EoQTLFTRgOQ1FBLkstjWtayDeSgw=
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127 h1:qIbj1fsPNlZgppZ+VLlY7N33q108Sa+fhmuc+sWQYwY=
gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
gopkg.in/fsnotify.v1 v1.4.7/go.mod h1:Tz8NjZHkW78fSQdbUxIjBTcgA1z1m8ZHf0WmKUhAMys=
gopkg.in/natefinch/npipe.v2 v2.0.0-20160621034901-c1b8fa8bdcce/go.mod h1:5AcXVHNjg+BDxry382+8OKon8SEWiKktQR07RKPsv1c=
gopkg.in/olebedev/go-duktape.v3 v3.0.0-20190213234257-ec84240a7772/go.mod h1:uAJfkITjFhyEEuUfm7bsmCZRbW5WRq8s9EY8HZ6hCns=
gopkg.in/tomb.v1 v1.0.0-20141024135613-dd632973f1e7/go.mod h1:dt/ZhP58zS4L8KSrWDmTeBkI65Dw0HsyUHuEVlX15mw=
gopkg.in/urfave/cli.v1 v1.20.0/go.mod h1:vuBzUtMdQeixQj8LVd+/98pzhxNGQoyuPBlsXHOQNO0=
gopkg.in/yaml.v2 v2.2.1/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
gopkg.in/yaml.v2 v2.2.2 h1:ZCJp+EgiOT7lHqUV2J862kp8Qj64Jo6az82+3Td9dZw=
gopkg.in/yaml.v2 v2.2.2/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
gotest.tools v2.2.0+incompatible/go.mod h1:DsYFclhRJ6vuDpmuTbkuFWG+y2sxOXAzmJt81HFBacw=

View File

@@ -10,7 +10,6 @@ import (
"github.com/iden3/go-iden3-crypto/utils"
)
// SEED defines the seed used to constants
const SEED = "mimc"
var constants = generateConstantsData()
@@ -48,9 +47,8 @@ func getConstants(seed string, nRounds int) []*ff.Element {
return cts
}
// MIMC7HashGeneric performs the MIMC7 hash over a *big.Int, in a generic way,
// where it can be specified the Finite Field over R, and the number of rounds
func MIMC7HashGeneric(xInBI, kBI *big.Int, nRounds int) *big.Int { //nolint:golint
// MIMC7HashGeneric performs the MIMC7 hash over a *big.Int, in a generic way, where it can be specified the Finite Field over R, and the number of rounds
func MIMC7HashGeneric(xInBI, kBI *big.Int, nRounds int) *big.Int {
xIn := ff.NewElement().SetBigInt(xInBI)
k := ff.NewElement().SetBigInt(kBI)
@@ -74,8 +72,7 @@ func MIMC7HashGeneric(xInBI, kBI *big.Int, nRounds int) *big.Int { //nolint:goli
return res
}
// HashGeneric performs the MIMC7 hash over a *big.Int array, in a generic way,
// where it can be specified the Finite Field over R, and the number of rounds
// HashGeneric performs the MIMC7 hash over a *big.Int array, in a generic way, where it can be specified the Finite Field over R, and the number of rounds
func HashGeneric(iv *big.Int, arr []*big.Int, nRounds int) (*big.Int, error) {
if !utils.CheckBigIntArrayInField(arr) {
return nil, errors.New("inputs values not inside Finite Field")
@@ -91,9 +88,8 @@ func HashGeneric(iv *big.Int, arr []*big.Int, nRounds int) (*big.Int, error) {
return r, nil
}
// MIMC7Hash performs the MIMC7 hash over a *big.Int, using the Finite Field
// over R and the number of rounds setted in the `constants` variable
func MIMC7Hash(xInBI, kBI *big.Int) *big.Int { //nolint:golint
// MIMC7Hash performs the MIMC7 hash over a *big.Int, using the Finite Field over R and the number of rounds setted in the `constants` variable
func MIMC7Hash(xInBI, kBI *big.Int) *big.Int {
xIn := ff.NewElement().SetBigInt(xInBI)
k := ff.NewElement().SetBigInt(kBI)
@@ -141,7 +137,7 @@ func Hash(arr []*big.Int, key *big.Int) (*big.Int, error) {
// HashBytes hashes a msg byte slice by blocks of 31 bytes encoded as
// little-endian
func HashBytes(b []byte) *big.Int {
func HashBytes(b []byte) (*big.Int, error) {
n := 31
bElems := make([]*big.Int, 0, len(b)/n+1)
for i := 0; i < len(b)/n; i++ {
@@ -154,9 +150,5 @@ func HashBytes(b []byte) *big.Int {
utils.SetBigIntFromLEBytes(v, b[(len(b)/n)*n:])
bElems = append(bElems, v)
}
h, err := Hash(bElems, nil)
if err != nil {
panic(err)
}
return h
return Hash(bElems, nil)
}

View File

@@ -11,13 +11,9 @@ import (
func TestKeccak256(t *testing.T) {
res := crypto.Keccak256([]byte(SEED))
assert.Equal(t,
"b6e489e6b37224a50bebfddbe7d89fa8fdcaa84304a70bd13f79b5d9f7951e9e",
hex.EncodeToString(res))
assert.Equal(t, "b6e489e6b37224a50bebfddbe7d89fa8fdcaa84304a70bd13f79b5d9f7951e9e", hex.EncodeToString(res))
c := new(big.Int).SetBytes(crypto.Keccak256([]byte(SEED)))
assert.Equal(t,
"82724731331859054037315113496710413141112897654334566532528783843265082629790",
c.String())
assert.Equal(t, "82724731331859054037315113496710413141112897654334566532528783843265082629790", c.String())
}
func TestMIMC7Generic(t *testing.T) {
@@ -29,14 +25,10 @@ func TestMIMC7Generic(t *testing.T) {
// Generic Hash
mhg := MIMC7HashGeneric(b1, b2, 91)
assert.Equal(t,
"10594780656576967754230020536574539122676596303354946869887184401991294982664",
mhg.String())
assert.Equal(t, "10594780656576967754230020536574539122676596303354946869887184401991294982664", mhg.String())
hg, err := HashGeneric(big.NewInt(0), bigArray, 91)
assert.Nil(t, err)
assert.Equal(t,
"6464402164086696096195815557694604139393321133243036833927490113253119343397",
(*big.Int)(hg).String())
assert.Equal(t, "6464402164086696096195815557694604139393321133243036833927490113253119343397", (*big.Int)(hg).String())
}
func TestMIMC7(t *testing.T) {
@@ -51,8 +43,7 @@ func TestMIMC7(t *testing.T) {
h1, err := Hash(bigArray1, nil)
assert.Nil(t, err)
// same hash value than the iden3js and circomlib tests:
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(h1).Bytes()),
"0x237c92644dbddb86d8a259e0e923aaab65a93f1ec5758b8799988894ac0958fd")
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(h1).Bytes()), "0x237c92644dbddb86d8a259e0e923aaab65a93f1ec5758b8799988894ac0958fd")
// h2a, hash of 2 elements
bigArray2a := []*big.Int{b78, b41}
@@ -60,22 +51,19 @@ func TestMIMC7(t *testing.T) {
h2a, err := Hash(bigArray2a, nil)
assert.Nil(t, err)
// same hash value than the iden3js and circomlib tests:
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(h2a).Bytes()),
"0x067f3202335ea256ae6e6aadcd2d5f7f4b06a00b2d1e0de903980d5ab552dc70")
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(h2a).Bytes()), "0x067f3202335ea256ae6e6aadcd2d5f7f4b06a00b2d1e0de903980d5ab552dc70")
// h2b, hash of 2 elements
bigArray2b := []*big.Int{b12, b45}
mh2b := MIMC7Hash(b12, b45)
assert.Nil(t, err)
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(mh2b).Bytes()),
"0x2ba7ebad3c6b6f5a20bdecba2333c63173ca1a5f2f49d958081d9fa7179c44e4")
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(mh2b).Bytes()), "0x2ba7ebad3c6b6f5a20bdecba2333c63173ca1a5f2f49d958081d9fa7179c44e4")
h2b, err := Hash(bigArray2b, nil)
assert.Nil(t, err)
// same hash value than the iden3js and circomlib tests:
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(h2b).Bytes()),
"0x15ff7fe9793346a17c3150804bcb36d161c8662b110c50f55ccb7113948d8879")
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(h2b).Bytes()), "0x15ff7fe9793346a17c3150804bcb36d161c8662b110c50f55ccb7113948d8879")
// h4, hash of 4 elements
bigArray4 := []*big.Int{b12, b45, b78, b41}
@@ -83,14 +71,12 @@ func TestMIMC7(t *testing.T) {
h4, err := Hash(bigArray4, nil)
assert.Nil(t, err)
// same hash value than the iden3js and circomlib tests:
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(h4).Bytes()),
"0x284bc1f34f335933a23a433b6ff3ee179d682cd5e5e2fcdd2d964afa85104beb")
assert.Equal(t, "0x"+hex.EncodeToString((*big.Int)(h4).Bytes()), "0x284bc1f34f335933a23a433b6ff3ee179d682cd5e5e2fcdd2d964afa85104beb")
msg := []byte("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.") //nolint:lll
hmsg := HashBytes(msg)
assert.Equal(t,
"16855787120419064316734350414336285711017110414939748784029922801367685456065",
hmsg.String())
msg := []byte("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.")
hmsg, err := HashBytes(msg)
assert.Nil(t, err)
assert.Equal(t, "16855787120419064316734350414336285711017110414939748784029922801367685456065", hmsg.String())
}
func BenchmarkMIMC7(b *testing.B) {
@@ -101,6 +87,6 @@ func BenchmarkMIMC7(b *testing.B) {
bigArray4 := []*big.Int{b12, b45, b78, b41}
for i := 0; i < b.N; i++ {
Hash(bigArray4, nil) //nolint:errcheck,gosec
Hash(bigArray4, nil)
}
}

File diff suppressed because it is too large Load Diff

View File

@@ -2,84 +2,144 @@ package poseidon
import (
"errors"
"fmt"
"math/big"
"strconv"
"github.com/iden3/go-iden3-crypto/constants"
"github.com/iden3/go-iden3-crypto/ff"
"github.com/iden3/go-iden3-crypto/utils"
"golang.org/x/crypto/blake2b"
)
const NROUNDSF = 8 //nolint:golint
const SEED = "poseidon"
const NROUNDSF = 8
const NROUNDSP = 57
const T = 6
var NROUNDSP = []int{56, 57, 56, 60, 60, 63, 64, 63} //nolint:golint
var constC []*ff.Element
var constM [T][T]*ff.Element
func zero() *ff.Element {
func Zero() *ff.Element {
return ff.NewElement()
}
func modQ(v *big.Int) {
v.Mod(v, constants.Q)
}
func init() {
constC = getPseudoRandom(SEED+"_constants", NROUNDSF+NROUNDSP)
constM = getMDS()
}
func getPseudoRandom(seed string, n int) []*ff.Element {
res := make([]*ff.Element, n)
hash := blake2b.Sum256([]byte(seed))
for i := 0; i < n; i++ {
hashBigInt := big.NewInt(int64(0))
res[i] = ff.NewElement().SetBigInt(utils.SetBigIntFromLEBytes(hashBigInt, hash[:]))
hash = blake2b.Sum256(hash[:])
}
return res
}
func nonceToString(n int) string {
r := strconv.Itoa(n)
for len(r) < 4 {
r = "0" + r
}
return r
}
// https://eprint.iacr.org/2019/458.pdf pag.8
func getMDS() [T][T]*ff.Element {
nonce := 0
cauchyMatrix := getPseudoRandom(SEED+"_matrix_"+nonceToString(nonce), T*2)
for !checkAllDifferent(cauchyMatrix) {
nonce += 1
cauchyMatrix = getPseudoRandom(SEED+"_matrix_"+nonceToString(nonce), T*2)
}
var m [T][T]*ff.Element
for i := 0; i < T; i++ {
for j := 0; j < T; j++ {
m[i][j] = ff.NewElement().Sub(cauchyMatrix[i], cauchyMatrix[T+j])
m[i][j].Inverse(m[i][j])
}
}
return m
}
func checkAllDifferent(v []*ff.Element) bool {
for i := 0; i < len(v); i++ {
if v[i].Equal(ff.NewElement()) {
return false
}
for j := i + 1; j < len(v); j++ {
if v[i].Equal(v[j]) {
return false
}
}
}
return true
}
// ark computes Add-Round Key, from the paper https://eprint.iacr.org/2019/458.pdf
func ark(state []*ff.Element, c []*ff.Element, it int) {
for i := 0; i < len(state); i++ {
state[i].Add(state[i], c[it+i])
func ark(state [T]*ff.Element, c *ff.Element) {
for i := 0; i < T; i++ {
state[i].Add(state[i], c)
}
}
// exp5 performs x^5 mod p
// cubic performs x^5 mod p
// https://eprint.iacr.org/2019/458.pdf page 8
func exp5(a *ff.Element) {
func cubic(a *ff.Element) {
a.Exp(*a, 5)
}
// sbox https://eprint.iacr.org/2019/458.pdf page 6
func sbox(nRoundsF, nRoundsP int, state []*ff.Element, i int) {
if (i < nRoundsF/2) || (i >= nRoundsF/2+nRoundsP) {
for j := 0; j < len(state); j++ {
exp5(state[j])
func sbox(state [T]*ff.Element, i int) {
if (i < NROUNDSF/2) || (i >= NROUNDSF/2+NROUNDSP) {
for j := 0; j < T; j++ {
cubic(state[j])
}
} else {
exp5(state[0])
cubic(state[0])
}
}
// mix returns [[matrix]] * [vector]
func mix(state []*ff.Element, newState []*ff.Element, m [][]*ff.Element) {
mul := zero()
for i := 0; i < len(state); i++ {
func mix(state [T]*ff.Element, newState [T]*ff.Element, m [T][T]*ff.Element) {
mul := Zero()
for i := 0; i < T; i++ {
newState[i].SetUint64(0)
for j := 0; j < len(state); j++ {
for j := 0; j < T; j++ {
mul.Mul(m[i][j], state[j])
newState[i].Add(newState[i], mul)
}
}
}
// Hash computes the Poseidon hash for the given inputs
func Hash(inpBI []*big.Int) (*big.Int, error) {
t := len(inpBI) + 1
if len(inpBI) == 0 || len(inpBI) >= len(NROUNDSP)-1 {
return nil, fmt.Errorf("invalid inputs length %d, max %d", len(inpBI), len(NROUNDSP)-1)
}
// PoseidonHash computes the Poseidon hash for the given inputs
func PoseidonHash(inpBI [T]*big.Int) (*big.Int, error) {
if !utils.CheckBigIntArrayInField(inpBI[:]) {
return nil, errors.New("inputs values not inside Finite Field")
}
inp := utils.BigIntArrayToElementArray(inpBI[:])
state := make([]*ff.Element, t)
state[0] = zero()
copy(state[1:], inp[:])
nRoundsF := NROUNDSF
nRoundsP := NROUNDSP[t-2]
newState := make([]*ff.Element, t)
for i := 0; i < t; i++ {
newState[i] = zero()
state := [T]*ff.Element{}
for i := 0; i < T; i++ {
state[i] = ff.NewElement().Set(inp[i])
}
// ARK --> SBox --> M, https://eprint.iacr.org/2019/458.pdf pag.5
for i := 0; i < nRoundsF+nRoundsP; i++ {
ark(state, c.c[t-2], i*t)
sbox(nRoundsF, nRoundsP, state, i)
mix(state, newState, c.m[t-2])
var newState [T]*ff.Element
for i := 0; i < T; i++ {
newState[i] = Zero()
}
for i := 0; i < NROUNDSF+NROUNDSP; i++ {
ark(state, constC[i])
sbox(state, i)
mix(state, newState, constM)
state, newState = newState, state
}
rE := state[0]
@@ -87,3 +147,51 @@ func Hash(inpBI []*big.Int) (*big.Int, error) {
rE.ToBigIntRegular(r)
return r, nil
}
// Hash performs the Poseidon hash over a ff.Element array
// in chunks of 5 elements
func Hash(arr []*big.Int) (*big.Int, error) {
r := big.NewInt(int64(1))
for i := 0; i < len(arr); i = i + T - 1 {
var toHash [T]*big.Int
j := 0
for ; j < T-1; j++ {
if i+j >= len(arr) {
break
}
toHash[j] = arr[i+j]
}
toHash[j] = r
j++
for ; j < T; j++ {
toHash[j] = big.NewInt(0)
}
ph, err := PoseidonHash(toHash)
if err != nil {
return nil, err
}
modQ(r.Add(r, ph))
}
return r, nil
}
// HashBytes hashes a msg byte slice by blocks of 31 bytes encoded as
// little-endian
func HashBytes(b []byte) (*big.Int, error) {
n := 31
bElems := make([]*big.Int, 0, len(b)/n+1)
for i := 0; i < len(b)/n; i++ {
v := big.NewInt(int64(0))
utils.SetBigIntFromLEBytes(v, b[n*i:n*(i+1)])
bElems = append(bElems, v)
}
if len(b)%n != 0 {
v := big.NewInt(int64(0))
utils.SetBigIntFromLEBytes(v, b[(len(b)/n)*n:])
bElems = append(bElems, v)
}
return Hash(bElems)
}

View File

@@ -12,86 +12,111 @@ import (
func TestBlake2bVersion(t *testing.T) {
h := blake2b.Sum256([]byte("poseidon_constants"))
assert.Equal(t,
"e57ba154fb2c47811dc1a2369b27e25a44915b4e4ece4eb8ec74850cb78e01b1",
hex.EncodeToString(h[:]))
assert.Equal(t, "e57ba154fb2c47811dc1a2369b27e25a44915b4e4ece4eb8ec74850cb78e01b1", hex.EncodeToString(h[:]))
}
func TestPoseidonHash(t *testing.T) {
b0 := big.NewInt(0)
func TestPoseidon(t *testing.T) {
b1 := big.NewInt(1)
b2 := big.NewInt(2)
h, err := Hash([]*big.Int{b1})
h, err := Hash([]*big.Int{b1, b2})
assert.Nil(t, err)
assert.Equal(t,
"18586133768512220936620570745912940619677854269274689475585506675881198879027",
h.String())
h, err = Hash([]*big.Int{b1, b2})
assert.Nil(t, err)
assert.Equal(t,
"7853200120776062878684798364095072458815029376092732009249414926327459813530",
h.String())
h, err = Hash([]*big.Int{b1, b2, b0, b0, b0})
assert.Nil(t, err)
assert.Equal(t,
"1018317224307729531995786483840663576608797660851238720571059489595066344487",
h.String())
h, err = Hash([]*big.Int{b1, b2, b0, b0, b0, b0})
assert.Nil(t, err)
assert.Equal(t,
"15336558801450556532856248569924170992202208561737609669134139141992924267169",
h.String())
assert.Equal(t, "4932297968297298434239270129193057052722409868268166443802652458940273154855", h.String())
b3 := big.NewInt(3)
b4 := big.NewInt(4)
h, err = Hash([]*big.Int{b3, b4, b0, b0, b0})
h, err = Hash([]*big.Int{b3, b4})
assert.Nil(t, err)
assert.Equal(t,
"5811595552068139067952687508729883632420015185677766880877743348592482390548",
h.String())
h, err = Hash([]*big.Int{b3, b4, b0, b0, b0, b0})
assert.Nil(t, err)
assert.Equal(t,
"12263118664590987767234828103155242843640892839966517009184493198782366909018",
h.String())
assert.Equal(t, "4635491972858758537477743930622086396911540895966845494943021655521913507504", h.String())
b5 := big.NewInt(5)
b6 := big.NewInt(6)
h, err = Hash([]*big.Int{b1, b2, b3, b4, b5, b6})
b7 := big.NewInt(7)
b8 := big.NewInt(8)
b9 := big.NewInt(9)
b10 := big.NewInt(10)
b11 := big.NewInt(11)
b12 := big.NewInt(12)
h, err = Hash([]*big.Int{b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12})
assert.Nil(t, err)
assert.Equal(t,
"20400040500897583745843009878988256314335038853985262692600694741116813247201",
h.String())
assert.Equal(t, "15278801138972282646981503374384603641625274360649669926363020545395022098027", h.String())
msg := []byte("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.")
n := 31
msgElems := make([]*big.Int, 0, len(msg)/n+1)
for i := 0; i < len(msg)/n; i++ {
v := new(big.Int)
utils.SetBigIntFromLEBytes(v, msg[n*i:n*(i+1)])
msgElems = append(msgElems, v)
}
if len(msg)%n != 0 {
v := new(big.Int)
utils.SetBigIntFromLEBytes(v, msg[(len(msg)/n)*n:])
msgElems = append(msgElems, v)
}
hmsg, err := Hash(msgElems)
assert.Nil(t, err)
assert.Equal(t, "16019700159595764790637132363672701294192939959594423814006267756172551741065", hmsg.String())
msg2 := []byte("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. Lorem ipsum dolor sit amet.")
msg2Elems := make([]*big.Int, 0, len(msg2)/n+1)
for i := 0; i < len(msg2)/n; i++ {
v := new(big.Int)
utils.SetBigIntFromLEBytes(v, msg2[n*i:n*(i+1)])
msg2Elems = append(msg2Elems, v)
}
if len(msg2)%n != 0 {
v := new(big.Int)
utils.SetBigIntFromLEBytes(v, msg2[(len(msg2)/n)*n:])
msg2Elems = append(msg2Elems, v)
}
hmsg2, err := Hash(msg2Elems)
assert.Nil(t, err)
assert.Equal(t, "2978613163687734485261639854325792381691890647104372645321246092227111432722", hmsg2.String())
hmsg2, err = HashBytes(msg2)
assert.Nil(t, err)
assert.Equal(t, "2978613163687734485261639854325792381691890647104372645321246092227111432722", hmsg2.String())
}
func TestErrorInputs(t *testing.T) {
b0 := big.NewInt(0)
b1 := big.NewInt(1)
b2 := big.NewInt(2)
_, err := Hash([]*big.Int{b1, b2, b0, b0, b0, b0})
func TestPoseidonBrokenChunks(t *testing.T) {
h1, err := Hash([]*big.Int{big.NewInt(0), big.NewInt(1), big.NewInt(2), big.NewInt(3), big.NewInt(4),
big.NewInt(5), big.NewInt(6), big.NewInt(7), big.NewInt(8), big.NewInt(9)})
assert.Nil(t, err)
_, err = Hash([]*big.Int{b1, b2, b0, b0, b0, b0, b0})
assert.NotNil(t, err)
assert.Equal(t, "invalid inputs length 7, max 7", err.Error())
_, err = Hash([]*big.Int{b1, b2, b0, b0, b0, b0, b0, b0})
assert.NotNil(t, err)
assert.Equal(t, "invalid inputs length 8, max 7", err.Error())
h2, err := Hash([]*big.Int{big.NewInt(5), big.NewInt(6), big.NewInt(7), big.NewInt(8), big.NewInt(9),
big.NewInt(0), big.NewInt(1), big.NewInt(2), big.NewInt(3), big.NewInt(4)})
assert.Nil(t, err)
assert.NotEqual(t, h1, h2)
}
func BenchmarkPoseidonHash(b *testing.B) {
b0 := big.NewInt(0)
b1 := utils.NewIntFromString("12242166908188651009877250812424843524687801523336557272219921456462821518061") //nolint:lll
b2 := utils.NewIntFromString("12242166908188651009877250812424843524687801523336557272219921456462821518061") //nolint:lll
func TestPoseidonBrokenPadding(t *testing.T) {
h1, err := Hash([]*big.Int{big.NewInt(int64(1))})
assert.Nil(t, err)
h2, err := Hash([]*big.Int{big.NewInt(int64(1)), big.NewInt(int64(0))})
assert.Nil(t, err)
assert.NotEqual(t, h1, h2)
}
bigArray4 := []*big.Int{b1, b2, b0, b0, b0, b0}
func BenchmarkPoseidon(b *testing.B) {
b12 := big.NewInt(int64(12))
b45 := big.NewInt(int64(45))
b78 := big.NewInt(int64(78))
b41 := big.NewInt(int64(41))
bigArray4 := []*big.Int{b12, b45, b78, b41}
for i := 0; i < b.N; i++ {
Hash(bigArray4) //nolint:errcheck,gosec
Hash(bigArray4)
}
}
func BenchmarkPoseidonLarge(b *testing.B) {
b12 := utils.NewIntFromString("11384336176656855268977457483345535180380036354188103142384839473266348197733")
b45 := utils.NewIntFromString("11384336176656855268977457483345535180380036354188103142384839473266348197733")
b78 := utils.NewIntFromString("11384336176656855268977457483345535180380036354188103142384839473266348197733")
b41 := utils.NewIntFromString("11384336176656855268977457483345535180380036354188103142384839473266348197733")
bigArray4 := []*big.Int{b12, b45, b78, b41}
for i := 0; i < b.N; i++ {
Hash(bigArray4)
}
}

View File

@@ -1,11 +0,0 @@
package utils
import (
"fmt"
"math/bits"
"testing"
)
func TestShowArchBits(t *testing.T) {
fmt.Printf("Architecture is %v bits\n", bits.UintSize)
}

View File

@@ -66,7 +66,9 @@ func HexEncode(bs []byte) string {
// HexDecode decodes a hex string into an array of bytes.
func HexDecode(h string) ([]byte, error) {
h = strings.TrimPrefix(h, "0x")
if strings.HasPrefix(h, "0x") {
h = h[2:]
}
return hex.DecodeString(h)
}
@@ -77,7 +79,7 @@ func HexDecodeInto(dst []byte, h []byte) error {
h = h[2:]
}
if len(h)/2 != len(dst) {
return fmt.Errorf("expected %v bytes in hex string, got %v", len(dst), len(h)/2) //nolint:gomnd
return fmt.Errorf("expected %v bytes in hex string, got %v", len(dst), len(h)/2)
}
n, err := hex.Decode(dst, h)
if err != nil {
@@ -90,7 +92,10 @@ func HexDecodeInto(dst []byte, h []byte) error {
// CheckBigIntInField checks if given *big.Int fits in a Field Q element
func CheckBigIntInField(a *big.Int) bool {
return a.Cmp(constants.Q) == -1
if a.Cmp(constants.Q) != -1 {
return false
}
return true
}
// CheckBigIntArrayInField checks if given *big.Int fits in a Field Q element
@@ -103,7 +108,6 @@ func CheckBigIntArrayInField(arr []*big.Int) bool {
return true
}
// BigIntArrayToElementArray converts an array of *big.Int into an array of *ff.Element
func BigIntArrayToElementArray(bi []*big.Int) []*ff.Element {
var o []*ff.Element
for i := range bi {
@@ -111,15 +115,3 @@ func BigIntArrayToElementArray(bi []*big.Int) []*ff.Element {
}
return o
}
// ElementArrayToBigIntArray converts an array of *ff.Element into an array of *big.Int
func ElementArrayToBigIntArray(e []*ff.Element) []*big.Int {
var o []*big.Int
for i := range e {
ei := e[i]
bi := big.NewInt(0)
ei.ToBigIntRegular(bi)
o = append(o, bi)
}
return o
}