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

zk-SNARKs 的结构包含许多元素的精妙组合;完全了解这些元素需要花费一些时间。

如果你不得不选择 一个最重要的元素,那么你可以把它称为 同态隐藏 (HH) [1]。在这篇博文中,我们将解释 HH 是什么,并解释它为什么如此重要,同时阐述它的构成。

一个 HH \(E(x)\) 是一个关于 \(x\) 的函数,它有如下特点:

以下是关于为什么 HH 可以用于零知识证明的一个简单的例子: 假设 Alice 需要向 Bob 证明她知道数字 \(x,y\) ,则她可以说 \(x+y=7\) 。(当然,知道 \(x,y,\) 的具体数字并不会令人非常激动,但这是解释这个概念非常简洁的例子)。

  1. Alice 发送 \(E(x)\)\(E(y)\) 给 Bob。
  2. Bob 从得到的数值中计算出 \(E(x+y)\) (他可以这么做的原因是 \(E\) 是一个 HH)。
  3. Bob 同样计算出了 \(E(7),\) 并检查 \(E(x+y)=E(7).\) 等式是否成立。只有在等式成立是,他才能认可 Alice 所提供的证明。

由于不同的输入在通过 \(E\) 之后被映射到了不同的隐藏数,因此 Bob 仅仅在 Alice 发送隐藏数 \(x,y\)\(x+y=7.\) 时才能接受这份证明。 在另一方面,Bob 并不知道 \(x\)\(y\),他只能获得与他们有联系的隐藏数 [2]

现在让我们从一个例子中了解隐藏数时如何构成的。事实上,我们不能使用常规的整数加法来构造他们,因此,我们需要关注“有限群”:

假设 \(n\) 时某个整数。当我们对整数 \(A\) 写下 \(A\;\mathrm{mod}\;n\) 时,我们的意思是在 \(A\) 除以 \(n\) 后取余数。比如 \(9\;\mathrm{mod}\; 7 = 2\)\(13\; \mathrm{mod}\;12 = 1\)。 我们可以使用 \(\mathrm{mod}\; n\) 取余操作来定义对于数组 \(\{0,\ldots,n-1\}\) 的额外操作:我们在常规加法后对结果进行 \((\mathrm{mod}\; n)\) 取余操作,并在数组 \(\{0,\ldots,n-1\}\) 范围中得到一个返回值。 我们有时会在右边写下 \((\mathrm{mod}\; n)\) 来声明我们使用的是此种类型的加法。 比如,\(2+3 = 1\; (\mathrm{mod} \;4)\)。 我们将这个数组 \(\{0,\ldots,n-1\}\) 连同求和运算一起称为 \(\mathbb{Z}_n\)

对于一个质数 \(p\),我们可以使用 \(\mathrm{mod}\;p\) 操作来定义一个 乘法 操作,这个乘法操作的元素由数组 \(\{1,\ldots,p-1\}\) 中取得,同时结果也会在数组 \(\{1,\ldots,p-1\}\) 中得到。通过进行对质数的常规乘法,并对结果进行|mod p.| [3] 比如,\(2\cdot 4=1\; (\mathrm{mod}\; 7).\)

这些元素一起构成了组 \(\mathbb{Z}_p^*\)\(\mathbb{Z}_p^*\) 由以下有益的特点:

  1. 它是一个 循环 组;这意味着在 \(\mathbb{Z}_p^*\) 中有些元素 \(g\) 被称为 发生器。因此, \(\mathbb{Z}_p^*\) 中所有的元素都可以被写成 \(g^a\) 的形式,而 \(a\)\(\{0,..,p-2\}\) 中的元素,我们同时定义 \(g^0=1\)
  2. 离散对数问题\(\mathbb{Z}_p^*\) 中相对困难。这意味着,当 p 值较大时,在 \(\mathbb{Z}_p^*\) 中元素 \(h\) 给定的情况下,很难在数组 \(\{0,..,p-2\}\) 中找到整数 \(a\) 。比如 \(g^a=h\;(\mathrm{mod}\;p)\)
  3. 由于 “元素相乘时它们的指数会相加”,则我们可以得到 \(a,b\)\(\{0,..,p-2\}\) \(g^a\cdot g^b = g^{a+b\;(\mathrm{mod}\;p-1)}\) 中。

使用这些特性,我们现在可以建立一个 “支持加法” 的 HH - 这意味着 \(E(x+y)\) 可以由 \(E(x)\)\(E(y)\) 计算得到。 我们假设 \(E\) 中的输入 来自|groupminusone|,因此它的范围是 \(\{0,..,p-2\}\)。 我们将这样的 \(x\) 定义为 \(E(x)=g^x\) ,并称这样的 \(E\) 是一个 HH: 第一个特性表明,在 \(\mathbb{Z}_{p-1}\) 中的不同 \(x\) 会映射不同的输出。 第二个特性表明,对于确定的 \(E(x)=g^x\),很难计算出 \(x\)。 最终,使用第三个特性,对于给定的 \(E(x)\)\(E(y)\),我们可以计算出 \(E(x+y)\)\(E(x+y) = g^{x+y\;\mathrm{mod}\; p-1} = g^x\cdot g^y = E(x)\cdot E(y)\)

[1]同态隐藏并不是密码学中常用的短语,在这里出于解释说明的目的被引入。它与知名的短语“可计算的隐藏承诺”意思相近,但没有这个短语与其强烈。它们的不同点在于,HH 是由输入决定的函数,而承诺则使用了额外的随机性。因此,HH 可以基本“隐藏绝大部分 x”,而承诺则可以“隐藏每一个x”。
[2]Bob 确实可以从 x 和 y 中获得*一些*信息。比如,他可以选择一个随机的 x‘,并通过计算 E(x') 的方式检查 x=x' 等式是否成立。出于这种原因,上面的协议并不是一个真正的零知识证明协议,它仅仅是一个解释例子。事实上,我们会在以后的博文中看到,HH 仅在 snark 隐藏验证者挑战时使用,而不在验证秘密时使用。
[3]当 p 不是质数时,以以上的方式定义乘法是有问题的。其中的一个问题是即便两个参数都不为零,乘积的结果仍可能为零。比如当 p = 4 是,我们可以得到 2*2=0 (mod 4)。