LPCP和LIP

LIP

在线性 IP (Linear IP, LIP) 模型中，Prover 和 Verifier 进行对话。但是，相比于 IP 模型，增加了一些限制条件：Prover 只能是线性的。

什么是线性的 Prover 呢? 首先, Verifier 发给 Prover 的消息只能是 \(\mathbb{F}^n\) 中的向量, 而 Prover 的消息只能是 Verifier 消息的线性函数。一个向量的线性函数, 其实就是在这个向量上乘一个矩阵。所以, 在第 \(i\) 轮交互中, 收到 Verifier 的请求 \(\vec{v}_i \in \mathbb{F}^n\), 此时 Prover 已经收到了 \(i\) 个 Verifier 消息, 记这些消息合在一起的向量为 \(\left(\vec{v}_1\|\cdots\| \vec{v}_i\right)\), 它的长度是 \(n \cdot i\) 。于是, Prover 只能选取一个矩阵 \(A_i \in \mathbb{F}^{n \cdot i \times k}\) 并计算 \(\vec{y}_i=A_i\left(\vec{v}_1\|\cdots\| \vec{v}_i\right)\) 发送给 Verifier。

Prover 计算矩阵 \(A_i\) 时, 不能用到 Verifier 的请求中的信息, 否则 Prover 最终的计算结果就不是线性的了。也就是说, 计算 \(A_i\) 时只能使用 Setup 信息, 陈述 \(x\), 证据 \(w\) 以及 Prover 自己的随机数。因为计算矩阵 \(A_i\) 时, Prover 没有用到任何的 Verifier 消息。所以, 在和 Verifier 交流之前, Prover 就可以把所有矩阵提前计算好。

因为 LIP 对 Prover 做了很强的限制, 它是一个理想模型, 现实中并不存在严格遵守约定的 Prover。假如有一个 LIP 模型下的零知识证明系统, 现在我们要把它转化成 zkSNARK。转化的思路是, 使用密码学手段让 Prover 无法破坏线性的约定。

我们用只支持加法的同态加密 \(\operatorname{Enc}(\cdot)\) 来确保 Prover 只能计算 Verifier 消息的线性函数。每当 Verifier 需要发送消息 \(\vec{v}\) 时, Verifier 对 \(\vec{v}\) 的每一位计算 \(c_i=\operatorname{Enc}\left(v_i\right)\), 得到一个密文向量 \(\vec{c}\) 。在密文空间中, Prover 只能进行线性运算, 而且根据密文无法获知明文。而 Verifier 可以用密钥解开密文 \(A \vec{c}\) 得到 \(\vec{y}=A \vec{v}\) 。

使用同态加密 \(\operatorname{Enc}(\cdot)\), 只是把 LIP 模型下的证明系统转化成了 IP 模型下的证明系统。这是一个秘密随机数的证明系统, 所以不能对它应用 Fiat-Shamir 变换得到 zkSNARK。要想得到 zkSNARK, 需要用到可信第三方 TTP。TTP 采样出所有 \(\vec{v}_i\) 并加密得到 \(\vec{c}_i\), 把密文放到 Setup 信息中, 然后把密钥删掉。

==目前上面这一部分理解的还不是很透彻==

这样一来，不仅 Prover，连 Verifier 也只能够进行线性运算了。这么一来，这个系统就没多大意义。为了能让 Verifier 做至少一次非线性运算，一个方法就是引入双线性对。双线性对允许对密文做乘法，但是乘法的计算结果是在另外一个密文空间中的，所以不影响安全性。

一个双线性包含以下内容: 群 \(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T\), 其中 \(\mathbb{G}_1\) 和 \(\mathbb{G}_2\) 的生成元分别为 \(g_1, g_2\), 以及映 射 \(e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T\), 满 足 \(e\left(g_1, g_2\right)\) 是 \(\mathbb{G}_T\) 的生成元, 且 \(e\left(\alpha \cdot g_1, \beta \cdot g_2\right)=\alpha \beta \cdot e\left(g_1, g_2\right)\) 。

即使使用双线性对, Verifier 也只能在验证中使用一次乘法, 这对 LIP 模型来说是一个很强的限制。

我们如下构造一个通用的从 LIP 到 zkSNARK 的转换。简便起见, 我们假设 LIP 的验证过程中只会用到 \(\vec{y}_i\) 和 \(\vec{v}_i\) 之间的乘法以及 \(\vec{v}_i\) 内部元素之间的乘法。另外假设 Verifier 的消息的计算过程不依赖于 Prover 消息。

