Dovezi Zero-Knowledge: Ce sunt zk-STARK-urile și cum funcționează?

1. Ce este?

Sistemul zk-STARK Proof of Reserves (PoR – dovada rezervelor) folosește teoria STARK, o soluție matematică complexă. zk-STARK vine de la Zero-Knowledge Scalable Transparent Argument of Knowledge, o tehnologie de dovadă criptografică bazată pe ideea lui Vitalik și gândită să asigure integritatea și confidențialitatea calculelor pe blockchain. În acest articol vom prezenta modul său de funcționare și vom explica conceptul matematic general, dar dacă vă interesează să aprofundați subiectul, începeți aici sau aici.

Cum funcționează?

Figura 1. Tabelul de urmărire a execuției (trace table) și arborele Merkle construite pentru zk-STARK PoR

Pasul 1: construirea constrângerilor

Pentru a dovedi pasivele bursei noastre, formulăm trei afirmații:

Afirmația 1: Am acumulat corect valorile fiecărui utilizator, inclusiv valoarea fiecărei criptomonede și valoarea netă a fiecărui utilizator

Afirmația 2: Bursa nu a creat niciun utilizator virtual cu valoare netă negativă pentru a reduce pasivele totale ale bursei (un utilizator individual cu solduri negative este acceptabil numai dacă valoarea netă a acestuia este mai mare de 0)

Afirmația 3: Valoarea totală comunicată de bursă ia în considerare fiecare utilizator individual, astfel încât fiecare utilizator ar trebui să poată verifica includerea valorii sale nete în valoarea totală

Pentru a testa și a verifica afirmațiile de mai sus, trebuie să formulăm constrângeri precum:

Afirmația 1: Constrângerea soldului total (constrângerea unui sold total corect)

uts: dimensiunea urmei utilizatorului, reprezentând numărul de rânduri incluse în datele fiecărui utilizator.

suma: soldul total al utilizatorului

N: numărul de utilizatori

Afirmația 2: Constrângerea nenegativă (constrângere de capital net pozitiv)

Afirmația 3: Constrângere de incluziune (constrângere de includere a soldului întregului cont de client)

În conformitate cu constrângerile de mai sus, creăm un tabel de urmărire, pentru a angaja și a verifica soldurile totale și nenegativitatea prin inspecții prin eșantionare. Iată cum este construit tabelul de urmărire (pentru un exemplu simplu, 3 utilizatori a căror valoare maximă USD este mai mică de 4^6 = 4.096):

1. Inițializam un tabel cu 32 de rânduri și 5 coloane și introducem valorile și ID-urile utilizatorului în al

rând, unde k % 8 = 6 și

. Fiecare 8 rânduri reprezintă un bloc, iar informațiile despre activele utilizatorului se află acum în

penultimul rând al fiecărui bloc. Primului utilizator i se acordă solduri virtuale 0, așa că îl putem publica pentru a dovedi că acumularea de valori nu pleacă de la o valoare negativă.

2. Acumulăm valorile activelor utilizatorului una câte una și completăm rezultatul în

rânduri, unde k % 8 = 7 și

, reprezentând ultimele rânduri ale fiecărui bloc

3. Împărțim în continuare valoarea totală a fiecărui utilizator la 4 rând cu rând de la

penultimul rând al fiecărui bloc, rotunjind în jos. Facem acest lucru pentru a menține nenegativă valoarea netă a utilizatorului, verificând dacă primele rânduri sunt zero pentru fiecare bloc. Dacă cineva are o valoare netă negativă, primul rând al blocului său nu va fi zero, deoarece o valoare negativă (-x) se va dovedi a fi (p - x) în câmp finit

, fiind o valoare pozitivă foarte mare.

4. Introducem numere aleatorii pentru fiecare utilizator și completăm spațiile goale din tabel cu 0

Pasul 2: Extensie polinomială de grad scăzut Folosind constrângerile polinomiale de mai sus, putem obține un polinom de urmărire de calcul cu lungimea uts * N. Din rațiuni de securitate efectuăm angajamentul față de polinom pe un domeniu de evaluare mai mare, cu factorul de amplificare a domeniului ca factor de_extensie.

În cazul de mai sus am putea calcula un polinom p(x) din I(x). Când folosim un factor de_extensie de 8, vom calcula alte 32(8-1)* de puncte pe p(x).

