Efficient Representation of Numerical Optimization Problems for SNARKs

Sebastian Angel; Andrew J.  Blumberg; Eleftherios Ioannidis; Jess Woods

Paper 2021/1436

Efficient Representation of Numerical Optimization Problems for SNARKs

Sebastian Angel, Andrew J. Blumberg, Eleftherios Ioannidis, and Jess Woods

Abstract

This paper introduces Otti, a general-purpose compiler for (zk)SNARKs that provides support for numerical optimization problems. Otti produces efficient arithmetizations of programs that contain optimization problems including linear programming (LP), semi-definite programming (SDP), and a broad class of stochastic gradient descent (SGD) instances. Numerical optimization is a fundamental algorithmic building block: applications include scheduling and resource allocation tasks, approximations to NP-hard problems, and training of neural networks. Otti takes as input arbitrary programs written in a subset of C that contain optimization problems specified via an easy-to-use API. Otti then automatically produces rank-1 constraint satisfiability (R1CS) instances that express a succinct transformation of those programs. Correct execution of the transformed program implies the optimality of the solution to the original optimization problem. Our evaluation on real benchmarks shows that Otti, instantiated with the Spartan proof system, can prove the optimality of solutions in zero-knowledge in as little as 100 ms---over 4 orders of magnitude faster than existing approaches

Note: This version contains 2 appendices which provide additional experiments and code snippets.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Minor revision. USENIX Security 2022
Keywords: SNARK numerical optimization compilers
Contact author(s): sebastian angel @ cis upenn edu
History: 2022-02-23: last of 4 revisions; 2021-10-26: received; See all versions
Short URL: https://ia.cr/2021/1436
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1436,
      author = {Sebastian Angel and Andrew J.  Blumberg and Eleftherios Ioannidis and Jess Woods},
      title = {Efficient Representation of Numerical Optimization Problems for {SNARKs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1436},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1436}
}