A Twisted Edwards curve (Jubjub) is provided by package github.com/consensys/gurvy/bls381/twistededwards.GetEdwardsCurve() for use with BLS12-381. The curve parameters specify that the Order is:

52435875175126190479447740508185965837647370126978538250922873299137466033592

However, this is not the order of the base point, which of course is prime. This number is actually the order times the cofactor (8), which is not what I expect. In particular, including the cofactor in the order is inconsistent with the Twisted Edwards curve provided for BN256. I would expect the order to be the prime order of the base point:

6554484396890773809930967563523245729705921265872317281365359162392183254199

Continuous fuzz testing with go-fuzz

On eddsa.PrivateKey, eddsa.PublicKey and eddsa.Signature:

• generate (by hand) a hex encoded serialized object with a previous gnark-crypto version, define it as const in one test. Add a test that ensure that each subsequent release serialization matches.
• same logic; sign a dummy message, and verify that the signature is still verifiable / equal to the previous version.

Field inverse is computing 1/x mod p. This is currently used for FFT, hash-to-curve, final exponentiation (easy part), coordinates conversion and Karabina's cyclotomic square decompression (final exp. hard part). This can also be possibly needed for BW6 Miller loop in 2-NAF (see here) and BatchAffineAddition (see #72). Particularly, for BatchAffineAddition and Karabina (see #75), the faster the field inversion is the better the the performance is.

Currently, gnark-crypto implements Algorithm 16 in [GKPP06]. Implementing this work [Pronin20] in pure Go should yield better performances.

Summary

It seems that the twisted edwards implementation for embedded curves does not match the hyperelliptic reference in the comments. it seems that the implementation assumes Z2=1, whereas this is not always the case. Also the receiver is being used in the calculation which seems to be a mistake.

Description

Reference

Point addition using projective co-ordinates, no assumptions (copied from the hyper-elliptic website)

      A = Z1*Z2
      B = A2
      C = X1*X2
      D = Y1*Y2
      E = d*C*D
      F = B-E
      G = B+E
      X3 = A*F*((X1+Y1)*(X2+Y2)-C-D)
      Y3 = A*G*(D-a*C)
      Z3 = F*G

Link: https://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html

Implementation

(Commented beside the lines which are incongruent with my understanding)

func (p *PointProj) Add(p1, p2 *PointProj) *PointProj {

	var res PointProj

	ecurve := GetEdwardsCurve()

	var A, B, C, D, E, F, G, H, I fr.Element
	A.Mul(&p1.Z, &p2.Z)
	B.Square(&A)
	C.Mul(&p1.X, &p2.X)
	D.Mul(&p1.Y, &p2.Y)
	E.Mul(&ecurve.D, &C).Mul(&E, &D)
	F.Sub(&B, &E)
	G.Add(&B, &E)
	H.Add(&p1.X, &p1.Y)
	I.Add(&p2.X, &p2.Y)
	res.X.Mul(&H, &I).
		Sub(&res.X, &C).
		Sub(&res.X, &D).
		Mul(&res.X, &p1.Z). // should be Mul(&res.X, &A) 
		Mul(&res.X, &F)
	res.Y.Add(&D, &C).
		Mul(&res.Y, &p.Z). // should be Mul(&res.Y, &A). Also note it is using p.Z
		Mul(&res.Y, &G)
	res.Z.Mul(&F, &G)

	p.Set(&res)
	return p
}

Link to code: https://github.com/ConsenSys/gnark-crypto/blob/master/ecc/bls12-381/twistededwards/point.go#L262

Discussion

• My understanding of the API being used is that the receiver should not be used in calculation and it is there to avoid unnecessary allocations.

• It seems that possibly in the past that gnark-crypto had a use-case for adding an affine point to a projective point which might have led to the code linked above. Currently, since both parameters are projective points, I do not believe it is possible to assume that p2.Z = 1

