Technische Ausrichtung: Analysieren Sie die Vor- und Nachteile von FPGA- und GPU-beschleunigtem, wissensfreiem Proof-Computing

Autor: Star Li
Dieser Artikel dient nur zu Lern- und Austauschzwecken in der Branche und stellt keine Investitionsreferenz dar. Wenn Sie ein Zitat benötigen, geben Sie bitte die Quelle an. Für einen Nachdruck wenden Sie sich bitte an das IOSG-Team, um eine Genehmigung und Anweisungen zum Nachdruck zu erhalten. Besonderer Dank geht an den Autor Star Li für den Inhalt!
Die Zero-Knowledge-Proof-Technologie wird zunehmend für Datenschutznachweise, Berechnungsnachweise, Konsensnachweise usw. eingesetzt. Auf der Suche nach mehr und besseren Anwendungsszenarien haben viele Menschen nach und nach entdeckt, dass die wissensfreie Leistung einen Engpass darstellt. Das Team von Trapdoor Tech begann im Jahr 2019 mit der umfassenden Forschung zur Zero-Knowledge-Proof-Technologie und erforschte effiziente Zero-Knowledge-Proof-Beschleunigungslösungen. GPU oder FPGA sind derzeit gängige Beschleunigungsplattformen auf dem Markt. Dieser Artikel beginnt mit der Berechnung von MSM und analysiert die Vor- und Nachteile von FPGA- und GPU-beschleunigten wissensfreien Berechnungen.
TL;DR
ZKP ist eine Technologie mit breiten Zukunftsaussichten. Immer mehr Anwendungen nutzen Zero-Knowledge-Proof-Technologie. Es gibt jedoch viele ZKP-Algorithmen und verschiedene Projekte verwenden unterschiedliche ZKP-Algorithmen. Gleichzeitig ist die Rechenleistung des ZKP-Beweises relativ schlecht. In diesem Artikel werden der MSM-Algorithmus, der Punktadditionsalgorithmus für elliptische Kurven, der Montgomery-Multiplikationsalgorithmus usw. im Detail analysiert und der Leistungsunterschied zwischen GPU und FPGA bei der Kurvenpunktaddition BLS12_381 verglichen. Im Allgemeinen sind in Bezug auf ZKP-Beweisberechnungen die kurzfristigen Vorteile der GPU relativ offensichtlich, wie z. B. hoher Durchsatz, hohe Kostenleistung, Programmierbarkeit usw. FPGA hat gewisse Vorteile hinsichtlich des Stromverbrauchs. Langfristig könnte es für ZKP-Berechnungen geeignete FPGA-Chips oder für ZKP angepasste ASIC-Chips geben.
 Der ZKP-Algorithmus ist komplex
ZKP ist die Sammelbezeichnung für Zero-Knowledge-Proof-Technologie (Zero Knowledge Proof). Es gibt zwei Hauptkategorien: zk-SNARK und zk-STARK. Die derzeit gängigen Algorithmen für zk-SNARK sind Groth16, PLONK, PLOOKUP, Marlin und Halo/Halo2. Die Iteration des zk-SNARK-Algorithmus erfolgt hauptsächlich in zwei Richtungen: 1/ob ein vertrauenswürdiges Setup erforderlich ist 2/die Leistung der Schaltungsstruktur. Der Vorteil des zk-STARK-Algorithmus besteht darin, dass er kein vertrauenswürdiges Setup erfordert, sondern der Verifizierungsberechnungsbetrag logarithmisch linear ist.
Im Hinblick auf die Anwendung des zk-SNARK/zk-STARK-Algorithmus sind die von verschiedenen Projekten verwendeten Zero-Knowledge-Proof-Algorithmen relativ verstreut. Bei der Anwendung des zk-SNARK-Algorithmus kann es zu immer mehr Anwendungen kommen, da der PLONK/Halo2-Algorithmus universell ist (kein vertrauenswürdiges Setup erforderlich).
 PLONK beweist Rechenaufwand
