SNARK Sicherheit und Leistung

Ein SNARK (Succinct Non-interactive Argument of Knowledge) ist ein kryptografisches Werkzeug, das spannende neue Möglichkeiten im Systemdesign eröffnet, insbesondere in dezentralisierten Umgebungen. SNARKs ermöglichen die Verarbeitung von Daten durch nicht vertrauenswürdige Stellen, die dann nachweisen können, dass die Daten gültig sind und korrekt verarbeitet wurden. Ein naiver Weg, dies zu beweisen, wäre, die Daten zu veröffentlichen, damit jeder, der möchte, ihre Gültigkeit überprüfen und direkt verarbeiten kann. 

Ein SNARK erzielt den gleichen Effekt, jedoch zu geringeren Kostens an die Validierer. Beispielsweise verarbeitet ein Rollup-Dienst in einem verifizierbaren Layer-Two-Rollup (L2) Blockchain-Transaktionen. Der Dienst postet regelmäßig die Kontostände seiner Benutzer in der Layer-One-Blockchain. Jedes Mal, wenn es eine Aktualisierung der Salden veröffentlicht, hängt es einen SNARK-Beweis an, dass es eine Folge gültiger Transaktionen kennt, die die alten Kontosalden in die aktualisierten geändert haben. Auf diese Weise müssen Blockchain-Validatoren weder die harte Arbeit der Überprüfung der Transaktionsgültigkeit (z. B. Überprüfung einer digitalen Signatur für jede Transaktion) noch die Transaktionen explizit verarbeiten, um die aktualisierten Salden zu berechnen.  

My previous post konzentrierte sich auf die Leistung von SNARK-Prüfern – die primäre Determinante der SNARK-Anwendbarkeit. Während das Ausführen eines SNARK-Provers rechenintensiv sein kann, so dass es unmöglich ist, einen Beweis für umfangreiche Berechnungen zu generieren, ist die SNARK-Verifizierung in der Regel weitaus billiger als die direkte Überprüfung und Verarbeitung von Daten. Die Kosten für die SNARK-Verifizierung variieren jedoch erheblich. Dieser Beitrag packt diese Kosten aus und vergleicht die Sicherheitseigenschaften verschiedener SNARKs. 

Insbesondere erkläre ich, dass bei praktischen SNARKs mit plausibler Post-Quantum-Sicherheit (PQ-SNARKs) ein erhebliches Spannungsverhältnis zwischen Sicherheits- und Verifizierungskosten besteht. Darüber hinaus wird dieses Spannungsverhältnis derzeit in einigen Fällen zugunsten der Verifizierungskosten gegenüber der Sicherheit aufgelöst.

Damit SNARKs ihr Potenzial ausschöpfen können, müssen die bereitgestellten Systeme sicher sein und die Benutzer müssen sich auf ihre Sicherheit verlassen können. Ich beschließe den Beitrag, indem ich einfache Maßnahmen vorschlage, die die web3-Community ergreifen kann, um sicherzustellen, dass diese Eigenschaften langfristig erhalten bleiben. 

Quantitative Sicherheitsmaßnahmen 

Ein SNARK ist sicher, wenn es rechnerisch nicht möglich ist, einen überzeugenden Beweis für eine falsche Aussage zu erbringen. Im Zusammenhang mit L2-Rollups würde ein Angreifer, der meine Gelder stehlen möchte, beispielsweise eine falsche Aussage des Formulars beweisen wollen: „Ich kenne eine digital signierte Transaktion, die alle Vermögenswerte von Justin auf mein eigenes Konto überträgt.“ 

Das Sicherheitsniveau eines SNARK wird am Arbeitsaufwand gemessen, der aufgewendet werden muss, um einen überzeugenden Beweis für eine falsche Aussage zu finden. Ähnlich wie bei anderen kryptografischen Primitiven wie digitalen Signaturen wird der Logarithmus dieses Arbeitsaufwands als „Sicherheitsbits“ bezeichnet. Beispielsweise bedeuten 30 Sicherheitsbits, dass 2³⁰ ≈ 1 Milliarde „Arbeitsschritte“ sind erforderlich, um den SNARK anzugreifen. Dies ist von Natur aus ein ungefähres Maß für die Sicherheit in der realen Welt, da der Begriff eines Arbeitsschritts variieren kann und praktische Erwägungen wie Speicheranforderungen oder Möglichkeiten für Parallelität nicht berücksichtigt werden.

Und qualitative

Bits of Security ist a quantitativ Maß für die Sicherheit eines SNARK. SNARKs unterscheiden sich auch in ihrer qualitativ Sicherheitseigenschaften. 

