您好!刚知道Zcash吗?
Zcash网络很年轻,但发展迅速! 注册以后我们将与您联系告知有关如何开始使用Zcash的更多信息!

语言

SNARKs 的解释第三部分:知识系数测试和假设

Ariel Gabizon | Mar 28, 2017

<< 第二部分

在第二部分中,我们了解了 Alice 可以使用她的 \(d\) 阶多项式 \(P\)\(s\) 点盲评价属于 Bob 的函数 \(E(P(s))\)。我们将其称为 "盲" 验证,因为 Alice 在这个过程中并不知道 \(s\)

然而,在那项协议中有缺失的部分 - Alice 能够 计算出 \(E(P(s))\) 并不能保证她可以将 \(E(P(s))\) 发送给 Bob,更不用说一些完全不相关的价值。

因此,我们需要一种 “强制” Alice 正确地遵从协议的方式。我们将在第四部分详细解释我们如何实现这一点。在本片博文中,我们专注与解释实现这一功能需要用到的工具 - 我们将其称为 "知识系数(KC)测试"。

正如之前一样,我们使用 \(g\) 表示由 \(G\)\(|G|=p\) 时的一组计算结果,在这里离散对数是困难的。在文章开始时使用加法而不是乘法是更加方便的解释方式。 那就是,对于 \(\alpha\in\mathbb{F}_p\)\(\alpha\cdot g\) 表示 \(\alpha\) 副本 \(g\) 的求和。

KC 测试

对于 \(\alpha\in\mathbb{F}_p^*\) [1], 如果 \(a,b \neq 0\)\(b=\alpha\cdot a\) 成立,则我们称 \(G\) 中的一组元素 \((a,b)\)\(\alpha\)-pair。

KC 测试按照如下的步骤进行。

  1. Bob 随机选择了 \(\alpha\in\mathbb{F}_p^*\)\(a\in G\) 。他计算得到了 \(b=\alpha\cdot a\)
  2. 他发送 "挑战" 对 \((a,b)\) 给 Alice。注意,\((a,b)\) 是一个 \(\alpha\)-pair 。
  3. Alice 现在必须回复一个*不同的* 对 \((a',b')\) 同时也必须是 \(\alpha\)-pair 。
  4. 如果 \((a',b')\) 确实是一个 \(\alpha\)-pair ,则 Bob 接受 Alice 的回复。(由于他知道 \(\alpha\) ,他可以检查 \(b'=\alpha\cdot a'.)\) 是否成立。)

现在,让我们思考 Alice 如何成功地回复挑战。 让我们假设她 知道 \(\alpha\) 。 在这种情况下,她便可以在 \(G\) 中简单地挑选出 \(a'\),并计算出 \(b'=\alpha\cdot a';\) 同时返回 \((a',b')\) 表示她得到了新的 \(\alpha\)-pair 。

然而,由于 Alice 在 \(\alpha\cdot a\) 中仅有唯一的信息 \(\alpha\) ,并且 \(G\) 存在难解的离散对数问题,我们可以假设 Alice 并不能得到 \(\alpha\)

因此,如果让 Alice 在不知道 \(\alpha\) 的前提下成功回复挑战呢?

以下是实现这一目标的自然做法: Alice 简单地选择一些 \(\gamma\in\mathbb{F}_p^*\),并且回复 \((a',b')=(\gamma\cdot a,\gamma\cdot b)\)

在这种情况下,我们有:

\(b'=\gamma \cdot b = \gamma \alpha \cdot a = \alpha (\gamma\cdot a) =\alpha \cdot a',\)

确实 \((a',b')\) 是这里需要的 \(\alpha\)-pair 。

注意到,如果 Alice 使用这种策略进行回复,她将 知道 \(a\)\(a'\) 的比例。 也就是说,她知道系数 \(\gamma\) 根据 \(a'=\gamma\cdot a\)

知识系数假设 [2] (KCA) 称 这总是如此,也就是说:

KCA: 如果 Alice 返回一个有效的回复 \((a',b')\) * 给 Bob 的挑战 * \((a,b)\) 此时有不可忽视的可能性 Bob 选择了 \(a,\alpha\)此时她便知道 \(\gamma\) 因此得到 \(a'=\gamma\cdot a\)

KC 测试和假设将是第四部分说明的重要工具。

“Alice 知道” 的确切意义是什么?

你也许会好奇我们如何将 KCA 用准确地数学形式表达出来;特别地,我们如何用数学的方法定义 “Alice 知道 \(\gamma\)”?

上述功能通过以下步骤实现: 我们说,除了 Alice 之外,我们有一个被称为 Alice 的提取器 的角色。 Alice 的提取器可以访问 Alice 的内部状态。

我们这时便可以用公式表示 KCA: 当 Alice 使用一个 \(\alpha\)-pair \((a',b')\) 成功回复时,Alice 的提取器将输出 \(\gamma\) 从而得到 \(a'=\gamma\cdot a.\) [3]

[1]\(\mathbb{F}_p^*\) 表示 \(\mathbb{F}_p\) 中的非零元素,它与第一部分描述的 \(\mathbb{Z}_p^*\) 相类似。
[2]它的书面名称为知识系数假设,这个称为的由来是古时候它被用于形容聚在一起写作的小组。
[3]在这里的完整正式定义需要让提取器 “稍微休息以下”并声明,Alice 成功回复但是提取器无法正常输出 \(\gamma\) 的可能性可以忽略。

cryptography, zkSNARKs, explainers | 查看所有标签