zk-SNARKs vs. Zk-STARKs vs. BulletProofs? (Aktualisiert)

zk-S N ARKs , Zk-S T ARKs und BulletProofs sind drei wichtige Zero-Knowledge-Beweise, um Datenschutz für die Blockchain-Technologie bereitzustellen.

Wenn wir sie vergleichen können,

(1) Bulletproofs und Zk-S T ARKs erfordern keine vertrauenswürdige Einrichtung.

Im Gegensatz zu zk-S N ARKs , die eine vertrauenswürdige Einrichtung erfordern, die eine unangenehme Situation für sie schafft.

(2) Zcash , das zk-S N ARKs verwendet, kann die Betragsadresse zusammen mit Absender und Empfänger verbergen .

Mir ist noch nicht klar, ob es möglich ist, Absender und Empfänger durch Bulletproofs und Zk-S T ARKs zu verbergen .

(3) Anscheinend ist Zk-S T ARKs schneller als zk -S N ARKs ist schneller als Bulletproofs .

(4) Bulletproofs ist kürzer als zk-S N ARKs und Zk-S T ARKs .

Was sind im Allgemeinen die Hauptunterschiede (Vor- und Nachteile) zwischen diesen 3 wichtigsten Zero-Knowledge-Proof-Techniken?

Hinweis: Die Referenzen werden für die obigen Vergleiche verwendet:

https://crypto.stanford.edu/bulletproofs/

https://blockonomi.com/bullet-proofs/

https://nulltx.com/mit-review-acclaims-zk-snarks-but-zk-starks-may-steal-the-show/

Anmerkung 1: Der folgende Artikel vergleicht SNARKs mit STARKs: https://medium.com/coinmonks/zk-starks-create-verifiable-trust-even-against-quantum-computers-dd9c6a2bb13d

Anmerkung 2: Ich habe zk-SNARKs vs. Zk-STARKs vs. BulletProofs in der folgenden Abbildung verglichen. Jeder Kommentar zu diesem Vergleich ist willkommen:

Geben Sie hier die Bildbeschreibung ein

Antworten (3)

Einige Ihrer Punkte sind gültig (zB SNARKs und STARKS sind beide schneller als Bulletproofs), aber es gibt auch einige Fehler:

  1. STARKs sind nur auf Prüferebene schneller als SNARKs (1,6 s gegenüber 2,3 s), während das Protokoll für Prüfer etwas langsamer ist (16 ms gegenüber 10 ms).
  2. Wenn Sie mit kürzer die Größe in Byte meinen, sind Bulletproofs nur kleiner als STARKs (1.300 B vs. 45.000 B), während sie deutlich größer als SNARKs sind (1.300 B vs. 288 B).

Was sind die Hauptunterschiede (Vor- und Nachteile)?

Laut dem großartigen ZKP-Repo :

genialZKP

Laut Elena Nadilinskis Folien von Devcon4:

Leanthebean

Laut der Keynote von Zooko Wilcox (Zcash) von Devcon4:

zooko

Laut Eli-Ben Sassons (STARKware) Keynote auf der Technion Summer School (beachten Sie, dass dieses letzte Bild einen Subset-Sum-Löser misst, der wahrscheinlich komplexer ist als die Berechnungen im obigen Vergleich):

elb

Danke, könnten Sie bitte sagen, was "Größenordnungen zu groß" bedeuten? (in Ihrer dritten Abbildung.) Danke
Größenordnungen sind ungefähr die Potenzen von 10 in einer Zahl. Sie können diese leicht vergleichen, wenn Sie Zahlen in wissenschaftlicher Notation darstellen. Zum Beispiel: ``` 27 = 2,7 * 10^1 98 = 9,8 * 10^1 342 = 3,42 * 10^2 50000 = 5 * 10^4 ``` Die ersten beiden Zahlen, obwohl eine fast 4 mal so groß ist wie die anderen, liegen in der gleichen Größenordnung: Beide liegen zwischen 10 und 100. Die anderen sind allerdings größer. 50000 ist 3 Größenordnungen über 27, weil sein Exponent in wissenschaftlicher Schreibweise 4, und 27 ist 1.

Starks sind rundum fast besser als Snarks: Sie erfordern schwächere Krypto-Annahmen, benötigen kein vertrauenswürdiges Setup und sind postquantenresistent. Aber sie haben einen großen Nachteil, denn der Beweis ist riesig.

