Halo2 协议

预备工作

我们定义 $λ$ 作为一个安全参数，且除明确标注外，文档中所有的算法和敌手(adversaries)都是在该安全参数下运行时间为多项式的概率型图灵机。我们使用 $negl (λ)$ 表示一个在 $λ$ 下可忽略的函数。

密码学群

我们令 $G$ 表示一个阶为素数 $p$ 的循环群，群的单位元记作 $O$ 。将 $G$ 中元素的标量表示为阶为 $p$ 的标量域 $F$ 中的元素。群元素用大写字母表示，标量则用小写字母或希腊字母表示。群元素或标量所组成的向量用粗体字表示，例如 $a \in F^{n}$ 以及 $G \in G^{n}$ 。群上的运算记作加法，群元素 $G$ 和标量 $a$ 的乘法记作 $[a] G$ 。

我们会经常使用 $⟨ a, b ⟩$ 表示长度相等的， $F^{n}$ 上 $a, b$ 两个向量的内积。同样地也用这种表示法描述群元素的一个线性组合 $⟨ a, G ⟩$ ，其中 $a \in F^{n}, G \in G^{n}$ ，该内积的计算是通过群中的标量乘法和加法实现的。

我们使用 $0^{n}$ 描述域 $F$ 中长度为 $n$ 的，只包含零元的向量。

离散对数关系问题 攻击者优势（advantage）的度量（metric）为： $Adv_{G, n}^{dl - rel} (A, λ) = Pr [G_{G, n}^{dl - rel} (A, λ)]$ 其定义为赢得以下游戏的概率。 $\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})$ 即：如果攻击者能够给出一个 $a$ 使得 $⟨ 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}$ 描述该问题。

交互式证明是一个算法三元组 $IP = (Setup, P, V)$ 。 $Setup (1^{λ})$ 算法用于生成某些被 $pp$ 引用的 公开参数 。证明者 $P$ 和验证者 $V$ 是能够访问 $pp$ 的交互式机器，我们用 $⟨ P (x), V (y)⟩$ 表示在 $P$ 和 $V$ 之间执行的两方协议，其输入为 $x$ 和 $y$ 。协议的输出是一个 transcript ，包含了所有 $P$ 和 $V$ 之间交互的消息。在协议的最后，验证者输出一个决策位，表示它是否接受证明者的证明。

关于知识的零知识证明

知识证明是一种交互式证明，指证明者试图向验证者证明它知道一个 witness $w$ 使得 $(x, w) \in R$ ，其中 $x$ 为一个 statement ， $R$ 为多项式时间内可决定的 relation。我们假设证明者的计算能力是有限的，在这个假设下研究知识证明。

我们将从四个角度分析知识证明的安全程度：

完备性: 如果证明者有一个有效的 witness ，它是否总是能够向验证者证明这一点？完备性做出了一些假设，理解完备性将有助于理解其他的安全性
可靠性: 一个试图作弊的证明者能否向验证者成功证明一个错误的 statement ? 我们将发生这种情况的可能性称为 可靠性错误 。
知识可靠性: 当验证者确信 statement 是正确的时候，证明者是否实际拥有（“知道”）一个有效的 witness ？我们将验证者确信，但证明者并不拥有有效 witness 的可能性称为 知识错误 。
零知识性: 除了 statement 的正确性和证明者实际拥有该有效 witness 之外，验证者是否还获得了额外的知识？

首先，我们考察完备性的一个简单定义：

完美完备性： 一个交互式证明 $(Setup, P, V)$ 是 完美完备的 当对于所有的多项式时间内可决定的关系 $R$ 和所有非均匀的多项式时间攻击者 $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 变换，它被实现为 非交互式 的。

Public coin： 我们将那种验证者发送的每个消息都来自新的随机性采样的交互式证明称为 public coin 式。

Fiat-Shamir 变换： 将验证者发送的消息替换为密码学上健壮的哈希函数以产生足够的随机性，即可将交互的 public coin 式证明在 随机预言机模型 中转换为 非交互式 的。

这种形式变换意味着在实际的协议中，一个试图作弊的证明者可以通过对 transcript 进行分叉，修改某个时刻自己应该发送给验证者的消息，从而轻易的达成状态“回卷”。因此，研究我们的协议在 Fiat-Shamir 变换之后的安全性是非常重要的。幸运的是我们可以依照 Ghoshal 和 Tessaro 提出的框架 ([GT20]) 来进行分析。

我们通过 状态恢复可靠性 的概念分析我们的协议。在该模型中，（作弊的）证明者可以“回卷”验证者至之前任意的状态。如果证明者能通过这种方式使验证者接受证明，则是对我们协议一次成功的攻击。

状态恢复可靠性： 令 $IP$ 是一个交互式的 argument ，包含有 $r >= r (λ)$ 个验证者挑战。令第 $i$ th 个挑战是从 $Ch_{i}$ 中采样获得，则一个具备状态恢复能力的证明者 $P$ 的优势度量（advantage metric）为 $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 。这意味着，对于任意成功证明的证明者算法，都存在一个高效的仿真器，通过状态“回卷”和提供新的随机数，仿真器可以从算法中提取出 witness 。

但我们必须调整一下我们对于 witness extended emulation 的定义，以描述一个事实，即我们协议中的证明者都是有状态恢复能力的证明者，能够“回卷”验证者。另外，为避免在提取 witness 时回卷证明者，我们在 代数群模型 中研究我们的协议。

代数群模型（Algebraic Group Model, AGM） 若攻击者 $P_{alg}$ 在每次输出群元素 $X$ 的时候同时也输出 $X$ 在 $F^{n}$ 中的一个表示 $x \in F^{n}$ ，使得 $⟨ x, G ⟩ = X$ ， $G \in G^{n}$ 是 $P_{alg}$ 到目前为止所知的群元素的向量，则我们说 $P_{alg}$ 是 代数的 。

我们用 $[X]$ 描述一个以代数方法表示的群元素 $X$ ，定义 $[X]_{i}^{G}$ 为 $X$ 用 $G_{i}$ 表示的系数，即 $X = i = 0 \sum n - 1 [[X]_{i}^{G}] G_{i}$

代数群模型允许我们对某些协议进行所谓的“在线”提取：提取者可以从某个被接受的 transcript 的表示方式中提取出 witness 。

状态恢复的 witness extended emulation 令 $IP$ 是一个关系 $R$ 的交互式证明，包含 $r = r (λ)$ 个挑战。我们对所有非均匀的代数证明者 $P_{alg}$ ，提取者 $E$ ，以及拥有无限计算能力的辨别者 $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 ⊥$

零知识性

若验证者在协议的交互中除了知道存在一个有效的 $w$ 之外没有获得任何其他额外的知识，则我们说该关于知识的证明是 零知识性 的。

完美特殊诚实验证者零知识性 一个交互式的 public coin 证明 $(Setup, P, V)$ 拥有 完美特殊诚实验证者零知识性 (PSHVZK) 仅当对于所有多项式时间可决定的关系 $R$ 和所有 $(x, w) \in R$ 及所有非均匀多项式时间的攻击者 $A_{1}$ ， $A_{2}$ ，存在一个概率性的多项式时间模拟器 $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, ρ) ⎦ ⎤$ $ρ$ 表示 verifier 内在的随机性。

在这个零知识性的定义下，验证者预期将会“诚实地”进行交互，并发送只与它的内在随机性相关的挑战。它们不能根据证明者发送的消息改变自己的挑战。我们使用该定义的一种增强形式，要求模拟器输出包含和验证者所发送的相同挑战的 transcript 。

协议

令 $ω \in F$ 是 $n = 2^{k}$ 的单位根，组成一个 domain $D = (ω^{0}, ω^{1}, ..., ω^{n - 1})$ ， $t (X) = X^{n} - 1$ 为该 domain 上的消退多项式。令 $k, n_{g}, n_{a}$ 为正整数。对于关系 $R = ⎩ ⎨ ⎧ ((g (X, C_{0}, C_{1}, ..., C_{n_{a} - 1})); (a_{0} (X), a_{1} (X, C_{0}), ..., a_{n_{a} - 1} (X, C_{0}, C_{1}, ..., C_{n_{a} - 1}))) : g (ω^{i}, C_{0}, C_{1}, ..., C_{n_{a} - 1}) = 0 \forall i \in [0, 2^{k}) ⎭ ⎬ ⎫$

我们提出一种交互式证明 $Halo = (Setup, P, V)$ ，其中 $a_{0}, a_{1}, ..., a_{n_{a} - 1}$ 是关于 $X$ 的阶为 $n - 1$ 的（多变量）多项式， $g$ 是关于 $X$ 的阶为 $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}$ .
令 $σ (i) = q_{j}$ ，若 $q_{j} = p_{i}$ .

令 $n_{q}$ 表示集合 $q$ 的大小，不失一般性地，令 $n_{e}$ 表示每个 $p_{i}$ 集合的大小。

在下述的协议中，我们默认每个 $a_{i} (X, \dots)$ 多项式为 $n_{e} + 1$ 个盲因子均为验证者新采样的，且以 domain $D$ 上各点值的形式表示。

$P$ 和 $V$ 进行 $n_{a}$ 轮交互，在第 $j$ 轮中（轮次从0开始）

$P$ 设置 $a_{j}^{'} (X) = a_{j} (X, c_{0}, c_{1}, ..., c_{j - 1})$
$P$ 发送一个隐藏用的承诺 $A_{j} = ⟨ a^{'}, G ⟩ + [\cdot] W$ ，其中 $a^{'}$ 为单变量多项式 $a_{j}^{'} (X)$ 的系数， $\cdot$ 为某个随机且独立采样的盲因子。
$V$ 回应 $P$ 一个挑战 $c_{j}$ .

$P$ 和 $V$ 设置 $g^{'} (X) = g (X, c_{0}, c_{1}, ..., c_{n_{a} - 1})$ .
$P$ 发送一个承诺 $R = ⟨ r, G ⟩ + [\cdot] W$ ，其中 $r \in F^{n}$ 为随机采样的单变量多项式 $r (X)$ 的系数，其度数为 $n - 1$ 。
$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$ 将所有的承诺 $H_{i} = ⟨ h_{i}, G ⟩ + [\cdot] W$ 发送给 $V$ ，其中 $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}]$ ，都有 $(a_{i})_{j} = a_{i}^{'} (ω^{(p_{i})_{j}} x)$ 。
对所有的 $i \in [0, n_{a})$ ， $P$ 和 $V$ 设置 $s_{i} (X)$ 为度数最低的单变量多项式，使得对所有的 $j \in [0, n_{e})$ ， $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$ 到 $i = n_{a} - 1$ ， $V$ 设置 $Q_{σ (i)} := [x_{1}] Q_{σ (i)} + A_{i}$ .
最后 $V$ 设置 $Q_{0} := [x_{1}^{2}] Q_{i} + [x_{1}] H^{'} + R$ .

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

从 $i = 0$ 开始到 $i = 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$ 开始到 $i = 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$ ， $V$ 使用由 $P$ 提供的 $r$ 和 $a$ 计算 $h = \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}}$ 使得 $u_{i} = q_{i} (x_{3})$ for all $i \in [0, n_{q})$ .
$V$ 回以挑战 $x_{4}$ .
$P$ 和 $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$ 的多项式 $s (X)$ （其中一个根为 $x_{3}$ ），并发送其承诺 $S = ⟨ s, G ⟩ + [\cdot] W$ ， $s$ 为 $s (X)$ 多项式的系数。
$V$ 回以挑战 $ξ, z$ .
$P$ 和 $V$ 设置 $P^{'} = P - [v] G_{0} + [ξ] S$ .
$P$ 设置 $p^{'} (X) = p (X) - v + ξ s (X)$ .
初始化 $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$ and $R_{j} = ⟨ p^{'}_{lo}, G^{'}_{hi} ⟩ + [z ⟨ p^{'}_{lo}, b_{hi} ⟩] U + [\cdot] W$ .
$V$ 回以挑战 $u_{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}$ 以及盲因子 $f$ .
若 $\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$ ，则 $V$ 接受证明。

The halo2 Book