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

Sinsemilla

概述

Sinsemilla 是一种抗碰撞(collision-resistant)的哈希(hash)函数和承诺(commitment)方案,其设计目标是在支持查表(lookups)的代数电路模型(如 PLONK 或 Halo 2)中保持高效。

Sinsemilla 的安全性质与 Pedersen 哈希类似;它并非设计用于需要随机预言机(random oracle)、PRF 或抗原像(preimage-resistant)哈希的场合。该哈希函数唯一声称的安全性质是对定长输入的抗碰撞性。

在电路内部,Sinsemilla 的效率大约比代数哈希 Rescue 和 Poseidon 低 4 倍,但在电路外部却比 Rescue 高约 19 倍。与这两种哈希不同的是,Sinsemilla 的抗碰撞性质可以基于已确立至少 20 年的密码学假设来证明。Sinsemilla 还可用作一个计算上绑定(computationally binding)且完美隐藏(perfectly hiding)的承诺方案。

总体思路是把消息切分成 $k$ 比特的小片,对每一片,从我们密码学群中的一张含 $2^k$ 个基底(bases)的表里选出一个。我们用倍加(double-and-add)算法把所选的基底组合起来。最终其安全性可证明地等同于一个向量 Pedersen 哈希,并且充分利用了 Halo 2 所支持的查表功能。

描述

本节是 Sinsemilla 工作原理的概述:规范性的定义请参阅协议规范中的 §5.4.1.9 Sinsemilla 哈希函数。我们下文使用的不完全点加(incomplete point addition)运算符 ⸭ 也在那里定义。

设 $\mathbb{G}$ 是一个素数阶 $q$ 的密码学群。我们用加法记号书写 $\mathbb{G}$,其单位元为 $\mathcal{O}$,并用 $[m]P$ 表示 $P$ 被 $m$ 作标量乘法。

设 $k\ge 1$ 是一个基于效率考量选取的整数(表的大小将为 $2^k$)。设 $n$ 是一个整数,对每个实例化是固定的,使得消息为 $kn$ 比特,其中 $2^n\le \frac{q-1}{2}$。必要时我们用零填充(zero-padding)补到下一个 $k$ 比特的整数倍。

$\text{Setup}$:选取 $Q$ 和 $P[\mathrm{0..}{2}^k-1]$ 作为 $\mathbb{G}$ 的 $2^k+1$ 个独立的、可验证随机(verifiably random)的生成元,方法是使用一个合适的"哈希进 $\mathbb{G}$"(hash into $\mathbb{G}$)函数,使得 $Q$ 与 $P[\mathrm{0..}{2}^k-1]$ 都不等于 $\mathcal{O}$。

在 Orchard 中,我们将 $Q$ 定义为依赖于一个域分隔符(domain separator)$D$。协议规范用 $\mathcal{Q}(D)$ 替代 $Q$,用 $\mathcal{S}(m)$ 替代 $P[m]$。

$\text{Hash}(M)$:

• 把 $M$ 切分成 $n$ 组,每组 $k$ 比特。把每组解释为一个 $k$ 比特小端(little-endian)整数 $m_i$。
• 令 ${\mathsf{Acc}}_0:=Q$
• 对 $i$ 从 $0$ 到 $n-1$:
  • 令 ${\mathsf{Acc}}_{i+1}:=({\mathsf{Acc}}_i⸭P[m_{i+1}])⸭{\mathsf{Acc}}_i$
• 返回 ${\mathsf{Acc}}_n$

设 $\text{ShortHash}(M)$ 为 $\text{Hash}(M)$ 的 $x$ 坐标。(这里假定 $\mathbb{G}$ 是短 Weierstrass 形式(short Weierstrass form)的素数阶椭圆曲线,对 Pallas 和 Vesta 而言确实如此。)

把一个倍加 $[2]A+R$ 表示为 $(A+R)+A$ 会稍微高效一些。我们也使用不完全加法:Sinsemilla 安全性论证中证明了,在 $\mathbb{G}$ 为素数阶短 Weierstrass 椭圆曲线的情形下,加法的一个例外情形(exceptional case)将会导致求出一个离散对数(discrete logarithm),而即便对于敌手构造的输入,这也可以假定以可忽略的概率发生。

用作承诺方案

独立于 $Q$ 与 $P[\mathrm{0..}{2}^k-1]$ 另选一个生成元 $H$。

承诺的随机量 $r$ 在 $[0,q)$ 上均匀选取。

令 ${\text{Commit}}_r(M)=\text{Hash}(M)⸭[r]H$。

设 ${\text{ShortCommit}}_r(M)$ 为 ${\text{Commit}}_r(M)$ 的 $x\text{ 坐标}$。(这同样假定 $\mathbb{G}$ 是短 Weierstrass 形式的素数阶椭圆曲线。)

