零知识证明 - 从QSP到QAP

2019-06-12 19:50:11

通过QSP问题证明来验证另外一个NP问题的解。

  前一段时间,介绍了零知识证明 - zkSNARK入门,通过QSP问题证明来验证另外一个NP问题的解。最近在看QAP问题相关的文章和资料,分享一下QAP问题的理解。

  00  背景介绍

  QSP/QAP问题的思想都是出自2012年一篇论文:Quadratic Span Programs and Succinct NIZKs without PCPs。论文的下载地址:https://eprint.iacr.org/2012/215.pdf。

image.png


  这篇论文提出了使用QSP/QAP问题,而不使用PCP方式,实现零知识证明。


  01  术语介绍

  SP  - Span Program ,采用多项式形式实现计算的验证。

  QSP - Quadratic Span Program,QSP问题,实现基于布尔电路的NP问题的证明和验证。

  QAP - Quadratic Arithmetic Program,QAP问题,实现基于算术电路的NP问题的证明和验证,相对于QSP,QAP有更好的普适性。

  PCP - Probabilistically Checkable Proof ,在QSP和QAP理论之前,学术界主要通过PCP理论实现计算验证。PCP是一种基于交互的,随机抽查的计算验证系统。

  NIZK - Non-Interactive Zero-Knowledge,统称,无交互零知识验证系统。NIZK需要满足三个条件:1/ 完备性(Completeness),对于正确的解,肯定存在相应证明。 2/可靠性 (Soundness) ,对于错误的解,能通过验证的概率极低。3/ 零知识。

  SNARG - Succinct Non-interactive ARGuments,简洁的无须交互的证明过程。

  SNARK - Succinct Non-interactive ARgumentss of Knowledge,相比SNARG,SNARK多了Knowledge,也就是说,SNARK不光能证明计算过程,还能确认证明者“拥有”计算需要的Knowledge(只要证明者能给出证明就证明证明者拥有相应的解)。

  zkSNARK - zero-knowledge SNARK,在SNARK的基础上,证明和验证双方除了能验证计算外,验证者对其他信息一无所知。

  Statement - 对于QSP/QAP而言,某个计算电路的输入。Statement对证明者和验证者都是公开的。

  Witness - Witness只有证明者知道。可以理解成,某个计算电路的输出(output)。


  02  QAP问题和算术电路

  QAP的定义和QSP的定义有些相似(毕竟都是一个思想理论的两种形式)。论文中给出了QAP的一般定义和强定义。QAP的强定义如下:


image.png

  算术电路可以简单看成由如下的三种门组成:加门,系数乘法门以及通用乘法门(减法可以转化为加法,除法可以转化为乘法)。Vitalik在2016年写过的QAP介绍,深入浅出的解释NP问题的算术电路生成和QAP问题的转化。推荐大家都读一读。

  https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

image.png



  03  算术问题转化为QAP问题

  把一个算术电路转化为QAP问题的过程,其实就是将电路中的每个门描述限定的过程,也就是所谓的R1CS (Rank-1 constraint system)。


  3.1 算术电路拍平

image.png


image.png


  3.3 多项式表达

image.png




image.png

image.png




image.png


image.png




image.png





最新推荐