aspnet网站开发工具,物流单号查询网站建设,服装网站建设运营规划,全美网站建设公司我们的目标是构造 zkSNARK。在我们的目标场景中#xff0c;Prover 只需要发送一个简短的证明字符串给 Verifier#xff0c;而 Verifier 不需要给 Prover 发送任何消息。
直接构造一个满足这个场景的 zkSNARK 可能会很困难。一个更灵活的方式是在先在理想模型下构造证明系统Prover 只需要发送一个简短的证明字符串给 Verifier而 Verifier 不需要给 Prover 发送任何消息。
直接构造一个满足这个场景的 zkSNARK 可能会很困难。一个更灵活的方式是在先在理想模型下构造证明系统然后用一个通用的转换把这个只能在理想场景下的系统转化成现实场景中可以工作的 zkSNARK。
理想模型中就是指这个模型用到了场景中并不存在的功能叫做理想功能。理想功能的存在使得构造证明更加方便。构造好之后使用密码学工具模拟这个不存在的功能以实现这个理想模型。
下图是 ZKP 常用的理想模型以及它们之间的转换关系。接下来我们会一一介绍这些模型以及它们之间的转换的具体实现。 IP PCP
Babai 等人在 1991 年提出了随机可查证明 (Probabilistically Checkable Proof, PCP)。在 PCP 模型中Prover 构造一个证明字符串叫做 PCP 证明。PCP 证明的长度可以非常长远远超过 Verifier 的计算能力。所以Prover 不会直接把 PCP 证明发送给 Verifier而是向 Verifier 发送一个预言机 (Oracle)叫做 PCP 预言机。Verifier 可以随意查询 PCP 预言机获取 PCP 字符串任意位置的比特。 为了理解 IP 和 PCP 的关系我们举一个现实中的例子。我们请上我们熟悉的主人公 Alice 和 Bob。假设 Alice 是一名即将毕业的研究生Bob 的任务是评审 Alice 的课题是否合格。IP 模型就是答辩Alice 和 Bob 直接对话如果 Alice 能成功回答 Bob 的所有提问Alice 就成功毕业了。而在 PCP 模型中没有答辩Alice 只是把毕业论文发给 Bob而毕业论文超级长Bob 不可能看完论文只能在论文中随机挑选几段来读如果挑的这些段落都没有问题相互之间逻辑通顺Bob 就相信 Alice 的课题是合格的。
PCP 预言机提供了这样的功能它本身很短传递它只需要很小的通信量它传递的信息量却很大通过它可以随机访问一个很长的字符串。显然真正的 PCP 预言机是不存在的PCP 是一个理想化的模型。 IPCP IPCP (Interactive PCP) 模型可以看做 IP 模型和 PCP 模型的相加。在 IPCP 模型中Prover 向 Verifier 发送了 PCP 预言机后Prover 和 Verifier 继续进行交互。交互过程中Verifier 可以不时地访问 PCP 预言机。 继续使用上一节中 Alice 和 Bob 的例子。如果说 IP 模型是只有答辩PCP 模型是只有毕业论文那么 IPCP 模型就是在 Alice 答辩之前把毕业论文发给 Bob。在答辩过程中Bob 可以一边看毕业论文一边向 Alice 提问。
基于 IPCP 模型构造的证明系统也可以通过 Merkle-Tree 或一般的 VC 方案转化成 IP 模型下的证明系统过程和 PCP 模型的转换完全一样区别仅在于Verifier 在查询 PCP 证明的请求中可能夹杂着普通的交互。
IP 模型和 PCP 模型都可以看做是特殊的 IPCP 模型。其中IP 模型相当于在 IPCP 模型中 Prover 发送一个空预言机给 Verifier。PCP 模型相当于在 IPCP 中省略掉 Prover 和 Verifier 的对话环节。
IOP
如果说 IPCP 模型是把 IP 和 PCP 模型做加法那么 IOP (Interactive Oracle Proof) 模型就是把 IP 和 PCP 做乘法。在 IOP 模型中Verifier 向 Prover 发送消息而 Prover 则向 Verifier 发送 PCP 预言机。Verifier 可以随意查询 Prover 发过的任何 PCP 预言机。 继续使用前面 Alice 和 Bob 的例子来解释 IOP 模型。Alice 把毕业论文发给 BobBob 给 Alice 回复一个简短的评论意见然后 Alice 再写一篇论文发给 BobBob 再回复这样来回进行多次。这个过程中Bob 可以随时阅读 Alice 发给过他的任何一篇论文当然 Bob 的时间仍然不够Bob 仍然只能随机选取一小部分阅读。最后Bob 判断 Alice 的课题是否合格。
和 PCP、IPCP 一样在 IOP 模型下构造的证明系统也可以类似转化成 IP 模型下的证明系统。
IPCP 模型可以看做特殊的 IOP 模型。在 IPCP 模型中把对话环节的 Prover 消息都看做一个 PCP 预言机那么一个 IPCP 模型下的协议就可以看做 IOP 模型下的协议。
IOP (Interactive Oracle Proofs)是一个交互式证明模型。 在一个交互式证明模型中两个算法Prover和Verifier进行交互Prover的目标是向Verifier证明一个实例x属于语言L。例如对于RPT问题而言实例x就是一个RS码f(S)而语言L就是RS[F,S,ρ]。
IOP是在两个更早的交互式证明模型IP和PCP的基础上发展而来的。
IP (Interactive Proofs)最早提出的交互式证明模型。在这个模型中Prover和Verifier进行多轮交互交互结束后Verifier输出0或者1
PCP (Probabilistic Checkable Proofs)在这个模型中Prover和Verifier只进行一次交互这一次交互中Prover向Verifier发送一个字符串叫做PCP。和IP的主要区别是Verifier不需要读取完整的PCP字符串而是可以对其进行随机访问。Verifier计算结束后输出0或者1
IOP其实就是IP和PCP的结合它像IP一样允许多轮交互而每一轮交互都是一个PCP模型即Verifier可以随机访问Prover发来的字符串而不需要读取整个字符串。多轮交互结束后Verifier输出0或者1。
IOP的一个变种叫做IOPP这个多出来的P就是Proximity。在上一节介绍RPT时讲过Proximity的意思是x要么是合法的要么和L中的任何一个元素都相差至少δ距离。
PIOP
多项式 IOP (Polynomial IOP, PIOP) 模型是对 IOP 模型的进一步一般化。和 IOP 模型类似在 PIOP 模型中Verifier 向 Prover 发送消息而 Prover 向 Verifier 发送预言机不过这次不同的是Prover 发送的是多项式预言机。 因为多项式预言机可以实现 PCP 预言机的功能IOP 模型可以看做特殊的 PIOP 模型。
把 PIOP 模型下构造的证明系统转化为 IP 模型下的系统基本思想是和 PCP、IPCP 以及 IOP 的情况一致的即让 Prover 代替多项式预言机的角色但是需要的密码学工具就不一样了。简单的 Merkle-Tree 或 VC 是不能模拟多项式预言机的。我们要用到一个更强大的密码工具叫做多项式承诺 (Polynomial Commitment, PC)。 接下来我们介绍另外两个模型LIP 和 LPCP。目前已有的 Verifier 复杂度和证明大小为常数级别的 zkSNARK 都是基于这两个模型构造的。
LIP
在线性 IP (Linear IP, LIP) 模型中Prover 和 Verifier 进行对话。但是相比于 IP 模型增加了一些限制条件Prover 只能是线性的。 这样一来不仅 Prover连 Verifier 也只能够进行线性运算了。这么一来这个系统就没多大意义。为了能让 Verifier 做至少一次非线性运算一个方法就是引入双线性对。双线性对允许对密文做乘法但是乘法的计算结果是在另外一个密文空间中的所以不影响安全性。 LPCP 参考 [1]https://www.528btc.com/blocknews/160860602772697.html [2]https://blog.nowcoder.net/n/f9742fdb7b2c459ca2be87c7ff5a7f46
