上一节中介绍了匹诺曹协议的大致框架，不过最后还有两个问题没有解决，一个是支持加法和乘法的同态隐藏，因为验证者需要在验证过程中使用乘法，另一个是从交互式证明转换到非交互式证明，也就是实现zk-SNARKs中的N
本节中会利用椭圆曲线ECC，来实现一个有限的但是可以满足要求的同态隐藏，这个同态隐藏也可以帮助将协议由交互式转换为非交互式的协议
椭圆曲线对
假设$p$是一个大于3的素数，椭圆曲线方程如下
$$ y^2=x^3+ax+b $$
其中$a,b\in F_p$，满足$a^3+27b^2\neq 0$
一个椭圆曲线是一系列的$(x,y)$点集，椭圆曲线提供了一种很好的方式来构建群，群元素$(x,y)\in F^2_p$来自于曲线上的点，此外还有一个特殊的点$O$，称为无穷远点，表示群上的零元
举个例子，如果我们有曲线上的两点$P=(x_1,y_1)$和$Q=(x_2,y_2)$，如何得到第三个点，ECC上的加法规则源自于一个称为曲线上的因子类群的抽象概念，出于一些目的，对这个因子类群加以一些限制：任意一条线上的点之和必须为零，也即直线与椭圆曲线相交的点之和必须为$O$，接下来举个例子
以上面这个图为例子，比如说有一条直线$x=c$，假设这个直线与椭圆曲线相交于两个点$P=(x_1,y_1)$和$Q=(x_1,-y_1)$，因为曲线方程为$y^2=x^3+ax+b$，不难得出曲线与直线仅相交于这两个点，因此可以得到$P+Q=O$，也即$P=-Q$，P和Q互为群上的逆元
然后再看另一个例子，也就是下面这个图
在上一个例子中，$P$和$Q$有相同的横坐标，假设$P$和$Q$的横坐标不相等，也即$x_1\neq x_2$，不难看出他们的纵坐标$y_1\neq y_2$，此时连接$PQ$并延长，交曲线于第三点$R(x_3,y_3)$，根据之前的定义，直线上的点之和为零，因此有$P+Q+R=O$，也即$P+Q=-R$，从而得到了曲线上群加法如下
- ECC上的加法：给定ECC上两点$P$和$Q$，连接并延长$PQ$，交ECC于第三点$R$，取该点关于$x$轴的对称点作为ECC上点加法的结果
记这个曲线上的点构成的群为$C(F_p)$，表示其是由坐标在$F_{p}$中的曲线C上的点构成的，这里给他换个名字，暂且记为$G_1$，假设$G_1$中元素的个数为一个素数$r$，也即$|G_1|=r$，且$r\neq p$，此时群里有一个生成元$g\in G_1,g\neq O$，可以生成群内所有的非零元
接下来定义嵌入阶
- 嵌入阶：使得$p^k-1$能被r整除的最小整数$k$称为曲线的嵌入阶
当$k$不太小的时候，$G_1$上的离散对数问题将会是困难的（Zcash的BN曲线采用$k=12$）
乘法群$F_{p^k}$包含了一个阶位r的子群，记为$G_T$，此时可以观察那些坐标不仅在$F_{p}$上，还可能在$F_{p^k}$上的曲线上的点，根据相同的加法法则，这些点和零点$O$也构成一个群，不难看出群$C(F_{p^k})$包含了群$G_1$，除了群$G_1$以外，还包含了一个额外的$r$阶子群$G_2$（实际上包含了$r-1$个$r$阶子群，这里只讨论一个）
之前提到了$G_1$中的生成元为$g$，设$G_2$中的生成元为$h$，此时可以得到一个高效的映射，称为Tate归约配对（Tate Reduced Pairing）$[11]$，他将一对$G_1$和$G_2$中的元素映射到$G_T$中，满足
- $e=Tate(g,h)$是$G_T$中的生成元
- 对于给定的元素$a,b\in F_r$，有$Tate(a\cdot g,b\cdot h)=e^{ab}$
Tate归约配对比较复杂，详细的内容这里不再展开，简要描述一下Tate的定义
对于$a\in F_p$，多项式$(X-a)^r$在点a处的值为$0^r$，在其余的点处均不为0，因此对于一个点Pin G_1，利用因子可以证明存在一个从曲线映射到$F_p$的函数$f_P$，同样满足这个特性，也即函数在点P的位置的值为，其余位置均不为0，因此Tate(P,Q)的定义为
$$ Tate(P,Q)=f_P(Q)^{(p^k-1)/r} $$
Tate的特性比较复杂，这里不再赘述，回到之前的问题
定义$E_1(x)=x\cdot g,E_2(x)=x\cdot h,E(x)=x\cdot e$，从而我们可以得到一个支持加法和乘法的同态隐藏的简单版本，对于给定的$E_1(x),E_2(y)$，我们可以计算$E(xy)$，换句话说，如果我们有$x$和$y$的隐藏，不难得出$xy$的隐藏，但是仅适用于二元数对，意思是如果有$x,y,z$的隐藏，这个方法不能得到$xyz$的隐藏
有了这个定义，接下来讨论非交互式证明系统
非交互式证明系统
非交互式证明系统最直观的理解就是，Alice为了证明某一个陈述，她向所有人广播一条消息，且事先Alice与其他人没有任何形式的通信，但是已有研究表明，这种形式的证明只能证明BPP类中的语言，而通常证明过程中人们希望证明NP语言中的问题，且学界普遍认为NP比BPP要大得多，因此需要一种方式来完成这一转化
非交互式证明的一个稍微宽松的概念是允许使用公共引用字符串（Common Reference String，CRS）$[12]$，CRS模型中，所有的参与方会在证明开始之前先构造并公开一个随机串，这个串所有的参与方都可以看见，之后再利用这个串来构造与验证所需要的证明（CRS模型中需要假设任何人都不知道用以创建CRS的随机数，因为倘若某个参与方知道了这个随机数，则其可以利用它对一个错误的陈述构造一个虚假的证明）
接下来就是将第四节中可验证的盲评估协议和第六节中的协议全部组合起来，然后转化为非交互式证明
这个过程首先就是将Bob的第一条消息当作CRS广播出来，回顾一下之前的协议，协议的目的是为了获取Alice在随机点$s\in F_r$上的多项式P的隐藏$E[P(s)]$，具体操作如下
- 初始设置：随机选择$\alpha \in F^*_r,s\in F_r$，令CRS如下
$$ CRS=[E_1(1),E_1(s),...,E_1(s^d),E_2(\alpha),E_2(\alpha \cdot s),...,E_2(\alpha \cdot s^d)] $$
然后公开CRS
- 协议证明：Alice利用CRS计算$a=E_1[P(s)],b=E_2[\alpha \cdot P(s)]$（根据前面提到的内容，E_1和E_2在同态隐藏下可以完成线性组合的运算）
- 协议验证：固定$x,y\in F_r$，满足$a=E_1(x),b=E_2(y)$，然后Bob计算$E(\alpha \cdot x)=Tate[E_1(x),E_2(\alpha)]$和$E(y)=Tate[E_1(1),E_2(y)]$，并检查是否有$E(\alpha \cdot x)=E(y)$（如果等式成立，则意味着$\alpha \cdot x = y$
和第四节中介绍的一样，Alice若要构造一个可以通过验证的$(a,b)$，则$a$必须是$d$阶多项式$P$在点$s$处$P(s)$的隐藏，而$d$是Alice已知的，但Bob不知道$\alpha$也不需要知道，因为可以利用Tate归约配对来从$E_1(x),E_2(\alpha)$计算出$E(\alpha \cdot x)$
综上，Alice不需要发送第一条消息，因为这个消息可以从CRS中获取到，Bob也无需向Alice返回挑战的响应，从而Alice可以直接发送协议的第三条即可完成证明