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

协议描述(Protocol Description)

预备知识

我们取 $λ$ 作为安全参数(security parameter),除非另有明确说明,所有算法和敌手(adversary)都是在该安全参数下以多项式时间运行的概率性(交互式)图灵机。我们用 $negl (λ)$ 表示一个在 $λ$ 上可忽略(negligible)的函数。

我们令 $G$ 表示一个素数阶 $p$ 的循环群。群的单位元写作 $O$ 。我们把 $G$ 中元素的标量(scalar)称为大小为 $p$ 的标量域(scalar field) $F$ 中的元素。群元素用大写字母书写,标量用小写字母或希腊字母书写。标量向量或群元素向量用粗体书写,即 $a \in F^{n}$ 和 $G \in G^{n}$ 。群运算以加法形式书写,群元素 $G$ 乘以标量 $a$ 写作 $[a] G$ 。

我们经常用记号 $⟨ a, b ⟩$ 来表示两个等长标量向量 $a, b \in F^{n}$ 的内积(inner product)。我们也用这个记号来表示群元素的线性组合,例如 $⟨ a, G ⟩$ ,其中 $a \in F^{n}, G \in G^{n}$ ,在实践中通过多标量乘法(multiscalar multiplication)来计算。

我们用 $0^{n}$ 表示一个长度为 $n$ 、仅包含 $F$ 中零元素的向量。

离散对数关系问题(Discrete Log Relation Problem)。 优势度量(advantage metric) $Adv_{G, n}^{dl-rel} (A, λ) = Pr [G_{G, n}^{dl-rel} (A, λ)]$ 是相对于以下博弈(game)定义的。 $\underline{Game G_{G, n}^{dl-rel} (A, λ) :} G \leftarrow G_{λ}^{n} a \leftarrow A (G) Return (⟨ a, G ⟩ = O \land a \neq = 0^{n})$

给定一个 $n$ 长度的群元素向量 $G \in G^{n}$ ,离散对数关系问题 要求找出 $g \in F^{n}$ 使得 $g \neq = 0^{n}$ 但 $⟨ g, G ⟩ = O$ ,我们称之为一个 非平凡的 离散对数关系。如 [JT20] 的引理 3 所示,该问题的困难性可由群中离散对数问题的困难性紧致地推出。形式上,我们使用上面定义的博弈 $G_{G, n}^{dl-rel}$ 来刻画该问题。

交互式证明(Interactive Proofs)

交互式证明 是一个三元组算法 $IP = (Setup, P, V)$ 。算法 $Setup (1^{λ})$ 输出某些 公共参数(public parameters),通常用 $pp$ 来指代。证明者 $P$ 和验证者 $V$ 是交互式机器(可访问 $pp$ ),我们用 $⟨ P (x), V (y)⟩$ 表示一个在它们之间以输入 $x, y$ 执行两方协议的算法。该协议的输出是它们交互的一个 副本(transcript),包含 $P$ 与 $V$ 之间发送的所有消息。在协议结束时,验证者输出一个决策比特。

零知识知识论证(Zero knowledge Arguments of Knowledge)

知识证明(proofs of knowledge)是这样的交互式证明:证明者旨在使验证者相信,对于某个陈述 $x$ 和多项式时间可判定关系 $R$ ,他们知道一个证据(witness) $w$ 使得 $(x, w) \in R$ 。我们将处理 论证(arguments) 形式的知识证明,它假设证明者在计算上是有界的。

我们将通过四种安全概念来分析知识论证。

完备性(Completeness): 如果证明者持有一个有效的证据,他们能总是说服验证者吗?理解这一性质很有用,因为它可能会对其他安全概念产生影响。
可靠性(Soundness): 一个作弊的证明者能否虚假地使验证者相信一个实际上并不正确的陈述的正确性?我们把作弊证明者能虚假地说服验证者的概率称为 可靠性误差(soundness error)。
知识可靠性(Knowledge soundness): 当验证者被说服相信陈述是正确的时,证明者是否确实持有("知道")一个有效的证据?我们把作弊证明者虚假地使验证者相信这种知识的概率称为 知识误差(knowledge error)。
零知识(Zero knowledge): 验证者除了能从陈述的正确性以及证明者拥有有效证据这一事实推断出来的内容之外,是否还学到了别的东西?

首先,我们来看完备性的简单定义。

完美完备性(Perfect Completeness)。 一个交互式论证 $(Setup, P, V)$ 具有 完美完备性,如果对于所有多项式时间可判定关系 $R$ 以及所有非一致(non-uniform)多项式时间敌手 $A$ $P r [(x, w) \in / R \lor ⟨ P (pp, x, w), V (pp, x)⟩ accepts pp \leftarrow Setup (1^{λ}) (x, w) \leftarrow A (pp)] = 1$

可靠性

使我们的分析复杂化的是,尽管我们的协议被描述为一个交互式论证,但它在实践中是通过使用 Fiat-Shamir 变换实现为一个 非交互式论证(non-interactive argument) 的。

公开掷币(Public coin)。 我们说一个交互式论证是 公开掷币(public coin) 的,当验证者发送的所有消息都各自以新鲜随机性采样时。

Fiat-Shamir 变换(Fiat-Shamir transformation)。 在这个变换中,一个交互式、公开掷币的论证可以在 随机预言机模型(random oracle model) 下被变为 非交互式,方法是用一个产生足够随机外观输出的密码学强哈希函数替换验证者算法。

这一变换意味着,在具体协议中,一个作弊的证明者可以通过分叉副本(forking the transcript)并向验证者发送新消息来轻易地"回退(rewind)"验证者。研究我们的构造在应用这一变换之后的具体安全性很重要。幸运的是,我们能够遵循 Ghoshal 和 Tessaro([GT20])的一套分析框架,它已被应用于与我们类似的构造。

我们将通过 状态恢复可靠性(state-restoration soundness) 这一概念来研究我们的协议。在这个模型中,允许(作弊的)证明者将验证者回退到它之前所处的任意状态。如果证明者能够产生一个被接受的副本,则他们获胜。

状态恢复可靠性(State-Restoration Soundness)。 设 $IP$ 是一个具有 $r = r (λ)$ 个验证者挑战(challenge)的交互式论证,并设第 $i$ 个挑战从 $Ch_{i}$ 中采样。状态恢复证明者 $P$ 的优势度量 $Adv_{IP}^{SRS} (P, λ) = Pr [SRS_{P}^{IP} (λ)]$ 是相对于以下博弈定义的。 $\underline{Game SRS_{IP}^{P} (λ) :} win \leftarrow false; tr \leftarrow ϵ pp \leftarrow IP . Setup (1^{λ}) (x, st_{P}) \leftarrow P_{λ} (pp) Run P_{λ}^{O_{SRS}} (st_{P}) Return win \underline{Oracle O_{SRS} (τ = (a_{1}, c_{1}, ..., a_{i - 1}, c_{i - 1}), a_{i}) :} If τ \in tr then If i \leq r then c_{i} \leftarrow Ch_{i}; tr \leftarrow tr ∣∣ (τ, a_{i}, c_{i}); Return c_{i} Else if i = r + 1 then d \leftarrow IP . V (pp, x, (τ, a_{i})); tr \leftarrow (τ, a_{i}) If d = 1 then win \leftarrow true Return d Return ⊥$

如 [GT20](定理 1)所示,状态恢复可靠性与应用 Fiat-Shamir 变换之后的可靠性紧致相关。

知识可靠性

