Adding zero knowledge to Plonk-Halo

The Plonk paper describes how to achieve zero knowledge, but lacks a proof. We will show that their method indeed achieves zero knowledge, then describe another blinding method which is more suitable for Halo-style polynomial commitments.

Preliminaries

We will assume that our polynomial commitments are hiding, so we are only concerned about openings leaking witness information, not about commitments.

For some $S \subseteq [1 \twodots H]$, let $L_S(x)$ be the unique polynomial in $\mathbb{F}_{<|H|}[x]$ defined by $$ L_S(g^i) = \begin{cases} 1 & \text{if } i \in S, \\ 0 & \text{otherwise}, \end{cases} $$ or equivalently, $$ L_S(x) = \sum_{i \in S} L_i(x), $$ where $L_i(x)$ is defined as in the Plonk paper.

Plonk's blinding scheme

Let $s(x) \in \mathbb{F}_{<d}[x]$ be a secret witness polynomial. Let $C = \{ c_1, \dots, c_k \}$ be our challenge points, drawn from some challenge space $\mathbb{C} \subseteq \mathbb{F}$.

Let $b(x)$ be a blinding polynomial, selected uniformly at random from $\mathbb{F}_{< k}[x]$. The Plonk paper suggests combining $s$ and $b$ like so: $$ s'(x) = s(x) + b(x) Z_H(x). $$ Notice that $s$ and $s'$ agree on $H$, so we can substitute $s'$ for $s$ in the remainder of the protocol without breaking any constraints.

Does opening $s'$ at $C$ leak information about $s$? If some $c_i \in H$, then it clearly does: the blinding term vanishes, leaving us with $s'(c_i) = s(c_i)$. Under an honest verifier assumption, this happens with a negligible $|\mathbb{C} \cap H| / |\mathbb{C}|$ probability. If we wish to achieve perfect zero knowledge, we can choose $\mathbb{C} \subseteq \mathbb{F} \setminus H$, making this probability zero.

