Volatile and Persistent Memory for zkSNARKs via Algebraic Interactive Proofs

—In verifiable outsourcing, an untrusted server runs an expensive computation and produces a succinct proof (called a SNARK) of the results. In many scenarios, the computation accesses a RAM that the server maintains a commitment to (persistent RAM) or that is initially zero (volatile RAM). But, SNARKs for such scenarios are limited by the high overheads associated with existing techniques for RAM checking. We develop new proofs about volatile, persistent, and sparse persistent RAM that reduce SNARK proving times. Our results include both asymptotic and concrete improvements—including a proving time reduction of up to 51.3 × for persistent RAM. Along the way, we apply two tools that may be of independent interest. First, we generalize an existing construction to convert any algebraic interactive proof (AIP) into a SNARK. An AIP is a public-coin, non-succinct, interactive proof with a verifier that is an arithmetic circuit. Second, we apply Bézout’s identity for polynomials to construct new AIPs for uniqueness and disjointness. These are useful for showing the independence of accesses to different addresses.

在可验证外包中，不可信的服务器运行一项昂贵的计算，并生成结果的简洁证明（称为零知识简洁非交互式知识论证，即SNARK）。在许多场景中，计算会访问服务器对其有承诺的随机存取存储器（持久随机存取存储器），或者初始为零的随机存取存储器（易失随机存取存储器）。但是，此类场景的SNARK受到与现有随机存取存储器检查技术相关的高开销的限制。我们针对易失、持久和稀疏持久随机存取存储器开发了新的证明，减少了SNARK的证明时间。我们的结果包括渐近和具体的改进——对于持久随机存取存储器，证明时间减少了高达51.3倍。在此过程中，我们应用了两个可能具有独立研究价值的工具。首先，我们推广了一种现有构造，将任何代数交互式证明（AIP）转换为SNARK。AIP是一种公开硬币、非简洁的交互式证明，其验证者是一个算术电路。其次，我们应用多项式的贝祖等式为唯一性和不相交性构建新的AIP。这些对于表明对不同地址访问的独立性很有用。