零知识证明详解七——椭圆曲线配对
本文翻译自zcash官方博客，讲解zcash中所使用的zk-SNARKs的原理第七部分，也是最后一部分，此处是原文链接。友情提示：本文偏技术化，适合对技术和数学非常感兴趣的同学阅读。
zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的简称，意思是：简洁的非交互的零知识证明
(本文授权BH好文好报群摘编、转载以及相关转授权推文行为)
在第六章中，我们见到了zk-SNARK一个皮诺曹协议的概述。我们目前还差两个东西——一个支持加法和乘法的同态隐藏，这是验证者校验所必须的东西；以及一个从交互式协议向非交互式证明系统的转换。
在本章中，我们将使用椭圆曲线来实现一个支持乘法的同态隐藏函数(HH)，虽然这个HH有一定的限制，不过足够满足我们的要求。我们还将会看到这个受限的HH也完全可以把我们的交互式协议转化为我们想要的非交互式系统。
我开始介绍椭圆曲线了，并解释它们是怎么给出我们的HH的。
椭圆曲线及其配对
假设p是一个大于3的质数，并选择某个u, v \in \mathbb{F}_p，满足4u^3 + 27 v^2 \neq 0。我们看一下这个方程：
Y^2 = X^3 + u*X + v
一个椭圆曲线C就是满足这样一个方程的点(x, y)的集合。这种曲线有一种非常有趣的方法来构造群。群里的元素是在曲线上的点(x, y) \in \mathbb{F}_p^2。也就是这些点都满足上面这个方程。另外还有一个特别的点\Omega也属于这个群，这个纯粹是技术上的需要，我们把它定义为"无限远的一个点"，它是这个群的零元。
现在的问题是，如何把两个点P = (x_1, y_1)和Q = (x_2, y_2)相加得到第三个点？加法规则来源于一个抽象的概念，它被称作曲线的"除数类群"。为了我们的目的，关于"除数类群"你只需要知道它给加法的定义增加了如下限制：任何线上的点相加都是0， 也就是\Omega。
我们来看看这个加法规则是怎么从这个限制衍生出来的。我们先来看一条垂直的线，它的方程是这样的：X= c。假设这条线与曲线相交于一个P = (x_1, y_1)点。因为这个曲线的方程是这种形式的：Y^2 = f(X)，所以如果(x_1, y_1)在曲线上，那么点Q := (x_1, -y_1)也在这条曲线上。另外，因为这个这是一条垂直线并且曲线方程中Y是二阶的，那么我们可以确定，除这两个点外，它们之间没有其他的交点了。
ex1.png
因此，我们必定有P + Q = \Omega，也就是说 P = -Q；换言之，在这个群里，Q是P的逆元素。
我们再来看看如果点P和Q的横坐标不同，也就是x_1 \neq x_2时，怎样把这两个点相加。我们经过P, Q画一条线。
ex2.png
因为这个曲线方程中X是3次的，同时已经有一个非垂直的直线经过了其中的两个点，那么它必然也会经过曲线中的第三个点，我们把它标记为R = (x, y)。除此三点以外，没有其他交点了。
因此我们必然有P + Q + R = \Omega，也就是说P + Q = -R；我们知道，-R可以通过把R的纵坐标y取反得到-y。
因此，我们就得到了群的加法规则：给定点曲线上的P和Q，并经过它们作一条直线，那么把这条直线与曲线的第三个交点做个镜像，即可得到它们的和。
这个群通常被称作C(\mathbb{F}_p)，因为它由在曲线C上面并且坐标值属于\mathbb{F}_p的点构成；不过我们后面都将使用G_1代表它。为了简单起见，假设G_1里元素的个数是一个质数r，并且不等于p。这种情况非常常见，Zcash现在用的曲线就是。在这种情况下，任何g \in G_1并且不是\Omega的元素都可以产生G_1。
能满足r整除p^k -1的最小整数k，被称为曲线的嵌入度。可以推测，当k不太小的时候，比如说，不小于6，这时G_1的离散对数问题就非常难解，也就是说，通过g和\alpha * g找到\alpha非常困难(Zcash当前使用的BN曲线中, k=12)。
\mathbb{F}_{p^k}的乘法群包含一个r阶子群，我们记作G_T。我们看下曲线上那些坐标值在\mathbb{F}_{p^k}上但是不再{\mathbb{F}_p}上的点。在同样的加法规则下，这些点连同\Omega也构成了一个群，记作C(\mathbb{F}_{p^k})。注意，C(\mathbb{F}_{p^k})完全包含G_1，不仅G_1，C(\mathbb{F}_{p^k})也包含一个r阶的加法子群G_2(事实上，有r-1个r阶加法子群)
给定生成器g \in G_1, h \in G_2，你会发现一个高效的map，称为Tate简化配对:接收G_1和G_2中的一对元素，生成G_T的一个元素。
就像这样：
- Tate(g, h) = g, g是G_T的一个生成元，并且
- 给定一组元素a, b \in \mathbb{F}_r，我们就得到了Tate(a*g, b*h) = g^{ab}
定义Tate有点超过本系列的范围，它依赖于代数几何的概念。这里是Tate的概要定义：
对于a \in \mathbb{F}_p，多项式(X - a)^r在点a处为0， 并且没有其他的点使得它为0。对于一个点P \in G_1，除数可以使我们证明存在一个从曲线到\mathbb{F}_p的函数f_p，同时，该函数在P点的值也为0，并且没有其他的零点了。所以 Tate(P, Q)可以定义为：f_P(Q)^{(p^k - 1)/r}
可能这个定义和乘法同态和加法同态没有太大关系，的确要证明Tate具有这些特性是比较复杂的。
定义E_1(x) := x*g, E_2(x) : = x*h, E(x) := x * g，我们得到了一个弱版本的HH，它支持加法和乘法： E_1, E_2, E都是支持加法的HH, 给定隐藏数E_1(x), E_2(y)，我们可以计算出E(xy)。 换句话说，如果我们有x 和y的隐藏数，我们就可以计算出xy的隐藏数。不过，如果我们有x, y, z的隐藏数，我们无法得到xyz。
我们开始继续前行，开始讨论非交互式的证明系统。我们先从“什么是非交互式”开始。
公共引用串模式的非交互式证明
对于“非交互”最强烈和最直观的感受可能是这样的，为了证明某个声明，证明者向所有人广播一条消息，在此之前，没有任何人有过任何形式的交流；然后任何收到这个消息的人都会相信证明者的声明。在多数情况下，这可以认为是不可能的。
一个稍微宽松的非交互证明的概念是允许一个公共引用串(CRS)。在这个CRS模式中，在任何证明被构造以前，有一个安装阶段，这个阶段中，一个串根据某种随机过程构造出来，并且广播给所有的当事人。这个串被称作CRS，可以用于构造和检验证明。这里的前提是，这个构造CRS的随机过程是任何人都不知道的——因为知道了这个随机过程，就可以构造假证明了。
我们下面将解：在CRS模型下，我们如何把第四章里可验证的盲式计算协议转化为一个非交互式系统。第六章包含了一些类似的子协议，所以他们也可以用类似的方法转化为 非交互式证明系统。
一个非交互式计算协议
这个非交互式的计算协议中，基本上包含了把Bob的第一条消息公布为CRS。回忆一下，这个协议的目的是为了获取Alice的多项式P在随机选择的s \in F_r点上隐藏数E(P(s))。
安装阶段：随机选择\alpha \in \mathbb{F}_r^*, s \in \mathbb{F}_r，以及公布CRS：
(E_1(1), E_1(s), ..., E_1(s^d), E_2(\alpha), E_2(\alpha s), ..., E_2(\alpha s^d))。
证明：Alice通过使用CRS里的元素计算出a = E_1(P(s)) 和b = E_2(\alpha P(s))，事实上， E_1和E_2都支持线性组合。
验证: 找到x, y \in \mathbb{F}_r，使它满足a = E_1(x)和b = E_2(y)。Bob计算出E(\alpha x) = Tate(E_1(x), E_2(\alpha)) 以及 E(y) = Tate(E_1(1), E_2(y))， 然后检查它们是否相等，如果相等，说明\alpha x = y
正如第四章说明的，Alice只能通过它知道的多项式P及其阶次d，计算出P(s)的隐藏数a，她由此构造的a, b才能通过Bob的验证。这里的主要区别是，Bob在验证的时候不需要知道\alpha，因为他可以通过配对函数从E_1(x)和E_2(\alpha)计算出E(\alpha x)。因此，他不需要构造并发送他的第一个消息，这个消息可以简单地固定在CRS中。
译者注：zcash的这篇关于椭圆曲线讲解的比较粗糙，有点云雾缭绕，V神有篇文章对椭圆曲线和Tate函数做了更深入一点的讲解，下次我把V神的这篇文章也翻译一下
早赞声明：为方便早赞、避免乱赞，“BH好文好报群”为点赞者、写作者牵线搭桥，实行“先审后赞、定时发表”的规则，也让作品脱颖而出、速登热门！加群微信：we01230123（天平）。
