零知识证明的最小理论框架

Scope: relation、view、simulator 与 extractor 的最小定义链。

后面整条 ZK 系列都会调用同一批对象：relation、language、instance、witness、prover、verifier、transcript、view、simulator、extractor。本篇先固定它们的类型、量词和相互关系。

completeness、soundness、zero knowledge 与 knowledge soundness 分别约束不同事件。honest-verifier 结论也不能直接推广到任意 verifier；argument 的可靠性还带有计算有界条件。混用这些层次会直接破坏后续的安全性论证。

下面从 \(R(x, w)\) 定义语言和接受事件，再定义 verifier view 与 simulator 的分布关系，最后给出 argument/proof 与 knowledge soundness 的边界。^{1 2}

First Principles: Relation, Language, Instance, Witness

零知识证明不是“证明一个命题”这么宽泛。它的最小对象是一个二元关系

\[ R \subseteq \mathcal{X} \times \mathcal{W}, \]

其中 \(x \in \mathcal{X}\) 是 instance，\(w \in \mathcal{W}\) 是 witness。由关系 \(R\) 诱导出的语言是

\[ L_R = \{x \in \mathcal{X} \mid \exists w \in \mathcal{W},\ R(x, w) = 1 \}. \]

这一步必须先固定，因为后面所有性质都围绕下面这个结构展开:

• prover 试图说服 verifier 某个 \(x\) 属于 \(L_R\)
• witness \(w\) 是 prover 的额外信息，使得 \(R(x, w) = 1\)
• verifier 通常不直接看到 \(w\)

Formal Definition. 一个零知识协议以 relation membership 为对象：给定公开实例 \(x\)，证明者持有见证 \(w\)，并满足 \(R(x, w)=1\)。

例如，离散对数关系可以写成

\[ R_{\mathrm{DL}}((G, g, y), w) = 1 \iff y = g^w. \]

这里公开实例是 \((G, g, y)\)，见证是指数 \(w\)。这已经足够支撑后面 Schnorr 风格 proof of knowledge 的讨论，但本文先停在接口层，不展开具体协议。

Transcript Versus Verifier View

进入交互之后，至少要区分两个对象:

1. transcript: 双方发送的消息序列
2. verifier view: verifier 在执行中“看到”的全部信息

如果协议轮数为 \(t\)，那么 transcript 可写成

\[ \tau = (m_1, m_2, \dots, m_t). \]

但 verifier view 通常比 transcript 更大。对于一个 verifier \(V^{*}\)，它的 view 可以写成

\[ \mathrm{View}_{V^{*}}^{P}(x, w; z) = (x, z, r, m_1, \dots, m_t), \]

其中 \(r\) 是 verifier 的随机性，\(z\) 是 auxiliary input。后面 zero knowledge 定义里，simulator 要模拟的是这个 view 的分布，而不只是消息串本身。

transcript 是外层消息对象，view 是包含随机性和辅助输入的分布对象。zero knowledge 必须在后者上陈述。

一个 transcript 级数值例子

取模 23 乘法群中阶为 11 的子群，令 \(g=2\)，witness 为 \(w=3\)，公开值为

\[ y=g^w=2^3=8 \pmod {23}. \]

用 Schnorr 的三步消息做一个接口检查。prover 取 \(r=4\)，得到 \(a=g^r=16\)；verifier 取 challenge \(e=5\)；prover 返回

\[ z=r+ew=4+5\cdot 3=8 \pmod {11}. \]

于是公开 transcript 为

\[ \tau=(a,e,z)=(16,5,8), \]

且验证等式成立：

\[ 2^8=16\cdot 8^5=3 \pmod {23}. \]

这个 transcript 没有记录 prover 的 \(r\) 或 witness \(w\)。honest verifier 的 view 还包含自己的随机带；在这个例子里可写成 \((y,e,a,z)=(8,5,16,8)\)。simulator 无需 \(w\)：它先选 \((e,z)=(5,8)\)，再计算

\[ a=g^z y^{-e}=16 \pmod {23}. \]

模拟结果与上面的 view 相同。这里仅展示“要模拟什么”；分布相等的证明留到 Sigma 协议一篇。

Interactive Proof 的最小定义

现在引入两台交互机器: prover \(P\) 与 verifier \(V\)。给定 instance \(x\)，若 prover 还持有见证 \(w\)，则运行记为

\[ \langle P(w), V \rangle(x). \]

verifier 最终输出 accept 或 reject。交互证明的第一层只有两个性质: completeness 和 soundness。

Completeness

当 \(x \in L_R\) 且 prover 确实持有满足 \(R(x, w)=1\) 的 witness 时，诚实双方运行应当接受。形式上可写成

\[ \Pr[\langle P(w), V \rangle(x) = 1] \ge 1 - \varepsilon_c(\lambda), \]

其中 \(\varepsilon_c(\lambda)\) 通常是 negligible，很多协议甚至要求 perfect completeness，即接受概率恰好为 \(1\)。

completeness 只回答一个问题: 真命题加真见证时，系统会不会把正确输入误杀。它不涉及“学到了什么”，也不涉及“伪造者能做到什么”。

