Greetings! New to Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with more information about how you can get started with Zcash!

语种

Zcash 参数 和如何产生这些参数

Ariel Gabizon | Sep 22, 2016

Zcash 隐私技术的核心依赖于一项新颖的密码学工具,这个工具被称之为 zkSNARK - 一个小型的、廉价的 零知识证明工具 。Zcash 是第一个将这个工具规模化的项目。为了让这些 zkSNARK 正常工作,需要进行相位配置以便 "系统参数" 可以产生。 这个相位配置类似于配置密码学系统中公钥的相位,与之不同的是这里的相位需要捕捉一个参数。更为具体的解释是:在密码学系统的公钥里,一对参数 (\(\mathsf{privkey},\) \(\mathsf{pubkey)}\) 会被计算产生,但 \(\mathsf{privkey}\) 在产生后被立即 销毁 。真实情况是:在系统相位被设定后,没有人可以取得 \(\mathsf{privkey}\) 对于整个系统的完整性是有帮助的。

\(\mathsf{privkey}\) 与需求的系统参数相一致。 \(\mathsf{privkey}\) 与所谓的”有毒肥料“相一致 here, 拥有 \(\mathsf{privkey}\) 可以具获得造新币的能力(但是不能获得供给其他用户转账隐私的能力)。

为了减小风险,Zcash在 \(\mathsf{privkey}\) 生成的地方设计了一个多用户协议。这个协议拥有串联参与者的秘密随机数的功能。因此,除非所有的参与者都是不诚实的或者是勾结在一起的,不然 \(\mathsf{privkey}\) 是会被销毁的。

这篇博文的目的是简单的解释 \(\mathsf{privkey}\) 是什么和他的协议是如何产生的。

\(\mathsf{pubkey}\) 是什么样子的?

假设 \(g\) 是一组离散对数 \(G\) 的发生器。我们假定 \(G\)\(r\) 阶素数 \(r,\) ,并且我们可以写入一组附加的操作。所以,对于 \(s\in \mathbb{F}\) , 我们可以写 \(s\cdot g\) 来表示 \(g\)\(s\) 的标量成绩,其中 \(\mathbb{F}\)\(r\) 的字段长度。 例如: \(s\cdot g\) 是由添加 \(s\)\(g\) 后得到的。一个简单版本的 (\(\mathsf{privkey},\) \(\mathsf{pubkey)}\) 例子是: \(\mathsf{privkey}\) 是由 \(s\in \mathbb{F}^*\) 产生的一致性随机数, \(\mathsf{pubkey}\) 是一组有序的数字。

\(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g)\)

在上文中, \(\mathbb{F}^*\) 表示所有在 \(\mathbb{F}.\) 中不为零的元素。

如何产生 \(\mathsf{pubkey}\)

我们会在稍后介绍 为什么 \(\mathsf{pubkey}\) 会是这样的形式和它是如何被使用的。让我们先来关注如何设计协议来生成 \(\mathsf{pubkey}\)

为了简便,让我们先集中于 \(d=2\) ;同时忽略 \(\mathsf{pubkey}\) 第一个 \(g\) 元素。假设现在有两个人 Alice 和 Bob,他们想要为系统生成一个有效的公钥 \(\mathsf{pubkey}=\) \((s\cdot g, s^2\cdot g)\) 。他们希望在生成公钥的过程中,没有人会知道 \(s.\) 这个参数。让我们先把问题简化,假设他们只想要生成 \(s\cdot g\) (同样没有人会知道 \(s.\) )。他们使用了下面的协议:

  1. Alice 选择了一个随机的 \(a\in \mathbb{F}^*\), 并将:math:M_1:= acdot g 发送给 Bob 。
  2. Bob 选择一个随机的 \(b\in \mathbb{F}^*\) 并将 \(M_1\)\(b\) 相乘。他将 \(M:= b\cdot M_1\) 结合在一起并将信息发回给 Alice 。

在协议的结尾,我们得到了 \(M=b\cdot a \cdot g = (a b)\cdot g\). 让我们将它表示为 \(s:= a b\).

请注意

  • Bob 并没有从消息 \(M_1,\) 中得到数据 \(a\),因为我们假设在 \(G\) 中的离散对数是非常复杂的。同样的情况适用于 Alice,她并没有得到数据 \(b.\)。尤其是,他们中没有人知道 \(a\)\(b\) 的乘积 \(s\)
  • 对于任何固定的 \(a\in \mathbb{F}^*\), 当 \(b\) 是一个随机数时, \(\mathbb{F}^*\) 中的 \(a b\) 也是一个随机数。因此,即便 Alice 作弊,即便她没有随机的选择参数 \(a\) ,比如她每次都只选择 \(a=4\), 但 \(s\) 依然会是随机数。同样的情况发生在 Bob 意图选用非随机数 \(b\) 进行作弊的场景中。

