Implement Montgomery backend with 32 bits

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

625 stars 140 forks source link

Implement Montgomery backend with 32 bits #538

Open MauroToscano opened 1 year ago

MauroToscano commented 1 year ago

Currently montgomery backend works with limbs of 64 bits. For really small fields, like babybear, it may be useful to have a 32 bits version. This version doesn't need to support multiple limbs, since it's use is limited to this field, but it may be useful to generalize it.

[ ] Implement a montgomery backend of 32 bits, with only one u32 as limb.
[ ] Add a fuzzer to compare both montgomery backends
[ ] Generalize it to be multi limb

We recommend just doing the first task, then generalizing

RajeshRk18 commented 1 year ago

I can take up this!

iammadab commented 1 year ago

I can take up this!

@RajeshRk18 still working on this?

RajeshRk18 commented 1 year ago

I can take up this!

@RajeshRk18 still working on this?

Yeah, wip

skaunov commented 9 months ago

:wave: Could I take this one?

RajeshRk18 commented 9 months ago

:wave: Could I take this one?

It's almost done. Just need to add fuzzer.

skaunov commented 9 months ago

Am I correct that for generalizing over both word size the only way is to move const fn from impl blocks, as being generic instantly prevents them from working? So minimum boilerplating would be with a trait Word for generic and having macros for const fn (anyway they're associated) which would generate it for the type aliases... And is intricate to balance readibility/maintainability of such solution with wins from having u32 backend?

Just trying to understand this issue better. Sorry if miss/confused something. Would be nice to see correction of my comprehension of this one! :pray: