Batch-Affine Addition

Problem

Given two sets of EC points $\{P_i\}$ and $\{Q_ i \}$, $i \in \{1,..,n\}$, calculate $\{R_i = P_i + Q_i\}$.

Affine Addition

If $P = (x_p, y_p)$, $Q=(x_q, y_q)$, and $R = P + Q = (x_r, y_r)$, an addition operation on an elliptic curve in short Weierstrass form $y^2 = x^3 + ax + b$ is defined as below:

$$k = \begin{cases} \frac{y_Q - y_P}{x_Q - x_P} &\text{if } P\not=\pm Q \\ \frac{3x_P^2+a}{2y_P} &\text{if }P=Q \end{cases}\\ x_R=k^2-x_P-x_Q\\ y_R=k(x_P-x_R)-y_P$$

We observe that each addition requires an inversion operation. In finite fields, computing an inverses is expensive and requires Extended Euclidean Theorem. Multiplicative inversions are on the order of 100x more expensive than a multiplication. As a result, no one uses (unbatched) affine point arithmetic in standard operation. Addition in projective coordinates are commonly used instead.

Batch-Affine Addition

Point addition becomes different when independently adding many points. In that case we may use only 1 inversion for all point additions.

Consider $n$ pairs of points:

$$P_i = (x_{P_i}, y_{P_i}), Q_i = (x_{Q_i}, y_{Q_i}), i \in \{1,...,n\}$$

We want to calculate:

$$R_i = P_i + Q_i = (x_{R_i}, y_{R_i})$$

Let's denote:

$$\lambda_i = x_{Q_i} − x_{P_i}$$

The product of all $\lambda$s left to $\lambda_i$ yields:

$$L_i = \prod_{j=1}^{i-1} \lambda_j$$

Then, the product of all $\lambda$s right to $\lambda_i$ is:

$$R_i = \prod_{j=i+1}^{n} \lambda_j$$

Let's also denote:

$$\lambda_{inv} = (\prod_{j=1}^{n} \lambda_j)^{-1}$$

With the results above, we can calculate inversion as the following:

$$\frac{1}{x_{Q_i} − x_{P_i}} = \frac{1}{\lambda_i} = \frac{L_i R_i}{\prod_i \lambda_i} = L_iR_i\lambda_{inv}$$

Since $\lambda_{inv}$can be precomputed, the same inversion result can be shared across all pairs of points.

Therefore, we reduced the number of inversions required to calculate $n$ additions from $n$ to $1$. In total, computing the affine addition of $n$ distinct pairs requires 1 division, 5*n multiplications, n squarings, and 6*n additions on finite fields.

Sage example:

# BN254
Fq = GF("21888242871839275222246405745257275088696311157297823662689037894645226208583")
E = EllipticCurve(Fq,[0,3])

def batch_add(lhs, rhs):
    assert(len(lhs) == len(rhs))
    n = len(lhs)
    
    lambdas = [Fq(0) for k in range(0, n)]
    Ls = [E(0) for k in range(0, n)]
    lambda_acc = Fq(1)
    for i in range(0, n):
        lambdas[i] = rhs[i][0] - lhs[i][0]
        Ls[i] = lambda_acc
        lambda_acc *= lambdas[i]
    lambda_inv = lambda_acc.inverse_of_unit()
    
    result = [E(0) for k in range(0, n)]
    lambda_inv_times_R_i = lambda_inv
    for i in range(n-1, -1, -1):
        k = Ls[i] * lambda_inv_times_R_i * (rhs[i][1] - lhs[i][1])
        lambda_inv_times_R_i *= lambdas[i]
        
        x = k * k - rhs[i][0] - lhs[i][0]
        y = k * (lhs[i][0] - x) - lhs[i][1]
        result[i] = E(x,y)
    return result
    
def naive_add(lhs, rhs):
    assert(len(lhs) == len(rhs))
    n = len(lhs)
    
    result = []
    for i in range(0, n):
        result.append(lhs[i] + rhs[i])
    return result
    
n = 2**10
p = [E.random_element() for k in range(0, 16)]
q = [E.random_element() for k in range(0, 16)]
batch_add(p, q) == naive_add(p, q)