# Buidler DAO: “Plain” ZK Series (Part 1): Construction and Case Studies of zk-SNARK

ZK technology has been highly regarded in the Web3 field in the past two years. Starting with Rollup, more and more projects in different tracks have begun to try to use ZK technology. SNARK and STARK are the two most commonly heard terms. Buidler DAO researcher Wenchuan simplified the proof logic of SNARK from a non-technical perspective, and then used Scroll’s zk Rollup as an example to illustrate the operation of the zk proof system.

zk-SNARK is a proof system that uses ZK technology. SNARK is the name of a class of schemes, and there are many different combinations of methods that can be used to implement SNARK. zk-SNARK aims to solve the “computational verification problem”, which is to efficiently verify the result of a computation without the verifier knowing the privacy of the prover.

Construction of zk-SNARK: 1) Converting the problem to be proved into a polynomial: In simple terms, the idea of SNARK is to convert whether a proof statement is true into whether a polynomial equation is true. The conversion process is: the problem to be proved → arithmetic circuit → R1CS → polynomial → transformation between polynomials. This transformation achieves the simplicity of the system and effectively reduces the proof size by using a Merkle tree structure in the proof protocol. 2) Prove that the polynomial is true: In the process of deriving the polynomial, two random numbers are selected, and the verifier cannot obtain the coefficients of the original polynomial from them, that is, the prover’s secret input, to achieve ZK. 3) Implement non-interaction: Before the proof starts, introduce a third party, a trusted setup, to transfer the task of the verifier selecting random numbers to the trusted setup, thereby achieving non-interaction between the verifier and the prover.

The workflow of zk Rollup on Scroll: The user initiates a transaction on L2, the Sequencer retrieves the transaction, executes the transaction off-chain, and generates an L2 block and a new state root. The transaction data and the new state root are submitted to the Rollup contract on Ethereum (implementing data availability). When an L2 block is generated, the Coordinator receives the execution trace of the block from the Sequencer and randomly assigns it to any Roller. The Roller converts the received execution trace into a circuit and generates a validity proof to send back to the Coordinator. When k L2 blocks are generated, the Coordinator sends an aggregation task to another Roller to aggregate the proofs of k blocks into a single aggregation proof. The Coordinator submits the single aggregation proof to the Rollup contract, and the Rollup contract verifies the aggregation proof together with the previously submitted state root and transaction data. If the verification is successful, the corresponding block is considered as finally confirmed on Scroll.

Reference: https://mp.weixin.qq.com/s/7iCJqya0YwUjFxf6LNLbGg