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

<< 第 6 部分

在第六部分中,我们看到了匹诺曹 zk-SNARK 的概述 。但我们忽略了两件事情 - 验证器检查需要一个支持加法和乘法的HH,以及从交互式协议到非交互式证明机制的转换 。

在这篇文章中,我们将看到,通过椭圆曲线我们可以得到一个受限,这个受限可以满足我们的目的,得到一个支持乘法的 HH形式。然后,我们会证明这个有限的 HH 足以把我们的协议转换成期望的非交互式机制。

我们从介绍椭圆曲线开始,再解释它如何给我们必要的 HH。

椭圆曲线和它们的配对

假设 \(p\) 是一个大于 3 的质数,取 \(u,v\in\mathbb{F}_p\) 使得 \(4u^3+27v^2\neq 0\) 。我们来看这个方程

\(Y^2=X^3 +u\cdot X +v\)

一条椭圆曲线 \({\mathcal C}\) 是满足特定方程的所有点 \((x,y)\) [1] 的集合。 这些曲线给我们一种很有趣的方式建群。 群元素是在曲线上的点 \((x,y)\in \mathbb{F}^2_p\),例如,有一个特殊的点 \({\mathcal O}\) 满足这个等式,由于技术原因,有时候它被称为“无穷远点”,并且被看做单位元素,例如,群里面的 0 。

现在的问题是,我们如何添加两个点 \(P=(x_1,y_1),Q=(x_2,y_2)\) 得到第三个点? 这个加法规则是从一个有点儿抽象的对象中派生出来的,这个对象叫做曲线的除子类群。 它的加法定义有以下约束条件: 任何线上的点加起来必须为 0 ,例如, \({\mathcal O}\)

让我们看看由这个约束条件如何推导出这个规则。 看这条由方程 \(X=c\) 定义的垂线。假设这条线与曲线相交于点 \(P=(x_1,y_1)\) 。 因为这条曲线方程的形式是 \(Y^2=f(X)\) ,如果 \((x_1,y_1)\) 在曲线上,那么点 \(Q:=(x_1,-y_1)\) 也在曲线上。 而且,因为这是一条垂线并且曲线是关于 \(Y\) 平方的方程, 我们可以确定这是垂线和曲线相交的唯一两个点。

Test |P+Q=O --> P=-Q|

因此,必有 \(P+Q={\mathcal O}\) ,意味着 \(P=-Q\);也就是说在群里,\(Q\)\(P\) 的相反数。

现在让我们来看下有着不同第一坐标的点 \(P\)\(Q\) - 也就是 \(x_1\neq x_2\) , 然后再看如何添加他们。 我们过 \(P\)\(Q\) 做一条直线。

Test |P+Q=O --> P=-Q|

因为这条曲线是由 \(X\) 的三次多项式定义的,并且已经和这条线(非垂直的)相交于两个点, 因此它必和这条直线相交于第三个点 \(R=(x,y)\) ,并且没有其他的交点。

所以必有 \(P+Q+R={\mathcal O}\) ,这意味着 \(P+Q=-R\) 。 所以到现在为止我们知道 \(-R\) 是通过 \(R\) 翻转第二坐标 \(y\)\(-y\) 所得。

因此,我们为这个群派生了加法规则: 给定点 \(P\)\(Q\) ,做一条通过它们的直线, 取这条线与曲线的第三个交点的“镜像”点作为加法的结果。 [2]

这个群通常叫做 \({\mathcal C}(\mathbb{F}_p)\) - 因为它由曲线 \({\mathcal C}\) 上的点组成,这些点包含的坐标元素属于有限域 \(\mathbb{F}_p\) ; 现在,让我们用 \(G_1\) 来表示这个群。 简单假设 \(G_1\) 里元素的数量是质数 \(r\) , 并且 \(r\) 不同于 \(p\)。 这是经常出现的情况,例如 Zcash 现在正在用的曲线。 在这个例子中,任何 \(G_1\) 中不同于 \({\mathcal O}\) 的元素 \(g\in G_1\)

\(r\) 除以 \(p^k-1\) 的最小整数 \(k\) 叫做 曲线的嵌入度 。我们猜想当 \(k\) 不会太小,假设至少是 6 时,那么, \(G_1\) 的离散对数问题,例如已知 \(g\)\(\alpha \cdot g\) ,得出 \(\alpha\) ,是极其困难的。(在 BN 曲线上 [3] ,当前 Zcash 用的是 \(k=12\) 。)

\(\mathbb{F}_{p^k}\) 的乘法群包含一个 \(r\) 阶子群,我们将其称之为 \(G_T\) 。 我们可以用在 \(\mathbb{F}_{p^k}\) 中且不仅仅在 \(\mathbb{F}_p\) 上的坐标来观察曲线点。 在同样的加法规则下,这些点也组成一个群,与 \({\mathcal O}\) 统称为 \({\mathcal C}(\mathbb{F}_{p^k})\) 。 注意 \({\mathcal C}(\mathbb{F}_{p^k})\) 明显包含 \(G_1\) 。除了 \(G_1\)\({\mathcal C}(\mathbb{F}_{p^k})\) 还会包含另一个 \(r\) 阶加法子群 \(G_2\) (事实上,\(r-1\)\(r\) 阶加法子群)。

固定生成元 \(g\in G_1,h\in G_2\) 。 结果存在一个有效映射,叫做 Tate 可约化配对, 可以从 \(G_1\)\(G_2\) 中取一对元素变成 \(G_T\) 的一个元素,

这样

1,\(\mathrm{Tate}(g,h)=\mathbf{g}\)\(G_T\) 的生成元,并且 2,给定一对元素 \(a,b \in \mathbb{F}_r\) ,可得 \(\mathrm{Tate}(a\cdot g,b\cdot h)=\mathbf{g}^{ab}\)

