GKR Input Layer

We have now seen that a GKR interactive proof begins with the prover making a claim ${\tilde{V}}_0(r_1^{(0)},...,r_n^{(0)})=c_0$ on the layered circuit's output layer ${\tilde{V}}_0$ and reducing this claim via sumcheck and claim aggregation to claims on layers closer to the circuit's input layer, e.g. ${\tilde{V}}_1(r_1^{(1)},...,r_n^{(1)})=c_1$.

At the end of this process, we should be left with only claims on input layer(s), e.g.

$$\begin{gathered} {\tilde{V}}_d(r_1^{(d,1)},...,r_n^{(d,1)})=c_d^{(1)} \\ {\tilde{V}}_d(r_1^{(d,2)},...,r_n^{(d,2)})=c_d^{(2)} \\ ⋮ \\ {\tilde{V}}_d(r_1^{(d,m)},...,r_n^{(d,m)})=c_d^{(m)} \end{gathered}$$

These claims are optionally aggregated via interpolative claim aggregation (note that RLC claim aggregation does not work for input layer claims; see here for more details) into a single claim

$${\tilde{V}}_d(r_1^{\star },...,r_n^{\star })=c_d^{\star }$$

which the verifier must check on its own, optionally with help from the prover. There are several types of input layers, and we describe the methodology for each.

Public Inputs

Public input layers are circuit inputs where the prover sends the values to the verifier in the clear. In particular, this means that the verifier knows the full set of evaluations of ${\tilde{V}}_d$ over $\{0,1{\}}^n$ and can evaluate the MLE on its own. Thus:

• Before the prover generates the output layer claim challenges ($r_1^{(0)},...,r_n^{(0)}$ above), they send these evaluations to the verifier by absorbing them into the transcript.
• When the verifier is ready to check the claim ${\tilde{V}}_d(r_1^{\star },...,r_n^{\star })=c_d^{\star }$, they use the aforementioned evaluations to directly evaluate ${\tilde{V}}_d$ at $r_1^{\star },...,r_n^{\star }$ and check that the evaluation is indeed the claimed $c_d^{\star }$.

Committed Inputs

Committed input layers are circuit inputs where the prover sends a commitment to the values (generally as a polynomial commitment). Committed inputs are not directly revealed to the verifier (although they may leak information unless a zero-knowledge polynomial commitment scheme, like Hyrax, is used), and thus the prover must additionally help the verifier when they wish to check the input claim ${\tilde{V}}_d(r_1^{\star },...,r_n^{\star })=c_d^{\star }$ by providing an evaluation proof, which roughly shows that the polynomial which the prover committed to earlier actually evaluates to $c_d^{\star }$ at the evaluation point $r_1^{\star },...,r_n^{\star }$.

(See KZG10, page 6, and Tha24, page 188 for more details). Let $\lambda \in \mathbb{N}$ be the security parameter. Let ${\tilde{V}}_d\in {\mathbb{F}}^{<2}[X_1,...,X_n]$ be the MLE which the prover wishes to commit to. Let $r_1^{\star },...,r_n^{\star }\in {\mathbb{F}}^n$ be the evaluation point, and let $c_d^{\star }$ be the claimed value. Roughly speaking, a polynomial commitment scheme (PCS) consists of the following four functions:

• $\text{KeyGen}:\lambda \mapsto \{\text{ck},\text{vk}\}$. $\text{ck}$ here is the commitment key which the prover has access to while committing and generating evaluation proofs, and $\text{vk}$ here is the verification key which the verifier has access to while checking an evaluation proof. This function takes in a single security parameter $\lambda$ such that the resulting commitment scheme has roughly $\lambda$ bits of soundness.
• $\text{Commit}:\text{ck},{\tilde{V}}_d\mapsto \mathrm{com}$. The $\text{Commit}$ function takes in an MLE (for our purposes; in general this can be a univariate or multivariate polynomial of higher degree) and generates a commitment to be sent to the verifier.
• $\text{Eval}:\text{ck},\mathrm{com},r_1^{\star },...,r_n^{\star },c_d^{\star }\mapsto \pi$. The $\text{Eval}$ function takes in an evaluation point $r_1^{\star },...,r_n^{\star }\in {\mathbb{F}}^n$ and produces an evaluation proof $\pi$ that the original polynomial which was committed to in $\mathrm{com}$ actually evaluates to $c_d^{\star }$. Note that the verifier uses $\text{vk}$ to check the evaluation proof $\pi$.
• $\text{Open}:\mathrm{com},f\in {\mathbb{F}}^{<2}[X_1,...,X_n]\mapsto \{0,1\}$. The $\text{Open}$ function takes in a commitment and an MLE $f$ and outputs whether that MLE is the one committed to by $\mathrm{com}$, i.e. whether $f={\tilde{V}}_d$.