Beispielsweise erfordern einige SNARKs eine vertrauenswürdige Einrichtungszeremonie, um einen strukturierten Prüfschlüssel zu generieren. SNARKs, die überhaupt kein vertrauenswürdiges Setup benötigen, werden aufgerufen transparent. 

Damit ein nicht transparenter SNARK sicher ist, muss sich normalerweise mindestens ein Teilnehmer an der Zeremonie ehrlich verhalten haben, was bedeutet, dass er eine „Falltür“ hergestellt und dann verworfen hat, die, wenn sie mit den Falltüren aller anderen Teilnehmer kombiniert wird, es einfach machen würde um überzeugende SNARK-„Beweise“ für jede falsche Aussage zu finden. Vertrauenswürdige Setups sind Sein Lauf mit Hunderten oder Tausenden von Teilnehmern, um diese Annahme so mild wie möglich zu machen. 

SNARKs unterscheiden sich auch in ihrer Anfälligkeit für Quantenangriffe. Insbesondere viele SNARKs (z. B. Wachstum16, PlönK, Marlin, Kugelsicherungen, Nova) beruhen auf der Annahme, dass diskrete Logarithmen schwer zu berechnen sind (und in einigen Fällen auch auf zusätzlichen Annahmen). Das Berechnen diskreter Logarithmen ist etwas, das Quantencomputer effizient leisten könnten. Daher sind diese SNARKs nicht postquantensicher (nicht-PQ). 

Während dringende Bemühungen im Gange sind, auf Post-Quantum umzustellen Verschlüsselungsschemata, wird dies in erster Linie durch die Notwendigkeit angetrieben, verschlüsselte Nachrichten viele Jahrzehnte in der Zukunft geheim zu halten. Ein Angreifer, der heute eine abgefangene Nachricht speichert und darauf wartet, dass ein Quantencomputer in, sagen wir, fünfzig Jahren eintrifft, kann den Computer verwenden, um die fünfzig Jahre alte Nachricht zu entschlüsseln. Ganz anders ist die Situation bei SNARKs. Die Verwendung von Nicht-PQ-SNARKs heute sollte die Sicherheit von Blockchains in fünfzig Jahren nicht gefährden, selbst wenn Quantencomputer bis dahin auf den Markt kommen. 

Polynomiale Verpflichtungen

Alle SNARKs verwenden ein kryptografisches Primitiv, das als a bekannt ist Polynomielles Commitment-Schema, und diese Komponente ist oft ein Leistungsengpass. (Details siehe meine previous post.) Darüber hinaus werden die Transparenz und die plausible Post-Quanten-Sicherheit eines SNARK ausschließlich durch das verwendete Polynom-Commitment-Schema bestimmt. 

Ein prominentes Beispiel sind die sog KZG-Polynomverpflichtungen, die von verwendet werden PlönK, Marlin, und viele andere. KZG-Verpflichtungen sind weder transparent noch postquantensicher. Andere Verpflichtungssysteme sind transparent, aber nicht nach Quanten, einschließlich Kugelsicherungen, Klippschliefer und Dory. 

Wieder andere Schemata sind sowohl transparent als auch plausibel post-quantum. Diese beinhalten Freitag, Licht, Ligero++, Bremsung und Orion. Alle diese Schemata basieren auf Fehlerkorrekturcodes. Hashing ist das einzige kryptografische Primitiv, das sie verwenden. Sie haben auch die folgende Eigenschaft gemeinsam: Die Verifizierungskosten (gemessen an der Anzahl der Hash-Auswertungen und Feldoperationen) wachsen linear mit der Anzahl der Sicherheitsbits.

Grob gesagt erreicht eine einzige „Iteration“ dieser Post-Quanten-Polynomverpflichtungen nur eine kleine Anzahl (z. B. 2–4) Bits an Sicherheit. Daher muss das Protokoll viele Male wiederholt werden, um das Sicherheitsniveau zu „verstärken“, wobei die Überprüfungskosten mit jeder Wiederholung steigen. Um die Verifizierungskosten in PQ-SNARKs (und damit die Gaskosten in Blockchain-Anwendungen) zu kontrollieren, werden Protokolldesigner daher dazu angeregt, das Sicherheitsniveau niedrig zu halten. 

