译自 halo2 book：user/tips-and-tricks.md

技巧与窍门

本节包含各种你在编写 halo2 电路(circuit)时可能会觉得有用的想法和代码片段。

小范围约束

R1CS 电路中常用的一种约束是布尔约束(boolean constraint)：$b\ast (1-b)=0$。这个约束只能被 $b=0$ 或 $b=1$ 满足。

在 halo2 电路中，你可以用类似的方式约束某个单元格(cell)取一小组值中的某一个。例如，要把 $a$ 约束到范围 $[\mathrm{0..5}]$，你可以创建如下形式的门(gate)：

$$a\cdot (1-a)\cdot (2-a)\cdot (3-a)\cdot (4-a)=0$$

而要把 $c$ 约束为 7 或 13，你可以使用：

$$(7-c)\cdot (13-c)=0$$

这里的底层原理是：我们构造一个多项式约束(polynomial constraint)，让它在我们想要允许的那组可能取值中的每一个值处都有一个根。在 R1CS 电路中，所支持的多项式最大次数(degree)为 2（因为所有约束都是 $a\ast b=c$ 的形式）。在 halo2 电路中，你可以使用任意次数的多项式——但前提是，次数越高的约束使用起来成本越高。

注意，这些根不必是常数；例如 $(a-x)\cdot (a-y)\cdot (a-z)=0$ 会把 $a$ 约束为等于 $\{x,y,z\}$ 中的某一个，其中后者可以是任意多项式，只要整个表达式保持在最大次数界限之内即可。

小集合插值

我们可以使用拉格朗日插值(Lagrange interpolation)构造一个多项式约束，对于小集合 $X\in \{x_i\},Y\in \{y_i\}$ 实现映射 $f(X)=Y$。

例如，假设我们想把一个 2 比特的值映射到一个与零交错排列的"展开(spread)"版本。我们首先预计算每个点处的取值：

$$\begin{array}{rcl}00\to 0000& ⟹& 0\to 0\\ 01\to 0001& ⟹& 1\to 1\\ 10\to 0100& ⟹& 2\to 4\\ 11\to 0101& ⟹& 3\to 5\end{array}$$

然后，我们使用如下恒等式为每个点构造拉格朗日基多项式(Lagrange basis polynomial)： $$l_j(X)=\prod _{0\le m<k,m\ne j}\frac{x-x_m}{x_j-x_m},$$ 其中 $k$ 是数据点的个数。（在上面的例子中 $k=4$。）

回顾一下，拉格朗日基多项式 $l_j(X)$ 在 $X=x_j$ 处取值为 $1$，在所有其他 $x_i,j\ne i$ 处取值为 $0$。

继续我们的例子，我们得到四个拉格朗日基多项式：

$$\begin{array}{ccc}{l}_0(X)& =& \frac{(X-3)(X-2)(X-1)}{(-3)(-2)(-1)}\\ l_1(X)& =& \frac{(X-3)(X-2)(X)}{(-2)(-1)(1)}\\ l_2(X)& =& \frac{(X-3)(X-1)(X)}{(-1)(1)(2)}\\ l_3(X)& =& \frac{(X-2)(X-1)(X)}{(1)(2)(3)}\end{array}$$

于是我们的多项式约束为

$$\begin{array}{cccccccccccl}& f(0)\cdot l_0(X)& +& f(1)\cdot l_1(X)& +& f(2)\cdot l_2(X)& +& f(3)\cdot l_3(X)& -& f(X)& =& 0\\ ⟹& 0\cdot l_0(X)& +& 1\cdot l_1(X)& +& 4\cdot l_2(X)& +& 5\cdot l_3(X)& -& f(X)& =& 0.\end{array}$$