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

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.

Available format(s)
Publication info
zero knowledge proofprogramming languageparallelizationautomated 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
2023-05-11: approved
2023-05-09: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.