译自 halo2 book:https://zcash.github.io/halo2/design/implementation/proofs.html

Halo 2 证明(proofs)

证明作为不透明的字节流

在诸如 bellman 这样的证明系统实现中,存在一个具体的 Proof 结构体,它封装了证明数据,由证明者(prover)返回,并可被传递给验证者(verifier)。

halo2 出于以下几个原因,并不包含任何类似证明的结构:

• 证明结构会包含(若干)曲线点(curve point)和标量(scalar)的向量。这会使证明的序列化/反序列化变得复杂,因为这些向量的长度取决于电路(circuit)的配置。然而,我们不希望把向量的长度编码进证明里,因为在运行时电路是固定的,因此证明大小也是固定的。
• 很容易意外地把某些没有同时放入文字记录(transcript)的东西放进证明结构里,这在开发与实现证明系统时是一种隐患。
• 我们需要能够同时创建多个 PLONK 证明;当这些证明针对同一电路时,它们会共享许多不同的子结构。

因此,halo2 把证明对象当作不透明的字节流来处理。这些字节流的创建与消费都通过文字记录(transcript)进行:

• TranscriptWrite trait 表示我们可以(在证明时)向其写入证明组件的某个对象。
• TranscriptRead trait 表示我们可以(在验证时)从其读取证明组件的某个对象。

至关重要的一点是,TranscriptWrite 的实现负责在把内容哈希进文字记录的同时,也向某个 std::io::Write 缓冲区写入;TranscriptRead/std::io::Read 同理。

作为额外的好处,把证明当作不透明的字节流可确保验证过程把反序列化的开销也计算在内——由于点压缩(point compression),这个开销并不可忽略。

证明编码

一个在曲线 $E({\mathbb{F}}_p)$ 上构造的 Halo 2 证明,被编码为如下内容组成的流:

• 点 $P\in E({\mathbb{F}}_p)$(用于对多项式的承诺,commitment),以及
• 标量 $s\in {\mathbb{F}}_q$(用于多项式的求值,以及盲化值,blinding values)。

对于 Pallas 和 Vesta 曲线,点和标量都采用 32 字节编码,这意味着证明的大小总是 32 字节的倍数。

halo2 crate 支持同时证明一个电路的多个实例,以便共享公共的证明组件和协议逻辑。

在下面的编码描述中,我们将使用以下与电路相关的常量:

• $k$ —— 电路的大小参数(电路有 $2^k$ 行)。
• $A$ —— 建议列(advice column)的数量。
• $F$ —— 固定列(fixed column)的数量。
• $I$ —— 实例列(instance column)的数量。
• $L$ —— 查找论证(lookup argument)的数量。
• $P$ —— 置换论证(permutation argument)的数量。
• ${\text{Col}}_P$ —— 参与置换论证 $P$ 的列的数量。
• $D$ —— 商多项式(quotient polynomial)的最大次数。
• $Q_A$ —— 建议列查询(query)的数量。
• $Q_F$ —— 固定列查询的数量。
• $Q_I$ —— 实例列查询的数量。
• $M$ —— 同时被证明的电路实例的数量。

由于证明编码直接遵循文字记录,我们可以把编码拆分成与 Halo 2 协议相对应的若干部分:

• PLONK 承诺:

  • $A$ 个点(重复 $M$ 次)。
  • $2L$ 个点(重复 $M$ 次)。
  • $P$ 个点(重复 $M$ 次)。
  • $L$ 个点(重复 $M$ 次)。

• 消去论证(vanishing argument):

  • $D-1$ 个点。
  • $Q_I$ 个标量(重复 $M$ 次)。
  • $Q_A$ 个标量(重复 $M$ 次)。
  • $Q_F$ 个标量。
  • $D-1$ 个标量。

• PLONK 求值:

  • $(2+{\text{Col}}_P)\times P$ 个标量(重复 $M$ 次)。
  • $5L$ 个标量(重复 $M$ 次)。

• 多点打开论证(multiopening argument):

  • 1 个点。
  • 多点打开论证中每组点对应 1 个标量。

• 多项式承诺方案(polynomial commitment scheme):

  • $1+2k$ 个点。
  • $2$ 个标量。