k/2-th Frobenius powers can be replaced by conjugations in the final exponentiation of the pairing implementation for the curves.

Motivation

In Tate-based pairings, the target group GT is the r-th root of unity in Fq^k where q is the finite field prime, r the curve subgroup order and k the embedding degree. The pairing requires also a final exponentiation to (q^k-1)/r to reduce the output to a unique value. Using k-th cyclotomic polynomial, the exponent can be simplified into an easy part (q^k-1)/phi_k(q) and a hard part phi_k(q)/r. The easy part can be computed cheaply using Frobenius powers. However, if there is a power to k/2 it should be replaced by a simple conjugation. An inverse is a power to q^(k/2) but since there is a q^(k/2)-1 component in that exponent, the element f becomes unitary (i.e. norm 1) and the inversion becomes a simple conjugation.

Currently, gnark-crypto implements 2-dim GLV for all curves and 2-dim GLS for twists over Fp2 (BLS12, BN) and over Fp4 (BLS24). This issue is a placeholder to track implementation of 4-dim GLS (BLS12, BN) and 8-dim GLS (BLS24). This would speedup scalar multiplication on G2 for these curves and potentially multi-scalar-multiplication on G2 (needed for Groth16 in gnark).

Bandersnatch curve (https://eprint.iacr.org/2021/1152.pdf) is a new elliptic curve built over the BLS12-381 scalar field. It is equipped with an efficient endomorphism, allowing a fast scalar multiplication algorithm. It is an alternative to jubjub currently implemented in gnark-crypto [here].

Hello.
As I already requested over the Discord, it will be awesome if you can add the SSWU HashToCurve functions for bls381

I have been using the https://github.com/kilic/bls12-381 library for our blockchain (https://github.com/olympus-protocol/ogen) since it is the only pure go BLS library which follows the latest drafts.

Recently I have discovered that kilic library is not very fast (compared with herumi mcl or blst) and that's where I found gurvy.

I really hope you can add it since there is no efficient BLS pure go implementation right now.

hi, i try to map any data's hash to bn256 curve by HashToCurveG2Svdw(), but it seems false

msg := []byte("aaaaaa")
dst := make([]byte,20)
r,e :=HashToCurveG2Svdw(msg,dst)
r.IsOnCurve()  ----- return false

BTW, is there some method to map any data's to twistededwards curve? previous HashToCurveG2Svdw() only map data to bn256 curve.
thanks!

Most of the library is tested with property based testing & fuzzing.

Need to add:

• cross libraries checks, when available
• carefully crafted test vectors (check other libraries -- with appropriate licensing -- )
• non regression tests (example; hash function or signatures should always be backward compatible)

Hey all, been trying to include gurvy's bn256 package into go-ethereum so it can be used in our differential fuzzing efforts.
One problem I ran into is, that gurvy uses go-ethereum as a dependency for tests. This forces us to depend on an older version of go-ethereum which forces us to import older versions of the same packages we import the newest version from. E.g adding gurvy imports 5 additional versions of golang.org/x/exp.

It would be great if you could move the tests from bn256/interop_test.go into another package.

See also https://github.com/ethereum/go-ethereum/pull/21812/files

edit. Removing go-ethereum from the codebase would reduce the go.sum file by 136 lines

Currently all curves of embedding degree 12 (ie. everything except BW6-761) implement (and test!) all six of the methods MulByV, MulByVW, MulByV2W, MulByVWNRInv, MulByV2NRInv, MulByWNRInv even though each curve actually uses only three:

• BLS12-381 pairing uses only MulByVWNRInv, MulByV2NRInv, MulByWNRInv
• BLS12-377, BN256 pairings use only MulByVW, MulByV, MulByV2W

These methods appear in e12.go for each curve.
This is bad design. The original purpose was to facilitate automatic generation of known-answer tests in sage---ie. so we can use the same sage script to generate KATs for all degree-twelve field extensions in all curves. (The relevant sage script is pointed to in #6.)

BW6-761 needs its own new trio of methods: MulByVMinusThree, MulByVminusTwo, MulByVminusFive. I don't think we should simply pile these three additional methods on top of the other six. Instead, we should remove these methods from e12.go to pairing.go; each curve should keep only the three methods it needs instead of supporting all of them.

There's no need for KATs for these methods, so we can simply remove them from the sage script to save time. Instead, we can test these methods in pure Go by comparing against the output of Mul. Code will be simpler, tests will be simpler.

Hi @rojotek @jmlubin @ggutoski @gbotrel @ThomasPiellard ，
gnark is wonderful project, but some code is hard to read if not all theory known by reader. Could anyone write some document/guide/api doc and provide some paper/blog/wiki link implement in gnark. Draft material is OK too. Thank you very much.

Shouldn't it be equal to sizePointCompressed? https://github.com/ConsenSys/gurvy/blob/master/bw761/twistededwards/point.go#L127
Likewise are the lengths in the comments on lines 95-96 correct?

Previous version of the fft included bit reverse operation in the domain pre-computed coset tables (in a dirty way, non generalizable to many cosets).

Need to propose a general pattern to avoid bitReverse operations.

I noticed that the G1Jac, G1Affine, G2Jac and G2Affine have no way to marshal them from and to a byte array.
Both the google and cloudflare implementations of bn256 have these methods as well as killic's implementation of bls12-381 (FromBytes and ToBytes).
I would suggest to implement the marshaling as follows:

// Marshal
func (n *G1Jac) Marshal() []byte {}
	
// Unmarshal 
func (e *G1Jac) Unmarshal(m []byte) ([]byte, error) {}

Which is in line with the implementations of google and cloudflare used in go-ethereum and the golang bn256 implementation.

For BLS12-377 and BLS24-315: https://eprint.iacr.org/2020/1407.pdf

Field element multiplication, at a minimum, should have an optimized arm64 implementation.

baidudeMacBook-Pro:09$ GOOS=linux GOARCH=arm64 go build

github.com/consensys/gurvy/bls377/fr

/opt/gopath/pkg/mod/github.com/consensys/[email protected]/bls377/fr/element.go:517:2: undefined: fromMontElement
/opt/gopath/pkg/mod/github.com/consensys/[email protected]/bls377/fr/element.go:530:2: undefined: mulAssignElement

github.com/consensys/gurvy/bls381/fr

/opt/gopath/pkg/mod/github.com/consensys/[email protected]/bls381/fr/element.go:517:2: undefined: fromMontElement
/opt/gopath/pkg/mod/github.com/consensys/[email protected]/bls381/fr/element.go:530:2: undefined: mulAssignElement

github.com/consensys/gurvy/bn256/fr

/opt/gopath/pkg/mod/github.com/consensys/[email protected]/bn256/fr/element.go:517:2: undefined: fromMontElement
/opt/gopath/pkg/mod/github.com/consensys/[email protected]/bn256/fr/element.go:530:2: undefined: mulAssignElement

github.com/consensys/gurvy/bn256/fp

/opt/gopath/pkg/mod/github.com/consensys/[email protected]/bn256/fp/element.go:517:2: undefined: fromMontElement
/opt/gopath/pkg/mod/github.com/consensys/[email protected]/bn256/fp/element.go:530:2: undefined: mulAssignElement

hi teams, I have a question for you guys. which curve can be used for type-1 pairing implementation？

any reply will be appreciated. thanks.

Should be a const + verifications of the hash(const) for the MiMC construct?

e.g. In ./internal/generator/config/bls12-381.go, if we set GLV: false and CofactorCleaning: false, the template internal/generator/ecc/template/point.go.tmpl handles incorrectly this case.

FRI is an interactive oracle proof of proximity for polynomials to assess probabilistically (in a logarithmic-in-the-degree number of rounds) if a function, provided as an oracle, is a low degree polynomial. It leverages the same structure than the FFT, that is it works on a sequence of finite algebraic groups, with associated rational maps (which can be the identity, as in the multiplicative FFT), linked together by surjective maps with given kernel. As the ECFFT is used to mimic the FFT in an arbitrary finite field, the ECFFT technique can be used to implement FRI on an arbitrary finite field. The ECFFT allows to do fast polynomials operations (like division) on an arbitrary finite field. However, when working on arbitrary finite fields, one lacks an efficient polynomial commitment scheme. With FRI+ECFFT, this gap is filled because FRI can be transposed on arbitrary finite fields. It would allow PLONK to work on an arbitrary finite field.

We are running gnark-crypto against other bls implementations on oss-fuzz, and have found a crash. Essentially, the code which crashes it this (printouts added by me) :

	// sample a random scalar
	s, err := randomScalar(input, fp.Modulus())
	if err != nil {
		return nil, nil, err
	}
	fmt.Printf("Scalar: %x\n", s)
	// compute a random point
	cp := new(gnark.G1Affine)
	_, _, g1Gen, _ := gnark.Generators()
	cp.ScalarMultiplication(&g1Gen, s)
	cpBytes := cp.Marshal()
	fmt.Printf("Scalar mult, bytes: %x\n", cpBytes)

	// marshal gnark point -> geth point
	g1 := bls12381.NewG1()
	kp, err := g1.FromBytes(cpBytes)

And what happens is

Scalar: 73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff0000000100000000000000
Scalar mult, bytes: 400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
panic: Could not marshal gnark.G1 -> geth.G1: must be less than modulus

goroutine 1 [running]:
github.com/ethereum/go-ethereum/tests/fuzzers/bls12381.getG1Points({0x709380, 0xc00002ecf0})
        /home/user/go/src/github.com/ethereum/go-ethereum/tests/fuzzers/bls12381/bls12381_fuzz.go:205 +0x64b

So we do a scalar mult, then marshal the result into cpBytes. Then we try to unmarshal those bytes into a bls12381 . And then we find that the first field element is smaller than the modulus, which it apparently rejects.

I'm not sufficiently knowledgeable here to know what is happening or why, so would appreciate some help assessing this.
I did test this against the latest version of gnark-crypto also, but go the same result.

When deserializing points (see ecc/xxx/Decoder) , we do a subgroup check.

gnark may need to deserialize millions of such points, and performance wise, we can't afford to do multiple scalar multiplication per point.

See (?):

• https://cseweb.ucsd.edu/~mihir/papers/batch.pdf

Multiexp code generation generates lots of msmCXX functions (to allocate buckets on the stack).

Would be nice to find a way (maybe using unsafe pointers on []byte arrays / custom memory allocator) to have a single msmCXX function per curve.

To be integrated with continuous benchmarking.

Plookup (the bare bone protocol, not the merge of plookup+plonk) should be implemented and benchmarked.

Prettify godoc for pkg.go.dev as a target.

We should clean and correct comments across gnark-crypto. Also, It would be nice in the code generation to use mmcloughlin's mathfmt for equations and bib for Bibtex references.

It's been decided that the template generator should generate only the following:

• EC group code (g1.go, g2.go)
• field tower (e2.go, e6.go, e12.go)
• Frobenius constants (frobenius.go)

In particular, the template generator should not produce any pairing code (except for Frobenius constants). Pairing code is too dependent on the specific curve---generating this code inside the template is just a mess.

We should split the template generator into a separate repo, similar to goff. (Maybe merge the gurvy template generator into goff?) The gurvy repo should not contain any template code. Instead it should contain only the output of the template generator plus any curve-specific code such as pairing code.

Just try the following test:

A := new(Point).ScalarMul(Base, big.NewInt(5))
B := new(Point).ScalarMul(Base, big.NewInt(-5))
C := new(Point).Add(A,B)

D := new(Point).ScalarMul(Base, Order)

The outputs A,B are the same result. And D is not (0,1). The computation result is different from: iden3-crypto. And I'm wondering that could I implement BulletProofs based on twisted edwards bn254?

Right now one tree could only be used once, could we optimize it?
such as adding UpdateNode function

Some tests are failing for generated secp256k1 fields which has 256 bit dense modulus value. To regenerate in a clean directory:

goff -m 115792089237316195423570985008687907853269984665640564039457584007908834671663 -o . -p secp256k1_fp -e Element
go mod init tmp && go mod tidy
go test

https://hackmd.io/@zkteam/eccbench

I would like to clarify the benchmarks above, since when I benchmarked it locally, some discrepancies appeared.

In particular, I noticed the BenchmarkG1AffineDouble-16 bench was much slower, relative to other timings, than in the above listed benchmarks. Hence, my questions is whether any of the benches listed were based on the extended rather than jacobian representation.

I notice the consistency of this discrepancy. mcl is faster for mixed add but gurvy supposedly faster for double. But when I bench on my machine, double is very slow, and only the extended double has the claimed speed. Hence, my suggestion is to redo the data collection since now I think there is reason to doubt it.

Another question I have is with regards to the odd naming convention. In particular, why one lists BenchmarkG1AffineDouble-16 instead of BenchmarkG1JacDouble-16, since one is not using affine coordinates...

Currently the KZG code allows to

• Compute an opening proof of one polynomial at single point + verifying such a proof
• Compute a batch opening proof of several polynomials at a single point + verifying such a batch opening proof

However the method to batch verify multiple proofs at different points is missing in the API.

In all curves, the 2- and 6-degree field extensions have methods MulByNonResidue, MulByNonResidueInv. Sometimes the most efficient way to implement these methods is to call Mul with a hard-coded constant. Example: the inverse of 2: https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/bls381/e6.go#L530
These constants should be computed automatically by the template generator. Right now we only compute the inverse of 2, as in here: https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/internal/generators/tower/generator.go#L96
Similar constants are not automatically computed. Instead they are simply hard-coded in the template generator. Example: this constant for BLS377: https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/bls377/e6.go#L509
is simply hard-coded in the template here: https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/internal/generators/tower/templates/fp2/inline.go#L37
That's bad, of course. All these constants should be computed automatically.

An egregious example

Our current "hello world" implementation of the BW6-761 pairing initializes the inverse of 4 via string conversion inside the Miller loop! https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/bw761/pairing.go#L418
That must be slowing down the Miller loop. Thus, a proper solution for this issue should yield a noticeable performance improvement for the BW6-761 Miller loop.

What to do

As mentioned above, our only auto-generated constant in this family is the inverse of 2. But that template code is a PoC and does not immediately generalize. A more intelligent design is needed in the template generator.

Most (all?) of these hard-coded constants appear only in the MulByV, etc methods in #7 . Presumably, design work for this issue will directly affect #7, too.

The cost of the final exponentiation is dominated by Expt(), which is a square-and-multiply exponentiation by the curve seed u. Currently, the squarings are implemented as in the Granger-Scott cyclotomic squaring (GS).

For the curves implemented in gnark-crypto (except for BN254), there is a series of consecutive 0's in the seed and it might be interesting to switch to the Karabina cyclotomic squaring only of this series.

Karabina's method works on compressed GT elements and saves 2 multiplications in F_p^{k/d} compared to GS, where k is the embedding degree and d the twist degree. The cost of decompression, however, is dominated by an inverse in F_p^{k/d}.

Concretely, given a series of s 0's in the seed, the trick is worth it if:

• For BLS12, 1 inverse over F_p costs less than 6*s-4 muls over F_p
• For BLS24, 1 inverse over F_p costs less than 18*s-16 muls over F_p

w/ subgroup check on GT.

• d := NewDomain(1, 1, false) triggers a panic
• cosetGensInv[i].Mul(&cosetGensInv[1], &d.FinerGeneratorInv) instead of cosetGensInv[i].Mul(&cosetGensInv[i-1], &d.FinerGeneratorInv).

The error didn't trigger failing tests in PLONK, because only the FFT (not FFTInverse) is used on cosets > 1, on which there is no error. The FFTInverse on cosets is used only for the first coset, on which there is no error.

Figure out best algorithm and implement.

May be useful for MultiExponentiation with lots of 1 ( gnark circuit with binary decomposition for example) .

Summary

When instantiating the curve parameters for an embedded curve like JubJub, the A parameter needs to be set, however the group arithmetic formulas assume that A = -1.

A is set here: https://github.com/ConsenSys/gnark-crypto/blob/1572c4e3cda6663b8d00ae05291e4b1d4f585cd8/ecc/bls12-381/twistededwards/twistededwards.go#L52

point addition is computed here, implicitly assuming a = -1 : https://github.com/ConsenSys/gnark-crypto/blob/1572c4e3cda6663b8d00ae05291e4b1d4f585cd8/ecc/bls12-381/twistededwards/point.go#L199

Disadvantages

Explicitly adding the support for various As will add an extra field multiplication per affine point addition and other various costs.

Advantages

If someone uses your library and does not use A = -1, it will produce the correct results. All of the embedded curves used in your library so far use A=-1.

Solutions

• One can assume that A will always be -1 for all curves of interest to gnark-crypto, and not allow the A variable to be configurable.
• Change the group arithmetic to use any specified a value. I'm not familiar with go-generate; it may be possible to generate code when a=-1 and otherwise generate the general formulas

Currently, gnark-crypto implements twisted Edwards arithmetic in affine coordinates and projective coordinates. We should implement extended coordinates as they allow faster arithmetic out-circuit.

Here's the paper: 2020/351 - Optimized and secure pairing-friendly elliptic curves suitable for one layer proof composition
Links to reference implementations in C++ and sage within.

This issue is a place to collect notes on development.

Branches

Work has already begun on branch feature/bw6-761. While working here, I re-designed the template generator to better facilitate new curves. This re-design is in experimental-pairing-gen, which is branched from feature/bw6-761. There's an active PR to merge experimental-pairing-gen back into feature/bw6-761: #5

It was decided during offline discussion that work on BW6-761 would continue on experimental-pairing-gen, and that branch will be merged into develop only once BW6-761 is complete.

Tests for the field tower, Frobenius, final exponentiation

Tests for the field tower (including Frobenius, final exponentiation) for existing curves (BLS12-377, BLS12-381, BN256) were generated using a template before gurvy was split from gnark. That template was removed from both gnark and gurvy, but the tests generated by it are still used.

In order to get things done as quickly as possible, I dug up this template in order to generate new tests for BW6-761.

• The old gnark commit with the testpoint generator: gnark@7dcd496ba42799bf1d4b695226ce6cc4c1f48792
• I added some new commits to gnark with fresh code for BW6-761: gnark@f1c4c75b9e0cd3e1b48e22f3d30dfa9a3543c9b7
• These commits are in an orphan branch of gnark that might be deleted in the future. gnark@bw6-tower-tests

I used a throwaway sage script to assist in debugging the final exponentiation for BW6-761 and for comparison against the sage reference implementation cited above. I put that script into git so that it can be found in the future and then deleted it from the repo. It can be found here: 6c7511c

Similarly to BLS12 curves, BLS24 Miller loop counter is the curve seed u. Although this seed is 32 bits (half the size of BLS12 seeds), the BLS24 Miller loop is slower. This is mainly because the most costly operations encountered in the Miller loop computation are those that take place in the full extension field Fp24. Implementing this paper's [CBNW10] quadruple-and-add algorithm would reduce operations in Fp24 (see section 6 for comparisons).