Was ist ein zk-STARK und wie funktioniert er?

Was ist ein zk-STARK?

Ein zk-STARK ist eine kryptografische Methode, um zu beweisen, dass eine Berechnung korrekt ist, ohne dass die Person, die den Proof überprüft, die gesamte Berechnung noch einmal ausführen muss. Dank der Zero-Knowledge-Eigenschaft können außerdem bestimmte Daten, die bei der Berechnung verwendet werden, verborgen bleiben.

Die Abkürzung steht für Zero-Knowledge Scalable Transparent ARgument of Knowledge. Das klingt technisch, aber die Bestandteile lassen sich gut erklären:

• Zero-Knowledge: Du kannst beweisen, dass etwas stimmt, ohne die zugrunde liegenden geheimen Informationen offenzulegen.
• Scalable: Auch bei großen Berechnungen kann der Proof relativ effizient überprüft werden.
• Transparent: Es ist kein Trusted Setup nötig. Es muss also vorher keine spezielle Einrichtung stattfinden, bei der geheime Informationen entstehen, die danach sicher vernichtet werden müssen.
• Argument of Knowledge: Ein gültiger Proof zeigt, dass der Ersteller über die Informationen verfügt, die nötig sind, um die Berechnung korrekt auszuführen. Dadurch ist es extrem schwer, einfach so einen gültigen Proof zu fälschen.

In Krypto ist das vor allem nützlich, wenn große Berechnungen außerhalb der Blockchain ausgeführt werden. Ein System kann zum Beispiel viele Transaktionen off-chain verarbeiten und danach einen einzigen Proof an die Blockchain senden. Die Blockchain muss dann nicht jede Berechnung erneut ausführen, sondern prüft nur, ob der eingereichte Proof gültig ist.

Beispiel: Stell dir vor, Tausende Transaktionen werden außerhalb von Ethereum verarbeitet. Statt all diese Transaktionen erneut auf Ethereum auszuführen, kann ein System einen einzigen zk-STARK erzeugen, der beweist, dass der gesamte Batch nach den Regeln verarbeitet wurde. Ethereum muss anschließend nur diesen Proof prüfen.

Die Grundlage für STARKs wurde 2018 von Eli Ben-Sasson, Iddo Bentov, Yinon Horesh und Michael Riabzev beschrieben. Das System wurde entwickelt, um große Berechnungen effizient überprüfbar zu machen, ohne Trusted Setup.

Wichtigste Erkenntnisse

• Ein zk-STARK beweist, dass eine Berechnung korrekt ausgeführt wurde, ohne sie vollständig noch einmal zu machen.
• Zero Knowledge kann private Eingaben verborgen halten, ist aber nicht automatisch in jeder STARK-Anwendung vorhanden.
• STARKs brauchen kein Trusted Setup mit geheimen Parametern.
• Bei Rollups können viele Off-Chain-Transaktionen mit einem einzigen Validity Proof auf einer Blockchain überprüft werden.
• Die Technik kann sowohl für Blockchain-Scaling als auch für verifizierbare Berechnungen außerhalb von Krypto genutzt werden.

Wie funktioniert ein zk-STARK?

Ein zk-STARK wandelt eine große Berechnung in eine Form um, die viel effizienter überprüft werden kann. Die Partei, die die Berechnung ausführt, der Prover, erstellt danach einen kryptografischen Proof. Der Verifier prüft diesen Proof, ohne die gesamte ursprüngliche Berechnung noch einmal auszuführen.

Einfach gesagt: Der Prover erledigt die schwere Rechenarbeit und der Verifier kontrolliert mit einigen kryptografischen und mathematischen Prüfungen, ob das Ergebnis stimmt.

Im Groben funktioniert das so:

1. Die Berechnung wird in mathematische Regeln übersetzt: Zuerst wird festgelegt, welche Regeln jeder Schritt der Berechnung erfüllen muss. Bei STARKs geschieht das oft über eine sogenannte Algebraic Intermediate Representation (AIR). Du kannst dir das als mathematische Beschreibung davon vorstellen, was während der Berechnung erlaubt ist und was nicht.

2. Der Prover hält alle Rechenschritte fest: Der Prover führt die Berechnung aus und erstellt dabei eine sogenannte Execution Trace. Das kannst du dir als große Tabelle vorstellen, in der die verschiedenen Schritte der Berechnung festgehalten werden.

3. Die Daten werden kryptografisch festgehalten: Der Prover verarbeitet diese Daten mathematisch und hält sie mit kryptografischen Commitments fest, zum Beispiel mit einem Merkle Tree. Dadurch kann der Prover die Daten später nicht einfach verändern.

