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
