我们都知道,在 ZK-SNARKs 中我们整合了许多工具,从而一步步达到了我们想要的目的,即零知识和证明。而双线性配对是其中非常重要的一环。为什么这么说呢,下面我们就来介绍一下双线性配对在零知识证明中的意义。
配对的基本概念
配对(Pairing)将输入的两个群成员映射为第三个群的成员,将配对记为e
。
e:
上式左边的群由椭圆曲线上的点构成。
配对必须具备一些代数特征,比如最重要的双线性:
而配对的另一个非常重要的特征就是非退化性:
右边的 1 表示目标群 中的乘法单位元。非退化性保证了只要我们选择椭圆曲线上的非单位成员 G ,就能得到目标群中的非单位元。
双线性配对在零知识证明中的应用
开门见山,最重要的一句话:
配对可以用于验证一个数学过程是否正确执行,配对可以揭示秘密值是通过加法以及最多一次乘法来关联起来的
同样,这也是配对在 ZK-SNARKs 中的用途。假设,存在这样一个二次方程:
为了说服你我的确知道上述方程的一个解,一个办法就是告诉你我所知道的这个解,然后你自己带入上述方程去验证。另一个办法就是我不告诉你这个具体的解是多少,但是使用椭圆曲线上的配进行验证。
首先注意,如果:
那么 k 要么是0,要么是群的阶的倍数,因此如果以下等式成立,我们就可以确定二次方程成立:
此时,我需要说服你我知道当前方程式的解 a ,但是我却不能暴露给你,于是我就利用椭圆曲线的特性,把解 a 作为一个生成元,由此来获得该椭圆曲线上的两个点,即 。我可以把 都给你,但是由于离散对数难的特性,你也无法计算出 a 的值,所以我们就保证了 a 值的秘密性。此时我们就可以使用配对来计算:
根据之前提到的双线性的特性,我们知道上述算式就等于:
如果这个式子等于 1 ,那也就意味着 极有可能等于 0 。
总结一下,对于 zk-SNARKs 来说,椭圆曲线配对被应用在对二阶约束系统系统的检测上,当且仅当满足二阶约束时,系统才会转换为具有特定根的单个大多项式。
最后给大家推荐一下关于配对的入门书籍:
Craig Costello’s Pairings for Beginners:
http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdfThis talk by Dan Boneh:
https://www.youtube.com/watch?v=8WDOpzxpnTE