Für bestimmte Anwendungen, wie die, bei der ich arbeiten muss, ist das einfach nicht machbar. Wir mussten zwischen einem Snark-Proof in der Größenordnung von Hunderten von Bytes und einem STARK-Proof in der Größenordnung von Hunderten von Kilobytes wählen. Dieser einzelne Faktor war ein Killer für uns.

Die Verifizierungszeit ist bei Starks auch deutlich länger als bei Snarks. Bei ersterem wächst es in der Zeit O(poly log n), während es bei Snarks linear in der Eingabegröße ist , die gerade in komplexen Schaltungen nur eine kleine Konstante ist. Denken Sie daran, dass n hier die Anzahl der Tore ist.

Nehmen Sie zum Beispiel eine Schaltung, die beweist, dass Sie das Pre-Image eines bestimmten Hash-Werts kennen. Die Eingabe hat die Größe dieser Eingabe, die 32 Byte beträgt, wenn Sie SHA256 verwenden. Für diese Funktion wird die Anzahl der Gates jedoch in die Zehntausende gehen, und Sie können sehen, wie die Überprüfungszeit für den SNARK im Vergleich dazu vernachlässigbar ist.

Die Zahlen in den obigen Tabellen sind sehr irreführend. Sie sagen Ihnen nicht, welche Art von Schaltung Sie haben und wie groß n ist. Je nachdem, wie komplex Ihre Schaltung ist, können sie stark variieren. Ich bevorzuge die asymptotische Notation, und dafür gibt es in diesem Artikel eine gute Tabelle (Seite 3).

Vielen Dank, aber im STARKs-Papier wird erwähnt: "Für mittlere und große sequentielle Berechnungen ist unsere ZK-STARK-Verifiziererzeit besser als andere Lösungen " (Seite 12) (Link zum Papier: eprint.iacr.org /2018/046.pdf ). Bedeutet das, dass sie behaupten, dass die Überprüfungszeit von STARKs im Durchschnitt kürzer ist als die von SNARKs? Danke
Hallo, danke für die Frage. Die Antwort ist, ich weiß es nicht. Nach dem, was ich gelesen habe, haben die Autoren des Papiers einen ganz bestimmten Schaltungstyp ausgewählt (den DPM-Benchmark). Ich denke auch, dass sie ein bisschen unehrlich darin sind, wie sie die Verifizierungszeit messen, da sie die einmalige Einrichtung hinzufügen. Dazu gibt es keinen Grund, die Verifizierung und die Einrichtung sind voneinander unabhängige Prozesse. Wenn Sie die Grafik sehen, haben sie auch eine Zeile für libSnark ohne das Setup eingefügt und liegen deutlich unter der ZKStark-Linie.
Die asymptotische Notation spiegelt das Wachstum der Berechnung wider, wenn die Eingabegröße zunimmt, und spiegelt möglicherweise nicht immer die tatsächlichen Kosten wider. In vielen Fällen kann STARK SNARK in der Verifikationszeit übertreffen, da es einfache Feldarithmetik verwendet, während letzteres teure elliptische Kurvenpaare auf Erweiterungsfeldern verwendet.

AFAIK Bulletproofs sind kürzer, aber ihre Verifizierung dauert viel länger als Starks, wodurch sie nicht für Blockchain-TX-Verschleierung skalierbar sind.

Danke, ja, aber wie wäre es mit S T arks? wenn sie schneller sind als sowohl S N Arks als auch Bulletproofs und gleichzeitig kein vertrauenswürdiges Setup benötigen . Und was ist der Vorteil dieser Tatsache, dass Bulletproofs kürzer sind als S T arks? Danke
Laut Kommentar hier ( bitcoin.stackexchange.com/q/79423/41513 ) hängen Größe und Geschwindigkeit in sNarks und Bulletproofs von der Komplexität und Einfachheit der Aussage ab, aber ich bin mir nicht sicher, ob sTarks Größe und Geschwindigkeit unabhängig sind auf die Komplexität der Aussage. Danke
Die Geschwindigkeit der SNARK- Verifizierung ist im Gegensatz zu anderen Systemen nicht von der Schaltungsgröße abhängig.
zk-SNARKs vs. Zk-STARKs vs. BulletProofs? (Aktualisiert)
AntwortenHierDatenschutz-Bestimmungen1y, 1v