我们将证明,我们的协议满足一种被称为 证据扩展模拟(witness extended emulation) 的、被强化的知识可靠性概念。非形式地说,这一概念指出:对于任何成功的证明者算法,都存在一个高效的 模拟器(emulator),它能通过回退该算法并向其提供新鲜随机性来从中提取出一个证据。

然而,我们必须对证据扩展模拟的定义稍作调整,以考虑到我们的证明者是状态恢复证明者并且能够回退验证者这一事实。此外,为了避免在证据提取过程中需要回退状态恢复证明者,我们在代数群模型(algebraic group model)下研究我们的协议。

代数群模型(Algebraic Group Model,AGM)。 一个敌手 $P_{alg}$ 被称为 代数的(algebraic),如果每当它输出一个群元素 $X$ 时,它也输出一个 表示(representation) $x \in F^{n}$ 使得 $⟨ x, G ⟩ = X$ ,其中 $G \in G^{n}$ 是 $P_{alg}$ 迄今为止所见到的群元素向量。在记号上,我们写 ${X}$ 来表示带有该表示增强的群元素 $X$ 。我们也写 ${X}_{i}^{G}$ 来标识 $X$ 的表示中对应于 $G_{i}$ 的分量。换言之, $X = i = 0 \sum n - 1 [{X}_{i}^{G}] G_{i}$

代数群模型允许我们对某些协议执行所谓的"在线(online)"提取:提取器(extractor)可以从单个(被接受的)副本的表示本身中获得证据。

状态恢复证据扩展模拟(State Restoration Witness Extended Emulation) 设 $IP$ 是一个针对关系 $R$ 、具有 $r = r (λ)$ 个挑战的交互式论证。我们对于所有非一致的代数证明者 $P_{alg}$ 、提取器 $E$ ,以及计算上无界的区分器(distinguisher) $D$ 定义优势度量 $Adv_{IP, R}^{sr-wee} (P_{alg}, D, E, λ) = Pr [WEE-real_{IP, R}^{P, D} (λ)] - Pr [WEE-ideal_{IP, R}^{E, P, D} (λ)]$ 是相对于以下博弈定义的。 $\underline{Game WEE-real_{IP, R}^{P_{alg}, D} (λ) :} tr \leftarrow ϵ pp \leftarrow IP . Setup (1^{λ}) (x, st_{P}) \leftarrow P_{alg} (pp) Run P_{alg}^{O_{real}} (st_{P}) b \leftarrow D (tr) Return b = 1 \underline{Game WEE-ideal_{IP, R}^{E, P_{alg}, D} (λ) :} tr \leftarrow ϵ pp \leftarrow IP . Setup (1^{λ}) (x, st_{P}) \leftarrow P_{alg} (pp) st_{E} \leftarrow (1^{λ}, pp, x) Run P_{alg}^{O_{ideal}} (st_{P}) w \leftarrow E (st_{E}, ⊥) b \leftarrow D (tr) Return (b = 1) \land (Acc (tr) ⟹ (x, w) \in R) \underline{Oracle O_{real} (τ = (a_{1}, c_{1}, ..., a_{i - 1}, c_{i - 1}), a_{i}) :} If τ \in tr then If i \leq r then c_{i} \leftarrow Ch_{i}; tr \leftarrow tr ∣∣ (τ, a_{i}, c_{i}); Return c_{i} Else if i = r + 1 then d \leftarrow IP . V (pp, x, (τ, a_{i})); tr \leftarrow (τ, a_{i}) If d = 1 then win \leftarrow true Return d Return ⊥ \underline{Oracle O_{ideal} (τ, a) :} If τ \in tr then (r, st_{E}) \leftarrow E (st_{E}, [(τ, a)]) tr \leftarrow tr ∣∣ (τ, a, r) Return r Return ⊥$

零知识

我们说一个知识论证是 零知识(zero knowledge) 的,如果验证者除了从有效 $w$ 存在这一事实所能学到的内容之外,也不从他们的交互中学到任何其他东西。更形式地说,

完美特殊诚实验证者零知识(Perfect Special Honest-Verifier Zero Knowledge)。 一个公开掷币的交互式论证 $(Setup, P, V)$ 具有 完美特殊诚实验证者零知识(PSHVZK),如果对于所有多项式时间可判定关系 $R$ 、所有 $(x, w) \in R$ ,以及所有非一致多项式时间敌手 $A_{1}, A_{2}$ ,都存在一个概率多项式时间模拟器(simulator) $S$ 使得 $= P r A_{1} (σ, x, tr) = 1 pp \leftarrow Setup (1^{λ}); (x, w, ρ) \leftarrow A_{2} (pp); t r \leftarrow ⟨ P (pp, x, w), V (pp, x, ρ)⟩ P r A_{1} (σ, x, tr) = 1 pp \leftarrow Setup (1^{λ}); (x, w, ρ) \leftarrow A_{2} (pp); t r \leftarrow S (pp, x, ρ)$ 其中 $ρ$ 是验证者的内部随机性。

在这个(常见的)零知识定义中,验证者被期望"诚实地"行动,并发送仅与其内部随机性相对应的挑战;他们不能基于证明者的消息自适应地响应证明者。我们使用这一定义的一种强化形式,它强制模拟器输出一个带有验证者算法发送给证明者的相同(由敌手提供的)挑战的副本。

协议

设 $ω \in F$ 是一个 $n = 2^{k}$ 次本原单位根(primitive root of unity),构成域 $D = (ω^{0}, ω^{1}, ..., ω^{n - 1})$ , $t (X) = X^{n} - 1$ 是该域上的消失多项式(vanishing polynomial)。设 $n_{g}, n_{a}, n_{e}$ 为正整数,满足 $n_{a}, n_{e} < n$ 且 $n_{g} \geq 4$ 。我们针对关系 $R = ⎩ ⎨ ⎧ ((g (X, C_{0}, ..., C_{n_{a} - 1}, a_{0} (X), ..., a_{n_{a} - 1} (X, C_{0}, ..., C_{n_{a} - 1}, a_{0} (X), ..., a_{n_{a} - 2} (X)))); (a_{0} (X), a_{1} (X, C_{0}, a_{0} (X)), ..., a_{n_{a} - 1} (X, C_{0}, ..., C_{n_{a} - 1}, a_{0} (X), ..., a_{n_{a} - 2} (X)))) : g (ω^{i}, \dots) = 0 \forall i \in [0, 2^{k}) ⎭ ⎬ ⎫$ 给出一个交互式论证 $Halo = (Setup, P, V)$ ,其中 $a_{0}, a_{1}, ..., a_{n_{a} - 1}$ 是关于 $X$ 度数为 $n - 1$ 的(多元)多项式, $g$ 关于任意不定元 $X, C_{0}, C_{1}, ...$ 的度数至多为 $n_{g} (n - 1)$ 。

$Setup (λ)$ 返回 $pp = (G, F, G \in G^{n}, U, W \in G)$ 。

对于所有 $i \in [0, n_{a})$ :

设 $p_{i}$ 为所有整数 $j$ (模 $n$ )的穷举集合,使得 $a_{i} (ω^{j} X, \dots)$ 作为一项出现在 $g (X, \dots)$ 中。
设 $q$ 是一个由互异整数集合构成的列表,包含 $p_{i}$ 以及集合 $q_{0} = {0}$ 。
当 $q_{j} = p_{i}$ 时设 $σ (i) = q_{j}$ 。

设 $n_{q} \leq n_{a}$ 表示 $q$ 的大小,并不失一般性地设 $n_{e}$ 表示每个 $p_{i}$ 的大小。