给定 LIP 方案 \(\mathcal{P}_{\text {LIP }}\) 和 \(\mathcal{V}_{\text {LIP }}\), 以及双线性对 \(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, g_1, g_2, e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T\), 可以得到如下 zkSNARK 方案: 1. Setup 阶段，由可信第三方执行 \(\mathcal{V}\), 得到 Verifier 消息 \(\vec{v}_1, \cdots, \vec{v}_m\), 计算出 \(\operatorname{Setup}_P=\operatorname{Setup}_V=\left(\vec{v}_1 \cdot g_1, \cdots \vec{v}_m \cdot g_1, \vec{v}_1 \cdot g_2, \cdots, \vec{v}_m \cdot g_2\right)\) 2. Prover 按照 \(\mathcal{P}_{\text {LIP }}\) 的逻辑, 根据输入的 \(x\) 和 \(w\) 构造矩阵 \(A_1, \cdots, A_m\), 然后对 \(i \in[1, m]\) 计算证明 \(\vec{y}_i \cdot g_1=A_i\left(\vec{v}_1, \cdots, \vec{v}_i\right) \cdot g_1\) 3. Verifier 调用 \(\mathcal{V}_{\mathrm{LIP}}\) 验证 \(\vec{v}_1, \cdots, \vec{v}_m, \vec{y}_1, \cdots, \vec{y}_m\) 的合法性。验证过程中, 调用映射 \(e\) 来计算乘积

LPCP

在线性 PCP (Linear PCP, LPCP) 模型中, Prover 发送一个线性预言机给 Verifier。一个线性预言机代表一个线性函数 \(\pi: \mathbb{F}^n \rightarrow \mathbb{F}\) 。Verifier 可以随意查询线性预言机, 得到 \(\pi\left(\vec{v}_1\right), \cdots, \pi\left(\vec{v}_m\right)\), 最后根据得到的所有数据做出判断。

LPCP 模型下的证明系统可以由 LIP 模型实现。让 Prover 来充当线性预言机的角色。不过, 需要确保 Prover 每次都会用同一个线性函数 \(\pi\) 。因为 Prover 只能使用线性策略,这个转换很简单, 完全不用密码学的工具。

给定一个 LPCP 方案 \(\mathcal{P}_{\mathrm{LPCP}}\) 和 \(\mathcal{V}_{\mathrm{LPCP}}\), 构造如下的 LIP 方案 \(\mathcal{P}_{\mathrm{LIP}}\) 和 \(\mathcal{V}_{\mathrm{LIP}}\) 。 1. \(\mathcal{P}_{\text {LIP }}\) 执行 \(\mathcal{P}_{\text {LPCP }}\) 生成线性函数 \(\pi\) 。 2. 当 \(\mathcal{P}_{\text {LPCP }}\) 需要发送线性预言机时, \(\mathcal{P}_{\text {LIP }}\) 什么也不做。 3. \(\mathcal{V}_{\mathrm{LIP}}\) 调用 \(\mathcal{V}_{\mathrm{LPCP}}\) 生成查询 \(\vec{v}_i\) 。 4. 当 \(\mathcal{V}_{\mathrm{LPCP}}\) 需要查询线性预言机时, \(\mathcal{V}_{\mathrm{LIP}}\) 将 \(\vec{v}_i\) 发送给 \(\mathcal{P}_{\mathrm{LIP}}, \mathcal{P}_{\mathrm{LIP}}\) 计算 \(a_i=\pi\left(\vec{v}_i\right)\) 发送给 \(\mathcal{V}_{\mathrm{LIP}}\) 5. \(\mathcal{V}_{\mathrm{LPCP}}\) 所有的查询结束后, \(\mathcal{V}_{\mathrm{LIP}}\) 再额外随机产生 \(\alpha_1, \cdots, \alpha_m\), 并发送 \(\vec{v}_{m+1}=\sum_{i=1}^m \alpha_i \vec{v}_i\) 给 \(\mathcal{P}_{\text {LIP 。 }}\) 6. \(\mathcal{P}_{\text {LIP }}\) 计算 \(a_{m+1}=\pi\left(\vec{v}_{m+1}\right)\) 返回给 \(\mathcal{V}_{\text {LIP 。 }}\) 7. \(\mathcal{V}_{\mathrm{LIP}}\) 验证 \(a_{m+1}=\sum_{i=1}^m \alpha_i a_i\) 。 8. 最后 \(\mathcal{V}_{\mathrm{LIP}}\) 执行 \(\mathcal{V}_{\mathrm{LPCP}}\) 的验证逻辑, 验证 \(a_1, \cdots, a_m\) 是合法的证明过程。

第 5-7 步中验证随机的线性组合, 就是用来确保 Prover 每次一定使用相同的 \(\pi\) 。因为在 LIP 模型中, Prover 使用的所有矩阵都是独立于 Verifier 消息的。除非 Prover 在每一步都使用相同的 \(\pi\), 否则上述第 7 步的验证都大概率不会通过。