如何在 Circom 中生成對右移位運算符的約束

如何在circom電路語言中生成對右移位運算符的約束？

我正在嘗試執行以下操作：

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表達式不能被circom 編譯器重新表示為二次表達式的事實有關。

我很難將表達式重寫為二次的。它可能涉及將賦值和約束編寫為兩個單獨的操作，但我不確定對於右移來說正確的驗證約束是什麼。

在測試案例方面，我希望type是 $ 5 $ v什麼時候 $ 168 $ 例如。

使用來自circomlib的 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();

編輯：這並不能充分驗證移位操作。請參閱@meshcollider 的答案。

好的，我不完全確定這是否正確，但這就是我想出的。

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();

這些評論貫穿了我的思想，但基本上我用減法/乘法約束驗證了信號分配。

引用自：https://crypto.stackexchange.com/questions/98415