Zero-Knowledge Proofs for Set Membership

With a Merkle tree one can accumulate sets made of arbitrary elements using a collision-resistant hash function. We refer to this resource or this one for a more detailed explanation, but the basic idea is the following.

The public parameters simply consist of an hash function (e.g., SHA-256).
In order to accumulate a set $S = \{x_1, \ldots, x_n\}$ (let us assume for simplicity that $n$ is a power of $2$), one builds a binary tree in which $ \{x_1, \ldots, x_n\}$ are the leaves, and every internal node is the hash of its two children. The accumulator value $A$ is then the value at the root of such tree.
To create a proof $\pi_j$ that a certain $x_j \in S$, one returns all the sibling nodes that are in the path from the leaf $x_j$ until the root.
From the binary tree structure one then gets that these proofs consist of $\log(n)$ strings of $\ell$ bits each (where $\ell$ is the hash’s output bit length), and can be verified by using the siblings to recompute the nodes in the path and then check if the final result is equal to the root $A$.

Merkle trees are a very powerful construct, with countless applications and a lot of nice properties. They are actually more powerful than accumulators; they realize a so-called vector commitment, since the position of each leaf in the tree is also encoded in a binding way, in the sense that it is computationally impossible to claim two distinct values at the same position.

With RSA Accumulators one can accumulate sets made of prime numbers. The main ingredient of these constructions are groups of unknown order, of which RSA groups (from which the name) or class groups are candidate realizations. Let us show how this works in RSA groups.

The public parameters consist of an RSA modulus $N=p \cdot q$ product of two large prime numbers $p$ and $q$, and of a random generator $G \in \mathbb{Z}_{N}^{*}$. Here, $\mathbb{Z}_{N}$ denotes the ring of non-negative integers modulo $N$—the set $\{0, 1, \ldots, N-1\}$—while $\mathbb{Z}^{*}_{N}$ is the subset of elements in $\mathbb{Z}_{N}$ that are also coprime with $N$, which form a group under multiplication.

In order to accumulate a set $S$ of prime numbers $\{e_1,\ldots e_{n}\}$, one computes
$$A \leftarrow G^{\prod_{i=1}^{n} e_i} \bmod N.$$
To create a proof that a certain $e_j \in S$, one computes
$$\pi_j \leftarrow G^{\prod_{i=1,i\neq j}^{n} e_i} \bmod N = A^{1/e_j} \bmod N$$
which can be verified by checking if
$$\pi_j^{e_j} = A \bmod N$$

Overall, RSA accumulators are a quite simple and elegant construction. While the basic construction above has the limitation that elements must be prime numbers, this can be solved by using appropriately constructed hash functions that map arbitrary strings into primes. Compared to Merkle trees, they have the appealing property that everything is constant-size: both $A$ and the proof $\pi_j$ consist of one group element each, and verification requires one modular exponentiation only.
On top of this, they enjoy further properties. For example, it is possible to efficiently add elements to the accumulator value (i.e. it is dynamic), to create proofs of non-membership (it is universal), and to create short proofs for membership of many elements. See for example this recent work by Boneh, Bunz and Fisch to read about these and more properties.

We have seen how accumulators can provide a solution to the problem of proving and verifying set membership in an efficient manner.
Let us now move to the question of how to make these proofs also privacy-preserving, namely how to prove that $x \in S$ without revealing $x$.

Actually, in most applications, the privacy requirement about $x$ typically goes together with the need of proving more than just membership. One may wish to prove that a property $P(x)$ holds for some element $x \in S$, without revealing exactly for which element.
In other (more cryptographic) words, one is interested in making a zero-knowledge proof (ZKP) for the NP relation $R(S, x) := x\in S \wedge P(x)$, where $S$ is public and $x$ is secret.
A ZKP for $R$ however is not necessarily “efficient” in the same sense as discussed earlier since the verifier should read $S$, and the proof itself may not be succinct.

To make the proof also short and efficient to verify, a solution is to mix ZKPs with accumulators, that is to build a ZKP for the following relation
$$R(A, (x, \pi_x)) := \textsf{Verify}(A, x, \pi_{x}) \wedge P(x)$$
that, in words, proves existence of an element $x$ for which $P$ holds and for which there is a valid accumulator proof relative to $A$, which in turn implies membership in the set accumulated in $A$.

This blueprint can be applied to both Merkle trees and RSA accumulators.
In the rest of this post, we review the main existing solutions that follow these two approaches, and then we conclude by mentioning a recent work.

