前言
上一篇我们介绍了zkSNARK的基本原理，多项式是一种很好的证明媒介，但要做到简洁的零知识证明，还需要借助椭圆曲线一些有趣的性质。在介绍具体如何优化之前，本篇让我们先了解一下什么是椭圆曲线以及如何在椭圆曲线上做加密。
本篇提纲
1. 基本概念-群和域
2. 非对称加密基础-离散对数难题
3. 密码学进阶-椭圆曲线
4. 一个神奇的函数-双线性映射函数
5. 总结
1. 基本概念 – 群和域
在学习椭圆曲线之前，我们先了解一下简单的数论概念。介绍这些数学概念本应严谨精确地定义，但数学上的定义理解起来多少有点抽象，所以本篇介绍的相关定义都比较简单直白，提高可读性，要进一步研究的话建议大家自行查阅这些概念标准的定义。
群和域都是数的集合+运算规则，它们对运算的性质要求不一样，但都需要保证运算的结果依然在集合内。而我们要讨论的加密或者椭圆曲线，就是在这样的集合中符合该运算规则的一系列计算。所以我们先来了解，什么样的集合适合做密码学计算。
1.1有限域
计算机能处理的数的大小和精度都是有限的，而密码学用到的数很多都是需要随机选取，并且计算机能够正常计算，那么我们需要在一个有限的集合来做这件事。比如整数集合0,1,2,3,…，通过对一个数取模（求余数）可以得到一个有限整数集合：
可以看出，对不同的整数取模可以得到不同大小的集合，这样的集合是有限的。如果这样有限的集合上面还有一种运算，运算的结果也在这个集合内，我们就可以放心的让计算机去做计算。
比如对7取模后的得到的集合，定义两种运算：加法和乘法，运算的结果也要取模，有2*6=5，4*5=6。这样构造出来的有限的集合和集合上的两种运算一起被称为有限域。这里说的有限域都是整数集合，只定义了整数运算，没有浮点数，也给我们提供了较好的计算条件，但是这里计算的结果还是有规律的，不适合用来加密，做加密还需要进一步构造循环群。
举个例子：已知2*6=5，求4*6。这里知道4=2*2，直接2*(2*6)=2*5=3(mod7)。
接下来让我们看看在循环群上做同样的计算有多困难。
1.2 循环群
我们首先看看效果，在有限域随机选择一个数（生成元），比如模11的有限域F11，选择一个生成元2，一直做乘法（乘多次即指数）得到一个循环群，注意这里还是有限域内的计算，结果是取了模之后的：
可以看出计算的结果还是在0-11之间，但是不断累积后得到的结果却是离散的，即我们计算出23=8，但是不能直接通过23得出26=9，还是要计算24、25、26，不像上面那样可以走捷径了。这里如果继续计算210=20=1,211=21=2，即再往后计算得到的结果是循环重复的，同时这个集合只有一种运算（这里是乘法），这样的集合称为循环群。
02 非对称加密基础-离散对数问题
基于循环群结果离散的性质，我们可以构造一个难题用来做非对称加密：在循环群中，对于g^x=h，如果知道底数g和结果h，无法直接计算得到指数x是多少。
这里我们称其为离散对数难题，无法直接计算指的是计算机在有限时间内很难算出来。上面F11构造的循环群还很小，可以通过穷举法列举出所有结果。但当模的数取的足够大时，知道底数和结果，很难得到指数。因为如果指数是100000，就要计算差不多99999次运算。这样的假设帮助我们实现了很多非对称加密算法，比如RSA。
整数的离散对数难题已经足够支持我们设计很多经过验证的安全算法，试想有一种曲线，曲线点的横坐标在有限域取值，这样得到一个类似有限域的点集，点与点之间也定义一种运算，然后也能构造一个循环群，但是这样计算结果更加离散，于是我们只需要更小的数就能保证更大的安全性（结果离散程度越高就越不容易快速计算）。相对整数上构造的循环群有更多的特性和更大的发展前景。
03 密码学进阶-椭圆曲线
椭圆曲线在平面上的方程和对应的图像如下所示：
正如上面提到的，椭圆曲线的优势在于，在这样的曲线上定义一种运算后，能够构成一个更加离散的循环群，这里需要提一下，群的定义要求上面的运算要满足结合律。所以核心的问题是如何构造这样一种满足结合律的点的运算规则，进而构造可以用来椭圆曲线加密的群。
我们定义的运算规则如下，可以叫它椭圆曲线上的加法（也可以叫乘法，只是一个名称）：
对于点P和Q，有运算P+Q=R’，在图像上就是PQ连线交曲线于一点R，由R做x轴垂直线交曲线于一点R’，R’就是P+Q的结果。
这里我们不用深究为什么这样定义加法，只需要知道这里定义的加法和整数上的加法、乘法都满足结合律，因此我们可以通过这样的运算在有限域上的椭圆曲线定义一个循环群。
椭圆曲线方程为Y^2=X^3+3X+8，有限域选择F13，即x取值为模13的结果[0,12]，注意这里限制了横坐标x和纵坐标y都是0-12的整数，所以
当x=0，y^2=8时，y不是整数，无解；
当x=1，y^2=12(mod13)，有5^2[mod13]=12、8^2[mod13]=12，所以存在点(1,5) (1,8)。
这样对方程求解可以得到方程F13所有点解，因为椭圆曲线上的运算比较复杂，下面列出所有点之间的运算结果：
还记得上面我们在整数上是如何构建循环群的吗？选一个生成元，然后对自身不断的进行乘法，得到一个结果离散的循环群。
从上图可以看出，选择一个点不断对自身做加法，能得到一组离散的点。比如计算(1,5)^4只能一步一步来，先计算(1,5)^2=(2,10)，(1,5)^3=(1,5)(2,10)=(9,7)，(1,5)^4=(9,7)(1,5)=(12,2)。
因此只要选的有限域足够大，我们就可以基于这个循环群构造椭圆曲线上的离散对数难题。即对于点g^x=h知道底数点g和结果h，是很难直接得到x的。
04 一个神奇的函数 – 双线性映射函数
设G1、G2和Gt是三个椭圆曲线上的循环群，一般Gt>G2>G1（这里说的大小是指在循环群里数的取值范围）。实际上这里有扩域的概念，我们只需要知道这是三个椭圆曲线上的群，实际应用时发现G2的点坐标会比G1大，这是正常的。双线性映射函数e如下：
我们用到的基本就是上面这个性质。双线性映射函数神奇的地方在于，它是乘法同态的。什么是加法同态和乘法同态？
回忆一下上面讲的离散对数难题，在整数的循环群中，可以通过加法同态进行下述隐私计算：
· a、b是用户的隐私数据，需要服务器资源计算g^(a+b),于是用户发给服务器h1=g^a,h2=g^b,g
· 离散对数难题保证了服务器知道h1,h2,g的情况下，无法计算出a和b的值
· 服务器利用加法同态可以计算g^a * g^b = g^(a+b)，返回结果
但是如果用户需要的是(g^ab)*d的值呢？一般来说乘法同态应用场景更多，如果有一种函数可以满足乘法同态就能帮我们解决很多问题，显然上面双线性配对函数的性质就满足乘法同态，这里不再赘述，这也是椭圆曲线在零知识证明中大显身手的主要原因。具体我们将在本系列的下一篇文章中详细讲解。
05 总结
这一篇我们简单介绍了一般的加密基础和椭圆曲线的基本原理，引出了零知识证明中很重要的双线性配对函数，主要为方便我们后面更深入理解零知识证明。现在我们已经做好了基本的知识储备，接下来就可以轻松理解零知识证明了。