译自 halo2 book:https://zcash.github.io/halo2/design/gadgets/ecc.html

椭圆曲线(Elliptic Curves)

EccChip

halo2_gadgets 提供了一个芯片(chip),它使用 10 个 advice 列实现了 EccInstructions。 该芯片目前仅限于 Pallas 曲线,但在不久的将来会扩展以支持 Vesta 曲线。

芯片假设(Chip assumptions)

EccChip 所做假设的一个非穷尽列表:

• $0$ 不是曲线上任何有效点(point)的 $x$ 坐标。
  • 对 Pallas 成立,因为 $5$ 在 ${\mathbb{F}}_q$ 中不是平方数。
• $0$ 不是曲线上任何有效点的 $y$ 坐标。
  • 对 Pallas 成立,因为 $-5$ 在 ${\mathbb{F}}_q$ 中不是立方数。

布局(Layout)

下表展示了各个芯片子区域的门(gate)如何使用各列:

• $W$ - 见证点(witnessing points)。
• $AI$ - 不完全点加法(incomplete point addition)。
• $AC$ - 完全点加法(complete point addition)。
• $MF$ - 定基标量乘(Fixed-base scalar multiplication)。
• $MVI$ - 变基标量乘(variable-base scalar multiplication),不完全轮(incomplete rounds)。
• $MVC$ - 变基标量乘,完全轮(complete rounds)。
• $MVO$ - 变基标量乘,溢出检查(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}$$