HomeEconomicOne article to understand the Sum-check Protocol in the zero-knowledge proof

# One article to understand the Sum-check Protocol in the zero-knowledge proof

Tips from FT Chinese Website: If you are interested in more content of FT Chinese Website, please search for “FT Chinese Website” in the Apple App Store or Google Play, and download the official application of FT Chinese Website.

With the spread of concepts such as Bitcoin, blockchain, and smart contracts, more and more people are paying attention to the vigorous development of the Web3 field. In terms of technology, many developers also pay attention to the cryptographic protocols that support the underlying blockchain. Among them, the zero-knowledge proof protocol shines with its unique features, and it plays a key role in realizing privacy protection and in the zkrollup project that realizes Layer 2 performance expansion.

Zero-knowledge proof is a general term for a class of algorithms. So far, researchers have invented many protocols including Plonk, Groth16, zkStark, Virgo, Orion, Foaks, etc. Different protocols are suitable for different computing scenarios, and the complexity and efficiency are also different. For example, Foaks has the advantages of linear proof time and small proof length.

For each of the above-mentioned protocols, the protocol goal is the same, that is, the prover (Prover) hopes to convince the verifier that he has the secret without disclosing any information about his own secret to the verifier. The sum-check protocol is a component of many protocols, and it was first proposed in it. Many computational problems can be transformed into problems that can be handled by the sum-check protocol to generate proofs. The underlying protocols of many protocols, including Foaks, are based on the sum-check protocol, which is implemented by adjusting it.

This protocol also plays an important role in the Foaks proof system adopted by Fox Tech. Specifically, in order to prove the correctness of an opcode, it is necessary to first convert it into an arithmetic circuit, then convert it into a matrix, and finally generate a polynomial, apply the algorithm in the proof system to the polynomial, and compress the part of the proof at the end Among them, the interactive process between the prover (Prover) and the verifier (Verifier) ​​is also converted into a process of calculating a certain sum, that is, the process of sum-check protocol.

Figure 1: Where the Sum-check Protocol is located

Sum-check Protocol

1. Objectives of the Agreement

The goal of the protocol is very simple and easy to understand.

Suppose we have a v-variable polynomial defined over a finite field F, denoted as g. The goal of the protocol is to compute the sum: Similar to the “outsourcing calculation” scenario considered in zkRollup, in the application, the calculation amount of the above formula will be very large. We hope to hand over the calculation of this formula to the prover (Prover), and then the prover will report to the verifier (Verifier) ​​to prove that their calculation results are correct.

2. Agreement assumptions

First of all, it is necessary to clarify the capabilities of the verifier in this protocol. We assume that the verifier has an oracle (Oracle) that can compute the function g. That is to say, it is easy for the verifier to calculate g(r1, … ,rv) after certain inputs r1, … ,rv are determined. But computing the complete result H is difficult.

In fact, in real applications, the oracle will not exist, but it can be realized by some means. For example, we can let the prover help the verifier to calculate this value, and use more skills to attach the proof of correctness.

The second point is about the goal of the protocol. In fact, the sum-check protocol can calculate bBmg(b) for any set B, but without loss of generality, we assume that B={0,1}.

3. Agreement process

The agreement contains a total of v rounds. One variable in g is processed in each round.

Round 1: If the prover is honest, H=g1(0)+g1(1) should be established. The verifier verifies, and if it passes, selects the random number r1 and sends it to the certifier. Note that, according to the assumptions of the protocol, the prover can complete the above verification.

We use degi(p) to denote the degree of the ith variable in the multivariate polynomial p. The degree of g1(X1) is deg1(g), so we know that g1 can be represented by deg1(g)+1 domain elements.

Round j (j>1): If the prover is honest, gj-1(rj-1)=gj(0)+gj(1) should be established. The verifier verifies, and if it passes, the random number rj is selected and sent to the certifier.

Round v:  1. Completeness: If the prover has a valid Witness, the verifier will accept the proof with a probability not lower than (1-negl(n));

2. Soundness: If the prover does not have a valid Witness, the verifier will reject the proof with a probability lower than negl(n)

3. Succinctness: The Size of Proof must be much smaller than the Size of Witness;

4. Zero-knowledge: The verifier cannot obtain any information about the witness through the interactive process of the proof

#where negl(n) is any negligible function

4. Protocol complexity

Through the demonstration in Part 3, we can see that the protocol consists of v rounds. In each round, the prover needs to send a degi(g) degree polynomial to the verifier, that is, deg1(g)+1 domain elements , so the overall communication complexity is O(i=1vdegi(g)). In terms of computational complexity, if each round of verification is passed, the prover needs to perform at most 2v operations on the value of g; Take the value of wheel pair g.

The following table shows the complexity results in detail, where T represents the overhead required to access an oracle (Oracle), that is, to evaluate g once. Figure 3: The complexity of the Sum-check protocol

Application of Sum-check Protocol

Among many zero-knowledge proof algorithms, the sum-check protocol is playing an important role. The proof of many problems relies on converting the original problem into a sum-check form, and then completing the subsequent steps.

For example, the sum-check protocol can be used to count the number of triangles in an undirected graph.

First, we use the adjacency matrix A to represent the undirected graph G, let E be its edge set, then Ai,j=1(i,j)E, that is to say, if there is an edge between points i,j then Ai,j =1 otherwise 0. For points i, j, k, the conditions for three points to form a triangle are Ai, j=1, Ai, k=1, Aj, k=1.

Next, the matrix A is recorded as a mapping table, which represents the mapping as f:{0,1}log n{0,1}log n{0,1}, where logn is the binary length of i and j. So for points i, j, k, the condition of three points forming a triangle can be further expressed as f(i, j)f(i,k)f(j,k)=1. In addition, in many proof systems, the sum-check protocol is used as the underlying logic for construction. The figure below shows different proof systems based on different transformations based on sum-check. Figure 4: Application of Sum-check protocol in four types of proof systems Figure 5: Specific application of Sum-check protocol in concise proof

epilogue

This article sorts out the specific process of the sum-check protocol, discusses the complexity of the protocol, and demonstrates its application in many proof systems.

As the web3 field continues to expand, cryptography, as the underlying component of blockchain technology, is playing an increasingly important role. As zkrollup, privacy protection, and other applications and projects that rely on zero-knowledge proofs are gradually born, the sum-check protocol, as an important component of many proof systems, is also receiving more and more attention from both academia and industry.

references

Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39:859–868, October 1992.

https://people.cs.georgetown.edu/jthaler/sumcheck.pdf

The Unreasonable Power of the Sum-CheckProtocol

https://eprint.iacr.org/2021/333.pdf

Introducing the Chinese blog of sum-check https://blog.csdn.net/mutourend/article/details/111610754

(Introduction to the author: Kang Shuiyue is the CEO of Fox Tech; Meng Xuanji is the chief scientist of Fox Tech. This article only represents the author’s point of view. Responsible editor email: Tao.feng@ftchinese.com)