ZKPs for set membership via Merkle trees are a straightforward application of the ZKP & Accumulators mixing approach mentioned above.
Notably, this idea has been implemented in the Zcash protocol, which used the general-purpose power of zkSNARKs in order to prove in zero-knowledge existence of a valid Merkle path (in addition to other properties modeling the validity of a transaction). This in turn translates into proving correctness of about $\log |S|$ hash computations on secret inputs. Encoding hash computations in the zkSNARK is what makes this approach particularly expensive for the prover. Zcash’s Sapling provided significant speedups of this approach via an ingenious choice of a pairing-friendly elliptic curve and the Pedersen hash function. Nevertheless, proving set membership is by now the most expensive part of proof generation in Zcash.

For the case of RSA Accumulators, a notable work is that of Camenisch and Lysyanskaya who designed a ZKP protocol for the knowledge of an integer $e$ that is in the accumulator and that is committed in a group $\mathbb{G}$ of prime order $q$. More technically, given an accumulator $A$ and a Pedersen commitment $C_{e}\in \mathbb{G}$ as public values, they show how to prove knowledge of $(e, W, r)$ such that
$$A = W^{e} \bmod N \wedge C_e = g^{e} h^{r} \in \mathbb{G}$$
Having the commitment $C_{e}$ comes in handy if the final goal is to prove some property $P$ about the set element $e$: one simply creates another commit-and-prove ZKP for proving knowledge of $(e, r)$ such that $C_e = g^{e} h^{r} \in \mathbb{G}$ and $P(e)$ holds.

The Camenisch-Lysyanskaya protocol is potentially more efficient than the one based on Merkle trees as it does not require expensive general-purpose ZKPs that encode hash computations. Nevertheless, its use can be cumbersome due to some technical details. Most notably, the accumulated sets must be prime numbers of a specific size (which also imposes a minimum size for the prime-order group), and the hash-to-prime trick to avoid this problem cannot be used straightforwardly to mitigate this issue.

In the last part of this post, I would like to mention a recent work [BCFK19] that investigates modular and efficient constructions of ZKPs for set membership.

One is often confronted with creating ZKPs for “composite statements”, e.g., statements of the form “I know a value $x$ that belongs to a set $S$ and for which properties $P_1(x)$ and $P_2(x)$ hold”. In such a case, it can be convenient to create a proof by using three different proof systems, one for each subtask, e.g., $\Pi_{mem}$ for set membership, $\Pi_1$ for $P_1$, $\Pi_2$ for $P_2$.
This modular approach can be beneficial in multiple ways: one can focus on designing efficiency-optimized ZKPs for specific tasks, the same scheme can be re-used and replaced in a plug-and-play fashion, and it is just a simple design paradigm.

Technically, this approach can be realized by using commit-and-prove ZKP systems.
In a nutshell, a proof system $\Pi$ for a property $P$ is commit-and-prove if it can prove statements of the form “I know $x$ such that $P(x)$ holds and $C_{x}$ is a commitment to $x$”. Since commitments are binding, generating two such proofs with respect to the same commitment immediately implies an AND composition of the two proven statement. Essentially, commitments act as a “secure glue” between different proof systems.
While commit-and-prove has been known and used extensively in cryptography constructions, the recent LegoSNARK paper studied this paradigm in the context of succinct ZKPs, aka zkSNARKs.

The [BCFK19] paper starts from the observation that an accumulator value can be seen as a commitment to a set, and that the whole accumulator primitive can be seen as a succinct commit-and-prove system for set membership relations. In this sense, accumulators with ZK proofs of knowledge (i.e., that can prove “I know a valid accumulator proof for an $x$ in the commitment”) can be seen as commit-and-prove zkSNARK for set membership relations involving two types of commitments, a commitment to a set—the accumulator—and a commitment to an element.

So, one theoretical contribution of the paper is to extend the model of commit-and-prove zkSNARKs (and their composability properties) to the setting of typed-commitments, namely commitments to messages of different types (e.g., strings and sets over strings).

On the more practical side, [BCFK19] proposes new commit-and-prove zkSNARKs for set-membership, notably two solutions based on RSA accumulators that can be combined modularly and efficiently with other popular ZKP systems, such as Bulletproofs or Groth16. The latter feature is useful since it allows one to prove statements of the form “I know a value $x$ that belongs to a set $S$ and for which property $P(x)$ holds'”, by using this specialized scheme for the set-membership part and a general-purpose one for any other property about $x$.