Nehmen Sie den PLONK-Algorithmus als Beispiel, um den Berechnungsumfang des PLONK-Beweises zu analysieren.
Der Berechnungsbetrag des PLONK-Proof-Teils besteht aus vier Teilen:
1/ MSM – Mehrfache Skalarmultiplikation. MSM wird häufig zur Berechnung polynomialer Verpflichtungen verwendet.
2/ NTT-Berechnung – Polynomtransformationen zwischen Punktwert und Koeffizientendarstellung.
3/ Polynomberechnungen – Polynomaddition, -subtraktion, -multiplikation und -division. Polynomauswertung (Auswertung) und so weiter.
4/ Schaltkreissynthese – Schaltkreissynthese. Dieser Teil der Berechnung hängt von der Größe/Komplexität der Schaltung ab.
Im Allgemeinen besteht der Berechnungsumfang des Schaltungssyntheseteils aus mehr Beurteilung und Schleifenlogik, der Parallelitätsgrad ist relativ gering und er eignet sich besser für die CPU-Berechnung. Im Allgemeinen bezieht sich die Zero-Knowledge-Proof-Beschleunigung im Allgemeinen auf die Berechnungsbeschleunigung der ersten drei Teile. Unter diesen weist MSM relativ den größten Rechenaufwand auf, gefolgt von NTT.
Was ist MSM
MSM (Multiple Scalar Multiplication) bezieht sich auf eine Reihe von Punkten und Skalaren auf der elliptischen Kurve und berechnet den Punkt, der dem Ergebnis der Addition dieser Punkte entspricht.
Beispiel: Gegeben sei eine Reihe von Punkten auf einer elliptischen Kurve:
Gegeben sei ein fester Satz elliptischer Kurvenpunkte aus einer angegebenen Kurve:
[G_1, G_2, G_3, ..., G_n]
Und Zufallskoeffizienten:
und ein zufällig ausgewähltes endliches Feldelement aus einem angegebenen Skalarfeld:
[s_1, s_2, s_3, ..., s_n]
MSM ist die Berechnung zum Erhalt des elliptischen Kurvenpunkts Q:
Q = \sum_{i=1}^{n}s_i*G_i
Die Industrie verwendet im Allgemeinen den Pippenger-Algorithmus, um MSM-Berechnungen zu optimieren. Schauen wir uns das schematische Diagramm des Prozesses des Pippenger-Algorithmus genauer an:
Der Berechnungsprozess des Pippenger-Algorithmus ist in zwei Schritte unterteilt:
1/ Scalar ist in Windows aufgeteilt. Wenn der Skalar 256 Bit und ein Fenster 8 Bit hat, wird der gesamte Skalar in 256/8=32 Fenster unterteilt. Jede Ebene von Window verwendet „Buckets“, um Zwischenergebnisse vorübergehend zu speichern. GW_x ist der Punkt des kumulativen Ergebnisses auf einer Ebene. Die Berechnung von GW_x ist ebenfalls relativ einfach. Jeder Skalar in einer Ebene wird nacheinander durchlaufen, und der Wert der Skalarebene wird als Index verwendet und der entsprechende G_x wird zum entsprechenden Buckets-Bit hinzugefügt. Tatsächlich ist das Prinzip relativ einfach. Wenn die Koeffizienten der Addition zweier Punkte gleich sind, addieren Sie zuerst die beiden Punkte und führen Sie dann eine skalare Addition für die beiden Punkte durch .
2/ Die von jedem Fenster berechneten Punkte werden durch Doppeladdierung akkumuliert, um das Endergebnis zu erhalten.
Der Pippenger-Algorithmus verfügt auch über viele Algorithmen zur Verformungsoptimierung. In jedem Fall ist die zugrunde liegende Berechnung des MSM-Algorithmus die Punktaddition auf der elliptischen Kurve. Unterschiedliche Optimierungsalgorithmen entsprechen unterschiedlichen Punktadditionszahlen.
 Elliptische Kurvenpunktzus
