您好!刚知道Zcash吗?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

语言

解释 SNARKs 第四部分: 如何为可验证多项式进行盲评价

Ariel Gabizon | Apr 11, 2017

<< 第三部分

在这一部分中,我们在第二部分和第三部分的基础上开发可验证的盲评价多项式协议,我们将在稍后给出它的定义。在第五部分中,我们将开始建造 SNARKs,因此请随我一起在建立与 SNARKs 联系之前再忍耐以下。:)

假设,在 第二部分 中,Alice 有 \(d\) 阶多项式 \(P\),Bob 有它随机选择的点 \(s\in\mathbb{F}_p\) 。我们希望建立一个可以让 Bob 来学习 \(E(P(s))\) 的协议,比如,在 \(s\) 中隐藏 \(P\) 。并使用两种额外的性能。

  1. 盲的: Alice 将*不会*得知 \(s\) (同时 Bob 不会得知 \(P\) )。
  2. 可验证性:Alice 发送从 \(d\) 阶多项式 \(P\) 中发送一笔价值 \(E(P(s))\),这个行为是她了解的, Bob 同样接受。以上这件事发生的可能性可以忽略。

这就是被我们称为 可验证 的盲评价多项式。第二部分的协议给出了我们需要的第一个条款,但没有包括第二个。为了实现可验证性,我们需要将第三部分提到的知识系数假设 (KCA) 扩充到一个新的版本。

可验证性和盲特性是在一起协同使用的,这是由于它们可以让 Alice 在 不查看 \(s\) 的情况下决定选择哪个多项式 \(P\)[1] 这,在某种意义上,可以保证 Alice 在不查看 “挑战点” \(s\) 的情况下得到"答案多项式"。这种直觉将在后面的系列中变得更加清晰。

一个可扩充的 KCA

KCA 在第三部分的定义是: 如果 Bob 给了 Alice 一些 \(\alpha\)-pair \((a,b = \alpha\cdot a)\),则 Alice 便会产生新的 \(\alpha\)-pair \((a',b')\),这时她便可以推导出 \(c\) 因为 \(a'=c\cdot a\)。换句话来说,Alice 知道了 \(a'\)\(a\) 之间的关系。

现在,假设 Bob 并没有给 Alice 发送一个而是发送了多个 \(\alpha\)-pairs \((a_1,b_1),\ldots,(a_d,b_d)\) (对于同一个 \(\alpha\)) 同样,在收到这些对之后,Alice 需要产生另外一些 \(\alpha\)-pair \((a',b')\)。 回想起关键点在于 Alice 必须在 她不知道 的前提下这么做。

正如我们在第三部分看到的,一个让 Alice 产生这样的 \(\alpha\)-pair 的自然方式是选取她从 Bob 处收到的一个配对 \((a_i,b_i)\),并将两个元素都与 \(c\in\mathbb{F}^*_p\) 相乘; 如果 \((a_i,b_i)\) 是一个 \(\alpha\)-pair,则 \((c\cdot a_i,c\cdot b_i)\) 将同样也是。 但是,Alice 可以鉴于 Alice 收到了 多重 \(\alpha\)-pairs,她可以有更多的方式产生 \(\alpha\)-pairs 吗? 或许可以*同时*使用多个收到的 \(\alpha\)-pairs 来产生一个新的配对?

