49.概率可检验证明（PCP）

title: 49. 概率可检验证明（PCP） tags: zk computation theory probabilistically checkable proof PCP WTF zk 教程第 49 讲：概率可检验证明（PCP） 这一讲，我们将探讨概率可检验证明（Probabilistically Checkable Proof，PCP）这一重要概念。PCP 定理为我们提供了一种验证证明的方式，允许验证者在仅检验少部分证明的情况下，以高概率确定其正确性。PCP 是 zk-SNARKs 中一个关键的理论基础。 PCP 概述 PCP 是一种局部可验证的证明系统，验证者只需要检查证明的少部分内容就能高概率地验证其正确性。与传统的 NP 证明系统不同，PCP 验证者具有两个特性： 随机性：验证者使用随机选择的方式抽取证明中的部分内容进行检查。 预言机访问：验证者可以查询一个“证明预言机”（oracle），在一个计算步骤内返回证明中某个位置的值。 随机性在之前的 BPP 和 IP 中已经出现过，而预言机（oracle）则首次出现在这里。在计算理论中，预言机是一个强大的“黑盒子”，它可以瞬...