Adding zero knowledge to Plonk-Halo

Daniel Lubarov · 2020-10-09

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.

Let $L_{[a \twodots b]}(x)$ be the unique polynomial in $\mathbb{F}_{<|H|}[x]$ defined by $$ L_{[a \twodots b]}(x) = \begin{cases} 1 & \text{if } x \in \{ g^a, \dots, g^b \}, \\ 0 & \text{for other } x \in H, \end{cases} $$ or equivalently, $$ L_{[a \twodots b]}(x) = \sum_{i=a}^b 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 $d$ 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 + 1$ random points to each witness polynomial (in addition to the $k$ from the previous section), then add a copy constraint involving all $k + 1$ points. This has the effect of randomizing $k$ entries of $Z$.

To simplify notation, let's fix $k = 2$. We already added blinding factors to each witness polynomial at $g^{d+1}$ and $g^{d+2}$ (as described in the previous section), so now we add blinding factors at $g^{d+3}$, $g^{d+4}$ and $g^{d+5}$. The copy constraint creates a 3-cycle in our permutation $\sigma$:

$$ \begin{aligned} \sigma(g^{d+3}) &= g^{d+4}, \\ \sigma(g^{d+4}) &= g^{d+5}, \\ \sigma(g^{d+5}) &= g^{d+3}. \end{aligned} $$ Based on the definition of $Z$, we have $$ \begin{aligned} Z'(g^{d+3}) &= Z(g^{d+3}) \left( \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{\sigma(d+3)}) + \beta \sigma(d+3) + \gamma} \right) \\ &= Z(g^{d+3}) \left( \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{d+4}) + \beta (d+4) + \gamma} \right), \\ Z'(g^{d+4}) &= Z(g^{d+4}) \left( \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{\sigma(d+3)}) + \beta \sigma(d+3) + \gamma} \right) \left( \frac{b(g^{d+4}) + \beta (d+4) + \gamma}{b(g^{\sigma(d+4)}) + \beta \sigma(d+4) + \gamma} \right) \\ &= Z(g^{d+4}) \left( \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{d+4}) + \beta (d+4) + \gamma} \right) \left( \frac{b(g^{d+4}) + \beta (d+4) + \gamma}{b(g^{d+5}) + \beta (d+5) + \gamma} \right) \\ &= Z(g^{d+4}) \left( \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{d+5}) + \beta (d+5) + \gamma} \right), \\ Z'(g^{d+5}) &= Z(g^{d+4}) \left( \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{\sigma(d+3)}) + \beta \sigma(d+3) + \gamma} \right) \left( \frac{b(g^{d+4}) + \beta (d+4) + \gamma}{b(g^{\sigma(d+4)}) + \beta \sigma(d+4) + \gamma} \right) \left( \frac{b(g^{d+5}) + \beta (d+5) + \gamma}{b(g^{\sigma(d+5)}) + \beta \sigma(d+5) + \gamma} \right) \\ &= Z(g^{d+4}) \left( \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{d+4}) + \beta (d+4) + \gamma} \right) \left( \frac{b(g^{d+4}) + \beta (d+4) + \gamma}{b(g^{d+5}) + \beta (d+5) + \gamma} \right) \left( \frac{b(g^{d+5}) + \beta (d+5) + \gamma}{b(g^{d+3}) + \beta (d+3) + \gamma} \right) \\ &= Z(g^{d+5}). \end{aligned} $$ So, $Z'$ diverges from $Z$ at $g^{d+3}$ and $g^{d+4}$, then converges again at $g^{d+5}$. For inputs in $H$, we can write $Z'$ as $$ Z'(g^i) = \begin{cases} Z(g^i) m(g^i) & \text{if } i \in [ d+3 \twodots d+4 ], \\ Z(g^i) & \text{otherwise}, \end{cases} $$ or, moving to arbitrary $x \in \mathbb{F}$, we can write $$ \tag{1} Z'(x) = Z(x) \left(1 + L_{[ d+3 \twodots d+4 ]}(x) (m(x) - 1) \right), $$ where $m$ is the unique polynomial in $\mathbb{F}_{<2}[x]$ satisfying $$ \tag{2} m(g^{d+3}) = \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{d+4}) + \beta (d+4) + \gamma}, $$ $$ \tag{3} m(g^{d+4}) = \frac{b(g^{d+3}) + \beta (d+3) + \gamma}{b(g^{d+5}) + \beta (d+5) + \gamma}. $$ Note that there are only $|\mathbb{F}^*|^2$ possible $m$, not $|\mathbb{F}|^2$. The denominators cannot be zero, as that would cause the prover to abort, and the numerator cannot be zero, since each numerator has a matching denominator in $Z'$.

Assuming $Z(c_i) \ne 0$ and $L_{[ d+3 \twodots d+4 ]}(c_i) \ne 0$, we can rearrange Equation 1 to get $$ \tag{4} m(c_i) = \frac{Z'(c_i) / Z(c_i) - 1}{L_{[ d+k+1 \twodots d+2k ]}(c_i)} + 1. $$ As before, $L_{[ d+3 \twodots d+4 ]}(c_i) \ne 0$ can be enforced by our choice of $\mathbb{C}$, but the case of $Z(c_i) = 0$ is more difficult. If we are satisfied with statistical zero knowledge, we can simply argue that an honest verifier will not select a root of $Z$ except with negligible probability. If we are using Fiat-Shamir, we can maintain perfect zero knowledge by aborting in cases where $Z(c_i) = 0$.

With those edge cases out of the way, 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. From Equations 2 and 3, we can see that each $m$ is produced by $|\mathbb{F}^*|$ choices $b$, so each opening set is likewise produced by $|\mathbb{F}^*|$ choices $b$. Since we have a uniform ensemble of opening sets regardless of $Z$, the opening set reveals no information about $Z$.

Relaxing the honest-verifier assumption

In some of the scenarios above, we argued statistical zero-knowledge from an assumption that an honest verifier will sample each $c_i \in \mathbb{C}$ uniformly. In the random oracle model, we can compile such an honest-verifier argument of knowledge into a non-interactive argument of knowledge using the Fiat-Shamir transform. But what if we want to avoid a random oracle assumption?

If we are willing to use interaction, we can use the following compiler. Instead of the verifier sampling $c_i \in \mathbb{C}$, we have the prover sample $p_i$ while the verifier samples $v_i$. The prover sends $\operatorname{Commit}(p_i)$ while the verifier sends $\operatorname{Commit}(v_i)$ (in either order), then both parties open their commitments.

The result is $c_i = f(p_i, v_i)$, where $f: \mathbb{C}^2 \rightarrow \mathbb{C}$ is any function with the property that partial application of either argument produces a permutation of $\mathbb{C}$. (If $\mathbb{C} = \mathbb{F}$, we can simply use $f(p_i, v_i) = p_i + v_i$.) This ensures that $c_i$ is unpredictable to both parties until the opening phase, at which point both parties are bound to their contributions.