答案是肯定的:比如,Alice 可以选择 两个 \(c_1,c_2\in \mathbb{F}_p\) 的值,从而计算配对 \((a',b')=(c_1\cdot a_1 + c_2\cdot a_2, c_1\cdot b_1 + c_2\cdot b_2)\)。一个简单的计算方法表明,只要 \(a'\) 非零,就可以得到一个 \(\alpha\)-pair:

\(b' = c_1\cdot b_1 + c_2 \cdot b_2 = c_1 \alpha \cdot a_1 + c_2\alpha\cdot a_2 = \alpha (c_1\cdot a_1 + c_2\cdot a_2) = \alpha\cdot a'.\)

更一般的,Alice 可以使用任何 \(d\) 配对的 线性组合,从而选择任何 \(c_1,\ldots,c_d\in\mathbb{F}_p\),并且定义 \((a',b')=(\sum_{i=1}^d c_i a_i,\sum_{i=1}^d c_ib_i)\).

注意到,如果 Alice 使用这种策略生成她的 \(\alpha\)-pair,她将知道一些 \(a'\)\(a_1,\ldots,a_d\) 之间的线性关系;也就是说,她将根据 \(a'=\sum_{i=1}^d c_i\cdot a_i\) 知道 \(c_1,\ldots,c_d\)

扩充的 KCA 表明,这是 Alice 产生一个 \(\alpha\)-pair 的唯一方式; 也就是说,当她成功时,她会知道 \(a'\)\(a_1,\ldots,a_d\) 之间的线性关系。 更正式地来说,假设 \(G\) 是由 \(p\) 组成的一个组,并且在第三部分中附加地产生了 \(g\)。 则 \(G\) 中的 d-power 知识系数假设 (d-KCA) [2] 将会是以下形式:

d-KCA假设 Bob 随机选择 \(\alpha\in\mathbb{F}_p^*\) \(s\in\mathbb{F}_p\), 同时发送给 Alice |alphapairs| |galpg-sdgalpsdg|. 假设 Alice 这时输出了另外一个 \(\alpha\)-pair \((a',b')\)。这时,除了可忽略的可能性,Alice 知道 \(c_1,\ldots,c_d\in\mathbb{F}_p\) 比如 \(\sum_{i=0}^d c_i s^i\cdot g = a'\).

注意到,在 d-KCA 中,Bob 并没有发送任意的 \(\alpha\)-pairs,而是发送了有特定“多项式结构” 的多项式。这将为下面提到的协议有所帮助。

可验证的盲评价合约

假设我们的 HH\(E(x)=x\cdot g\) 的映射,它用来为上面的 \(G\) 产生 \(g\)

为简单期间,我们对于这个特别的 \(E\) 展示了协议:

  1. Bob 选择一个随机的 \(\alpha\in\mathbb{F}_p^*\),并且发送给 Alice 隐藏的 \(g,s\cdot g,\ldots,s^d\cdot g\) (对应 \(1,s,\ldots,s^d\) ) 和同样隐藏的 \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\) (对应 \(\alpha,\alpha s,\ldots,\alpha s^d\))。
  2. Alice 使用第一步中发送的元素计算出 \(a=P(s)\cdot g\)\(b=\alpha P(s)\cdot g\),并且都发送给 Bob。
  3. Bob 检查了 \(b=\alpha \cdot a\),如果这个等式成立就会将其接受。

首先,注意到对于给定的系数 \(P\)\(P(s)\cdot g\)\(g,s\cdot g,\ldots,s^d\cdot g\) 的线性组合;而 \(\alpha P(s)\cdot g\)\(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\) 的线性组合。 因此,与第二部分的协议相似,Alice 确实能够计算出 Bob 所发送来的价值,从而得到多项式 \(P\)

其次,通过 d-KCA,如果 Alice 发送了 \(a\), \(b\) 比如 \(b=\alpha \cdot a\) 则,可以确定她知道 \(c_1,\ldots,c_d\in\mathbb{F}_p\) 比如 \(a=\sum_{i=0}^d c_is^i\cdot g\)。 在这种情况下,多项式 \(P(X)=\sum_{i=0}^d c_i\cdot X^i\) 中所使用的 \(a=P(s)\cdot g\) 便被 Alice 所知晓。 换句话来说,Bob 在第 3 部接受的同时 Alice 不知道 \(P\) 的概率几乎可以忽略。

总结,通过使用 d-KCA ,我们已经研发出了可验证的盲评价多项式的协议。在下面的博文中,我们将看到它所建立的区块是如何构建 SNARK 的。

[1]在完全正式的证明中,事物是非常微妙的,比如 Alice 在决定 \(P\) 之前 确实 看到了关于 \(s\) 的信息 - 比如, ⇥隐藏的 \(s,\ldots,s^d\)
[2]d-KCA 在 Jens Groth 的 文章 中有所介绍。

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