Vitalik Buterin über die Vitalik Buterin Blog
Dies ist ein Spiegelbild des Beitrags unter https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
Dies ist der dritte Teil einer Artikelserie, die erklärt, wie die Technologie hinter zk-SNARKs funktioniert; die vorherigen Artikel über Quadratische Rechenprogramme machen Elliptische Kurvenpaare sind Pflichtlektüre, und dieser Artikel setzt Kenntnisse beider Konzepte voraus. Grundkenntnisse darüber, was ZK-SNARKs sind und was sie tun, werden ebenfalls vorausgesetzt. Siehe auch Den Artikel von Christian Reitwiessner hier für eine weitere technische Einführung.
In den vorherigen Artikeln haben wir das quadratische Arithmetikprogramm vorgestellt, eine Möglichkeit, jedes Rechenproblem mit einer Polynomgleichung darzustellen, die für verschiedene Formen mathematischer Tricks viel besser geeignet ist. Wir haben auch elliptische Kurvenpaare eingeführt, die eine sehr begrenzte Form der homomorphen Einwegverschlüsselung ermöglichen, mit der Sie Gleichheitsprüfungen durchführen können. Jetzt beginnen wir dort, wo wir aufgehört haben, und verwenden elliptische Kurvenpaare zusammen mit einigen anderen mathematischen Tricks, um einem Prüfer zu ermöglichen, zu beweisen, dass er eine Lösung für einen bestimmten QAP kennt, ohne etwas anderes darüber preiszugeben tatsächliche Lösung.
Dieser Artikel konzentriert sich auf die Pinocchio-Protokoll von Parno, Gentry, Howell und Raykova aus dem Jahr 2013 (oft als PGHR13 bezeichnet); Es gibt einige Variationen des Grundmechanismus, sodass ein in der Praxis implementiertes ZK-SNARK-Schema möglicherweise etwas anders funktioniert, die Grundprinzipien jedoch im Allgemeinen gleich bleiben.
Lassen Sie uns zunächst auf die wichtigste kryptografische Annahme eingehen, die der Sicherheit des Mechanismus zugrunde liegt, den wir verwenden werden: die *Wissen-des-Exponenten* Annahme.
Grundsätzlich gilt: Wenn Sie ein Punktpaar � und � erhalten, wobei �⋅�=�, und Sie einen Punkt � erhalten, ist es nicht möglich, �⋅� zu finden, es sei denn, � ist auf irgendeine Weise von � „abgeleitet“. dass Sie wissen. Dies mag intuitiv offensichtlich erscheinen, aber diese Annahme kann tatsächlich nicht aus einer anderen Annahme (z. B. der diskreten logarithmischen Härte) abgeleitet werden, die wir normalerweise verwenden, wenn wir die Sicherheit elliptischer Kurven-basierter Protokolle nachweisen, und so beruhen zk-SNARKs tatsächlich auf einer gewissen Annahme Die Grundlage ist wackeliger als die der Elliptischen-Kurven-Kryptographie im Allgemeinen – obwohl sie immer noch stabil genug ist, dass die meisten Kryptographen damit einverstanden sind.
Lassen Sie uns nun darauf eingehen, wie dies genutzt werden kann. Angenommen, ein Paar Punkte (�,�) fällt vom Himmel, wobei �⋅�=�, aber niemand weiß, welchen Wert � hat. Nehmen wir nun an, ich erhalte ein Punktepaar (�,�), bei dem �⋅�=� gilt. Dann impliziert die KoE-Annahme, dass die einzige Möglichkeit, dieses Punktepaar zu bilden, darin bestand, � und � zu nehmen und beide mit einem Faktor r zu multiplizieren das weiß ich persönlich. Beachten Sie auch, dass dank der Magie elliptischer Kurvenpaarungen überprüft werden kann, dass �=�⋅� erfordert eigentlich kein Wissen � – Stattdessen können Sie einfach prüfen, ob �(�,�)=�(�,�) ist oder nicht.
Lasst uns etwas Interessanteres machen. Nehmen wir an, dass zehn Punktepaare vom Himmel fallen: (�1,�1),(�2,�2)…(�10,�10). In allen Fällen gilt ��⋅�=��. Angenommen, ich gebe Ihnen dann ein Punktepaar (�,�), wobei �⋅�=�. Was weißt du jetzt? Sie wissen, dass � eine lineare Kombination �1⋅�1+�2⋅�2+…+�10⋅�10 ist, wobei ich die Koeffizienten �1,�2…�10 kenne. Das heißt, die einzige Möglichkeit, zu einem solchen Punktepaar (�,�) zu gelangen, besteht darin, einige Vielfache von �1,�2…�10 zu nehmen, sie zu addieren und die gleiche Berechnung mit �1,�2... durchzuführen. �10.
Beachten Sie, dass Sie bei einem bestimmten Satz von �1...�10 Punkten, für den Sie möglicherweise Linearkombinationen überprüfen möchten, die zugehörigen �1...�10 Punkte nicht wirklich erstellen können, ohne zu wissen, was � ist und wenn Sie wissen, was � Dann können Sie ein Paar (�,�) mit �⋅�=� für jedes gewünschte � erstellen, ohne sich die Mühe machen zu müssen, eine lineare Kombination zu erstellen. Damit dies funktioniert, ist es daher unbedingt erforderlich, dass derjenige, der diese Punkte erstellt, vertrauenswürdig ist und tatsächlich löscht – sobald er die zehn Punkte erstellt hat. Daher kommt das Konzept eines „Trusted Setup“..
Denken Sie daran, dass die Lösung eines QAP eine Menge von Polynomen (�,�,�) ist, so dass �(�)⋅�(�)−�(�)=�(�)⋅�(�), wobei:
- � ist eine lineare Kombination einer Menge von Polynomen {�1…��}
- � ist die Linearkombination von {�1…��} mit den gleichen Koeffizienten
- � ist eine Linearkombination von {�1…��} mit den gleichen Koeffizienten
Die Mengen {�1…��}, {�1…��} und {�1…��} sowie das Polynom � sind Teil der Problemstellung.
In den meisten realen Fällen sind �,� und � jedoch extrem groß; Bei etwas mit vielen tausend Schaltungsgliedern wie einer Hash-Funktion können die Polynome (und die Faktoren für die Linearkombinationen) viele tausend Terme haben. Anstatt also den Beweiser die Linearkombinationen direkt bereitstellen zu lassen, werden wir den Trick verwenden, den wir oben eingeführt haben, um den Beweiser beweisen zu lassen, dass er etwas liefert, das eine Linearkombination ist, ohne jedoch etwas anderes preiszugeben.
Möglicherweise ist Ihnen aufgefallen, dass der obige Trick bei elliptischen Kurvenpunkten und nicht bei Polynomen funktioniert. Was also tatsächlich passiert, ist, dass wir dem vertrauenswürdigen Setup die folgenden Werte hinzufügen:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Sie können sich t als einen „geheimen Punkt“ vorstellen, an dem das Polynom ausgewertet wird. � ist ein „Generator“ (ein zufälliger elliptischer Kurvenpunkt, der als Teil des Protokolls angegeben wird) und �,��,�� und �� sind „Giftmüll“, Zahlen, die unbedingt um jeden Preis gelöscht werden müssen, andernfalls Wer sie hat, kann gefälschte Beweise anfertigen. Wenn Ihnen nun jemand ein Punktepaar �, � gibt, so dass �⋅��=� (zur Erinnerung: Wir brauchen �� nicht, um dies zu überprüfen, da wir eine Paarungsprüfung durchführen können), dann wissen Sie, was sie sind Sie erhalten eine lineare Kombination von ��-Polynomen, ausgewertet bei �.
Daher muss der Prüfer bisher Folgendes angeben:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Beachten Sie, dass der Prüfer �,��,�� oder �� nicht wirklich kennen muss (und auch nicht wissen sollte!), um diese Werte zu berechnen; vielmehr sollte der Prüfer in der Lage sein, diese Werte allein aus den Punkten zu berechnen, die wir dem vertrauenswürdigen Setup hinzufügen.
Der nächste Schritt besteht darin, sicherzustellen, dass alle drei Linearkombinationen die gleichen Koeffizienten haben. Dies können wir tun, indem wir dem vertrauenswürdigen Setup einen weiteren Satz von Werten hinzufügen: �⋅(��(�)+��(�)+��(�))⋅�, wobei � eine weitere Zahl ist, die als „toxisch“ betrachtet werden sollte Abfall“ gespeichert und verworfen, sobald die vertrauenswürdige Einrichtung abgeschlossen ist. Anschließend können wir den Prüfer eine lineare Kombination dieser Werte mit denselben Koeffizienten erstellen lassen und denselben Paarungstrick wie oben verwenden, um zu überprüfen, ob dieser Wert mit dem bereitgestellten „+“+ übereinstimmt.
Schließlich müssen wir beweisen, dass �⋅�−�=�⋅�. Das machen wir noch einmal mit einem Pairing-Check:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Wobei �ℎ=�⋅�(�). Wenn der Zusammenhang zwischen dieser Gleichung und �⋅�−�=�⋅� für Sie keinen Sinn ergibt, gehen Sie zurück und lesen Sie die Artikel über Paarungen.
Wir haben oben gesehen, wie man �,� und � in elliptische Kurvenpunkte umwandelt; � ist nur der Generator (d. h. das elliptische Kurvenpunktäquivalent der Zahl Eins). Wir können �⋅�(�) zum vertrauenswürdigen Setup hinzufügen. � ist schwieriger; � ist nur ein Polynom, und wir können im Voraus nur sehr wenig über die Koeffizienten jeder einzelnen QAP-Lösung vorhersagen. Daher müssen wir dem vertrauenswürdigen Setup noch weitere Daten hinzufügen; konkret die Reihenfolge:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
Im vertrauenswürdigen Zcash-Setup beträgt die Reihenfolge hier etwa 2 Millionen. Dies ist die Anzahl der Potenzen von �, die Sie benötigen, um sicherzustellen, dass Sie immer �(�) berechnen können, zumindest für die spezifische QAP-Instanz, die sie interessiert. Und damit kann der Prüfer dem Prüfer alle Informationen zur Verfügung stellen, die er für die endgültige Prüfung benötigt.
Es gibt noch ein weiteres Detail, das wir besprechen müssen. Meistens wollen wir nicht nur abstrakt beweisen, dass es eine Lösung für ein bestimmtes Problem gibt; Vielmehr möchten wir entweder die Richtigkeit einer bestimmten Lösung beweisen (z. B. beweisen, dass das Endergebnis mit 3x0fe73064 beginnt, wenn Sie das Wort „Kuh“ nehmen und es millionenfach mit SHA5 hashen) oder dass eine Lösung existiert, wenn Sie einschränken einige der Parameter. Beispielsweise möchten Sie bei einer Kryptowährungsinstanziierung, bei der Transaktionsbeträge und Kontostände verschlüsselt werden, nachweisen, dass Sie einen Entschlüsselungsschlüssel k kennen, sodass Folgendes gilt:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Die verschlüsselte old_balance
, tx_value
machen new_balance
sollten öffentlich angegeben werden, da dies die spezifischen Werte sind, die wir zu diesem bestimmten Zeitpunkt überprüfen möchten; Lediglich der Entschlüsselungsschlüssel sollte ausgeblendet werden. Um einen „benutzerdefinierten Verifizierungsschlüssel“ zu erstellen, der einer bestimmten Einschränkung der Eingaben entspricht, sind einige geringfügige Änderungen am Protokoll erforderlich.
Gehen wir nun einen Schritt zurück. Hier ist zunächst der vollständige Verifizierungsalgorithmus, mit freundlicher Genehmigung von Ben Sasson, Tromer, Virza und Chiesa:
Die erste Zeile befasst sich mit der Parametrisierung; Im Wesentlichen können Sie sich seine Funktion als die Erstellung eines „benutzerdefinierten Verifizierungsschlüssels“ vorstellen. für den konkreten Fall des Problems wobei einige der Argumente angegeben sind. Die zweite Zeile ist die Linearkombinationsprüfung für �,� und �; Die dritte Zeile ist die Prüfung, ob die Linearkombinationen die gleichen Koeffizienten haben, und die vierte Zeile ist die Produktprüfung �⋅�−�=�⋅�.
Insgesamt besteht der Verifizierungsprozess aus einigen Multiplikationen mit elliptischen Kurven (eine für jede „öffentliche“ Eingabevariable) und fünf Paarungsprüfungen, von denen eine eine zusätzliche Paarungsmultiplikation beinhaltet. Der Beweis enthält acht elliptische Kurvenpunkte: jeweils ein Punktpaar für �(�),�(�) und �(�), einen Punkt �� für �⋅(�(�)+�(�)+�(� )) und einen Punkt �ℎ für �(�). Sieben dieser Punkte befinden sich auf der ��-Kurve (jeweils 32 Bytes, da Sie die �-Koordinate auf ein einzelnes Bit komprimieren können), und in der Zcash-Implementierung befindet sich ein Punkt (��) auf der verdrehten Kurve in ��2 (64). Bytes), sodass die Gesamtgröße des Beweises ~288 Bytes beträgt.
Die beiden rechenintensivsten Teile bei der Erstellung eines Beweises sind:
- Dividieren Sie (�⋅�−�)/�, um � zu erhalten (Algorithmen basierend auf dem Schnelle Fourier-Transformation kann dies in subquadratischer Zeit tun, ist aber immer noch recht rechenintensiv)
- Durchführen der Multiplikationen und Additionen der elliptischen Kurve, um die Werte �(�),�(�),�(�) und �(�) und ihre entsprechenden Paare zu erstellen
Der Hauptgrund, warum die Erstellung eines Beweises so schwierig ist, ist die Tatsache, dass das, was in der ursprünglichen Berechnung ein einzelnes binäres Logikgatter war, zu einer Operation wird, die kryptografisch durch Operationen mit elliptischen Kurven verarbeitet werden muss, wenn wir daraus einen wissensfreien Beweis erstellen wollen . Diese Tatsache, zusammen mit der Superlinearität schneller Fourier-Transformationen, bedeutet, dass die Beweiserstellung für eine Zcash-Transaktion etwa 20–40 Sekunden dauert.
Eine weitere sehr wichtige Frage ist: Können wir versuchen, das vertrauenswürdige Setup etwas weniger vertrauenswürdig zu gestalten? Leider können wir es nicht völlig vertrauenswürdig machen; Die KoE-Annahme selbst schließt die Bildung unabhängiger Paare (��,��⋅�) aus, ohne zu wissen, was � ist. Wir können die Sicherheit jedoch erheblich erhöhen, indem wir die Mehrparteienberechnung verwenden, d .
Um ein Gefühl dafür zu bekommen, wie Sie dies tun würden, finden Sie hier einen einfachen Algorithmus, mit dem Sie einen vorhandenen Satz (�,�⋅�,�⋅�2,�⋅�3…) nehmen und Ihr eigenes Geheimnis „hinzufügen“ können Sie benötigen also sowohl Ihr Geheimnis als auch das vorherige Geheimnis (oder den vorherigen Satz Geheimnisse), um zu betrügen.
Der Ausgabesatz ist einfach:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Beachten Sie, dass Sie dieses Set erstellen können, wenn Sie nur das ursprüngliche Set und die s kennen, und dass das neue Set genauso funktioniert wie das alte Set, außer dass jetzt �⋅� als „Giftmüll“ anstelle von � verwendet wird. Solange Sie und die Person (oder die Personen), die das vorherige Set erstellt haben, es nicht versäumen, Ihren Giftmüll zu löschen, und später Absprachen treffen, ist das Set „sicher“.
Dies für das gesamte vertrauenswürdige Setup zu tun, ist deutlich schwieriger, da mehrere Werte beteiligt sind und der Algorithmus zwischen den Parteien in mehreren Runden durchgeführt werden muss. Es handelt sich um einen Bereich aktiver Forschung, um herauszufinden, ob der Mehrparteien-Berechnungsalgorithmus weiter vereinfacht werden kann und so gestaltet werden kann, dass weniger Runden erforderlich sind oder er parallelisierbarer gemacht werden kann, denn je mehr Sie tun können, desto mehr Parteien können in die vertrauenswürdige Einrichtungsprozedur einbezogen werden . Es ist durchaus nachvollziehbar, warum ein vertrauenswürdiger Aufbau zwischen sechs Teilnehmern, die sich alle kennen und miteinander arbeiten, manchen Leuten Unbehagen bereiten könnte, aber ein vertrauenswürdiger Aufbau mit Tausenden von Teilnehmern wäre kaum von gar keinem Vertrauen zu unterscheiden – und wenn man wirklich paranoid ist , können Sie selbst am Einrichtungsvorgang teilnehmen und sicherstellen, dass Sie Ihren Wert persönlich gelöscht haben.
Ein weiterer Bereich aktiver Forschung ist die Verwendung anderer Ansätze, die nicht auf Paarungen und das gleiche vertrauenswürdige Setup-Paradigma zurückgreifen, um dasselbe Ziel zu erreichen; sehen Eli ben Sassons jüngste Präsentation für eine Alternative (aber seien Sie gewarnt, sie ist mindestens so mathematisch kompliziert wie SNARKs!)
Besonderer Dank geht an Ariel Gabizon und Christian Reitwiessner für die Rezension.
- SEO-gestützte Content- und PR-Distribution. Holen Sie sich noch heute Verstärkung.
- PlatoData.Network Vertikale generative KI. Motiviere dich selbst. Hier zugreifen.
- PlatoAiStream. Web3-Intelligenz. Wissen verstärkt. Hier zugreifen.
- PlatoESG. Kohlenstoff, CleanTech, Energie, Umwelt, Solar, Abfallwirtschaft. Hier zugreifen.
- PlatoHealth. Informationen zu Biotechnologie und klinischen Studien. Hier zugreifen.
- BlockOffsets. Modernisierung des Eigentums an Umweltkompensationen. Hier zugreifen.
- Quelle: Datenintelligenz von Platon.