\(\mathrm{Tate}\) 的定义有点超出这个系列的范围, 并且依赖代数几何的概念,最显著的是 divisors 。 这是 \(\mathrm{Tate}\) 的定义:[4]

对于 \(a\in\mathbb{F}_p\) ,多项式 \((X-a)^r\) 在点 \(a\) 上有 \(r\) 阶零点并且没有其他零点。 对于点 \(P\in G_1\) , 我们可以证明存在一个从曲线到 \(\mathbb{F}_p\) 的函数 \(f_P\) , 并且存在 \(P\) 上的 \(r\) 阶零点且没有其他零点。 这样 \(\mathrm{Tate}(P,Q)\) 被定义为 \(f_P(Q)^{(p^k-1)/r}\)

这个定义和所声明的属性间的关系并不清晰, 确实,证明 \(\mathrm{Tate}\) 拥有这些属性是相当复杂的。 定义 \(E_1(x) := x\cdot g, E_2(x):=x\cdot h, E(x):=x\cdot \mathbf{g}\) ,我们得到一个支持加法和乘法的弱版本 HH 。\(E_1,E_2,E\) 都是支持加法的HH,给定隐匿的 \(E_1(x)\), \(E_2(y)\) ,我们可以计算出 E|E(xy)| 。换言之,如果我们有“正确”的隐匿 \(x\)\(y\) 我们可以得到一个 ( 不同的 ) 隐匿 \(xy\) 但是,如果我们有隐匿的 \(x,y,z\) ,我们不能得到隐匿 \(xyz\)

我们继续探讨非交互式证明机制。首先,我们先解释到底什么是“非交互式”。

在公共参考串模型中的非交互式证明

以下可能是非交互式证明最有力最直观的概念了。 为了证明一个准确无误的证词,一个证人广播了一消息给所有的当事人, 没有任何形式的优先通讯,任何人读到这条消息都会相信这个证人的证词。 在大多数情况下,这基本是不可能的。[5]

非交互证明的一个有点不严格的概念就是允许公共参考串 ( CRS ) 。 在 CRS 模型里,建立任何证明前,有一个准备阶段,在这个阶段里,会根据一个确定的随机过程建立一个串并且广播给给所有当事人。 这个串叫做 CRS ,用于帮助建立和验证证明。人们的假设是用于创建 CRS 的随机性不被任何一方所知 – 因为这个随机性也许能成为伪声明的证据。

我们会解释在 CRS 模型里,如何把 第四部分 提到的可验证的盲评估协议转换成一种非交互式证明机制。 因为第六部分中的协议包含了一些这样的子协议,它可以通过类似的方式变成一个非交互式证明机制。

非交互式评估协议

评估协议的非交互式版本主要包括将 Bob 的第一条消息发布为 CRS 。回想一下,这个协议的目的是为了在随机选择 \(s\in\mathbb{F}_r\) 中获得 Alice 的多项式 \(P\) 的隐匿 \(E(P(s))\)

搭建:随机选择 \(\alpha\in \mathbb{F}_r^*,s\in\mathbb{F}_r\) , 发布 CRS:
\((E_1(1),E_1(s),\ldots,E_1(s^d),\) \(E_2(\alpha),E_2(\alpha s),\ldots,E_2(\alpha s^d))\)

证明: Alice用 CRS 的元素和 \(E_1\)\(E_2\) 支持线性组合 的事实计算 \(a=E_1(P(s))\)\(b=E_2(\alpha P(S))\)

Verification: Fix the \(x,y\in \mathbb{F}_r\) 这样 \(a=E_1(x)\) and \(b=E_2(y)\). Bob computes \(E(\alpha x)=\mathrm{Tate}(E_1(x),E_2(\alpha))\) and \(E(y)=\mathrm{Tate}(E_1(1),E_2(y))\), and checks that they are equal. (If they are equal it implies \(\alpha x =y\).)

就像在第四部分中解释的那样,如果 \(a\) 是对 Alice 已知的 \(P(s)\) 阶多项式 \(P\) 的隐匿 , Alice只能建立会传递校验检查的 \(a,b\) 。 这里最主要的区别在于,为了校验检查, Bob 不需要知道 \(\alpha\) ,因为他可以只通过 \(E_1(x)\)\(E_2(\alpha)\) ,用配对函数计算 \(E(\alpha x)\) 。 这样,他不需要亲自构建和发送第一条消息,这条消息可以简单的固定在 CRS 中。

[1]你也许会问:这些点来自哪里?。我们指的是坐标在 𝔽p 的代数闭包上的点集。而且,这条曲线有仿射和投射两个版本。当我们指投射版本时,通常包括“无穷远点” \({\mathcal O}\) 作为曲线上的一个元素。
[2]我们没有提到将 \(P\) 添加到自身的情况。这是通过一条与曲线相切于 \(P\) 的直线,取 \(R\) 为这条直线与曲线的第二个交点做到的。
[3]https://eprint.iacr.org/2005/133.pdf
[4]Zcash 真正使用的是 最佳 Ate 配对,这建立在 Tate 可约化配对的基础上,而且可以比 \(\mathrm{Tate}\) 更高效的计算出来。
[5]在计算复杂度理论中,我们可以证明只有 BPP 上的语言有非交互性零知识证明。在 Zcash 交易中,我们需要证明的声明类型,例如,“我知道这个串的哈希图像”, 与被认为比 BPP大得多的复杂度类别 NP 相对应。
[6]所用的图片取自接下来的 文章,并在 知识共享许可协议 下使用。

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