search

lambdaclass / lambdaworks

lambdaworks offers implementations for both SNARKs and STARKs provers, along with the flexibility to leverage their individual components for constructing customized SNARKs.
https://lambdaclass.github.io/lambdaworks/
Apache License 2.0
622 stars 136 forks source link

Investigate Canonical Signed Digit representation for faster exponentiations and EC scalar mul #108

Open feltroidprime opened 1 year ago

feltroidprime commented 1 year ago

The canonical signed digit, or Non-Adjacent Form (NAF) is a unique way to represent a binary number with a lower absolute hamming weight, using digit € {0,1,-1} as coefficients instead of just digit € {0,1}.

See https://en.wikipedia.org/wiki/Non-adjacent_form

It should improve performance in exponentiation by squaring algorithms and similar as you just need a sub or negate function for -1 cases. The overall hamming weight W = sum([abs(digit) for digit in bin(int)]) is in average 1/3 instead of 1/2. Using this representation should lead to improvements in the range of 10-25% for the average case.

An example of this technique can be found in the gnark repo :

definition : https://github.com/ConsenSys/gnark-crypto/blob/8f7ca09273c24ed9465043566906cbecf5dcee91/ecc/bn254/bn254.go#L141-L143 usage (miller loop) : https://github.com/ConsenSys/gnark-crypto/blob/8f7ca09273c24ed9465043566906cbecf5dcee91/ecc/bn254/pairing.go#L161

jules commented 1 year ago

As an addendum to your point here, this can be combined very efficiently with GLV scalar multiplication, which can allow for ~50% speedups when performing group scalar muls. I've implemented the code for BLS12-377 here and I'd be happy to port that code over as well :)