Halo2学习笔记——用户手册之Tips and tricks（1）

1. 引言

此文包含在写halo2 circuit时可能有用的各种想法和片段。

2. Small range constraints

R1CS circuit中，常用的constraint为boolean constraint： b ∗ ( 1 − b ) = 0 b*(1-b)=0 b∗(1−b)=0，当且仅当 b = 0 b=0 b=0或 b = 1 b=1 b=1时，该constraint才satisfied。

类似地，在halo2 circuit中，也可constrain a cell to have one of a small set of values。如，constrain a a a to the range [ 0..5 ] [0..5] [0..5]，则可构建如下形式的gate： a ⋅ ( 1 − a ) ⋅ ( 2 − a ) ⋅ ( 3 − a ) ⋅ ( 4 − a ) = 0 a\cdot (1-a)\cdot (2-a)\cdot (3-a)\cdot (4-a)=0 a⋅(1−a)⋅(2−a)⋅(3−a)⋅(4−a)=0 当constrain c c c为 7 7 7或 13 13 13时，可： ( 7 − c ) ⋅ ( 13 − c ) = 0 (7-c)\cdot (13-c)=0 (7−c)⋅(13−c)=0

底层核心思想为将set内的所有值作为constraint多项式的根。在R1CS circuit中，支持的最大polynomial degree 为 2 2 2（因为所有constraints的形式均为 a ∗ b = c a*b=c a∗b=c）。在halo2 circuit中，可使用任意degree的多项式——但是，degree越高，使用成本也越高。

注意，此处并不限制根必须是常量，如 ( a − x ) ⋅ ( a − y ) ⋅ ( a − z ) = 0 (a-x)\cdot (a-y)\cdot (a-z)=0 (a−x)⋅(a−y)⋅(a−z)=0，将constrain a a a to be equal to one of { x , y , z } \{x,y,z\} {x,y,z}，而 x , y , z x,y,z x,y,z可为任意多项式，只要整个表达式的degree不超过maximum degree bound。

3. Small set interpolation

可使用Lagrange interpolation来创建a polynomial constraint that maps f ( X ) = Y f(X)=Y f(X)=Y for small sets of X ∈ { x i } , Y ∈ { y i } X\in\{x_i\}, Y\in\{y_i\} X∈{xi​},Y∈{yi​}。

如，将a 2-bit value map为 a “spread” version interleaved with zeros：

• 首先，precompute the evaluations at each point： 00 → 0000 ⇒ 0 → 0 00\rightarrow 0000 \Rightarrow 0\rightarrow 0 00→0000⇒0→0 01 → 0001 ⇒ 1 → 1 01\rightarrow 0001 \Rightarrow 1\rightarrow 1 01→0001⇒1→1 10 → 0100 ⇒ 2 → 4 10\rightarrow 0100 \Rightarrow 2\rightarrow 4 10→0100⇒2→4 11 → 0101 ⇒ 3 → 5 11\rightarrow 0101 \Rightarrow 3\rightarrow 5 11→0101⇒3→5

• 然后，构建the Lagrange basis polynomial for each point using the identity： l j ( X ) = ∏ i ≤ m < k , m ≠ j x − x m x j − x m l_j(X)=\prod_{i\leq m