注意,与简单的 Pedersen 承诺不同,这个承诺方案($\text{Commit}$ 或 $\text{ShortCommit}$)不是加法同态(additively homomorphic)的。

高效实现

设计的目标是,在给定表大小的前提下,优化算法每一步(每步需要在 $\mathbb{G}$ 中作一次倍乘和一次加法)所能处理的比特数。使用一张大小为 $2^k$ 个群元素的单表,我们每次可以处理 $k$ 比特。

不完全加法

在 Sinsemilla 的每一步中,我们要计算 $A_{i+1}:=(A_i⸭P_i)⸭A_i$。设 $R_i:=A_i⸭P_i$ 为中间结果,使得 $A_{i+1}:=A_i⸭R_i$。 回顾不完全加法公式:

$$\begin{array}{rl}{x}_3& ={\left(\frac{y_1-y_2}{x_1-x_2}\right)}^2-x_1-x_2\\ y_3& =\frac{y_1-y_2}{x_1-x_2}\cdot (x_1-x_3)-y_1\end{array}$$

令 $\lambda =\frac{y_1-y_2}{x_1-x_2}$。依次代入每个不完全加法的坐标并整理,我们得到

$$\begin{array}{rl}{\lambda }_{1,i}& =\frac{y_{A,i}-y_{P,i}}{x_{A,i}-x_{P,i}}\\ & ⟹y_{A,i}-y_{P,i}={\lambda }_{1,i}\cdot (x_{A,i}-x_{P,i})\\ & ⟹y_{P,i}=y_{A,i}-{\lambda }_{1,i}\cdot (x_{A,i}-x_{P,i})\\ x_{R,i}& ={\lambda }_{1,i}^2-x_{A,i}-x_{P,i}\\ y_{R,i}& ={\lambda }_{1,i}\cdot (x_{A,i}-x_{R,i})-y_{A,i}\end{array}$$ 以及 $$\begin{array}{rl}{\lambda }_{2,i}& =\frac{y_{A,i}-y_{R,i}}{x_{A,i}-x_{R,i}}\\ & ⟹y_{A,i}-y_{R,i}={\lambda }_{2,i}\cdot (x_{A,i}-x_{R,i})\\ & ⟹y_{A,i}-\left({\lambda }_{1,i}\cdot (x_{A,i}-x_{R,i})-y_{A,i}\right)={\lambda }_{2,i}\cdot (x_{A,i}-x_{R,i})\\ & ⟹2\cdot y_{A,i}=({\lambda }_{1,i}+{\lambda }_{2,i})\cdot (x_{A,i}-x_{R,i})\\ x_{A,i+1}& ={\lambda }_{2,i}^2-x_{A,i}-x_{R,i}\\ y_{A,i+1}& ={\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i+1})-y_{A,i}.\end{array}$$

约束程序

令 $\mathcal{P}=\left\{(j,x_{P[j]},y_{P[j]})\text{ 对 }j\in \{\mathrm{0..}{2}^k-1\}\right\}$。

输入:$m_{\mathrm{1..}=n}$。(这里消息字(message words)的下标从 1 开始,与协议规范一致,但我们让循环从 $i=0$ 开始,使得 $(x_{A,i},y_{A,i})$ 对应协议规范中的 ${\mathsf{Acc}}_i$。)

输出:$(x_{A,n},y_{A,n})$。

• $(x_{A,0},y_{A,0})=Q$
• 对 $i$ 从 $0$ 到 $n-1$:
  • $y_{P,i}=y_{A,i}-{\lambda }_{1,i}\cdot (x_{A,i}-x_{P,i})$
  • $x_{R,i}={\lambda }_{1,i}^2-x_{A,i}-x_{P,i}$
  • $2\cdot y_{A,i}=({\lambda }_{1,i}+{\lambda }_{2,i})\cdot (x_{A,i}-x_{R,i})$
  • $(m_{i+1},x_{P,i},y_{P,i})\in \mathcal{P}$
  • ${\lambda }_{2,i}^2=x_{A,i+1}+x_{R,i}+x_{A,i}$
  • ${\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i+1})=y_{A,i}+y_{A,i+1}$

PLONK / Halo 2 约束

消息分解(decomposition)

我们有一条 $n$ 比特的消息 $m=m_1+2^k{m}_2+...+2^{k\cdot (n-1)}{m}_n$。(注意消息字的下标从 1 开始,与协议规范一致。)

将累加和(running sum)初始化为 $z_0=\alpha$,并定义 $z_{i+1}:=\frac{z_i-m_{i+1}}{2^K}$。最终我们将得到 $z_n=0.$

