crypto/secp256k1: BitCurve.Add() returns an undefined point when adding the point at infinity.

[adr1anh]

System information

Geth version: geth version
OS & Version: OSX
Commit hash :

Expected behaviour

I had some tests that failed when using "github.com/ethereum/go-ethereum/crypto/secp256k1", but succeeded with other implementations.
After investigating, I noticed that func (BitCurve *BitCurve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) does not return the correct result when either (x1,y1) or (x2,y2) is equal to the point at infinity O = (0,0).

Now, the official documentation for elliptic.Curve indicates that:

// Note that the point at infinity (0, 0) is not considered on the curve, and
// although it can be returned by Add, Double, ScalarMult, or ScalarBaseMult, it
// can't be marshaled or unmarshaled, and IsOnCurve will return false for it.

Unfortunately, most secp256k1 implementations for elliptic.Curve (as well as the official NIST family of curves in the standard lib) do perform addition correctly in this situation.
Therefore, it would be expected of go-ethereum/crypto/secp256k1 to mirror this behavior.

Proposed Fix

There are a few ways this could be mitigated.

1. If the point at infinity should not be used, Add should panic() if this is detected.
2. Imitate the Go implementation, and return the argument when the other is zero:

// zForAffine returns a Jacobian Z value for the affine point (x, y). If x and
// y are zero, it assumes that they represent the point at infinity because (0,
// 0) is not on the any of the curves handled here.
func zForAffine(x, y *big.Int) *big.Int {
	z := new(big.Int)
	if x.Sign() != 0 || y.Sign() != 0 {
		z.SetInt64(1)
	}
	return z
}

// Add returns the sum of (x1,y1) and (x2,y2)
func (BitCurve *BitCurve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
	z1 := zForAffine(x1, y1)
	z2 := zForAffine(x2, y2)
	return BitCurve.affineFromJacobian(BitCurve.addJacobian(x1, y1, z1, x2, y2, z2))
}

// addJacobian takes two points in Jacobian coordinates, (x1, y1, z1) and
// (x2, y2, z2) and returns their sum, also in Jacobian form.
func (BitCurve *BitCurve) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
	// See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
	x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
	if z1.Sign() == 0 {
		x3.Set(x2)
		y3.Set(y2)
		z3.Set(z2)
		return x3, y3, z3
	}
	if z2.Sign() == 0 {
		x3.Set(x1)
		y3.Set(y1)
		z3.Set(z1)
		return x3, y3, z3
	}
        ...
}

Steps to reproduce the behaviour

package main

import (
	"fmt"
	"math/big"

	"github.com/ethereum/go-ethereum/crypto/secp256k1"
)

func main() {
	curve := secp256k1.S256()

	// Get base point G = (Gx, Gy)
	Gx, Gy := curve.Params().Gx, curve.Params().Gy
	GyNeg := new(big.Int).Neg(Gy)

	// -G = (Gx, -Gy)
	GyNeg.Mod(GyNeg, curve.Params().N)

	// O = (Ox, Oy) = G - G
	Ox, Oy := curve.Add(Gx, Gy, Gx, GyNeg)
	zero := big.NewInt(0)
	if Ox.Cmp(zero) != 0 || Oy.Cmp(zero) != 0 {
		fmt.Println("both components of O = (Ox, Oy) should be 0")
	}

	// Try G2 = G + O
	G2x, G2y := curve.Add(Gx, Gy, zero, zero)
	if G2x.Cmp(Gx) != 0 {
		fmt.Println("G2x should be equal to Gx")
	}
	if G2y.Cmp(Gy) != 0 {
		fmt.Println("G2y should be equal to Gy")
	}
}

[ligi]

ref the great PR by @MariusVanDerWijden #22621

[fjl]

Fixed by #22621