1. 主页
  2. 文档
  3. zk-SNARKS验证教程
  4. 椭圆曲线配对

椭圆曲线配对

添加“零知识”以掩藏赋值

在先前的系列文章中,Alice 为了在 zk-SNARK 中掩藏赋值信息,而 E(L(s)),E(R(s)),E(O(s)),E(H(s)) 会提供赋值的相关信息。

举个例子,在给定某些满足条件的赋值$(c’_1,…,c’_m)$ 的情况下, Bob 可以计算出对应的 L’,R’,O’,H’ ,以及其对应的同态隐藏 E(L'(s)),E(R'(s)),E(O'(s)),E(H'(s))。如果这些信息与 Alice 的不同,那么可由此推断,$(c’_1,…,c’_m)$不是 Alice 的赋值。

为避免此类信息泄露,Alice 可通过对每个多项式进行“随机 T 转换” 以掩藏赋值信息,即 Alice 从域 $\mathbb{F}_p^*$ 中随机选择$\xi_1,\xi_2,\xi_3,并给出如下定义:

$L_z:=L+\xi_1*T,R_z:=R+\xi_2*T,O_z:=O+\xi_3*T$

假设 L,R,O 由满足条件的赋值生成,因此其满足等式:
$L*R-O=T*H$,

以下是 T 整除$L_z*R_z-O_z$ 的证明过程:
$L_z*R_z-O_z=(L+\xi_1*T)(R+\xi_2*T)-O-\xi_3*T=
(L*R-O)+L*\xi_2*T+\xi_1*T*R+\xi_1\xi_2*T^2-\xi_3*T=T*(H+L*\xi_2+\xi_1*R+\xi_1\xi_2*T-\xi_3)$

因此,基于定义$H_z=H+L*\xi_2+\xi_1*R+\xi_1\xi_2*T-\xi_3$
可得 $L_z*R_z-O_z=T*H_z$
因此,如果 Alice 使用多项式 $L_z,R_z,O_z,H_z$, Bob 总是会接受。

从另一个角度来说,多项式在 s 点没有披露赋值的相关信息,其中 $T(s)\neq 0$。

举个例子,因为 T(s) 是非零的,并且$\xi_1$随机,$\xi_1T(s)$也是随机值,因此 $L_z(s)=L(s)+\xi*T(s)$不会披露任何信息。

这是第二个问题的解决方案,接下来是第三个问题。即构建支持乘法操作的同态隐藏,以在知晓 E(H(s))和 E(T(s))的基础上计算 E(H(s)*T(s)) ,在这之前仅仅介绍了加法操作和线性组合,先从椭圆曲线开始,阐述如何构造所需的同态隐藏(HH).

椭圆曲线及其配对

假设 p 为大于 3 的素数,并且取域 $\mathbb{F}_p$ 上的两个值 u,v ,使得 $4u^3+27v^2\neq0$
再构造这样一个等式:
$Y^2=X^3+u*X+v$

椭圆曲线$C$是满足上述等式的点集(x,y),这提供一个有趣的构建“群”的方式,“群”的元素$(x,y)\in\mathbb{F}_p^2$;
其中特殊点$O$,是群中的零点。

下面是从约束中导出加法规则的过程:

假设存在一条直线 $X=c$ ,与曲线的交点是$P=(x_1,y_1)$,曲线方程是$Y^2=f(X)$,那么如果点$(x_1,y_1)$在曲线上,点 $Q:=(x_1,-y_1)$ 也会在曲线上,椭圆方程的最高阶数为 2 ,所以可以确定的是垂线与曲线的相交处为几个点。

因此可得 $P+Q=O$,即$P=-Q$,也就是在群中 Q 是 P 的逆元。

假设现在 P 和 Q 的横坐标是不同的,那么如何对这两个点进行相加呢?

首先过 P 和 Q 作一条直线,因为曲线方程是三次多项式,并且与该直线(非垂线)相交于两个点,那么势必会相交于第三个点,设为 R(x,y);

由此可得$P+Q+R=O$,即$P+Q=-R$,而 $-R$由R的纵坐标取负得到。

基于此导出了群的加法规则:给定点P和Q,过两点做一条直线,取直线与曲线相交的第三点的镜像作为加法结果。

这个群通常被称作$C(\mathbb{F}_p)$,接下来用$G_1$来代替它。

简单起见,假设$G_1$中的元素个数是素数r,与之前的素数 p 是不同的。满足r整除$p^k-1$的最小整数k是椭圆曲线的嵌入度,其中k至少是6,那么群G1中的离散对数问题,即基于$g$和$\alpha*g$找到$\alpha$是困难的,在 Zcash 里所用到的 k 为12.

在域$\mathbb{F}_{p^k}$中的乘法群包含了 r 阶子群,设为$G_T$。

在类似的加法规则下,$\mathbb{F}_{p^k}$ 上的曲线点与零点$O$ 一起组成群$C(\mathbb{F}_{p^k})$ ,显而易见的是它包含群$G_1$,与此同时它还包含 r 阶子群$G_2$。

存在一个叫做 Tate reduced pairings 的高效映射,基于$g\in G_1,h\in G_2$,通过接收$G_1,G_2$ 中的元素以生成$G_T$元素 :

  1. Tate(g,h)=g
  2. 给定$a,b\in \mathbb{F}_r$ ,可得 Tate(a*g,b*h) =$g^{ab}$

这里不对 Tate 作过多的阐述,接下来的文章会阐述 CRS 模型中的非交互式证明。

我们要如何帮助您?