Multilinear polynomial KGZ10 commitment with linear pairing check
Let f(\mathbf{x}) is a multilinear function.
\text{kzg10_comm}(f) = [f(\mathbf{s})], where \mathbf{s}=\{s, s^2, s^4, ...\ s^{2^{n-1}}\}, s is KZG10 secret multiplier, [] is representation as G_1 group element.
To make opening at \mathbf{t} = \{t_0, t_1, ...\ t_{n-1}\}, let’s consider \mathbf{t}_{(k)}=\{t_0, ...\ t_{k-1}, s^{2^k}, ...\ s^{2^{n-1}}\}, \mathbf{x}_{(k)}=\{t_0, ...\ t_{k-1}, x^{2^k}, s^{2^{k+1}} ...\ s^{2^{n-1}}\}.
Then f(\mathbf{x}_{(k)}) - f(\mathbf{t}_{(k+1)}) = q_k(x) (x^{2^k}-t_{k}), where q_k(x) is quotent polynomial.
These equations could be verified via pairing check:
e([f(\mathbf{t}_{(k)})] - [f(\mathbf{t}_{(k+1)}], [1]_2) = e([q_{k+1}], [s^{2^k}-t_k]_2)).
The issue is that if we do the multilinear sum, we get a bilinear expression in the pairing check on the right side, which is not recursion friendly. For recursion we need something like e(A, [1]_2) = e(B, [s]_2).
Let’s consider
r_k(x) = f(\mathbf{x}_{(k)}) - f(\mathbf{t}_{(k+1)}) + q_k(x) t_k.
Notice, that
r_k(s) = f(\mathbf{t}_{(k)}) - f(\mathbf{t}_{(k+1)}) + q_k(s) t_k.
Then it’s enough to check q_k x^{2^k} - r_k = 0, using random linear combination with opening at random point y and factor l:
\sum_k l^k \left( q_k x^{2^k} - r_k \right) = 0,
e(\sum_k l^k \left( y^{2^k} [q_k(s)] - [r_k(s)] \right), [1]_2) = e([Q(s)], [s-y]),
e(\sum_k l^k \left( y^{2^k} [q_k(s)] - [r_k(s)] \right)+ y [Q(s)], [1]_2) = e([Q(s)], [s]).
The last expression could be used in the original PLONK recursion because it is a linear check.