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

We explain in this post how to think about and leverage the type of arithmetization used in PLONK. In its most general form, we refer to such an arithmetization as a Randomized Air with Preprocessing, RAP for short. However, in practice it will usually be convenient to work with restricted cases of RAPs, that we call turbo-Plonk and ultra-Plonk programs. We will explain all these terms!

5/15/2024Contracts: https://github.com/shuklaayush/aztec-token-partition-tableFrontend: https://github.com/shuklaayush/aztec-token-pt-frontendCommentSuggest edit

4/29/2024#[aztec(private)]fn add_rand(b: Field) -> Field {rand() + b}#[test]unconstrained fn test_add_rand() {OracleMock::mock(“getRandomField”).returns(3).times(2);let priv_circ_pub_inputs = add_rand(PrivateContextInputs::empty(), 2);assert(2.lt(priv_circ_pub_inputs.return_values[0]), “Is not less than!!”);}

3/26/2024recursive proof composition for the lazy bastards

3/15/2024
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up