4. Der Verifier prüft eine Auswahl der Daten: Anschließend werden an unvorhersehbaren Stellen Kontrollen durchgeführt. Der Verifier prüft dabei unter anderem, ob die Daten mit den zuvor festgehaltenen Commitments übereinstimmen und ob die mathematischen Regeln der Berechnung eingehalten wurden. STARKs nutzen dafür unter anderem eine Technik namens FRI. Damit kann effizient geprüft werden, ob die verwendeten mathematischen Funktionen die richtige Form haben, ohne alle Daten einzeln zu kontrollieren.

5. Der Proof wird verifiziert: Wenn alle Kontrollen erfolgreich sind, hat der Verifier starke kryptografische Sicherheit, dass die Berechnung korrekt ausgeführt wurde. Die gesamte Berechnung muss dafür nicht noch einmal ausgeführt werden. Bei der Nutzung auf einer Blockchain kann der Prover den endgültigen Proof an einen Smart Contract senden. Dieser Contract prüft den Proof und akzeptiert das neue Ergebnis nur, wenn es gültig ist. StarkWare nutzt zum Beispiel On-Chain-Verifier auf Ethereum, um STARK-Proofs zu prüfen.

Beispiel: Stell dir vor, ein Rollup verarbeitet 1.000 Transaktionen außerhalb von Ethereum. Das Rollup führt alle Berechnungen aus und erstellt danach einen einzigen Proof, der zeigt, dass die Transaktionen nach den Regeln verarbeitet wurden. Ethereum muss diese 1.000 Transaktionen anschließend nicht alle noch einmal ausführen. Stattdessen prüft ein Smart Contract den Proof. Ist er gültig, kann der neue Zustand des Rollups akzeptiert werden.

Das macht zk-STARKs vor allem für Skalierbarkeit interessant: Viel Rechenarbeit kann außerhalb der Blockchain stattfinden, während die Blockchain trotzdem kryptografisch prüfen kann, ob das Ergebnis korrekt ist.

Was sind Zero-Knowledge-Proofs?

Ein Zero-Knowledge-Proof macht es möglich, zu beweisen, dass eine Aussage stimmt, ohne die geheimen Informationen hinter dieser Aussage preiszugeben.

Einfach gesagt: Der Prover zeigt dem Verifier, dass etwas korrekt ist, ohne alle zugrunde liegenden Daten teilen zu müssen.

Ein Zero-Knowledge-Proof hat drei wichtige Eigenschaften:

• Completeness: Wenn die Aussage stimmt und der Prover alles korrekt ausführt, kann der Verifier den Proof akzeptieren.
• Soundness: Jemand, der versucht, eine falsche Aussage zu beweisen, hat nur eine vernachlässigbar kleine Chance, damit durchzukommen.
• Zero Knowledge: Der Verifier erfährt keine zusätzlichen geheimen Informationen, außer dass die Aussage stimmt.

Beispiel: Ein System kann beweisen, dass ein Batch von Transaktionen nach allen Regeln verarbeitet wurde, ohne bestimmte private Daten aus diesen Transaktionen öffentlich zu machen.

Bei einem Rollup kann die öffentliche Aussage zum Beispiel sein, dass ein neuer State Root aus einer gültigen Reihe von Transaktionen hervorgeht. Welche Daten dabei verborgen bleiben, hängt davon ab, wie das Proof-System und die Anwendung gestaltet sind.

Wichtig zu wissen: Ein Validity Proof bietet nicht automatisch Privatsphäre. Ein System kann kryptografisch beweisen, dass Transaktionen korrekt verarbeitet wurden, während die Transaktionsdaten selbst weiterhin öffentlich sind. Für Privatsphäre muss die Zero-Knowledge-Eigenschaft bewusst in das System eingebaut werden.

Welche Rolle spielen STARKs?

STARKs sind das Proof-System, mit dem große Berechnungen effizient bewiesen und ohne Trusted Setup überprüft werden können.

Die Zero-Knowledge-Eigenschaft bestimmt dabei, welche Informationen verborgen bleiben können. Die STARK-Technik sorgt dafür, dass der Verifier effizient prüfen kann, ob die Berechnung nach den Regeln ausgeführt wurde.

Ein wichtiges Merkmal von STARKs ist, dass sie transparent sind. Es ist kein Trusted Setup nötig, bei dem vorher geheime kryptografische Parameter erzeugt werden, die danach sicher vernichtet werden müssen. Stattdessen stützt sich das System unter anderem auf öffentliche Zufälligkeit und kryptografische Hashfunktionen.

STARKs nutzen außerdem Techniken wie FRI, mit denen effizient geprüft werden kann, ob die mathematische Struktur hinter dem Proof stimmt.

