search

Consensys / gnark

gnark is a fast zk-SNARK library that offers a high-level API to design circuits. The library is open source and developed under the Apache 2.0 license
https://hackmd.io/@gnark
Apache License 2.0
1.44k stars 369 forks source link

bug: constants are reduced before being split in limbs #996

Closed hussein-aitlahcen closed 10 months ago

hussein-aitlahcen commented 10 months ago

Hi, I was wondering why do we reduce the constant value here? I have a constant value > p and figured out it was getting reduced (hence tests failing). Decomposing the value into limbs myself works. I assumed that splitting in limbs was done to allow for bigger numbers than the base field? Since decomposing myself the value is working, I'm not really understanding why we have this limitation in emulated.ValueOf... Am I missing something obvious? Thanks

ivokub commented 10 months ago

Keep in mind that p here is the non-native modulus, not the curve scalar field modulus.

We usually think about emulated.Element as a field element and it is convenient to represent it mod p. We reduce automatically after some operations (multiplication, inverse, division) anyway, so I think user couldn't assume specific integer value, but equivalence mod p only.

What is the use case why would you need to have constant values >p?

hussein-aitlahcen commented 10 months ago

Keep in mind that p here is the non-native modulus, not the curve scalar field modulus.

We usually think about emulated.Element as a field element and it is convenient to represent it mod p. We reduce automatically after some operations (multiplication, inverse, division) anyway, so I think user couldn't assume specific integer value, but equivalence mod p only.

What is the use case why would you need to have constant values >p?

That makes sense, it's the bn254 (doing emulated bn254 on bn254) cofactor I'm using to clear the cofactor after mapping to the curve, the value is > p in this case... My first try was to halve the cofactor and clear by doing add(scalarmul(cofactor/2, x), scalarmul(cofactor/2, x)), which is working. But decomposing myself is also working if I don't reduce the value, which halve the above constraints. Thanks for the details :)

hussein-aitlahcen commented 10 months ago

@ivokub I assume we need to extend the uint module to be able to handle that then (would be a u256 here)?

hussein-aitlahcen commented 10 months ago

I think it can be closed, thanks again

yelhousni commented 10 months ago

Or maybe you can clear the cofactor differently instead of multiplying by that big value? For example https://cacr.uwaterloo.ca/techreports/2011/cacr2011-26.pdf sec. 6.1 which you can find implemented in gnark-crypto. You only need a constant of 64 bits.

hussein-aitlahcen commented 10 months ago

Or maybe you can clear the cofactor differently instead of multiplying by that big value? For example https://cacr.uwaterloo.ca/techreports/2011/cacr2011-26.pdf sec. 6.1 which you can find implemented in gnark-crypto. You only need a constant of 64 bits.

Thanks for the link but I already tried to implement the non naive version without success... I'll give it another try and replicate the gnark-crypto implementation.

hussein-aitlahcen commented 10 months ago

Alright thanks a lot @yelhousni, I figured out the issue in the code with you call, looks like the circuit is now compatible with the gnark-crypto MapToCurve2 :+1: