语种

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.