Auf dieser Website können Sie sich verschiedene Algorithmen zur Punktaddition auf elliptischen Kurven der „kurzen Weierstrass“-Form ansehen.
http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
Unter der Annahme, dass die projektiven Koordinaten der beiden Punkte (x1, y1, z1) bzw. (x2, y2, z2) sind, kann das Ergebnis der Punktaddition (x3, y3, z3) mithilfe der folgenden Berechnungsformel berechnet werden.
Der Grund für die detaillierte Beschreibung des Berechnungsprozesses besteht darin, zu zeigen, dass der gesamte Berechnungsprozess hauptsächlich aus ganzzahligen Operationen besteht. Die Bitbreite einer Ganzzahl hängt von den Parametern der elliptischen Kurve ab. Geben Sie die Bitbreiten einiger gängiger elliptischer Kurven an:
BN256 – 256 Bit BLS12_381 – 381 Bit BLS12_377 – 377 Bit
Beachten Sie insbesondere, dass es sich bei diesen ganzzahligen Operationen um Operationen auf dem Modulo-Feld handelt. Modulare Addition/modulare Subtraktion ist relativ einfach. Konzentrieren wir uns auf das Prinzip und die Implementierung der modularen Multiplikation.
Modul (Modulare Multiplikation)
Gegeben seien zwei Werte im Modulbereich: x und y. Modulare Multiplikationsberechnungen beziehen sich auf x*y mod p. Beachten Sie, dass die Bitbreite dieser ganzen Zahlen der der elliptischen Kurve entspricht. Der klassische Algorithmus zur modularen Multiplikation ist die Montgomery-Multiplikation. Vor der Montgomery-Multiplikation muss der Multiplikand in die Montgomery-Darstellung umgewandelt werden:
Die Formel für die Montgomery-Multiplikation lautet wie folgt:
Es gibt viele Implementierungsalgorithmen für die Montgomery-Multiplikation: CIOS (Coarsely Integrated Operand Scanning), FIOS (Finely Integrated Operand Scanning) und FIPS (Finely Integrated Product Scanning) usw. Dieser Artikel geht nicht auf die Details verschiedener Algorithmusimplementierungen ein, interessierte Leser können sie selbst studieren.
Um die Leistungsunterschiede zwischen FPGA und GPU zu vergleichen, wird die grundlegendste Methode zur Algorithmusimplementierung ausgewählt:
Einfach ausgedrückt kann der modulare Multiplikationsalgorithmus weiter in zwei Berechnungen unterteilt werden: Multiplikation großer Zahlen und Addition großer Zahlen. Nachdem Sie die Berechnungslogik von MSM verstanden haben, können Sie die Leistung der modularen Multiplikation (Durchsatz) auswählen, um die Leistung von FPGA und GPU zu vergleichen.
 Beobachten und nachdenken
Bei einem solchen FPGA-Design kann geschätzt werden, dass der gesamte VU9P einen Durchsatz an den Punkten der elliptischen Kurve BLS12_381 bereitstellen kann. Eine Punktaddition (add_mix-Methode) erfordert ungefähr 12 modulare Multiplikationen. Der Systemtakt des FPGA beträgt 450 MB.
Unter Verwendung desselben modularen Multiplikations-/Modulo-Additionsalgorithmus und unter Verwendung desselben Punktadditionsalgorithmus übersteigt der Punktadditionsdurchsatz des Nvidia 3090 (unter Berücksichtigung von Datenübertragungsfaktoren) 500 M/s. Natürlich umfasst die gesamte Berechnung eine Vielzahl von Algorithmen. Möglicherweise gibt es einige Algorithmen, die für FPGA geeignet sind, und einige Algorithmen, die für GPU geeignet sind. Der Grund für die Verwendung desselben Algorithmusvergleichs besteht darin, die Kernrechenfunktionen von FPGA und GPU zu vergleichen.
Basierend auf den obigen Ergebnissen fassen wir den Vergleich zwischen GPU und FPGA im Hinblick auf die ZKP-Beweisleistung zusammen:
 Zusammenfassen
Immer mehr Anwendungen nutzen Zero-Knowledge-Proof-Technologie. Es gibt jedoch viele ZKP-Algorithmen und verschiedene Projekte verwenden unterschiedliche ZKP-Algorithmen. Nach unserer praktischen Ingenieurserfahrung zu urteilen, ist FPGA eine Option, aber derzeit ist GPU eine kostengünstige Option. FPGA bevorzugt deterministisches Rechnen und bietet Vorteile bei Latenz und Stromverbrauch. Die GPU ist hochgradig programmierbar, verfügt über ein relativ ausgereiftes Hochleistungs-Computing-Framework, hat einen kurzen Entwicklungsiterationszyklus und bevorzugt Durchsatzszenarien.