Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimized arithmetic and comparisons for UInt gadgets #150

Open
DanieleDiBenedetto opened this issue Dec 22, 2021 · 0 comments
Open

Optimized arithmetic and comparisons for UInt gadgets #150

DanieleDiBenedetto opened this issue Dec 22, 2021 · 0 comments
Assignees
Labels
enhancement New feature or request new feature optimization Performance improvement for the current codebase

Comments

@DanieleDiBenedetto
Copy link
Collaborator

Depends on #149 .

Actually, for our applications, in which we compare only small numbers (usually max 64 bits in length), we can do better by defining the comparison directly for the UInt gadgets: to prove an inequality of the from x >= y, where x and y are UInt gadgets, we can follow an approach similar to what we did for the ThresholdSignatureCircuit (enforcing number_of_valid_signatures >= threshold) https://github.com/HorizenOfficial/zendoo-sc-cryptolib/blob/development/doc/GenericThresholdCircuit.pdf, e.g. enforcing that pack(x_bits) - pack(y_bits) == pack(alloc(x_val-y_val).to_bits_with_length_restriction[..64])
(We can do this with 1 LC of the form 2^0(x_b0 - y_b0) + ... + 2^n-1(x_bn-1 - y_bn-1) = 2^0 diff_0 + ... + 2^n-1 * diff_n-1.
We can also integrate Add and Mul gadgets for UInt (we already have AddMany), and let them return an "overflow" bit that, if desired, we can enforce it to be 0. This will make operations and comparison doable without using any Field gadget, thus completely controllable and secure.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request new feature optimization Performance improvement for the current codebase
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants