A More Efficient Approach to Zero Knowledge for PLONK
In PLONK (considered as an interactive oracle proof), the prover sends the verifier several polynomials. They are evaluated at some $k$ points during the course of the protocol. Of course, if we want zeroknowledge, we would require that those evaluations do not reveal anything about the proof’s underlying witness.
PLONK as described here achieves zero knowledge by multiplying the polynomials with a small degree polynomial of random coefficients. When PLONK is instantiated with a discretelog base Bootle et al type polynomial commitment scheme, the polynomial degrees must be padded to the nearest power of two. As a result, since several of the polynomials in PLONK already have degree equal to a power of two before the zeroknowledge masking, the multiplication with a random polynomial pushes the degree to the next power of two, which hurts efficiency. In order to avoid it, we propose an alternative method of achieving zero knowledge.
Zero Knowledge for the Column Polynomials
Let $w$ be the number of rows in a PLONK constraint system. For a typical realworld circuit, $w$ will not be equal to a power of two.
Let the witness elements from one column be $s_{1},s_{2},…,s_{w}$. Let $n$ be the closest power of two to $w$ such that $n≥w$. Let $F$ be the field that witness elements belong to.
Now, in vanilla PLONK, we pad the $s_{i}$ with $n−w$ elements, interpolate the polynomial over a domain of size $n$, scale it by a low degree random polynomial, and commit to the resulting polynomial. We want to avoid increasing the degree with the scaling by a low degree polynomial, so consider the following procedure.
Procedure. Sample $k$ elements uniformly from $F$: $r_{w+1},…,r_{w+k}$. Append them to the tuple of witness elements and then pad the remaining $n−(w+k)$ places as zeroes. The resulting tuple is interpolated as the witness polynomial. This approach ensures zero knowledge for the witness polynomials as established by Lemma 1.
Lemma 1. Let $H⊂F$ be a domain of size $n$. Let $s_{1},s_{2},…,s_{w}∈F$. Let $r_{w+1},…,r_{w+k}$ be $k$ uniformly and independently random elements in $F.$ Let $v$ be the $n$tuple $v=(s_{1},s_{2},…,s_{w},r_{w+1},…,r_{w+k},0,…_{n  (w+k) times})$. Let $f(X)$ be an interpolation polynomial of degree $n−1$ such that $f(h_{i})=v_{i}$, where $h_{i}∈H$. Let $c_{1},…,c_{k}$ be any elements in $F$ such that $c_{i}=v_{j}$ for every $i,j$. Then, $(f(c_{1}),…,f(c_{k}))$ is distributed uniformly at random in $F_{k}$.
Proof sketch. Recall that the interpolation polynomial is
$f(X)=∑_{j=1}∏_{k=j}(h_{j}−h_{k})(X−h_{k}) v_{j}$
With $V_{w+1},…,V_{w+k}$ as random variables, we have, $f(X)=a_{w+1}V_{w+1}+a_{w+2}V_{w+2}+…+a_{w+k}V_{w+k}+a$ for some constant field elements $a,a_{w+1},…,a_{w+k}$. Therefore, assigning random values to $V_{w+1},…,V_{w+k}$ will give $k$ degrees of freedom that will let $(f(c_{1}),…,f(c_{k}))$ to be distributed uniformly at random in $F_{k}$.
Zero Knowledge for the Permutation Polynomial
The other polynomial in PLONK for which we need zeroknowledge is the “permutation polynomial” $z$. The idea here is to set the last $k$ evaluations to be uniformly random elements $t_{1},…,t_{k}$ in $F$. Then, we’ll modify the verification equation to not check for those values to satisfy the permutation property.
Modified permutation polynomial. Specifically, set $z(X)$ as follows.
$z(X)=L_{1}(X)+∑_{i=1}(L_{i+1}∏_{j=1}frac_{i,j})+t_{1}L_{n−k}(X)+…+t_{k}L_{n}(X)$
From Lemma 1, the above $z(X)$ has the desired zero knowledge property when $k$ evaluations are revealed. However, we need to modify the other parts of the protocol so that the last $k$ elements are not subject to the permutation evaluation, since they will no longer satisfy the permutation check. Specifically, we will need to modify the permutation polynomial to disregard those random elements, as follows.
$ t(X)=(a(X)b(X)q_{M}(X)+a(X)q_{L}(X)+b(X)q_{R}(X)+c(X)q_{O}(X)+PI(X)+q_{C}(X))z_{H}(X)1 +((a(X)+βX+γ)(b(X)+βk_{1}X+γ)(c(X)+βk_{2}X+γ)z(X)(X−h_{n−k})…(X−h_{n−1})(X−h_{n}))z_{H}(X)α −((a(X)+βS_{σ1}(X)+γ)(b(X)+βS_{σ2}(X)+γ)(c(X)+βS_{σ3}(X)+γ)z(Xω)(X−h_{n−k})…(X−h_{n−1})(X−h_{n}))z_{H}(X)α +(z(X)−1)L_{1}(X)z_{H}(X)α_{2} +(z(X)−1)L_{n−k}(X)z_{H}(X)α_{3} $
Modified permutation checks. To recall, the permutation check was originally as follows. For all $h∈H$,
 $L_{1}(h)(Z(h)−1)=0$
 $Z(h)[(a(h)+βh+γ)(b(h)+βk_{1}h+γ)(c(h)+βk_{2}h+γ)]=Z(ωh)[(a(h)+βS_{σ1}(h)+γ)(b(h)+βS_{σ2}(h)+γ)(c(h)+βS_{σ3}(h)+γ)]$
The modified permuation checks that ensures that the check is performed only on all the values except the last $k$ elements in the witness polynomials are as follows.

For all $h∈H$, $L_{1}(h)(Z(h)−1)=0$

For all $h∈H∖{h_{n−k},…,h_{n}}$, $ Z(h)[(a(h)+βh+γ)(b(h)+βk_{1}h+γ)(c(h)+βk_{2}h+γ)]=Z(ωh)[(a(h)+βS_{σ1}(h)+γ)(b(h)+βS_{σ2}(h)+γ)(c(h)+βS_{σ3}(h)+γ)] $

For all $h∈H$, $L_{n−k}(h)(Z(h)−1)=0$
In the modified permutation polynomial above, the multiple $(X−h_{n−k})…(X−h_{n−1})(X−h_{n})$ ensures that the permutation check is performed only on all the values except the last $k$ elements in the witness polynomials.