译自 halo2 book:https://zcash.github.io/halo2/design/gadgets/sinsemilla/merkle-crh.html

MerkleCRH

消息分解(decomposition)

$\mathsf{SinsemillaHash}$ 被用在 $\mathsf{MerkleCR}{\mathsf{H}}^{\mathsf{Orchard}}$ 哈希函数中。$\mathsf{SinsemillaHash}$ 的输入是:

$$l\star ||\text{left}\star ||\text{right}\star ,$$

其中:

• $l\star ={\text{I2LEBSP}}_{10}(l)={\text{I2LEBSP}}_{10}({\text{MerkleDepth}}^{\text{Orchard}}-1-\text{layer})$,
• $\text{left}\star ={\text{I2LEBSP}}_{{\ell }_{\text{Merkle}}^{\text{Orchard}}}(\text{left})$,
• $\text{right}\star ={\text{I2LEBSP}}_{{\ell }_{\text{Merkle}}^{\text{Orchard}}}(\text{right})$,

其中 ${\ell }_{\text{Merkle}}^{\text{Orchard}}=255.$ $\text{left}\star$ 和 $\text{right}\star$ 允许是 $\text{left}$ 和 $\text{right}$ 的非规范(non-canonical)$255$ 比特编码。

Sinsemilla 以 10 比特的整数倍进行操作,所以我们首先把消息分解(decomposing)成若干块(chunks):

$$\begin{array}{rl}l\star & =a_0\\ \text{left}\star & =a_1||b_0||b_1\\ & =(\text{bits }\mathrm{0..}=239\text{ of }\text{ left })||(\text{bits }\mathrm{240..}=249\text{ of }\text{left})||(\text{bits }\mathrm{250..}=254\text{ of }\text{left})\\ \text{right}\star & =b_2||c\\ & =(\text{bits }\mathrm{0..}=4\text{ of }\text{right})||(\text{bits }\mathrm{5..}=254\text{ of }\text{right})\end{array}$$

然后我们把这些块重新组合(recompose)成若干 MessagePiece(消息片):

$$\begin{array}{cl}\text{Length (bits)}& \text{Piece}\\ 250& a=a_0||a_1\\ 20& b=b_0||b_1||b_2\\ 250& c\end{array}$$

每个消息片都被 $\mathsf{SinsemillaHash}$ 约束到其所声明的长度。此外, $\text{left}$ 和 $\text{right}$ 作为域元素(field elements)被见证(witnessed),所以我们知道它们 是规范的(canonical)。然而,我们还需要额外的约束来确保这些块具有正确的比特长度(否则它们可能在分解中相互重叠,从而允许证明者(prover)见证出任意的 $\mathsf{SinsemillaHash}$ 消息)。

其中一些约束可以用可复用的电路 gadget 来实现。我们定义一个由选择子(selector)$q_{\mathsf{decompose}}$ 控制的自定义门(custom gate)来承载其余的约束。

比特长度约束

块 $c$ 由 Sinsemilla 直接约束。我们用以下约束来约束其余的块:

$a_0,a_1$

$z_{1,a}$,即 $\text{SinsemillaHash}(a)$ 的下标为 1 的累加和(running sum)输出,被拷入门中。$z_{1,a}$ 已被 $\text{SinsemillaHash}$ 约束为 $240$ 比特,并且恰好就是 $a_1$。我们利用 $a,z_{1,a}$ 来恢复块 $a_0$: $$\begin{array}{rl}{z}_{1,a}& =\frac{a-a_0}{2^{10}}\\ & =a_1\\ ⟹a_0& =a-z_{1,a}\cdot 2^{10}.\end{array}$$

$b_0,b_1,b_2$

$z_{1,b}$,即 $\text{SinsemillaHash}(b)$ 的下标为 1 的累加和输出,被拷入门中。$z_{1,b}$ 已被 $\text{SinsemillaHash}$ 约束为 $10$ 比特。我们在该门之外见证子片(subpieces)$b_1,b_2$,并各自约束它们为 $5$ 比特。在门内,我们检查 $$b_1+2^5\cdot b_2=z_{1,b}.$$ 我们还利用 $(b,z_{1,b})$ 恢复子片 $b_0$: $$\begin{array}{rl}{z}_{1,b}& =\frac{b-b_{\mathrm{0..}=10}}{2^{10}}\\ ⟹b_0& =b-(z_{1,b}\cdot 2^{10}).\end{array}$$

约束

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ & \text{short\_lookup\_range\_check}(b_1,5)\\ & \text{short\_lookup\_range\_check}(b_2,5)\\ 2& q_{\mathsf{decompose}}\cdot (z_{1,b}-(b_1+b_2\cdot 2^5))=0\end{array}$$

其中 $\text{short\_lookup\_range\_check}()$ 是一个 短查表范围检查(short lookup range check)。

分解约束

至此我们已经导出或见证了每个子片,并对每个子片做了范围约束:

• $a_0$($10$ 比特),导出为 $a_0=a-2^{10}\cdot z_{1,a}$;
• $a_1$($240$ 比特),等于 $z_{1,a}$;
• $b_0$($10$ 比特),导出为 $b_0=b-2^{10}\cdot z_{1,b}$;
• $b_1$($5$ 比特)在门外被见证并约束;
• $b_2$($5$ 比特)在门外被见证并约束;
• $c$($250$ 比特)在门外被见证并约束。
• $b_1+2^5\cdot b_2$ 被约束为等于 $z_{1,b}$。

现在我们可以用它们来重建原始的域元素输入:

$$\begin{array}{rl}l& =a_0\\ \mathsf{left}& =a_1+2^{240}\cdot b_0+2^{250}\cdot b_1\\ \mathsf{right}& =b_2+2^5\cdot c\end{array}$$

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{decompose}}\cdot (a_0-l)=0\\ 2& q_{\mathsf{decompose}}\cdot (a_1+(b_0+b_1\cdot 2^{10})\cdot 2^{240}-\mathsf{left})=0\\ 2& q_{\mathsf{decompose}}\cdot (b_2+c\cdot 2^5-\mathsf{right})=0\end{array}$$

区域布局(Region layout)

$$\begin{array}{cccccc}& & & & & q_{\mathsf{decompose}}\\ a& b& c& \mathsf{left}& \mathsf{right}& 1\\ z_{1,a}& z_{1,b}& b_1& b_2& l& 0\end{array}$$

电路组件

Orchard 电路横跨 $10$ 个建议列(advice columns),而 $\text{Sinsemilla}$ 芯片(chip)只使用 $5$ 个建议列。我们把路径哈希(path hashing)均匀地分摊到两个 $\text{Sinsemilla}$ 芯片上,以便更好地利用可用的电路面积。由于上一层哈希的输出会被拷入下一层哈希,即使在从一个芯片转到另一个芯片时,我们也能保持连续性。