TY - GEN
T1 - A 2.1 KHz Zero-Knowledge Processor with BubbleRAM
AU - Heath, David
AU - Kolesnikov, Vladimir
N1 - Funding Information:
work has constructed succinct non-interactive ZK proofs in a processor model similar to ours [7, 10, 11]. Because of non-interactivity and succinctness, these works are applicable to more problems than our approach. In exchange, our approach is vastly more efficient. These approaches attain a clock rate less than 10Hz on powerful hardware and manipulate memories containing hundreds of bits. Ours runs at 2.1KHz on commodity hardware and can manipulate a main memory holding hundreds of KBs of data. Acknowledgement. This work was supported in part by NSF award #1909769 and in part by Sandia National Laboratories, a multi-mission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA-0003525.
Publisher Copyright:
© 2020 ACM.
PY - 2020/10/30
Y1 - 2020/10/30
N2 - Zero-Knowledge (ZK) proofs (ZKP) are foundational in cryptography. Most recent ZK research focuses on non-interactive proofs (NIZK) of small statements, useful in blockchain scenarios. Another line, and our focus, instead targets proofs of large statements that are useful, e.g., in proving properties of programs in ZK. We specify a zero-knowledge processor that executes arbitrary programs written in a simple instruction set, and proves in ZK the correctness of the execution. Such an approach is well-suited for constructing ZK proofs of large statements as it efficiently supports complex programming constructs, such as loops and RAM access. Critically, we propose several novel ZK improvements that make our approach concretely efficient: (1) an efficient arithmetic representation with conversions to/from Boolean, (2) an efficient read-only memory that uses $2log n$ OTs per access, and (3) an efficient read-write memory, øurram, which uses $\frac1 2 log^2 n$ OTs per access. øurram beats linear scan for RAM of size $>3$ elements! Prior ZK systems used generic ORAM costing orders of magnitude more. We cast our system as a garbling scheme that can be plugged into the ZK protocol of [Jawurek et al, CCS'13]. Put together, our system is concretely efficient: for a processor instantiated with $512$KB of main memory, each processor cycle costs $24$KB of communication. We implemented our approach in \textttC++. On a 1Gbps LAN our implementation realizes a $2.1$KHz processor.
AB - Zero-Knowledge (ZK) proofs (ZKP) are foundational in cryptography. Most recent ZK research focuses on non-interactive proofs (NIZK) of small statements, useful in blockchain scenarios. Another line, and our focus, instead targets proofs of large statements that are useful, e.g., in proving properties of programs in ZK. We specify a zero-knowledge processor that executes arbitrary programs written in a simple instruction set, and proves in ZK the correctness of the execution. Such an approach is well-suited for constructing ZK proofs of large statements as it efficiently supports complex programming constructs, such as loops and RAM access. Critically, we propose several novel ZK improvements that make our approach concretely efficient: (1) an efficient arithmetic representation with conversions to/from Boolean, (2) an efficient read-only memory that uses $2log n$ OTs per access, and (3) an efficient read-write memory, øurram, which uses $\frac1 2 log^2 n$ OTs per access. øurram beats linear scan for RAM of size $>3$ elements! Prior ZK systems used generic ORAM costing orders of magnitude more. We cast our system as a garbling scheme that can be plugged into the ZK protocol of [Jawurek et al, CCS'13]. Put together, our system is concretely efficient: for a processor instantiated with $512$KB of main memory, each processor cycle costs $24$KB of communication. We implemented our approach in \textttC++. On a 1Gbps LAN our implementation realizes a $2.1$KHz processor.
KW - garbling scheme
KW - verifiable garbled circuits
KW - zero knowledge
UR - http://www.scopus.com/inward/record.url?scp=85096184849&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85096184849&partnerID=8YFLogxK
U2 - 10.1145/3372297.3417283
DO - 10.1145/3372297.3417283
M3 - Conference contribution
AN - SCOPUS:85096184849
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 2055
EP - 2074
BT - CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
T2 - 27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020
Y2 - 9 November 2020 through 13 November 2020
ER -