Mit selten Ausnahmen, tritt diese Spannung zwischen konkreten Sicherheits- und Verifizierungskosten bei Nicht-PQ-SNARKs (transparent und nicht transparent gleichermaßen) nicht auf. Nicht-PQ-SNARKs verwenden Elliptische-Kurven-Gruppen, bei denen davon ausgegangen wird, dass diskrete Logarithmen schwer zu berechnen sind, und ihre Sicherheitsstufen von der verwendeten Gruppe bestimmt werden. Die Größe der geeigneten Elliptische-Kurven-Gruppe und somit die Kosten jeder Gruppenoperation wachsen mit dem gewünschten Sicherheitsniveau. Allerdings ist die Anzahl von Gruppenelementen in einem Beweis sind unabhängig von der Wahl der Gruppe. 

Bei PQ-SNARKs wächst nicht nur die Größe der Hash-Auswertungen linear mit der gewünschten Sicherheitsstufe, sondern auch die Anzahl der in den Nachweis einbezogenen und vom Verifizierer durchgeführten Auswertungen. 

Konkrete Prüferkosten und Sicherheit in eingesetzten SNARKs

Die konkreten Verifiziererkosten und Sicherheitsstufen der eingesetzten SNARKs variieren erheblich. Hier einige anschauliche Beispiele:

Verifiziererkosten 

My previous post zwei Beispiele für konkrete Verifizierungskosten genannt: PlönK Nachweise kosten für 300,000 Gas auf Ethereum zu überprüfen, während die Beweise von StarkWare etwa 5 Millionen Gas kosten. Die Beweise von StarkWare sind transparent und plausibel post-quantum, während die von PlonK dies nicht sind. Wie im Folgenden beschrieben, werden die Beweise von StarkWare jedoch auf einem viel niedrigeren Sicherheitsniveau ausgeführt als die Beweise von PlonK auf Ethereum.

Konkrete Sicherheit

Die einzige elliptische Kurve mit Ethereum-Vorkompilierungen heißt altbn128, also ist dies die Kurve, die alle Nicht-PQ-SNARKs verwenden, die auf Ethereum eingesetzt werden, einschließlich Aztecund zkSync's. Es wurde ursprünglich angenommen, dass diese Kurve – und damit auch die eingesetzten SNARKs, die sie verwenden – ungefähr 128 Bit Sicherheit bietet. Aber wegen verbesserte Angriffe (deren genaue Laufzeit ist schwer zu bestimmen), wird die Kurve heute allgemein als 100 bis 110 Bit Sicherheit angesehen. 

Es gibt EIPs für Berücksichtigung Vorkompilierungen für verschiedene Kurven einzuführen, von denen angenommen wird, dass sie fast 128 Bit Sicherheit bieten. Solche Kurven sind schon benutzt in den SNARKs von Nicht-Ethereum-Projekten, darunter ZCash, Algorand, Dfinity, Filecoin und Aleo. 

Im Gegensatz dazu wurden laut On-Chain-Daten die PQ-SNARKs von StarkWare (in seinem sogenannten SHARP-System, kurz für SHARed Prover) so konfiguriert, dass sie auf 80 Bit Sicherheit abzielen. Dieses Sicherheitsniveau gilt unter bestimmten Vermutungen über die statistische Solidität von FRI (auf die ich später in diesem Beitrag eingehen werde). 

Der Begriff „80-Bit-Sicherheit“ ist in diesem Zusammenhang vage, also lass es mich mal auspacken. Grob gesagt bedeutet dies, dass ein Angreifer durch Auswertung einer Hash-Funktion einen überzeugenden Beweis für eine Falschaussage erbringen kann 2⁸⁰ Zeiten (nämlich KECCAK-256, die von Ethereum verwendete Hash-Funktion). Genauer gesagt, ein Angreifer, der bereit ist, 2 auszuführen^k Hash-Auswertungen können mit einer Wahrscheinlichkeit von etwa 2 einen überzeugenden Beweis erbringen^k-80. Zum Beispiel mit 2⁷⁰ Hash-Auswertungen kann man mit einer Wahrscheinlichkeit von etwa 2 einen SNARK-„Beweis“ für eine Falschaussage finden^-10 = 1 / 1024. 

Dieser Begriff ist schwächer als das, was der Begriff „80-Bit-Sicherheit“ in anderen Kontexten bedeutet. Beispielsweise würde eine kollisionsresistente Hash-Funktion (CRHFs), die auf 80-Bit-Sicherheit konfiguriert ist, 160-Bit-Ausgaben erzeugen. Wenn die Hash-Funktion gut gestaltet ist, ist das schnellste Verfahren zur Kollisionsfindung das Geburtstags-Attacke, ein Brute-Force-Verfahren, das eine Kollision mit etwa 2 finden kann^160/2 = 2⁸⁰ Hash-Auswertungen. Allerdings mit 2^k Hash-Auswertungen findet der Birthday-Angriff eine Kollision mit einer Wahrscheinlichkeit von nur 2^2-160. 

