# Kimchi / Plonk / Halo / Pickles Glossary This is a list of terms that are often used throughout these general-purpose zero-knowledge proof systems. This is not meant to be a list that you should read through, but rather a reference if you sometimes encounter a term that you don't know about. In no order: * **constraint**: generally, a constraint can be thought of as an equation where the lhs is whatever you want, and the right handside is zero. This way, the equation constraints the values of some variables. For example, $x(x-1) = 0$ constraints $x$ to be equal to 0 or 1. Sometimes, the term constraint refers to a [gate] in a circuit (for example, "this circuit has 30 constraints" really means "this cicruit has 30 gates") * **gate**: usually used to refer to arithmetic gates, which allow you to do addition or multiplication of two inputs into one output. A circuit is a list of gates. The concept of arithmetic gate was generalized in plonk to a "generic gate" that is more versatile ($c_l \cdot l + c_r \cdot r + c_o \cdot o + c_m l \cdot r + c_c$), and in turboplonk with "custom gates" that are specialized for certain tasks (for example, hashing with poseidon, or doing parts of a scalar multiplication) * **row**: a row is really the synonym for a gate. As circuits are usually layed out as tables where gates are listed as rows, we sometimes just say things like "this circuit has 30 rows". * **column**: if you represent a circuit as a table, where [rows] are the [gates], then the columns are the variables used in those gates (for example, the witness variables $w_0, w_1, \dots$, the coefficients, etc.) Columns are usually interpolated into polynomials in the protocol. Some columns are secret (the 15 witness columns or kimchi), others are public (coefficients, selector polynomials). * **table**: a circuit table, made out of rows (gates) and columns (variables). * **register**: another term for a witness column. * **cell**: In a circuit table, where columns are limited to the witness columns that take part in the permutation, a cell is simply a tuple representing an entry `(row, col)` * **wires**: another term for a witness column. * **vanishing polynomial**: see https://o1-labs.github.io/proof-systems/plonk/domain.html#efficient-computation-of-the-vanishing-polynomial * **execution trace**: in a circuit table, a number of values are not fixed at setup/compile time. For example, witness columns are not fixed, but coefficients are fixed. The execution trace represent the values of these not-fixed columns after executing a circuit. (These values are usually hidden from the verifier.) * **evaluation frame**: The points used to evaluate polynomials in the protocol. In Plonk it's $\zeta$ and $\zeta \omega$. It is called evaluation _frame_ because they represent two adjacent rows in a circuit table. Theoretically, we could have constraints that involve more rows by increasing the window, but this increases the proof size. * **execution domain**: the domain used to create a circuit. It's usually a cyclic subgroup that has a succinct representation (see the [domain](https://o1-labs.github.io/proof-systems/plonk/domain.html) chapter in the Mina book), and rows of the circuit are defined on elements of that subgroup. The execution domain is often larger than the circuit for two reasons: it must leave some rows empty for zero-knowledge during proving time, and it also must be a power of 2 for FFT and bulletproof to work efficiently. * **base field**: an elliptic curve is an equation defined over some field $F$. Consequently, elliptic curve points have coordinates in this field. We call this field the base field. * **scalar field**: an elliptic curve has a number of points $n$. This means that for any curve point $P$, we have $[n] P = [0] P = O$ ($P$ added to itself $n$ times), where $O$ is the point at infinity. Furthermore, you can do arithmetic with scalars before multiplying them with a point: $[a \cdot b] P$ or $[a + b]P$. The set of all the scalars thus forms another field, called the scalar field. (It happens that this field is prime in the pasta curves, and is equal to the base field of the other curve.) * **multi-scalar multiplication (MSM)**: it is simply the addition of many points multiplied by many scalars $[a]P + [b]Q + [c]R + \dots$. There are efficient algorithms to do this in a non-naive way. * **multi-exponentiation**: equivalent to an [MSM], if you use the multiplicative notation for your group (common in cryptography). ## Other ressources * https://www.risczero.com/docs/key-terminology terminology * https://nmohnblatt.github.io/zk-jargon-decoder/foreword.html jargon
Last changed by  
 
David Wong
279

Read more

List of PLONK implementations

Written for running in production kimchi (rust) zk-garage/ark-plonk (rust) dusk network plonk (rust) astar (rust) aztec network barretenberg (C++) matterlabs based on bellman (rust) jellyfish (rust) halo2 (zcash) (rust)

12/12/2022
RFC: Plookup in kimchi

In 2020, plookup showed how to create lookup proofs. Proofs that some witness values are part of a lookup table. Two years later, an independent team published plonkup showing how to integrate Plookup into Plonk. This document specifies how we integrate plookup in kimchi. It assumes that the reader understands the basics behind plookup. Overview We integrate plookup in kimchi with the following differences: we snake-ify the sorted table instead of wrapping it around (see later) we allow fixed-ahead-of-time linear combinations of columns of the queries we make we only use a single table (XOR) at the moment of this writing

4/4/2022
How to write a tic-tac-toe snapp

(photo by @micheile) Snapps are zero-knowledge smart contracts that will launch on Mina next year. You can learn more about them here. This tutorial teaches you how to write a tic-tac-toe game using snarkyjs, the official library to write snapps on Mina. Set up You can quickly create a project by using the Snapp CLI: $ npm install -g snapp-cli $ snapp project my-proj

1/13/2022
ZK HACK: 1st puzzle write up

Last Tuesday was the start of ZK HACK, a "7-week virtual event featuring weekly workshops and advanced puzzle solving competitions". All related to zero-knowledge proofs, as the name suggests. The talks of the first day were really good, and you can rewatch them here. At the end of the first day, a puzzle called Let's hash it out was released. This post about solving this puzzle. The puzzle The puzzle is a Github repo containing a Rust program. If you run it, it displays the following message: Alice designed an authentication system in which users gain access by presenting it a signature on a username, which Alice provided. One day, Alice discovered 256 of these signatures were leaked publicly, but the secret key wasn't. Phew. The next day, she found out someone accessed her system with a username she doesn't know! This shouldn't be possible due to existential unforgeability, as she never signed such a message. Can you find out how it happend and produce a signature on your username?

10/28/2021
Read more from David Wong
Published on HackMD