search

ethereum / go-ethereum

Go implementation of the Ethereum protocol
https://geth.ethereum.org
GNU Lesser General Public License v3.0
47.22k stars 19.99k forks source link

NAF representation in bn256 #27957

Open Raneet10 opened 1 year ago

Raneet10 commented 1 year ago

Hey folks! In bn256/cloudflare, one thing that caught my eye was the NAF representation of 6u + 2 (u = 4965661367192848881) : https://github.com/ethereum/go-ethereum/blob/5976e58415a633c24a0d903e8a60a3780abdfe59/crypto/bn256/cloudflare/optate.go#L115-L118 Now , in the NAF representation aren't the non zero values not supposed to be adjacent ? Is this a different representation than NAF that's maybe faster ? Or I am interpreting it wrong (most likely) ? Btw by using this https://github.com/Consensys/gnark-crypto/blob/30ae949dd2311dceba5069585b9b324d53dccf15/ecc/utils.go#L12 ,it came out to be [0 0 0 1 0 1 0 -1 0 0 -1 0 0 0 1 0 0 -1 0 -1 0 0 0 1 0 -1 0 0 0 0 -1 0 0 1 0 -1 0 0 1 0 0 0 0 0 -1 0 0 -1 0 1 0 -1 0 0 0 -1 0 -1 0 0 0 1 0 -1 0 1] on my end.

Apologies if this has already been discussed/answered!

EDIT: Probably this shouldn't be under docs type

MariusVanDerWijden commented 1 year ago

We're just using bn256/cloudflare as a vendored in library, so all questions regarding the lib should be better asked here: https://github.com/cloudflare/bn256

I tried a few online naf calculators with 29793968203157093288 = 6u + 2 (u = 4965661367192848881) and they returned different naf representations (e.g. https://ngn.bitbucket.io/k/#eJxLs9LVVzeK0TVSNFYw1OICgjQFI0tzS2NLMwsjA2NDU3MDS2MjCwsuAKUCB70=)

Raneet10 commented 1 year ago

I see but isn't the cloudflare's lib using a different value for u ( u = 6518589491078791937 given here ; the NAF form also looks correct) than what we use ?

I guess the NAF representation might differ based on the algorithm used. Though my understanding was that in general in NAF the non-zero values can't be adjacent to each other (https://hackmd.io/@drouyang/S1GgWQvoj).

Raneet10 commented 1 year ago

Another thing I missed mentioning was that the number of non-zero bits currently is 26 as compared to 22 in the representation in my comment above and 20 in the calculator you shared. Since the hamming weight is lower in the other 2 alternative representations, we can theoretically optimise the Miller loop with lower number of additions.