Soundness

soundness 约束的是假命题。若 \(x \notin L_R\)，则任意作弊 prover \(P^{*}\) 都不应高概率骗过 verifier:

\[ \Pr[\langle P^{*}, V \rangle(x) = 1] \le \varepsilon_s(\lambda). \]

这条公式的含义由量词顺序决定：

• 先固定一个假的 instance \(x \notin L_R\)
• 再对任意作弊 prover \(P^{*}\) 取上界
• 最后要求接受概率足够小

很多口语化解释会把 soundness 说成“证明者不会撒谎”。这不准确。soundness 只是在说: 对不在语言里的实例，想让 verifier 接受会很难。

Proof Versus Argument

这一层马上出现第一条硬边界。

如果 soundness 对任意甚至无限算力 prover 都成立，我们通常称其为 proof。若 soundness 只对 probabilistic polynomial-time cheating prover 成立，那么它是 argument。

所以：

• proof: 信息论或无条件地排除了伪造接受
• argument: 只在计算边界内排除了伪造接受

现代零知识系统里，大量对象其实是 argument，不是 proof。原因很简单: 一旦 soundness 依赖离散对数、pairing hardness、Fiat-Shamir random oracle、low-degree testing 假设之类的计算前提，它就已经不再是对无限算力 prover 的陈述。

这一点必须在第一篇就写清楚，否则后面很容易把“系统很安全”误读成“这是 proof，而不是 argument”。

从 Verifier View 到 Zero Knowledge

到目前为止，我们只约束了“真的要能过，假的不该过”。这还不是零知识。zero knowledge 讨论的是: 在接受性之外，verifier 究竟学到了什么。

最常见的误解是把它说成“验证者没有获得任何信息”。这句话几乎总是错误的，因为 verifier 至少学到了一个事实:

\[ x \in L_R. \]

zero knowledge 要求 verifier 除 statement validity 及其高效推论外，不获得额外知识。simulator 将这句话变成可检验的分布命题。

Honest Verifier 的 View

若先只看 honest verifier，定义会简单一些。诚实 verifier \(V\) 按协议规定产生随机性和挑战，因而其 view 分布是确定的：

\[ \mathrm{View}_{V}^{P}(x, w) = (x, r, \tau). \]

如果存在一个高效算法 \(\mathrm{Sim}\)，仅从公开 instance \(x\) 就能生成一个分布，与真实交互中的 verifier view 近似不可区分，那么我们说协议是 zero knowledge 的某种形式。

形式上：

\[ \mathrm{Sim}(x) \approx \mathrm{View}_{V}^{P}(x, w). \]

这里的 \(\approx\) 需要具体化。

Perfect, Statistical, Computational

根据“近似”的强弱不同，zero knowledge 分成三层:

1. perfect zero knowledge: 两个分布完全相同
2. statistical zero knowledge: 两个分布的统计距离可忽略
3. computational zero knowledge: 任意高效 distinguisher 都无法有效区分

强弱关系是

\[ \text{perfect} \Rightarrow \text{statistical} \Rightarrow \text{computational}. \]

如果一个协议只对诚实 verifier 满足这个条件，通常称为 HVZK, honest-verifier zero knowledge。若对任意多项式时间恶意 verifier \(V^{*}\) 都存在 simulator，则才是更一般的 ZK:

\[ \forall V^{*} \in \mathrm{PPT},\ \exists \mathrm{Sim}_{V^{*}}\ \text{s.t.}\ \mathrm{Sim}_{V^{*}}(x, z) \approx \mathrm{View}_{V^{*}}^{P}(x, w; z). \]

这比 HVZK 强得多，因为恶意 verifier 可以偏离协议、嵌入辅助输入、按自选策略生成挑战。

Key Observation. zero knowledge 约束 real view distribution 与 simulated view distribution 的距离。

为什么直觉不够: 一条最小定义链

现在把前面的对象串起来。

给定 relation \(R\)，我们先得到语言

\[ L_R = \{x \mid \exists w,\ R(x,w)=1\}. \]

随后定义一个交互协议 \((P, V)\)，它必须先满足：

1. completeness: 真实例加真 witness 能让 verifier 接受
2. soundness or argument soundness: 假实例不能被高概率伪造为真

但如果要称其为 zero knowledge，还必须再补一条分布要求：

3. 对某类 verifier，真实 view 与 simulator 输出不可区分

用更压缩的写法，这条链是

\[ R(x,w)=1 \Longrightarrow x \in L_R \Longrightarrow \Pr[\langle P(w),V\rangle(x)=1]\ \text{高} \]

以及

\[ x \notin L_R \Longrightarrow \Pr[\langle P^{*},V\rangle(x)=1]\ \text{低}, \]

同时

\[ \mathrm{View}_{V^{*}}^{P}(x,w;z) \approx \mathrm{Sim}_{V^{*}}(x,z). \]

这三条属于三个独立维度：

• completeness 关心正确性
• soundness 关心伪造接受
• zero knowledge 关心 view distribution

