zksecurity / noname

Noname: a programming language to write zkapps
https://zksecurity.github.io/noname/
179 stars 46 forks source link

Not equal using `equal_cells` #128

Closed lognorman20 closed 3 months ago

lognorman20 commented 3 months ago

This PR aims to optimize #119. Implements equal_cells in is_zero in an effort to reduce constraints. The result of doing this are presented in this table:

Backend Constrains w/o not_equal Constraints w/ not_equal
R1CS 10 12
Kimchi 19 24

Although the number of constraints went in the wrong direction, I have an idea for improvement. First is implementing more bitwise operations to avoid adding constraints. Functions such as equal, is_zero_cell, and even arithmetic operations like sub and mul can be implemented using bitwise operations that avoid creating unnecessary internal variables. As the language continues to expand, more operations will come such as bitshifts and xor which will enhance the possibilities to optimize. Moving the workload to bitwise operators to reduce constraints might just be moving the problem to another area though and I'm curious to hear what other ideas there are.

lognorman20 commented 3 months ago

Another aspect I noticed is that the # of constraints for equal and not equal are roughly the same. Definitely some improvement can be done for both

mimoo commented 3 months ago

thanks for the experiment here! I can close this one as we merged the other!