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:
- 4 values are admissible as valid signatures, leading to some malleability (antinomic to disambiguity efforts like in
the BIP 0062 - Bitcoin Wiki, today Bitcoin ECDSA isn’t malleable) - more computations are necessary for the verifier, to check all admissible values
- Shamir’s trick cannot be used to speed up computations. Shamir’s trick enables a speed up of 40% of speed (gas cost)
The Shamir’s trick is a classical verification speed up, implemented here (Optimizing ECDSA with Shamir's trick and windowing by rdubois-crypto · Pull Request #3 · cartridge-gg/cairo-secp256r1 · GitHub) and here
Optimization of signature verification using Shamir's trick and windowing by rdubois-crypto · Pull Request #138 · starkware-libs/cairo-lang · GitHub).
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%.