In series 2, we reviewed the architecture, design, and assembly instructions of TinyRAM, which is a convenient tool for expressing the provability of non-deterministic computations. This article focuses on zkp algorithm, the Halo principle, introduced by the Zcash R&D team in 2019.
Among the zkp algorithms that are currently in use, existing problems include the need to layout a trust set up, such as Groth16, Plonk, etc.; or the proof size is way too large, such as Zk-snarks.
Fractal is a recursive zkp protocol based on LDT technology, which fully satisfies the conciseness of zkp and is quantum-resistant. Although Halo is not concise enough, its recursive proof size remains around 3.5KiB, a much lower size compared to 120KiB (average proof size of Fractal's); moreover, Halo's simple one-step verification (linearly related to the circuit size) can be executed at the final step of recursive, attributing to the innovative Nested Amortization algorithm based on Accumulation schemes.
The Arithmetization process and Sonic algorithm of Halo are based on the circuit design of R1CS, and then perform Polynomial IOP. However, it turns out that the Arithmetization process and Polynomial IOP scheme described in Plonk are more efficient; hence, based on the above changes, the Zcash team launched the Halo2 ZKP algorithm.
Halo VS Halo2
A simple diagram can be used to show the process and similarities as well as differences of the above-listed two ZKP algorithms, as shown below:
The Polynomial IOP technology in Sonic is applied by Halo to describe a Recursive Proof Composition algorithm, and the Inner Product argument technology in Bulletproof is also employed to replace the Polynomial Commitment Scheme in the algorithm, the replacement which eliminates the dependence on Trust Setup.
Halo2 has been further optimized, mainly in the direction of Polynomial IOP. In recent years, researchers have discovered Polynomial IOP Scheme which is more efficient than Sonic, such as Marlin and Plonk. In comparison, Plonk was selected because it supports a more flexible circuit design.
Halo2 Arithmetization
In Halo, R1CS is applied to describe Circuit, and the mode is as follows:
A * B = C qL * Xa + qR * Xb + qO * Xc + qM * XaXb + qC = 0
Plonk Arithmetization is used to represent Circuit in Halo2, and the mode is as follows:
qL * Xa + qR * Xb + qO * Xc + qM * XaXb + qC = 0
Among all, q* is the selector polynomial. Different values represent different Gates, as shown in the following table:
Standard Plonk Arithmetization is made up of Add-rage and Multi-gate. In fact, we can also customize gates for actual application scenarios, such as Custom-gate. For instance, when needing to achieve constraint xc_i = xa_i xb_ixc_i-1(running product in the replacement argument), we can design it as follows:
While Plonk Arithmetization can express it as:
qL * Xa + qR * Xb + qO * Xc + qM * XaXb + qp * (Xc - XaXbXc(xw-1)) + qC = 0
Commitment Scheme
Analogous to the Bulletproof algorithm, Halo2 adopts the Polynomial Commitment Scheme based on the Inner Product Argument and has made some optimization. Its calculation process can be shown as below:
In short, the Inner Product Argument reduces the interaction complexity of Polynomial Commitment from O(n) to O(log(n)). Nonetheless, Verifier needs to perform one 0(n) level of operation for each Commitment proof, that is to calculate b and G. A new solution has been introduced in Halo2. For b calculations, it can be solved by using Laurent Polynomial, a special polynomial that can be calculated in the log time to get b; as for G, it is just available in the above-mentioned Polynomial Commitment based on the Inner Product Argument, but as mentioned earlier, each Commitment proof requires an O(n) level operation, so an Accumulation Scheme is proposed in Halo2. That is, the 0(n) level of operation is processed by Accumulate, and a plurality of proof verifying O(n) operation is accumulated on a proof. In the final part of Recursive, one calculation of O(n) is performed, so that multiple proofs amortize the time over one calculation time of an O(n). In Halo2, this process is defined as Nested Amortization.
Recursive zk-snarks & Accumulation Scheme
Halo2 applies Pasta curves: Pallas and Vesta to implement Recursive zk-snarks verification system. Mina also uses the cycle curves.
Since Halo2 applies the Inner Product Argument, the complexity of Verify is O(n), which undermines the conciseness of Snarks. Hence, Halo2 proposes a new technology Nested Amortization, an Accumulation Scheme aggregation technique. Details are as follows:
-
In the verification circuit, the operation of G is not implemented. The operation is O(n) while the Prover provides G and related calculation parameters as the witness of the circuit, that is, for the verification circuit, the G has been defaulted correctness, in fact, the correctness of G still needs a verifier to do, but this step can be aggregated, namely, the Accumulation Scheme is adopted;
-
As mentioned in the first point, Verifier is still needed to verify the correctness of G, but we can accumulate multiple proof instances of G and its related parameters, and iterate to the last step, which is completed once by the verifier. The process actually completes the amortization of verification costs and is the core of Nested Amortization.
Summary
Halo2, which eliminates trust setup, is a recursive zk-snarks algorithm based on UltraPlonk Atithmetization technology and built on the Pasta curve. Many of Halo2's optimizations are worth of research and study, including the not-mentioned lookup (analogous to the Plookup protocol) friendly Pedersen-like hash algorithm and Sinsemilla. In the follow-up work, we will continue to study it and apply it to improve some viable work.