Update to goff v0.2.0

.github/workflows/lint.yml

@@ -1,16 +0,0 @@
-on: [ push, pull_request ]
-name: Lint
-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.24.0
-        $(go env GOPATH)/bin/golangci-lint run

.github/workflows/test.yml

@@ -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 ./...

.travis.yml

@@ -0,0 +1,15 @@
+dist: xenial
+language: go
+
+go:
+  - "1.12"
+
+jobs:
+  include:
+    - name: "Unit Tests 64 bit arch"
+      env: GOARCH="amd64"
+    - name: "Unit Test 32 bit arch"
+      env: GOARCH="386"
+
+env:
+  - GO111MODULE=on

README.md

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

babyjub/babyjub.go

@@ -154,7 +154,10 @@ func (p *Point) InSubGroup() bool {
 // 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
 }
 
 func PackPoint(ay *big.Int, sign bool) [32]byte {

babyjub/eddsa.go

@@ -36,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])
@@ -50,7 +43,7 @@ func SkToBigInt(k *PrivateKey) *big.Int {
 	s := new(big.Int)
 	utils.SetBigIntFromLEBytes(s, sBuf32[:])
 	s.Rsh(s, 3)
-	return s
+	return NewPrivKeyScalar(s)
 }
 
 // Pub returns the public key corresponding to a private key.

babyjub/eddsa_test.go

