group: ge(j) should have as invariant that the curve equation holds

[real-or-random]

I was surprised to see that this may be violated in secp256k1_eckey_pubkey_parse:

secp256k1/src/eckey_impl.h

Lines 26 to 31 in cc55757

	secp256k1_ge_set_xy(elem, &x, &y);
	if ((pub[0] == SECP256K1_TAG_PUBKEY_HYBRID_EVEN || pub[0] == SECP256K1_TAG_PUBKEY_HYBRID_ODD) &&
	secp256k1_fe_is_odd(&y) != (pub[0] == SECP256K1_TAG_PUBKEY_HYBRID_ODD)) {
	return 0;
	}
	return secp256k1_ge_is_valid_var(elem);

I claim

• ge(j) objects should always represent valid points on the curve.
• This invariant should be checked in VERIFY mode, in secp256k1_ge(j)_verify or at least in secp256k1_ge_set_xy
• There should be a separate function secp256k1_ge_try_set_xy which checks if (x,y) is on the curve, and only if yes, returns 1 and outputs a ge. That function can be used to implement secp256k1_eckey_pubkey_parse.
• secp256k1_ge_is_valid_var should be removed (or repurposed to secp256k1_ge_verify_on_curve_var without return value, as mentioned above).

[sipa]

secp256k1_ge(j) are also used to represent points on effective affine isomorphic curves. Does that mean that in VERIFY mode we need to store the isomorphism factor inside ge(j).

[real-or-random]

secp256k1_ge(j) are also used to represent points on effective affine isomorphic curves.

Oh right, that's a valid point. [1]

Does that mean that in VERIFY mode we need to store the isomorphism factor inside ge(j).

Perhaps it makes sense to have a separate type for effective affine computations. This will also make the code more self-documenting and thus enhance readability.

[1] Absolutely no pun intended.

[apoelstra]

When doing the exhaustive tests we also use off-curve points (though we stick to a single group, so we use a fixed isomoprhism class). So we would need to be able to configure or disable this check.

I was going to say that there's also some really awful abuse of ge_storage in ecmult_impl.h, which I introduced in #557, but sadly(?) all that got deleted in #956 when we deleted ecmult_context.

Perhaps it makes sense to have a separate type for effective affine computations. This will also make the code more self-documenting and thus enhance readability.

I think this is a good idea, independently of this.