Zero Knowledge for Everything and Everyone: Fast ZK Processor with Cached ORAM for ANSI C Programs
Zero Knowledge for Everything and Everyone: Fast ZK Processor with Cached ORAM for ANSI C Programs
复制标题
DOI：
10.1109/sp40001.2021.00089
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
David Heath;Yibin Yang;David Devecsery;V. Kolesnikov
中科院分区：
文献类型：
--
作者：
David Heath;Yibin Yang;David Devecsery;V. Kolesnikov
我们构建了一个完整且高效的 ZK 工具链，用于处理编码为任意 ANSI C 程序的证明语句。零知识 (ZK) 证明是密码学的基础。最近的 ZK 研究主要集中在小语句的非交互式证明上，这在区块链场景中很有用。相反，我们的目标是有用的大型语句，例如，在证明程序的属性时。最近的工作（Heath 和 Kolesnikov，CCS 2020 [HK20a]）设计了一种高效的概念验证 ZK 机器（ZKM）。他们的机器通过最小指令集执行任意程序，并在 ZK 中验证程序执行。在这项工作中，我们在效率和通用性方面都显着扩展了这项研究主旨。我们的贡献包括：• 丰富且面向性能的架构，用于将任意 ZK 证明表示为程序。• 完整的编译器工具链，为 ANSI C95 程序提供全面支持。我们运行了现成的有错误的 Linux 程序 sed 和 gzip 版本，在 ZK 中证明每个程序都有错误。据我们所知，这是第一个能够执行标准Linux 程序的ZK 系统。• 改进的ZK 不经意RAM (ORAM)。 [HK20a] 引入了一种高效的 ZK 特定 ORAM BubbleRAM，每次访问消耗 O(log2 n) 通信。我们通过多级缓存扩展了 BubbleRAM，将每次访问的通信量减少到 O(log n)。这引入了缓存未命中的可能性，我们处理这种情况的成本很低。我们的实验表明缓存未命中的情况很少见；单独来看，即忽略其他处理器成本，BubbleCache 比 BubbleRAM 的通信性能提高了 8 倍以上。使用 BubbleCache 将我们处理器的总通信（包括缓存未命中成本）提高了约 25-30%。• 大量低级优化，使 CPU 比 [HK20a] 更具表现力，速度快约 5.5 倍。• 注重用户体验。我们面向工程师的 ZK 工具和扩展是最小且易于使用的。总而言之，我们的系统高效且通用，并且可以运行许多标准 Linux 程序。最终的机器在 1Gbps LAN 上以高达 11KHz 的速度运行，并支持 MB 的 RAM。
We build a complete and efficient ZK toolchain that handles proof statements encoded as arbitrary ANSI C programs.Zero-Knowledge (ZK) proofs are foundational in cryptography. Recent ZK research has focused intensely on non-interactive proofs of small statements, useful in blockchain scenarios. We instead target large statements that are useful, e.g., in proving properties of programs.Recent work (Heath and Kolesnikov, CCS 2020 [HK20a]) designed an efficient proof-of-concept ZK machine (ZKM). Their machine executes arbitrary programs over a minimal instruction set, authenticating in ZK the program execution. In this work, we significantly extend this research thrust, both in terms of efficiency and generality. Our contributions include:• A rich and performance-oriented architecture for representing arbitrary ZK proofs as programs.• A complete compiler toolchain providing full support for ANSI C95 programs. We ran off-the-shelf buggy versions of the Linux programs sed and gzip, proving in ZK that each program has a bug. To our knowledge, this is the first ZK system capable of executing standard Linux programs.• Improved ZK oblivious RAM (ORAM). [HK20a] introduced an efficient ZK-specific ORAM BubbleRAM that consumes O(log2 n) communication per access. We extend BubbleRAM with multi-level caching, decreasing communication to O(log n) per access. This introduces the possibility of a cache miss, which we handle cheaply. Our experiments show that cache misses are rare; in isolation, i.e., ignoring other processor costs, BubbleCache improves communication over BubbleRAM by more than 8×. Using BubbleCache improves our processor’s total communication (including costs of cache misses) by ≈ 25-30%.• Numerous low-level optimizations, resulting in a CPU that is both more expressive and ≈ 5.5× faster than [HK20a]’s.• Attention to user experience. Our engineer-facing ZK instrumentation and extensions are minimal and easy to use.Put together, our system is efficient and general, and can run many standard Linux programs. The resultant machine runs at up to 11KHz on a 1Gbps LAN and supports MBs of RAM.