Addition using projective co-ordinates does not match reference

[kevaundray]

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

[yelhousni]

Good catch @kevaundray !
gnark-crypto use-case of twisted Edwards is edDSA in affine coordinates which explains why edDSA tests don't fail. However, as you pointed out, there are two problems with the addition of twisted Edwards points in projective coordinates:

• The linked code corresponds to a mixed addition of a projective point and an affine point (EFD) but the API takes two points in projective with the assumption Z2=1. The tests didn't catch this because we directly use projective points that are converted from random affine points, hence Z=1 always.
• There is indeed a mistake when multiplying by p.Z instead of p1.Z (or A). The tests didn't catch this because they use p1.Add(&p1, &p2) so in this case p.Z=p1.Z in the Add() function, which is wrong in general.

I made a PR (#90) that renames the current projective Add() to MixedAdd() and takes an affine point and a projective point. It also implements the normal Add() with no assumptions on Z and revisits the tests so that it catches these problems.

Thank you.