Let's learn about the most popular zkSNARK scheme together - an introduction to zero-knowledge proof (3)

2021-01-25 17:34

Read this article in 11 Minutes

This article describes the Groth16 scheme.

Original title: " Let's learn about the most popular zkSNARK scheme——Introduction to Zero Knowledge Proof (3) "

Original source: Nervos Chinese community

In the previous article, we introduced Basic concept of zero-knowledge proof and Basic idea and method of constructing zkSNARK. Starting from this article, we will introduce the most popular zkSNARK schemes one by one. The article is intended to give the reader an understanding of the rationale for these schemes. For the convenience of description and easy understanding, we will make some simplifications when describing the plan, focusing on conveying the core idea of the plan.

This article is about the Groth16 solution. The Groth16 scheme, as the name suggests, is the scheme proposed by Groth in a paper [Gro16] published in 2016. Groth16 is by far the most widely used zkSNARK in practice (none). In particular, the zkSNARK scheme currently used by Zcash is Groth16. In terms of performance, Groth16's Verifier performance is the fastest among all zkSNARKs, and its proof string is also the shortest.

The biggest disadvantage of Groth16 is that it needs to perform a trusted initialization for each circuit.

Before introducing Groth16, let's briefly review the problems zkSNARK is going to solve. We call this problem the "computational verification problem".

Computation Verification Problem

Any calculation can be described as an arithmetic circuit. An arithmetic circuit can perform arithmetic operations on numbers. The circuit consists of addition gates, multiplication gates and some constant gates, as shown in the figure below:

< p style="text-align: center;">

Summarize the calculation and verification problem in one sentence: Can Verifier not know the secret input , to efficiently verify computation results?

From circuit to R1CS Question

From R1CS question to QAP question

Polynomial interpolation

< /h3>

QAP Questions

Now, we directly replace the column vectors in the R1CS matrix with their polynomial interpolation, and the result is shown in the figure below.

< img src="https://image.theblockbeats.com/upload/2021-01-25/1ad603cb6eb53bf4c99df12ef83fffe75f55d407.png">

< br>

Summary

In this article, We explain the construction principle of Groth16, a zkSNARK scheme. We start with arithmetic circuits and show how to convert computation verification problems into R1CS problems and QAP problems. We then explain how to use the Groth16 scheme to prove knowledge of a solution to a QAP problem. The Groth16 scheme used KoE assumptions and bilinear pairings. Its disadvantage is that it requires a trusted third party to initialize, and the initialization process needs to be done once for each circuit. At the same time, Groth16 enjoys the most efficient Verifier algorithm and the shortest proof string, making Groth16 the most widely used zkSNARK scheme so far.