EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs

Shankara Pailoor, Yanju Chen, Franklyn Wang, Clara Rodríguez, Jacob Van Geffen, Jason Morton, Michael Chu, Brian Gu, Yu Feng, Işıl Dillig

Proceedings of the ACM on Programming Languages · 06.06.2023 · 7 (PLDI) · 1510-1532

DOI: 10.1145/3591282 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 06.06.2023. Verfasst von Shankara Pailoor und 9 weiteren Autor:innen. Die Arbeit wurde bisher 24-mal zitiert (Crossref) und nennt 52 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

As zero-knowledge proofs gain increasing adoption, the cryptography community has designed domain-specific languages (DSLs) that facilitate the construction of zero-knowledge proofs (ZKPs). Many of these DSLs, such as Circom, facilitate the construction of arithmetic circuits, which are essentially polynomial equations over a finite field. In particular, given a program in a zero-knowledge proof DSL, the compiler automatically produces the corresponding arithmetic circuit. However, a common and serious problem is that the generated circuit may be underconstrained, either due to a bug in the program or a bug in the compiler itself. Underconstrained circuits admit multiple witnesses for a given input, so a malicious party can generate bogus witnesses, thereby causing the verifier to accept a proof that it should not. Because of the increasing prevalence of such arithmetic circuits in blockchain applications, several million dollars worth of cryptocurrency have been stolen due to underconstrained arithmetic circuits. Motivated by this problem, we propose a new technique for finding ZKP bugs caused by underconstrained polynomial equations over finite fields. Our method performs semantic reasoning over the finite field equations generated by the compiler to prove whether or not each signal is uniquely determined by the input. Our proposed approach combines SMT solving with lightweight uniqueness inference to effectively reason about underconstrained circuits. We have implemented our proposed approach in a tool called QED 2 and evaluate it on 163 Circom circuits. Our evaluation shows that QED 2 can successfully solve 70% of these benchmarks, meaning that it either verifies the uniqueness of the output signals or finds a pair of witnesses that demonstrate non-uniqueness of the circuit. Furthermore, QED 2 has found 8 previously unknown vulnerabilities in widely-used circuits.

Zitieren

APA

Pailoor, S., Chen, Y., Wang, F., Rodríguez, C., Geffen, J. V., Morton, J., Chu, M., Gu, B., Feng, Y., & Dillig, I. (2023). Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs. Proceedings of the ACM on Programming Languages, 7(PLDI), 1510-1532. https://doi.org/10.1145/3591282

Vancouver

Pailoor S, Chen Y, Wang F, Rodríguez C, Geffen JV, Morton J, et al. Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs. Proceedings of the ACM on Programming Languages. 2023;7(PLDI):1510-1532. doi:10.1145/3591282

BibTeX
@article{Pailoor2023,
  author = {Pailoor, Shankara and Chen, Yanju and Wang, Franklyn and Rodríguez, Clara and Geffen, Jacob Van and Morton, Jason and Chu, Michael and Gu, Brian and Feng, Yu and Dillig, Işıl},
  title = {Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2023},
  volume = {7},
  number = {PLDI},
  pages = {1510--1532},
  doi = {10.1145/3591282}
}
Kostenlos starten →