zk-SNARKs: Prägnante nicht interaktive Argumente

Ein zk-SNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) ist ein Beweis, der (1) Zero-Knowledge ist, (2) kompakt ist (kleiner Beweis, schnelle Verifikation unabhängig von der Größe der Berechnung) und (3) nicht interaktiv ist (eine einzige Beweiszeichenkette).

Sigma-Protokolle eignen sich für einfache Aussagen (Kenntnis eines diskreten Logarithmus). Für komplexe Berechnungen — etwa „Ich habe diese Funktion korrekt mit privaten Eingaben ausgeführt“ — benötigen wir ein allgemeines Beweissystem. SNARKs weisen beliebige Berechnungen in O(1) Verifikationszeit nach.

Die Berechnung wird zunächst als arithmetische Schaltung dargestellt: ein gerichteter azyklischer Graph aus Additions- und Multiplikationstoren über einem endlichen Körper. Beispiel: Sie weisen nach, dass Sie ein x kennen, für das x^3 + x + 5 = 35 gilt, ohne x=3 offenzulegen. Die Schaltung hat ungefähr fünf Tore.

Eine arithmetische Schaltung wird in R1CS umgewandelt: eine Menge von Constraints (A*z)*(B*z) = C*z, wobei z ein Vektor aller Leitungswerte ist. Aus jedem Multiplikationstor wird ein Constraint. Der Prover muss ein z finden, das alle Constraints erfüllt, ohne private Leitungen offenzulegen.

R1CS wird in ein QAP umgewandelt: Polynome A(x), B(x), C(x), sodass A(x)*B(x)-C(x) genau dann durch ein Zielpolynom t(x) teilbar ist, wenn die Constraints erfüllt sind. Der Prover weist nach, dass er ein Polynom H(x) als Quotienten kennt, ohne den Witness offenzulegen.

Groth16 (2016) ist der effizienteste allgemeine SNARK. Nach einem Trusted Setup (CRS-Erzeugung) gibt der Prover einen Beweis aus drei Gruppenelementen aus (etwa 192 Bytes für BLS12-381). Die Verifikation umfasst drei Pairing-Operationen. Die Beweisgröße bleibt unabhängig von der Größe der Schaltung konstant.

Groth16 erfordert ein Trusted Setup pro Schaltung: Zunächst wird Toxic Waste (ein zufälliges Geheimnis) erzeugt und daraus die Common Reference String berechnet; anschließend wird das Toxic Waste zerstört. Bleibt es erhalten, kann ein Angreifer Beweise fälschen. Zeremonien mit mehreren Parteien (Powers of Tau) verteilen das Vertrauen.

PLONK (2019) verwendet ein universelles Trusted Setup: Eine einzige Zeremonie funktioniert für alle Schaltungen bis zu einer festgelegten Größenbeschränkung. Ein Setup pro Schaltung ist nicht erforderlich. Der Nachteil sind etwas größere Beweise als bei Groth16. PLONK wird in ZK-EVM-Implementierungen verwendet (Polygon Hermez, zkSync Era).

STARKs (Scalable Transparent ARguments of Knowledge) benötigen kein Trusted Setup und verwenden Hashfunktionen (postquanten-sicher). Der Nachteil sind größere Beweise (Dutzende KB statt 200 Bytes). Sie werden in StarkWare/StarkNet und der Sprache Cairo verwendet. SNARKs sind kleiner, STARKs quantensicher.

Groth16 verwendet bilineare Pairings: e: G1 × G2 → GT, wobei e(a*P, b*Q) = e(P,Q)^{ab} gilt. Damit lassen sich Polynomidentitäten im Exponenten prüfen, ohne die Werte offenzulegen. Die Kurve BLS12-381 ist für effiziente Groth16-Pairings optimiert.

Die Beweiserzeugung mit Groth16 für eine Schaltung mit 10^6 Toren dauert auf einer modernen CPU etwa 10 Sekunden. Die Verifikation dauert etwa 1 ms. Diese Asymmetrie ist beabsichtigt: Der Prover, der die aufwendige Berechnung durchgeführt hat, übernimmt die Arbeit; der Verifier, also der Blockchain-Knoten, hat nahezu keinen Aufwand.

Was ist der größte Nachteil von Groth16 gegenüber PLONK?

zk-SNARKs weisen beliebige Berechnungen mit Beweisen konstanter Größe nach. Ablauf: Berechnung → arithmetische Schaltung → R1CS → QAP → SNARK-Beweis. Groth16 ist am effizientesten, erfordert aber ein Trusted Setup pro Schaltung; PLONK verwendet ein universelles Setup. Als Nächstes folgen ZKP-Anwendungen in der Blockchain.