Skip to content

Add wnaf#14

Merged
NikVolf merged 2 commits into
paritytech:masterfrom
AztecProtocol:add-wnaf
May 28, 2019
Merged

Add wnaf#14
NikVolf merged 2 commits into
paritytech:masterfrom
AztecProtocol:add-wnaf

Conversation

@zac-williamson

Copy link
Copy Markdown

Hello!

This is a small modification to the miller_loop and precompute methods. Both methods iterate over the bits of parameter ate_loop_count. If the bit is set to true, a line function for the G2 group element is precomputed in precompute. Then later in miller_loop, the line function is scaled by the paired G1 group element, with the result being multiplied into the accumulated Fp12 element f.

We can take advantage of the fact that negations on an elliptic curve are essentially free, and use a Non-Adjacent-Form representation of ate_loop_count. Instead of a binary representation, each 'bit' can be either 0, 1 or -1. The hamming weight of the NAF is ~50% less than the binary form.

The precompute algorithm is modified to iterate over NAF entries of ate_loop_count_naf. If an entry is -1, a line function relative to -G2 is computed. This reduces the number of precomputed G2 entries, from 102 to 87.

This provides a corresponding ~15% reduction in the run-time of the miller loop, as each precompute entry requires a line doubling computation in Fp2 and a scalar multiplication in Fp12, both of which are expensive.

@NikVolf

NikVolf commented May 6, 2019

Copy link
Copy Markdown

hey @burdges can you take a quick second look on this?

@NikVolf NikVolf merged commit 6beba2e into paritytech:master May 28, 2019
@NikVolf

NikVolf commented May 28, 2019

Copy link
Copy Markdown

Thanks!

@burdges

burdges commented May 28, 2019

Copy link
Copy Markdown

Oops, this fell off my radar, sorry! I have not checked the conversion of all the test vectors or ate_loop_* but otherwise everything makes sense.

There is however one Rust issue though, ate_loop_count_naf() allocates needlessly, as you never write to the result, so it should be replaced by

const ATE_LOOP_COUNT_NAF : [u8; 64] = [1,0,1,0,0,0,3,0,3,0,0,0,3,0,1,0,3,0,0,3,0,0,0,0,0,1,0,0,3,0,1,0,0,3,0,0,0,0,3,0,1,0,0,0,3,0,3,0,0,1,0,0,0,3,0,0,3,0,1,0,1,0,0,0];

As an aside, even if you wrote to the result, then for a short array like this you should return a [u8; 64] directly. Vec should be avoided unless you cannot know the length in advance

@zac-williamson

Copy link
Copy Markdown
Author

Oops, this fell off my radar, sorry! I have not checked the conversion of all the test vectors or ate_loop_* but otherwise everything makes sense.

There is however one Rust issue though, ate_loop_count_naf() allocates needlessly, as you never write to the result, so it should be replaced by

const ATE_LOOP_COUNT_NAF : [u8; 64] = [1,0,1,0,0,0,3,0,3,0,0,0,3,0,1,0,3,0,0,3,0,0,0,0,0,1,0,0,3,0,1,0,0,3,0,0,0,0,3,0,1,0,0,0,3,0,3,0,0,1,0,0,0,3,0,0,3,0,1,0,1,0,0,0];

As an aside, even if you wrote to the result, then for a short array like this you should return a [u8; 64] directly. Vec should be avoided unless you cannot know the length in advance

Heya, thanks for the feedback on this, rust is a language I'm somewhat unfamiliar with. Given the branch is merged, is it too late to push a change to fix this?

@dvdplm

dvdplm commented May 29, 2019

Copy link
Copy Markdown

is it too late to push a change to fix this?

Yes. If you have the time it would be fantastic if you opened a second PR. Otherwise I can do it. :)

dvdplm added a commit that referenced this pull request May 29, 2019
@dvdplm dvdplm mentioned this pull request May 29, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants