# ZKP Gadgets

$ \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 $$

## Sign check

## 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 + γ ) $$

## Range check

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

## Permutation check

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

## Plookup

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

## Read only memory

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