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
```

babyjub/babyjub.go

@@ -5,15 +5,22 @@ import (
 	"math/big"
 
 	"github.com/iden3/go-iden3-crypto/constants"
+	"github.com/iden3/go-iden3-crypto/ff"
 	"github.com/iden3/go-iden3-crypto/utils"
 )
 
 // A is one of the babyjub constants.
 var A *big.Int
 
+// Aff is A value in *ff.Element representation
+var Aff *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
+
 // Order of the babyjub curve.
 var Order *big.Int
 
@@ -29,6 +36,8 @@ var B8 *Point
 func init() {
 	A = utils.NewIntFromString("168700")
 	D = utils.NewIntFromString("168696")
+	Aff = ff.NewElement().SetBigInt(A)
+	Dff = ff.NewElement().SetBigInt(D)
 
 	Order = utils.NewIntFromString(
 		"21888242871839275222246405745257275088614511777268538073601725287587578984328")
@@ -41,6 +50,70 @@ func init() {
 		"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 (res *PointProjective) Add(p *PointProjective, q *PointProjective) *PointProjective {
+	// add-2008-bbjlp https://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#doubling-dbl-2008-bbjlp
+	a := ff.NewElement().Mul(p.Z, q.Z)
+	b := ff.NewElement().Square(a)
+	c := ff.NewElement().Mul(p.X, q.X)
+	d := ff.NewElement().Mul(p.Y, q.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(p.X, p.Y)
+	x2y2 := ff.NewElement().Add(q.X, q.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)
+
+	res.X = x3
+	res.Y = y3
+	res.Z = z3
+	return res
+}
+
 // Point represents a point of the babyjub curve.
 type Point struct {
 	X *big.Int
@@ -59,62 +132,32 @@ func (p *Point) Set(c *Point) *Point {
 	return p
 }
 
-// Add adds Point a and b into res
+// Projective returns a PointProjective from the Point
-func (res *Point) Add(a *Point, b *Point) *Point {
+func (p *Point) Projective() *PointProjective {
-	// x = (a.x * b.y + b.x * a.y) * (1 + D * a.x * b.x * a.y * b.y)^-1 mod q
+	return &PointProjective{
-	x1a := new(big.Int).Mul(a.X, b.Y)
+		X: ff.NewElement().SetBigInt(p.X),
-	x1b := new(big.Int).Mul(b.X, a.Y)
+		Y: ff.NewElement().SetBigInt(p.Y),
-	x1a.Add(x1a, x1b) // x1a = a.x * b.y + b.x * a.y
+		Z: ff.NewElement().SetOne(),
-
+	}
-	x2 := new(big.Int).Set(D)
-	x2.Mul(x2, a.X)
-	x2.Mul(x2, b.X)
-	x2.Mul(x2, a.Y)
-	x2.Mul(x2, b.Y)
-	x2.Add(constants.One, x2)
-	x2.Mod(x2, constants.Q)
-	x2.ModInverse(x2, constants.Q) // 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 := new(big.Int).Mul(a.Y, b.Y)
-	y1b := new(big.Int).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 := new(big.Int).Set(D)
-	y2.Mul(y2, a.X)
-	y2.Mul(y2, b.X)
-	y2.Mul(y2, a.Y)
-	y2.Mul(y2, b.Y)
-	y2.Sub(constants.One, y2)
-	y2.Mod(y2, constants.Q)
-	y2.ModInverse(y2, constants.Q) // y2 = (1 - D * a.x * b.x * a.y * b.y)^-1
-
-	res.X = x1a.Mul(x1a, x2)
-	res.X = res.X.Mod(res.X, constants.Q)
-
-	res.Y = y1a.Mul(y1a, y2)
-	res.Y = res.Y.Mod(res.Y, constants.Q)
-
-	return res
 }
 
 // Mul multiplies the Point p by the scalar s and stores the result in res,
 // which is also returned.
 func (res *Point) Mul(s *big.Int, p *Point) *Point {
-	res.X = big.NewInt(0)
+	resProj := &PointProjective{
-	res.Y = big.NewInt(1)
+		X: ff.NewElement().SetZero(),
-	exp := NewPoint().Set(p)
+		Y: ff.NewElement().SetOne(),
+		Z: ff.NewElement().SetOne(),
+	}
+	exp := p.Projective()
 
 	for i := 0; i < s.BitLen(); i++ {
 		if s.Bit(i) == 1 {
-			res.Add(res, exp)
+			resProj.Add(resProj, exp)
 		}
-		exp.Add(exp, exp)
+		exp = exp.Add(exp, exp)
 	}
-
+	res = resProj.Affine()
 	return res
 }
 

babyjub/babyjub_test.go

@@ -15,7 +15,7 @@ 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)}
 
-	c := NewPoint().Add(a, b)
+	c := NewPoint().Projective().Add(a.Projective(), b.Projective())
 	// fmt.Printf("%v = 2 * %v", *c, *a)
 	assert.Equal(t, "0", c.X.String())
 	assert.Equal(t, "1", c.Y.String())
@@ -34,7 +34,7 @@ func TestAdd2(t *testing.T) {
 		"2626589144620713026669568689430873010625803728049924121243784502389097019475")
 	b := &Point{X: bX, Y: bY}
 
-	c := NewPoint().Add(a, b)
+	c := NewPoint().Projective().Add(a.Projective(), b.Projective()).Affine()
 	// fmt.Printf("%v = 2 * %v", *c, *a)
 	assert.Equal(t,
 		"6890855772600357754907169075114257697580319025794532037257385534741338397365",
@@ -42,6 +42,17 @@ 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) {
@@ -57,7 +68,7 @@ func TestAdd3(t *testing.T) {
 		"20819045374670962167435360035096875258406992893633759881276124905556507972311")
 	b := &Point{X: bX, Y: bY}
 
-	c := NewPoint().Add(a, b)
+	c := NewPoint().Projective().Add(a.Projective(), b.Projective()).Affine()
 	// fmt.Printf("%v = 2 * %v", *c, *a)
 	assert.Equal(t,
 		"7916061937171219682591368294088513039687205273691143098332585753343424131937",
@@ -80,7 +91,7 @@ func TestAdd4(t *testing.T) {
 		"20819045374670962167435360035096875258406992893633759881276124905556507972311")
 	b := &Point{X: bX, Y: bY}
 
-	c := NewPoint().Add(a, b)
+	c := NewPoint().Projective().Add(a.Projective(), b.Projective()).Affine()
 	// fmt.Printf("%v = 2 * %v", *c, *a)
 	assert.Equal(t,
 		"16540640123574156134436876038791482806971768689494387082833631921987005038935",
@@ -108,8 +119,8 @@ func TestMul0(t *testing.T) {
 	p := &Point{X: x, Y: y}
 	s := utils.NewIntFromString("3")
 
-	r2 := NewPoint().Add(p, p)
+	r2 := NewPoint().Projective().Add(p.Projective(), p.Projective()).Affine()
-	r2 = NewPoint().Add(r2, p)
+	r2 = NewPoint().Projective().Add(r2.Projective(), p.Projective()).Affine()
 	r := NewPoint().Mul(s, p)
 	assert.Equal(t, r2.X.String(), r.X.String())
 	assert.Equal(t, r2.Y.String(), r.Y.String())
@@ -244,7 +255,8 @@ func TestCompressDecompressRnd(t *testing.T) {
 		buf := p1.Compress()
 		p2, err := NewPoint().Decompress(buf)
 		assert.Equal(t, nil, err)
-		assert.Equal(t, p1, p2)
+		assert.Equal(t, p1.X.Bytes(), p2.X.Bytes())
+		assert.Equal(t, p1.Y.Bytes(), p2.Y.Bytes())
 	}
 }
 
@@ -261,6 +273,7 @@ func BenchmarkBabyjub(b *testing.B) {
 	}
 
 	var points [n]*Point
+	var pointsProj [n]*PointProjective
 	baseX := utils.NewIntFromString(
 		"17777552123799933955779906779655732241715742912184938656739573121738514868268")
 	baseY := utils.NewIntFromString(
@@ -269,6 +282,7 @@ func BenchmarkBabyjub(b *testing.B) {
 	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
@@ -279,17 +293,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()
 
-		p2 := NewPoint()
+		p2 := NewPoint().Projective()
 		for i := 0; i < b.N; i++ {
-			p2.Add(p0, p1)
+			p2.Add(p0Proj, p1Proj)
 		}
 	})
 
 	b.Run("AddRnd", func(b *testing.B) {
-		res := NewPoint()
+		res := NewPoint().Projective()
 		for i := 0; i < b.N; i++ {
-			res.Add(points[i%(n/2)], points[i%(n/2)+1])
+			res.Add(pointsProj[i%(n/2)], pointsProj[i%(n/2)+1])
 		}
 	})
 

babyjub/eddsa.go

@@ -236,7 +236,9 @@ func (p *PublicKey) VerifyMimc7(msg *big.Int, sig *Signature) bool {
 	r1 := big.NewInt(8)
 	r1.Mul(r1, hm)
 	right := NewPoint().Mul(r1, p.Point())
-	right.Add(sig.R8, right) // right = 8 * R + 8 * hm * A
+	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)
 }
 
@@ -253,7 +255,7 @@ func (k *PrivateKey) SignPoseidon(msg *big.Int) *Signature {
 	R8 := NewPoint().Mul(r, B8) // R8 = r * 8 * B
 	A := k.Public().Point()
 
-	hmInput := [poseidon.T]*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, big.NewInt(int64(0))}
 	hm, err := poseidon.Hash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
 	if err != nil {
 		panic(err)
@@ -270,7 +272,7 @@ 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 := [poseidon.T]*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, big.NewInt(int64(0))}
 	hm, err := poseidon.Hash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
 	if err != nil {
 		panic(err)
@@ -280,7 +282,9 @@ func (p *PublicKey) VerifyPoseidon(msg *big.Int, sig *Signature) bool {
 	r1 := big.NewInt(8)
 	r1.Mul(r1, hm)
 	right := NewPoint().Mul(r1, p.Point())
-	right.Add(sig.R8, right) // right = 8 * R + 8 * hm * A
+	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)
 }
 

babyjub/eddsa_test.go

@@ -96,7 +96,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
 		"15383486972088797283337779941324724402501462225528836549661220478783371668959",
 		sig.R8.Y.String())
 	assert.Equal(t,
-		"248298168863866362217836334079793350221620631973732197668910946177382043688",
+		"1662463587877312619203503803508234533733252768380479199263194005796068211378",
 		sig.S.String())
 
 	ok := pk.VerifyPoseidon(msg, sig)
@@ -108,7 +108,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
 
 	assert.Equal(t, ""+
 		"dfedb4315d3f2eb4de2d3c510d7a987dcab67089c8ace06308827bf5bcbe02a2"+
-		"28506bce274aa1b3f7e7c2fd7e4fe09bff8f9aa37a42def7994e98f322888c00",
+		"b23a1f04909fc088dec7e4835d85a326f7c0d0b2a3d0232d84448ca7c9ebac03",
 		hex.EncodeToString(sigBuf[:]))
 
 	ok = pk.VerifyPoseidon(msg, sig2)

poseidon/poseidon.go

@@ -2,177 +2,90 @@ 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 SEED = "poseidon"
 const NROUNDSF = 8
-const NROUNDSP = 57
-const T = 6
 
-var constC []*ff.Element
+var NROUNDSP = []int{56, 57, 56, 60, 60, 63, 64, 63}
-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 [T]*ff.Element, c *ff.Element) {
+func ark(state []*ff.Element, c []*ff.Element, it int) {
-	for i := 0; i < T; i++ {
+	for i := 0; i < len(state); i++ {
-		state[i].Add(state[i], c)
+		state[i].Add(state[i], c[it+i])
 	}
 }
 
-// cubic performs x^5 mod p
+// exp5 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(state [T]*ff.Element, i int) {
+func sbox(nRoundsF, nRoundsP int, state []*ff.Element, i int) {
-	if (i < NROUNDSF/2) || (i >= NROUNDSF/2+NROUNDSP) {
+	if (i < nRoundsF/2) || (i >= nRoundsF/2+nRoundsP) {
-		for j := 0; j < T; j++ {
+		for j := 0; j < len(state); j++ {
-			cubic(state[j])
+			exp5(state[j])
 		}
 	} else {
-		cubic(state[0])
+		exp5(state[0])
 	}
 }
 
 // mix returns [[matrix]] * [vector]
-func mix(state [T]*ff.Element, newState [T]*ff.Element, m [T][T]*ff.Element) {
+func mix(state []*ff.Element, newState []*ff.Element, m [][]*ff.Element) {
-	mul := Zero()
+	mul := zero()
-	for i := 0; i < T; i++ {
+	for i := 0; i < len(state); i++ {
 		newState[i].SetUint64(0)
-		for j := 0; j < T; j++ {
+		for j := 0; j < len(state); j++ {
-			mul.Mul(m[i][j], state[j])
+			mul.Mul(m[j][i], state[j])
 			newState[i].Add(newState[i], mul)
 		}
 	}
 }
 
 // Hash computes the Poseidon hash for the given inputs
-func Hash(inpBI [T]*big.Int) (*big.Int, error) {
+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)
+	}
 	if !utils.CheckBigIntArrayInField(inpBI[:]) {
 		return nil, errors.New("inputs values not inside Finite Field")
 	}
 	inp := utils.BigIntArrayToElementArray(inpBI[:])
-	state := [T]*ff.Element{}
+	state := make([]*ff.Element, t)
-	for i := 0; i < T; i++ {
+	copy(state[:], inp[:])
-		state[i] = ff.NewElement().Set(inp[i])
+	state[len(state)-1] = zero()
+
+	nRoundsF := NROUNDSF
+	nRoundsP := NROUNDSP[t-2]
+
+	newState := make([]*ff.Element, t)
+	for i := 0; i < t; i++ {
+		newState[i] = zero()
 	}
 
 	// ARK --> SBox --> M, https://eprint.iacr.org/2019/458.pdf pag.5
-	var newState [T]*ff.Element
+	for i := 0; i < nRoundsF+nRoundsP; i++ {
-	for i := 0; i < T; i++ {
+		ark(state, c.c[t-2], i*t)
-		newState[i] = Zero()
+		sbox(nRoundsF, nRoundsP, state, i)
-	}
+		if i < nRoundsF+nRoundsP-1 {
-	for i := 0; i < NROUNDSF+NROUNDSP; i++ {
+			mix(state, newState, c.m[t-2])
-		ark(state, constC[i])
-		sbox(state, i)
-		mix(state, newState, constM)
 			state, newState = newState, state
 		}
+	}
 	rE := state[0]
 	r := big.NewInt(0)
 	rE.ToBigIntRegular(r)
 	return r, nil
 }
-
-// HashSlice performs the Poseidon hash over a ff.Element array
-// in chunks of 5 elements
-func HashSlice(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 := Hash(toHash)
-		if err != nil {
-			return nil, err
-		}
-		modQ(r.Add(r, ph))
-	}
-
-	return r, nil
-}

poseidon/poseidon_test.go

@@ -19,104 +19,53 @@ func TestPoseidonHash(t *testing.T) {
 	b0 := big.NewInt(0)
 	b1 := big.NewInt(1)
 	b2 := big.NewInt(2)
-	h, err := Hash([T]*big.Int{b1, b2, b0, b0, b0, b0})
+
+	h, err := Hash([]*big.Int{b1})
 	assert.Nil(t, err)
-	assert.Equal(t, "12242166908188651009877250812424843524687801523336557272219921456462821518061", h.String())
+	assert.Equal(t, "11043376183861534927536506085090418075369306574649619885724436265926427398571", h.String())
+
+	h, err = Hash([]*big.Int{b1, b2})
+	assert.Nil(t, err)
+	assert.Equal(t, "17117985411748610629288516079940078114952304104811071254131751175361957805920", h.String())
+
+	h, err = Hash([]*big.Int{b1, b2, b0, b0, b0})
+	assert.Nil(t, err)
+	assert.Equal(t, "3975478831357328722254985704342968745327876719981393787143845259590563829094", h.String())
+	h, err = Hash([]*big.Int{b1, b2, b0, b0, b0, b0})
+	assert.Nil(t, err)
+	assert.Equal(t, "19772360636270345724087386688434825760738403416279047262510528378903625000110", h.String())
 
 	b3 := big.NewInt(3)
 	b4 := big.NewInt(4)
-	h, err = Hash([T]*big.Int{b3, b4, b0, b0, b0, b0})
+	h, err = Hash([]*big.Int{b3, b4, b0, b0, b0})
 	assert.Nil(t, err)
-	assert.Equal(t, "17185195740979599334254027721507328033796809509313949281114643312710535000993", h.String())
+	assert.Equal(t, "3181200837746671699652342497997860344148947482942465819251904554707352676086", h.String())
-}
+	h, err = Hash([]*big.Int{b3, b4, b0, b0, b0, b0})
-
-func TestPoseidonHashArbitraryLen(t *testing.T) {
-	b1 := big.NewInt(1)
-	b2 := big.NewInt(2)
-	h, err := HashSlice([]*big.Int{b1, b2})
 	assert.Nil(t, err)
-	assert.Equal(t, "4932297968297298434239270129193057052722409868268166443802652458940273154855", h.String())
+	assert.Equal(t, "8386348873272147968934270337233829407378789978142456170950021426339096575008", h.String())
-
-	b3 := big.NewInt(3)
-	b4 := big.NewInt(4)
-	h, err = HashSlice([]*big.Int{b3, b4})
-	assert.Nil(t, err)
-	assert.Equal(t, "4635491972858758537477743930622086396911540895966845494943021655521913507504", h.String())
 
 	b5 := big.NewInt(5)
 	b6 := big.NewInt(6)
-	b7 := big.NewInt(7)
+	h, err = Hash([]*big.Int{b1, b2, b3, b4, b5, b6})
-	b8 := big.NewInt(8)
-	b9 := big.NewInt(9)
-	b10 := big.NewInt(10)
-	b11 := big.NewInt(11)
-	b12 := big.NewInt(12)
-	h, err = HashSlice([]*big.Int{b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12})
 	assert.Nil(t, err)
-	assert.Equal(t, "15278801138972282646981503374384603641625274360649669926363020545395022098027", h.String())
+	assert.Equal(t, "5202465217520500374834597824465244016759843635092906214933648999760272616044", 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 := HashSlice(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 := HashSlice(msg2Elems)
-	assert.Nil(t, err)
-	assert.Equal(t, "2978613163687734485261639854325792381691890647104372645321246092227111432722", hmsg2.String())
 }
 
-func TestPoseidonHashArbitraryLenBrokenChunks(t *testing.T) {
+func TestErrorInputs(t *testing.T) {
-	h1, err := HashSlice([]*big.Int{big.NewInt(0), big.NewInt(1), big.NewInt(2), big.NewInt(3), big.NewInt(4),
+	b0 := big.NewInt(0)
-		big.NewInt(5), big.NewInt(6), big.NewInt(7), big.NewInt(8), big.NewInt(9)})
+	b1 := big.NewInt(1)
-	assert.Nil(t, err)
+	b2 := big.NewInt(2)
-	h2, err := HashSlice([]*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 TestPoseidonHashArbitraryLenBrokenPadding(t *testing.T) {
+	_, err := Hash([]*big.Int{b1, b2, b0, b0, b0, b0})
-	h1, err := HashSlice([]*big.Int{big.NewInt(int64(1))})
 	assert.Nil(t, err)
-	h2, err := HashSlice([]*big.Int{big.NewInt(int64(1)), big.NewInt(int64(0))})
-	assert.Nil(t, err)
-	assert.NotEqual(t, h1, h2)
-}
 
-func BenchmarkPoseidonHashSmallValues(b *testing.B) {
+	_, err = Hash([]*big.Int{b1, b2, b0, b0, b0, b0, b0})
-	b12 := big.NewInt(int64(12))
+	assert.NotNil(t, err)
-	b45 := big.NewInt(int64(45))
+	assert.Equal(t, "invalid inputs length 7, max 7", err.Error())
-	b78 := big.NewInt(int64(78))
-	b41 := big.NewInt(int64(41))
-	bigArray4 := []*big.Int{b12, b45, b78, b41}
 
-	for i := 0; i < b.N; i++ {
+	_, err = Hash([]*big.Int{b1, b2, b0, b0, b0, b0, b0, b0})
-		HashSlice(bigArray4) //nolint:errcheck
+	assert.NotNil(t, err)
-	}
+	assert.Equal(t, "invalid inputs length 8, max 7", err.Error())
 }
 
 func BenchmarkPoseidonHash(b *testing.B) {
@@ -124,7 +73,7 @@ func BenchmarkPoseidonHash(b *testing.B) {
 	b1 := utils.NewIntFromString("12242166908188651009877250812424843524687801523336557272219921456462821518061")
 	b2 := utils.NewIntFromString("12242166908188651009877250812424843524687801523336557272219921456462821518061")
 
-	bigArray4 := [T]*big.Int{b1, b2, b0, b0, b0, b0}
+	bigArray4 := []*big.Int{b1, b2, b0, b0, b0, b0}
 
 	for i := 0; i < b.N; i++ {
 		Hash(bigArray4) //nolint:errcheck