$\gdef\set#1{\mathcal{#1}}$

## Binary check

Constrain $a ∈ {0, 1}$:

Constraints:

$$a ⋅(1 - a) = 0$$

This is a special case of constraining $a$ to a small set of values $\{c_0, c_1, \dots \}$:

$$(a - c_0) ⋅(a - c_1) \cdots = 0$$

## Zero check

Given $a$ construct

$$b = \begin{cases} 0 & a \ne 0 \\ 1 & a = 0 & \end{cases}$$

Constraints:

\begin{aligned} b &= 1 - a ⋅ w & a ⋅ b &= 0 \end{aligned}

Witness: $w = a^{-1}$.

Alternatively can inline the definition of $b$:

$$(1 - a ⋅ w) ⋅ a = 0$$

source

## Multiset equality

Given trace columns of values $\vec v$, $\vec w$ represented as polynomials $V(ω^i) = v_i$, $W(ω^i) = w_i$. We can proof that the multi-set of values in $\vec v$ equals $\vec w$.

$$\prod_{a ∈ \vec v} ( a + γ ) = \prod_{b ∈ \vec w} ( b + γ )$$

source

## Range check

https://hackmd.io/D-vjBYtHQB2BuOB-HMUG5Q

## Permutation check

https://hackmd.io/@arielg/ByFgSDA7D

source

## Plookup

Given $a$ constrain $a ∈ \set A$.

source

Given $i$ constrain $a = v_i$ for constant vector $\vec v$.

Use Plookup with

$$A = \{ i ⋅ c + v_i\}$$

where $c > \max \vec v$ and constrain $a + i ⋅ c ∈ A$.

Alternatively take $v_i ⋅c$, $c > |v|$ and $a ⋅ c + i ∈ A$.

## Random access memory

$a = \mathtt{get}(i)$

$\mathtt{set}(i, a)$

The trace is augmented by a $v$ counter that increases (at least) for every RAM operation.

In addition to trace, provide permuted copy of RAM operations such that:

• $i$ (location) is monotonically increasing.
• $v$ (version) is monotonically increasing while $i$ is constant.
• $c$ (contents) is constant unless a $\mathtt{set}$ changes it or $i$ changes.

https://hackmd.io/@bobbinth/HJr56BKKt

Implementation tricks https://zips.z.cash/protocol/canopy.pdf#circuitdesign

https://zcash.github.io/halo2/user/tips-and-tricks.html

Remco Bloemen
Math & Engineering
https://2π.com