Skip to content

Instantly share code, notes, and snippets.

@LCamel
Last active May 29, 2023 14:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save LCamel/4638804256815beb78e672b3716d0626 to your computer and use it in GitHub Desktop.
Save LCamel/4638804256815beb78e672b3716d0626 to your computer and use it in GitHub Desktop.
False positives for the LessThan circuit (caused by overflow)
// https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom
const p = 23;
const N = 2;
var fp = []; // false positive
for (var x = 0; x < p; x++) {
fp[x] = [];
for (var y = 0; y < p; y++) {
fp[x][y] = ' ';
const diff = (x + (1 << N) - y + p) % p;
if (diff < (1 << (N + 1))) { // can pass Num2Bits
fp[x][y] = 'B';
if ((diff & (1 << N)) == 0) { // the logic of LessThan for "true"
fp[x][y] = 'L';
if (x >= y) { // false positive
fp[x][y] = 'F';
}
}
}
}
}
console.log("\nB: can pass Num2Bits L: and LessThan == 1 F: but false positive\n");
for (var y = p - 1; y >= 0; y--) {
var s = "";
for (var x = 0; x < p; x++) {
s += fp[x][y];
}
console.log(s);
}
console.log();
% node false_positive.js
B: can pass Num2Bits L: and LessThan == 1 F: but false positive
BBB LLLLB
BB LLLLBB
B LLLLBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLLBBBB
LLLBBBB F
LLBBBB FF
LBBBB FFF
BBBB FFFF
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment