So they accept as arguments a standard composer, a set, and a potential member of that set. The output is a variable carrying 1 if member belongs to set and 0 otherwise.
I wrote 3 versions of the function that differ in the way they treat set:
check_private_set_membership treats the set as consisting of private inputs. This version probably doesn't make much sense because what's the value of proving that a secret witness belongs to a secret set? I don't know, but I included it just in case there is such a use case. Let me know your thoughts.
check_public_set_membership treats the set as consisting of public inputs. This seems to be the correct version for a set that consists of something like Merkle roots of various trees, since these roots would all be public knowledge. Treating the set's elements as public inputs reduces the number of variables that need to be added to the composer.
check_constant_set_membership treats the set as consisting of constants. The advantage of this is that I noticed a way to cut the number of gates in half by treating the set's elements as constants (see below). The problem is that this probably isn't appropriate for sets that change over time, like roots of Merkle trees. But maybe it has a use case.
If the elements of set can be treated as constants then this optimization works:
Ultimately we are checking that the following product equals 0:
(x - s_1)(x - s_2) ... (x - s_n)
If we let pi_k denote the first k terms in that product then pi_{k+1} = pi_k (x - s_{k+1}) , so it's enough to add a constraint pi_{k+1} = pi_k * x - s_{k+1} * pi_k. As long as s_{k+1} is a constant, this constraint can be added in a single arithmetic gate, as opposed to the 2 arithmetic gates needed to perform the subtraction and multiplication in separate operations. At the end we check that the final variable pi_n equals 0.
Unfortunately this doesn't work if we want to treat the set as public input because plonk doesn't allow us to multiply variables by public input values, only to add.
Adds functions for checking set membership. These all have the form
So they accept as arguments a standard composer, a set, and a potential member of that set. The output is a variable carrying 1 if
memberbelongs tosetand 0 otherwise.I wrote 3 versions of the function that differ in the way they treat
set:check_private_set_membershiptreats the set as consisting of private inputs. This version probably doesn't make much sense because what's the value of proving that a secret witness belongs to a secret set? I don't know, but I included it just in case there is such a use case. Let me know your thoughts.check_public_set_membershiptreats the set as consisting of public inputs. This seems to be the correct version for a set that consists of something like Merkle roots of various trees, since these roots would all be public knowledge. Treating the set's elements as public inputs reduces the number of variables that need to be added to the composer.check_constant_set_membershiptreats the set as consisting of constants. The advantage of this is that I noticed a way to cut the number of gates in half by treating the set's elements as constants (see below). The problem is that this probably isn't appropriate for sets that change over time, like roots of Merkle trees. But maybe it has a use case.If the elements of
setcan be treated as constants then this optimization works:Ultimately we are checking that the following product equals 0:
If we let
pi_kdenote the first k terms in that product thenpi_{k+1} = pi_k (x - s_{k+1}), so it's enough to add a constraintpi_{k+1} = pi_k * x - s_{k+1} * pi_k. As long ass_{k+1}is a constant, this constraint can be added in a single arithmetic gate, as opposed to the 2 arithmetic gates needed to perform the subtraction and multiplication in separate operations. At the end we check that the final variablepi_nequals 0.Unfortunately this doesn't work if we want to treat the set as public input because plonk doesn't allow us to multiply variables by public input values, only to add.
This will close #120