Understanding Interactive Proof Systems and Sum Check Protocol: Part 1

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.

1. Function commitments :

Polynomial Commitments: commitments to functions of type:

$$P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0$$

Generalized Polynomial Expression
Multilinear Commitments: commitments to functions of type f(x1,…xk)

$$f(x_1, x_2, \ldots, x_n) = a_{1,2,\ldots,n} x_1 x_2 \cdots x_n + \sum_{\substack{i_1,i_2,\ldots,i_k \ 1 \leq k < n}} a_{i_1,i_2,\ldots,i_k} x_{i_1} x_{i_2} \cdots x_{i_k}$$

Generalized Multilinear Expression
Vector commitments: eg. Merkle trees.

$$\ {u} = (u_1, u_2, u_3, \ldots, u_d) \in \mathbb{F}_p^d$$

1. SZDL Lemma:

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

• Let p != q be a univariate polynomial of degree almost d. Then

  $$\Pr_{r \in \mathbb{F}}[p(r) = q(r)] \leq \frac{d}{|\mathbb{F}|}$$

• SZDL: Let p!= q be l-variate polynomials of total degree almost d.
  Then

  $$\Pr_{r \in \mathbb{F}^l}[p(r) = q(r)] \leq \frac{d}{|\mathbb{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:

$$S = \sum_{x_1 \in \mathbb{F}} \sum_{x_2 \in \mathbb{F}} \cdots \sum_{x_l \in \mathbb{F}} P(x_1, x_2, \ldots, x_l)$$

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₁. The protocol must check the ( where F ∈{0,1} ):
  $$C₁ = \sum_{x_1 \in \mathbb{F}} \sum_{x_2 \in \mathbb{F}} \cdots \sum_{x_l \in \mathbb{F}} P(x_1, x_2, \ldots, x_l)$$
• Round 1: P sends a univariate polynomial S₁ ( X₁) claimed to equal:
  $$H_1(X_1) = \sum_{x_2 \in \mathbb{F}} \cdots \sum_{x_l \in \mathbb{F}} P(x_1, x_2, \ldots, x_l)$$
• The verifier needs to check 2 things:
  1. Does S₁ equals H₁
  2. Even if S₁ equals H₁, is that consistent with try answer C₁.
• Verifier checks
  1. C₁ = S₁(0) + S₁(1) where F ∈{0,1}
  2. Now to check S₁ and H₁, verifier simply checks if S₁ and H₁ agrees at a random point r₁. S₁ is easy to calculate at r₁ since the prover explicitly sends the polynomial to a verifier. But evaluating H₁(r₁) is hard to calculate for the verifier. To address this V picks r₁ at random from F and sends r₁ to P.
• Round 2: To address the issue of how to calculate H₁(r₁), the verifier recursively checks that S₁(r₁) = H₁(r₁). We utilize the form of expression that H₁ to do this, by using the following relation:
  $$S_1(R_1) = \sum_{x_2 \in \mathbb{F}} \cdots \sum_{x_l \in \mathbb{F}} P(r_1, x_2, \ldots, x_l)$$
• Round n ( Final round ) : P sends a univariate polynomial sₙ(Xn) claimed to equal:
  $$S_1(R_1) = \ g(r_1, r_2, \ldots, r_{n-1}, X_n)$$
• V checks that sₙ₋₁(rₙ₋₁) = sₙ(0) + sₙ(1). Also, sₙ(rₙ) = g(r₁, …, rₙ), which the verifier can easily compute since it can simply query the oracle for the value of g(..) 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