Example: Fixed-base scalar multiplication

The NAF scalar representation

We assume our scalar $s$ is in the range $\{1,..,M\}$ for $M$ smaller than half the elliptic curve group order having the form $2\cdot 4^n -1$ for some integer $n$ . (Allowing a general scalar requires some additional work which we omit here for simplicity of presentation.) When s is in this range, we can write $s = t +\sum_{i=0}^{n-1}b_i\cdot 4^i$ , where $b_i\in \{-3,-1,1,3\}$, and $t\in \{4^n,4^n+1\}$. Thus, we think of our input as consisting of $n$ input quads $\{b_i\}$ and one input bit $t$.

Our program consists of $n$ rounds where in round $i$, we add either $-3[g_i], -1[g_i], 1[g_i], 3[g_i]$, where $g_i = 4^{n-i}[g]$is a precomputed power of our actual generator. We initialize our sum as $t [g]$. An optimization we use to reduce program width, is that we only explicitly represent "intermediate sums" of our scalar, and not the actual input quads (the intermediate sums are more convenient than the quads in checking the correct scalar $s$was used). We define the intermediate sums as follows: $a_0=t/4^n, a_1 =t/4^{n-1} + b_{n-1}$ , and for $i \in \{2,\ldots,n\}$ $a_i = 4\cdot {a_{i-1}} + b_{n-i}$ . Induction shows we get $a_{n} = s$.

Another optimization we use is that by squaring the difference of two intermediate sums, we cancel the effect of the sign of the input quad, which is useful since the $x$ coordinate of the point we want to select only depends on the magnitude of the difference. (And needing to explicitly represent this magnitude would again increase the width of the final program.)

2-bit NAF addition gate

We describe a width 4 program that given row values $(x_1,y_1,x_\alpha,a_{i-1}),(x_2,y_2,x_{\alpha,2},a_i)$, checks that $(x_2,y_2) = (x_1,y_1) + (a_i - 4 a_{i-1})[g_i]$ .

Selecting the correct point to add

The first step is to use a variant of the lookup method from the previous section to choose the coordinates of the correct point out to add in a given round.

Let's focus on a specific round $i\in [n]$ and denote $g_i=(x_\beta,y_\beta), 3[g_i] = (x_\gamma,y_\gamma)$. Let's also denote by $(x_\alpha,y_\alpha)$ the point we wish to add in this round according to the input; thus $(x_\alpha,y_\alpha)$is one of the points in the set$\{(x_\beta,y_\beta), (x_\beta,-y_\beta),(x_\gamma,y_\gamma), (x_\gamma, -y_\gamma)\}$. We can recover $x_{\alpha}$ via the following relationship:

$$\frac{(a_{i}-4a_{i-1})^2 - 9}{-8}x_\beta + \frac{(a_{i} - 4a_{i-1})^2 - 1}{8}x_{\gamma} = x_\alpha \\ \implies(a_{i}-4a_{i-1})^2\frac{x_\gamma-x_\beta}{8} + \frac{9x_\beta - x_\gamma}{8} = x_\alpha$$

We can represent the precomputed constants by selectors:

$$q_{x_{\alpha, 1}}=\frac{x_\gamma-x_\beta}{8} \quad, \quad q_{x_{\alpha, 2}}=\frac{9x_\beta - x_\gamma}{8} \\ \implies (a_{i} - 4a_{i-1})^2q_{x_{\alpha, 1}} + q_{x_{\alpha, 2}} = x_\alpha$$

By storing $x_\alpha$as a distinct wire value, we can extract the y-coordinate, $y_\alpha$, using a cubic polynomial identity

$$\frac{(x_\alpha-x_\gamma)(a_{i} - 4a_{i-1})}{(x_\beta - x_\gamma)}y_\beta+ \frac{(x_\alpha - x_\beta)(a_{i}-4a_{i-1})}{3(x_\gamma - x_\beta)}y_\gamma = y_\alpha \\ \implies \bigg(x_\alpha\frac{3y_\beta - y_\gamma}{3(x_\beta - x_\gamma)} + \frac{x_\beta y_\gamma - 3x_\gamma y_\beta}{3(x_\beta - x_\gamma)} \bigg)(a_{i}-4a_{i-1}) = y_\alpha$$

