如何在Circom中生成右移位位算子的约束

Question

如何在圆环电路语言中生成右移位位运算符的约束？

我想做以下几件事：

pragma circom 2.0.0;

template MAIN() {

    signal input v;
    signal output type;

    type <== v >> 5;
}

component main = MAIN();

我得到了以下错误：

error[T3001]: Non quadratic constraints are not allowed!
   ┌─ "/Users/ilia/compiling/main-circom/main.circom":68:5
   │
68 │     type <== v >> 5;
   │     ^^^^^^^^^^^^^^^ found here
   │
   = call trace:
     ->MAIN

我认为这与v >> 5表达式不能由圆环编译器重新表示为二次表达式有关。

我很难把这个表达式改写成二次型。它可能需要将赋值和约束作为两个单独的操作来编写，但我不确定对于右移位来说，正确的验证约束是什么。

在测试用例方面，例如，当type是168时，我希望v是D8。

Answer 1

使用来自LessThan的圆环库比较器的解决方案：

//... import comparators from circomlib ...

template MAIN() {

    signal input v;
    signal output type;
    signal check_v;
    component lessThan = LessThan(8);

    type <-- v >> 5;
    check_v <== type*32;
    // use circomlib LessThan to check that (v - check_v) < 32
    lessThan.in[0] <== v - check_v;
    lessThan.in[1] <== 32;    
    lessThan.out === 1;
}

component main = MAIN();
```#qcStackCode#

Answer 2

编辑:这不能充分验证shift操作。请参阅@mesh对撞机的答案。

好吧，我不确定这是不是对的，但这是我想出来的。

pragma circom 2.0.0;

template MAIN() {

    signal input v;
    signal output type;

    // assign `type` signal
    // shift 0bXXXYYYYY to 0b00000XXX
    // v is a trusted signal
    type <-- v >> 5;

    // prepare constraint checking for `type`
    signal three_upper_bits;
    // 0b11100000 = 0xE0
    // v is trusted signal
    three_upper_bits <-- v & 0xE0; // 3 upper bits of v (0bXXX00000). v can only be 8 bits.

    // should_only_be_lower_bits is 0b000YYYYY
    // we get it by 0bXXXYYYYY - 0bXXX00000 to get 0b000YYYYY
    var should_only_be_lower_bits = v - three_upper_bits;
    // we're checking that should_only_be_lower_bits can only be LESS THAN 32 (0b00011111)
    // that verifies that three_upper_bits are pristine and were not messed with.
    // if someone were to mess with three_upper_bits, should_only_be_lower_bits would contain higher bits
    // and be more than 32 (0b00011111).
    // by doing that, we cryptographically assert that should_only_be_lower_bits is in the form of 0b000YYYYY
    signal upper_bit_1;
    signal upper_bit_2;
    signal upper_bit_3;
    upper_bit_1 <-- should_only_be_lower_bits & 0x80; // 0b10000000. This signal can be 0bX0000000
    upper_bit_2 <-- should_only_be_lower_bits & 0x40; // 0b01000000. This signal can be 0b0X000000
    upper_bit_3 <-- should_only_be_lower_bits & 0x20; // 0b00100000. This signal can be 0b00X00000
    upper_bit_1 === 0; // Assert that 0bX0000000 is 0b00000000
    upper_bit_2 === 0; // Assert that 0b0X000000 is 0b00000000
    upper_bit_3 === 0; // Assert that 0b00X00000 is 0b00000000

    // generate constraint for type signal
    // 2^5 = 32
    type * 32 === three_upper_bits;
}

component main = MAIN();

注释经过我的思考，但本质上我用减法/乘法约束来验证信号赋值。

Answer 3

circomlib/circuits/sha256/shift.circom有一个执行右移位的ShR组件。

    var InputBits = 8;
    var ResultBits = 3;

    // convert v to bits
    component n2b = Num2Bits(InputBits);
    n2b.in <== v;

    // shift
    component shr = ShR(InputBits, 5); // v >> 5
    for (var i = 0; i < InputBits; i++) {
        shr.in[i] <== n2b.out[i];
    }

    // convert back to number
    component b2n = Bits2Num(ResultBits);
    for (var i = 0; i < ResultBits; i++) {
        b2n.in[i] <== shr.out[i];
    }
    type <== b2n.out;