This set membership proof is used in P2P networks, when one party possesses a private value, and the other party possesses a set. They would have to broadcast some data associated with the value and set through the network, and any third party is able to confirm that the value belongs to the set. No parties should be able to obtain the set or value from the broadcasted data.

Using hash functions was my first attempt, but the reverse-engineering of hashes is making it insecure. Plus, hashing every value in M and broadcasting it through the network requires a tremendously large bandwidth for all parties in the network, especially when M is large.

How can a zk-proof that fits the above be formulated that is feasible for usage even on a client that has a low bandwidth, while being secure as described before?

EDIT: I may have not made myself clear. Mathematically, it looks like this: There is the value $m$, the set $M$ plus a hypothetical function $f$, which works like this: $f(m) = Q$ and $f(M) = Z$ plus, there's another probably used number $k$. If, and only if $m ∈ M$, $Q$ and $Z$ has a specific mathematical relationship, such as $Q ≡ Z (mod k)$, or $Q = Z$. Achieving equality is the best scenario, since there are no possibility of false positives or negatives, but it is possibly impossible.


To prove a membership belonging to a set, as far as I know, there are two ways:

  1. Privacy-preserving authenticaiton scheme, such as group signatrues, anonymous credentials, etc., can keep the identity of a member secret and meanwhile supply the method to prove a memeber belonging to a group.
  2. Bloom filter. it is a probabilistic data structure that we can use to answer the question of whether or not a given element is in a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set.".

According to your question, the zk-proof which privacy-preserving schemes always used can certainly meet your requirements without broadcasting the set or hashing every value in M.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.