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)

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.

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

(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

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?

What is an inner product argument? The inner product argument is the following construction: given the commitments (for now let's say the hash) of two vectors $\vec{a}$ and $\vec{b}$ of size $n$ and with entries in some field $\mathbb{F}$, prove that their inner product $\langle \vec{a}, \vec{b} \rangle$ is equal to $z$. There exist different variants of this inner product argument. In some versions, none of the values ($\vec{a}$, $\vec{b}$ and $z$) are given, only commitments. In some other version, which is interesting to us and that I will explain here, only $\vec{a}$ is unknown. How is that useful? Inner products arguments are useful for several things, but what we're using them for in Mina is polynomial commitments. The rest of this post won't make too much sense if you don't know what a polynomial commitment is, but briefly: it allows you to commit to a polynomial $f$ and then later prove its evaluation at some point $s$. Check my post on Kate polynomial commitments for more on polynomial commitment schemes. How does that translate to the inner product argument though? First, let's see our polynomial $f$ as a vector of coefficients:

Foundation Commitments Inner product argument: the idea Inner product argument: the protocol Non-interaction with Fiat-Shamir Optimizations Compressing point equality proofs of multiple polynomials