Zero-Knowledge-Proofs: Was sind zk-STARKs und wie funktionieren sie?

1. Was ist es?

Das zk-STARK Proof of Reserves (PoR)-System nutzt die STARK-Theorie, eine komplexe mathematische Lösung. zk-STARK steht für: Zero-Knowledge Scalable Transparent Argument of Knowledge, eine kryptografische Beweistechnologie basierend auf Vitaliks Idee, um die Integrität und Vertraulichkeit von Berechnungen auf Blockchains durchzusetzen. In diesem Artikel erklären wir, wie es funktioniert, und erläutern das allgemeine mathematische Konzept. Wenn Sie jedoch tiefer eintauchen möchten, beginnen Sie hier oder hier.

Wie funktioniert es?

Abbildung 1. Ausführungs-Trace-Tabelle und Merkle-Baum, erstellt für zk-STARK PoR

Schritt 1: Bauliche Einschränkungen

Zum Nachweis der Haftung unserer Börse führen wir drei Ansprüche an:

Anspruch 1: Wir haben die Werte jeder Benutzerin und jedes Benutzers korrekt kumuliert, einschließlich des Werts jeder Kryptowährung und des Nettowerts jeder Benutzerin und jedes Benutzers

Anspruch 2: Die Börse hat keine virtuelle Benutzerin oder Benutzer gefälscht, deren oder dessen Nettowert negativ ist, um die Gesamtverbindlichkeit der Börse zu verringern (Eine einzelne Benutzerin oder ein einzelner Benutzer mit negativen Salden ist nur akzeptabel, wenn ihr oder sein Nettowert über 0 liegt)

Anspruch 3: Der Gesamtwert, den die Börse beansprucht, gilt für jede einzelne Benutzerin und jeden einzelnen Benutzer. Die Benutzerinnen und Benutzer sollten daher in der Lage sein, die Einbeziehung des Nettowerts in den Gesamtwert zu überprüfen

Um die oben genannten Behauptungen zu testen und zu verifizieren, müssen wir Einschränkungen erstellen wie:

Anspruch 1: Gesamtsaldo-Einschränkung (Einschränkung eines korrekten Gesamtsaldos)

uts: Benutzer-Trace-Größe, also die Anzahl der Trace-Zeilen, die in den Daten jeder Benutzerin oder jedes Benutzers enthalten sind.

Summe: Gesamtbenutzerguthaben

N: Anzahl der Benutzerinnen und Benutzer

Anspruch 2: Nicht-negative Einschränkung (Beschränkung des positiven Nettoeigenkapitals)

Anspruch 3: Einbeziehungsbeschränkung (Einschränkung der Einbeziehung des gesamten Kundenkontoguthabens)

Gemäß den oben genannten Einschränkungen erstellen wir eine Trace-Tabelle, um die Gesamtsalden und Nichtnegativitäten durch Stichprobenprüfungen festzulegen und zu überprüfen. So wird die Trace-Tabelle erstellt (für ein einfaches Beispiel 3 Benutzerinnen oder Benutzer, deren maximaler USD-Wert kleiner als 4^6 = 4096 ist):

1）Wir initialisieren eine Tabelle mit 32 Zeilen und 5 Spalten und geben die Werte und IDs der Benutzerin oder des Benutzers in die Zeile ein, wobei k % 8 = 6, und ist. Alle 8 Zeilen ergeben einen Block und Benutzer-Asset-Informationen sind jetzt in rückwärts von jedem Block enthalten. Die erste Benutzerin oder der erste Benutzer erhält virtuelle 0-Salden, sodass wir sie oder ihn veröffentlichen können, um zu beweisen, dass die Anhäufung von Werten nicht bei einem negativen Wert beginnt.

2）Wir sammeln nacheinander Benutzer-Assetwerte und tragen das Ergebnis in  Zeilen mit k % 8 = 7 und ein. Das sind die letzten Zeilen jedes Blocks