In addition to the above, a commitment scheme must satisfy hiding and evaluation binding.

• Hiding implies that given a commitment $\mathrm{com}$ and fewer than $2^n$ evaluation pairs, an adversary cannot determine the evaluation ${\tilde{V}}_d(h_1,...,h_n)$ for a point $h_1,...,h_d$ not in the set of evaluation pairs.
• Evaluation binding implies that given an evaluation point $r_1^{\star },...,r_n^{\star }$ and a claimed value $c_d^{\star }\ne {\tilde{V}}_d(r_1^{\star },...,r_n^{\star })$, a prover should be able to produce an accepting evaluation proof $\pi$ for generated $\mathrm{com}$ with negligible probability.

In general, we run $\text{KeyGen}$ once and distribute the resulting $\text{ck},\text{vk}$ to the prover and verifier, and focus on the $\text{Commit}$ and $\text{Eval}$ functions. During the interactive GKR protocol, the prover and verifier do the following:

• The prover invokes the $\text{Commit}$ functionality on ${\tilde{V}}_d$ and sends the resulting $\mathrm{com}$ to the verifier. They send this value to the verifier before any claims on output layers (including challenges) are generated. Note that this takes the place of the prover sending the evaluations of ${\tilde{V}}_d$ in the public inputs section above.
• After the prover has sent all circuit inputs to the verifier in either committed or direct evaluation form, the verifier generates the output claim challenges and the prover and verifier engage in the GKR claim reduction protocols until we're left with a single claim ${\tilde{V}}_d(r_1^{\star },...,r_n^{\star })=c_d^{\star }$.
• The prover then invokes the $\text{Eval}$ functionality on $\mathrm{com}$ and the aforementioned $r_1^{\star },...,r_n^{\star },c_d^{\star }$ values to produce evaluation proof $\pi$, which the verifier receives and checks.

Remainder's GKR prover uses a non-ZK version of the PCS implicit in AHIV17 (also explicitly described in the GLS+21 paper as Shockwave), which we briefly detail in our documentation's Ligero PCS page. Remainder's Hyrax prover uses the ZK PCS explicitly described within WTS+17, which we briefly detail in our documentation's Hyrax PCS page.

"Fiat-Shamir" Inputs

A third type of circuit "input" is that of a "Fiat-Shamir" challenge value. These inputs are different from the others in the sense that the prover does not supply them at all, but rather the (interactive) verifier sends them after the prover has committed to all other input values. These values are used when the circuit itself is computing a function which requires a random challenge (see LogUp, e.g., for one usage of such challenges). In general, claims on these layers are checked via the following:

• First, as mentioned, the (interactive) prover sends all other inputs (both public and committed) to the verifier.
• Next, the verifier sends random values (we can view these as the evaluations of ${\tilde{V}}_d$ over $\{0,1{\}}^n$) to the prover as challenge values.
• When the verifier needs to check a claim ${\tilde{V}}_d(r_1^{\star },...,r_n^{\star })=c_d^{\star }$ on the Fiat-Shamir input layer, it can do so by simply referencing the evaluations it generated earlier to evaluate ${\tilde{V}}_d$ at $r_1^{\star },...,r_n^{\star }$ and ensure that the evaluation is actually $c_d^{\star }$, exactly as is the case for public inputs.