Understanding Interactive Proof Systems and Sum Check Protocol: Part 1

· Cryptography & Blockchain

In computational complexity theory, an interactive proof system is an abstract machine that models computation as exchanging messages between two parties: a prover* and a *verifier. The parties interact by exchanging messages to ascertain whether a given string") belongs to a language. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has “convinced” itself that it is correct.

This article will teach you how such a system works at a mathematical level and lay the foundation for a new area of research namely “Zero-Knowledge Proofs”.

#### Some terms to know before we continue further:

1. Commitment scheme:

In cryptography, a commitment scheme is a fundamental concept that allows one party to commit to a chosen value (or chosen statement) while keeping it hidden from others, with the ability to reveal the committed value later. Commitment schemes are designed to be binding and hiding:

* Binding: This property ensures that the committing party cannot change a value once a value has been committed. In other words, it’s impossible (or computationally infeasible) for the committer to find another value they can convincingly claim to have committed to originally. * Hiding: This property ensures that the value remains secret until the committer chooses to reveal it. Before the reveal, no other party can determine the committed value.

2\. Function commitments :

* Polynomial Commitments: commitments to functions of type:

P(x_1, \dots, x_k) = \sum_{i_1, \dots, i_k} c_{i_1, \dots, i_k} x_1^{i_1} \dots x_k^{i_k}

Generalized Polynomial Expression

* Multilinear Commitments: commitments to functions of type $f(x_1, \dots, x_k)$

f(x_1, \dots, x_k) = \sum_{e \in \{0, 1\}^k} c_e \prod_{j=1}^k x_j^{e_j}

Generalized Multilinear Expression

* Vector commitments: eg. Merkle trees.

\vec{v} = (v_1, v_2, \dots, v_n)

Example Expression for Vector

3\. SZDL Lemma:

Schwartz-Zippel-Demillo-Lipton lemma is a multivariate generalization of fact:

* Let $p \neq q$ be a univariate polynomial of degree at most $d$. Then \Pr_{r \in F} [p(r) = q(r)] \le \frac{d}{|F|}

* SZDL: Let $p \neq q$ be $l$-variate polynomials of total degree at most $d$. Then \Pr_{r \in F^l} [p(r) = q(r)] \le \frac{d}{|F|}

* “Total degree” refers to the maximum sum of degrees of all variables in any term.

Sum-Check Protocol

The Sum-Check Protocol is a fundamental technique in theoretical computer science, particularly in the field of interactive proof systems and complexity theory. It’s often used to prove properties about polynomials and is a key component in constructing various interactive proofs, including those for NP-complete problems.

Input: $V$ given Oracle access to an $l$-variate polynomial $g$ over field $F$.

Goal: The goal is to verify a claim about the sum of values of a multivariate polynomial i.e. compute the expression:

H = \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \dots \sum_{x_l \in \{0,1\}} g(x_1, \dots, x_l)

Generalized Expression to compute in Sum-Check protocol

Computing the above expression is expensive, and hence the verifier uses interactive proof to verify the result of the expression that the prover returns ( after computing the given expression ).

Protocol Steps:

* Initialization:  The prover wants to convince the verifier that the sum of the polynomial $g$ over a specified domain is a certain value $S$. * In each round, the prover sends a claim about the sum of a certain polynomial. The verifier checks the claim at a randomly chosen point and asks the prover for a new claim about a related, but simpler polynomial (typically, by fixing one variable). This process is repeated for each variable of $P$. * $P$ (prover) sends claimed answer $C_1$. The protocol must check if $C_1 = H$ (where variables are in $\{0,1\}$):

C_1 = \sum_{x_1, \dots, x_l \in \{0,1\}} g(x_1, \dots, x_l)

* Round 1: $P$ sends a univariate polynomial $S_1(X_1)$ claimed to equal:

H_1(X_1) = \sum_{x_2, \dots, x_l \in \{0,1\}} g(X_1, x_2, \dots, x_l)

* The verifier needs to check 2 things:  1\. Does $S_1$ equal $H_1$? 2\. Even if $S_1 = H_1$, is that consistent with the claimed answer $C_1$? * Verifier checks: 1\. $C_1 = S_1(0) + S_1(1)$ 2\. Now to check $S_1$ and $H_1$, the verifier simply checks if $S_1$ and $H_1$ agree at a random point $r_1$. $S_1$ is easy to calculate at $r_1$ since the prover explicitly sends the polynomial to the verifier. But evaluating $H_1(r_1)$ is hard to calculate for the verifier. To address this, $V$ picks $r_1$ at random from $F$ and sends $r_1$ to $P$. * Round 2: To address the issue of how to calculate $H_1(r_1)$, the verifier recursively checks that $S_1(r_1) = H_1(r_1)$. We utilize the form of expression that $H_1$ has by using the following relation:

H_1(r_1) = \sum_{x_2 \in \{0,1\}} \dots \sum_{x_l \in \{0,1\}} g(r_1, x_2, \dots, x_l)

* Round $n$ (Final round): $P$ sends a univariate polynomial $s_n(X_n)$ claimed to equal:

s_n(X_n) = g(r_1, \dots, r_{n-1}, X_n)

* $V$ checks that $s_{n-1}(r_{n-1}) = s_n(0) + s_n(1)$. Also, $s_n(r_n) = g(r_1, \dots, r_n)$, which the verifier can easily compute since it can simply query the oracle for the value of $g(\dots)$ directly. * Final Step: The prover sends a univariate polynomial to the verifier. The verifier checks this final polynomial at a random point to confirm the prover’s claim.

#### Properties:

Soundness: If the prover’s original claim about *S is false, then with high probability, they will be caught in a lie at some point in the protocol. * Completeness: If the prover’s claim is true, they can always convince the verifier.

I won’t be diving into the calculations for the above properties here. Feel free to use the reference links if interested.

In Part 2, I will cover a simple implementation of the Protocol from scratch.  Connect with me on Twitter and LinkedIn, for any help, or to talk about cryptography, privacy, and blockchain in general.

References: \- ChatGPT 4 \- Interactive Proofs by Justin Thaler Link