Assuming $c_i \notin H$, we know $Z_H(c_i) \ne 0$, so we can write $$ b(c_i) = \frac{s'(c_i) - s(c_i)}{Z_H(c_i)}. $$ For a given secret polynomial $s$, each possible opening set $\left( s'(c_1), \dots, s'(c_k) \right)$ is produced by exactly one choice of $b$, namely the unique degree $<k$ interpolant of $\left( b(c_1), \dots, b(c_k) \right)$ as expressed above. Since each $s$ produces the same (uniform) probability ensemble of opening sets, it follows that $\left( s'(c_1), \dots, s'(c_k) \right)$ reveal nothing about $s$.

Blinding in the Halo setting

The scheme described above does not work well with Halo-style polynomial commitments, since Halo deals with power-of-two-degree polynomials, and $\deg(s') = |H| + \deg(b)$ would slightly exceed a power of two.

We can instead append blinding factors to each witness polynomial in Lagrange basis form, before they are padded to a power of two. Let $s$ be a witness polynomial consisting of $n$ witness elements followed by several zeros (from padding). The blinded polynomial $s'$ can then be expressed as $$ s'(x) = s(x) + b(x) L_{[d+1 \twodots d+k]}(x). $$ Since the degree of $L_{[d+1 \twodots d+k]}(x)$ is $|H| - 1$, it has at most $|H| - 1$ roots. As before, we can choose a $\mathbb{C}$ disjoint from this root set, or argue that $C$ is unlikely to contain a root under an honest verifier assumption. Then, for $c_i \in C$, we can write $$ b(c_i) = \frac{s'(c_i) - s(c_i)}{L_{[d+1 \twodots d+k]}(c_i)}. $$ We can now apply the interpolation argument from the previous section, which establishes that a set of openings $\left( s'(c_1), \dots, s'(c_k) \right)$ reveals no information about $s$.

Blinding Z

The polynomial involved in Plonk's permutation argument, $Z$, would also leak information about the witness if opened directly. We cannot simply append blinding factors to $Z$'s point-value form, as that would break the $Z(a) f'(a) = g'(a) Z(a g)$ check.

To blind $Z$ while maintaining the validity of our proof, we can append $k$ pairs of points, where each pair contains the same random value. (This is in addition to the random points added in the previous section.) We then add a copy constraint for each such pair, which creates a corresponding 2-cycle in $\sigma$, and effectively randomizes an entry of $Z$.

To prove zero knowledge, we must understand the behavior of $Z$ in relation to $\sigma$. We start with the following property:

Lemma 1. If the restriction of $\sigma$ to $[1 \twodots i-1]$ is a permutation, then $Z(g^i) = 1$.

Proof. Let $S = [1 \twodots i-1]$ and $\pi = \sigma{\restriction_S}$. Notice that the expression defining $Z$ can be rewritten as $$ Z(g^i) = \prod_{j \in S} \frac{w(j)}{w(\pi(j))} = \frac{\prod_{j \in S} w(j)}{\prod_{j \in S} w(\pi(j))}, $$ where $w(j) = f(g^j) + \beta j + \gamma$.

If $\pi$ is a permutation, then $\pi(S) = S$ and thus $w(\pi(S)) = w(S)$, so the numerator and denominator above are equal.

Let $f'$, $\sigma'$ and $Z'$ be our updated versions of $f$, $\sigma$ and $Z$, respectively. To simplify notation, let's fix $k = 2$.

We sample random $b_1, b_2 \in \mathbb{F}$, then set $f'(g^{d + 3}) = f'(g^{d + 4}) = b_1$ and $f'(g^{d + 5}) = f'(g^{d + 6}) = b_2$. (We start at $g^{d + 3}$ because $g^{d+1}$ and $g^{d+2}$ were used in the previous section.) We then create a copy constraint for each pair, resulting in the following 2-cycles in $\sigma'$: $$ \begin{aligned} \sigma'(d+3) &= d+4, & \sigma'(d+4) &= d+3, \\ \sigma'(d+5) &= d+6, & \sigma'(d+6) &= d+5. \end{aligned} $$

Next, we will show that $Z$ and $Z'$ agree on $H$ except at two points:

Lemma 2. For $i \notin \{ d + 4, d + 6 \}$, $Z(g^i) = Z'(g^i).$

Proof. We know that $\sigma{\restriction_{[1 \twodots d]}}$ and $\sigma'{\restriction_{[1 \twodots d]}}$ are permutations, since they contain all cycles related to circuit wiring, and nothing more. So by Lemma 1, $Z(g^{d + 1}) = Z'(g^{d + 1}) = 1$.

Any restriction of $\sigma$ to a superset of $[1 \twodots d]$ must also be a permutation, since $f$ contains only zero-padding at indices beyond $d$. Since the zero entries are not subject to any copy constraints, they are fixed points of $\sigma$, so injectivity is maintained. By Lemma 1, $Z(g^{d + 1}) = Z(g^{d + 2}) = \ldots = Z(g^{|H|}) = 1$.

By similar logic, $\sigma'{\restriction_{[1 \twodots d + 2]}}$ is a permutation, since $d + 1$ and $d + 2$ are the indices of the blinding factors added in the previous section, and we did not add any copy constraints involving those points. By Lemma 1, $Z'(g^{d + 3}) = 1$.

We know that $\sigma'{\restriction_{[d + 3 \twodots d + 4]}}$ and $\sigma'{\restriction_{[d + 5 \twodots d + 6]}}$ are permutations, since they are cycles as we established above. Since a union of disjoint permutations is itself a permutation, $\sigma'{\restriction_{[1 \twodots d + 4]}}$ and $\sigma'{\restriction_{[1 \twodots d + 6]}}$ are also permutations. By Lemma 1, $Z'(g^{d + 5}) = Z'(g^{d + 7}) = 1$. Subsequent points of $Z'$ are also 1, since they correspond to zero-padded entries.

We know $Z(g^i) = Z'(g^i)$ for $i \le d + 1$ since the blinding factors do not appear until $d + 1$. For all other points except $d + 4$ and $d + 6$, we have shown that $Z(g^i) = 1$ and $Z'(g^i) = 1$, implying $Z(g^i) = Z'(g^i)$.

Next, let's examine the values of $Z'$ at these two interesting points: $$ \begin{aligned} Z'(g^{d+4}) &= \frac{f(g^{d + 3}) + \beta (d + 3) + \gamma}{f(g^{\sigma'(d + 3)}) + \beta \sigma'(d + 3) + \gamma} &= \frac{f(g^{d + 3}) + \beta (d + 3) + \gamma}{f(g^{d + 4}) + \beta (d + 4) + \gamma} &= \frac{b_1 + \beta (d + 3) + \gamma}{b_1 + \beta (d + 4) + \gamma}, \\ Z'(g^{d+6}) &= \frac{f(g^{d + 5}) + \beta (d + 5) + \gamma}{f(g^{\sigma'(d + 5)}) + \beta \sigma'(d + 5) + \gamma} &= \frac{f(g^{d + 5}) + \beta (d + 5) + \gamma}{f(g^{d + 6}) + \beta (d + 6) + \gamma} &= \frac{b_2 + \beta (d + 5) + \gamma}{b_2 + \beta (d + 6) + \gamma}. \end{aligned} $$ Since $Z'(g^i) = Z(g^i)$ on the rest of $H$, we can write $Z'$ as $$ \tag{1} Z'(x) = Z(x) + L_{ \{ d+4, d+6 \} }(x) \left( m(x) - 1 \right), $$ where $m$ is the unique polynomial in $\mathbb{F}_{<2}[x]$ satisfying $$ \tag{2} m(g^{d+4}) = \frac{b_1 + \beta (d + 3) + \gamma}{b_1 + \beta (d + 4) + \gamma}, $$ $$ \tag{3} m(g^{d+6}) = \frac{b_2 + \beta (d + 5) + \gamma}{b_2 + \beta (d + 6) + \gamma}. $$ Assuming $L_{ \{ d+4, d+6 \} }(c_i) \ne 0$ (which, as before, can be enforced by our choice of $\mathbb{C}$), we can rearrange Equation 1 to get $$ \tag{4} m(c_i) = \frac{Z'(c_i) - Z(c_i) }{L_{ \{ d+4, d+6 \} }(c_i)} + 1. $$ Finally, we can argue that each $Z$ produces the same distribution of opening sets. For a fixed $Z$, each opening set $\left( Z'(c_1), Z'(c_2) \right)$ is compatible with exactly one $m$, namely the unique degree $<2$ interpolant of $\left( m(c_1), m(c_2) \right)$ as expressed in Equation 4. Each $m$ is produced by exactly one choice of $(b_1, b_2)$, namely the one obtained by solving Equations 2 and 3 for $b_1$ and $b_2$. Since we have a uniform ensemble of opening sets regardless of $Z$, the opening set reveals no information about $Z$.

Thanks

Thanks to Nat Bunner for pointing out a significant error in an earlier version of this post.