--- 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