零知识证明（16）：多项式盲评估

请注意，本文编写于 736 天前，最后修改于 721 天前，其中某些信息可能已经过时。

概述

本文介绍一个新的概念——多项式的盲评估，以及如何利用同态隐藏来实现这一方式，多项式盲评估是zk-SNARKs的核心

记$F_p$为一域，其大小为$p$，记$P$为一$F_p$上的多项式，其阶为$d$

$$ P(X)=a_0+a_1X+...+a_dX^d $$

其中$a_0,...,a_d\in F_p$

在点$s\in F_p$处评估$P$表示计算点$s$处$P$的值，也即计算

$$ P(s)=a_0+a_1s+...+a_ds^d $$

对于确定的$P$而言，$P(s)$是$1,s,s^2,...,s^d$的线性组合，或者称为加权和（权重为$a_0,a_1,...,a_d$）

之前讨论HH时提到了$E(x)$是支持算术加法的，不难看出其也是支持线性组合的，因为对于给定的$a,b,E(x),E(y)$，不难计算

$$ E(ax+by)=g^{ax}\cdot g^{by}=(g^x)^a\cdot (g^y)^b = E(x)^a\cdot E(y)^b $$

假设Alice有一个阶为$d$的多项式，Bob有一个其随机选择的点$s\in F_p$，Bob希望在Alice不知道$s$的情况下计算$P(s)$，Alice也不希望Bob知道$P$，利用同态隐藏可以做到，具体如下

Bob计算并向Alice发送$E(1),E(s),E(s^2),...,E(s^d)$（也即上述提到的$P(s)$的线性组合）
Alice根据$P$，利用$E(1),E(s),E(s^2),...,E(s^d)$计算$E(P(s))$，并将$E(P(s))$发送给Bob

根据之前介绍的内容，这个简单的协议可以做到Alice不知道$s$且Bob不知道$P$

这里有一个引理使得这个盲评估确实是有效的，称为Schwartz-Zippel引理$[2]$，引理具体不再展开，简而言之就是阶数相同的两个不同的多项式在大多数点的值是不同的，当阶数足够大时，随机选择一个点使得这两个多项式取值相等的概率很小

实际上Zcash使用的$d$很大，大约是$d=2*10^6$

上述内容只介绍了同态隐藏可以保证不能从$E(s)$恢复$s$，但是可以证明的是恶意的敌手也不能从$E(s),E(s^2),...,E(s^d)$恢复$s$，这里不再展开

本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正