Der Begriff Argument of Knowledge bedeutet, dass ein Prover nicht einfach so einen gültigen Proof erzeugen kann. Unter den Sicherheitsannahmen des Systems muss der Prover über die Informationen verfügen, die nötig sind, um die Berechnung korrekt auszuführen.

Wofür werden zk-STARKs verwendet?

zk-STARKs werden vor allem genutzt, um große Berechnungen außerhalb einer Blockchain auszuführen und anschließend mit einem einzigen kryptografischen Proof zu beweisen, dass das Ergebnis stimmt. Eine wichtige Anwendung dafür sind Validity Rollups.

Bei so einem Rollup werden viele Transaktionen außerhalb der Basisschicht verarbeitet. Danach wird ein Proof an die Blockchain gesendet, der zeigt, dass der neue Zustand aus dem alten Zustand nach den Regeln entstanden ist.

Das ist praktisch, weil die Basisschicht nicht alle Berechnungen noch einmal ausführen muss. Die Kosten eines einzelnen Proofs können so auf eine große Gruppe von Transaktionen verteilt werden.

Ein bekanntes Beispiel ist StarkEx. Dieses System nutzt STARK-Proofs, um große Mengen an Transaktionen für Anwendungen wie Handel, Zahlungen, Gaming und NFTs zu verarbeiten. Die Transaktionen werden gebündelt, danach wird ein Proof erstellt und von einem Smart Contract auf Ethereum überprüft.

STARK-Technologie kann auch außerhalb von Krypto genutzt werden. Grundsätzlich eignet sich die Technik für Situationen, in denen du beweisen willst, dass eine große Berechnung korrekt ausgeführt wurde, ohne dass der Prüfer alle Berechnungen noch einmal machen muss. Mit Zero Knowledge können dabei auch bestimmte zugrunde liegende Daten verborgen bleiben.

Ein Proof löst allerdings nicht alles. Bei Rollups bleibt zum Beispiel wichtig, wo die Daten der Transaktionen verfügbar sind. Ein gültiger Proof beweist, dass die Berechnung nach den festgelegten Regeln stimmt, sorgt aber nicht automatisch für die Verfügbarkeit aller Daten.

Welche Blockchains nutzen STARKs?

Das bekannteste Beispiel für ein Blockchain-Netzwerk, das STARK-Proofs nutzt, ist Starknet. Starknet ist eine Layer 2 auf Ethereum, die viele Transaktionen außerhalb von Ethereum verarbeitet und danach einen STARK-Proof an Ethereum sendet.

Ethereum prüft diesen Proof, um zu bestätigen, dass der neue Zustand von Starknet korrekt berechnet wurde. Dadurch muss Ethereum nicht alle Transaktionen, die auf Starknet stattfinden, einzeln noch einmal ausführen.

Auch StarkEx nutzt STARK-Proofs, aber StarkEx ist keine eigenständige Blockchain. Es ist eine Scaling-Lösung, mit der verschiedene Krypto-Anwendungen große Mengen an Transaktionen außerhalb von Ethereum verarbeiten und anschließend kryptografisch beweisen können, dass die Berechnungen korrekt ausgeführt wurden.

Ethereum selbst nutzt STARKs also nicht als eigenen Konsens- oder Transaktionsmechanismus. Das Netzwerk kann aber STARK-Proofs prüfen, die von Anwendungen und Layer-2-Netzwerken wie Starknet eingereicht werden.

Wichtig zu wissen: Die Nutzung von STARK-Proofs bedeutet nicht automatisch, dass Transaktionen privat sind. Starknet nutzt STARK Validity Proofs, um zu beweisen, dass Berechnungen korrekt ausgeführt wurden, während Zero-Knowledge-Privatsphäre eine separate Eigenschaft ist.

Was sind die Vorteile von zk-STARKs?

zk-STARKs machen es möglich, große Berechnungen viel effizienter zu überprüfen, als wenn jeder Teilnehmer alle Berechnungen noch einmal ausführen müsste.

Die wichtigsten Vorteile sind:

• Kein Trusted Setup: STARKs brauchen keine vorherige Zeremonie, bei der geheime kryptografische Informationen erzeugt und danach sicher vernichtet werden müssen.
• Effiziente Verifikation: Der Verifier kann eine große Berechnung prüfen, ohne jeden einzelnen Schritt noch einmal auszuführen.
• Geeignet für Skalierbarkeit: Ein Proof kann die korrekte Ausführung eines großen Batches von Transaktionen belegen, wodurch Blockchains mehr Transaktionen außerhalb der Basisschicht verarbeiten können.
• Möglichkeit zur Privatsphäre: Wenn Zero Knowledge in das System eingebaut ist, können bestimmte private Daten verborgen bleiben, während die Berechnung trotzdem überprüfbar ist.
• Hash-basierte Sicherheit: STARKs stützen sich für ihre Proving Layer auf kryptografische Hashfunktionen statt auf elliptische Kurvenpaarungen, die in vielen klassischen SNARK-Systemen verwendet werden.

