# Non-index-revealing proof of membership in polynomial commitments A common primitive used in many ZK applications is the "non-index-revealing proof of membership": given a set $\{z_1 ... z_n\}$, prove that you know a secret $s_i$ that is somehow mathematically linked to $z_i$, without revealing which $z_i$ it is linked to. Importantly, the proving process should take much less than $O(n)$ time (or if it does, the $O(n)$ should be a single precomputation, and there should be an easy algorithm for updating the proof when the set changes). This is usually done with a ZK-SNARK over a Merkle branch. This post proposes a less prover-heavy approach based on polynomial commitments. ## Main ingredient: basic non-index-revealing proof of membership **Goal**: given a polynomial commitment $C$, prove that you know _some_ $z_i$ in the evaluation set of $C$, without revealing the coordinate $i$ where $C(\omega^i) = z_i$. This is useless by itself because typically in the above-mentioned use cases the data in $C$ is public and so revealing $z_i$ by itself also reveals the index because anyone can just scan the data for the index, but this will be a critical ingredient in the later schemes. **Construction**: basically, a blinded version of the standard proof of membership. Standard proof of membership: to prove $C(\omega^i) = z$, provide $Q = [\frac{C - z}{X - \omega^i}]$. The verifier verifies that $e(Q, [X - \omega^i]) = e([C - z], [1])$. (Notation note: square brackets mean "the polynomial commitment of the thing inside the brackets") Blinded proof of membership: provide $L = [aX - b]$ and $Q = [\frac{C-z}{aX - b}]$. Also provide a degree-proof to verify that $deg(L) \le 1$, and a degree-proof to prove $deg(Q) \le deg(P) - 1$ (and thereby proving $deg(L)$ precisely equals 1). This proof proves that $C(\frac{b}{a}) = z$ but without revealing $\frac{b}{a}$; instead, it only reveals $L$, a _commitment_ to $\frac{b}{a}$. ## Putting this into a useful proof But we don't want to reveal $z$ (and also, we want to verify that $\frac{b}{a}$ is in the right domain, ie. $(\frac{b}{a})^N = 1$). We satisfy both of these goals as follows. First, we don't run the above scheme directly on $C$. Instead, we run it on $R = C - I$, where $I$ is a fixed (per-prover) polynomial where $I(\omega^i) = z + 1$ (we'll assume that $-1$ is a banned value that never gets legitimately included into $C$). This allows us to just prove that $R(\frac{b}{a}) = -1$. The user makes a separate proof, proving that $I$ is only nonzero in two positions across the domain: (i) $\omega^i$, and (ii) $1$, a reserved index allowing the evaluation of $I$ there free rein for blinding (otherwise, you can discover $i$ from $I$ by enumeration).. This proof can be done easily with PLONK-style accumulator arguments: * Make a polynomial $W$ satisfying $W(x) \in \{0,1\}$ and $(1 - W(x)) * I(x) = 0$ (meaning, $W(x)$ = 1 where $I$ is nonzero, where $I(x)$ is zero $W(x)$ can be 0 or 1) * Make a polynomial $A_1$ (think: sum of evaluations of $W$) where $A_1(x * \omega) = A_1(x) + W(x)$. Verify that $A_1(1) = 0$, $A_1(\omega) = 1$ and $A_1(end\_coordinate) = 2$. * Add another polynomial $A_2(x)$ (think: polynomial that grabs the nonzero evaluation in $I$) which satisfies $A_2(x * \omega) = A_2(x) + I(x)$ and verify $A_2(\omega) = 0$. $A_2(end\_coordinate)$ should equal $z+1$ (remember that $z$ is hidden and never shown directly) Note that this proof is over $I$, not $P$, so while it costs $O(N)$ time to produce, it does not require updating when $P$ updates. To prove that $\frac{b}{a}$ is inside the evaluation domain, we add another polynomial $A_3$, and prove that it agrees with $L$ at $\{1, \omega\}$; that is, we provide $Q_2 = [\frac{A_3 - L}{(X - 1)(X - \omega)}]$. This means that $A_3$ must have $a-b$ and $a-\omega b$ as the first two evaluations. We then need to check the equations: * $A_3(\omega^2) = \frac{A_3(1) - A_3(\omega)}{\omega - 1}$ (so $A_3(\omega^2) = b$) * $A_3(\omega^3) = A_3(\omega) + \omega A_3(\omega^2)$ (so $A_3(\omega^3) = a$) * $A_3(\omega^4) * A_3(\omega^3) = A_3(\omega^2)$ (so $A_3(\omega^4) = \frac{b}{a}$) * $A_3(\omega x) = A_3(x)^2$ for $x \in \{\omega^4 ... \omega^{4+log(N)}\}$ (so $A_3(\omega^{5+log(N)}) = 1$ if and only if $\frac{b}{a}$ is a root of unity) These constraints can be verified using standard techniques: one creates a composite constraint $\sum_{i=1}^4 C_i(A_3(\omega^2 x), A_3(\omega x), A_3(x)) * I_i(x)$, where $C_1 ... C_4$ are the four constraints above and $I_1 ... I_4$ are indicator polynomials representing where the constraints apply. One checks that this composite constraint applies to $A_3$ by providing the commitment to $H(x) = \frac{C(A_3(\omega^2 x), A_3(\omega x), A_3(x))}{Z(x)}$, and opening the polynomials at a random point to prove correctness. ## Summary: proof components * $L = [aX - b]$ * Degree proof for $L$ * $Q$ * $I$: polynomial that is nonzero only at $1$ and at the $x_i$ coordinate (and at positions after the end coordinate) * $W$ and $A_1$: witnesses proving that $I$ is only nonzero at two positions, one of them $1$ * $A_2$: accumulator with the desired property $A_2(end\_coordinate) = z+1$ * Another set of polynomials to do computation on the $z$, depending on protocol (can be consistency checked against $A_2$ by providing $\frac{P_k - A_2}{X - end\_coordinate}$) * $A_3$, $Q_2$, $H$, plus openings $A_3(r), A_3(\omega r), A_3(\omega^2 r), Z(r), H(r)$: prove that $\frac{b}{a}$ is inside the subgroup ## Updating the proof Only $Q$ depends on $P$. Furthermore, one should be able to pre-compute with FFTs the delta to $Q$ that arises from a chance in $P$ at any coordinate. Users verifying proofs could store _only_ the commitment to $P$, as one can update the commitments to both $P$ and $Q$ without knowing either polynomial. Making multiple proofs proving different claims about $z$ requires only adjusting some $O(1)$ sized polynomials, and re-randomizing $A_2$ for blinding purposes (which can be done with $O(1)$ modifications). Hence, all required ongoing steps should be doable in far less than linear time per update.