为什么关注ZK-ConSNARK？

Suterusu项目关注的是无需trusted
setup，且证明空间复杂度为常数的，计算高效的零知识证明方案，简称ZK-ConSNARK。我们知道，一般情况下区块链系统需要将交易通过p2p网络传输给系统中每个验证节点进行验证。

因此，网络单位时间能处理的交易数目，俗称出块率，很大程度上取决于区块大小，以及单位交易所占空间大小【CDEGJKMSSSS16】。交易越小，则出块率越高。在隐私保护区块链方案中，交易大小又很大程度上取决于其所包含的零知识证明大小。

事实上，需要trusted setup的ZK-ConSANRK文献里已有不少，Zcash所使用的方案就属于这个类别。但无需trusted
setup的ZK-ConSNARK却是稀有品种，目前本人所能找到这方面的结果只有两篇：Crypto 2019年新鲜出炉的结果【LM19,
BBF19】。这篇文章将简单介绍这两个方案的基本思路以及Suterusu项目在ZK-ConSANRK上的关注点。

上述两篇论文【LM19, BBF19】都结合了概率性可验证证明（Probabilistical Checkable
Proof，PCP）和子向量承诺（Subvector
Commitment）方案。PCP是复杂性理论和密码学里一个非常经典的结果，相关定理的提出者因此获奖无数。

PCP作为一个基础方案可用于构造零知识证明。上述两篇论文主要贡献不在于PCP，而在于这个子向量承诺方案。其原因在于PCP方案如果想在非交互式零知识证明这个领域施展身手离不开高效的子向量承诺方案这个助手。

首先，我们简单介绍下什么是概率性可验证证明。我们在前文【林19-1】中介绍过零知识证明的概念。零知识证明中有这么个验证者的概念，在PCP中也有个验证者。但PCP的验证者特别懒，所以我们需要考虑验证者讲解能在做非常少工作的情况下，还能准确判断PCP证明者针对一个定理提供的证明是否正确。

尽管PCP本身的证明是非常长，但PCP有个神奇的性质就是在证明者生成证明后，验证者只需随机在证明上查询若干点(实际中大概是安全系数×3bits即可，所以如果是256-bit
security，查询长度只需256*3 bits)，然后做一些极为高效的运算就可以验证证明的正确性。

我们在前文【林19-1】中提过，区块链中使用的零知识证明需要是极为简短的且**计算也是高效的，尽管PCP的验证计算颇为高效，但证明过长仍是个弊病。我们注意到在验证时验证者真正需要访问的只是整个证明中极小一部分内容。

那么问题来了，有没有可能让证明者在生成PCP证明后自己在证明上随机选取验证者需要的查询点，然后只传输这些信息给验证者，从而大大减少通信量呢?

这个思路是对的，但一个恶意的证明者，或者一个不掌握证明秘密的人可以针对这个简单思路发起如下几个攻击：比如可能这个用于随机选取查询点的随机数本身不随机，或者攻击者先生成随机数，然后再针对这些随机位置生成对应证明，换句话说他可能没有能力生成全部正确PCP证明，但他却有办法针对提前生成的随机位置生成合法的部分证明，进而相应地替换篡改他所生成的非法证明的对应位置内容，从而通过验证。