---
header-includes:
- \usepackage[ruled,vlined,linesnumbered]{algorithm2e}
---

# $w$NAF in Barretenberg
**Disclaimer:** This documentation was written on April, 2022. It is intended to give readers a high-level understanding. The codebase is the canonical source of truth, and over time this document might fall behind the implementation details of the code.
###### tags: `audit`
###### Authors: `Suyash, Arijit`

## NAF Representation

The non-adjacent form (NAF)[^1] of a number is a unique signed-digit representation, in which non-zero values are non-adjacent. For example:
$$
\begin{matrix}
(0 & 1 & 0 & 1 & 1) & \equiv & (8+2+1)=11 \\
(0 & 1 & 1 & 0 & -1) & \equiv & (8+4-1)=11 \\
(\color{red}{1} & \color{red}{0} & \color{red}{-1} & \color{red}{0} & \color{red}{-1}) & \equiv & (16-4-1)=11 \\
(1 & -1 & 1 & 0 & -1) & \equiv & (16-8+4-1)=11 \\
(1 & -1 & 0 & 1 & 1) & \equiv & (16-8+2+1)=11 \\
\end{matrix}
$$

The third representation (in red) of $11$ is the only NAF form in the five possible representations. For regular binary representations of numbers, half of all bits will be non-zero, on average, but with NAF this drops to only one-third of all digits. This is very useful when performing scalar multiplication in Elliptic Curve Cryptography. The following is an example algorithm to compute a NAF form.

1. Input in binary form: $I = (b_{n-1} \ b_{n-2} \ \ \dots \ \ b_1 \ b_0)_2$
2. Output in NAF form: $O = (w_{n} \ w_{n-1} \ \ \dots \ \ w_1 \ w_0)_{\text{NAF}}$
3. Initialise iterator: $i=0$
4. While $I > 0$ do:
- if $I \wedge 1 \neq 0$ //($I$ is odd)
- $w_i = 2 − (I \bmod 2^2)$
- $I = I − w_i$
- else:
- $w_i = 0$
- $I \leftarrow I/2$
- $i \leftarrow (i+1)$
5. Return $O$.

In the above discussion, we considered the integers $\{-1,0,1\}$ to be used in the non-adjacent form. This is referred to as a 2-bit windowed NAF form. It is possible to increase the window size so as to reduce the number of non-zero entries in the NAF form. We call this as a windowed non-adjacent form ($w$NAF).

## wNAF Representation of Scalars in $\mathbb{F}_r$

A scalar $b \in \mathbb{F}_r$, identified with the corresponding integer in $\{0,\ldots,r-1\}$, can be represented in a 2-window Non-adjacent Form (short $w$NAF), i.e. $b = \sum_{i = 0}^{127} p_i \cdot 4^{i}$ where $p_i \in \{-1,0,1\}$ are quad values. Note that for a 256-bit number, we'll have 128 quads. When the scalar $b$ is to be multiplied to a generator $G \in \mathbb{G}_1$, we can use the $w$NAF form to reduce the computation of a scalar multiplication.
$$
bG = \left(\sum_{i = 0}^{127} p_i \cdot 4^{i}\right)G = p_{127}(4^{127}G) + p_{126}(4^{126}G) + \dots + p_0G
$$

Now, since every alternate element in the $w$NAF form would be $0$, the terms corresponding to those quads can be ignored in the final sum. Further, depending on the sign of the quads when $p_i \in \{-1,1\}$, we only need to add or subtract the point $(4^{i}G)$ from the accumulated sum. This enables efficient scalar multiplication.

However, there is an issue while using this technique in Aztec circuits. For the quads which are $0$, we need conditional circuit logic to ensure that those terms are not considered in the accumulated sum. Such conditional logic costs a lot of gates, nullifying the benefits of $w$NAF form in scalar multiplication.

To address this, we do the following modification.
**Implementation in Aztec**
Instead of choosing quads from the set $\{1,0,-1\}$, we choose the quads from the set $\{-3,-1,1,3\}$, hence avoiding the 0 value.

In the code [^2][^3], each wnaf entry (from which the quad values $b_i$s are derived) is represented by a 64 bits unsigned integer, of which the least significant 31 bits represent its value and the 32nd bit represents its sign. The most significant 32 bits in a quad value represent a point-index which is used in Pippenger's algorithm. Note, with 31 bits we can support window size much higher than 2 if required in future.

For the $i$th wnaf entry we define:
$$
\textsf{sign}[i]=1 - \textsf{wnaf}[i][32]
$$
Here, $\textsf{wnaf}$ represents an array of 64 bits unsigned integers containing all the wnaf entries.

We map the least significant 32 bits in a wnaf entry to quad values in the set $\{-3,-1,1,3\}$ as:
$$
b_i =
\begin{cases}
(2(\textsf{wnaf}[i][0]) + 1), & \textsf{sign}[i] = 1 \\
-(2(\textsf{wnaf}[i][0]) + 1), & \textsf{sign}[i] = 0,
\end{cases}
$$