Zum Beispiel 2⁷⁰ Hash-Auswertungen ergeben eine Kollision mit einer Wahrscheinlichkeit von 2^-20  ≈ 1/1,000,000. Dies ist viel kleiner als die Wahrscheinlichkeit von 1/1,000, dass ein Angreifer einen PQ-SNARK-Beweis fälscht, der auf 80 Bit Sicherheit konfiguriert ist. 

Dieser Unterschied kann die Attraktivität der Durchführung eines Angriffs drastisch verändern. Stellen Sie sich zur Veranschaulichung vor, ein Angreifer hat ein Budget von 100 US-Dollar, mit dem er 2 kaufen kann⁷⁰ Hash-Auswertungen. Und angenommen, sollte der Angreifer erfolgreich sein, beläuft sich die Auszahlung auf 200 Millionen Dollar. Der erwartete Wert des Angriffs auf einen PQ-SNARK, der auf 80 Bit Sicherheit konfiguriert ist, beträgt (1/1,000) * 200 Millionen US-Dollar oder 200 US-Dollar – das Doppelte der Kosten. Wenn die Erfolgswahrscheinlichkeit nur 1/1,000,000 wäre, wie bei einem CRHF, würde der erwartete Wert des Angriffs nur 200 $ betragen. 

Die beiden Begriffe „80-Bit-Sicherheit“ unterscheiden sich auch dramatisch in ihrer Robustheit gegenüber unabhängigen Angriffen. Angenommen, 1,000 unabhängige Parteien greifen jeweils den PQ-SNARK an, indem sie 2 ausführen⁷⁰ Hash-Auswertungen. Da jeder mit einer Wahrscheinlichkeit von etwa 1/1,000 erfolgreich ist, ist mindestens einer von ihnen ziemlich wahrscheinlich erfolgreich. Dies wäre nicht der Fall, wenn jeder mit einer Wahrscheinlichkeit von nur 1/1,000,000 erfolgreich wäre.

Es wird erwartet, dass sich gut gestaltete elliptische Kurvengruppen ähnlich wie CRHFs verhalten, mit geburtstagsähnlichen Angriffen wie z Pollards Rho-Algorithmus am bekanntesten zu sein. Dies bedeutet, dass in einer Gruppe, die 128 Bit Sicherheit bietet, 2^k Gruppenoperationen sollten eine Lösung für eine Instanz des Problems des diskreten Logarithmus mit einer Wahrscheinlichkeit von nur 2 liefern^2-256. Zum Beispiel 2⁷⁰ Gruppenoperationen würden einen diskreten Logarithmus mit nur einer astronomisch kleinen Wahrscheinlichkeit von 2 finden^-116. Darüber hinaus ist jede Gruppenoperation langsamer als eine CRHF-Auswertung. 

Wie viele Hash-Auswertungen sind heute machbar?

Im Januar 2020 kosteten Computer nur knapp 2⁶⁴ SHA-1-Auswertungen mit GPUs war $45,000. Das kostet 2⁷⁰ SHA-1-Bewertungen für GPUs bei einigen Millionen Dollar (vielleicht niedriger nach der Ethereum-Fusion, da der Übergang weg vom GPU-dominierten Proof-of-Work-Mining wahrscheinlich die Nachfrage nach GPU-Computing verringern und seine Kosten senken wird). 

Da Gültigkeits-Rollups bereits Hunderte von Millionen Dollar an Benutzergeldern speichern, kann das Finden eines überzeugenden Beweises für eine falsche Aussage viele Millionen Dollar Gewinn bringen. Die Konfiguration eines PQ-SNARK mit 80 Bit Sicherheit unter aggressiven Vermutungen lässt weniger als 10 Bit Spielraum zwischen profitablen Angriffen und der mutmaßlichen Sicherheit des PQ-SNARK.

Als weiterer Datenpunkt liegt die Netzwerk-Hash-Rate von Bitcoin derzeit bei etwa 2⁶⁴  Hash-Auswertungen pro Sekunde, was bedeutet, dass Bitcoin-Miner insgesamt 2 ausführen⁸⁰ SHA-256-Auswertungen alle 18 Stunden. Diese atemberaubende Zahl ist natürlich auf die enormen Investitionen in ASICs für das Bitcoin-Mining zurückzuführen. 

Unter der Annahme, sechs Bitcoin-Blöcke pro Stunde erstellt, und angesichts der aktuellen Blockbelohnung von 6.25 Bitcoin pro Block, diese 2⁸⁰ SHA-256-Evaluierungen kosten vermutlich weniger als 22,000 $ * 18 * 6 * 6.25 ≈ 15 Millionen $. Andernfalls wäre das Bitcoin-Mining zu den aktuellen Preisen nicht rentabel. 

