TY - GEN
T1 - Ou
T2 - 30th ACM SIGSAC Conference on Computer and Communications Security, CCS 2023
AU - Sang, Yuyang
AU - Luo, Ning
AU - Judson, Samuel
AU - Chaimberg, Ben
AU - Antonopoulos, Timos
AU - Wang, Xiao
AU - Piskac, Ruzica
AU - Shao, Zhong
N1 - Acknowledgement This work is partly supported by NSF awards CCF-2106845, CCF-2131476, CCF-1763399, CNS-2016240, CCF-2019285, CNS-2236819, CCF-2219995, CCF-2318974, CCF-2318975, DARPA under Contract No. HR001120C0087, DARPA and NIWC Pacific under Contract No. N6600121C4018, and the Office of Naval Research (ONR) of the United States Department of Defense through a National Defense Science and Engineering Graduate (NDSEG) Fellowship. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.
PY - 2023/11/15
Y1 - 2023/11/15
N2 - 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: (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.
AB - 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: (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.
KW - Parallelization
KW - Programming language
KW - Zero-knowledge proofs
UR - http://www.scopus.com/inward/record.url?scp=85179854355&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85179854355&partnerID=8YFLogxK
U2 - 10.1145/3576915.3616621
DO - 10.1145/3576915.3616621
M3 - Conference contribution
AN - SCOPUS:85179854355
T3 - CCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
SP - 534
EP - 548
BT - CCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
Y2 - 26 November 2023 through 30 November 2023
ER -