Going more into the detail, [BCFK19] proposes two solutions based on RSA.
Both of them provide a functionality similar to the ZKP of Camenisch and Lysyanskaya mentioned earlier, in the sense that the element $x$ object of the membership proof is committed in a Pedersen commitment $C_x$ over a group $\mathbb{G}$ of prime order $q$.
One key difference that helps efficient modularity however is that in [BCFK19] $\mathbb{G}$ can be of standard size (e.g., 256 bits for 128 bits of security). This, we recall, means that other commit-and-prove systems that want to use $C_x$ do not need to suffer efficiency slowdowns due to inflated sizes of $\mathbb{G}$.
In terms of supported sets, both solutions in [BCFK19] allow more flexible choices of sets than the Camenisch-Lysyanskaya protocol: the first scheme supports the accumulation of sets whose elements are arbitrary binary strings, while in the second scheme elements are prime numbers of exactly $\mu$ bits (for various flexible choices of $\mu$).

Let us go even deeper and see how [BCFK19] achieves these improvements. In a nutshell, this is due to a new way to link a proof of membership for RSA accumulators to a Pedersen commitment in a prime order group, together with a careful analysis showing how this can be secure under parameters not requiring a larger prime order group.
For this post we only summarize the main idea for the scheme supporting sets of primes; we refer the interested readers to the paper for further details.

Let us recall the setting. The statement known to the verifier consists of an accumulator $A = G^{\prod_{i=1}^{n} e_i} \bmod N$, which is a commitment to a set $S = \{e_1, \ldots, e_n\}$, and of a Pedersen commitment $C_{e}$ in a group $\mathbb{G}$ of prime order $q$.
The goal of the prover is to argue knowledge of $(e, r)$ that open $C_e$, i.e., $C_{e} = g^{e} h^{r}$, and such that $e \in S$ where $A = \textsf{Acc}(S)$. This is achieved through a combination of the following:

• $C^{*}_e$, a commitment to $e$ created by the prover in the RSA group: $C^{*}_{e} = G^{e} H^{s} \bmod N$.
• $\Pi_{root}$, a ZKP of a committed root for $A$, i.e., a proof of knowledge of $e, s$ and $W$ such that
  $$W^{e} = A \bmod N \quad \textrm{and} \quad C^{*}_{e} = G^{e} H^{s} \bmod N.$$
• $\Pi_{modeq}$, a ZKP that $C^{*}_{e}$ and $C_{e}$ commit to the same value modulo $q$.
• $\Pi_{range}$, a ZKP that $C_{e}$ commits to an integer in the range $(2^{\mu-1}, 2^{\mu})$.

Intuitively, $\Pi_{root}$ shows that $C^*_{e}$ commits to an integer that is accumulated in $A$ (at this point, however, such integer may be a trivial root, i.e., $1$). The goal of $\Pi_{modeq}$ and $\Pi_{range}$ is to rule out this corner case $e=1$ and to “securely link” the commitment $C^*_e$ in the RSA group created by the prover with the prime-order group commitment $C_e$ known to the verifier, namely to ensure that these two commitment open to the same integer $e$.
This is less straightforward than expected because $\Pi_{modeq}$ is only able to prove that the equality of the values committed in $C^*_e$ and $C_e$ holds modulo $q$ and not necessarily over the integers. Also, from $\Pi_{root}$ alone, one can only infer that $C^*_{e}$ commits to some integer $e^*$ that divides $\prod_{i=1}^{n} e_i$.

So, the bad case that malicious provers may trigger and that the protocol must exclude is that $e^*$ and $e^* \bmod q$ are different over the integers. This can be shown with a quite detailed analysis whose basic idea is to use the fact that $\Pi_{root}$ nevertheless guarantees that $e^*$ can be the product of only few primes in $S$ (say 1, 2, depending on the difference between $\mu$ and $|q|$), and that $\Pi_{range}$ ensures that $e^* \bmod q$ lies in the range $(2^{\mu-1}, 2^{\mu})$.

To summarize, this technique enables linking the commitments in the RSA and prime-order group in an efficient way, and this enables to use this ZKP for set membership in combination with other SNARKs that are instantiated over the same prime-order group.

To conclude, in this post we went on a journey about the set membership problem. We started from seminal works (Merkle trees and RSA accumulators) that provide a solution to the scalability problem of set membership. Next, we went on to discuss solutions that allow one to maintain the privacy of the element involved in the set membership statement — a problem that is key in a number of applications from different domains, including finance, and business- or governmental-level interaction. Given the emergence of ZKP applications in the real-world, we expect that new solutions to the problem of privacy-preserving set membership will come out.