ECC multiplication strategies inside PLONK

This document assumes constrained elliptic curve is in SW form with a = 0

Montgomery Ladder

We require lots of sequential double and adding operations in ecc multiplication algorithms. Fortunately we have small but cool optimization trick to calculate P_2 = 2 * P_0 + P_1. Rather than one doubling and one addition we combine two formulas and find a simpler P_2 = P_0 + P_1 + P_0 formula. Below we can calculate the result skipping calculation of y coordinate of intermediate result.

lambda_0 = (y_1 - y_0) / (x_1 - x_0)
x_2 = lambda_0 * lambda_0 - x_0 - x_1
lambda_1 = lambda_0 + 2 * y_0 / (x_2 - x_0)
x_res = lambda_1 * lambda_1 - x_0 - x_2
y_res = lambda_1 * (x_res - x_0) - y_0

Random accumulation initializer

Random accumulation initializer is a point that should allow us to use incomplete formulas. In naive way in doubling we would need such constaints:

def double(P_0):
    cond_is_inf = is_inf(P_0)
    canditate_res = constrain_doubling(P_0)
    return select(cond_is_inf, candidate_res, infinity)

So can we make sure that input point P_0 is not infinity without asserting each time while we constrain doubling?

And in addition it looks like this

def add(P_0, P_1):
    cond_is_inf_0 = is_inf(P_0)
    cond_is_inf_1 = is_inf(P_1)
    cond_is_equal = is_equal(P_0, P_1)
    canditate_res_add = constain_addition(P_0, P_1)
    canditate_res_dou = constrain_doubling(P_0)
    T = select(cond_is_equal, canditate_res_dou, canditate_res_add)
    T = select(cond_is_inf_0, P_1, T)
    T = select(cond_is_inf_1, P_0, T)
    return T

In the intermediate step just before selection we have 5 candidate results! Also we had to apply doubling to stay safe while P_0 == P_1.

Below conditions are ideally what we would like to have that operands satisfies to make formulas much shorter.

• P_0 != 0 and P_1 != 0 to skip infinity checks
• P_0 != P_1 to just constrain addition
• P_0 != -P_1 to avoid result goes to infinity.

And also keep in mind that we are not using an embedded curve ie. base field of the subject elliptic curve is not equal to the scalar field where we constrain equations. Therefore infinity and equality checks becomes more expensive than we would like.

We can just make sure that any public inputs are not point of infinity by simply checking if point is on curve. However this won't guarantee P_0 == P_1 to escape branching in addition since an earlier addition with P_0 = -P_1 operands would produce an infinity inside of the circuit.

Case: Simple double-and-add method.

Let's denote multiplication like R = P * e where e is a scalar and can be decomposed as [b_0, b_1, ...]

def mul(P_0, e):
    
    bits = decompose(e)
    table = [infinity, P_0]
    Acc = select(bits[0], table)
    
    for b in bits[1:]:
        Acc = double(Acc)
        to_add = select(b, table)
        Acc = add(Acc, to_add)
        
    return Acc

In the naive multiplication above in the table we have point of infinity as first entry. Constraints must follow complete formulas even if input point P_0 is guaranteed not to be point of infinity.

So we will use an auxiliary point AuxInit which is fed with public inputs in order to avoid using complete formulas. Then selection table is now [AuxInit, AuxInit + P_0] rather than [infinity, P_0]

AuxInit
AuxFin = AuxInit * ((1 << n) -1)

def mul(P_0, e):
    
    bits = decompose(e)
    table = [AuxInit, P_0 + AuxInit]
    Acc = select(bits[0], table)
    
    for b in bits[1:]:
        Acc = double_incomplete(Acc)
        to_add = select(b, table[0], table[1])
        Acc = add_incomplete(Acc, to_add)
        # or more in optimal way
        # Acc = ladder_incomplete(Acc, select(b, table[0], table[1]))
        
    Acc = Acc - AuxFin
        
    return Acc

So we not only achieved non infinity point initialization but also guaranteed operands in addition will not be equal! It means we don't have to branch for infinity points in the circuit.

This claim must hold only if prover doesn't have an access to AuxInit point before creating the proof.

Sliding window

So we can just precompute (or preconstrain) a wider table to reduce number of iterations in the double-and-add algorithm. While this step introduce more selection steps it will reduce number of additions.

For example wherewindow_size = 2 a scalar e is decomposed as:

bits = [b_0, b_1, ...]

and we window those bits as

windows = [[b_0, b_1], [b_2,b_3], ...]

So selection table will be

table = [0, P_0, 2*P_0, 3*P_0]

Or with auxiliary point

table = [Aux, P_0 + Aux, 2*P_0 + Aux, 3*P_0 + Aux]

• Number of selection size will grow by window_size times.
• Number of addition will be reduced by 1/window_sizetimes.
• And main trade-off is between number of iteration and precomputation cost that grows by 2^window_size. So a sweet window size can be found.

Sliding window technique is cheaper because selection operation is much cheaper than addition operation (even if incomplete addition).

Multi Multiplication

Multi multiplication mostly covers linear combination of points and has some application area for example can be used in recursion circuits or polynomial commitment inside of a circuit.

So we can generalize simple double-and-add algorithm to share the same doubling step across point scalar pairs. We will also use sliding window and auxiliary initial value technique.

pairs = [(P_0, e_0), (P_1, e_1), (P_2, e_2)]

Scalar values decomposed as:

e_0 = [b_0, b_1, ...]
e_1 = [b_0, b_1, ...]
e_2 = [...]

Let's window scalars:

w_0 = [[b_0, b_1], [b_2,b_3], ...]
w_1 = [[b_0, b_1], [b_2,b_3], ...]
w_2 = [...]

AuxGen is random point where DL is unknown that generates aux values for each pair. We should calculate an aux per pair and we have to make it linear independent to use incomplete formulas ie. to avoid a=b in add(a,b) operation. Each pair could have their own independent aux points however we expect this aux point from public input and we also don't want to bloat public input size. So we can still a generator point to make tables independent.

A_0 = AuxGen * 2^0
A_1 = AuxGen * 2^1
A_2 = AuxGen * 2^2

Then we will be able to construct tables as:

table_0 = [A_0, A_0 + P_0, A_0 + 2 * P_0, A_0 + 3 * P_0]
table_1 = [A_1, A_1 + P_1, A_1 + 2 * P_1, A_1 + 3 * P_1]
table_2 = [...]