整理后得到原消息每个字的表达式 $m_{i+1}=z_i-2^k\cdot z_{i+1}$,我们可以在表中对它进行查表。我们把 $z_i$ 和 $z_{i+1}$ 放在同一列的相邻两行,这样就能沿整条消息顺序地施加该约束。

换言之,$z_{n-i}=\sum _{h=0}^{i-1}{2}^{kh}\cdot m_{h+1}$。

对于此处所用的小端分解,累加和初始化为该标量并以 0 结束。而对于变基标量乘法(variable-base scalar multiplication)中所用的大端(big-endian)分解,累加和会从 0 开始,并以恢复出原标量结束。

高效打包(packing)

累加和只适用于单个域元素(field element)内部的消息字。这意味着,如果 $n\ge \mathtt{PrimeField}::NUM\_BITS$,我们就需要多个互不相交的累加和。更长的消息可以通过把消息字拆分到多个域元素中来构造,然后运行下面这些约束的多个实例。

上面 $m_{i+1}$ 的表达式在 $z_i$ 列中需要 $n+1$ 行,这会在相邻列里留下一行空隙,使得 ${\mathsf{Acc}}_i$ 更难累加。为了支持把多个域元素串联起来而不留空隙,我们对 $m_{i+1}$ 使用一个稍复杂、包含一个选择子(selector)的表达式:

$$m_{i+1}=z_i-2^k\cdot q_{run,i}\cdot z_{i+1}$$

这实际上把每个域元素最后一步的 ${\mathbf{z}}_n$ 强制为零,从而让本应作为 ${\mathbf{z}}_n$ 的那个单元(cell)可以被用来为下一个域元素重新初始化累加和。

这样安排好之后,不完全加法累加器几乎可以完全消去 $y_{A,i}$,办法是在当前行和下一行中用 $x$ 和 $\lambda$ 的值进行代换。两个例外是在 Sinsemilla 的起点(那里我们需要约束累加器的初始值为 $Q$)和终点(那里我们需要见证(witness)$y_{A,n}$ 以供 Sinsemilla 之外使用)。

选择子

我们总共需要四个逻辑选择子,用于:

• 控制 Sinsemilla 门(gate)和查表。
• 区分一个累加和中的最后一个消息字与它之前的各个字。
• 标记 Sinsemilla 的开始。
• 标记 Sinsemilla 的结束。

我们对 Sinsemilla 门选择子 $q_{S1}$ 和 Sinsemilla 起始选择子 $q_{S4}$ 使用普通的选择子列。另外两个选择子从单一固定列 $q_{S2}$ 按如下方式合成(synthesized):

$$\begin{array}{rl}{q}_{S3}& =q_{S2}\cdot (q_{S2}-1)\\ q_{run}& =q_{S2}-q_{S3}\end{array}$$

$$\begin{array}{ccc}{q}_{S2}& q_{S3}& q_{run}\\ 0& 0& 0\\ 1& 0& 1\\ 2& 2& 0\end{array}$$

我们在大多数 Sinsemilla 行上把 $q_{S2}$ 设为 $1$,在每个域元素的最后一步设为 $0$,但最后一个域元素例外,那里设为 $2$。然后我们可以用 $q_{S3}$ 在两种约束之间切换:约束相邻两行上经代换的 $y_{A,i+1}$,以及约束 Sinsemilla 末尾处所见证的 $y_{A,n}$:

$${\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i+1})=y_{A,i}+\frac{2-q_{S3}}{2}\cdot y_{A,i+1}+\frac{q_{S3}}{2}\cdot y_{A,n}$$

生成元查表表

Sinsemilla 电路使用了 $2^{10}$ 个预计算的随机生成元。它们被装入一张查表表中: $$\begin{array}{ccc}tabl{e}_{idx}& tabl{e}_x& tabl{e}_y\\ 0& x_{P[0]}& y_{P[0]}\\ 1& x_{P[1]}& y_{P[1]}\\ 2& x_{P[2]}& y_{P[2]}\\ ⋮& ⋮& ⋮\\ 2^{10}-1& x_{P[2^{10}-1]}& y_{P[2^{10}-1]}\end{array}$$

布局(Layout)