We can also represent this via two precomputed selectors

$$q_{y_{\alpha, 1}} = \frac{3y_\beta - y_\gamma}{3(x_\beta - x_\gamma)} \quad , \quad q_{y_{\alpha, 2}} = \frac{x_\beta y_\gamma - 3x_\gamma y_\beta}{3(x_\beta - x_\gamma)} \\ \implies (x_\alpha q_{y_{\alpha, 1}} + q_{y_{\alpha, 2}})(a_{i}-4a_{i-1}) = y_\alpha$$

We can recover $y_\alpha^2$ by computing $x_\alpha^3 +b_{curve}$, where $b_{curve}$is a constant that describes the short weierstrass curve in question (for our BN254 embedded curve, $b_{curve} = -17$)

Finally, we also check that the differences of intermediate sums fall within the prescribed range via the equation

$$(a_i - 4a_{i-1} + 3)(a_i - 4a_{i-1} +1)(a_i - 4a_{i-1} -1)(a_i - 4a_{i-1} -3) = 0$$

We've seen how to select the correct point to add in a given round, let's now see how to actually add it.

Adding the selected point

As we are adding in each round powers of disjoint magnitude of our generator, we can use an incomplete affine addition formula that doesn't handle repeated $x$ coordinate. To add point $(x_1, y_1)$with point $(x_\alpha, y_\alpha)$, to obtain output $(x_2, y_2)$, the formula is:

$$x_2 = \big(\frac{y_{\alpha} - y_1}{x_{\alpha} - x_1}\big)^2 - x_\alpha - x_1 \\ \\ y_2 = \big(\frac{y_{\alpha} - y_1}{x_{\alpha} - x_1}\big)\big(x_1 - x_2\big) - y_1$$

Expressed as an identity we can evaluate via a gate, we have

$$\big(x_2 + x_\alpha + x_1\big)\big(x_\alpha - x_1\big)^2-\big(y_\alpha - y_1\big)^2 = 0 \\ \\ \big(y_2 + y_1 \big)\big(x_\alpha - x_1 \big) - \big(y_\alpha - y_1 \big)\big(x_1 - x_2 \big) = 0$$

Affine addition using precomputed selectors

x-coordinate check

$$(x_2 + x_1 + x_\alpha)(x_\alpha - x_1)^2 \\ + 2(a_i - 4a_{i-1})(x_\alpha q_{y_{\alpha, 1}} + q_{y_{\alpha, 2}})y_1 \\ -y_1^2 - b_{curve} = 0$$

y-coordinate check

$$(y_2 + y_1)(x_\alpha - x_1) - ((a_i - 4a_{i-1})(x_\alpha q_{y_{\alpha, 1}} + q_{y_{\alpha, 2}}) - y_1)(x_1 - x_2) = 0$$

Initialization gate

What is left to do is to add the "offset" t. We do this by initializing the "starting point" $(x_0,y_0)$ as either $(4^n)[g]$ or $(4^n +1)[g]$, according to whether the value of $a_0$ is $1$ or $1 + 1/4^n$ .We also check that $a_0$ is in this range using the corresponding degree two constraint.

The Final Program

We summarize the ideas above and describe the program. We will have n+1 rows each containing values labeled $x_i, y_i,x_{\alpha}, a$. The 2-bit NAF addition gate will be active on the first n rows.In the first row the initialization gate will also be active.

$$\begin{pmatrix} x_0 & y_0 & - & a_0 \\ x_1 & y_1 & x_{\alpha,0} & a_1 \\ \vdots & \vdots & \vdots & \vdots \\ x_n & y_n & x_{\alpha,n-1} & a_n \end{pmatrix}$$