NilFoundation / zkLLVM

Zero-Knowledge Proof Systems Circuit Compiler
https://docs.nil.foundation/zkllvm
285 stars 48 forks source link

Support comparison flag for unsigned types #561

Closed akokoshn closed 6 months ago

akokoshn commented 7 months ago

Now >, < are mocked on assigner side, but we have comporison_flag component for deal with these operations. https://www.notion.so/nilfoundation/New-Components-Description-8012f3c4067b43b89e7c8246b42ccc38

One limitation: bits_amount has to be less than the field’s modulus_bits - 1. Looks like no problem for pallas base filed<255> with max value (modulus) = 0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001_cppui255 We can't support negative values.

Possible problem: For modulus_bits = 254 the max value is 4000000000000000000000000000000000000000000000000000000000000000 but max value of pallas base field<255> is greater 40000000000000000000000000000000224698fc094cf91b992d30ed00000001. According manual check comporison_flag works even with max of pallas base field<255>

#include <nil/crypto3/algebra/curves/pallas.hpp>

using namespace nil::crypto3::algebra::curves;

[[circuit]] typename pallas::base_field_type::value_type
    cmp() {
    const typename pallas::base_field_type::value_type max =           0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001_cppui255;
    const typename pallas::base_field_type::value_type max_minus_one = 0x40000000000000000000000000000000224698fc094cf91b992d30ed00000000_cppui255;
    const typename pallas::base_field_type::value_type one = 0x1_cppui255;
    return max > max_minus_one;
}
akokoshn commented 7 months ago

Initial implementation (just for check if comporison_flag works): https://github.com/NilFoundation/zkllvm-assigner/tree/561-enable-comporison-flag