译自 halo2 book:https://zcash.github.io/halo2/design/gadgets/decomposition.html

分解(Decomposition)

给定一个域元素(field element)$\alpha$,这些 gadget 把它分解(decompose)成 $W$ 个 $K$ 比特的窗口(windows) $$\alpha =k_0+2^K\cdot k_1+2^{2K}\cdot k_2+\cdots +2^{(W-1)K}\cdot k_{W-1}$$ 其中每个 $k_i$ 是一个 $K$ 比特的值。

这是用一个累加和(running sum)$z_i,i\in [\mathrm{0..}W)$ 来完成的。我们将累加和初始化为 $z_0=\alpha ,$ 并计算后续各项 $z_{i+1}=\frac{z_i-k_i}{2^K}.$ 这给出:

$$\begin{array}{rl}{z}_0& =\alpha \\ & =k_0+2^K\cdot k_1+2^{2K}\cdot k_2+2^{3K}\cdot k_3+\cdots ,\\ z_1& =(z_0-k_0)/2^K\\ & =k_1+2^K\cdot k_2+2^{2K}\cdot k_3+\cdots ,\\ z_2& =(z_1-k_1)/2^K\\ & =k_2+2^K\cdot k_3+\cdots ,\\ & ⋮\\ \downarrow & \text{ (in strict mode)}\\ z_W& =(z_{W-1}-k_{W-1})/2^K\\ & =0\text{ (because }{z}_{W-1}=k_{W-1}\text{)}\end{array}$$

严格模式(Strict mode)

严格模式把累加和输出 $z_W$ 约束为零,从而把该域元素范围约束(range-constrain)在 $W\cdot K$ 比特之内。

在严格模式下,我们还能确信 $z_{W-1}=k_{W-1}$ 给出了分解中的最后一个窗口。

查表分解(Lookup decomposition)

这个 gadget 利用一张 $K$ 比特的查表表把域元素 $\alpha$ 分解成 $K$ 比特的字(words)。每个 $K$ 比特字 $k_i=z_i-2^K\cdot z_{i+1}$ 都通过在 $K$ 比特表中查表而被范围约束。

查表分解的区域布局使用单个建议列(advice column)$z$,以及两个选择子(selectors)$q_{lookup}$ 和 $q_{running}.$ $$\begin{array}{ccc}z& q_{lookup}& q_{running}\\ z_0& 1& 1\\ z_1& 1& 1\\ ⋮& ⋮& ⋮\\ z_{n-1}& 1& 1\\ z_n& 0& 0\end{array}$$

短范围检查(Short range check)

使用两次 $K$ 比特查表,我们可以把一个域元素 $\alpha$ 范围约束为 $n$ 比特,其中 $n\le K.$ 做法是:

1. 用一次 $K$ 比特查表把 $0\le \alpha <2^K$ 约束在 $K$ 比特之内。
2. 用一次 $K$ 比特查表把 $0\le \alpha \cdot 2^{K-n}<2^K$ 约束在 $K$ 比特之内。

查表分解的短变体(short variant)引入了一个 $q_{bitshift}$ 选择子。这里把同一个建议列 $z$ 重命名为 $\text{word}$ 以便表述清晰: $$\begin{array}{cccc}\text{word}& q_{lookup}& q_{running}& q_{bitshift}\\ \alpha & 1& 0& 0\\ {\alpha }^{\prime }& 1& 0& 1\\ 2^{K-n}& 0& 0& 0\end{array}$$

其中 ${\alpha }^{\prime }=\alpha \cdot 2^{K-n}.$ 注意 $2^{K-n}$ 在密钥生成(keygen)时被赋到一个固定列里,并在证明(proving)时拷入。它被用在由 $q_{bitshift}$ 选择子启用的门中,以检查 $\alpha$ 是否被正确地移位(shifted): $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{bitshift}\cdot ((\alpha \cdot 2^{K-n})-{\alpha }^{\prime })\end{array}$$

合并的查表表达式

由于查表分解及其短变体都使用同一张查表表,我们把它们的查表输入表达式合并成一个:

$$q_{lookup}\cdot \left(q_{running}\cdot (z_i-2^K\cdot z_{i+1})+(1-q_{running})\cdot \text{word}\right)$$

其中 $z_i$ 和 $\text{word}$ 是同一个单元(cell)(此处为了用法上的清晰而加以区分)。

短范围分解(Short range decomposition)

对于一个短范围(例如 $[0,\text{range})$,其中 $\text{range}\le 8$),我们可以用一个 $\text{range}$ 次多项式约束来范围约束每个字,而不必用查表: $$\text{range\_check}(word,range)=\text{word}\cdot (1-\text{word})\cdots (\text{range}-1-\text{word}).$$