3）Wir dividieren den Gesamtwert jeder Benutzerin oder jedes Benutzers Zeile für Zeile durch 4 ab rückwärts von jedem Block. Wir tun dies, um den Nettowert der Benutzerin oder des Benutzers nicht negativ zu halten, indem wir prüfen, ob die ersten Zeilen für jeden Block Null sind. Wenn jemand einen negativen Nettowert hat, ist die erste Zeile des Blocks nicht Null, da sich ein negativer Wert (-x) im endlichen Feld als (p - x) herausstellt, was ein sehr großer positiver Wert ist.

4）Wir geben für jede Benutzerin und jeden Benutzer Zufallszahlen ein und füllen die Leerstellen in der Tabelle mit 0

Schritt 2: Polynomerweiterung niedrigen Grades Unter Verwendung der oben genannten Polynomeinschränkungen erhalten wir ein Berechnungsverfolgungspolynom der Länge uts * N. Aus Sicherheitsgründen führen wir die Festlegung des Polynoms in einem größeren Bewertungsbereich durch, mit dem Domänenverstärkungsfaktor als Erweiterungs_faktor.

Im obigen Fall könnten wir aus I(x) ein Polynom p(x) berechnen. Wenn wir einen Erweiterungs_faktor von 8 verwenden, berechnen wir weitere 32(8-1)* Punkte auf p(x).

Da sich zwei verschiedene Polynome mit dem Grad D höchstens D Punkte teilen, teilt sich ein Beispielpolynompaar mit einem gültigen Polynom (das die oben genannten Einschränkungen erfüllt) und einem falschen Polynom mit dem Grad D (das die oben genannten Einschränkungen nicht erfüllt) höchstens D Punkte. Das bedeutet, dass ein falsches Polynom eine Chance von hat eine Stichprobenprüfung zu bestehen. Wenn wir die Stichprobenprüfung n Mal durchführen, sinkt die Wahrscheinlichkeit auf .

Wir implementieren die Standarderweiterungs_faktor von 16 und die Stichprobenprüfung ist standardmäßig 16, sodass die Sicherheitsstufe 80 Bits beträgt.

Schritt 3: Polynom-Verpflichtung Wir berechnen den Hash-Wert der Berechnungsspur und den entsprechenden Benutzersaldo, die Benutzer-ID und den Wert des entsprechenden Einschränkungspolynoms für jede Zeile und generieren einen Merkle-Baum. Die Merkle-Wurzel ist der Bindungswert des Polynoms.

Schritt 4: Stichprobennachweis erstellen Unter Verwendung der Merkle-Wurzel als Zufallsquelle nehmen wir Stichproben aus den Daten. Um den Verlust von Berechnungs-Trace-Daten zu vermeiden, umgehen wir Daten mit einem Index von *k ** als Erweiterungs_faktor während der Stichprobe und generieren den Merkle-Proof-Pfad, der dem Stichprobenindex entspricht.

Wir führen Stichprobenprüfungen durch, um zu überprüfen, ob das festgelegte Polynom ein gültiges Polynom ist, das die in Schritt 1 aufgeführten Einschränkungen erfüllt. Wie in Schritt 2 angegeben, haben die Zeitpunkte der Stichprobenkontrollen Einfluss auf die Wahrscheinlichkeit, dass Manipulationen oder Eingriffe erfolgreich sind.

Schritt 5: Generieren eines Low-Grade-Proofs

Durch Stichprobenkontrolle können wir die Wahrscheinlichkeit einer erfolgreichen Manipulation oder eines Eingriffs kontrollieren. Es gibt jedoch die in Schritt 2 erwähnte Bedingung, dass wir sicherstellen müssen, dass der Grad des zu verifizierenden Polynoms nicht höher ist als der Grad eines gültigen Polynoms. Um die Beweiseffizienz zu verbessern, kombinieren wir alle Einschränkungspolynome linear zu einem Polynom und generieren dafür einen Beweis niedrigen Grades. Die Kombinationskoeffizienten werden ebenfalls unter Verwendung der Merkle-Wurzel als Zufallsquelle generiert.

