arkworks-rs / r1cs-std

R1CS constraints for bits, fields, and elliptic curves
https://www.arkworks.rs
Apache License 2.0
133 stars 58 forks source link

Implement O(sqrt(n)) `conditionally_select_power_of_two_vector` method #118

Open mmagician opened 1 year ago

mmagician commented 1 year ago

Summary

Currently the function conditionally_select_power_of_two_vector uses method 5.1 from https://github.com/mir-protocol/r1cs-workshop/blob/master/workshop.pdf. By implementing the SumOfConditions method and then combining it with the existing technique, we could achieve less constraints.

For Admin Use