Vorgeschlagene Maßnahmen für ein gesundes Ökosystem

Der springende Punkt bei der Verwendung von SNARKs in Rollups besteht darin, Blockchain-Skalierbarkeit zu erreichen, ohne dass Benutzer dem Rollup-Dienst blind vertrauen müssen. Da der Rollup-Service den Smart Contract geschrieben hat, der als SNARK-Verifizierer fungiert, muss die Öffentlichkeit in der Lage sein, den Vertrag einzusehen und zu bestätigen, dass er tatsächlich SNARK-Beweise der entsprechenden Aussagen überprüft. Eine öffentliche Prüfung des Smart Contracts kann auch erforderlich sein, um sicherzustellen, dass der Rollup-Dienst nicht in der Lage ist, seine eigenen Benutzer zu zensieren. Vorgeschlagene Methoden zur Zensurresistenz erfordern den Smart Contract des Rollups, damit Benutzer die Auszahlung ihrer Gelder erzwingen können, wenn der Rollup-Dienst ihre Transaktionen nicht verarbeitet. 

Angesichts der ausgeklügelten Natur dieser Protokolle erlegt dieses Paradigma der öffentlichen Kontrolle den Experten eine gewisse Belastung auf, die Sicherheit der bereitgestellten Verträge offen und ehrlich zu diskutieren. 

Aber bei PQ-SNARKs kann es sogar für Experten schwierig sein, das Sicherheitsniveau des eingesetzten Protokolls festzustellen, aus dem gleichen Grund, aus dem Sicherheit und Verifiziererleistung bei diesen SNARKs in Spannung stehen: Das Sicherheitsniveau (und die Verifiziererkosten) hängen von internen Parametern des ab SCHNARK. Und zumindest für StarkWare Smart Contracts, diese Parameter, called logBlowupFactor, proofOfWorkBits und n_Queries werden nicht direkt im Code des Smart Contracts angegeben, sondern als öffentliche Daten an den Smart Contract übergeben. Soweit ich weiß, ist der einfachste Weg, diese Parameter anhand von On-Chain-Informationen zu identifizieren, ein vierstufiger Prozess: 

1. sehen die passender Smart Contract auf einem Block-Explorer wie Etherscan, 
2. klicken Sie auf ein entsprechende „Verify Proof“-Transaktion, 
3. die Eingabedaten der Transaktion entschlüsseln und
4. finde heraus, wie es geht interpretieren die decodierten Eingabedaten, um die wichtigsten SNARK-Parameter zu lernen, die zusammen das Sicherheitsniveau bestimmen. 

Dieser letzte Schritt erfordert das Finden des geeigneten Solidity-Codes, der die Transaktion implementiert, was selbst eine verwirrende Aufgabe sein kann. (Als ich mich vorbereitete Umfrage Vorträge Bei Rollups in diesem Sommer konnte Etherscan die relevanten Eingabedaten für die SHARP-Überprüfungstransaktionen gemäß Schritt 2 oben entschlüsseln. Aber das scheint nicht mehr zu funktionieren.)

Vorschlag 1: Prüfung 

Vor diesem Hintergrund ist mein erster Vorschlag an die web3-Community, es viel einfacher zu machen, das Sicherheitsniveau von eingesetzten Post-Quantum-SNARKs zu überprüfen. Dies beinhaltet wahrscheinlich bessere Tools zum Verständnis von On-Chain-Daten und eine erhöhte Transparenz durch die Projekte selbst bei der Bekanntgabe dieser Parameter. 

Vorschlag 2: Stärkere Normen

80 Bit Sicherheit sind zu wenig, vor allem die schwache Version, bei der 2⁷⁰ Hash-Auswertungen reichen aus, um mit einer Wahrscheinlichkeit von etwa 1/1000 erfolgreich anzugreifen – umso mehr angesichts der langen Geschichte überraschender Angriffe auf kryptografische Primitive. Einer, der oben erwähnt wurde, sind bessere Angriffe auf Pairing-freundliche elliptische Kurven wie altbn128. Ein bekannteres Beispiel ist SHA-1, das auf 80 Bit Sicherheit standardisiert wurde, aber schließlich nur etwa 60 Bit erreichte. Angesichts dieser Geschichte sollten PQ-SNARK-Designer sich mehr als 10 Bits Spielraum lassen, wenn sie das Sicherheitsniveau konfigurieren, insbesondere wenn die Sicherheitsanalyse starke Vermutungen über die statistische Sicherheit relativ neuer Protokolle wie FRI beinhaltet.

