Merge pull request #36 from iden3/feature/poseidon-update-reference-impl

Update Poseidon last changes of the reference impl

babyjub/babyjub.go

@@ -203,31 +203,46 @@ func PointCoordSign(c *big.Int) bool {
 	return c.Cmp(new(big.Int).Rsh(constants.Q, 1)) == 1
 }
 
-// PackPoint packs a point into a 32 byte array
+// PackSignY packs the given sign and the coordinate Y of a point into a 32
-func PackPoint(ay *big.Int, sign bool) [32]byte {
+// byte array. This method does not check that the values belong to a valid
-	leBuf := utils.BigIntLEBytes(ay)
+// Point in the curve.
+func PackSignY(sign bool, y *big.Int) [32]byte {
+	leBuf := utils.BigIntLEBytes(y)
 	if sign {
 		leBuf[31] = leBuf[31] | 0x80 //nolint:gomnd
 	}
 	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 PackPoint(p.Y, sign)
+	return PackSignY(sign, p.Y)
 }
 
 // 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) {
-	sign := false
+	var sign bool
-	if (leBuf[31] & 0x80) != 0x00 { //nolint:gomnd
+	sign, p.Y = UnpackSignY(leBuf)
-		sign = true
-		leBuf[31] = leBuf[31] & 0x7F //nolint:gomnd
-	}
-	utils.SetBigIntFromLEBytes(p.Y, leBuf[:])
 	return PointFromSignAndY(sign, p.Y)
 }
 

babyjub/babyjub_test.go

@@ -218,6 +218,26 @@ func TestPointFromSignAndy(t *testing.T) {
 	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(
 		"17777552123799933955779906779655732241715742912184938656739573121738514868268")

babyjub/eddsa.go

@@ -354,3 +354,21 @@ 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
+}

babyjub/eddsa_test.go

@@ -97,7 +97,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
 		"15383486972088797283337779941324724402501462225528836549661220478783371668959",
 		sig.R8.Y.String())
 	assert.Equal(t,
-		"1398758333392199195742243841591064350253744445503462896781493968760929513778",
+		"1672775540645840396591609181675628451599263765380031905495115170613215233181",
 		sig.S.String())
 
 	ok := pk.VerifyPoseidon(msg, sig)
@@ -109,7 +109,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
 
 	assert.Equal(t, ""+
 		"dfedb4315d3f2eb4de2d3c510d7a987dcab67089c8ace06308827bf5bcbe02a2"+
-		"32f16b0f2f4c4e1169aa59685637e1429b6581a9531d058d65f4ab224eab1703",
+		"9d043ece562a8f82bfc0adb640c0107a7d3a27c1c7c1a6179a0da73de5c1b203",
 		hex.EncodeToString(sigBuf[:]))
 
 	ok = pk.VerifyPoseidon(msg, sig2)
