Ou: Automating the Parallelization of Zero-Knowledge Protocols
Last modified: Mon Jan 1 01:14:19 2024 GMT.
AbstractA zero-knowledge proof (ZKP) is a powerful cryptographic primitive used in many decentralized or privacy-focused applications. However, the high overhead of ZKPs can restrict their practical applicability. We design a programming language, Ou, aimed at easing the programmer's burden when writing efficient ZKPs, and a compiler framework, Lian, that automates the analysis and distribution of statements to a computing cluster. Ou uses programming language semantics, formal methods, and combinatorial optimization to automatically partition an Ou program into efficiently sized chunks for parallel ZK-proving and/or verification. We contribute: (1) A front-end language where users can write proof statements as imperative programs in a familiar syntax; (2) A compiler architecture and implementation that automatically analyzes the program and compiles it into an optimized IR that can be lifted to a variety of ZKP constructions; and (3) A cutting algorithm, based on Pseudo-Boolean optimization and Integer Linear Programming, that reorders instructions and then partitions the program into efficiently sized chunks for parallel evaluation and efficient state reconciliation.
PublishedIn Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS'23), Copenhagen, Denmark, pages 534-548, November 2023.
Copyright © 1996-2024 The FLINT Group
<flint at cs dot yale dot edu>
Yale University Department of Computer Science