✳flâneur — a map of the web's best reading

Lookup argument - The halo2 Book

zcash.github.io · 1,751 words · saved by 1 readers

Halo 2 uses the following lookup technique, which allows for lookups in arbitrary sets, and is arguably simpler than Plookup. In addition to the general notes on language: For ease of explanation, we'll first describe a simplified version of the argument that ignores zero knowledge. We express lookups in terms of a "subset argument" over a table with 2 k rows (numbered from 0), and columns A and S. The goal of the subset argument is to enforce that every cell in A is equal to some cell in S. This means that more than one cell in A can be equal to the same cell in S, and some cells in S don't need to be equal to any of the cells in A. Let ℓ i ​ be the Lagrange basis polynomial that evaluates to 1 at row i, and 0 otherwise. We start by allowing the prover to supply permutation columns of A and S. Let's call these A ′ and S ′ , respectively. We can enforce that they are permutations using a permutation argument with product column Z with the rules: Z(ωX)⋅(A ′ (X)+β)⋅(S ′ (X)+γ)−Z(X)⋅

Lookup argument - The halo2 Book Keyboard shortcuts Press ← or → to navigate between chapters Press S or / to search in the book Press ? to show this help Press Esc to hide this help Auto Light Rust Coal Navy Ayu The halo2 Book Lookup argument Halo 2 uses the following lookup technique, which allows for lookups in arbitrary sets, and is arguably simpler than Plookup. Note on Language In addition to the general notes on language : We call the Z ( X ) polynomial (the grand product argument polynomial for the permutation argument) the “permutation product” column. Technique Description For ease o

Explore this link on the map →

related reading