Need help writing R1CS constraint

General Education
1

How would i write constraints for this, given variables a and b, put 1 in variable c if a != b else put 0. a and b are not boolean. I need this proving that only n variables in 2 lists (of equal length) of variables are different where n is a public value.

l1 = [a1, a2, a3, ...am]
l2 = [b1, b2, b3, ...bm]
r = [a1-b1,a2-b2,....am-bm]

If all variables in r are 0 or 1 then i can constrain sum of variables in r to n.

1 Like
2

This is a “boolean scaling” which can be done in 3 constraints:

(1 - c) × (c) = 0    // c is boolean
(a - b) × (λ) = (c)  // a = b  ⇒  c = 0
(ÎŒ) × (c) = (a - b)  // a ≠ b  ⇒  c ≠ 0

If you only need to prove that at most n pairs of variables are different, then it’s only 2 constraints per pair because you only need the first and third constraints above.

Similarly, for at least n different, you only need the first and second constraints.

1 Like
3

Thanks @daira. How would the prover set λ and Ό? λ = (a - b)-1 (0 when a == b) and Ό = λ-1 which is (a - b)?
You can do this with 2 constraints as i found this in the Pinocchio paper on page 7, under Zero-Equality Gate. The constraints for Y = (X! = 0)?1 : 0 are:

X × M − Y = 0
(1 − Y) × X = 0

Now Y cannot be anything other than 0 or 1. We set X to a - b, M to be (a - b)-1, then Y is c.

Regarding “at least n pairs of variables are different”, for the r pairs that are equal with r >= n, the prover sets λ = (a - b)-1 for n equal pairs and for the remaining r - n pairs, sets λ = 0.
Don’t follow the " at most n pairs" argument

1 Like
4

Ah ok, yes that looks correct. The first constraint enforces X = 0 ⇒ Y = 0, and the second enforces X ≠ 0 ⇒ Y = 1.

Never mind what I said about the “at least” and “at most” optimizations; they can’t be combined with the two-constraint zero-equality gate, and so they don’t help. (The reason they can’t be combined is that each of the two zero-equality gate constraints alone doesn’t enforce booleanity of Y.)

5

Are the “at least” and “at most” optimizations possible in the 3 constraint case? Or do we need a different approach where we do a range check on n?

6

Yes, the former. For example, for “at most n are different”, if we do this for each pair:

(1 - c) × (c) = 0    // c is boolean
(ÎŒ) × (c) = (a - b)  // a ≠ b  ⇒  c ≠ 0

then for pairs that are different we must have c = 1, and for pairs that are the same we can choose either c = 0 or c = 1. So we can arbitrarily pick m - n of the pairs that are the same and set c = 0 for those; then set c = 1 for all the other (n) pairs. Then the sum of the c’s will be n.

Similarly for “at least n are different”, we do this for each pair:

(1 - c) × (c) = 0    // c is boolean
(a - b) × (λ) = (c)  // a = b  ⇒  c = 0

then for pairs that are the same we must have c = 0, and for pairs that are different we can choose either c = 0 or c = 1. So we can arbitrarily pick n of the pairs that are different and set c = 1 for those; then set c = 0 for all the other (m - n) pairs. Then the sum of the c’s will be n.

Incidentally, there’s no need for a separate constraint to prove that the sum is n (in any of the three cases). Just substitute n - ∑c1
m-1 for all occurrences of c0.

2 Likes
7

@daira Thanks a lot for the explanations.

2 Likes