Întrucât două polinoame diferite cu gradul D vor avea în comun cel mult D puncte, într-un exemplu de pereche de polinoame cu un polinom valid (care satisface constrângerile de mai sus) și un polinom fals cu gradul D (care nu satisface constrângerile de mai sus), cele două polinoame vor avea în comun cel mult D puncte. Acest lucru înseamnă că un polinom fals are șansa

de a trece o inspecție prin eșantionare aleatorie. Dacă efectuăm inspecția prin eșantionare de n ori, șansa va scădea la

.

Indroducem factorul_de_extensie cu valoarea implicită de 16 și timpul implicit al inspecției prin eșantionare ca 16, deci nivelul de securitate va fi de 80 de biți.

Pasul 3: angajament polinomial Calculăm valoarea hash a urmei de calcul și soldul utilizatorului respectiv, ID-ul utilizatorului și valoarea funcției polinomialle de restrângere pentru fiecare rând și generăm un arbore Merkle. Rădăcina Merkle este valoarea de angajament a polinomului.

Pasul 4: generarea dovezii de eșantionare Folosind rădăcina Merkle ca sursă aleatorie, eșantionăm datele. Pentru a evita scurgerea datelor de urmărire de calcul, evităm datele cu indice de factor de_extensie *k ** în timpul eșantionării și generăm calea de verificare Merkle corespunzătoare indicelui de eșantionare.

Efectuăm inspecțiile prin eșantionare pentru a verifica dacă polinomul angajat este un polinom valid care satisface constrângerile enumerate la Pasul 1. După cum se specifică în Pasul 2, perioadele de inspecție prin eșantionare vor afecta șansa unei intervenții neautorizate sau manipulări reușite.

Pasul 5: generarea unei dovezi de grad scăzut

Putem controla probabilitatea de intervenție neautorizată sau manipulare prin intermediul inspecției prin eșantionare. Cu toate acestea, există o condiție, menționată în Pasul 2, potrivit căreia trebuie să ne asigurăm că gradul polinomului verificat nu este mai mare decât gradul unui polinom valid. Pentru a îmbunătăți eficiența dovezii, combinăm liniar toate polinoamele de constrângere într-un singur polinom și generăm o dovadă de grad scăzut pentru aceasta. Coeficienții de combinație sunt, de asemenea, generați folosind rădăcina Merkle ca sursă aleatorie.

De exemplu, dacă vrem să demonstrăm că p0(x), p1(x) și p2(x) nu au grade mai mari de D, putem genera 2 coeficienți aleatorii din rădăcina Merkle generată în Pasul 3 și apoi putem calcula polinomul liniar l(x) ca:

k0 = hash(rădăcină + „0”) k1 = hash(rădăcină + „1”) l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)

Dacă se poate demonstra că l(x) nu are gradul mai mare decât D, atunci șansa ca gradul oricăruia dintre p0(x), p1(x) și p2(x) să fie mai mare decât D va fi aproape de 0

Pasul 6: verificarea soldului total În primul rând, verificăm dovada de grad scăzut generată la Pasul 5.

Apoi se efectuează o verificare deschisă suplimentară a datelor eșantionate generate în Pasul 4. Mai întâi pentru a verifica dacă datele corespund cu angajamentul polinomial și în al doilea rând pentru a verifica dacă datele îndeplinesc constrângerile construite în Pasul 1. În final, se verifică coeficienții de combinație ai polinomului de test de grad scăzut.

Pasul 7: se generează dovada includerii utilizatorului Pentru a dovedi că un anumit utilizator este inclus în suma totală comunicată de bursă, punem la dispoziție urma calculată a utilizatorului, soldul utilizatorului, ID-ul utilizatorului și un număr aleatoriu corespunzător indicelui utilizatorului. De asemenea, punem la dispoziție și calea Merkle care corespunde cu acestor date.

Pasul 8: verificarea dovezii de includere de către utilizator Utilizatorul își verifică soldul, ID-ul, calculează valoarea hash a datelor corespunzătoare indicelui său și verifică valoarea hash pe nodul-frunză al arborelui Merkle folosind calea Merkle furnizată de noi.

2. Cum se efectuează verificarea pe cont propriu a dovezii rezervelor (PoR)?

2.1 Verificarea constrângerii de includere zk-STARK

Teoria verificării