$$\begin{array}{cccccccccc}\text{Step}& x_A& x_P& bits& {\lambda }_1& {\lambda }_2& q_{S1}& q_{S2}& q_{S4}& \text{fixed\_y\_Q}\\ 0& x_Q& x_{P[m_1]}& z_0& {\lambda }_{1,0}& {\lambda }_{2,0}& 1& 1& 1& y_Q\\ 1& x_{A,1}& x_{P[m_2]}& z_1& {\lambda }_{1,1}& {\lambda }_{2,1}& 1& 1& 0& 0\\ 2& x_{A,2}& x_{P[m_3]}& z_2& {\lambda }_{1,2}& {\lambda }_{2,2}& 1& 1& 0& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& 1& 1& 0& 0\\ n-1& x_{A,n-1}& x_{P[m_n]}& z_{n-1}& {\lambda }_{1,n-1}& {\lambda }_{2,n-1}& 1& 0& 0& 0\\ 0^{\prime }& x_{A,0}^{\prime }& x_{P[m_1^{\prime }]}& z_0^{\prime }& {\lambda }_{1,0}^{\prime }& {\lambda }_{2,0}^{\prime }& 1& 1& 0& 0\\ 1^{\prime }& x_{A,1}^{\prime }& x_{P[m_2^{\prime }]}& z_1^{\prime }& {\lambda }_{1,1}^{\prime }& {\lambda }_{2,1}^{\prime }& 1& 1& 0& 0\\ 2^{\prime }& x_{A,2}^{\prime }& x_{P[m_3^{\prime }]}& z_2^{\prime }& {\lambda }_{1,2}^{\prime }& {\lambda }_{2,2}^{\prime }& 1& 1& 0& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& 1& 1& 0& 0\\ n-1^{\prime }& x_{A,n-1}^{\prime }& x_{P[m_n^{\prime }]}& z_{n-1}^{\prime }& {\lambda }_{1,n-1}^{\prime }& {\lambda }_{2,n-1}^{\prime }& 1& 2& 0& 0\\ n^{\prime }& x_{A,n}^{\prime }& & & y_{A,n}& & 0& 0& 0& 0\end{array}$$

$x_Q$、$z_0$、$z_0^{\prime }$ 等通过相等约束(equality constraints)拷入。

优化后的 Sinsemilla 门

$$\begin{array}{lrcl}\text{对 }i\in [0,n),\text{ 令}& x_{R,i}& =& {\lambda }_{1,i}^2-x_{A,i}-x_{P,i}\\ & Y_{A,i}& =& ({\lambda }_{1,i}+{\lambda }_{2,i})\cdot (x_{A,i}-x_{R,i})\\ & y_{P,i}& =& Y_{A,i}/2-{\lambda }_{1,i}\cdot (x_{A,i}-x_{P,i})\\ & m_{i+1}& =& z_i-q_{run,i}\cdot z_{i+1}\cdot 2^k\\ & q_{run}& =& q_{S2}-q_{S3}\\ & q_{S3}& =& q_{S2}\cdot (q_{S2}-1)\end{array}$$

Halo 2 电路 API 可以自动代换 $y_{P,i}$、$x_{R,i}$、$Y_{A,i}$ 和 $Y_{A,i+1}$,所以我们无需手动去做。

• $x_{A,0}=x_Q$
• $2\cdot y_Q=Y_{A,0}$
• 对 $i$ 从 $0$ 到 $n-1$:
  • $(m_{i+1},x_{P,i},y_{P,i})\in \mathcal{P}$
  • ${\lambda }_{2,i}^2=x_{A,i+1}+x_{R,i}+x_{A,i}$
  • $4\cdot {\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i+1})=2\cdot Y_{A,i}+(2-q_{S3})\cdot Y_{A,i+1}+2q_{S3}\cdot y_{A,n}$

注意,相对于前面给出的约束程序,最后一个约束的每一项都乘以了 $4$。这是一个小的优化,可以避免除以 $2$。

通过用 $q_{S1}$ 来门控(gating)查表表达式,我们避免了为了让查表论证(lookup argument)通过而用哑值(dummy values)去填充未用单元的需要。优化后的查表值(使用默认下标 $0$)为:

$$\begin{array}{ll}(& q_{S1}\cdot m_{i+1},\\ & q_{S1}\cdot x_{P,i}+(1-q_{S1})\cdot x_{P,0},\\ & q_{S1}\cdot y_{P,i}+(1-q_{S1})\cdot y_{P,0})\end{array}$$

这把查表论证的次数(degree)提高到了 $6$。

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 4& q_{S4}\cdot (2\cdot y_Q-Y_{A,0})=0\\ 6& q_{S1,i}\Rightarrow (m_{i+1},x_{P,i},y_{P,i})\in \mathcal{P}\\ 3& q_{S1,i}\cdot ({\lambda }_{2,i}^2-(x_{A,i+1}+x_{R,i}+x_{A,i}))\\ 5& q_{S1,i}\cdot \left(4\cdot {\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i+1})-(2\cdot Y_{A,i}+(2-q_{S3,i})\cdot Y_{A,i+1}+2\cdot q_{S3,i}\cdot y_{A,n})\right)=0\end{array}$$