Tự động cập nhật và thu tiền lời sau mỗi lần cược và tài khoản KING33 AXNHD1 hay trên hd1 đã liên kết làm mô Agribank
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:
The third representation (in red) of 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.
Input in binary form:
Output in NAF form:
Initialise iterator:
While do:
if //( is odd)
else:
Return .
In the above discussion, we considered the integers 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 (NAF).
wNAF Representation of Scalars in
A scalar , identified with the corresponding integer in , can be represented in a 2-window Non-adjacent Form (short NAF), i.e. where are quad values. Note that for a 256-bit number, we'll have 128 quads. When the scalar is to be multiplied to a generator , we can use the NAF form to reduce the computation of a scalar multiplication.
Now, since every alternate element in the NAF form would be , the terms corresponding to those quads can be ignored in the final sum. Further, depending on the sign of the quads when , we only need to add or subtract the point 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 , 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 NAF form in scalar multiplication.
To address this, we do the following modification. Implementation in Aztec Instead of choosing quads from the set , we choose the quads from the set , hence avoiding the 0 value.
In the code [2][3], each wnaf entry (from which the quad values 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 th wnaf entry we define: Here, 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 as:
It is important to note that since the quad values are in , we can only encode odd numbers with this representation. To represent even numbers, we use a flag called skew. is 1, if the input is even (including input zero). The skew if the input is odd. For an even number we define: (Here the second funtion is the normal decomposition function described previously.) In other words, the quad values for an even number are actually the quad values which correspond to the next odd number, i.e. . To recover the input from the quad values for any , we define: Hence for odd numbers, the quad values represent the original input and we get back the input using the original reconstruction formula because in this case. For even numbers, the quad values represent the next odd number. To get back the original input, we subtract in the reconstruction formula. Example: The NAF form of would be:
We can verify this as: We have added this test to verify the above description.
Claim: For field scalars in , i.e. integers , the most significant quad will always be . Proof: We can prove this claim by contradiction. Suppose the most significant quad . In that case, let denote the smallest number we can represent with our NAF form. should have all the remaining quad values to be , i.e. for all and .
Clearly . Therefore, in the context of field scalars, we can never have the most significant quad . Furthermore, it can neither be or . Let denote the greatest number we can represent with our NAF form when . must have all the remaining quads to be equal to and .
Since any field scalar , it cannot be negative. Hence, for field scalars, we will always have .
Mini example: Let's say , so your field is .
For , we compute the wNAF of the next odd 3. We then substract 1 since the skew is true. The other calculations are done similarly.