Durch diesen hashbasierten Ansatz gelten STARKs auch oft als besser vorbereitet auf eine Zukunft mit leistungsfähigen Quantencomputern. Bekannte Quantenalgorithmen sind nämlich für viele elliptische-Kurven-Konstruktionen problematischer als für gut gewählte kryptografische Hashfunktionen.

Das bedeutet nicht, dass jede Anwendung mit STARKs automatisch vollständig quantensicher ist. Auch die verwendeten Hashfunktionen, Parameter, die Implementierung und andere kryptografische Bestandteile des Systems bleiben wichtig.

Was sind die Grenzen von zk-STARKs?

zk-STARKs haben auch Nachteile. Vor allem das Erstellen eines Proofs kann viel Rechenleistung und Speicher benötigen. Die schwere Arbeit verschwindet also nicht, sondern wird vor allem auf den Prover verlagert.

Außerdem sind STARK-Proofs in der Regel größer als Proofs vieler klassischer zk-SNARK-Systeme. Das kann bedeuten, dass mehr Daten verarbeitet werden müssen, wenn ein Proof auf einer Blockchain verifiziert wird.

Weitere Einschränkungen sind:

• Technische Komplexität: Entwickler müssen Berechnungen korrekt in eine Form übersetzen, die vom Proof-System überprüft werden kann.
• Kosten der Proof-Erstellung: Das Erstellen von Proofs kann viel Rechenleistung erfordern und damit Kosten verursachen.
• Der Proof prüft nur die festgelegten Regeln: Wenn die Anwendungslogik selbst einen Fehler enthält, beweist ein gültiger Proof nur, dass diese fehlerhaften Regeln korrekt befolgt wurden.
• Privatsphäre ist nicht automatisch vorhanden: Ein STARK-basiertes System kann Validity Proofs nutzen, ohne Transaktionsdaten geheim zu halten.

Kurz gesagt: Ein STARK-Proof kann sehr stark beweisen, dass eine bestimmte Berechnung nach den festgelegten Regeln ausgeführt wurde, aber nicht entscheiden, ob diese Regeln selbst gut entworfen sind.

Was ist der Unterschied zwischen zk-STARKs und zk-SNARKs?

zk-STARKs und zk-SNARKs haben dasselbe allgemeine Ziel: effizient zu beweisen, dass eine Berechnung korrekt ausgeführt wurde, ohne dass der Verifier die gesamte Berechnung noch einmal ausführen muss.

Der wichtigste Unterschied liegt in der kryptografischen Technik, die dafür verwendet wird.

Ein wichtiger Vorteil von zk-SNARKs ist, dass Proofs bei vielen Systemen sehr klein sein können. Dadurch sind sie attraktiv, wenn die Menge der Daten, die on-chain verifiziert werden muss, so klein wie möglich bleiben soll.

zk-STARKs haben meist größere Proofs, brauchen aber kein Trusted Setup und verwenden andere kryptografische Annahmen. Dadurch sind sie vor allem für große Berechnungen und Anwendungen attraktiv, bei denen Transparenz beim Setup wichtig ist.

Wichtig ist allerdings, nicht alle zk-SNARKs über einen Kamm zu scheren. zk-SNARK ist ein Sammelbegriff für mehrere Proof-Systeme. Nicht jeder SNARK nutzt dieselbe Kryptografie und nicht jede Variante erfordert die gleiche Art von Trusted Setup.

Auch bei beiden Techniken gilt: Ein Validity Proof bedeutet nicht automatisch Privatsphäre. Zero Knowledge muss Teil des jeweiligen Proof-Systems und der Anwendung sein.

Fazit

Ein zk-STARK ist eine kryptografische Technik, mit der du beweisen kannst, dass eine große Berechnung korrekt ausgeführt wurde, ohne dass der Verifier diese gesamte Berechnung noch einmal ausführen muss.

Das macht zk-STARKs vor allem für die Skalierbarkeit von Blockchains interessant. Rollups können große Mengen an Transaktionen außerhalb der Basisschicht verarbeiten und anschließend mit einem einzigen Proof zeigen, dass das Ergebnis stimmt.

Wichtige Vorteile sind der transparente Aufbau ohne Trusted Setup und die effiziente Verifikation großer Berechnungen. Dem stehen größere Proofs, viel Rechenarbeit für den Prover und technische Komplexität gegenüber.

zk-STARKs sind also vor allem eine Methode, große Berechnungen effizient und kryptografisch überprüfbar zu machen. Privatsphäre kann dabei Teil des Systems sein, ist aber nicht automatisch vorhanden.