椭圆曲线配对(进阶)

**添加“零知识”以掩藏赋值**
在先前的系列文章中，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 模型中的非交互式证明。