Linearisation Polynomial Example

Let's say we want to constuct a proof system for \(h_{in1}(X)h_{in2}(X) = h_{in3}(X)\)

First, prover adds the zk souce. Samples \(r0, r1, r2\) and computes,

\(h_1(X) = r0 * Z_H(X) + h_{in1}(X)\)
\(h_2(X) = r1 * Z_H(X) + h_{in2}(X)\)
\(h_3(X) = r2 * Z_H(X) + h_{in3}(X)\)

Where \(Z_H(X)\) is the vanishing polynomial.

Naive system

Prover

Commits to the input polynomials,

\(H_1 = com(h_1(X))\)
\(H_2 = com(h_2(X))\)
\(H_3 = com(h_3(X))\)

Compute quotient polynomial and commits,

\(t(X) = \frac{h_1(X)h_2(X) - h_3(X)}{Z_H(X)}\)

\(T = com(t(X))\)

Computes challenge \(z\) and evaluate input and quotient polynomials,

\(h_1 = h_1(z)\)
\(h_2 = h_2(z)\)
\(h_3 = h_3(z)\)
\(t = t(z)\)

Computes challenge \(v\) and compute witness and commits,

\(w(X) = \frac{(t(X) - t) + v(h_1(X) - h_1) + v^2(h_2(X) - h_2) + v^3(h_3(X) - h_3)}{X - z}\)

\(W = com(w(X))\)

Sends proof to the Verifier

\(\pi = (H_1, H_2, H_3, h_1, h_2, h_3, W, T)\)

Verifier

Computes quotient evaluation,

\(t = \frac{(h_1h_2 - h_3)}{Z_h(z)}\)

Computes batch commitment,

\(F = T + v * H_1 + v^2 * H_2 + v^3 * H_3\)

Computes batch evaluation point,

\(E = (t + vh_1 + v^2h_2 + v^3h_3) * G\)

And checks,

\(e(W, X) \stackrel{?}{=} e(z * W + F - E, G)\)

Optimized

Prover

Commits to the input polynomials,

\(H_1 = com(h_1(X)) \\ H_2 = com(h_2(X)) \\ H_3 = com(h_3(X))\)

Computes challenge \(z\) and evaluate only \(h_1\),

\(h_1 = h_1(z)\)

Compute quotient polynomial and commit,

\(t(X) = \frac{h_1(X)h_2(X) - h_3(X)}{Z_H(X)}\)

\(T = com(t(X))\)

Computes linearisation polynomial,

\(r(X) = h_1 * h_2(X) - h_3(X)\)

\(r = r(z)\)

Computes challenge \(v\) and compute witness and commits,

\(w(X) = \frac {(t(X) - t) + v(r(X) - r) + v^2(h_1(X) - h_1)} {X - z}\)

\(W = com(w(X))\)

Sends proof to the Verifier.

\(\pi = (H_1, H_2, H_3, h_1, r, W, T)\)

Verifier

Computes quotient evaluation,

\(t = r / Z_h(z)\)

Computes batch commitment,

\(R = h_1 * H_2 + H_3\)

\(F = T + v * R + v^2 * H_1\)

Computes batch evaluation point,

\(E = (t + vr + v^2h_1) * G\)

And checks.

\(e(W, X) \stackrel{?}{=} e(z * W + F - E, G)\)

Cost

In optimized version

• Proof size reduced by 1 field element.
• 1 group addition is saved