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
SNARKnumerical optimizationcompilers
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/1436}},
      url = {https://eprint.iacr.org/2021/1436}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.