Selbst für PQ-SNARKs können immer angemessene Sicherheitsniveaus erreicht werden, indem einfach die Verifizierungskosten erhöht werden. Beispielsweise würde eine Erhöhung der Sicherheit von SHARPs Prüfer von 80 auf 128 Bit (unter Vermutungen über die statistische Solidität von FRI) die Gaskosten ungefähr um den Faktor zwei erhöhen, von etwas über 5 Millionen auf etwas über 10 Millionen. Ohne Vermutungen über FRI würden die Gaskosten um den Faktor zwei auf über 20 Millionen steigen. 

Mein nächster Vorschlag ist daher, dass die web3-Community strengere Normen für angemessene Sicherheitsstufen für eingesetzte SNARKs entwickeln sollte. Meine persönliche Empfehlung wäre mindestens 100 Bit und mindestens 128, wenn die Sicherheit von SNARK auf nicht standardmäßigen Annahmen basiert. Ich bin nicht der Erste einen solchen Vorschlag machen.

Hier bin ich bereit, die bedingungslose Sicherheit als „Standardannahme“ einzustufen zufälliges Orakelmodell, wenn das zufällige Orakel im bereitgestellten SNARK mit einer Standard-Hash-Funktion wie KECCAK-256 instanziiert wird. Das zufällige Orakelmodell ist eine idealisierte Einstellung, die das Verhalten gut entworfener kryptografischer Hash-Funktionen erfassen soll. Es wird häufig verwendet, um die Sicherheit von PQ-SNARKs zu analysieren. 

Ein Beispiel für nicht standardmäßige Annahmen sind Vermutungen (unten beschrieben) bezüglich der quantitativen Solidität eines Protokolls wie FRI, entweder in einer interaktiven Umgebung oder als nicht interaktives Protokoll im zufälligen Orakelmodell.

SNARK-Designer sind auf viele aufregende Arten innovativ, von denen einige in Bezug auf die Sicherheit an die Grenzen gehen können – zum Beispiel durch die Verwendung von SNARK-freundlichen Hash-Funktionen, die nicht so viel Kryptoanalyse unterzogen wurden wie Standard-Hash-Funktionen. Ich fordere kein Ende dieser Bemühungen – ganz im Gegenteil. Aber diese Primitiven sollten auf Sicherheitsniveaus instanziiert werden, die bekannte, durchführbare Angriffe um weit über 10 Bit übersteigen. 

Rollups, die SNARKs verwenden, werden allgemein so beschrieben, dass sie die Sicherheit ihrer L1 erben. Dies ist jedoch ein schwieriger Fall, wenn sie auf viel niedrigeren Sicherheitsstufen konfiguriert sind als alle kryptografischen Primitiven, die von L1 verwendet werden. Da SNARKs zunehmend angenommen werden, sollten wir sicherstellen, dass wir sie auf eine Weise einsetzen, die mit der Art und Weise übereinstimmt, wie wir über sie sprechen. Solange SNARKs sorgfältig analysiert, angemessen konfiguriert und korrekt implementiert werden, sind sie so sicher wie alle heute verwendeten kryptografischen Primitiven. 

Eine Randbemerkung: Tauchen Sie noch tiefer in die Sicherheit von PQ-SNARK ein

Die 80 Sicherheitsbits in den PQ-SNARKs von StarkWare werden wie folgt berücksichtigt. Diese PQ-SNARKs verwenden ein Polynom-Commitment-Schema namens Freitag, und der SHARP-Verifizierer von StarkWare führt FRI mit 48 Bit Sicherheit unter einer Vermutung aus. Grob gesagt ist die Vermutung, dass ein einfacher Angriff auf die Solidität von FRI optimal ist. Bei diesem Angriff erzeugt ein betrügerischer Beweiser mit geringem Aufwand einen „FRI-Beweis“, der die zufällig ausgewählten Prüfungen des Verifizierers mit Wahrscheinlichkeit 2 besteht^-48. 

StarkWare kombiniert FRI mit einer Technik namens „Grinding“. Dies erfordert, dass der ehrliche Prüfer einen 32-Bit-Proof of Work erstellt, bevor er einen FRI-Proof erstellt. Der Vorteil des Grindens besteht darin, dass es die Arbeit, die ein betrügerischer Prüfer benötigt, um den oben erwähnten einfachen Angriff auf FRI durchzuführen, drastisch auf etwa 2 erhöht³² Hash-Auswertungen. 

