Less is more: refinement proofs for probabilistic proofs

Kunming Jiang; Devora Chait-Roth; Zachary DeStefano; Michael Walfish; Thomas Wies

Paper 2022/1557

Less is more: refinement proofs for probabilistic proofs

Kunming Jiang, New York University, Carnegie Mellon University

Devora Chait-Roth, New York University

Zachary DeStefano, NYU

Michael Walfish, NYU

Thomas Wies, NYU

Abstract

There has been intense interest over the last decade in implementations of _probabilistic proofs_ (IPs, SNARKs, PCPs, and so on): protocols in which an untrusted party proves to a verifier that a given computation was executed properly, possibly in zero knowledge. Nevertheless, implementations still do not scale beyond small computations. A central source of overhead is the _front-end_: translating from the abstract computation to a set of equivalent arithmetic constraints. This paper introduces a general-purpose framework, called Distiller, in which a user translates to constraints not the original computation but an abstracted _specification_ of it. Distiller is the first in this area to perform such transformations in a way that is provably safe. Furthermore, by taking the idea of "encode a check in the constraints" to its literal logical extreme, Distiller exposes many new opportunities for constraint reduction, resulting in cost reductions for benchmark computations of 1.3–50$\times$, and in some cases, better asymptotics.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Minor revision. 2023 IEEE Symposium on Security and Privacy (SP)
DOI: 10.1109/SP46215.2023.00142
Keywords: probabilistic proofs zero knowledge outsourced computation refinement proofs formal methods widgets gadgets R1CS
Contact author(s): kunmingj @ andrew cmu edu
dc4451 @ nyu edu
zd2131 @ nyu edu
mwalfish @ cs nyu edu
wies @ cs nyu edu
History: 2023-08-02: revised; 2022-11-09: received; See all versions
Short URL: https://ia.cr/2022/1557
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1557,
      author = {Kunming Jiang and Devora Chait-Roth and Zachary DeStefano and Michael Walfish and Thomas Wies},
      title = {Less is more: refinement proofs for probabilistic proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1557},
      year = {2022},
      doi = {10.1109/SP46215.2023.00142},
      note = {\url{https://eprint.iacr.org/2022/1557}},
      url = {https://eprint.iacr.org/2022/1557}
}