How to simulate PLONK: A formal security analysis of a zk-SNARK

Abstract

Zero-Knowledge-Beweise ermöglichen es, etwas zu beweisen, ohne dabei Informationen über die Wahrheit der Aussage hinaus preiszugeben. Dieses paradoxe Konzept, welches ursprünglich rein theoretischer Natur war, hat in den letzten Jahrzehnten eine breite Anwendung in der Praxis gefunden. An der Spitze dieser Entwicklung stehen Beweissysteme, die zk-SNARKs genannt werden, was für Zero-Knowledge Succinct Non-Interactive Argument of Knowledge steht. Sie vermeiden nicht nur, dass mehrere Runden der Interaktion erforderlich sind, sondern haben auch Beweise, die deutlich kürzer als die bewiesene Aussage selbst sind, wobei einige Konstruktionen sogar Beweise mit konstanter Größe erreichen. Einer der aktuellsten zk-SNARKs ist "PLONK" von Gabizon, Williamson und Ciobotaru aus dem Jahr 2019. Seine Beweise haben mit nur einem halben Kilobyte konstante Größe und können in sublinearer Zeit verifiziert werden. Darüber hinaus müssen die erforderlichen öffentlichen Parameter nur einmalig aufgesetzt werden, um beliebige Aussagen bis zu einer bestimmten Länge beweisen zu können, was PLONK zu einem universellen und zeiteffizienten zk-SNARK macht. Obwohl PLONK sehr einflussreich ist und in mehreren realen Anwendungen eingesetzt wird, gibt es keinen formalen Sicherheitsbeweis seiner Zero-Knowledge-Eigenschaft. Im Rahmen dieser Arbeit zeigen wir auf, wie eine von uns gefundene Sicherheitslücke in der Zero-Knowledge-Implementierung von PLONK behoben werden kann. Das PLONK-Protokoll wurde bereits entsprechend ausgebessert. Unser Hauptbeitrag ist ein formaler Sicherheitsbeweis dafür, dass die resultierende Version von PLONK statistisches Zero-Knowledge erfüllt. Hierfür zeigen wir, wie Beweise bis auf einen exponentiell kleinen Unterschied simuliert werden können, ohne dabei Zugriff auf die geheimen Informationen des Beweisers zu haben. Gemäß der Standarddefinition von Zero-Knowledge folgt daraus, dass PLONK-Beweise (statistisch) keine Informationen über die Wahrheit der Aussage hinaus preisgeben. Zudem führen wir eine genaue Sicherheitsanalyse des gesamten PLONK-Protokolls durch, einschließlich des Nachweises der Sicherheit aller seiner Komponenten. Dabei beweisen wir eine präzise obere Schranke für den Knowledge-Soundness-Fehler von PLONK im algebraischen Gruppenmodell. Da der ursprüngliche Beweis der Knowledge-Soundness von PLONK ebenfalls auf diesem idealisierten Modell beruht, tragen unsere Ergebnisse zu einem allgemein besseren Verständnis der Sicherheitseigenschaften von PLONK bei.

Zero-knowledge proofs enable proving a statement without revealing any information beyond its truth. This paradoxical notion has evolved over the last few decades from a theoretical concept to the wide adoption of highly efficient zero-knowledge proof systems in practice. At the forefront of this development are proof systems called zk-SNARKs, which stands for zero-knowledge succinct non-interactive argument of knowledge. Not only do they avoid multiple rounds of interaction, but zk-SNARKs also offer succinct proofs whose length is much shorter than the size of the proved statement, with some constructions even achieving constant-size proofs. Among the most recent state-of-the-art constructions is the zk-SNARK "PLONK" by Gabizon, Williamson, and Ciobotaru from 2019. It has constant-size proofs of only half a kilobyte and sublinear proof verification time. Furthermore, it only requires a single trusted setup of its public parameters to support proofs of any statement up to a certain size bound, making PLONK a universal and fully succinct zk-SNARK. Although highly influential and implemented in several real-world applications, there is no formal security proof of its zero knowledge property. In this thesis, we disclose a vulnerability found in PLONK's implementation of zero knowledge and propose how to fix it. As a result, the PLONK protocol has been patched accordingly. Our primary contribution is a formal security proof establishing that the resulting version of PLONK achieves statistical zero knowledge. Towards this goal, we show how to simulate proofs up to an exponentially small difference without relying on any secret information used by the prover. Following the standard definition of zero knowledge, this implies that PLONK proofs reveal (statistically) zero information beyond the truth of the statement. Moreover, we conduct a rigorous security analysis of the entire PLONK protocol, proving the security of all its underlying components. This allows us to show a precise upper bound on PLONK's knowledge soundness error in the algebraic group model. Since the original proof given by the authors of PLONK relies on the same idealized model, our results help towards a better understanding of the security guarantees of PLONK in general.