@@ -1,6 +1,7 @@
 package babyjub
 
 import (
+	"crypto/rand"
 	"encoding/hex"
 	"fmt"
 	"math/big"
@@ -9,13 +10,25 @@ 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++ {
+	for i := 0; i < 256; i++ {
-		k[i] = byte(i)
+		hex.Decode(k[:], []byte{byte(i)})
 	}
 	pk := k.Public()
 	assert.True(t, pk.X.Cmp(constants.Q) == -1)
@@ -24,8 +37,7 @@ func TestPublicKey(t *testing.T) {
 
 func TestSignVerifyMimc7(t *testing.T) {
 	var k PrivateKey
-	_, err := hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
+	hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
-	require.Nil(t, err)
 	msgBuf, err := hex.DecodeString("00010203040506070809")
 	if err != nil {
 		panic(err)
@@ -69,8 +81,7 @@ func TestSignVerifyMimc7(t *testing.T) {
 
 func TestSignVerifyPoseidon(t *testing.T) {
 	var k PrivateKey
-	_, err := hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
+	hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
-	require.Nil(t, err)
 	msgBuf, err := hex.DecodeString("00010203040506070809")
 	if err != nil {
 		panic(err)
@@ -114,8 +125,7 @@ func TestSignVerifyPoseidon(t *testing.T) {
 
 func TestCompressDecompress(t *testing.T) {
 	var k PrivateKey
-	_, err := hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
+	hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
-	require.Nil(t, err)
 	pk := k.Public()
 	for i := 0; i < 64; i++ {
 		msgBuf, err := hex.DecodeString(fmt.Sprintf("000102030405060708%02d", i))
@@ -134,8 +144,7 @@ func TestCompressDecompress(t *testing.T) {
 
 func BenchmarkBabyjubEddsa(b *testing.B) {
 	var k PrivateKey
-	_, err := hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
+	hex.Decode(k[:], []byte("0001020304050607080900010203040506070809000102030405060708090001"))
-	require.Nil(b, err)
 	pk := k.Public()
 
 	const n = 256

babyjub/helpers.go

@@ -8,9 +8,6 @@ import (
 // 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[:])
+	h.Write(m[:])
-	if err != nil {
-		panic(err)
-	}
 	return h.Sum(nil)
 }

ff/arith.go

@@ -12,14 +12,19 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-// Code generated by goff DO NOT EDIT
+// Code generated by goff (v0.2.0) DO NOT EDIT
 
+// Package ff contains field arithmetic operations
 package ff
 
 import (
 	"math/bits"
+
+	"golang.org/x/sys/cpu"
 )
 
+var supportAdx = cpu.X86.HasADX && cpu.X86.HasBMI2
+
 func madd(a, b, t, u, v uint64) (uint64, uint64, uint64) {
 	var carry uint64
 	hi, lo := bits.Mul64(a, b)

ff/element.go

@@ -12,29 +12,33 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-// field modulus q =
+// Code generated by goff (v0.2.0) DO NOT EDIT
-//
-// 21888242871839275222246405745257275088548364400416034343698204186575808495617
-// Code generated by goff DO NOT EDIT
-// goff version:  - build:
-// Element are assumed to be in Montgomery form in all methods
 
-// Package ff (generated by goff) contains field arithmetics operations
+// Package ff contains field arithmetic operations
 package ff
 
+// /!\ WARNING /!\
+// this code has not been audited and is provided as-is. In particular,
+// there is no security guarantees such as constant time implementation
+// or side-channel attack resistance
+// /!\ WARNING /!\
+
 import (
 	"crypto/rand"
 	"encoding/binary"
 	"io"
 	"math/big"
 	"math/bits"
+	"strconv"
 	"sync"
-
 	"unsafe"
 )
 
 // Element represents a field element stored on 4 words (uint64)
 // Element are assumed to be in Montgomery form in all methods
+// field modulus q =
+//
+// 21888242871839275222246405745257275088548364400416034343698204186575808495617
 type Element [4]uint64
 
 // ElementLimbs number of 64 bits words needed to represent Element
@@ -311,6 +315,7 @@ func (z *Element) SetRandom() *Element {
 	z[3] %= 3486998266802970665
 
 	// if z > q --> z -= q
+	// note: this is NOT constant time
 	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
 		var b uint64
 		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
@@ -322,6 +327,38 @@ func (z *Element) SetRandom() *Element {
 	return z
 }
 
+// One returns 1 (in montgommery form)
+func One() Element {
+	var one Element
+	one.SetOne()
+	return one
+}
+
+// FromInterface converts i1 from uint64, int, string, or Element, big.Int into Element
+// panic if provided type is not supported
+func FromInterface(i1 interface{}) Element {
+	var val Element
+
+	switch c1 := i1.(type) {
+	case uint64:
+		val.SetUint64(c1)
+	case int:
+		val.SetString(strconv.Itoa(c1))
+	case string:
+		val.SetString(c1)
+	case big.Int:
+		val.SetBigInt(&c1)
+	case Element:
+		val = c1
+	case *Element:
+		val.Set(c1)
+	default:
+		panic("invalid type")
+	}
+
+	return val
+}
+
 // Add z = x + y mod q
 func (z *Element) Add(x, y *Element) *Element {
 	var carry uint64
@@ -332,6 +369,7 @@ func (z *Element) Add(x, y *Element) *Element {
 	z[3], _ = bits.Add64(x[3], y[3], carry)
 
 	// if z > q --> z -= q
+	// note: this is NOT constant time
 	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
 		var b uint64
 		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
@@ -352,6 +390,7 @@ func (z *Element) AddAssign(x *Element) *Element {
 	z[3], _ = bits.Add64(z[3], x[3], carry)
 
 	// if z > q --> z -= q
+	// note: this is NOT constant time
 	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
 		var b uint64
 		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
@@ -372,6 +411,7 @@ func (z *Element) Double(x *Element) *Element {
 	z[3], _ = bits.Add64(x[3], x[3], carry)
 
 	// if z > q --> z -= q
+	// note: this is NOT constant time
 	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
 		var b uint64
 		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
@@ -416,18 +456,31 @@ func (z *Element) SubAssign(x *Element) *Element {
 	return z
 }
 
-// Exp z = x^e mod q
+// Exp z = x^exponent mod q
-func (z *Element) Exp(x Element, e uint64) *Element {
+// (not optimized)
-	if e == 0 {
+// exponent (non-montgomery form) is ordered from least significant word to most significant word
+func (z *Element) Exp(x Element, exponent ...uint64) *Element {
+	r := 0
+	msb := 0
+	for i := len(exponent) - 1; i >= 0; i-- {
+		if exponent[i] == 0 {
+			r++
+		} else {
+			msb = (i * 64) + bits.Len64(exponent[i])
+			break
+		}
+	}
+	exponent = exponent[:len(exponent)-r]
+	if len(exponent) == 0 {
 		return z.SetOne()
 	}
 
 	z.Set(&x)
 
-	l := bits.Len64(e) - 2
+	l := msb - 2
 	for i := l; i >= 0; i-- {
 		z.Square(z)
-		if e&(1<<uint(i)) != 0 {
+		if exponent[i/64]&(1<<uint(i%64)) != 0 {
 			z.MulAssign(&x)
 		}
 	}
@@ -478,6 +531,7 @@ func (z *Element) FromMont() *Element {
 	}
 
 	// if z > q --> z -= q
+	// note: this is NOT constant time
 	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
 		var b uint64
 		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
@@ -549,6 +603,19 @@ func (z *Element) SetBigInt(v *big.Int) *Element {
 	zero := big.NewInt(0)
 	q := elementModulusBigInt()
 
+	// fast path
+	c := v.Cmp(q)
+	if c == 0 {
+		return z
+	} else if c != 1 && v.Cmp(zero) != -1 {
+		// v should
+		vBits := v.Bits()
+		for i := 0; i < len(vBits); i++ {
+			z[i] = uint64(vBits[i])
+		}
+		return z.ToMont()
+	}
+
 	// copy input
 	vv := new(big.Int).Set(v)
 
@@ -591,202 +658,97 @@ func (z *Element) SetString(s string) *Element {
 	return z.SetBigInt(x)
 }
 
-// Mul z = x * y mod q
+// Legendre returns the Legendre symbol of z (either +1, -1, or 0.)
-func (z *Element) Mul(x, y *Element) *Element {
+func (z *Element) Legendre() int {
+	var l Element
+	// z^((q-1)/2)
+	l.Exp(*z,
+		11669102379873075200,
+		10671829228508198984,
+		15863968012492123182,
+		1743499133401485332,
+	)
 
-	var t [4]uint64
+	if l.IsZero() {
-	var c [3]uint64
+		return 0
-	{
-		// round 0
-		v := x[0]
-		c[1], c[0] = bits.Mul64(v, y[0])
-		m := c[0] * 14042775128853446655
-		c[2] = madd0(m, 4891460686036598785, c[0])
-		c[1], c[0] = madd1(v, y[1], c[1])
-		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
-		c[1], c[0] = madd1(v, y[2], c[1])
-		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
-		c[1], c[0] = madd1(v, y[3], c[1])
-		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
-	}
-	{
-		// round 1
-		v := x[1]
-		c[1], c[0] = madd1(v, y[0], t[0])
-		m := c[0] * 14042775128853446655
-		c[2] = madd0(m, 4891460686036598785, c[0])
-		c[1], c[0] = madd2(v, y[1], c[1], t[1])
-		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
-		c[1], c[0] = madd2(v, y[2], c[1], t[2])
-		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
-		c[1], c[0] = madd2(v, y[3], c[1], t[3])
-		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
-	}
-	{
-		// round 2
-		v := x[2]
-		c[1], c[0] = madd1(v, y[0], t[0])
-		m := c[0] * 14042775128853446655
-		c[2] = madd0(m, 4891460686036598785, c[0])
-		c[1], c[0] = madd2(v, y[1], c[1], t[1])
-		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
-		c[1], c[0] = madd2(v, y[2], c[1], t[2])
-		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
-		c[1], c[0] = madd2(v, y[3], c[1], t[3])
-		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
-	}
-	{
-		// round 3
-		v := x[3]
-		c[1], c[0] = madd1(v, y[0], t[0])
-		m := c[0] * 14042775128853446655
-		c[2] = madd0(m, 4891460686036598785, c[0])
-		c[1], c[0] = madd2(v, y[1], c[1], t[1])
-		c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
-		c[1], c[0] = madd2(v, y[2], c[1], t[2])
-		c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
-		c[1], c[0] = madd2(v, y[3], c[1], t[3])
-		z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
 	}
 
-	// if z > q --> z -= q
+	// if l == 1
-	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
+	if (l[3] == 1011752739694698287) && (l[2] == 7381016538464732718) && (l[1] == 3962172157175319849) && (l[0] == 12436184717236109307) {
-		var b uint64
+		return 1
-		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
-		z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
-		z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
-		z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
 	}
-	return z
+	return -1
 }
 
-// MulAssign z = z * x mod q
+// Sqrt z = √x mod q
-func (z *Element) MulAssign(x *Element) *Element {
+// if the square root doesn't exist (x is not a square mod q)
+// Sqrt leaves z unchanged and returns nil
+func (z *Element) Sqrt(x *Element) *Element {
+	// q ≡ 1 (mod 4)
+	// see modSqrtTonelliShanks in math/big/int.go
+	// using https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020786.02p0470a.pdf
 
-	var t [4]uint64
+	var y, b, t, w Element
-	var c [3]uint64
+	// w = x^((s-1)/2))
-	{
+	w.Exp(*x,
-		// round 0
+		14829091926808964255,
-		v := z[0]
+		867720185306366531,
-		c[1], c[0] = bits.Mul64(v, x[0])
+		688207751544974772,
-		m := c[0] * 14042775128853446655
+		6495040407,
-		c[2] = madd0(m, 4891460686036598785, c[0])
+	)
-		c[1], c[0] = madd1(v, x[1], c[1])
+
-		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+	// y = x^((s+1)/2)) = w * x
-		c[1], c[0] = madd1(v, x[2], c[1])
+	y.Mul(x, &w)
-		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+
-		c[1], c[0] = madd1(v, x[3], c[1])
+	// b = x^s = w * w * x = y * x
-		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	b.Mul(&w, &y)
+
+	// g = nonResidue ^ s
+	var g = Element{
+		7164790868263648668,
+		11685701338293206998,
+		6216421865291908056,
+		1756667274303109607,
 	}
-	{
+	r := uint64(28)
-		// round 1
+
-		v := z[1]
+	// compute legendre symbol
-		c[1], c[0] = madd1(v, x[0], t[0])
+	// t = x^((q-1)/2) = r-1 squaring of x^s
-		m := c[0] * 14042775128853446655
+	t = b
-		c[2] = madd0(m, 4891460686036598785, c[0])
+	for i := uint64(0); i < r-1; i++ {
-		c[1], c[0] = madd2(v, x[1], c[1], t[1])
+		t.Square(&t)
-		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
-		c[1], c[0] = madd2(v, x[2], c[1], t[2])
-		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
-		c[1], c[0] = madd2(v, x[3], c[1], t[3])
-		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
 	}
-	{
+	if t.IsZero() {
-		// round 2
+		return z.SetZero()
-		v := z[2]
-		c[1], c[0] = madd1(v, x[0], t[0])
-		m := c[0] * 14042775128853446655
-		c[2] = madd0(m, 4891460686036598785, c[0])
-		c[1], c[0] = madd2(v, x[1], c[1], t[1])
-		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
-		c[1], c[0] = madd2(v, x[2], c[1], t[2])
-		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
-		c[1], c[0] = madd2(v, x[3], c[1], t[3])
-		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
 	}
-	{
+	if !((t[3] == 1011752739694698287) && (t[2] == 7381016538464732718) && (t[1] == 3962172157175319849) && (t[0] == 12436184717236109307)) {
-		// round 3
+		// t != 1, we don't have a square root
-		v := z[3]
+		return nil
-		c[1], c[0] = madd1(v, x[0], t[0])
+	}
-		m := c[0] * 14042775128853446655
+	for {
-		c[2] = madd0(m, 4891460686036598785, c[0])
+		var m uint64
-		c[1], c[0] = madd2(v, x[1], c[1], t[1])
+		t = b
-		c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
+
-		c[1], c[0] = madd2(v, x[2], c[1], t[2])
+		// for t != 1
-		c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		for !((t[3] == 1011752739694698287) && (t[2] == 7381016538464732718) && (t[1] == 3962172157175319849) && (t[0] == 12436184717236109307)) {
-		c[1], c[0] = madd2(v, x[3], c[1], t[3])
+			t.Square(&t)
-		z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+			m++
 		}
 
-	// if z > q --> z -= q
+		if m == 0 {
-	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
+			return z.Set(&y)
-		var b uint64
+		}
-		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
+		// t = g^(2^(r-m-1)) mod q
-		z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
+		ge := int(r - m - 1)
-		z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
+		t = g
-		z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
+		for ge > 0 {
+			t.Square(&t)
+			ge--
+		}
+
+		g.Square(&t)
+		y.MulAssign(&t)
+		b.MulAssign(&g)
+		r = m
 	}
-	return z
-}
-
-// Square z = x * x mod q
-func (z *Element) Square(x *Element) *Element {
-
-	var p [4]uint64
-
-	var u, v uint64
-	{
-		// round 0
-		u, p[0] = bits.Mul64(x[0], x[0])
-		m := p[0] * 14042775128853446655
-		C := madd0(m, 4891460686036598785, p[0])
-		var t uint64
-		t, u, v = madd1sb(x[0], x[1], u)
-		C, p[0] = madd2(m, 2896914383306846353, v, C)
-		t, u, v = madd1s(x[0], x[2], t, u)
-		C, p[1] = madd2(m, 13281191951274694749, v, C)
-		_, u, v = madd1s(x[0], x[3], t, u)
-		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
-	}
-	{
-		// round 1
-		m := p[0] * 14042775128853446655
-		C := madd0(m, 4891460686036598785, p[0])
-		u, v = madd1(x[1], x[1], p[1])
-		C, p[0] = madd2(m, 2896914383306846353, v, C)
-		var t uint64
-		t, u, v = madd2sb(x[1], x[2], p[2], u)
-		C, p[1] = madd2(m, 13281191951274694749, v, C)
-		_, u, v = madd2s(x[1], x[3], p[3], t, u)
-		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
-	}
-	{
-		// round 2
-		m := p[0] * 14042775128853446655
-		C := madd0(m, 4891460686036598785, p[0])
-		C, p[0] = madd2(m, 2896914383306846353, p[1], C)
-		u, v = madd1(x[2], x[2], p[2])
-		C, p[1] = madd2(m, 13281191951274694749, v, C)
-		_, u, v = madd2sb(x[2], x[3], p[3], u)
-		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
-	}
-	{
-		// round 3
-		m := p[0] * 14042775128853446655
-		C := madd0(m, 4891460686036598785, p[0])
-		C, z[0] = madd2(m, 2896914383306846353, p[1], C)
-		C, z[1] = madd2(m, 13281191951274694749, p[2], C)
-		u, v = madd1(x[3], x[3], p[3])
-		z[3], z[2] = madd3(m, 3486998266802970665, v, C, u)
-	}
-
-	// if z > q --> z -= q
-	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
-		var b uint64
-		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
-		z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
-		z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
-		z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
-	}
-	return z
 }

ff/element_mul.go

@@ -0,0 +1,170 @@
+// +build !amd64
+
+// Copyright 2020 ConsenSys AG
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Code generated by goff (v0.2.0) DO NOT EDIT
+
+// Package ff contains field arithmetic operations
+package ff
+
+// /!\ WARNING /!\
+// this code has not been audited and is provided as-is. In particular,
+// there is no security guarantees such as constant time implementation
+// or side-channel attack resistance
+// /!\ WARNING /!\
+
+import "math/bits"
+
+// Mul z = x * y mod q
+// see https://hackmd.io/@zkteam/modular_multiplication
+func (z *Element) Mul(x, y *Element) *Element {
+
+	var t [4]uint64
+	var c [3]uint64
+	{
+		// round 0
+		v := x[0]
+		c[1], c[0] = bits.Mul64(v, y[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd1(v, y[1], c[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd1(v, y[2], c[1])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd1(v, y[3], c[1])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 1
+		v := x[1]
+		c[1], c[0] = madd1(v, y[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, y[1], c[1], t[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, y[2], c[1], t[2])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, y[3], c[1], t[3])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 2
+		v := x[2]
+		c[1], c[0] = madd1(v, y[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, y[1], c[1], t[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, y[2], c[1], t[2])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, y[3], c[1], t[3])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 3
+		v := x[3]
+		c[1], c[0] = madd1(v, y[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, y[1], c[1], t[1])
+		c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, y[2], c[1], t[2])
+		c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, y[3], c[1], t[3])
+		z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+
+	// if z > q --> z -= q
+	// note: this is NOT constant time
+	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
+		var b uint64
+		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
+		z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
+		z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
+		z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
+	}
+	return z
+}
+
+// MulAssign z = z * x mod q
+// see https://hackmd.io/@zkteam/modular_multiplication
+func (z *Element) MulAssign(x *Element) *Element {
+
+	var t [4]uint64
+	var c [3]uint64
+	{
+		// round 0
+		v := z[0]
+		c[1], c[0] = bits.Mul64(v, x[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd1(v, x[1], c[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd1(v, x[2], c[1])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd1(v, x[3], c[1])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 1
+		v := z[1]
+		c[1], c[0] = madd1(v, x[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, x[1], c[1], t[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, x[2], c[1], t[2])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, x[3], c[1], t[3])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 2
+		v := z[2]
+		c[1], c[0] = madd1(v, x[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, x[1], c[1], t[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, x[2], c[1], t[2])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, x[3], c[1], t[3])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 3
+		v := z[3]
+		c[1], c[0] = madd1(v, x[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, x[1], c[1], t[1])
+		c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, x[2], c[1], t[2])
+		c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, x[3], c[1], t[3])
+		z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+
+	// if z > q --> z -= q
+	// note: this is NOT constant time
+	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
+		var b uint64
+		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
+		z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
+		z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
+		z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
+	}
+	return z
+}

ff/element_mul_amd64.go

@@ -0,0 +1,39 @@
+// Copyright 2020 ConsenSys AG
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Code generated by goff (v0.2.0) DO NOT EDIT
+
+// Package ff contains field arithmetic operations
+package ff
+
+// MulAssignElement z = z * x mod q (constant time)
+// calling this instead of z.MulAssign(x) is prefered for performance critical path
+//go:noescape
+func MulAssignElement(res, y *Element)
+
+// Mul z = x * y mod q (constant time)
+// see https://hackmd.io/@zkteam/modular_multiplication
+func (z *Element) Mul(x, y *Element) *Element {
+	res := *x
+	MulAssignElement(&res, y)
+	z.Set(&res)
+	return z
+}
+
+// MulAssign z = z * x mod q (constant time)
+// see https://hackmd.io/@zkteam/modular_multiplication
+func (z *Element) MulAssign(x *Element) *Element {
+	MulAssignElement(z, x)
+	return z
+}

ff/element_mul_amd64.s

@@ -0,0 +1,695 @@
+// Code generated by goff (v0.2.0) DO NOT EDIT
+
+#include "textflag.h"
+
+// func MulAssignElement(res,y *Element)
+// montgomery multiplication of res by y
+// stores the result in res
+TEXT ·MulAssignElement(SB), NOSPLIT, $0-16
+    
+    // dereference our parameters
+    MOVQ res+0(FP), DI
+    MOVQ y+8(FP), R8
+    
+    // check if we support adx and mulx
+    CMPB ·supportAdx(SB), $1
+    JNE no_adx
+    
+    // the algorithm is described here
+    // https://hackmd.io/@zkteam/modular_multiplication
+    // however, to benefit from the ADCX and ADOX carry chains
+    // we split the inner loops in 2:
+    // for i=0 to N-1
+    // 		for j=0 to N-1
+    // 		    (A,t[j])  := t[j] + a[j]*b[i] + A
+    // 		m := t[0]*q'[0] mod W
+    // 		C,_ := t[0] + m*q[0]
+    // 		for j=1 to N-1
+    // 		    (C,t[j-1]) := t[j] + m*q[j] + C
+    // 		t[N-1] = C + A
+    
+    // ---------------------------------------------------------------------------------------------
+    // outter loop 0
+    
+    // clear up the carry flags
+    XORQ R9 , R9
+    
+    // R12 = y[0]
+    MOVQ 0(R8), R12
+    
+    // for j=0 to N-1
+    //    (A,t[j])  := t[j] + x[j]*y[i] + A
+    
+    // DX = res[0]
+    MOVQ 0(DI), DX
+    MULXQ R12, CX ,  R9
+    
+    // DX = res[1]
+    MOVQ 8(DI), DX
+    MOVQ R9, BX
+    MULXQ R12, AX,  R9
+    ADOXQ AX, BX
+    
+    // DX = res[2]
+    MOVQ 16(DI), DX
+    MOVQ R9, BP
+    MULXQ R12, AX,  R9
+    ADOXQ AX, BP
+    
+    // DX = res[3]
+    MOVQ 24(DI), DX
+    MOVQ R9, SI
+    MULXQ R12, AX,  R9
+    ADOXQ AX, SI
+    
+    // add the last carries to R9
+    MOVQ $0, DX
+    ADCXQ DX, R9
+    ADOXQ DX, R9
+    
+    // m := t[0]*q'[0] mod W
+    MOVQ $0xc2e1f593efffffff, DX
+    MULXQ CX,R11, DX
+    
+    // clear the carry flags
+    XORQ DX, DX
+    
+    // C,_ := t[0] + m*q[0]
+    MOVQ $0x43e1f593f0000001, DX
+    MULXQ R11, AX, R10
+    ADCXQ CX ,AX
+    
+    // for j=1 to N-1
+    //    (C,t[j-1]) := t[j] + m*q[j] + C
+    
+    MOVQ $0x2833e84879b97091, DX
+    MULXQ R11, AX, DX
+    ADCXQ  BX, R10
+    ADOXQ AX, R10
+    MOVQ R10, CX
+    MOVQ DX, R10
+    
+    MOVQ $0xb85045b68181585d, DX
+    MULXQ R11, AX, DX
+    ADCXQ  BP, R10
+    ADOXQ AX, R10
+    MOVQ R10, BX
+    MOVQ DX, R10
+    
+    MOVQ $0x30644e72e131a029, DX
+    MULXQ R11, AX, DX
+    ADCXQ  SI, R10
+    ADOXQ AX, R10
+    MOVQ R10, BP
+    MOVQ $0, AX
+    ADCXQ AX, DX
+    ADOXQ DX, R9
+    MOVQ R9, SI
+    
+    // ---------------------------------------------------------------------------------------------
+    // outter loop 1
+    
+    // clear up the carry flags
+    XORQ R9 , R9
+    
+    // R12 = y[1]
+    MOVQ 8(R8), R12
+    
+    // for j=0 to N-1
+    //    (A,t[j])  := t[j] + x[j]*y[i] + A
+    
+    // DX = res[0]
+    MOVQ 0(DI), DX
+    MULXQ R12, AX,  R9
+    ADOXQ AX, CX
+    
+    // DX = res[1]
+    MOVQ 8(DI), DX
+    ADCXQ R9, BX
+    MULXQ R12, AX,  R9
+    ADOXQ AX, BX
+    
+    // DX = res[2]
+    MOVQ 16(DI), DX
+    ADCXQ R9, BP
+    MULXQ R12, AX,  R9
+    ADOXQ AX, BP
+    
+    // DX = res[3]
+    MOVQ 24(DI), DX
+    ADCXQ R9, SI
+    MULXQ R12, AX,  R9
+    ADOXQ AX, SI
+    
+    // add the last carries to R9
+    MOVQ $0, DX
+    ADCXQ DX, R9
+    ADOXQ DX, R9
+    
+    // m := t[0]*q'[0] mod W
+    MOVQ $0xc2e1f593efffffff, DX
+    MULXQ CX,R11, DX
+    
+    // clear the carry flags
+    XORQ DX, DX
+    
+    // C,_ := t[0] + m*q[0]
+    MOVQ $0x43e1f593f0000001, DX
+    MULXQ R11, AX, R10
+    ADCXQ CX ,AX
+    
+    // for j=1 to N-1
+    //    (C,t[j-1]) := t[j] + m*q[j] + C
+    
+    MOVQ $0x2833e84879b97091, DX
+    MULXQ R11, AX, DX
+    ADCXQ  BX, R10
+    ADOXQ AX, R10
+    MOVQ R10, CX
+    MOVQ DX, R10
+    
+    MOVQ $0xb85045b68181585d, DX
+    MULXQ R11, AX, DX
+    ADCXQ  BP, R10
+    ADOXQ AX, R10
+    MOVQ R10, BX
+    MOVQ DX, R10
+    
+    MOVQ $0x30644e72e131a029, DX
+    MULXQ R11, AX, DX
+    ADCXQ  SI, R10
+    ADOXQ AX, R10
+    MOVQ R10, BP
+    MOVQ $0, AX
+    ADCXQ AX, DX
+    ADOXQ DX, R9
+    MOVQ R9, SI
+    
+    // ---------------------------------------------------------------------------------------------
+    // outter loop 2
+    
+    // clear up the carry flags
+    XORQ R9 , R9
+    
+    // R12 = y[2]
+    MOVQ 16(R8), R12
+    
+    // for j=0 to N-1
+    //    (A,t[j])  := t[j] + x[j]*y[i] + A
+    
+    // DX = res[0]
+    MOVQ 0(DI), DX
+    MULXQ R12, AX,  R9
+    ADOXQ AX, CX
+    
+    // DX = res[1]
+    MOVQ 8(DI), DX
+    ADCXQ R9, BX
+    MULXQ R12, AX,  R9
+    ADOXQ AX, BX
+    
+    // DX = res[2]
+    MOVQ 16(DI), DX
+    ADCXQ R9, BP
+    MULXQ R12, AX,  R9
+    ADOXQ AX, BP
+    
+    // DX = res[3]
+    MOVQ 24(DI), DX
+    ADCXQ R9, SI
+    MULXQ R12, AX,  R9
+    ADOXQ AX, SI
+    
+    // add the last carries to R9
+    MOVQ $0, DX
+    ADCXQ DX, R9
+    ADOXQ DX, R9
+    
+    // m := t[0]*q'[0] mod W
+    MOVQ $0xc2e1f593efffffff, DX
+    MULXQ CX,R11, DX
+    
+    // clear the carry flags
+    XORQ DX, DX
+    
+    // C,_ := t[0] + m*q[0]
+    MOVQ $0x43e1f593f0000001, DX
+    MULXQ R11, AX, R10
+    ADCXQ CX ,AX
+    
+    // for j=1 to N-1
+    //    (C,t[j-1]) := t[j] + m*q[j] + C
+    
+    MOVQ $0x2833e84879b97091, DX
+    MULXQ R11, AX, DX
+    ADCXQ  BX, R10
+    ADOXQ AX, R10
+    MOVQ R10, CX
+    MOVQ DX, R10
+    
+    MOVQ $0xb85045b68181585d, DX
+    MULXQ R11, AX, DX
+    ADCXQ  BP, R10
+    ADOXQ AX, R10
+    MOVQ R10, BX
+    MOVQ DX, R10
+    
+    MOVQ $0x30644e72e131a029, DX
+    MULXQ R11, AX, DX
+    ADCXQ  SI, R10
+    ADOXQ AX, R10
+    MOVQ R10, BP
+    MOVQ $0, AX
+    ADCXQ AX, DX
+    ADOXQ DX, R9
+    MOVQ R9, SI
+    
+    // ---------------------------------------------------------------------------------------------
+    // outter loop 3
+    
+    // clear up the carry flags
+    XORQ R9 , R9
+    
+    // R12 = y[3]
+    MOVQ 24(R8), R12
+    
+    // for j=0 to N-1
+    //    (A,t[j])  := t[j] + x[j]*y[i] + A
+    
+    // DX = res[0]
+    MOVQ 0(DI), DX
+    MULXQ R12, AX,  R9
+    ADOXQ AX, CX
+    
+    // DX = res[1]
+    MOVQ 8(DI), DX
+    ADCXQ R9, BX
+    MULXQ R12, AX,  R9
+    ADOXQ AX, BX
+    
+    // DX = res[2]
+    MOVQ 16(DI), DX
+    ADCXQ R9, BP
+    MULXQ R12, AX,  R9
+    ADOXQ AX, BP
+    
+    // DX = res[3]
+    MOVQ 24(DI), DX
+    ADCXQ R9, SI
+    MULXQ R12, AX,  R9
+    ADOXQ AX, SI
+    
+    // add the last carries to R9
+    MOVQ $0, DX
+    ADCXQ DX, R9
+    ADOXQ DX, R9
+    
+    // m := t[0]*q'[0] mod W
+    MOVQ $0xc2e1f593efffffff, DX
+    MULXQ CX,R11, DX
+    
+    // clear the carry flags
+    XORQ DX, DX
+    
+    // C,_ := t[0] + m*q[0]
+    MOVQ $0x43e1f593f0000001, DX
+    MULXQ R11, AX, R10
+    ADCXQ CX ,AX
+    
+    // for j=1 to N-1
+    //    (C,t[j-1]) := t[j] + m*q[j] + C
+    
+    MOVQ $0x2833e84879b97091, DX
+    MULXQ R11, AX, DX
+    ADCXQ  BX, R10
+    ADOXQ AX, R10
+    MOVQ R10, CX
+    MOVQ DX, R10
+    
+    MOVQ $0xb85045b68181585d, DX
+    MULXQ R11, AX, DX
+    ADCXQ  BP, R10
+    ADOXQ AX, R10
+    MOVQ R10, BX
+    MOVQ DX, R10
+    
+    MOVQ $0x30644e72e131a029, DX
+    MULXQ R11, AX, DX
+    ADCXQ  SI, R10
+    ADOXQ AX, R10
+    MOVQ R10, BP
+    MOVQ $0, AX
+    ADCXQ AX, DX
+    ADOXQ DX, R9
+    MOVQ R9, SI
+    
+    reduce:
+    // reduce, constant time version
+    // first we copy registers storing t in a separate set of registers
+    // as SUBQ modifies the 2nd operand
+    MOVQ CX, DX
+    MOVQ BX, R8
+    MOVQ BP, R9
+    MOVQ SI, R10
+    MOVQ $0x43e1f593f0000001, R11
+    SUBQ  R11, DX
+    MOVQ $0x2833e84879b97091, R11
+    SBBQ  R11, R8
+    MOVQ $0xb85045b68181585d, R11
+    SBBQ  R11, R9
+    MOVQ $0x30644e72e131a029, R11
+    SBBQ  R11, R10
+    JCS t_is_smaller // no borrow, we return t
+    
+    // borrow is set, we return u
+    MOVQ DX, (DI)
+    MOVQ R8, 8(DI)
+    MOVQ R9, 16(DI)
+    MOVQ R10, 24(DI)
+    RET
+    t_is_smaller:
+    MOVQ CX, 0(DI)
+    MOVQ BX, 8(DI)
+    MOVQ BP, 16(DI)
+    MOVQ SI, 24(DI)
+    RET
+    
+    no_adx:
+    
+    // ---------------------------------------------------------------------------------------------
+    // outter loop 0
+    
+    // (A,t[0]) := t[0] + x[0]*y[0]
+    MOVQ (DI), AX // x[0]
+    MOVQ 0(R8), R12
+    MULQ R12 // x[0] * y[0]
+    MOVQ DX, R9
+    MOVQ AX, CX
+    
+    // m := t[0]*q'[0] mod W
+    MOVQ $0xc2e1f593efffffff, R11
+    IMULQ CX , R11
+    
+    // C,_ := t[0] + m*q[0]
+    MOVQ $0x43e1f593f0000001, AX
+    MULQ R11
+    ADDQ CX ,AX
+    ADCQ $0, DX
+    MOVQ  DX, R10
+    
+    // for j=1 to N-1
+    //    (A,t[j])  := t[j] + x[j]*y[i] + A
+    //    (C,t[j-1]) := t[j] + m*q[j] + C
+    MOVQ 8(DI), AX
+    MULQ R12 // x[1] * y[0]
+    MOVQ R9, BX
+    ADDQ AX, BX
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0x2833e84879b97091, AX
+    MULQ R11
+    ADDQ  BX, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, CX
+    MOVQ DX, R10
+    MOVQ 16(DI), AX
+    MULQ R12 // x[2] * y[0]
+    MOVQ R9, BP
+    ADDQ AX, BP
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0xb85045b68181585d, AX
+    MULQ R11
+    ADDQ  BP, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, BX
+    MOVQ DX, R10
+    MOVQ 24(DI), AX
+    MULQ R12 // x[3] * y[0]
+    MOVQ R9, SI
+    ADDQ AX, SI
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0x30644e72e131a029, AX
+    MULQ R11
+    ADDQ  SI, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, BP
+    MOVQ DX, R10
+    
+    ADDQ R10, R9
+    MOVQ R9, SI
+    
+    // ---------------------------------------------------------------------------------------------
+    // outter loop 1
+    
+    // (A,t[0]) := t[0] + x[0]*y[1]
+    MOVQ (DI), AX // x[0]
+    MOVQ 8(R8), R12
+    MULQ R12 // x[0] * y[1]
+    ADDQ AX, CX
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    // m := t[0]*q'[0] mod W
+    MOVQ $0xc2e1f593efffffff, R11
+    IMULQ CX , R11
+    
+    // C,_ := t[0] + m*q[0]
+    MOVQ $0x43e1f593f0000001, AX
+    MULQ R11
+    ADDQ CX ,AX
+    ADCQ $0, DX
+    MOVQ  DX, R10
+    
+    // for j=1 to N-1
+    //    (A,t[j])  := t[j] + x[j]*y[i] + A
+    //    (C,t[j-1]) := t[j] + m*q[j] + C
+    MOVQ 8(DI), AX
+    MULQ R12 // x[1] * y[1]
+    ADDQ R9, BX
+    ADCQ $0, DX
+    ADDQ AX, BX
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0x2833e84879b97091, AX
+    MULQ R11
+    ADDQ  BX, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, CX
+    MOVQ DX, R10
+    MOVQ 16(DI), AX
+    MULQ R12 // x[2] * y[1]
+    ADDQ R9, BP
+    ADCQ $0, DX
+    ADDQ AX, BP
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0xb85045b68181585d, AX
+    MULQ R11
+    ADDQ  BP, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, BX
+    MOVQ DX, R10
+    MOVQ 24(DI), AX
+    MULQ R12 // x[3] * y[1]
+    ADDQ R9, SI
+    ADCQ $0, DX
+    ADDQ AX, SI
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0x30644e72e131a029, AX
+    MULQ R11
+    ADDQ  SI, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, BP
+    MOVQ DX, R10
+    
+    ADDQ R10, R9
+    MOVQ R9, SI
+    
+    // ---------------------------------------------------------------------------------------------
+    // outter loop 2
+    
+    // (A,t[0]) := t[0] + x[0]*y[2]
+    MOVQ (DI), AX // x[0]
+    MOVQ 16(R8), R12
+    MULQ R12 // x[0] * y[2]
+    ADDQ AX, CX
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    // m := t[0]*q'[0] mod W
+    MOVQ $0xc2e1f593efffffff, R11
+    IMULQ CX , R11
+    
+    // C,_ := t[0] + m*q[0]
+    MOVQ $0x43e1f593f0000001, AX
+    MULQ R11
+    ADDQ CX ,AX
+    ADCQ $0, DX
+    MOVQ  DX, R10
+    
+    // for j=1 to N-1
+    //    (A,t[j])  := t[j] + x[j]*y[i] + A
+    //    (C,t[j-1]) := t[j] + m*q[j] + C
+    MOVQ 8(DI), AX
+    MULQ R12 // x[1] * y[2]
+    ADDQ R9, BX
+    ADCQ $0, DX
+    ADDQ AX, BX
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0x2833e84879b97091, AX
+    MULQ R11
+    ADDQ  BX, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, CX
+    MOVQ DX, R10
+    MOVQ 16(DI), AX
+    MULQ R12 // x[2] * y[2]
+    ADDQ R9, BP
+    ADCQ $0, DX
+    ADDQ AX, BP
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0xb85045b68181585d, AX
+    MULQ R11
+    ADDQ  BP, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, BX
+    MOVQ DX, R10
+    MOVQ 24(DI), AX
+    MULQ R12 // x[3] * y[2]
+    ADDQ R9, SI
+    ADCQ $0, DX
+    ADDQ AX, SI
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0x30644e72e131a029, AX
+    MULQ R11
+    ADDQ  SI, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, BP
+    MOVQ DX, R10
+    
+    ADDQ R10, R9
+    MOVQ R9, SI
+    
+    // ---------------------------------------------------------------------------------------------
+    // outter loop 3
+    
+    // (A,t[0]) := t[0] + x[0]*y[3]
+    MOVQ (DI), AX // x[0]
+    MOVQ 24(R8), R12
+    MULQ R12 // x[0] * y[3]
+    ADDQ AX, CX
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    // m := t[0]*q'[0] mod W
+    MOVQ $0xc2e1f593efffffff, R11
+    IMULQ CX , R11
+    
+    // C,_ := t[0] + m*q[0]
+    MOVQ $0x43e1f593f0000001, AX
+    MULQ R11
+    ADDQ CX ,AX
+    ADCQ $0, DX
+    MOVQ  DX, R10
+    
+    // for j=1 to N-1
+    //    (A,t[j])  := t[j] + x[j]*y[i] + A
+    //    (C,t[j-1]) := t[j] + m*q[j] + C
+    MOVQ 8(DI), AX
+    MULQ R12 // x[1] * y[3]
+    ADDQ R9, BX
+    ADCQ $0, DX
+    ADDQ AX, BX
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0x2833e84879b97091, AX
+    MULQ R11
+    ADDQ  BX, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, CX
+    MOVQ DX, R10
+    MOVQ 16(DI), AX
+    MULQ R12 // x[2] * y[3]
+    ADDQ R9, BP
+    ADCQ $0, DX
+    ADDQ AX, BP
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0xb85045b68181585d, AX
+    MULQ R11
+    ADDQ  BP, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, BX
+    MOVQ DX, R10
+    MOVQ 24(DI), AX
+    MULQ R12 // x[3] * y[3]
+    ADDQ R9, SI
+    ADCQ $0, DX
+    ADDQ AX, SI
+    ADCQ $0, DX
+    MOVQ DX, R9
+    
+    MOVQ $0x30644e72e131a029, AX
+    MULQ R11
+    ADDQ  SI, R10
+    ADCQ $0, DX
+    ADDQ AX, R10
+    ADCQ $0, DX
+    
+    MOVQ R10, BP
+    MOVQ DX, R10
+    
+    ADDQ R10, R9
+    MOVQ R9, SI
+    
+    JMP reduce

ff/element_square.go

@@ -0,0 +1,93 @@
+// +build !amd64
+
+// Copyright 2020 ConsenSys AG
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Code generated by goff (v0.2.0) DO NOT EDIT
+
+// Package ff contains field arithmetic operations
+package ff
+
+// /!\ WARNING /!\
+// this code has not been audited and is provided as-is. In particular,
+// there is no security guarantees such as constant time implementation
+// or side-channel attack resistance
+// /!\ WARNING /!\
+
+import "math/bits"
+
+// Square z = x * x mod q
+// see https://hackmd.io/@zkteam/modular_multiplication
+func (z *Element) Square(x *Element) *Element {
+
+	var p [4]uint64
+
+	var u, v uint64
+	{
+		// round 0
+		u, p[0] = bits.Mul64(x[0], x[0])
+		m := p[0] * 14042775128853446655
+		C := madd0(m, 4891460686036598785, p[0])
+		var t uint64
+		t, u, v = madd1sb(x[0], x[1], u)
+		C, p[0] = madd2(m, 2896914383306846353, v, C)
+		t, u, v = madd1s(x[0], x[2], t, u)
+		C, p[1] = madd2(m, 13281191951274694749, v, C)
+		_, u, v = madd1s(x[0], x[3], t, u)
+		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
+	}
+	{
+		// round 1
+		m := p[0] * 14042775128853446655
+		C := madd0(m, 4891460686036598785, p[0])
+		u, v = madd1(x[1], x[1], p[1])
+		C, p[0] = madd2(m, 2896914383306846353, v, C)
+		var t uint64
+		t, u, v = madd2sb(x[1], x[2], p[2], u)
+		C, p[1] = madd2(m, 13281191951274694749, v, C)
+		_, u, v = madd2s(x[1], x[3], p[3], t, u)
+		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
+	}
+	{
+		// round 2
+		m := p[0] * 14042775128853446655
+		C := madd0(m, 4891460686036598785, p[0])
+		C, p[0] = madd2(m, 2896914383306846353, p[1], C)
+		u, v = madd1(x[2], x[2], p[2])
+		C, p[1] = madd2(m, 13281191951274694749, v, C)
+		_, u, v = madd2sb(x[2], x[3], p[3], u)
+		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
+	}
+	{
+		// round 3
+		m := p[0] * 14042775128853446655
+		C := madd0(m, 4891460686036598785, p[0])
+		C, z[0] = madd2(m, 2896914383306846353, p[1], C)
+		C, z[1] = madd2(m, 13281191951274694749, p[2], C)
+		u, v = madd1(x[3], x[3], p[3])
+		z[3], z[2] = madd3(m, 3486998266802970665, v, C, u)
+	}
+
+	// if z > q --> z -= q
+	// note: this is NOT constant time
+	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
+		var b uint64
+		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
+		z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
+		z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
+		z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
+	}
+	return z
+
+}

ff/element_square_amd64.go

@@ -0,0 +1,34 @@
+// Copyright 2020 ConsenSys AG
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Code generated by goff (v0.2.0) DO NOT EDIT
+
+// Package ff contains field arithmetic operations
+package ff
+
+// SquareElement z = x * x mod q
+// calling this instead of z.Square(x) is prefered for performance critical path
+// go - noescape
+// func SquareElement(res,x *Element)
+
+// Square z = x * x mod q
+// see https://hackmd.io/@zkteam/modular_multiplication
+func (z *Element) Square(x *Element) *Element {
+	if z != x {
+		z.Set(x)
+	}
+	MulAssignElement(z, x)
+	// SquareElement(z, x)
+	return z
+}

ff/element_test.go

@@ -1,9 +1,26 @@
-// Code generated by goff DO NOT EDIT
+// Copyright 2020 ConsenSys AG
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Code generated by goff (v0.2.0) DO NOT EDIT
+
+// Package ff contains field arithmetic operations
 package ff
 
 import (
 	"crypto/rand"
 	"math/big"
+	"math/bits"
 	mrand "math/rand"
 	"testing"
 )
@@ -21,7 +38,14 @@ func TestELEMENTCorrectnessAgainstBigInt(t *testing.T) {
 
 	modulusMinusOne.Sub(modulus, &one)
 
-	for i := 0; i < 1000; i++ {
+	var n int
+	if testing.Short() {
+		n = 10
+	} else {
+		n = 500
+	}
+
+	for i := 0; i < n; i++ {
 
 		// sample 2 random big int
 		b1, _ := rand.Int(rand.Reader, modulus)
@@ -57,7 +81,7 @@ func TestELEMENTCorrectnessAgainstBigInt(t *testing.T) {
 
 		rbExp := new(big.Int).SetUint64(rExp)
 
-		var bMul, bAdd, bSub, bDiv, bNeg, bLsh, bInv, bExp, bSquare big.Int
+		var bMul, bAdd, bSub, bDiv, bNeg, bLsh, bInv, bExp, bExp2, bSquare big.Int
 
 		// e1 = mont(b1), e2 = mont(b2)
 		var e1, e2, eMul, eAdd, eSub, eDiv, eNeg, eLsh, eInv, eExp, eSquare, eMulAssign, eSubAssign, eAddAssign Element
@@ -106,12 +130,40 @@ func TestELEMENTCorrectnessAgainstBigInt(t *testing.T) {
 		cmpEandB(&eNeg, &bNeg, "Neg")
 		cmpEandB(&eInv, &bInv, "Inv")
 		cmpEandB(&eExp, &bExp, "Exp")
+
 		cmpEandB(&eLsh, &bLsh, "Lsh")
+
+		// legendre symbol
+		if e1.Legendre() != big.Jacobi(b1, modulus) {
+			t.Fatal("legendre symbol computation failed")
+		}
+		if e2.Legendre() != big.Jacobi(b2, modulus) {
+			t.Fatal("legendre symbol computation failed")
+		}
+
+		// these are slow, killing circle ci
+		if n <= 5 {
+			// sqrt
+			var eSqrt, eExp2 Element
+			var bSqrt big.Int
+			bSqrt.ModSqrt(b1, modulus)
+			eSqrt.Sqrt(&e1)
+			cmpEandB(&eSqrt, &bSqrt, "Sqrt")
+
+			bits := b2.Bits()
+			exponent := make([]uint64, len(bits))
+			for k := 0; k < len(bits); k++ {
+				exponent[k] = uint64(bits[k])
+			}
+			eExp2.Exp(e1, exponent...)
+			bExp2.Exp(b1, b2, modulus)
+			cmpEandB(&eExp2, &bExp2, "Exp multi words")
+		}
 	}
 }
 
 func TestELEMENTIsRandom(t *testing.T) {
-	for i := 0; i < 1000; i++ {
+	for i := 0; i < 50; i++ {
 		var x, y Element
 		x.SetRandom()
 		y.SetRandom()
@@ -125,7 +177,6 @@ func TestELEMENTIsRandom(t *testing.T) {
 // benchmarks
 // most benchmarks are rudimentary and should sample a large number of random inputs
 // or be run multiple times to ensure it didn't measure the fastest path of the function
-// TODO: clean up and push benchmarking branch
 
 var benchResElement Element
 
@@ -219,6 +270,15 @@ func BenchmarkSquareELEMENT(b *testing.B) {
 	}
 }
 
+func BenchmarkSqrtELEMENT(b *testing.B) {
+	var a Element
+	a.SetRandom()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		benchResElement.Sqrt(&a)
+	}
+}
+
 func BenchmarkMulAssignELEMENT(b *testing.B) {
 	x := Element{
 		1997599621687373223,
@@ -232,3 +292,183 @@ func BenchmarkMulAssignELEMENT(b *testing.B) {
 		benchResElement.MulAssign(&x)
 	}
 }
+
+func BenchmarkMulAssignASMELEMENT(b *testing.B) {
+	x := Element{
+		1997599621687373223,
+		6052339484930628067,
+		10108755138030829701,
+		150537098327114917,
+	}
+	benchResElement.SetOne()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		MulAssignElement(&benchResElement, &x)
+	}
+}
+
+func TestELEMENTAsm(t *testing.T) {
+	// ensure ASM implementations matches the ones using math/bits
+	modulus, _ := new(big.Int).SetString("21888242871839275222246405745257275088548364400416034343698204186575808495617", 10)
+	for i := 0; i < 500; i++ {
+		// sample 2 random big int
+		b1, _ := rand.Int(rand.Reader, modulus)
+		b2, _ := rand.Int(rand.Reader, modulus)
+
+		// e1 = mont(b1), e2 = mont(b2)
+		var e1, e2, eTestMul, eMulAssign, eSquare, eTestSquare Element
+		e1.SetBigInt(b1)
+		e2.SetBigInt(b2)
+
+		eTestMul = e1
+		eTestMul.testMulAssign(&e2)
+		eMulAssign = e1
+		eMulAssign.MulAssign(&e2)
+
+		if !eTestMul.Equal(&eMulAssign) {
+			t.Fatal("inconsisntencies between MulAssign and testMulAssign --> check if MulAssign is calling ASM implementaiton on amd64")
+		}
+
+		// square
+		eSquare.Square(&e1)
+		eTestSquare.testSquare(&e1)
+
+		if !eTestSquare.Equal(&eSquare) {
+			t.Fatal("inconsisntencies between Square and testSquare --> check if Square is calling ASM implementaiton on amd64")
+		}
+	}
+}
+
+// this is here for consistency purposes, to ensure MulAssign on AMD64 using asm implementation gives consistent results
+func (z *Element) testMulAssign(x *Element) *Element {
+
+	var t [4]uint64
+	var c [3]uint64
+	{
+		// round 0
+		v := z[0]
+		c[1], c[0] = bits.Mul64(v, x[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd1(v, x[1], c[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd1(v, x[2], c[1])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd1(v, x[3], c[1])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 1
+		v := z[1]
+		c[1], c[0] = madd1(v, x[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, x[1], c[1], t[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, x[2], c[1], t[2])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, x[3], c[1], t[3])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 2
+		v := z[2]
+		c[1], c[0] = madd1(v, x[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, x[1], c[1], t[1])
+		c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, x[2], c[1], t[2])
+		c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, x[3], c[1], t[3])
+		t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+	{
+		// round 3
+		v := z[3]
+		c[1], c[0] = madd1(v, x[0], t[0])
+		m := c[0] * 14042775128853446655
+		c[2] = madd0(m, 4891460686036598785, c[0])
+		c[1], c[0] = madd2(v, x[1], c[1], t[1])
+		c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
+		c[1], c[0] = madd2(v, x[2], c[1], t[2])
+		c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
+		c[1], c[0] = madd2(v, x[3], c[1], t[3])
+		z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
+	}
+
+	// if z > q --> z -= q
+	// note: this is NOT constant time
+	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
+		var b uint64
+		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
+		z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
+		z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
+		z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
+	}
+	return z
+}
+
+// this is here for consistency purposes, to ensure Square on AMD64 using asm implementation gives consistent results
+func (z *Element) testSquare(x *Element) *Element {
+
+	var p [4]uint64
+
+	var u, v uint64
+	{
+		// round 0
+		u, p[0] = bits.Mul64(x[0], x[0])
+		m := p[0] * 14042775128853446655
+		C := madd0(m, 4891460686036598785, p[0])
+		var t uint64
+		t, u, v = madd1sb(x[0], x[1], u)
+		C, p[0] = madd2(m, 2896914383306846353, v, C)
+		t, u, v = madd1s(x[0], x[2], t, u)
+		C, p[1] = madd2(m, 13281191951274694749, v, C)
+		_, u, v = madd1s(x[0], x[3], t, u)
+		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
+	}
+	{
+		// round 1
+		m := p[0] * 14042775128853446655
+		C := madd0(m, 4891460686036598785, p[0])
+		u, v = madd1(x[1], x[1], p[1])
+		C, p[0] = madd2(m, 2896914383306846353, v, C)
+		var t uint64
+		t, u, v = madd2sb(x[1], x[2], p[2], u)
+		C, p[1] = madd2(m, 13281191951274694749, v, C)
+		_, u, v = madd2s(x[1], x[3], p[3], t, u)
+		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
+	}
+	{
+		// round 2
+		m := p[0] * 14042775128853446655
+		C := madd0(m, 4891460686036598785, p[0])
+		C, p[0] = madd2(m, 2896914383306846353, p[1], C)
+		u, v = madd1(x[2], x[2], p[2])
+		C, p[1] = madd2(m, 13281191951274694749, v, C)
+		_, u, v = madd2sb(x[2], x[3], p[3], u)
+		p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
+	}
+	{
+		// round 3
+		m := p[0] * 14042775128853446655
+		C := madd0(m, 4891460686036598785, p[0])
+		C, z[0] = madd2(m, 2896914383306846353, p[1], C)
+		C, z[1] = madd2(m, 13281191951274694749, p[2], C)
+		u, v = madd1(x[3], x[3], p[3])
+		z[3], z[2] = madd3(m, 3486998266802970665, v, C, u)
+	}
+
+	// if z > q --> z -= q
+	// note: this is NOT constant time
+	if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
+		var b uint64
+		z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
+		z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
+		z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
+		z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
+	}
+	return z
+
+}

go.mod

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

go.sum

@@ -1,172 +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.8.27 h1:d+gkiLaBDk5fn3Pe/xNVaMrB/ozI+AUB2IlVBp29IrY=
 github.com/ethereum/go-ethereum v1.8.27/go.mod h1:PwpWDrCLZrV+tfrhqqF6kPknbISMHaJv9Ln3kPCZLwY=
-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/iden3/go-iden3 v0.0.5 h1:NV6HXnLmp+1YmKd2FmymzU6OAP77q1WWDcB/B+BUL9g=
-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/go.mod h1:dAy3ld7l9f0ibDNOQOHHMYYIIbhfbHSm3C4ZsoJORNo=
-github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
-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/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/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-20190621222207-cc06ce4a13d4 h1:ydJNl0ENAG67pFbB+9tfhiL2pYqLhfoaZFw/cjLhY4A=
 golang.org/x/crypto v0.0.0-20190621222207-cc06ce4a13d4/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
-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/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/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/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=

mimc7/mimc7.go

@@ -137,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++ {
@@ -150,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)
+	return Hash(bElems, nil)
-	if err != nil {
-		panic(err)
-	}
-	return h
 }

mimc7/mimc7_test.go

@@ -74,7 +74,8 @@ func TestMIMC7(t *testing.T) {
 	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.")
-	hmsg := HashBytes(msg)
+	hmsg, err := HashBytes(msg)
+	assert.Nil(t, err)
 	assert.Equal(t, "16855787120419064316734350414336285711017110414939748784029922801367685456065", hmsg.String())
 }
 
@@ -86,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
+		Hash(bigArray4, nil)
 	}
 }

poseidon/poseidon.go

@@ -179,7 +179,7 @@ func Hash(arr []*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++ {
@@ -193,9 +193,5 @@ func HashBytes(b []byte) *big.Int {
 		utils.SetBigIntFromLEBytes(v, b[(len(b)/n)*n:])
 		bElems = append(bElems, v)
 	}
-	h, err := Hash(bElems)
+	return Hash(bElems)
-	if err != nil {
-		panic(err)
-	}
-	return h
 }

poseidon/poseidon_test.go

@@ -73,7 +73,8 @@ func TestPoseidon(t *testing.T) {
 	assert.Nil(t, err)
 	assert.Equal(t, "2978613163687734485261639854325792381691890647104372645321246092227111432722", hmsg2.String())
 
-	hmsg2 = HashBytes(msg2)
+	hmsg2, err = HashBytes(msg2)
+	assert.Nil(t, err)
 	assert.Equal(t, "2978613163687734485261639854325792381691890647104372645321246092227111432722", hmsg2.String())
 }
 
@@ -103,7 +104,7 @@ func BenchmarkPoseidon(b *testing.B) {
 	bigArray4 := []*big.Int{b12, b45, b78, b41}
 
 	for i := 0; i < b.N; i++ {
-		Hash(bigArray4) //nolint:errcheck
+		Hash(bigArray4)
 	}
 }
 
@@ -116,6 +117,6 @@ func BenchmarkPoseidonLarge(b *testing.B) {
 	bigArray4 := []*big.Int{b12, b45, b78, b41}
 
 	for i := 0; i < b.N; i++ {
-		Hash(bigArray4) //nolint:errcheck
+		Hash(bigArray4)
 	}
 }

utils/showarchbits_test.go

@@ -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)
-}

utils/utils.go

@@ -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)
 }
 
@@ -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
-}