Wenn wir beispielsweise beweisen möchten, dass p0(x), p1(x) und p2(x) nicht mehr als D Grad sind, können wir 2 Zufallskoeffizienten aus der in Schritt 3 generierten Merkle-Wurzel generieren und das lineare Polynom l(x) wie folgt berechnen:

k0 = Hash(Wurzel + „0“)
k1 = Hash(Wurzel + „1“)
l(x) = k0 * p0(x) k1 * p1(x) p2(x)

Wenn nachgewiesen werden kann, dass l(x) nicht mehr als D Grad hat, dann liegt die Wahrscheinlichkeit, dass der Grad von p0(x), p1(x) und p2(x) mehr als D beträgt, nahe bei 0

Schritt 6: Überprüfung des Gesamtsaldos Zunächst überprüfen wir den in Schritt 5 generierten Nachweis mit niedrigem Grad.

Anschließend wird eine weitere offene Überprüfung der in Schritt 4 generierten Stichprobendaten durchgeführt. Erstens, um zu überprüfen, ob die Daten mit der Polynomverpflichtung übereinstimmen, und zweitens, um zu überprüfen, ob die Daten die in Schritt 1 erstellten Einschränkungen erfüllen. Abschließend werden die Kombinationskoeffizienten des Testpolynoms niedrigen Grades überprüft.

Schritt 7: Benutzereinschlussnachweis erstellen Um zu beweisen, dass eine bestimmte Benutzerin oder ein bestimmter Benutzer in dem von der Börse beanspruchten Gesamtbetrag enthalten ist, stellen wir die berechnete Trace der Benutzerin oder des Benutzers, den Benutzersaldo, die Benutzer-ID und eine Zufallszahl entsprechend dem Benutzerindex bereit. Wir stellen auch den Merkle-Pfad bereit, der diesen Daten entspricht.

Schritt 8: Benutzerüberprüfung des Einschlussnachweises Die Benutzerin oder der Benutzer überprüft den Kontostand und die ID, berechnet den Hash-Wert der Daten, die dem Index entsprechen, und überprüft den Hash-Wert auf dem Blattknoten des Merkle-Baums mithilfe des bereitgestellten Merkle-Pfads.

**2. So führen Sie ** eine Selbstverifizierung des Proof of Reserves (PoR) durch?

2.1 Überprüfen Sie die zk-STARK-Einschlussbeschränkung

Verifizierungstheorie

Nach dem STARK-Verfahren berechnen wir die Ausführungs-Trace-Tabelle aller Benutzerressourcen wie unten beschrieben und hashen die Informationen jeder Benutzerin und jedes Benutzers als Trace-Tabelle, die zu einem Merkle-Baumblatt wird. Anschließend übergeben wir die Blätter an eine Merkle-Wurzel, die während jeder PoR-Prüfungsrunde veröffentlicht wird.

Um zu überprüfen, ob Ihre Assets im Stammverzeichnis enthalten sind, stellen wir Ihnen den Merkle-Pfad zur Überprüfung zur Verfügung. Sie können Ihr Blatt zunächst durch Hashing Ihrer Asset-Informationen berechnen und dann überprüfen, ob Ihr Blatt ein gültiges Blatt im von uns veröffentlichten Merkle-Baum und der Merkle-Wurzel ist.

In Abbildung 1 berechnet die Benutzerin oder der Benutzer mit der ID id_k beispielsweise hashk = hash("20" "15" "5" "id_k" "99821"). Die anderen Daten im roten quadratischen Rahmen sind die Merkle-Pfadüberprüfung. Für diese Überprüfung wird den Benutzerinnen und Benutzern ein Open-Source-Tool zur Verfügung gestellt.

Da es sich bei den Blättern des Merkle-Baums um Hashes handelt, werden keine Ihrer privaten Informationen an andere weitergegeben.

So verifizieren Sie:

