Try   HackMD

Fooby halo2 notes

tags: fooby adrian

see updated link: https://hackmd.io/fiaKvd0bR1min9d_gp9ARA

The original Halo paper explains how the Bulletproofs/IPA commitment scheme can be used to speed up recursive SNARK verification.

  • Use IPA as PCS
  • Notice that IPA is a "split accumuluation scheme" (c.f. Proof-Carrying Data from Accumulation Schemes)
  • Based on Sonic arithmetization, the precursor to PlonK.
  • The hard part of recursive verification is computing a final MSM inside a circuit over the non-native field
    • Using curve cycles, create a SNARK over a curve where the base field corresponds to the MSM's curve.
    • The circuit performing the MSM is really small, and doesn't do anything else.

To my knowledge, there never really was any implementation of halo, and zcash went directly with halo2 which replaces the Sonic arithmetization with Plonkish.
The implementation is largely focused on the arithmetization, enabling users to write highly specialized circuits.

It's now the best way to write circuits for PlonKish arithmetization.

Key developers

zcash

Original developers of halo2, have the most experience with designing circuit building architecture (bellman for R1CS, previous work on libsnark I think).

Geometry

Mainly Ying Tong?

Scroll

Implement the zkEVM circuit

Axiom

halo2 verifier circuits

Last changed by 
 
adr1anh
0
147

Read more

Note on "Small field zerocheck"

In Jim Posen's note, the protocol ends with the verifier querying each polynomial M_i at

Apr 24, 2024
Compressed SNARK description

Multiple Sumcheck claims can be batched together by running the protocol over a random-linear combination of the input claims. The existing implementation of ppSNARK already includes this functionality, though we augmented it to handle instances defined over fewer variables.

Dec 13, 2023
Issue with public inputs

Let’s assume our R1CS shape has 2^n variables, \ell public inputs (including the initial 1, or u), and 2^m constraints, where \ell < 2^n. Take N = \max\{2^{n+1}, 2^m\} as the size of the public parameters.

Dec 13, 2023
Batched Sumcheck explanation

Lagrange Polynomial basics For $0 \leq i < 2^n$, define it's bit representation as $(i_0,\ldots, i_{n-1})$ such that $$ i = \sum_{k=0}^{n-1} i_k \cdot 2^{n-k-1} $$ Note that for $n' < n$, if $i <2^{n'}$ then its bit representation will look like $(0,\ldots,0,i_{n'-n},\ldots, i_{n-1})$, with $n-n'$ zeros in front. The Lagrange polynomials over ${0,1}^n$ are indexed by $0\leq i<2^n$, where $$ \begin{aligned}

Nov 26, 2023
Read more from adr1anh
Published on HackMD