3.2 Proof Generation

The generation of zero-knowledge proof is a complex cryptographic process that allows a prover to demonstrate the validity of a statement without revealing any information beyond the fact that the statement is true. It typically involves several key steps, including statement formulation, circuit construction, and proof generation. Statement Formulation: The first step in ZKP generation is to formulate the statement that the prover wishes to prove. In the transaction execution scenario, it refers to the execution process of EVM instructions. This statement could be anything from the correctness of a computation to the possession of a secret key. The statement is typically expressed in a formal language, such as arithmetic circuits or Boolean circuits, that can be efficiently processed by the cryptographic algorithms used in ZKP generation. Circuit Construction: Once the statement is formulated, the prover constructs a corresponding arithmetic circuit or Boolean circuit that represents the computation required to prove the statement. This circuit encapsulates the logic of the statement and serves as the basis for the subsequent steps in the ZKP generation process. Proof Generation: With the circuit constructed, the prover employs cryptographic techniques, like non-interactive protocols, to generate a proof of the statement's validity. This proof is typically generated by performing a series of mathematical computations on the circuit and the prover's input data. The goal of the proof generation process is to produce a succinct and efficiently verifiable proof that convincingly demonstrates the truth of the statement. The generation process can be described mathematically as follows.Assume that the confidential data possessed by the prover is referred to as the "witness," while the public data is referred to as the "statement." They can be written as

$statement:=Function(witness)$

First of all, convert the disclosed computational relationship $Function$ into $Circuit$constraints

$Circuit\leftarrow Function$

Then, input two types of data (witness, statement) into the circuit constraints, and calculate intermediate computation states and final result values.

$f_i=Circuit(witness,statement),i=1,...,n$

$f_1,...,f_n$ can be set as the value of polynomial。 Additionally, apply FFT(Fast Fourier Transform) to$f_1,...,f_n$，and calculate the coefficients of the polynomial expression.$(k_1,...,k_n)$

$\Sigma_{i=0}^{i=n}(k_i\cdot x^i)\leftarrow FFT(f_1,...,f_n)$

Furthermore, use multiple exponentiation to calculate MulExp，as inputting the polynomial coefficient expressions$(k_1,...,k_n)$and the elliptic curve generators$(G_1,...,G_n)$, and compute the corresponding random points on the elliptic curve.

$(F_1,...,F_n)\leftarrow MulExp(k_1\cdot G_1,...,k_n\cdot G_n)$

Finally, compress the n random points$(F_1,...,F_n)$on elliptic curve into another 3 elliptic curve random points$(A,B,C)$

$(A,B,C)\leftarrow Compress(F_1,...,F_n)$

And the proof can be represented as$proof=(A,B,C)$，then this proof is sent to the contract on Layer1.

Throughout the ZKP generation process, the verifier needs to follow strict cryptographic protocols to ensure the security and integrity of the proof. These protocols often involve the use of cryptographic primitives, such as hash functions, digital signatures, and commitment schemes, to protect against various forms of attack, including impersonation attacks, replay attacks, and tampering attacks.