pragma circom 2.1.8;
include "../node_modules/circomlib/circuits/comparators.circom";
// Write a circuit that returns true when at least one
// element is 1. It should return false if all elements
// are 0. It should be unsatisfiable if any of the inputs
// are not 0 or not 1.
template MultiOR(n) {
signal input in[n];
signal output out;
}
component main = MultiOR(4);
Answer
template MultiOR(n) {
signal input in[n];
signal output out;
// constrain inputs to be only 1 or 0
for (var i = 0; i < n; i++) {
in[i] * (1 - in[i]) === 0;
}
// transformation
signal s[n];
// flip the first
s[0] <== 1 - in[0];
// flip term & multiply w/ prev. term
for(var i = 1; i < n; i++){
s[i] <== (1 - in[i]) * s[i - 1];
}
out <== 1 - s[n-1];
}
component main = MultiOR(4);
If you have a series of multiplications, within which there is a 0: x * x *0 * x, the entire series returns 0.
What MultiOR is saying is that: x * x * 1 * x * x, the entire series returns 1.
If there is a '1' term, the entire multiplication should return 1.
Observe the following transformation:
in --> 1 - in
[0,0,0] --> [1,1,1]
[1,1,1] --> [0,0,0]
[1,0,0] --> [0,1,1] ** 0*1*1 = 0
if we had at least one 1, then there will be at least one 0, upon transformation. If we multiply the inputs after transformation, we would get 0.
Then if we minus the result from 1, (1-0), we will get 1.
return 1, if at least 1 of the inputs is 1
[0,0,0] --> [1,1,1] || 1*1*1 = 1 || 1-1 = 0
if we had all inputs as 0, then they will be transformed to 1
multiplying the resulting inputs give us 1
Then if we minus the result from 1, (1-1), we will get 0.