@@ -139,7 +139,7 @@ func TestCompressDecompress(t *testing.T) {
 
 func TestSignatureCompScannerValuer(t *testing.T) {
 	privK := NewRandPrivKey()
-	var value driver.Valuer //nolint:gosimple this is done to ensure interface compability
+	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()
@@ -160,7 +160,7 @@ func TestSignatureScannerValuer(t *testing.T) {
 	assert.Equal(t, value, scan)
 }
 
-func TestPubKeyScannerValuer(t *testing.T) {
+func TestPublicKeyScannerValuer(t *testing.T) {
 	privKValue := NewRandPrivKey()
 	pubKValue := privKValue.Public()
 	privKScan := NewRandPrivKey()
@@ -175,6 +175,21 @@ func TestPubKeyScannerValuer(t *testing.T) {
 	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[:],

poseidon/poseidon.go

@@ -47,7 +47,7 @@ func mix(state []*ff.Element, newState []*ff.Element, m [][]*ff.Element) {
 	for i := 0; i < len(state); i++ {
 		newState[i].SetUint64(0)
 		for j := 0; j < len(state); j++ {
-			mul.Mul(m[j][i], state[j])
+			mul.Mul(m[i][j], state[j])
 			newState[i].Add(newState[i], mul)
 		}
 	}
@@ -64,8 +64,8 @@ func Hash(inpBI []*big.Int) (*big.Int, error) {
 	}
 	inp := utils.BigIntArrayToElementArray(inpBI[:])
 	state := make([]*ff.Element, t)
-	copy(state[:], inp[:])
+	state[0] = zero()
-	state[len(state)-1] = zero()
+	copy(state[1:], inp[:])
 
 	nRoundsF := NROUNDSF
 	nRoundsP := NROUNDSP[t-2]
@@ -79,11 +79,9 @@ func Hash(inpBI []*big.Int) (*big.Int, error) {
 	for i := 0; i < nRoundsF+nRoundsP; i++ {
 		ark(state, c.c[t-2], i*t)
 		sbox(nRoundsF, nRoundsP, state, i)
-		if i < nRoundsF+nRoundsP-1 {
 		mix(state, newState, c.m[t-2])
 		state, newState = newState, state
 	}
-	}
 	rE := state[0]
 	r := big.NewInt(0)
 	rE.ToBigIntRegular(r)

poseidon/poseidon_test.go

@@ -25,24 +25,24 @@ func TestPoseidonHash(t *testing.T) {
 	h, err := Hash([]*big.Int{b1})
 	assert.Nil(t, err)
 	assert.Equal(t,
-		"11043376183861534927536506085090418075369306574649619885724436265926427398571",
+		"18586133768512220936620570745912940619677854269274689475585506675881198879027",
 		h.String())
 
 	h, err = Hash([]*big.Int{b1, b2})
 	assert.Nil(t, err)
 	assert.Equal(t,
-		"17117985411748610629288516079940078114952304104811071254131751175361957805920",
+		"7853200120776062878684798364095072458815029376092732009249414926327459813530",
 		h.String())
 
 	h, err = Hash([]*big.Int{b1, b2, b0, b0, b0})
 	assert.Nil(t, err)
 	assert.Equal(t,
-		"3975478831357328722254985704342968745327876719981393787143845259590563829094",
+		"1018317224307729531995786483840663576608797660851238720571059489595066344487",
 		h.String())
 	h, err = Hash([]*big.Int{b1, b2, b0, b0, b0, b0})
 	assert.Nil(t, err)
 	assert.Equal(t,
-		"19772360636270345724087386688434825760738403416279047262510528378903625000110",
+		"15336558801450556532856248569924170992202208561737609669134139141992924267169",
 		h.String())
 
 	b3 := big.NewInt(3)
@@ -50,12 +50,12 @@ func TestPoseidonHash(t *testing.T) {
 	h, err = Hash([]*big.Int{b3, b4, b0, b0, b0})
 	assert.Nil(t, err)
 	assert.Equal(t,
-		"3181200837746671699652342497997860344148947482942465819251904554707352676086",
+		"5811595552068139067952687508729883632420015185677766880877743348592482390548",
 		h.String())
 	h, err = Hash([]*big.Int{b3, b4, b0, b0, b0, b0})
 	assert.Nil(t, err)
 	assert.Equal(t,
-		"8386348873272147968934270337233829407378789978142456170950021426339096575008",
+		"12263118664590987767234828103155242843640892839966517009184493198782366909018",
 		h.String())
 
 	b5 := big.NewInt(5)
@@ -63,7 +63,7 @@ func TestPoseidonHash(t *testing.T) {
 	h, err = Hash([]*big.Int{b1, b2, b3, b4, b5, b6})
 	assert.Nil(t, err)
 	assert.Equal(t,
-		"5202465217520500374834597824465244016759843635092906214933648999760272616044",
+		"20400040500897583745843009878988256314335038853985262692600694741116813247201",
 		h.String())
 }