Paper 2023/656

Formalizing Soundness Proofs of SNARKs

Bolton Bailey, University of Illinois Urbana-Champaign
Andrew Miller, University of Illinois Urbana-Champaign
Abstract

Succinct Non-interactive Arguments of Knowledge (SNARKs) have seen interest and development from the cryptographic community over recent years, and there are now constructions with very small proof size designed to work well in practice. A SNARK protocol can only be widely accepted as secure, however, if a rigorous proof of its security properties has been vetted by the community. Even then, it is sometimes the case that these security proofs are flawed, and it is then necessary for further research to identify these flaws and correct the record. To increase the rigor of these proofs, we turn to formal methods. Focusing on the soundness aspect of a widespread class of SNARKs, we formalize proofs for six different constructions, including the well-known Groth '16. Our codebase is written in the Lean 3 theorem proving language, and uses a variety of techniques to simplify and automate these proofs as much as possible.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
SNARKsFormal Methods
Contact author(s)
boltonb2 @ illinois edu
soc1024 @ illinois edu
History
2023-05-11: approved
2023-05-09: received
See all versions
Short URL
https://ia.cr/2023/656
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/656,
      author = {Bolton Bailey and Andrew Miller},
      title = {Formalizing Soundness Proofs of SNARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/656},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/656}},
      url = {https://eprint.iacr.org/2023/656}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.