Example: Fixed-base scalar multiplication

The NAF scalar representation

We assume our scalar ss is in the range {1,..,M}\{1,..,M\} for MM smaller than half the elliptic curve group order having the form 24n12\cdot 4^n -1 for some integer nn . (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+i=0n1bi4is = t +\sum_{i=0}^{n-1}b_i\cdot 4^i , where bi{3,1,1,3}b_i\in \{-3,-1,1,3\}, and t{4n,4n+1}t\in \{4^n,4^n+1\}. Thus, we think of our input as consisting of nn input quads {bi}\{b_i\} and one input bit tt.

Our program consists of nn rounds where in round ii, we add either 3[gi],1[gi],1[gi],3[gi]-3[g_i], -1[g_i], 1[g_i], 3[g_i], where gi=4ni[g]g_i = 4^{n-i}[g]is a precomputed power of our actual generator. We initialize our sum as t[g]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 sswas used). We define the intermediate sums as follows: a0=t/4n,a1=t/4n1+bn1a_0=t/4^n, a_1 =t/4^{n-1} + b_{n-1} , and for i{2,,n}i \in \{2,\ldots,n\} ai=4ai1+bnia_i = 4\cdot {a_{i-1}} + b_{n-i} . Induction shows we get an=sa_{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 xx coordinate of the point we want to select only depends on the magnitude on 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 (x1,y1,xα,ai1),(x2,y2,xα,2,ai)(x_1,y_1,x_\alpha,a_{i-1}),(x_2,y_2,x_{\alpha,2},a_i), checks that (x2,y2)=(x1,y1)+(ai4ai1)[gi](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[n]i\in [n] and denote gi=(xβ,yβ),3[gi]=(xγ,yγ)g_i=(x_\beta,y_\beta), 3[g_i] = (x_\gamma,y_\gamma). Let's also denote by (xα,yα)(x_\alpha,y_\alpha) the point we wish to add in this round according to the input; thus (xα,yα)(x_\alpha,y_\alpha)is one of the points in the set{(xβ,yβ),(xβ,yβ),(xγ,yγ),(xγ,yγ)}\{(x_\beta,y_\beta), (x_\beta,-y_\beta),(x_\gamma,y_\gamma), (x_\gamma, -y_\gamma)\}. We can recover xαx_{\alpha} via the following relationship:

(ai4ai1)298xβ+(ai4ai1)218xγ=xα(ai4ai1)2xγxβ8+9xβxγ8=xα\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:

qxα,1=xγxβ8,qxα,2=9xβxγ8(ai4ai1)2qxα,1+qxα,2=xα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αx_\alphaas a distinct wire value, we can extract the y-coordinate, yαy_\alpha, using a cubic polynomial identity

(xαxγ)(ai4ai1)(xβxγ)yβ+(xαxβ)(ai4ai1)3(xγxβ)yγ=yα(xα3yβyγ3(xβxγ)+xβyγxγyβ3(xβxγ))(ai4ai1)=yα\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 - x_\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

qyα,1=3yβyγ3(xβxγ),qyα,2=xβyγxγyβ3(xβxγ)(xαqyα,1+qyα,2)(ai4ai1)=yα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 - x_\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α2y_\alpha^2 by computing xα3+bcurvex_\alpha^3 +b_{curve}, where bcurveb_{curve}is a constant that describes the short weierstrass curve in question (for our BN254 embedded curve, bcurve=17b_{curve} = -17)

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

(ai4ai1+3)(ai4ai1+1)(ai4ai11)(ai4ai13)=0(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 hand repeated xx coordinate. To add point (x1,y1)(x_1, y_1)with point (xα,yα)(x_\alpha, y_\alpha), to obtain output (x2,y2)(x_2, y_2), the formula is:

x2=(yαy1xαx1)2xαx1y2=(yαy1xαx1)(x1x2)y1x_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

(x2+xα+x1)(xαx1)2(yαy1)2=0(y2+y1)(xαx1)(yαy1)(x1x2)=0\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

(x2+x1+xα)(xαx1)2+2(ai4ai1)(xαqyα,1+qyα,2)y1y12bcurve=0(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

(y2+y1)(xαx1)((ai4ai1)(xαqyα,1+qyα,2)y1)(x1x2)=0(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" (x0,y0)(x_0,y_0) as either (4n)[g](4^n)[g] or (4n+1)[g](4^n +1)[g], according to whether the value of a0a_0 is 11 or 1+1/4n1 + 1/4^n .We also check that a0a_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 xi,yi,xα,ax_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.

(x0y0xα,0a0x1y1xα,1a1xnynxα,nan)\begin{pmatrix} x_0 & y_0 & x_{\alpha,0} & a_0 \\ x_1 & y_1 & x_{\alpha,1} & a_1 \\ \vdots & \vdots & \vdots & \vdots \\ x_n & y_n & x_{\alpha,n} & a_n \end{pmatrix}