EC OP Builtin
The EC OP (Elliptic Curve OPeration) builtin performs elliptic curve operations on the STARK curve. Specifically, it computes R = P + mQ, where P and Q are points on the curve and m is a scalar multiplier. Each point (P, Q and R) is represented by a pair of field elements for its x and y coordinates.
This builtin enables efficient implementation of cryptographic algorithms that require elliptic curve arithmetic, providing significant performance advantages over implementing these operations directly in Cairo code.
Cells Organization
The EC OP builtin has its own dedicated segment during a Cairo VM run. Each operation is represented by a block of 7 cells:
| Offset | Description | Role |
|---|---|---|
| 0 | P.x coordinate | Input |
| 1 | P.y coordinate | Input |
| 2 | Q.x coordinate | Input |
| 3 | Q.y coordinate | Input |
| 4 | m scalar value | Input |
| 5 | R.x coordinate | Output |
| 6 | R.y coordinate | Output |
The first five cells are inputs that must be written by the program, while the last two cells are outputs that will be computed by the VM when read.
Valid Operation Example
In this example, we can see a correctly configured EC OP builtin operation:
The program has properly set:
- Point P coordinates
- Point Q coordinates
- Scalar m value
When the program reads cells at offsets 5 and 6, the VM computes R = P + mQ and returns the result coordinates.
Error Condition Example
In this example, we see an error condition when trying to read the result with incomplete inputs:
The program attempts to read the output cells at offsets 5 and 6, but the VM cannot compute R = P + mQ because:
- Point P coordinates are properly set
- Point Q coordinates are missing (both cells are empty)
- Scalar m value is set
Since the coordinates of point Q are missing, the VM cannot perform the calculation and will throw an error when attempting to read the output cells.
If any input value is invalid (not a field element) or missing, the EC OP builtin will fail when its output is accessed. All five input cells must contain valid field elements before reading the output.
Implementation References
These implementation references of the EC OP builtin might not be exhaustive:
Resources on Elliptic Curve Operations
If you're interested in elliptic curve operations and their cryptographic applications:
- StarkNet, STARK Curve
- Andrea Corbellini, Elliptic Curve Cryptography: a gentle introduction