Elliptic Curves

EccChip

halo2_gadgets provides a chip that implements EccInstructions using 10 advice columns. The chip is currently restricted to the Pallas curve, but will be extended to support the Vesta curve in the near future.

Chip assumptions

A non-exhaustive list of assumptions made by EccChip:

• $0$ is not an $x$-coordinate of a valid point on the curve.
  • Holds for Pallas because $5$ is not square in ${\mathbb{F}}_q$.
• $0$ is not a $y$-coordinate of a valid point on the curve.
  • Holds for Pallas because $-5$ is not a cube in ${\mathbb{F}}_q$.

Layout

The following table shows how columns are used by the gates for various chip sub-areas:

• $W$ - witnessing points.
• $AI$ - incomplete point addition.
• $AC$ - complete point addition.
• $MF$ - Fixed-base scalar multiplication.
• $MVI$ - variable-base scalar multiplication, incomplete rounds.
• $MVC$ - variable-base scalar multiplication, complete rounds.
• $MVO$ - variable-base scalar multiplication, overflow check.

$$\begin{array}{ccccccccccc}\text{Sub-area}& a_0& a_1& a_2& a_3& a_4& a_5& a_6& a_7& a_8& a_9\\ W& x& y& & & & & & & & \\ AI& x_p& y_p& x_q& y_q& & & & & & \\ & & & x_r& y_r& & & & & & \\ AC& x_p& y_p& x_q& y_q& \lambda & \alpha & \beta & \gamma & \delta & \\ & & & x_r& y_r& & & & & & \\ MF& x_p& y_p& x_q& y_q& \text{window}& u& & & & \\ & & & x_r& y_r& & & & & & \\ MVI& x_p& y_p& {\lambda }_2^{lo}& x_A^{hi}& {\lambda }_1^{hi}& {\lambda }_2^{hi}& z^{lo}& x_A^{lo}& {\lambda }_1^{lo}& z^{hi}\\ MVC& x_p& y_p& x_q& y_q& \lambda & \alpha & \beta & \gamma & \delta & z^{complete}\\ & & & x_r& y_r& & & & & & \end{array}$$