distaff icon indicating copy to clipboard operation
distaff copied to clipboard

Define elliptic curve for the VM

Open bobbinth opened this issue 3 years ago • 0 comments

It would be great if the VM supported EC operations (point addition, doubling, multiplication). This would open the door for verifying EC signatures (e.g. Schnorr) within the VM as well as many other useful things.

The biggest challenge is that the VM operates in a 128-bit base field, but for acceptable security we need elliptic curves in ~256-bit field. One way to address this is by defining an elliptic curve in a quadratic extension of the base field. This would be similar to Microsoft's FourQ curve.

Currently, the base field is defined by prime modulus m = 2128 - 45 * 240 + 1. This can be changed if needed, but the modulus should comply with the following constraints:

  1. m should be around 128 bits in size (could be a bit less if needed - e.g. 126 bits).
  2. m = k * n + 1, where n is a power of 2 greater than 232. This ensures that the field has enough roots of unity for STARK operations.
  3. (m - 1) % 3 != 0, and also ideally, (m - 1) % 5 != 0. This ensures that the field can be used with algebraic hash functions (e.g. Rescue, Poseidon).

bobbinth avatar Jul 27 '20 01:07 bobbinth