* 运行半可提取哈希的密钥生成算法 Gen针对索引集 I 生成哈希密钥 hash_key 和陷门 trapdoor。 * 运行 BARG 的 CRS 生成算法得到 CRS_BARG。 * 组合得到 SNARG 的 CRSCRS (hash_key, CRS_BARG)。运行作弊者将CRS输入给P*P*输出一个实例x*和一个 SNARG 证明π (V, π_BARG)。验证与重试如果π未被 SNARG 验证者接受则回到步骤 2 重新生成 CRS 并尝试。重复多项式次直到获得一个被接受的证明。提取与输出一旦获得被接受的证明使用陷门trapdoor从哈希值V中提取出索引集I对应的导线值{wi1, ..., wiL}。最后输出(x*, {wi1, ..., wiL})。为何满足局部一致性局部一致性源于底层 BARG 的可靠性即使是半自适应的可靠性也足够。思路假设E以不可忽略的概率输出了一个不满足局部一致性的赋值。这意味着存在某个门j其导线赋值不满足门约束。构造 BARG 作弊者我们可以利用P*和E来构造一个针对 BARG 的作弊证明者P**。P**首先生成一个针对导线集I包含门j的导线的哈希密钥。然后运行P*获得(x*, V, π_BARG)。P**将(hash_key, V, 1),(hash_key, V, 2), …,(hash_key, V, k)k为门的总数作为自适应选择的实例提交给 BARG 验证者。其中第j个实例(hash_key, V, j)声称门j被满足。但由于我们从E知道门j的赋值不满足约束并且哈希函数在索引I上是绑定的因此这个实例实际上没有合法的见证witness。然而P**却提交了被接受的 BARG 证明π_BARG。矛盾这就违反了 BARG 的可靠性。因此E输出不满足局部一致性赋值的概率必须是可忽略的。为何满足非信号性非信号性源于半可提取哈希函数的“索引隐藏”属性。在我们的构造中哈希函数是通过多次重复一个基础方案来支持多个可提取索引的。当提取器E使用陷门提取特定索引集I的导线值时它只使用了与I对应的那部分陷门。作弊证明者P*无法区分哈希密钥是针对哪些索引集生成的。因此提取出的导线值分布不会泄露关于其他索引的信息否则就破坏了哈希函数的索引隐藏性质。从局部一致性到全局一致性现在我们有一个局部赋值生成器E它能提供任何L根导线的、局部一致的赋值。我们最终的目标是证明如果 SNARG 验证者接受了证明那么原始实例x一定在语言中即存在一个全局的、一致的导线赋值使电路输出 1。这需要我们将局部一致性“缝合”成全局一致性。对于确定性电路P 语言的尝试对于确定性计算P 语言每个导线在给定输入后只有一个正确的值。我们曾尝试通过逐层归纳来证明全局一致性基础请求输入层的导线赋值。由于局部一致性这些值必须与输入x一致因此是正确的。归纳步骤假设第i层的导线赋值是正确的。为了证明第i1层的某个导线值w正确我们可以请求一个包含第i层相关导线和w的赋值窗口。根据非信号性第i层导线的赋值分布与之前请求时相同因此它们仍然是正确的。根据局部一致性w的值必须基于其前驱第i层导线的正确值计算得出因此w也是正确的。结论通过归纳所有导线赋值都正确输出导线值为 1因此x在语言中。尝试中的缺陷上述论证存在一个微妙但关键的缺陷它忽略了错误概率的累积。局部一致性和非信号性都是以“概率 1 - ν”成立的其中ν是可忽略的函数但不是零。在归纳步骤中要声称第i1层的导线w正确需要同时保证第i层的前驱导线赋值正确概率 ~ 1 - ν。局部一致性条件成立概率 ~ 1 - ν。因此w正确的概率大约是(1 - ν)^2 ≈ 1 - 2ν。随着电路深度d增加这个错误概率会以2^d的指数级增长。当d大于log(1/ν)时最终的错误概率可能不再可忽略。这就是“指数级诅咒”。解决方案与改进为了解决这个问题研究者们探索了多种方法空间有界计算最早的解决方案是针对空间有界的确定性计算。思路是让窗口大小L足以容纳整个计算的一个“配置”如整个内存状态。这样在归纳时我们一次读取整个配置错误概率是线性累积d * ν而非指数累积2^d * ν。但这使得 SNARG 证明的大小与计算空间成正比。电路变换例如添加默克尔哈希更通用的思路是修改待验证的原始电路C得到一个扩展电路C‘。例如可以在每一层计算完成后添加一个对该层所有导线值的默克尔哈希值作为电路的一部分。优点默克尔哈希的计算深度很浅。论证思路首先证明基础层如输入层的默克尔根是正确的。然后在归纳中当请求高层导线值时同时请求其对应的默克尔路径和根。如果根是正确的那么根据哈希函数的抗碰撞性路径末端的导线值也必须是正确的。这样错误主要来自证明根正确的过程而由于默克尔树深度小其错误累积是可控的。这种方法允许构造证明大小与电路深度无关的 SNARG适用于更广泛的电路类型。总结本节课中我们一起学习了局部一致性我们从 BARGs 构造的 SNARG 能够保证对于任何作弊证明者都存在一个局部赋值生成器能为任何一小部分导线提供看似一致且满足“非信号性”的赋值。局部 vs 全局虽然局部一致性是一个强有力的性质但将其提升为标准的全局可靠性即证明实例在语言中并非易事。对于确定性计算P简单的归纳论证会因错误概率的指数累积而失败。当前进展通过修改电路如引入默克尔哈希结构可以克服这一障碍从而为一大类电路构造出实用的 SNARGs。然而为所有 NP 语言构造 SNARGs 仍然是一个重大的开放性问题。这个领域展示了理论密码学中优美数学思想与实际应用如区块链和可验证计算的深刻结合是一个持续活跃且充满挑战的研究前沿。