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 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
History
2023-05-11: approved
2023-05-09: received
See all versions
Short URL
https://ia.cr/2023/657
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.