Seit (in Erwartung) 2⁴⁸ Versuche des einfachen Angriffs sind notwendig, bevor einer von ihnen erfolgreich ist, der gesamte Arbeitsaufwand, den der betrügerische Beweiser leisten muss, um einen FRI-Beweis zu fälschen, beträgt ungefähr 2⁴⁸ * 2³² = 2⁸⁰ Hash-Auswertungen.

Lassen Sie uns zum Schluss auspacken, wie die 48-Bit-Sicherheit für FRI entstehen. Der FRI-Verifizierer stellt „Abfragen“ an das festgeschriebene Polynom. Die Kosten für die FRI-Verifizierung wachsen linear mit der Anzahl der Abfragen. Beispielsweise sind 36 FRI-Verifizierer-Abfragen ungefähr viermal so teuer wie 4 Abfragen. Aber mehr Abfragen bedeuten mehr Sicherheit. Die Anzahl der „Sicherheitsbits pro Abfrage“ hängt von einem anderen Parameter von FRI ab, der als Coderate bezeichnet wird. 

Insbesondere verwendet FRI den so genannten Reed-Solomon-Ratencode r, Wobei r ist immer eine Zahl zwischen 0 und 1. Die Kosten des FRI-Prüfers sind umgekehrt proportional zu r, also führt eine Rate von 1/16 zu einem Prover, der etwa viermal langsamer und platzintensiver ist als eine Rate von ¼. 

Der SHARP-Verifizierer wurde FRI mit einer Coderate von 1/16 und mit 12 Verifiziererabfragen ausgeführt.

StarkWare vermutet, dass jede FRI-Überprüfungsabfrage ein Protokoll hinzufügt₂(1 /r) bisschen Sicherheit. Unter dieser Vermutung ergeben 12 Verifier-Abfragen 12 * log₂(16) = 48 Sicherheitsbits.

Aktuelle Analysen stellen jedoch nur fest, dass jede Verifier-Anfrage etwas weniger als log hinzufügt₂(1/r^1/2) Bits der Sicherheit. 12 FRI-Verifier-Abfragen ergeben also nur weniger als 12 * log₂(4) = 24 Bit „nachweisbare“ Sicherheit. 

Ein Vorschlag zur Entschärfung des Spannungsfeldes zwischen Sicherheit und Leistung

Praktische PQ-SNARKs haben Prüferkosten, die linear mit der gewünschten Anzahl von Sicherheitsbits wachsen. Eine vielversprechende Technik, um diese Spannungen zu mindern, ist die SNARK-Komposition – die ich in meinem vorherigen Beitrag als Mittel zur Auflösung der Spannungen zwischen Prüfer- und Verifiziererkosten beschrieben habe, aber sie kann auch die Sicherheit ansprechen. 

Zwei Beispiele 

Polygon Hermez ist Komponieren von PQ-SNARKs mit PlonK. Die Idee ist, dass der Beweiser zuerst einen PQ-SNARK-Beweis π erzeugt. Wenn der PQ-SNARK so konfiguriert ist, dass er einen schnellen Nachweis und ein angemessenes Sicherheitsniveau hat, dann wird π groß sein. Also sendet der Beweiser π nicht an den Verifizierer. Stattdessen verwendet es PlonK, um zu beweisen, dass es π kennt. 

Dies bedeutet, dass PlonK auf eine Schaltung angewendet wird, die π als Eingabe verwendet und prüft, ob der PQ-SNARK-Verifizierer π akzeptieren würde. Da der PQ-SNARK polylogarithmische Verifikationskosten hat, wird PlonK auf eine kleine Schaltung angewendet, und daher ist der PlonK-Prüfer schnell. Da PlonK-Proofs klein und billig zu verifizieren sind, sind die Verifikationskosten gering. 

Leider zerstört die Verwendung von PlonK Transparenz und Post-Quanten-Sicherheit. Man kann stattdessen erwägen, den PQ-SNARK selbst anstelle von PlonK zu verwenden, um die Kenntnis von π zu beweisen (tatsächlich ist der von Polygon verwendete PQ-SNARK auf diese Weise selbst zusammengesetzt). 

In dieser zweiten Anwendung des PQ-SNARK kann zum Nachweis der Kenntnis von π das System so konfiguriert werden, dass es eine angemessene Sicherheit mit Nachweisen angemessener Größe erreicht, indem beispielsweise eine sehr kleine Coderate zur Verwendung in FRI ausgewählt wird. Der entscheidende Punkt ist, dass, während diese kleine Coderate schlecht für die Beweiserzeit ist, die zweite Anwendung des PQ-SNARK nur auf eine kleine Schaltung angewendet wird, so dass die gesamte Beweiserzeit immer noch klein sein sollte.

