Ou: Automating the Parallelization of Zero-Knowledge Protocols

Last modified: Mon Jan 1 01:14:19 2024 GMT.

Authors

Yuyang Sang
Ning Luo
Samuel Judson
Ben Chaimberg
Timos Antonopoulos
Xiao Wang
Ruzica Piskac
Zhong Shao

Abstract

A 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.

Published

In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS'23), Copenhagen, Denmark, pages 534-548, November 2023.

Conference Paper [PDF]

colophon