Liam Eagen's Elliptic curve inner product

This is a summary of [Ea22]. I will follow the notations from the previous post. Let's think about the prover has elliptic curve points $P_i\in E(\mathbb{F})$, and wants to prove that $\sum _{i=0}^n{P}_i=O$. To achieve effectiveness, the paper uses the function field and the Weil reciprocity.

First, the prover prepares a divisor witness $f\in \mathbb{F}$ such that

$$\mathrm{div}(f)=\sum _{i=0}^{n-1}[P_i]-n[O]\in \mathrm{Div}(E).$$

Such $f$ exists because $\sum P_i=O$ as mentioned in the previous post. Such $f$ can be constructed efficiently by Euclidean algorithm or other methods. The output will be $f=a(x)-yb(x)$ for polynomials $a,b$ whose degrees are less than $n/2$. I will explain this later. Now, the prover commits $f$ and $P_i$. Then, the verifier chooses a random line

$$l=y-\lambda x-\mu \in \mathbb{F}(E)$$

in the function field whose intersection with $E$ is contained in rational points $E({\mathbb{F}}_q)$, and assume this line does not have zero at the point of infinity $O$. Alternatively, this can be done by choosing two points $A_0,A_1\in E({\mathbb{F}}_q)$ such that $A_0\ne \pm A_1$. Then, the line through $A_0$ and $A_1$ will be the random challenge. The line intersects with another point $A_2\in E(\mathbb{F})$ and it is automatically a rational point.

By the Weil reciprocity for $f$ and $l$,

$$D(A_0)D(A_1)D(A_2)=\prod _{i=0}^{n-1}l(P_i)$$

With some technical condition, log derivative with respect to$\mu$ yields

$$\sum _{i=0}^2\frac{f^{\prime }(A_i)}{f(A_i)}\frac{dx(A_i)}{d\mu }=\sum _{i=0}^{n-1}\frac{1}{l(P_i)}$$

where $f^{\prime }=\frac{d}{dx}f$ and $x(A_i)$ is a polynomial which maps $(\lambda ,\mu )$ to $x$-coordinate of $A_i$. The prover can make an arithmetic circuit with this equation instead of $\sum P_i=O$.

Higher multiplicity challenge

Instead of choosing distinct $A_0,A_1,A_2$ as a challenge, the verifier can choose $A_0=A_1\ne A_2$. That is, $l$ is the tangent line at $A_0$. Similarly, log derivative of the Weil reciprocity induces

$$-(c+2\lambda )\frac{f^{\prime }(A_0)}{f(A_0)}+c\frac{f^{\prime }(A_2)}{f(A_2)}=\sum _{i=0}^{n-1}\frac{x(A_0)-x(P_i)}{l(P_i)}$$

where

$$c=\frac{2y(A_2)(x(A_0)-x(A_2))}{3x(A_2{)}^2+A_0-2\lambda y(A_2)}$$

and $x(P)$ and $y(P)$ are $x$ and $y$-coordinate of elliptic curve points. This higher multiplicity challenge will reduce the number of multiplications in an arithmetic circuit and the length of the challenge. 

To prove $\sum P_i=O$ by sending all the points, the arithmetic circuit needs to implement $n-1$ elliptic curve additions, which requires $14(n-1)$ field multiplications in general. But for higher multiplicity challenges, the circuit requires only $n+1$ multiplications while it needs more commitments.

Inner product version

Now, let's reduce more if there is a lot of repetition of points. That is, the prover wants to show

$$\sum _{i=0}^{n-1}{e}_i{P}_i=Q.$$

First, calculate $(-3)$-adic representation of $e_i$. We have unique $d_{ij}\in \{-1,0,1\}$ such that

$$e_i=\sum _{j=0}^l{d}_{ij}(-3{)}^j$$

and divide $e_i$ into $a_i$ and $b_i$ such that $e_i=a_i-b_i$, namely,

$$a_i=\sum _{j=0}^l\frac{|d_{ij}|+d_{ij}}{2}(-3{)}^j,b_i=\sum _{j=0}^l\frac{|d_{ij}|-d_{ij}}{2}(-3{)}^j$$

From here, all the summations without range run over $0\le i\le n-1$. Define

$$\begin{array}{rl}{Q}_{l-1}& =\sum d_{i,l-1}{P}_i\\ Q_{l-2}& =\sum (d_{i,l-1}(-3)+d_{i,l-2})P_i\\ Q_{l-3}& =\sum (d_{i,l-1}(-3{)}^2+d_{i,l-2}(-3)+d_{i,l-3})P_i\\ ⋮\\ Q_1& =\sum (d_{i,l-1}(-3{)}^{l-2}+\cdots +d_{i,1})P_i\\ Q_0& =\sum e_i{P}_i=Q\end{array}$$

Then, choose $f_j\in \mathbb{F}(E)$ such that

$$\begin{array}{rl}\mathrm{div}(f_{l-1})& =\sum [d_{i,l-1}{P}_i]+[-Q_{l-1}]-N_{l-1}[O]\\ \mathrm{div}(f_{l-2})& =\sum [d_{i,l-2}{P}_i]+[-Q_{l-2}]+3[-Q_{l-1}]-N_{l-2}[O]\\ \mathrm{div}(f_{l-3})& =\sum [d_{i,l-3}{P}_i]+[-Q_{l-3}]+3[-Q_{l-2}]-N_{l-3}[O]\\ ⋮\\ \mathrm{div}(f_1)& =\sum [d_{i,1}{P}_i]+[-Q_1]+3[-Q_2]-N_1[O]\\ \mathrm{div}(f_0)& =\sum [d_{i,0}{P}_i]+[-Q]+3[-Q_1]-N_0[O]\end{array}$$

for some $N_j\in \mathbb{N}$ which makes $\mathrm{div}\in {\mathrm{Div}}_0(E)$. Then, we have

$$\mathrm{div}(f_0{f}_1^{(-3)}\cdots f_{l-1}^{(-3{)}^{l-1}})=[-Q]+\sum a_i[P_i]+b_i[-P_i]-N[O]$$

By the previous log derivations on the Weil reciprocity for $f_0{f}_1^{(-3)}\cdots f_{l-1}^{(-3{)}^{l-1}}$, we have

$$\sum _{j=0}^{l-1}(-3{)}^j\sum _{i=0}^2\frac{f_j^{\prime }(A_i)}{f_j(A_i)}\frac{dx(A_i)}{d\mu }=T(-Q)+\sum _{i=0}^{n-1}{a}_{i}T(P_i)+b_{i}T(-P_i)$$

where

$$T(P)=\frac{1}{l(P)}\{\begin{array}{}1& \text{if }{A}_0\ne A_1\\ x(A_0)-x(P)& \text{if }{A}_0=A_1\end{array}$$