Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Define elliptic curve for the VM #34

Open
bobbinth opened this issue Jul 27, 2020 · 0 comments
Open

Define elliptic curve for the VM #34

bobbinth opened this issue Jul 27, 2020 · 0 comments
Labels
enhancement New feature or request help wanted Extra attention is needed

Comments

@bobbinth
Copy link
Contributor

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 bobbinth added enhancement New feature or request help wanted Extra attention is needed labels Jul 27, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request help wanted Extra attention is needed
Projects
None yet
Development

No branches or pull requests

1 participant