Non ambiguous point representation for 40% verification speed up

The current implementation of elliptic computation use a x-only representation, ie only the x-coordinates is stored on chain, the y-coordinates being recovered using the curve equation.

This efficient representation allows to reduce the storage cost. An ambiguity exists, which can be solved by two possible ways:

  • allowing two admissible values for an input point of a function.
  • enforcing the expected value to have by convention an even value.

First choice is what is done on starknet. This choice comes with the following drawbacks:

A way to solve ambiguity is to let the signer realize the disambiguation (more signing computations). This is for instance done in the musig2 implementation.
Doing so would solve malleability and reduce verification gas cost over stark curve by 40%.