您好!刚知道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 | Mar 13, 2017

<< 第一部分

在这篇博文中,我们将回顾多项式的概念,并解释“盲法评估”多项式的概念,同时还包括如何使用 同态隐藏 (HH) 来实现这一方案。(查看 第一部分 对于 HH 的解释说明⇥)。 在未来的博文中,我们将会认识到盲法评估是 SNARK 建立的中心工具。

我们使用场的尺寸 \(p\) 来表示 \(\mathbb{F}_p\);也就是说,\(\mathbb{F}_p\) 内的元素是 \(\{0,\ldots,p-1\}\) ,同时加法和乘法在 \(\mathrm{mod}\;p\) 中进行,已经在第一部分给出了解释。

多项式和线性组合

回忆多项式 \(P\),在 \(\mathbb{F}_p\) 之上有 \(d\) 级是一种多项式的表现形式。

\(P(X) = a_0 + a_1\cdot X + a_2\cdot X^2 + \ldots + a_d\cdot X^d\), for some \(a_0,\ldots,a_d\in\mathbb{F}_p.\)

我们可以在一个给定点来 评估 \(P\) \(s\in {\mathbb{F}_p}\)\(s\) 带入 \(X\),并计算合成和。

\(P(s) = a_0 + a_1\cdot s + a_2\cdot s^2 + \ldots + a_d\cdot s^d\)

如果有人知道 \(P\)\(P(s)\) 的值是 \(1,s,\ldots,s^d\)线性组合 值 - 线性组合的意思是 “加权和”,也就是说 \(P(s)\) 的“权重是” \(a_0,\ldots,a_d.\)

在最后的博文中,我们看到了由 \(E(x)=g^x\) 定义的 HH \(E\),其中 \(g\) 是由一组难离散对数的结果而产生的。 我们提到这个 HH “支持求和” 的意义是 \(E(x+y)\) 可以由 \(E(x)\)\(E(y)\) 计算得出。 我们注意到它同样"支持线性组合",这意味着,对于给定的 \(a,b,E(x),E(y),\) ,我们可以计算出 \(E(ax+by)\)。 这样做是简单的因为:

\(E(ax+by)=g^{ax+by}=g^{ax}\cdot g^{by} = (g^x)^a\cdot (g^y)^b = E(x)^a\cdot E(y)^b.\)

盲评价一个多项式

假设 Alice 有 \(d\) 阶多项式 \(P\), 并且 Bob 可以随机地处理 \(s\in\mathbb{F}_p\), Bob 期望学习 \(E(P(s))\),比如,HH 对于 \(P\) 的评价是 \(s\) 这样做的两种简单方式是:

  • Alice 发送 \(P\) 给 Bob,从而 Bob 可以自行计算 \(E(P(s))\)
  • Bob 发送 \(s\) 给 Alice;她计算 \(E(P(s))\) 并发送给 Bob。

然而,在 盲评价问题 中,我们希望 Bob 在不了解 \(P\) 的情况下了解 \(E(P(s))\) - 这一准则将会排除第一种选择; 同时,更重要的是,我们不希望 Alice 了解 \(s\),这一准测将会排除第二种选择 [1]

使用 HH,我们可以使用以下方式实现盲法评估。

  1. Bob 给 Alice 发送隐藏的 \(E(1),E(s),\ldots,E(s^d).\)
  2. Alice 从所发送的元素中计算 \(E(P(s))\) 并将 \(E(P(s))\) 发送给 Bob。(Alice 能够这样做的原因是由于 \(E\) 支持线性组合,同时 \(P(s)\)\(1,s,\ldots,s^d.)\) 的一种线性组合)。

请注意,由于仅仅隐藏部分被发送了,因此 Alice 并不知道 \(s\) [2],同时 Bob 也不知道 \(P\)

为什么这是一种有用的方法?

在后面的博文中,我们将详细讨论盲评估技术如何被应用于 SNARKs。 大致的解释是验证器在内部有一个 “正确的”多项式,它需要检查是否证明方知道这件事。这将使得证明方可以在不知晓多项式的前提下验证这个多项式,并保证验证器中的多项式如果不正确,它们有更高的几率报错。这种做法依赖于多项式符号检验中的规则,即“不同多项式在不同的点会不相同”。

[1]我们不想将 P 发送给 Bob 的主要原因是,它是一个大的 -(d+1)元素,比如,d~2000000 是现有 Zcash 协议中,它最终会与“简洁的” SNARKs 协同工作。Bob 所发送给 Alice 隐藏的次序是真实的,但结果是这个次序在参数系统中“难以被编码”,反之 Alice 的信息将因 SNARK 证明的不同而不同。
[2]事实上,隐藏特性仅仅保证了 \(s\) 不能由 \(E(s)\) 反推得到,但在这里,我们想强调它同样不可能由序列 \(E(s),\ldots,E(s^d)\) 反推得到,虽然这个序列包涵了很多 \(s\) 的信息。这样的判断缘于 Diffie-Hellman 假设,这个假设论证了 SNARK 的安全性。