只要他们中的一个正确的遵循了协议,\(M=s\cdot g\) 的格式就会是正确的。

现在让我们来使用相似的方法生成 \((s\cdot g, s^2\cdot g)\):

  1. Alice 选择一个随机的 \(a\in \mathbb{F}^*,\) ,并且发送 \((A,B)\) 。其中 \(A:= a\cdot g\) and \(B := a^2\cdot g.\)。#. Bob 选择一个随机的 \(b\in \mathbb{F}^*,\) 并且发送 \(M=(b\cdot A, b^2\cdot B).\)
  2. 如果 Alice 和 Bob 都遵循协议,我们将得到 \(M= (b a \cdot g, b^2 a^2 \cdot g) = ( a b\cdot g, (a b)^2\cdot g).\) 。因此,这个向量是正确形式的 \(s:= ab.\)

现在有一个问题: 如果 Bob 作弊,将 \(B\) 乘以 \(c\neq b^2\)? 后进行计算,我们将得到 \((ab\cdot g, a^2 c \cdot g),\) ,此时就得不到任何以 \(s.\) 形式表示的 \((s\cdot g, s^2\cdot g)\) 。我们需要对输出向量 is\(s.\) 形式表示的 \((s\cdot g, s^2\cdot g)\) 进行检查。 在很多情况下,这些推测是有害于效率的,这就是通常所说的方形决策的 Diffie-Hellman 假设。 然而,在我们的配置中,我们面对的是双线性配对的一组对象。 这里有一份地图, \(e:G\times G\to G_T,\) 。这份地图是关于 \(G_T\) 的,同时包括 \(r\) 阶信号发生器 \(\mathbf{g}\) 。这个发生器被用乘法写出,形式为

\(e(a\cdot g, b\cdot g) = \mathbf{g}^{ab}\)

对于任意的 \(a,b\in\mathbb{F}.\),以上描述都给了我们检测输出值 \(M\) 是否格式正确的方法。

\(e(g,B) = e(A,A).\)

让我们假设如果没有人作弊,这个检测会顺利通过。 当没有人作弊时,我们将得到 \(A=s\cdot g,\)\(B=s^2\cdot g.\) 因此

\(e(g,B) = e(g,s^2\cdot g) =\mathbf{g}^{s^2}\),

同时

\(e(A,A) = e(s\cdot g,s\cdot g) = \mathbf{g}^{s^2}.\)

可以使用一个简单的计算来检测当 \(M\) 的格式不正确时,这两个数的值将不同,检测会失败。

如何使用 \(\mathsf{pubkey}\)

请先回忆一下一个含有 \(d\)\(\mathbb{F}\)多项式 \(P\) 有如下形式

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

我们在 评价 一个多项式时,可以使用 \(s\in \mathbb{F}\)\(s\) 替换为 \(X,\) 并计算结式和。 一个有用的事实是,如果 \(P\)\(Q\) 是有最高阶 \(d\) 的不同多项式,他们在 \(d\) 这项上的相似度会很高。 在 Zcash 中,发送方需要以一种特定的方式,建立包含2阶 \(d\) 的多项式 \(P\)\(Q\) 。很多数学的方法保证了他们可以成为相似或想通的多项式。比如:得到 \(P=Q,\) ,仅需要交易是真实的。

\(\mathsf{pubkey}\) can now be used to test if \(P\)\(Q\) are equal at a point \(s\) not known by the sender. Say

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

\(Q(X) = b_0 + b_1\cdot X + b_2\cdot X^2 + \ldots + b_d\cdot X^d\)

使用 \(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g),\) ,验证器可以计算

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

和 compute \(Q(s)\cdot g\) similarly. The verifier can then check if they are equal.

Since the sender of a non-valid transaction has to construct distinct \(P\)\(Q\) without knowing \(s,\) the chance that \(P(s)=Q(s)\) is very small.

免责声明

请注意,这篇博文是基础协议的显著简化版。一份详细的说明将会在日后的白皮书中呈现。

References

Our zkSNARKS use SCIPR Lab's implementation of the Pinnochio protocol, which in turn is based on the work of Gennaro, Gentry, Parno 和 Raykova. Our protocol for parameter generation builds on a previous work of Ben-Sasson, Chiesa, Green, Tromer 和 Virza.