如果不把 verifier view 写出来，“验证者没有获得额外信息”这句话其实没有参照对象。额外信息相对于什么定义？是 transcript，还是 verifier 的内部随机性，还是包含 auxiliary input 的完整 execution state？这些不写清楚，zero knowledge 就只剩修辞。

HVZK 为什么不等于 Full ZK

HVZK 的 simulator 只需要重现诚实 verifier 的 view。很多经典协议在这一步并不难，因为诚实 verifier 的挑战或随机性是按固定分布来的，simulator 可以“先采 challenge，再倒推出 transcript”。

但一旦 verifier 恶意化，问题就变了:

• verifier 可以让消息依赖辅助输入 \(z\)
• verifier 可以选择异常挑战分布
• verifier 可以把协议嵌进更大的环境中联合执行

所以 HVZK 常常只是第一步，不是最终目标。后面看到 Fiat-Shamir 时，这个边界尤其关键: 某些协议的 HVZK 很自然，但转到非交互或更强环境之后，定义和证明义务都会变。

参数边界也属于定义的一部分

还需要避免一个常见偷懒动作: 只写“概率很小”而不写小到什么程度。

密码学里通常要求错误概率是 negligible function，即对任意多项式 \(p(\lambda)\)，在足够大安全参数 \(\lambda\) 下都有

\[ \mu(\lambda) < \frac{1}{p(\lambda)}. \]

不写 negligible，只说“很难”或“几乎不可能”，在理论上没有可组合性。因为后续规约、并行重复、知识提取、Fiat-Shamir 转换，都会显式消耗这些误差项。

Knowledge Soundness 不是 Plain Soundness

plain soundness 只讨论假实例 \(x \notin L_R\)。它说的是: 伪造一个假命题的接受记录很难。

knowledge soundness 要求更强。它讨论的是另一件事:

如果某个 prover 能让 verifier 接受一个 instance，那么它是否“真的知道”某个 witness？

这就引入 extractor。非正式地说，若存在一个高效算法 \(E\)，能够通过访问 prover 的行为恢复出 witness，那么协议就有 proof of knowledge 风格的保证。一个常见接口写法是:

\[ \Pr[\text{accept}] - \Pr[R(x, E^{P^{*}}(x)) = 1] \le \kappa(\lambda), \]

其中 \(\kappa(\lambda)\) 是 knowledge error，用来界定接受概率与可抽取性之间允许存在的缺口。

这里要特别注意两点。

第一，Soundness 与 Knowledge Soundness 的量词不同

plain soundness 只需要保证:

\[ x \notin L_R \Rightarrow \Pr[\text{accept}] \text{ 很低}. \]

knowledge soundness 则要求:

\[ \text{若 } \Pr[\text{accept}] \text{ 足够高，则应能构造 extractor 恢复 witness。} \]

前者只排除了“假命题骗过系统”，后者还试图把“成功证明”与“拥有见证”绑定起来。

第二，True Statement 也可能缺少 Knowledge Guarantee

即使 \(x \in L_R\)，plain soundness 仍然什么都没说。因为 soundness 根本不讨论真实例上的作弊 prover。理论上，可能存在一个 prover 能在真实例上制造接受 transcript，但我们却无法从它那里抽取 witness。

这就是为什么后面进入 Sigma 协议、proof of representation、SNARK knowledge soundness 时，extractor 会变成核心对象。只说 soundness 远远不够。

Quick Note. “accepting transcript exists” 与 “prover knows a witness” 不是同义句。两者之间缺的正是 extractor 论证。

一个极小的接口视角

如果把本文压缩成一个后续可复用的模板，可以写成下面这样。

给定公开 instance \(x\)，我们先问：

1. 证明目标是什么语言成员性问题？
2. witness 的形式是什么？
3. verifier 接受的显式条件是什么？
4. 假实例上的伪造概率如何界定？
5. real view 与 simulated view 的距离如何界定？
6. 若要证明 knowledge soundness，extractor 的接口是什么？

后面几乎所有系统都只是把这六个问题搬到不同代数对象上：

• 在承诺与 Sigma 协议里，关系落在群元素与线性关系上
• 在 R1CS/QAP/AIR 里，关系落在向量与多项式恒等式上
• 在 KZG/FRI/PLONKish 里，acceptance condition 变成开点等式、低度性测试或 grand product identity

接口变了，定义链不变。

Summary

零知识证明的最小理论框架并不复杂，但它必须分层:

• relation/language 固定“在证明什么”
• completeness/soundness 固定“何时接受、何时拒绝”
• simulator-based zero knowledge 固定“view 是否可被模拟”
• argument/proof 区分 soundness 的计算边界
• knowledge soundness 通过 extractor 把“接受”与“知道 witness”连接起来

这套分层排除了三类常见误用：把 HVZK 推广成 full ZK，把 argument 写成 proof，以及用 plain soundness 代替 knowledge soundness。每一种误用都会改变证明中的量词或计算假设。

下一篇把这个接口落到有限域、循环群、离散对数与 Pedersen 承诺上。relation 将具体化为群上的代数约束，后续再给出 simulator 与 extractor 的完整构造。

References