Ou: Automating the Parallelization of Zero-Knowledge Protocols

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

Paper 2023/657

Ou: Automating the Parallelization of Zero-Knowledge Protocols

Yuyang Sang

, Yale University

Ning Luo

, Northwestern University

Samuel Judson, Yale University

Ben Chaimberg, Yale University

Timos Antonopoulos, Yale University

Xiao Wang, Northwestern University

Ruzica Piskac

, Yale University

Zhong Shao

, Yale University

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. Lian 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: • A front-end language where users can write proof statements as imperative programs in a familiar syntax; • 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 • 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.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: zero knowledge proof programming language parallelization automated reasoning
Contact author(s): yuyang sang @ yale edu
ning luo @ northwestern edu
samuel judson @ yale edu
ben chaimberg @ yale edu
timos antonopoulos @ yale edu
wangxiao1254 @ gmail com
ruzica piskac @ yale edu
zhong shao @ yale edu
History: 2023-05-11: approved; 2023-05-09: received; See all versions
Short URL: https://ia.cr/2023/657
License: CC BY

BibTeX

@misc{cryptoeprint:2023/657,
      author = {Yuyang Sang and Ning Luo and Samuel Judson and Ben Chaimberg and Timos Antonopoulos and Xiao Wang and Ruzica Piskac and Zhong Shao},
      title = {Ou: Automating the Parallelization of Zero-Knowledge Protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/657},
      year = {2023},
      url = {https://eprint.iacr.org/2023/657}
}