Try   HackMD

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:

(01011)(8+2+1)=11(01101)(8+41)=11(\colorred1\colorred0\colorred1\colorred0\colorred1)(1641)=11(11101)(168+41)=11(11011)(168+2+1)=11

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=(bn1 bn2    b1 b0)2
  2. Output in NAF form:
    O=(wn wn1    w1 w0)NAF
  3. Initialise iterator:
    i=0
  4. While
    I>0
    do:
    • if
      I10
      //(
      I
      is odd)
      • wi=2(Imod22)
      • I=Iwi
    • else:
      • wi=0
    • II/2
    • i(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
Fr

A scalar

bFr, identified with the corresponding integer in
{0,,r1}
, can be represented in a 2-window Non-adjacent Form (short
w
NAF), i.e.
b=i=0127pi4i
where
pi{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
GG1
, we can use the
w
NAF form to reduce the computation of a scalar multiplication.
bG=(i=0127pi4i)G=p127(4127G)+p126(4126G)++p0G

Now, since every alternate element in the

wNAF 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
pi{1,1}
, we only need to add or subtract the point
(4iG)
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

bis 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

ith wnaf entry we define:
sign[i]=1wnaf[i][32]

Here,
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:
bi={(2(wnaf[i][0])+1),sign[i]=1(2(wnaf[i][0])+1),sign[i]=0,

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{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
beFr
we define:
wnaf_decompose(be):=(wnaf_decompose(be+1),s)=({b127,b126,,b0},s).

(Here the second
wnaf_decompose
funtion is the normal decomposition function described previously.)
In other words, the quad values for an even number
be{0,2,4,,r1}
are actually the quad values which correspond to the next odd number, i.e.
(be+1)
. To recover the input from the quad values for any
b{0,1,2,,r1}
, we define:
b=wnaf_reconstruct({bi}i=0127, s):=(i=0127bi4i)s.

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:

bi={3i{0}{2,3,,126}1i=1273i=1ands=0

We can verify this as:

b=(i=0127bi4i)s=14127+(3)(4126+4125++42)+341+(3)400=141273(1+42++4126)+34=41273(1+4+42++4126)+34+12=41273(412713)+24=25.
We have added this test to verify the above description.

Claim: For field scalars in

Fr, i.e. integers
b{0,,r1}
, the most significant quad will always be
b127=1
.
Proof: We can prove this claim by contradiction. Suppose the most significant quad
b127=3
. In that case, let
b
denote the smallest number we can represent with our
w
NAF form.
b
should have all the remaining quad values to be
3
, i.e.
bi=3
for all
i{0,1,,126}
and
s=1
.

b=(i=0127bi4i)s=341273(1+4+42++4126)1=341273(412713)1=24127+11=2255

Clearly

b>r. Therefore, in the context of field scalars, we can never have the most significant quad
b127=3
. Furthermore, it can neither be
1
or
3
. Let
b
denote the greatest number we can represent with our
w
NAF form when
b127=1
.
b
must have all the remaining quads to be equal to
3
and
s=0
.

b=(i=0127bi4i)s=(1)4127+3(1+4+42++4126)0=4127+3(412713)=1

Since any field scalar

b{0,1,,r1}, it cannot be negative. Hence, for field scalars, we will always have
b127=1
.

Mini example: Let's say

r=5, so your field is
{0,1,2,3,4}
.

hash_single(1)wnaf_reconstruct(1,false)hash_single(2)wnaf_reconstruct(3,true)hash_single(3)wnaf_reconstruct(3,false)hash_single(4)wnaf_reconstruct(0,true)hash_single(0)wnaf_reconstruct(1,true)

For

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 non-adjacent form (NAF,8 − 2 %2B 1 %3D 7) ↩︎

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