交互式证明

交互式证明是可验证计算的基本概念,可确保智能合约,程序或数据库执行的计算完整性,由 Goldwasser,Micali, Rackoff[GMR89] 以及 Babai[Bab85]在1985年提出。

更重要的是,交互式证明理论为【非交互式零知识证明(NIZK)】,【非交互式知识论证(SNARKs)】 以及简洁透明的【知识论证(STARKs)】 奠定了基础。

最近证明系统在评估计算的完整性方面风生水起,它们可以帮助实现“加密审计员”,以证明确实计算了数据库上的“搜索”“查询” 等数学函数,保证了数据库的输出正确。


交互式证明

在证明系统中运用“零知识证明”来保证计算的隐私性,它可以验证数据集上的计算,而不会泄露与数据有关的任何信息,因此零知识证明通常用于隐私敏感域, 如匿名识别,数据库成员资格查询以及区块链支付等领域。

在计算复杂性理论中,交互式证明系统是一种抽象机器,它将计算模型转化为双方之间的消息交换。 证明者 Prover 和验证者 Verifier 通过交换消息以确定语句(statement)是否正确。 其中证明者除了不能被信任之外,具备无限的计算资源,而验证者的计算资源是有限的。消息在验证者和证明者之间传递,直到验证者可以验证或伪造语句。

所有的交互式证明系统都有两个关键属性:

  1. 完整性(Completeness) :如果陈述语句是正确的,那么诚实验证者可以通过诚实的证明者来确信这一事实,判断诚实与否,是通过是否正确遵循协议。
  2. 健全性(Soundness):如果陈述语句是错误的,那么恶意节点不能说服诚实的验证者以达到伪造陈述语句的目的。

值得注意的是,健全性使得验证者不会被虚假的陈述说服,而完整性使得证明者向验证者阐述真实语句,这两个属性对证明系统至关重要。


零知识证明

对于零知识证明来说,如果陈述语句是真实的,那么恶意节点除此之外将一无所获。

零知识交互证明系统的首次应用之一是识别方案(identification scheme),以权力游戏流媒体为例 :

  1. 完整性确保 Alice 是高级用户,并获得对高级平台内容的访问权限。
  2. 健全性确保任何其它方都不能生成自己是 Alice 以获取访问权限。
  3. 零知识证明确保包括内容提供方在内的任何其它方都不能够获取秘密信息,从而在未来的身份证明中冒充 Alice ,这也意味着身份证明是不可转让的 识别方案中,Alice 在向 Bob 证明她的身份后,为了防止 Bob 恶意伪造虚假身份信息,协议中确保 Bob 不会获得任何有关Alice 的部分身份信息。

这也是交互证明与传统静态证明之间比较明显的区别,在传统静态证明中,它是可转移的,这也就意味着如果 Alice 向 Bob 提供证明以示身份信息是真实的, 那么 Bob 可以通过复制证明来使 Charlee 相信 Bob 提供的身份信息是真实的。

除了【交互式证明(IP)】,【论证(argument)】,以及【零知识变量(zk-variants)】,还存在一些其它类型的证明系统,如【多方交互式证明(MIP)】和【概率可验证证明(PCP)】。 多方交互式证明类似于上述的交互式证明,其中有多个证明者,但是这些证明者之间是独立的,不能互相共享从验证者那边所获取的与挑战相关的信息, 这有些类似于现在的将犯罪嫌疑人分别安置在不同的房间内进行审讯。

Leave a Reply

Your email address will not be published.

当前无网络链接