Eine ausführliche Analyse der vollständigen Sicherheit von STARK

Artikel: Sicher und gesund – Ein tiefer Einblick in die STARK-Sicherheit
Übersetzung und Korrekturlesen: „Starknet Chinese Community“
Ausgewählte Kurzinformationen
Nicht-interaktives STARK wird von Interactive Oracle Proofs (IOPs) abgeleitet, die im stochastischen Oracle-Modell zu nicht-interaktiven Proofs kompiliert werden.
Dieser Artikel erläutert die neuesten Aktualisierungen der ethSTARK-Dokumentation und bietet eine umfassende und detaillierte Analyse der Sicherheit des ethSTARK-Protokolls im Random-Oracle-Modell.
Ausführliche Erklärung der STARK-Sicherheit
Das STARK-Beweissystem oder skalierbare transparente Wissensargument ist ein leistungsstarkes Werkzeug für die Rechenintegrität: Es ermöglicht eine vertrauenswürdige Überprüfung der Richtigkeit von Berechnungen, die an öffentlichen Daten durchgeführt werden. In diesem Artikel werden wir uns mit der Sicherheit befassen, die STARK-Beweise bieten, sie definieren und Techniken zum Nachweis der Sicherheit von Schemata untersuchen.
(Lesen Sie Abschnitt 6 der ethSTARK-Dokumentation (Version 1.2) für Einzelheiten sowie die wichtige und umfassende unabhängige Arbeit zu diesem Thema von Block et al.)
Was wollen wir mit Sicherheitsanalysen erreichen? Wir wollen „erfolgreiche Angriffe“ auf das STARK-System verhindern, die durch eine falsche Aussage und den von einem STARK-Validator als Reaktion auf diese (falsche) Aussage akzeptierten STARK-Beweis verursacht werden. Da Falschdarstellungen gefährlich sind und in allen Größen und Formen auftreten können, möchten wir vor ihnen allen sicher sein. Jede falsche Aussage, selbst so trivial wie 1+1=3, gilt in Kombination mit einem von einem STARK-Validator akzeptierten STARK-Beweis als erfolgreicher Angriff auf das System. (Für diejenigen mit einem Hintergrund in der Kryptographie könnte es interessant sein zu wissen, dass STARK auch strengere Sicherheitskonzepte wie Wissenszuverlässigkeit erfüllen kann, der Einfachheit halber konzentriert sich dieser Artikel jedoch auf den einfachen Fall der Zuverlässigkeit.)
Wie definieren wir formal die Sicherheit eines STARK-Systems? Wir stellen dies fest, indem wir den „Zuverlässigkeitsfehler“ analysieren. Der „Zuverlässigkeitsfehler“ misst grob die erwarteten „Kosten“, die ein Angreifer für einen erfolgreichen Angriff benötigt (d. h. einen STARK-Beweis für eine falsche Aussage finden, der von einem STARK-Validator akzeptiert wird). Mathematisch gesehen ist der Zuverlässigkeitsfehler eine Funktion (t), deren Eingabe der Zeitparameter t ist, der die Rechenzeit darstellt, die der Angreifer bereit ist, für den Start eines Angriffs aufzuwenden, und deren Ausgabe die Wahrscheinlichkeit ist, dass der Angriff des Angreifers erfolgreich sein wird (gefunden für). falsche Aussagen überzeugender Beweis). Je höher die „Kosten“ t sind, die der Angreifer bereit ist auszugeben, desto höher ist seine Erfolgswahrscheinlichkeit.
Bisher haben wir die Sicherheit von STARK als Funktion (t) definiert, was sich von der Art und Weise unterscheidet, wie Sicherheit täglich auf Krypto-Twitter diskutiert wird. Auf Twitter hören Sie vielleicht: „Diese Lösung verfügt über 96 Bit Sicherheit.“ Wie lässt sich das auf unsere Definition von Sicherheit übertragen? Darauf gibt es keine einheitliche Antwort, da die Menschen „x Bits an Sicherheit“ etwas anders verstehen:
Streng interpretiert bedeutet dies, dass für jedes t zwischen 1 und 2⁹⁶ der Zuverlässigkeitsfehler (t) 2⁹⁶ beträgt. Ein Angreifer, der für 2⁹⁶ oder weniger rennt, hat eine sehr geringe Erfolgswahrscheinlichkeit, weniger als 2⁹⁶, was weniger als 1 zu einer Milliarde mal 1 zu einer Milliarde ist.
Eine lockerere und vielleicht häufigere Interpretation ist, dass 96-Bit-Sicherheit bedeutet, dass es für jedes t einen Fall gibt, in dem t/(t) 2⁹⁶. Das bedeutet, dass die Erfolgswahrscheinlichkeit (umgekehrt) linear mit der Laufzeit ist. Hat der Angreifer eine Laufzeit von 2⁸⁶, dann beträgt seine Erfolgswahrscheinlichkeit höchstens 2¹⁰.
In diesem Artikel besprechen wir die zweite Option.
Von IOP bis STARK mit 96-Bit-Sicherheit
Wie beweisen wir also, dass eine Lösung über 96 Bit Sicherheit verfügt? Um diese Frage zu beantworten, müssen wir die übergeordnete Struktur verstehen, auf der STARK aufbaut. STARK besteht aus drei Hauptteilen: IOP (Interactive Oracle Proof), Merkle Tree und Fiat-Shamir Hash; unser Hauptaugenmerk liegt auf IOP. Sobald diese Komponenten spezifiziert sind, können wir sie kompilieren, um einen STARK zu erstellen. Wir werden diese Komponenten im Detail besprechen, einschließlich ihrer Bedeutung und ihrer Zusammengehörigkeit.
Die erste Komponente, die wir überprüfen werden, ist der IOP: Der IOP ähnelt einem standardmäßigen interaktiven Beweis, bei dem der Prüfer und der Prüfer mehrere Runden lang interagieren (wir beschränken uns auf öffentliche Münzprotokolle, bei denen der Prüfer nur zufällige Herausforderungen an den Prüfer sendet). Bei einem IOP liest der Prüfer die Nachricht des Prüfers nicht vollständig, sondern tastet stattdessen einen kleinen Teil der Bits aus der Nachricht jedes Prüfers ab. Aus diesem Grund erreicht das später kompilierte STARK seine Einfachheit.
Wie baue ich angesichts des IOP einen STARK daraus auf? Die Nachrichten des Prüfers können sehr lang sein (tatsächlich sind sie länger als die Berechnung selbst). Um diese Informationen zu komprimieren, verwenden wir Merkle-Bäume. Ein Merkle-Baum ist ein binärer Hash-Baum, in dem jeder Blattknoten eine Abfrage oder eine Antwort im IOP darstellt. Die Wurzeln sind das Versprechen der gesamten Botschaft. Wenn ein Validator einen bestimmten Ort in einer Nachricht lesen möchte, stellt der Prüfer den Wert dieses Orts und den Verifizierungspfad bereit. Der Validator kann diesen Pfad dann verwenden, um zu überprüfen, ob der Wert korrekt ist. Der IOP-Validator liest nur eine kleine Menge an Standortinformationen aus den Prüferinformationen. Daher können mithilfe von Merkle-Bäumen prägnante Protokolle (Protokolle mit geringem Kommunikationsvolumen) implementiert werden.
Kompressionsgeschosse
Wir können interaktives STARK wählen, aber um den Prozess der Generierung von STARK zu vereinfachen, wählen wir normalerweise nicht interaktives STARK, damit der Validator beim Erstellen von STARK nicht auf externe Informationen warten muss. Tatsächlich werden derzeit alle STARK-Systeme auf diese Weise bereitgestellt und das ethSTARK-Protokoll ist auf diese Weise aufgebaut. Nicht-interaktive STARKs sind auch ein Sonderfall transparenter SNARKs (transparent bedeutet, dass für ihre Instanziierung kein vertrauenswürdiges Setup erforderlich ist; „Arthur Merlin Protocol“ oder „Public Coin IOP“). Zu diesem Zweck besteht der letzte Schritt darin, den Fiat-Shamir-Algorithmus anzuwenden, um mehrere Interaktionsrunden in einer einzigen Nachricht zu komprimieren, was wir als STARK-Beweis bezeichnen. Die Fiat-Shamir-Transformation ist eine Methode zum Konvertieren eines interaktiven Protokolls in ein nicht interaktives Protokoll. Der Prüfer simuliert ein interaktives Protokoll, während er mit der Hash-Funktion kommuniziert. Um die zufällige Herausforderung für Runde i abzuleiten, hasht der Prüfer den Teildatensatz für Runde i und interpretiert die Ausgabe als nächste Herausforderung.
Dadurch wird sichergestellt, dass der Prüfer seine Antwort nicht ändern kann, nachdem die Herausforderung generiert wurde. Betrügenden Prüfern stehen jedoch einige neue Richtlinienmöglichkeiten zur Verfügung, die in interaktiven IOPs nicht verfügbar sind. Der Prüfer kann die Validator-Challenge neu generieren, indem er die letzten Prüferinformationen ändert, sodass er einen neuen Datensatz und damit eine neue Challenge erhält. Es stellt sich heraus, dass die Standardzuverlässigkeitskonzepte des IOP nicht ausreichen, um die Sicherheit des Fiat-Shamir-Umbaus nachzuweisen.
Nehmen Sie beispielsweise einen IOP von 96 Runden an und fügen Sie dem Validator den folgenden Hack hinzu: Wenn das erste Bit der Zufälligkeit des Validators in jeder der 96 Runden 0 ist, akzeptiert der Validator dies (ohne einen Beweis zu sehen). Wir können sehen, dass das Hinzufügen dieses Hacks zum Validator nur einen Term von 2⁹⁶ zum Zuverlässigkeitsfehler des IOP hinzufügt. Nach der Fiat-Shamir-Transformation kann ein Angreifer jedoch die Prüferinformationen leicht ändern, um sicherzustellen, dass jeder Hash-Wert mit 0 beginnt, und so das System in sehr kurzer Zeit kompromittieren. Seien Sie versichert, dieses schlimme Szenario ist nur ein theoretisches Beispiel und gilt nicht für eingesetzte STARKs. Werfen wir also einen Blick darauf, warum unser STARK doch sicher ist. Kurz gesagt werden wir zeigen, dass für einen Angreifer, der höchstens t Schritte läuft, die Wahrscheinlichkeit eines erfolgreichen Angriffs höchstens (t) t 2⁹⁶ beträgt.
IOP und Runde-zu-Runde-Zuverlässigkeit
Die Sicherheit von STARK hängt von den zugrunde liegenden IOPs ab. Aber was bedeutet es für einen IOP, über 96 Bit Sicherheit zu verfügen? Laut Standarddefinition weist IOP einen Zuverlässigkeitsfehler von 2⁹⁶ auf: Dies bedeutet, dass die Wahrscheinlichkeit, dass ein Angreifer (unabhängig von der Laufzeit) einen Validator täuschen kann, höchstens 2-96 beträgt. Wie wir bereits besprochen haben, ist die Zuverlässigkeit des IOP jedoch nur eine der drei Komponenten, was nicht ausreicht, um 96 Bit Sicherheit aus einem STARK zu erreichen, der aus allen drei Schritten kompiliert wurde. Im Gegensatz dazu wird die Sicherheit von kompiliertem STARK unter der Annahme nachgewiesen, dass STARK einen runden 96-Bit-Zuverlässigkeitsfehler aufweist (manchmal wird eine ähnliche Definition namens State Recovery Reliability verwendet).
Intuitiv bedeutet „Round-by-Round Solidness“, dass jede Runde über 96 Bit Sicherheit verfügt, nicht nur das gesamte Protokoll. Genauer gesagt bezieht sich die Zuverlässigkeit von Runde zu Runde auf die Existenz eines Prädikats, das einen Teil des Datensatzes des Protokolls erhalten und uns sagen kann, ob dieser Datensatz „trügerisch“ ist: „leerer Datensatz“ ist nicht „trügerisch“ und Wenn Und der vollständige Datensatz ist nur dann „trügerisch“, wenn er vom Validator akzeptiert wird. Schließlich beträgt die Wahrscheinlichkeit, dass der Datensatz in der nächsten Runde „gefälscht“ wird, für jeden Teildatensatz, der den Validator nicht „fälscht“, höchstens 2⁹⁶. Wenn es ein Prädikat mit diesen Eigenschaften gibt, sagen wir, dass das Protokoll eine Runde-für-Runde-Zuverlässigkeit von 96 Bit hat (dieses Prädikat erfordert keine effiziente Berechnung).
In vielen Fällen analysiert man nur die Zuverlässigkeit des IOP und nicht seine Runde-zu-Runde-Zuverlässigkeit. Zugegebenermaßen fällt es uns schwer, uns Beispiele (abgesehen von hergestellten Beispielen) für IOPs vorzustellen, die eine Standardzuverlässigkeit, aber keine Rund-zu-Runde-Zuverlässigkeit aufweisen. Bei der Ableitung spezifischer Sicherheitsgrenzen können jedoch Unterschiede zwischen beiden auftreten und jedes Bit zählt. Um enge und spezifische Grenzen abzuleiten, ist daher eine gründliche Analyse der Runden-zu-Runden-Zuverlässigkeit des Augeninnendrucks erforderlich. Genau das machen wir mit dem FRI-Protokoll und dem ethSTARK IOP, auf dem STARK IOP basiert. Die Analyse selbst ist alles andere als trivial und würde den Rahmen dieses Artikels sprengen. Mit der neuen Analyse können wir präzise Parameter für unseren Beweis festlegen.
Die Rundum-Zuverlässigkeit gibt uns wirklich die Sicherheit, die wir brauchen. Der Prüfer kann die Herausforderung mehrmals neu generieren, aber wir wissen, dass die Wahrscheinlichkeit, einen betrügerischen Datensatz zu generieren, in jeder Runde 2⁹⁶ beträgt. Wenn der Prüfer also t Mal hat (gemessen an der Anzahl der Hash-Aufrufe), kann er es versuchen die meisten t-mal, um einen irreführenden Datensatz zu erhalten, was seine Erfolgswahrscheinlichkeit auf (t) t 2⁹⁶ begrenzt.
Fügen Sie alle Fehler hinzu
Damit all dies zutrifft, müssen wir schließlich sicherstellen, dass der Prüfer den Merkle-Baum nicht manipulieren kann. Wir können zeigen, dass der Prüfer im Merkle-Baum nicht schummeln kann, solange er keine Kollisionen in der Hash-Funktion findet. Die Wahrscheinlichkeit, dass ein Angreifer mithilfe von t-Aufrufen (zufällige Hash-Funktion) eine Kollision findet, beträgt höchstens t2/2, was der Ausgabelänge der Hash-Funktion entspricht (verursacht durch das „Geburtstagsparadoxon“). Deshalb müssen wir festlegen Hash-Funktion Die Länge ist doppelt so groß wie die erforderliche Sicherheit. Wenn wir also eine Hash-Funktion mit einer Ausgabelänge von 192 und einem IOP mit einer Runden-zu-Runden-Zuverlässigkeit von 96 Bit haben, erhalten wir einen kompilierten STARK, der zuverlässig ist. Der lineare Fehler (t )=t2-⁹⁶ + t2 2¹⁹⁶. Da t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, hat dieses Schema 95 Bits Sicherheitsgeschlecht.
Zusammenfassen
Zusammengenommen bietet STARK eine leistungsstarke Methode zur vertrauenswürdigen Überprüfung der Richtigkeit von Berechnungen, die anhand öffentlicher Daten durchgeführt werden. Die Sicherheit von STARK wird normalerweise anhand des „Zuverlässigkeitsfehlers“ gemessen, der die Wahrscheinlichkeit darstellt, dass ein Angreifer erfolgreich eine falsche Aussage macht und den Validator mit einem Beweis überzeugt. Um ein erforderliches Sicherheitsniveau, beispielsweise 96 Bit, zu erreichen, muss der zugrunde liegende IOP eine Runde-für-Runde-Zuverlässigkeit erfüllen, um sicherzustellen, dass in jeder Runde ein hohes Sicherheitsniveau aufrechterhalten wird. Wir haben die Runden-zu-Runden-Zuverlässigkeit der IOPs, auf denen unser STARK basiert, analysiert, um spezifische Sicherheitsgrenzen abzuleiten.