api.Cmp is very costly

[sid-alluri]

Hi, I am trying to implement a ReLU function. I am using api.Cmp() and api.ToBinary(). My implementation is inefficient and costing a lot of memory. Is there any way I can optimize this and implement an efficient ReLU?

[ivokub]

Currently api.Cmp() indeed is quite costly - we use bitwise comparison method and we additionally have to constrain the bits against the modulus. We have on a roadmap an idea for implementing more efficient comparison method (see #831).

Alternatively - if you know that the absolute difference between the values you are comparing is small, then it is more efficient to use the math/cmp gadget (thanks to @aybehrouz for the contribution).

Can you describe what is ReLU function? Maybe there is an alternative way to implement it?

[sid-alluri]

That would impact to the logic of the circuit. From what I know negative numbers are represented as x-|p|, p=prime. Using api.IsZero won't work because the negative numbers are represented as positive too.

[aybehrouz]

I'd say you should try to define a bound b for the magnitude of a number |x| in your domain such that |x| <= b. Note that likely you have such a bound already, since on |x| > P/2 2's complement like overflow occurs which is very problematic in most domains. When you use the native field for signed arithmetic you still need to handle overflows. You'll have overflows similar to 2's complement overflow:

int main() {
    int x = 2147483647;
    printf("%d %d", x, x + 1); 
    // output: 2147483647 -2147483648

    return 0;
}

So whatever you use for handling overflow might work for defining a tighter bound. With a bound around P/4, you should be able to use BoundedComparator for checking positivity.

[ivokub]

To confirm, in-circuit all operations are done modulo the scalar modulus, so all corresponding integer values are positive in the range [0, modulus). Even if you assign negative values to the witness, we convert them internally to field elements to the range [0, modulus).

So you would have to define negative values essentially yourself (e.g. everything larger than modulus/2). And for that BoundedComparator is the best tool. Have a look at the example

[sid-alluri]

Thank you for the detailed explanation @ivokub and @aybehrouz. I am a little confused, while creating a NewBoundedComparator what should be the absDiffUpp to do the comparison for the above case (x>0)?

[aybehrouz]

The maximum possible value of |x|. For example if I have some numbers that are in range [-250, 100] absDiffUpp should be 250.

[aybehrouz]

@ivokub I'm so glad I could help.

@sid-alluri
If it is possible in your specific application, you could try to limit the bit length of your numbers to something that is less than api.Compiler().FieldBitLen(). For example you could limit your numbers to 128 bit numbers. You can enforce this restriction by using api.ToBinary and WithNbDigits option. Then, you should be able to use BoundedComparator, which is a bit more efficient.

[sid-alluri]

Thanks for the reply. Is there any example following similar steps. It would be really helpful

[aybehrouz]

Unfortunately that doesn't work for signed numbers very well.