Unser theoretisches Verständnis der Sicherheit zusammengesetzter SNARKs lässt zu wünschen übrig. Es gibt jedoch keine bekannten Angriffe auf sie, die schneller sind, als einen der einzelnen SNARKs anzugreifen. Wenn wir beispielsweise einen PQ-SNARK mit PlonK erstellen, kennen wir keinen besseren Angriff, als entweder den PQ-SNARK anzugreifen (dh einen PQ-SNARK-Beweis π einer falschen Aussage zu finden) oder PlonK anzugreifen (dh Finden Sie einen PlonK-Beweis für die falsche Aussage „Ich kenne einen PQ-SNARK-Beweis π, den der Verifizierer akzeptiert hätte.“)

Das Zusammenstellen von SNARKs auf diese Weise wird immer beliebter, um die Leistung zu verbessern. Ich hoffe, dass Protokolldesigner es auch verwenden, um die Sicherheit zu verbessern.

***

Justin Thaler ist Associate Professor an der Georgetown University. Bevor er zu Georgetown kam, verbrachte er zwei Jahre als Research Scientist bei Yahoo Labs in New York, davor war er Research Fellow am Simons Institute for The Theory of Computing an der UC BeRkeley. 

Herausgeber: Tim Sullivan @tim_org

***

Die hier geäußerten Ansichten sind die der einzelnen zitierten Mitarbeiter von AH Capital Management, LLC („a16z“) und nicht die Ansichten von a16z oder seinen verbundenen Unternehmen. Bestimmte hierin enthaltene Informationen stammen aus Drittquellen, einschließlich von Portfoliounternehmen von Fonds, die von a16z verwaltet werden. Obwohl sie aus als zuverlässig erachteten Quellen stammen, hat a16z solche Informationen nicht unabhängig überprüft und gibt keine Zusicherungen über die dauerhafte Genauigkeit der Informationen oder ihre Angemessenheit für eine bestimmte Situation. Darüber hinaus kann dieser Inhalt Werbung von Drittanbietern enthalten; a16z hat solche Anzeigen nicht überprüft und unterstützt keine darin enthaltenen Werbeinhalte.

Dieser Inhalt wird nur zu Informationszwecken bereitgestellt und sollte nicht als Rechts-, Geschäfts-, Anlage- oder Steuerberatung angesehen werden. Sie sollten diesbezüglich Ihre eigenen Berater konsultieren. Verweise auf Wertpapiere oder digitale Vermögenswerte dienen nur der Veranschaulichung und stellen keine Anlageempfehlung oder ein Angebot zur Erbringung von Anlageberatungsdiensten dar. Darüber hinaus richtet sich dieser Inhalt nicht an Anleger oder potenzielle Anleger und ist nicht für die Verwendung durch diese bestimmt, und es darf unter keinen Umständen darauf vertraut werden, wenn eine Entscheidung getroffen wird, in einen von a16z verwalteten Fonds zu investieren. (Ein Angebot zur Investition in einen a16z-Fonds wird nur durch das Privatplatzierungsmemorandum, den Zeichnungsvertrag und andere relevante Unterlagen eines solchen Fonds abgegeben und sollte vollständig gelesen werden.) Alle erwähnten, erwähnten oder erwähnten Investitionen oder Portfoliounternehmen oder Portfoliounternehmen Die beschriebenen Investitionen sind nicht repräsentativ für alle Investitionen in von a16z verwaltete Vehikel, und es kann nicht garantiert werden, dass die Investitionen rentabel sind oder dass andere Investitionen in der Zukunft ähnliche Merkmale oder Ergebnisse aufweisen werden. Eine Liste der Investitionen von Fonds, die von Andreessen Horowitz verwaltet werden (mit Ausnahme von Investitionen, für die der Emittent a16z keine Genehmigung zur öffentlichen Offenlegung erteilt hat, sowie unangekündigte Investitionen in öffentlich gehandelte digitale Vermögenswerte) ist unter https://a16z.com/investments verfügbar /.

Die darin bereitgestellten Diagramme und Grafiken dienen ausschließlich zu Informationszwecken und sollten bei Anlageentscheidungen nicht als verlässlich angesehen werden. Die Wertentwicklung in der Vergangenheit ist kein Hinweis auf zukünftige Ergebnisse. Der Inhalt spricht nur zum angegebenen Datum. Alle Prognosen, Schätzungen, Prognosen, Ziele, Aussichten und/oder Meinungen, die in diesen Materialien geäußert werden, können ohne Vorankündigung geändert werden und können von den Meinungen anderer abweichen oder ihnen widersprechen. Weitere wichtige Informationen finden Sie unter https://a16z.com/disclosures.