在以下协议中,我们将默认每个多项式 $a_{i} (X, \dots)$ 的定义方式使得:有 $n_{e} + 1$ 个盲化因子(blinding factor)由证明者新鲜采样,并各自作为 $a_{i} (X, \dots)$ 在域 $D$ 上的一个求值出现。在以下所有内容中,验证者的挑战不能为零或 $D$ 中的元素,此外对某些特定挑战还设置了额外的限制。

$P$ 和 $V$ 进行以下 $n_{a}$ 轮交互,在第 $j$ 轮(从 $0$ 开始)中

$P$ 设 $a_{j}^{'} (X) = a_{j} (X, c_{0}, c_{1}, ..., c_{j - 1}, a_{0} (X, \dots), ..., a_{j - 1} (X, \dots, c_{j - 1}))$
$P$ 发送一个隐藏承诺(hiding commitment) $A_{j} = ⟨ a^{'}, G ⟩ + [\cdot] W$ ,其中 $a^{'}$ 是一元多项式 $a_{j}^{'} (X)$ 的系数,而 $\cdot$ 是某个为简化叙述而省略的、随机且独立采样的盲化因子。(这种省略记号在本协议描述中通篇使用以简化叙述。)
$V$ 以挑战 $c_{j}$ 作出响应。

$P$ 设 $g^{'} (X) = g (X, c_{0}, c_{1}, ..., c_{n_{a} - 1}, \dots)$ 。
$P$ 发送一个承诺 $R = ⟨ r, G ⟩ + [\cdot] W$ ,其中 $r \in F^{n}$ 是一个随机采样的、度数为 $n - 1$ 的一元多项式 $r (X)$ 的系数。
$P$ 计算一元多项式 $h (X) = \frac{g ^{'} ( X )}{t ( X )}$ ,其度数为 $n_{g} (n - 1) - n$ 。
$P$ 计算至多 $n - 1$ 度的多项式 $h_{0} (X), h_{1} (X), ..., h_{n_{g} - 2} (X)$ 使得 $h (X) = i = 0 \sum n_{g} - 2 X^{ni} h_{i} (X)$ 。
$P$ 对所有 $i$ 发送承诺 $H_{i} = ⟨ h_{i}, G ⟩ + [\cdot] W$ ,其中 $h_{i}$ 表示 $h_{i} (X)$ 的系数向量。
$V$ 以挑战 $x$ 作出响应,并计算 $H^{'} = i = 0 \sum n_{g} - 2 [x^{ni}] H_{i}$ 。
$P$ 设 $h^{'} (X) = i = 0 \sum n_{g} - 2 x^{ni} h_{i} (X)$ 。
$P$ 发送 $r = r (x)$ ,并对所有 $i \in [0, n_{a})$ 发送 $a_{i}$ 使得对所有 $j \in [0, n_{e} - 1]$ 有 $(a_{i})_{j} = a_{i}^{'} (ω^{(p_{i})_{j}} x)$ 。
对所有 $i \in [0, n_{a})$ , $P$ 和 $V$ 设 $s_{i} (X)$ 为最低度数的一元多项式,其定义满足对所有 $j \in [0, n_{e} - 1)$ 有 $s_{i} (ω^{(p_{i})_{j}} x) = (a_{i})_{j}$ 。
$V$ 以挑战 $x_{1}, x_{2}$ 作出响应,并初始化 $Q_{0}, Q_{1}, ..., Q_{n_{q} - 1} = O$ 。

从 $i = 0$ 开始到 $n_{a} - 1$ , $V$ 设 $Q_{σ (i)} := [x_{1}] Q_{σ (i)} + A_{i}$ 。
$V$ 最后设 $Q_{0} := [x_{1}^{2}] Q_{0} + [x_{1}] H^{'} + R$ 。

$P$ 初始化 $q_{0} (X), q_{1} (X), ..., q_{n_{q} - 1} (X) = 0$ 。

从 $i = 0$ 开始到 $n_{a} - 1$ , $P$ 设 $q_{σ (i)} := x_{1} q_{σ (i)} + a^{'} (X)$ 。
$P$ 最后设 $q_{0} (X) := x_{1}^{2} q_{0} (X) + x_{1} h^{'} (X) + r (X)$ 。

$P$ 和 $V$ 初始化 $r_{0} (X), r_{1} (X), ..., r_{n_{q} - 1} (X) = 0$ 。

从 $i = 0$ 开始到 $n_{a} - 1$ , $P$ 和 $V$ 设 $r_{σ (i)} (X) := x_{1} r_{σ (i)} (X) + s_{i} (X)$ 。
最后 $P$ 和 $V$ 设 $r_{0} := x_{1}^{2} r_{0} + x_{1} h + r$ ,其中 $h$ 由 $V$ 使用 $P$ 提供的值 $r, a$ 计算为 $\frac{g ^{'} ( x )}{t ( x )}$ 。

$P$ 发送 $Q^{'} = ⟨ q^{'}, G ⟩ + [\cdot] W$ ,其中 $q^{'}$ 定义了多项式 $q^{'} (X) = i = 0 \sum n_{q} - 1 x_{2}^{i} \frac{q _{i} ( X ) - r _{i} ( X )}{j = 0 \prod n _{e} - 1 ( X - ω ^{(q_{i})_{j}} x )}$ 的系数。
$V$ 以挑战 $x_{3}$ 作出响应。
$P$ 发送 $u \in F^{n_{q}}$ 使得对所有 $i \in [0, n_{q})$ 有 $u_{i} = q_{i} (x_{3})$ 。
$V$ 以挑战 $x_{4}$ 作出响应。
$V$ 设 $P = Q^{'} + x_{4} i = 0 \sum n_{q} - 1 [x_{4}^{i}] Q_{i}$ 以及 $v =$ $i = 0 \sum n_{q} - 1 x_{2}^{i} \frac{u _{i} - r _{i} ( x _{3} )}{j = 0 \prod n _{e} - 1 ( x _{3} - ω ^{(q_{i})_{j}} x )} + x_{4} i = 0 \sum n_{q} - 1 x_{4} u_{i}$
$P$ 设 $p (X) = q^{'} (X) + [x_{4}] i = 0 \sum n_{q} - 1 x_{4}^{i} q_{i} (X)$ 。
$P$ 采样一个度数为 $n - 1$ 且在 $x_{3}$ 处有根的随机多项式 $s (X)$ ,并发送承诺 $S = ⟨ s, G ⟩ + [\cdot] W$ ,其中 $s$ 定义了 $s (X)$ 的系数。
$V$ 以挑战 $ξ, z$ 作出响应。
$V$ 设 $P^{'} = P - [v] G_{0} + [ξ] S$ 。
$P$ 设 $p^{'} (X) = p (X) - p (x_{3}) + ξ s (X)$ (其中 $p (x_{3})$ 应与验证者计算出的值 $v$ 相对应)。
将 $p^{'}$ 初始化为 $p^{'} (X)$ 的系数,并设 $G^{'} = G$ 以及 $b = (x_{3}^{0}, x_{3}^{1}, ..., x_{3}^{n - 1})$ 。 $P$ 和 $V$ 将进行以下 $k$ 轮交互,在第 $j$ 轮(从第 $j = 0$ 轮开始到第 $j = k - 1$ 轮结束)中:

$P$ 发送 $L_{j} = ⟨ p^{'}_{hi}, G^{'}_{lo} ⟩ + [z ⟨ p^{'}_{hi}, b_{lo} ⟩] U + [\cdot] W$ 和 $R_{j} = ⟨ p^{'}_{lo}, G^{'}_{hi} ⟩ + [z ⟨ p^{'}_{lo}, b_{hi} ⟩] U + [\cdot] W$ 。
$V$ 以挑战 $u_{j}$ 作出响应,该挑战的选取使得 $1 + u_{k - 1 - j} x_{3}^{2^{j}}$ 非零。
$P$ 和 $V$ 设 $G^{'} := G^{'}_{lo} + u_{j} G^{'}_{hi}$ 以及 $b := b_{lo} + u_{j} b_{hi}$ 。
$P$ 设 $p^{'} := p^{'}_{lo} + u_{j}^{- 1} p^{'}_{hi}$ 。

$P$ 发送 $c = p^{'}_{0}$ 以及由被省略的盲化因子计算出的合成盲化因子(synthetic blinding factor) $f$ 。
$V$ 仅当 $\sum_{j = 0}^{k - 1} [u_{j}^{- 1}] L_{j} + P^{'} + \sum_{j = 0}^{k - 1} [u_{j}] R_{j} = [c] G^{'}_{0} + [c b_{0} z] U + [f] W$ 时接受。

零知识与完备性

我们声称该协议是 完美完备的(perfectly complete)。这可以通过对协议的检视来验证;给定一个有效的证据 $a_{i} (X, \dots) \forall i$ ,证明者以概率 $1$ 成功说服验证者。

我们声称该协议是 完美特殊诚实验证者零知识(perfect special honest-verifier zero knowledge) 的。我们通过证明存在一个模拟器 $S$ 来做到这一点,该模拟器能够产生一个被接受的副本,其分布与一个有效证明者在相同公开掷币下与验证者交互的分布相同。该模拟器将如同一个诚实的证明者那样行动,但有以下例外:

在协议的第 $1$ 步中, $S$ 选择随机的度数为 $n - 1$ 的多项式(关于 $X$ ) $a_{i} (X, \dots) \forall i$ 。
在协议的第 $5$ 步中, $S$ 选择随机的 $n - 1$ 度多项式 $h_{0} (X), h_{1} (X), ..., h_{n_{g} - 2} (X)$ 。
在协议的第 $14$ 步中, $S$ 选择一个随机的 $n - 1$ 度多项式 $q^{'} (X)$ 。
在协议的第 $20$ 步中, $S$ 利用其对验证者所选 $ξ$ 的预知,生成一个度数为 $n - 1$ 的多项式 $s (X)$ ,其唯一约束条件是 $p (X) - v + ξ s (X)$ 在 $x_{3}$ 处有根。

首先,让我们考虑为什么这个模拟器总能成功产生一个 被接受的 副本。 $S$ 缺乏一个有效的证据,并且每当诚实证明者需要有效证据的知识时,它都只是简单地对随机多项式做承诺。验证者对副本中的标量值不设任何条件。 $S$ 只须保证协议第 $26$ 步中的检查成功。它通过利用其对挑战 $ξ$ 的知识,生成一个与 $p^{'} (X)$ 相互作用的多项式,以确保后者在 $x_{3}$ 处有根来做到这一点。因此,由于完美完备性,该副本将总是被接受。

为了理解为什么 $S$ 产生的副本与诚实证明者的副本分布完全相同,我们将逐一考察副本的每个部分并比较其分布。首先,注意 $S$ (正如诚实证明者那样)对副本中的每个群元素都使用一个新鲜随机的盲化因子,因此我们只需考虑副本中的 标量(scalars)。 $S$ 的行为与证明者完全相同,除了上述提到的几种情况,因此我们将逐一分析每种情况:

$S$ 与诚实证明者都揭示每个多项式 $a_{i} (X, \dots)$ 的 $n_{e}$ 个打开值,并在第 $16$ 步中至多揭示每个 $a_{i} (X, \dots)$ 的一个额外打开值。然而,诚实证明者用 $n_{e} + 1$ 个在域 $D$ 上的随机求值来盲化他们的多项式 $a_{i} (X, \dots)$ (关于 $X$ )。因此, $a_{i} (X, \dots)$ 在挑战 $x$ (协议禁止其为 $0$ 或位于域 $D$ 中)处的打开值,在 $S$ 与诚实证明者之间的分布完全相同。
$S$ 和诚实证明者都不揭示 $h (x)$ ,因为它由验证者计算。然而,诚实证明者可能会揭示 $h^{'} (x_{3})$ ——它与 $h (X)$ 有一种非平凡的关系——若不是因为诚实证明者还在第 $3$ 步中对一个随机的度数为 $n - 1$ 的多项式 $r (X)$ 做了承诺,产生一个承诺 $R$ ,从而确保在第 $12$ 步当证明者设 $q_{0} (X) := x_{1}^{2} q_{0} (X) + x_{1} h^{'} (X) + r (X)$ 时 $q_{0} (x_{3})$ 的分布是均匀随机的。因此, $h^{'} (x_{3})$ 永远不会被诚实证明者也不会被 $S$ 揭示。
$q^{'} (x_{3})$ 的期望值由验证者计算(在第 $18$ 步中),因此模拟器对 $q^{'} (X)$ 的实际选择是无关紧要的。
$p (X) - v + ξ s (X)$ 被约束为在 $x_{3}$ 处有根,但除此之外对 $s (X)$ 不设其他条件,因此无论 $s (X)$ 是否在 $x_{3}$ 处有根,度数为 $n - 1$ 的多项式 $p (X) - v + ξ s (X)$ 的分布都是均匀随机的。因此,第 $25$ 步中产生的 $c$ 的分布在 $S$ 与诚实证明者之间完全相同。第 $25$ 步中也揭示的合成盲化因子 $f$ 是证明者其他盲化因子的一个平凡函数,因此在 $S$ 与诚实证明者之间分布完全相同。

注:

在我们协议的较早版本中,作为多点打开论证(multipoint opening argument)的一部分,证明者会在 $x$ 处打开每个单独的承诺 $H_{0}, H_{1}, ...$ ,而验证者会确认这些打开值的一个线性组合(以 $x^{n}$ 的幂为系数)与 $h (x)$ 的期望值相符。这样做是因为它在递归证明中更高效。然而,我们当时不清楚这些承诺 $H_{0}, H_{1}, ...$ 的打开值的期望分布是什么,因此证明该论证是零知识的很困难。于是我们改变了论证,使得 验证者 计算这些承诺的一个线性组合,而这个线性组合在 $x$ 处被打开。这避免了泄露 $h_{i} (x)$ 。
如前所述,在第 $3$ 步中证明者对一个随机多项式做承诺,作为一种确保 $h^{'} (x_{3})$ 不会在多重打开(multiopen)论证中被揭示的方法。这样做是因为不清楚 $h^{'} (x_{3})$ 的分布会是什么。
从技术上讲,我们也可以用一个模拟器来证明零知识,该模拟器利用其对挑战 $x$ 的预知来承诺一个 $h (X)$ ,使其在 $x$ 处与它将被期望的值相符。这将省去协议中对随机多项式 $s (X)$ 的需求。不过这可能会使协议其余部分的零知识分析变得有些棘手,所以我们没有走这条路。
群元素盲化因子在第 $23$ 步(此处多项式被完全随机化)之后 在技术上 不再必要。然而,在实践中,确保协议中的每个群元素都被随机盲化对我们来说更简单,这使得涉及无穷远点(point at infinity)的边界情况更难出现。
至关重要的是,验证者不能挑战证明者在 $D$ 中的点处打开多项式,否则诚实证明者的副本将被迫包含可能是证明者证据一部分的内容。因此我们将挑战空间限制为包含域中除 $D$ 之外的所有元素,并且为简单起见,我们还禁止挑战为 $0$ 。

证据扩展模拟

设 $Halo = Halo [G]$ 为上述针对关系 $R$ 、群 $G$ (其标量域为 $F$ )的交互式论证。我们总能构造一个提取器 $E$ ,使得对于任何对其预言机做至多 $q$ 次查询的非一致代数证明者 $P_{alg}$ ,都存在一个非一致敌手 $H$ ,具有这样的性质:对于任何计算上无界的区分器 $D$

$Adv_{Halo, R}^{sr-wee} (P_{alg}, D, E, λ) \leq q ϵ + Adv_{G, n + 2}^{dl-rel} (H, λ)$

其中 $ϵ \leq \frac{n _{g} \cdot ( n - 1 )}{∣ Ch ∣}$ 。

证明。 我们将通过援引 [GT20] 的定理 1 来证明这一点。首先,我们注意到所有轮次的挑战空间是相同的,即 $\forall i Ch = Ch_{i}$ 。定理 1 要求我们定义:

对所有部分副本 $tr^{'} = (pp, x, [a_{0}], c_{0}, \dots, [a_{i}])$ 定义 $BadCh (tr^{'}) \in Ch$ 使得 $∣ BadCh (tr^{'}) ∣/∣ Ch ∣ \leq ϵ$ 。
一个提取器函数 $e$ ,它以一个被接受的扩展副本 $tr$ 作为输入,并返回一个有效证据或失败。
一个返回概率的函数 $p_{fail} (Halo, P_{alg}, e, R)$ 。

我们说一个被接受的扩展副本 $tr$ 包含"坏挑战(bad challenges)",当且仅当存在一个部分扩展副本 $tr^{'}$ 、一个挑战 $c_{i} \in BadCh (tr^{'})$ ,以及某个证明者消息和挑战序列 $([a_{i + 1}], c_{i + 1}, \dots [a_{j}])$ 使得 $tr = tr^{'} ∣∣ (c_{i}, [a_{i + 1}], c_{i + 1}, \dots [a_{j}])$ 。

定理 1 要求:当给定一个不包含"坏挑战"的被接受扩展副本 $tr$ 时, $e$ 返回该副本的一个有效证据,除非概率上界为 $p_{fail} (Halo, P_{alg}, e, R)$ 的情形发生。

我们的策略如下:我们将定义 $e$ ,相对于一个参与 $dl-rel_{G, n + 2}$ 博弈的敌手 $H$ 建立 $p_{fail}$ 的一个上界,将这些代入定理 1,然后逐步走过协议以确定 $BadCh (tr^{'})$ 大小的上界。敌手 $H$ 按如下方式参与 $dl-rel_{G, n + 2}$ 博弈:给定输入 $U, W \in G, G \in G^{n}$ ,敌手 $H$ 向 $P_{alg}$ 模拟博弈 $sr-wee_{Halo, R}$ ,使用来自 $dl-rel_{G, n + 2}$ 博弈的输入作为公共参数。如果 $P_{alg}$ 设法产生一个被接受的扩展副本 $tr$ , $H$ 在 $tr$ 上调用一个函数 $h$ 并返回其输出。我们将以这样的方式定义 $h$ :对于一个不包含"坏挑战"的被接受扩展副本 $tr$ ,只要 $h (tr)$ 不返回一个非平凡的离散对数关系, $e (tr)$ 就总是返回一个有效证据。这意味着概率 $p_{fail} (Halo, P_{alg}, e, R)$ 不大于 $Adv_{G, n + 2}^{dl-rel} (H, λ)$ ,从而确立了我们的声称。

有用的替换

我们将执行一些替换以辅助叙述。首先,让我们定义多项式

$κ (X) = j = 0 \prod k - 1 (1 + u_{k - 1 - j} X^{2^{j}})$

这样我们可以写 $b_{0} = κ (x_{3})$ 。 $κ (X)$ 的系数向量 $s$ 定义为

$s_{i} = j = 0 \prod k - 1 u_{k - 1 - j}^{f (i, j)}$

其中 $f (i, j)$ 当 $i$ 的第 $j$ 个比特被置位时返回 $1$ ,否则返回 $0$ 。我们也可以写 $G^{'}_{0} = ⟨ s, G ⟩$ 。

函数 $h$ 的描述

回忆一个被接受的副本 $tr$ 满足

$i = 0 \sum k - 1 [u_{j}^{- 1}] {L_{j}} + {P^{'}} + i = 0 \sum k - 1 [u_{j}] {R_{j}} = [c] G^{'}_{0} + [cz b_{0}] U + [f] W$

通过检视群元素关于 $G, U, W$ 的表示(回忆 $P_{alg}$ 是代数的,因此 $H$ 拥有它们),我们得到 $n$ 个等式

$i = 0 \sum k - 1 u_{j}^{- 1} {L_{j}}_{i}^{G} + {P^{'}}_{i}^{G} + i = 0 \sum k - 1 u_{j} {R_{j}}_{i}^{G} = c s_{i} \forall i \in [0, n)$

以及这些等式

$i = 0 \sum k - 1 u_{j}^{- 1} {L_{j}}^{U} + {P^{'}}^{U} + i = 0 \sum k - 1 u_{j} {R_{j}}^{U} = cz κ (x_{3})$

$i = 0 \sum k - 1 u_{j}^{- 1} {L_{j}}^{W} + {P^{'}}^{W} + i = 0 \sum k - 1 u_{j} {R_{j}}^{W} = f$

我们定义线性时间函数 $h$ ,它返回如下表达式的表示

$i = 0 \sum n - 1 + + [\sum_{i = 0}^{k - 1} u_{j}^{- 1} {L_{j}}_{i}^{G} + {P^{'}}_{i}^{G} + \sum_{i = 0}^{k - 1} u_{j} {R_{j}}_{i}^{G} - c s_{i}] [\sum_{i = 0}^{k - 1} u_{j}^{- 1} {L_{j}}^{U} + {P^{'}}^{U} + \sum_{i = 0}^{k - 1} u_{j} {R_{j}}^{U} - cz κ (x_{3})] [\sum_{i = 0}^{k - 1} u_{j}^{- 1} {L_{j}}^{W} + {P^{'}}^{W} + \sum_{i = 0}^{k - 1} u_{j} {R_{j}}^{W} - f] G_{i} U W$

它总是一个离散对数关系。如果上述任何等式不被满足,那么这个离散对数关系就是非平凡的。这就是 $H$ 所调用的函数。

提取器函数 $e$

提取器函数 $e$ 简单地从表示 ${A_{i}}$ 中返回 $a_{i} (X)$ , $i \in [0, n_{a})$ 。由于我们将对每一轮中坏挑战空间施加限制,只要敌手的函数 $h$ 返回的离散对数关系是平凡的,我们就能保证得到这样的多项式: $g (X, C_{0}, C_{1}, \dots, a_{0} (X), a_{1} (X), \dots)$ 在 $D$ 上消失。这平凡地给出:提取器函数 $e$ 成功的概率上界为所要求的 $p_{fail}$ 。

定义 $BadCh (tr^{'})$

回忆前面所述,以下 $n$ 个等式成立:

$i = 0 \sum k - 1 u_{j}^{- 1} {L_{j}}_{i}^{G} + {P^{'}}_{i}^{G} + i = 0 \sum k - 1 u_{j} {R_{j}}_{i}^{G} = c s_{i} \forall i \in [0, n)$

以及等式

$i = 0 \sum k - 1 u_{j}^{- 1} {L_{j}}^{U} + {P^{'}}^{U} + i = 0 \sum k - 1 u_{j} {R_{j}}^{U} = cz κ (x_{3})$

为方便起见,让我们引入以下记号

$M_{i}^{G} (m) M_{U} (m) = \sum_{i = 0}^{m - 1} u_{j}^{- 1} {L_{j}}_{i}^{G} + {P^{'}}_{i}^{G} + \sum_{i = 0}^{m - 1} u_{j} {R_{j}}_{i}^{G} = \sum_{i = 0}^{m - 1} u_{j}^{- 1} {L_{j}}^{U} + {P^{'}}^{U} + \sum_{i = 0}^{m - 1} u_{j} {R_{j}}^{U}$

这样我们可以把上面的式子(在对 $κ (x_{3})$ 展开后)重写为

$M_{i}^{G} (k) = c s_{i} \forall i \in [0, n)$

$M_{U} (k) = cz j = 0 \prod k - 1 (1 + u_{k - 1 - j} x_{3}^{2^{j}})$

我们可以通过将第一个等式的每个实例的两边都乘以 $s_{i}^{- 1}$ (因为 $s_{i}$ 永不为零)并代入第二个等式中的 $c$ ,来合并这些方程,得到以下 $n$ 个等式:

$M_{U} (k) = M_{i}^{G} (k) \cdot s_{i}^{- 1} z j = 0 \prod k - 1 (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \forall i \in [0, n)$

引理 1。 如果 $M_{U} (k) = M_{i}^{G} (k) \cdot s_{i}^{- 1} z \prod_{j = 0}^{k - 1} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \forall i \in [0, n)$ ,那么对于所有不包含坏挑战的副本,可推出 ${P^{'}}^{U} = z i = 0 \sum 2^{k} - 1 x_{3}^{i} {P^{'}}_{i}^{G}$ 。

证明。 引入又一个抽象会很有用,它首先定义为 $Z_{k} (m, i) = M_{i}^{G} (m)$ 然后对所有满足 $0 < r \leq k$ 的整数 $r$ 递归定义 $Z_{k - r} (m, i) = Z_{k - r + 1} (m, i) + x_{3}^{2^{k - r}} Z_{k - r + 1} (m, i + 2^{k - r})$ 这允许我们把上面的等式重写为 $M_{U} (k) = Z_{k} (k, i) \cdot s_{i}^{- 1} z j = 0 \prod k - 1 (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \forall i \in [0, n)$

现在我们将证明:对于所有满足 $0 < r \leq k$ 的整数 $r$ ,每当以下式子对 $r$ 成立时 $M_{U} (r) = Z_{r} (r, i) \cdot s_{i}^{- 1} z j = 0 \prod r - 1 (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \forall i \in [0, 2^{r})$ 同样的式子也对以下成立 $M_{U} (r - 1) = Z_{r - 1} (r - 1, i) \cdot s_{i}^{- 1} z j = 0 \prod r - 2 (1 + u_{k - 2 - j} x_{3}^{2^{j}}) \forall i \in [0, 2^{r - 1})$

对于所有满足 $0 < r \leq k$ 的整数 $r$ ,根据 $s$ 的定义我们有 $s_{i + 2^{r - 1}} = u_{r - 1} s_{i} \forall i \in [0, 2^{r - 1})$ 。由于 $s$ 中没有任何值、也没有任何挑战 $u_{r}$ 为零,这给我们 $s_{i + 2^{r - 1}}^{- 1} = s_{i}^{- 1} u_{r - 1}^{- 1} \forall i \in [0, 2^{r - 1})$ 。我们可以用这一点把一半的等式与另一半关联起来,如下: $M_{U} (r) = Z_{r} (r, i) \cdot s_{i}^{- 1} z \prod_{j = 0}^{r - 1} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) = Z_{r} (r, i + 2^{r - 1}) \cdot s_{i}^{- 1} u_{r - 1}^{- 1} z \prod_{j = 0}^{r - 1} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \forall i \in [0, 2^{r - 1})$

注意 $Z_{r} (r, i)$ 可以对所有 $i \in [0, 2^{r})$ 重写为 $u_{r - 1}^{- 1} {L_{r - 1}}_{i}^{G} + Z_{r} (r - 1, i) + u_{r - 1} {R_{r - 1}}_{i}^{G}$ 。因此我们可以把上式重写为

$M_{U} (r) = (u_{r - 1}^{- 1} {L_{r - 1}}_{i}^{G} + Z_{r} (r - 1, i) + u_{r - 1} {R_{r - 1}}_{i}^{G}) \cdot s_{i}^{- 1} z \prod_{j = 0}^{r - 1} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) = (u_{r - 1}^{- 1} {L_{r - 1}}_{i + 2^{r - 1}}^{G} + Z_{r} (r - 1, i + 2^{r - 1}) + u_{r - 1} {R_{r - 1}}_{i + 2^{r - 1}}^{G}) \cdot s_{i}^{- 1} u_{r - 1}^{- 1} z \prod_{j = 0}^{r - 1} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \forall i \in [0, 2^{r - 1})$

现在让我们把这些等式中的 $u_{r - 1}$ 替换为形式不定元 $X$ 来重写它们。

$X^{- 1} {L_{r - 1}}^{U} + M_{U} (r - 1) + X {R_{r - 1}}^{U} = (X^{- 1} {L_{r - 1}}_{i}^{G} + Z_{r} (r - 1, i) + X {R_{r - 1}}_{i}^{G}) \cdot s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) (1 + x_{3}^{2^{r - 1}} X) = (X^{- 1} {L_{r - 1}}_{i + 2^{r - 1}}^{G} + Z_{r} (r - 1, i + 2^{r - 1}) + X {R_{r - 1}}_{i + 2^{r - 1}}^{G}) \cdot s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) (X^{- 1} + x_{3}^{2^{r - 1}}) \forall i \in [0, 2^{r - 1})$

现在让我们把所有式子按 $X^{2}$ 重新缩放以消除负指数。

$X {L_{r - 1}}^{U} + X^{2} M_{U} (r - 1) + X^{3} {R_{r - 1}}^{U} = (X^{- 1} {L_{r - 1}}_{i}^{G} + Z_{r} (r - 1, i) + X {R_{r - 1}}_{i}^{G}) \cdot s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) (X^{2} + x_{3}^{2^{r - 1}} X^{3}) = (X^{- 1} {L_{r - 1}}_{i + 2^{r - 1}}^{G} + Z_{r} (r - 1, i + 2^{r - 1}) + X {R_{r - 1}}_{i + 2^{r - 1}}^{G}) \cdot s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) (X + x_{3}^{2^{r - 1}} X^{2}) \forall i \in [0, 2^{r - 1})$

这给了我们 $2^{r - 1}$ 个三元组,每组是关于 $X$ 的最高度数为 $4$ 的多项式,尽管它们的系数在 $u_{r - 1}$ 选定之前就已确定,但它们在 $u_{r - 1}$ 处取值相等。根据 Schwartz-Zippel 引理,这其中两个多项式会在 $u_{r - 1}$ 处取值相等却又互异的概率为 $\frac{4}{∣ Ch ∣}$ ,因此由联合界(union bound),这三个多项式取值相等却又其中任意一个与另一个不同的概率为 $\frac{8}{∣ Ch ∣}$ 。再次由联合界, $2^{r - 1}$ 个三元组中任意一个含有多个互异多项式的概率为 $\frac{2 ^{r - 1} \cdot 8}{∣ Ch ∣}$ 。通过相应地限制 $u_{r - 1}$ 的挑战空间,我们对整数 $0 < r \leq k$ 得到 $∣ BadCh (tr^{'} ∣_{u_{r}}) ∣/∣ Ch ∣ \leq \frac{2 ^{r - 1} \cdot 8}{∣ Ch ∣}$ ,从而 $∣ BadCh (tr^{'} ∣_{u_{k}}) ∣/∣ Ch ∣ \leq \frac{4 n}{∣ Ch ∣} \leq ϵ$ 。

现在我们可以得出多项式相等的结论,从而得出系数相等。首先考虑常数项的系数,这给我们 $2^{r - 1}$ 个等式 $0 = 0 = s_{i}^{- 1} z (j = 0 \prod r - 2 (1 + u_{k - 1 - j} x_{3}^{2^{j}})) \cdot {L_{r - 1}}_{i + 2^{r - 1}}^{G} \forall i \in [0, 2^{r - 1})$

$s$ 中没有任何值为零, $z$ 永远不会被选为 $0$ ,且每个 $u_{j}$ 的选取使得 $1 + u_{k - 1 - j} x_{3}^{2^{j}}$ 非零,因此我们可以得出 $0 = {L_{r - 1}}_{i + 2^{r - 1}}^{G} \forall i \in [0, 2^{r - 1})$

对于这些等式中 $X^{4}$ 项的系数,可以遵循一个相同的过程来确立 $0 = {R_{r - 1}}_{i}^{G} \forall i \in [0, 2^{r - 1})$ ,这取决于 $x_{3}$ 非零(它总是非零)。把这些代入我们的等式得到更简单的式子

$X {L_{r - 1}}^{U} + X^{2} M_{U} (r - 1) + X^{3} {R_{r - 1}}^{U} = (X^{- 1} {L_{r - 1}}_{i}^{G} + Z_{r} (r - 1, i)) \cdot s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) (X^{2} + x_{3}^{2^{r - 1}} X^{3}) = (Z_{r} (r - 1, i + 2^{r - 1}) + X {R_{r - 1}}_{i + 2^{r - 1}}^{G}) \cdot s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) (X + x_{3}^{2^{r - 1}} X^{2}) \forall i \in [0, 2^{r - 1})$

现在我们将考虑 $X$ 中的系数,它们给出等式

${L_{r - 1}}^{U} = s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \cdot {L_{r - 1}}_{i}^{G} = s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \cdot Z_{r} (r - 1, i + 2^{r - 1}) \forall i \in [0, 2^{r - 1})$

由与之前类似的推理,它给出等式 ${L_{r - 1}}_{i}^{G} = Z_{r} (r - 1, i + 2^{r - 1}) \forall i \in [0, 2^{r - 1})$

最后我们将考虑 $X^{2}$ 中的系数,它们给出等式

$M_{U} (r - 1) = s_{i}^{- 1} z \prod_{j = 0}^{r - 2} (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \cdot (Z_{r} (r - 1, i) + {L_{r - 1}}_{i}^{G} x_{3}^{2^{r - 1}}) \forall i \in [0, 2^{r - 1})$

它通过代入给我们 $\forall i \in [0, 2^{r - 1})$ $M_{U} (r - 1) = s_{i}^{- 1} z j = 0 \prod r - 2 (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \cdot (Z_{r} (r - 1, i) + Z_{r} (r - 1, i + 2^{r - 1}) x_{3}^{2^{r - 1}})$

注意到根据 $Z_{r - 1} (m, i)$ 的定义,我们可以把它重写为

$M_{U} (r - 1) = Z_{r - 1} (r - 1, i) \cdot s_{i}^{- 1} z j = 0 \prod r - 2 (1 + u_{k - 1 - j} x_{3}^{2^{j}}) \forall i \in [0, 2^{r - 1})$

这正是我们着手要证明的形式。

我们现在从已知成立的 $r = k$ 情形出发通过归纳法进行,直到达到 $r = 0$ ,这给我们 $M_{U} (0) = Z_{0} (0, 0) \cdot s_{0}^{- 1} z$

而因为 $M_{U} (0) = {P^{'}}^{U}$ 且 $Z_{0} (0, 0) = \sum_{i = 0}^{2^{k} - 1} x_{3}^{i} {P^{'}}_{i}^{G}$ ,我们得到 ${P^{'}}^{U} = z \sum_{i = 0}^{2^{k} - 1} x_{3}^{i} {P^{'}}_{i}^{G}$ ,这就完成了证明。

在确立了 ${P^{'}}^{U} = z \sum_{i = 0}^{2^{k} - 1} x_{3}^{i} {P^{'}}_{i}^{G}$ 之后,并鉴于 $x_{3}$ 和 ${P^{'}}_{i}^{G}$ 在 $z$ 选定之前就已固定,我们有:至多存在一个 $z \in Ch$ 的值(非零)使得 ${P^{'}}^{U} = z \sum_{i = 0}^{2^{k} - 1} x_{3}^{i} {P^{'}}_{i}^{G}$ 却又 ${P^{'}}^{U} \neq = 0$ 。通过相应地限制 $∣ BadCh (tr^{'} ∣_{z}) ∣/∣ Ch ∣ \leq \frac{1}{∣ Ch ∣} \leq ϵ$ ,我们得到 ${P^{'}}^{U} = 0$ ,从而由 ${P^{'}}^{G}$ 定义的多项式在 $x_{3}$ 处有根。

根据构造 $P^{'} = P - [v] G_{0} + [ξ] S$ ,这给我们由 ${P + [ξ] S}^{G}$ 定义的多项式在点 $x_{3}$ 处求值为 $v$ 。我们有 $v, P, S$ 在 $ξ$ 选定之前就已固定,因此要么由 ${S}^{G}$ 定义的多项式在 $x_{3}$ 处有根(这蕴含由 ${P}^{G}$ 定义的多项式在点 $x_{3}$ 处求值为 $v$ ),要么 $ξ$ 是 $Ch$ 中使得 ${P + [ξ] S}^{G}$ 在点 $x_{3}$ 处求值为 $v$ 、而 ${P}^{G}$ 本身却并非如此的唯一解。我们通过相应地限制 $∣ BadCh (tr^{'} ∣_{ξ}) ∣/∣ Ch ∣ \leq \frac{1}{∣ Ch ∣} \leq ϵ$ 来避免后一种情况,从而可以得出由 ${P}^{G}$ 定义的多项式在 $x_{3}$ 处求值为 $v$ 。

剩余的工作严格地处理证明者先前发送的群元素的表示及其与 $P$ 的关系,以及协议每一轮中所选的挑战。我们首先通过用 $p (X)$ 表示由 ${P}^{G}$ 定义的多项式来简化处理,因为这个 $p (X)$ 恰好对应于协议本身中同名的多项式。我们将对其他群元素(及其对应的多项式)做类似的替换以辅助叙述,因为这个证明的剩余部分主要是繁琐地应用 Schwartz-Zippel 引理来对协议中剩余每个挑战的坏挑战空间大小取上界。

回忆 $P = Q^{'} + x_{4} i = 0 \sum n_{q} - 1 [x_{4}^{i}] Q_{i}$ ,因此通过代入我们有 $p (X) = q^{'} (X) + x_{4} i = 0 \sum n_{q} - 1 x_{4}^{i} q_{i} (X)$ 。还回忆

$v = i = 0 \sum n_{q} - 1 x_{2}^{i} \frac{u _{i} - r _{i} ( x _{3} )}{j = 0 \prod n _{e} - 1 ( x _{3} - ω ^{(q_{i})_{j}} x )} + x_{4} i = 0 \sum n_{q} - 1 x_{4} u_{i}$

我们已经确立了 $p (x_{3}) = v$ 。注意上述关于 $v$ 和 $P$ 的表达式中的系数在 $x_{4} \in Ch$ 选定之前就已固定。由 Schwartz-Zippel 引理我们有:至多存在 $n_{q} + 1$ 个可能的 $x_{4}$ 选择,使得这些表达式被满足却又对某个 $i$ 有 $q_{i} (x_{3}) \neq = u_{i}$ ,或

$q^{'} (x_{3}) \neq = i = 0 \sum n_{q} - 1 x_{2}^{i} \frac{u _{i} - r _{i} ( x _{3} )}{j = 0 \prod n _{e} - 1 ( x _{3} - ω ^{(q_{i})_{j}} x )}$

通过限制 $∣ BadCh (tr^{'} ∣_{x_{4}}) ∣/∣ Ch ∣ \leq \frac{n _{q} + 1}{∣ Ch ∣} \leq ϵ$ ,我们可以得出上述所有不等式都不成立。现在我们可以对所有 $i$ 用 $q_{i} (x_{3})$ 替换 $u_{i}$ 以得到

$q^{'} (x_{3}) = i = 0 \sum n_{q} - 1 x_{2}^{i} \frac{q _{i} ( x _{3} ) - r _{i} ( x _{3} )}{j = 0 \prod n _{e} - 1 ( x _{3} - ω ^{(q_{i})_{j}} x )}$

假设 $q^{'} (X)$ (它是由 ${Q^{'}}^{G}$ 定义的多项式,度数至多为 $n - 1$ )不具有如下形式

$i = 0 \sum n_{q} - 1 x_{2}^{i} \frac{q _{i} ( X ) - r _{i} ( X )}{j = 0 \prod n _{e} - 1 ( X - ω ^{(q_{i})_{j}} x )}$

然而正如我们上面所确立的, $q^{'} (X)$ 在 $x_{3}$ 处与此表达式取值相符。由 Schwartz-Zippel 引理,这至多只能对 $n - 1$ 个 $x_{3} \in Ch$ 的选择发生,因此通过限制 $∣ BadCh (tr^{'} ∣_{x_{3}}) ∣/∣ Ch ∣ \leq \frac{n - 1}{∣ Ch ∣} \leq ϵ$ ,我们得到

$q^{'} (X) = i = 0 \sum n_{q} - 1 x_{2}^{i} \frac{q _{i} ( X ) - r _{i} ( X )}{j = 0 \prod n _{e} - 1 ( X - ω ^{(q_{i})_{j}} x )}$

接下来我们将通过再次相对于 $x_{2}$ 应用 Schwartz-Zippel 引理,来提取这个关于 $x_{2}$ 的多项式的系数(它们本身是关于形式不定元 $X$ 的多项式);同样,这导致限制 $∣ BadCh (tr^{'} ∣_{x_{2}}) ∣/∣ Ch ∣ \leq \frac{n _{q}}{∣ Ch ∣} \leq ϵ$ ,并且我们对所有 $i \in [0, n_{q} - 1)$ 得到以下度数至多为 $n - 1$ 的多项式

$\frac{q _{i} ( X ) - r _{i} ( X )}{j = 0 \prod n _{e} - 1 ( X - ω ^{(q_{i})_{j}} x )}$

在确立了这些各自是度数至多为 $n - 1$ 的非有理多项式之后,我们便可以说(由因式定理,factor theorem):对于每个 $i \in [0, n_{q} - 1]$ 和 $j \in [0, n_{e} - 1]$ , $q_{i} (X) - r_{i} (X)$ 在 $ω^{(q_{i})_{j}} x$ 处有根。注意,我们可以把每个 $q_{i} (X)$ 解释为一个二元多项式在点 $x_{1}$ 处的限制,该二元多项式关于 $x_{1}$ 的度数至多为 $n_{a} + 1$ ,其系数由各个多项式 $a_{i}^{'} (X)$ (来自表示 ${A_{i}^{'}}^{G}$ )以及 $h^{'} (X)$ (来自表示 ${H_{i}^{'}}^{G}$ )和 $r (X)$ (来自表示 ${R}^{G}$ )构成。通过类似地应用 Schwartz-Zippel 引理并以 $∣ BadCh (tr^{'} ∣_{x_{1}}) ∣/∣ Ch ∣ \leq \frac{n _{a} + 1}{∣ Ch ∣} \leq ϵ$ 限制挑战空间,我们(由协议第 12、13 步中每个 $q_{i}^{'} (X)$ 和 $r_{i} (X)$ 的构造)得到:证明者在第 9 步声称的 $r$ 值等于 $r (x)$ ;验证者在第 13 步计算的值 $h$ 等于 $h^{'} (x)$ ;并且对所有 $i \in [0, n_{q} - 1]$ ,证明者声称的值 $(a_{i})_{j} = a_{i}^{'} (ω^{(p_{i})_{j}} x)$ 对所有 $j \in [0, n_{e} - 1]$ 成立。

由第 7 步中 $h^{'} (X)$ (来自表示 ${H^{'}}^{G}$ )的构造,我们知道 $h^{'} (x) = h (x)$ ,其中我们用 $h (X)$ 指代度数至多为 $(n_{g} - 1) \cdot (n - 1)$ 的多项式,其系数对应于每个 ${H_{i}}^{G}$ 拼接后的表示。如前所述,假设 $h (X)$ 不具有形式 $g^{'} (X) / t (X)$ 。那么因为 $h (X)$ 在 $x$ 选定之前就已确定,由 Schwartz-Zippel 引理我们知道:如果这两个多项式不相等,它将至多在 $(n_{g} - 1) \cdot (n - 1)$ 个点处与 $g^{'} (X) / t (X)$ 相符。通过再次限制 $∣ BadCh (tr^{'} ∣_{x}) ∣/∣ Ch ∣ \leq \frac{( n _{g} - 1 ) \cdot ( n - 1 )}{∣ Ch ∣} \leq ϵ$ ,我们得到 $h (X) = g^{'} (X) / t (X)$ ,并且因为 $h (X)$ 是一个非有理多项式,由因式定理我们得到 $g^{'} (X)$ 在域 $D$ 上消失。

我们现在有 $g^{'} (X)$ 在 $D$ 上消失,但希望证明 $g (X, C_{0}, C_{1}, \dots)$ 在 $D$ 上的所有点处都消失,以完成证明。这只涉及对每个挑战重复应用同一技术;由于多项式 $g (\dots)$ 按定义关于任意不定元的度数至多为 $n_{g} \cdot (n - 1)$ ,并且因为每个多项式 $a_{i} (X, C_{0}, C_{1}, ..., C_{i - 1}, \dots)$ 在具体挑战 $c_{i}$ 选定之前就已确定,通过类似地限制 $∣ BadCh (tr^{'} ∣_{c_{i}}) ∣/∣ Ch ∣ \leq \frac{n _{g} \cdot ( n - 1 )}{∣ Ch ∣} \leq ϵ$ ,我们确保 $g (X, C_{0}, C_{1}, \dots)$ 在 $D$ 上消失,从而完成证明。

halo2 中文手册 (The halo2 Book · 简体中文版)