search

arkworks-rs / algebra

Libraries for finite field, elliptic curve, and polynomial arithmetic
https://arkworks.rs
Apache License 2.0
636 stars 248 forks source link

[Field] TWO_ADICITY implicitly upper-bounded #313

Open Nashtare opened 3 years ago

Nashtare commented 3 years ago

The current implementation / test suite implicitly assume that the TWO_ADICITY is upper bounded, and fits in one limb of the field element, or it will fail (this assertion in fft_field_tests() will fail, because of the implementation of get_root_of_unity()).

Is it already known? Is it planned to add support for larger two-adicities? In case it is not planned, maybe adding a specification in the documentation of the Field Trait could be good for newcomers.

weikengchen commented 3 years ago

Yes, as you observed, the current implementation of get_root_of_unity, which takes usize as input, implicitly makes a bound of the TWO_ADICITY. It is slightly more complicated to support larger two adicity, but should be doable.

I am thinking whether (1) to support larger two adicity as you mentioned or (2) to update the documentation to make this ~care~ clear.

Do you have a use case where TWO_ADICITY is higher than 64? My impression is that the pairing-friendly curves that people have been exploring so far mostly have this value under 64, but it does not mean that all the curves that people will use would always have a two adicity lower than 64. That is, it is sufficient in most cases, but is still restricted.

Pratyush commented 3 years ago

I guess the use-case would be for non-pairing-friendly fields, like the StarkWare field. Though in practice I'm not sure if we'll ever get to a world where we're doing FFTs over subgroups of size 2^64...

weikengchen commented 3 years ago

The problem seems to be, if the application never uses the subgroup as large as 2^64, but unfortunately this curve is just way too nice and have a high two adicity naturally, how should one write the curve file? and would it cause a problem?

ValarDragon commented 3 years ago

FWIW I think mersenne prime field extensions are the future of STARKs =p. The arithmetic is so much faster!

The quadratic extension field used in FourQ has a two adicity of 127 IIRC.

But these probably need specialized field impls anyway. Not sure the generic constructor needs to support two adicity's greater than 64, unless common fields/curves are using it? (If a field has greater two adicity, it does need to be accounted for, for tonneli shanks sqrt IIRC)

weikengchen commented 3 years ago

Dev is right. Starting from Libra, using an extension field of Mersenne prime field has become a known technique for efficiently implementing RS Code/Merkle Tree-based proofs.

I think the question is whether we want to change get_root_of_unity to support multiple limbs (i.e., taking [u64] as input).

kobigurk commented 2 years ago

Following up on this. It seems to me from looking at the code that setting TWO_ADICITY to be lower than the maximum might cause a problem with sqrt. Is there a known workaround, or just need custom implementations of either sqrt or the FFT?

ValarDragon commented 2 years ago

Per my recollection, the FFT algorithm should be identical. There should at most be something weird in creating the FFT domain. I think sqrt would need a custom implementation for tonelli shanks to handle it.

I feel like ideally we have a sqrt field parameter object where we can also add in constants for optimization, and then do stuff there. Though another ideal would be to just support greater two adicities, or to have 'unaccounted for two-adicity' as a variable. (Though the latter feels a bit hacky / silly)

kobigurk commented 2 years ago

Yeah, I think the FFT will be the same if we just make sure we use the right root of unity. I don’t think I’ve seen a way to encode it with the current abstraction yet.

On Fri, 11 Feb 2022 at 2:27 Dev Ojha @.***> wrote:

Per my recollection, the FFT algorithm should be identical. There should at most be something weird in creating the FFT domain. I think sqrt would need a custom implementation for tonelli shanks to handle it.

I feel like ideally we have a sqrt field parameter object where we can also add in constants for optimization, and then do stuff there. Though another ideal would be to just support greater two adicities, or to have 'unaccounted for two-adicity' as a variable. (Though the latter feels a bit hacky / silly)

— Reply to this email directly, view it on GitHub https://github.com/arkworks-rs/algebra/issues/313#issuecomment-1035675140, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA23MGFEI6A22GXYDBSZLFDU2RJXBANCNFSM5DUQNKRQ . You are receiving this because you commented.Message ID: @.***>

Pratyush commented 2 years ago

Maybe we change the signature to fn get_root_of_unity<const N: usize>(impl Into<BigInt<N>>) -> Option<Self>? That should suffice.