1）Um zu verifizieren, ob der Vermögenssaldo Ihres Kontos als zk-STARK Merkle-Blatt enthalten ist, melden Sie sich bei Ihrem OKX-Konto an und besuchen Sie „Prüfungen“. um die letzten Audits anzuzeigen, klicken Sie auf „Details“, um Ihre Auditdaten anzuzeigen.

2） Die für die manuelle Verifizierung erforderlichen Daten erhalten Sie über die Schaltfläche „Daten kopieren“.

3） Nachdem Sie auf „Daten kopieren“ geklickt haben, öffnen Sie den Texteditor (z. B. Notepad/Windows-Editor), fügen die Daten ein und speichern den JSON-String als JSON-Datei. Die Datei muss mit dem Namen „_Aufnahme_Proof.json.“ enden Die JSON-Zeichenfolge enthält Ihren Kontostand und eine Momentaufnahme des Merkle-Pfads und speichert die Datei dann in einem neuen Ordner.

Der JSON-Text wird wie folgt angezeigt:

{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
"total_value": 138312291,
"BTC": 2152907,
"ETH": 909757,
"USDT": 2319557,
"random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
"merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"total_value": 2007657936,
"BTC": 18915744,
"ETH": 21522734,
"USDT": 21268768,
"random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
"bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43"
]
}
}

4）Laden Sie das OKX Open-Source-Verifizierungstool zk-STARKValidator herunter

5）Speichern Sie das OKX Open-Source-Verifizierungstool zk-STARKValidator und die JSON-String-Datei zusammen im neuen Ordner aus Schritt 3. In unserem Fall speichern wir das Tool und die Datendatei im Ordner „Downloads“ unter der Bezeichnung „proof-of-reserves“, wie unten dargestellt:

6）Öffnen Sie den zk-STARKValidator. Er führt die JSON-String-Datei, die Sie im Ordner gespeichert haben, automatisch aus.

7）Überprüfen Sie das Ergebnis

• Wenn die Verifizierung erfolgreich ist, wird das Ergebnis „Validierung der Einschlussbeschränkung bestanden“ angezeigt:

  

• Wenn die Verifizierung fehlschlägt, wird das Ergebnis „Validierung der Einschlussbeschränkung fehlgeschlagen“ angezeigt:

  

2.2 Überprüfen Sie den zk-STARK-Gesamtsaldo und die nicht-negative Einschränkung

So verifizieren Sie:

Um zu überprüfen und zu beweisen, dass die von uns angeblich gehaltenen Vermögenswerte wahr sind und keine Benutzerin und kein Benutzer über ein negatives Nettoeigenkapital verfügt, besuchen Sie unsere „Prüfdateien“ Seite, laden Sie die „zk-STARK“-Dateien unter Haftungsbericht herunter und speichern Sie diese dann in einem neuen Ordner.

Entpacken Sie die heruntergeladene Datei. Es wird ein Ordner „Summennachweisdaten“ angezeigt, der Tausende von Zweigordnern und einen Stammordner enthält. Jeder Ordner enthält zwei JSON-Dateien mit den Namen „sum_„proof.json“ und „sum_value.json‘-Dateien.

Laden Sie das OKX Open-Source-Verifizierungstool zk-STARKValidator herunter

Speichern Sie das OKX Open-Source-Verifizierungstool zk-STARKValidator und die JSON-String-Datei zusammen im erstellten Ordner aus Schritt 1. In unserem Fall speichern wir das Tool und die Datendatei im Ordner „Downloads“ unter der Bezeichnung „proof-of-reserves“, wie unten dargestellt:

Öffnen Sie den zk-STARKValidator. Er führt die „Summennachweisdaten“, die Sie im Ordner gespeichert haben, automatisch aus.

Überprüfen Sie das Ergebnis

Wenn die Verifizierung erfolgreich ist, wird das Ergebnis „Gesamtsumme und nicht-negative Einschränkungsvalidierung bestanden“ angezeigt:

Wenn die Verifizierung fehlschlägt, wird das Ergebnis „Gesamtsumme und nicht-negative Einschränkungsvalidierung fehlgeschlagen“ angezeigt: