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.45k stars 381 forks source link

perf: fast path operations for small non-native values #1326

Closed ivokub closed 2 days ago

ivokub commented 6 days ago

Description

This PR enforces small non-native values to work on zero or one limb. I also added some fast-path operations when we can deduce the result without needing to perform any operations (mul by zero for example).

Also adds a few more emulation parameters useful for implementing small-fields.

Type of change

How has this been tested?

Existing tests succeed

How has this been benchmarked?

Updated the stats.

Checklist:

ivokub commented 4 days ago

lgtm. Shouldn't we also have fast path for Div / Inv / Sqrt ?

We should. I'll see how we could be able to implement them.

ivokub commented 2 days ago

lgtm. Shouldn't we also have fast path for Div / Inv / Sqrt ?

We should. I'll see how we could be able to implement them.

Added fast paths to Div/Sqrt methods. For inverse we don't support inverse of zero (different from gnark-crypto imo where we take inverse of zero to be zero), so omitted it.

Also added test for checking that the fast paths are complete against short zero (on zero limbs) and large zero.