Understanding the Halo 2 Protocol Description

[cadaniluk]

Hello there, I am currently reading the Protocol Description in the Halo 2 Book, but I have some trouble finding the link to other descriptions on Halo 2 I have read. I recognize concepts from the Halo paper and from the remainder of the Halo 2 Book, but there are some deviations that I have not found described anywhere else:

• g' seems to correspond to \text{gate}_0(x) + \cdots + y^i \cdot \text{gate}_i(x) + \cdots from the vanishing argument. But what are these challenges c_j about that it depends on? a_j' seems to depend on c_1, \ldots, c_{j-1}, but these seem to be neither reflected in the description on circuit commitments nor in the code (crate halo2_proofs, plonk/prover.rs).

• The polynomial to evaluate \boldsymbol{b} has changed from \prod_{j=1}^{k}(u_i+u_{i}^{-1}X^{2^j-1}) to \prod_{j=0}^{k-1}(1+u_{k-1-j}X^{2^j}). The idea seems to be the same, but why did this change?

I would be happy if someone could give me some hints on this!

[therealyingtong]

• each squeeze_challenge in the implementation can roughly be mapped to a c_i challenge in the protocol description. e.g. the beta, gamma challenges are used in defining the permutation grand product polynomial. this grand product polynomial varies in beta, gamma, and all the columns involved in the permutation: halo2/halo2_proofs/src/plonk/prover.rs at main · zcash/halo2 · GitHub

• the b polynomial and the inner product argument was modified to be similar to the construction in Appendix A.2 of “Proof-Carrying Data from Accumulation Schemes” (Proof-Carrying Data from Accumulation Schemes). This removes square challenges and the need for a forking transcript: Avoid square challenges in inner product argument by ebfull · Pull Request #113 · zcash/halo2 · GitHub

For close-reading of the protocol / spec, a helpful resource may be this recent report by a team from Aarhus University:
High_Assurance_Specification_Of_The_Halo2_Protocol.pdf (870.7 KB)

And for more halo2-specific questions, we also have a dedicated ecosystem Discord: Halo 2 Ecosystem

[cadaniluk]

Great, thanks a lot for all the links, that’s really helpful!