It is important to note that since the quad values are in $\{-3,-1,1,3\}$, we can only encode odd numbers with this representation. To represent even numbers, we use a flag called `skew` $s \in \{0,1\}$. $s$ is 1, if the input is even (**including input zero**). The skew $s=0$ if the input is odd. For an even number $b_e \in \mathbb{F}_r$ we define:
$$
\begin{aligned}
\textsf{wnaf_decompose}(b_e) := (\textsf{wnaf_decompose}(b_e+1),s) = (\{b_{127}, b_{126}, \dots, b_0\},s).
\end{aligned}
$$
(Here the second $\textsf{wnaf_decompose}$ funtion is the normal decomposition function described previously.)
In other words, the quad values for an even number $b_e \in \{0,2,4, \dots, r-1\}$ are actually the quad values which correspond to the next odd number, i.e. $(b_e+1)$. To recover the input from the quad values for any $b \in \{0,1,2, \dots, r-1\}$, we define:
$$
\begin{aligned}
b = \textsf{wnaf_reconstruct}\Big(\{b_i\}_{i=0}^{127}, \ s\Big) := \left(\sum_{i=0}^{127}b_i4^i\right) - s.
\end{aligned}
$$
Hence for odd numbers, the quad values represent the original input and we get back the input using the original reconstruction formula because $s=0$ in this case. For even numbers, the quad values represent the next odd number. To get back the original input, we subtract $s=1$ in the reconstruction formula.
**Example**: The $w$NAF form of $b=25$ would be:

$$
b_i =
\begin{cases}
-3 & i \in \{0\} \cup \{2,3,\dots, 126\} \\
1 & i=127 \\
3 & i=1
\end{cases}
\quad \text{and} \quad
s=0
$$

We can verify this as:
$$
\begin{aligned}
b &= \left(\sum_{i=0}^{127}b_i4^i\right) - s\\
&= 1\cdot 4^{127} + (-3)(4^{126} + 4^{125} + \dots + 4^{2}) + 3\cdot 4^1 + (-3)\cdot 4^0 - 0 \\
&= 1\cdot 4^{127} - 3(1 + 4^2 + \dots + 4^{126}) + 3\cdot 4 \\
&= 4^{127} - 3(1 + 4 + 4^2 + \dots + 4^{126}) + 3\cdot 4 + 12 \\
&= 4^{127} - 3 \left(\frac{4^{127}-1}{3}\right) + 24 \\
&= 25.
\end{aligned}
$$
We have added this [test](https://github.com/AztecProtocol/aztec2-internal/pull/692/commits/22fcf7170d3a7c3ec0c93a98c7c208610e8e2d60#diff-de28cddd3919beb5b29d37fefa782fb6ed0477a32650aa8c4cae85c26c9f8855) to verify the above description.
:::info
**Claim**: For field scalars in $\mathbb{F}_r$, i.e. integers $b\in\{0,\ldots,r-1\}$, the most significant quad will always be $b_{127}=1$.
**Proof**: We can prove this claim by contradiction. Suppose the most significant quad $b_{127}=3$. In that case, let $b^{\ast}$ denote the smallest number we can represent with our $w$NAF form. $b^{\ast}$ should have all the remaining quad values to be $-3$, i.e. $b_i = -3$ for all $i \in \{0,1,\dots, 126\}$ and $s=1$.

$$
\begin{aligned}
b^{\ast} &= \left(\sum_{i=0}^{127}b_i4^i\right) - s \\
&= 3\cdot 4^{127} - 3(1 + 4 + 4^2 + \dots + 4^{126}) - 1 \\
&= 3\cdot 4^{127} - 3\left(\frac{4^{127}-1}{3}\right) -1 \\
&= 2\cdot 4^{127} + 1-1 \\
&= 2^{255}
\end{aligned}
$$

Clearly $b^{\ast} > r$. Therefore, in the context of field scalars, we can never have the most significant quad $b_{127}=3$. Furthermore, it can neither be $-1$ or $-3$. Let $b^{\dagger}$ denote the greatest number we can represent with our $w$NAF form when $b_{127}=-1$. $b^{\dagger}$ must have all the remaining quads to be equal to $3$ and $s=0$.

$$
\begin{aligned}
b^{\dagger} &= \left(\sum_{i=0}^{127}b_i4^i\right) - s \\
&= (-1)\cdot 4^{127} + 3(1 + 4 + 4^2 + \dots + 4^{126}) - 0 \\
&= -4^{127} + 3\left(\frac{4^{127}-1}{3}\right) \\
&= -1
\end{aligned}
$$

Since any field scalar $b \in \{0,1,\dots, r-1\}$, it cannot be negative. Hence, for field scalars, we will always have $b_{127}=1$. $\blacksquare$
:::

:::success
**Mini example**: Let's say $r=5$, so your field is $\{0,1,2,3,4\}$.

$$
\begin{aligned}
\textsf{hash_single}(1) &\equiv \textsf{wnaf_reconstruct}(1, \text{false}) \\
\textsf{hash_single}(2) &\equiv \textsf{wnaf_reconstruct}(3, \text{true}) \\
\textsf{hash_single}(3) &\equiv \textsf{wnaf_reconstruct}(3, \text{false}) \\
\textsf{hash_single}(4) &\equiv \textsf{wnaf_reconstruct}(0, \text{true}) \\
\textsf{hash_single}(0) &\equiv \textsf{wnaf_reconstruct}(1, \text{true})
\end{aligned}
$$

For $\textsf{hash_single}(2)$, we compute the wNAF of the next odd 3. We then substract 1 since the `skew` is true. The other calculations are done similarly.

:::

[^1]: Non-Adjacent Form, Wikipedia: Link: https://en.wikipedia.org/wiki/Non-adjacent_form#:~:text=The%20non%2Dadjacent%20form%20(NAF,8%20%E2%88%92%202%20%2B%201%20%3D%207)
[^2]: bitcoin-core/secp256k1, Link: https://github.com/bitcoin-core/secp256k1/blob/master/src/ecmult_impl.h
[^3]: barretenberg, Link: https://github.com/AztecProtocol/barretenberg/blob/master/barretenberg/src/aztec/ecc/groups/wnaf.hpp