Urmând procedura STARK, vom calcula tabelul de urmărire a execuției pentru toate activelor utilizatorului prin metoda de mai jos și vom calcula informațiile fiecărui utilizator ca un tabel de urmărire care devine o frunză de arbore Merkle, apoi vom trimite frunzele către o rădăcină Merkle care va fi publicată în timpul fiecărei runde de audit PoR.

Pentru a verifica dacă activele vă sunt incluse în rădăcină, vă vom furniza calea Merkle pentru verificare. Mai întâi vă puteți calcula frunza prin aplicarea procesului de hashing asupra informațiilor despre activele pe care le dețineți, apoi puteți verifica dacă frunza este o frunză validă în arborele și rădăcina Merkle publicate de noi.

De exemplu, în Figura 1, utilizatorul cu un id id_k va calcula hashk = hash („20” „15” „5” „id_k” „99821”), iar celelalte date din chenarul roșu vor fi verificarea căii Merkle. Utilizatorilor li se va pune la dispoziție un instrument cu sursă deschisă pentru a efectua această verificare.

Deoarece frunzele arborelui Merkle sunt valori hash, niciuna dintre informațiile private nu vor ajunge la alte persoane.

Cum se efectuează verificarea:

1. Pentru a verifica dacă soldul activelor din contul pe care îl dețineți a fost inclus ca frunză Merkle zk-STARK, intrați în contul OKX, accesați „Audituri” pentru a vizualiza auditurile recente, dați clic pe „Detalii” pentru a vă vizualiza datele de audit.

2. Puteți obține datele de care aveți nevoie pentru verificarea manuală dând clic pe „Copiere date”.

3. După ce dați clic pe „Copiere date”, deschideți un editor de text (de exemplu: notepad), apoi lipiți și salvați șirul ca fișier JSON. Fișierul trebuie să se termine cu numele "_inclusion_proof.json." Șirul JSON conține soldul contului și un instantaneu al căii Merkle, apoi fișierul este salvat într-un folder nou.

Textul JSON este afișat după cum urmează:

{ "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" ] } }

1. Descărcați instrumentul de verificare cu sursă deschisă OKXzk-STARKValidator

2. Salvați și instrumentul de verificare cu sursă deschisă OKX zk-STARKValidatorși fișierul JSON cu șirul în noul folder de la pasul 3. În cazul nostru: punem instrumentul, precum și fișierul de date în dosarul „Descărcări”, într-un folder denumit „proof-of-reserves”, ca în imaginea de mai jos:

1. Deschideți zk-STARKValidator, acesta va rula automat fișierul JSON cu șirul pe care l-ați salvat în folder.

2. Verificați rezultatul

• În cazul în care verificarea are succes, va fi afișat rezultatul „Constrângerea de includere a fost validată”:

• În cazul în care verificarea eșuează, va fi afișat rezultatul „Constrângerea de includere nu a fost validată”:

  

2.2 Verificați soldul total zk-STARK și constrângerea nenegativă

Cum se efectuează verificarea:

Pentru a verifica și dovedi că activele pe care afirmăm că le deținem sunt reale și că niciun utilizator nu deține capital propriu negativ, accesați „Fișierele de auditare” și descărcați fișierul „zk-STARK” din Raportul de pasive, apoi salvați-l într-un folder nou.

Dezarhivați fișierul descărcat, obținând astfel un folder „sum proof data”, care include mii de foldere-ramură și un folder-trunchi. Fiecare folder conține două fișiere JSON numite „sum_proof.json" și „sum_value.json”.

Descărcați instrumentul de verificare cu sursă deschisă OKXzk-STARKValidator

Salvați instrumentul de verificare cu sursă deschisă OKXzk-STARKValidator și dosarul „sum proof data” în folderul nou-creat de la pasul 1. În cazul nostru: punem instrumentul și fișierul de date în folderul „Descărcări”, într-un folder denumit „proof-of-reserves”, ca în imaginea de mai jos:

Deschideți zk-STARKValidator, acesta va rula automat fișierul „sum proof data” pe care l-ați salvat în folder.

Verificați rezultatul

Dacă verificarea reușește, va fi afișat rezultatul „Suma totală și constrângerea nenegativă au fost validate”:

Dacă verificarea eșuează, va fi afișat rezultatul „Suma totală și constrângerea nenegativă nu au fost validate”: