Less is more: Refinement proofs for probabilistic proofs

Kunming Jiang, Devora Chait-Roth, Zachary Destefano, Michael Walfish, Thomas Wies

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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×, and in some cases, better asymptotics.

Original languageEnglish (US)
Title of host publicationProceedings - 44th IEEE Symposium on Security and Privacy, SP 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages18
ISBN (Electronic)9781665493369
StatePublished - 2023
Event44th IEEE Symposium on Security and Privacy, SP 2023 - Hybrid, San Francisco, United States
Duration: May 22 2023May 25 2023

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
ISSN (Print)1081-6011


Conference44th IEEE Symposium on Security and Privacy, SP 2023
Country/TerritoryUnited States
CityHybrid, San Francisco


  • R1CS-constraints
  • SNARKs
  • arithmetic-circuits
  • front-ends
  • probabilistic-proofs
  • refinement-proofs
  • verifiable-computation
  • widgets
  • zero-knowledge

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Less is more: Refinement proofs for probabilistic proofs'. Together they form a unique fingerprint.

Cite this