feat: ecip circuit

[ClementWalter]

Why

When we merged #291 we removed the ecdsa circuit builder in python (see https://github.com/feltroidprime/keth/blob/f5f8e0b657731469e77fae359e3bf8d59cdefea3/cairo/src/utils/ecdsa_circuit.py)

We need to be able to build the ecip circuit from our codebase

What

Write a cairo zero circuit with the same logic that compiles to the same circuit.

How

• Study source python and source paper
• write corresponding code

[zmalatrax]

Some updates on implementing the ECIP circuit of 2 points.
What the circuit does: Verify that $Q = k_1P_1 + k_2P_2$, with $Q, P_1, P_2$ points of an elliptic curve.
It verifies that the equation (3) from the paper "Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity", by Liam Eagen (source: https://eprint.iacr.org/2022/596.pdf, p.9) holds.

The computation is done through a hint, which fills the memory with all the required values to verify the eq (build_msm_hints_and_fill_memory)

Observations

I've noticed a few discrepancies between the ecip_input built in secp256k1.cairo and the input described in the hydra script (garaga circuit python descriptor) in function build_input(). The function _run_inner_circuit() is based on the input format from build_input().

In secp256k1.cairo the ecip_input takes 4 constants, which don't appear in ecdsa_circuit.py, and the order of the points' affine-coordinates & the scalars representation in base (-3) is different.

1. In secp256k1.cairo, we verify that $Q = u_1G + u_2R$, $G$ being the generator point of the elliptic curve, and $R$ a point from the ECDSA signature (r, s).

• 0:3]: constants
• [4:28]: RLCSumDLogDiv coeffs
• [30:31]: generator point of secp256k1, $G$
• [32:33]: point $R$, from ECDSA signature
• [34:37]: representation in base (-3) of the low part of the scalar $u_1$
• [38:41]: representation in base (-3) of the low part of the scalar $u_2$
• [42:45]: representation in base (-3) of the high part of the scalar $u_1$
• [46:49]: representation in base (-3) of the high part of the scalar $u_2$
• [50:51]: $Q_\text{low}$ point
• [52:53]: $Q_\text{high}$ point
• [54:55]: $Q_\text{high\_shifted}$ point
• [56:57]: random point $A_0$, used in the ECIP protocol
• [58]: The constant $a$ from the Weierstrass formula of the curve
• 59]: base_rlc

2. In ecdsa_circuit.py, it verifies that $Q = k_1P_1 + k_2P_2$:

• 0:25]: RLCSumDLogDiv coeffs
• [26:27]: $P_1$ point (equiv. $G$)
• [28:31]: representation in base (-3) of the low part of the scalar $k_1$ (equiv. $u_1$)
• [32:35]: representation in base (-3) of the high part of the scalar $k_1$
• [36:37]: $P_2$ point (equiv. $R$)
• [38:41] representation in base (-3) of the low part of the scalar $k_2$ (equiv. $u_2$)
• [42:45]: representation in base (-3) of the high part of the scalar $k_2$
• [46:47]: $Q_\text{low}$ point
• [48:49]: $Q_\text{high}$ point
• [50:51]: $Q_\text{high\_shifted}$ point
• [52:53]: random point $A_0$, used in the ECIP protocol
• [54]: The constant $a$ from the Weierstrass formula of the curve
• 55]: base_rlc

Implementation

What has to be implemented?
I've flattened the operations the _run_inner_circuit() function do. (equiv. to verify_ecip() in garaga.

The objective is to assert that $\text{LHS} = \text{RHS}$

• Verify that all the points ($P_1$, $P_2$, and $A_0$) are on the curve

Computing LHS

Compute $\text{LHS} = \text{coeff0} \cdot F(A_0) + \text{coeff2} \cdot F(A_2)$.
Where $F(x, y) = a(x) + yb(x)$, $a, b$ being rational functions.

• Compute the (doubling) slope $m_{A_0}$, and intercept $b_{A_0}$ between $A_0$ and itself
  $m_{A_0} = \frac{(3x_{A_0}^2 + A)}{2y_{A_0}}$
  $b_{A_0} = y_{A_0} - m_{A_0}x_{A_0}$
• Compute $A_2 = -2A_0$
• Compute the slope between $A_0$ and $A_2$
  $m_{A_0A_2} = \frac{y_{A_2} - y_{A_0}}{x_{A_2} - x_{A_0}}$
• Compute $\text{coeff2}$
  $\text{coeff2} = \frac{2y_{A_2}(x_{A_0} - x_{A_2})}{3x_{A_2}^2 + A - 2my_{A_2}}$
• Compute $\text{coeff0} = \text{coeff2} + 2m_{A_0A_2}$
• Compute $F(A_0)$ and $F(A_2)$
  • We use RLCSumDLogDiv to get the log_div_a_num, log_div_a_den, log_div_b_num and log_div_b_den values, which are the numerators/denominators of the rational functions $a(x)$ and $b(x)$ (being polynomials)
  • We evaluate the four polynomials in $A_0$ and $A_2$ (e.g. with Horner's method)

Computing RHS

Compute $\text{RHS} = c_0 \cdot \text{base\_rhs}_\text{low} + c_1 \cdot \text{base\_rhs}_\text{high} + c_2 \cdot \text{base\_rhs}_\text{high\_shifted}$

• Compute $\text{base\_rhs}_\text{low}$
  $\text{base\_rhs}_\text{low} = (x_{A_0} - x_G)\left( \frac{ \text{sp}_{low_{u_1}} \cdot \text{ep}_{low_{u_1}}}{y_{A_0} - (m_{A_0}x_G + b_{A_0})}) - \frac{\text{sn}_{low_{u_1}} \cdot \text{en}_{low_{u_1}}}{y_{A_0} + (m_{A_0}x_G + b_{A_0})}\right) + (x_{A_0} - x_R) \left(\frac{\text{sp}_{low_{u_2}} \cdot \text{ep}_{low_{u_2}}}{y_{A_0} - (m_{A_0}x_R + b_{A_0})} - \frac{\text{sn}_{low_{u_2}} \cdot \text{en}_{low_{u_2}}}{y_{A_0} + (m_{A_0}x_R + b_{A_0})}\right) - \frac{x_{A_0} - x_{Q_{low}}}{y_{A_0} + (m_{A_0}x_Q + b_{A_0})}$
• Compute $\text{base\_rhs}_\text{high}$
  • Use $\text{epns}_{high}, Q_\text{high}$
• Compute $\text{base\_rhs}_\text{high\_shifted}$
  • Use $\text{epns}_{high\_shifted}, Q_\text{high\_shifted}$
• Compute $c_0 = \text{base\_rlc}$
• Compute $c_1 = \text{base\_rlc}^2 = c_0^2$
• Compute $c_2 = \text{base\_rlc}^3 = c_1 \cdot c_0$

Final Check

Verify that $\text{LSH} - \text{RHS} = 0$

[zmalatrax]

The order of the ecip_input is based on the calls to circuit.write, so it's the enps order is actually similar.
I still don't know what are those 4 constants though (and why they are part of the ecip_input)