Introducere
„Generarea numerelor aleatoare este prea importantă pentru a fi lăsată la voia întâmplării“
Robert Cavu, 1970
Acest articol se concentrează pe aplicarea practică a soluțiilor care utilizează generarea colectivă de numere aleatoare într-un mediu nesigur. Pe scurt — cum și la ce se folosește aleatorietatea în blockchain-uri și câteva informații despre cum să diferențiem „aleatorietatea bună” de „aleatorietatea proastă”. Generarea unui număr cu adevărat aleatoriu este o problemă extrem de complexă, chiar și pe un computer singur, și este studiată de mult de criptografi. Iar în rețelele decentralizate, generarea numerelor aleatoare devine și mai complicată și mai importantă.
În rețelele în care participanții nu au încredere unul în altul, capacitatea de a genera un număr aleatoriu de necontestat permite eficient rezolvarea multor probleme cruciale și îmbunătățește semnificativ schemele deja existente. De fapt, jocurile de noroc și loteriile nu sunt deloc scopul principal, așa cum poate părea la prima vedere pentru cititorul neexperimentat.
Generarea numerelor aleatoare
Computerele nu pot genera singure numere aleatorii; au nevoie de ajutor extern. Un computer poate obține o anumită valoare aleatorie folosind, de exemplu, mișcările mouse-ului, cantitatea de memorie utilizată, curentul parazitar de pe contactele procesorului și multe alte surse, numite surse de entropie. Aceste valori nu sunt complet aleatorii, deoarece se află într-un anumit interval sau au un caracter previzibil al modificărilor. Pentru a transforma aceste numere în numere cu adevărat aleatorii într-un interval dat, se aplică criptotransformări, astfel încât valorile distribuite neuniform din sursa de entropie să devină valori pseudo-aleatorii distribuite uniform. Valorile obținute se numesc pseudo-aleatorii, deoarece nu sunt cu adevărat aleatorii, ci sunt generate determinist de entropie. Orice algoritm criptografic bun, criptând datele, produce texte criptate care, statistic, ar trebui să fie indistinguibile de o secvență aleatorie, așa că pentru a produce random, se poate folosi o sursă de entropie care asigură doar o bună ne-repetabilitate și imprevizibilitate a valorilor, chiar și în intervale mici, restul lucrării de dispersare și amestecare a biților în valoarea rezultată va fi preluat de algoritmul de criptare.
Pentru a încheia această lecție scurtă, voi adăuga că generarea numerelor aleatorii chiar și pe un singur dispozitiv este unul dintre pilonii care asigură securitatea datelor noastre, numerele pseudo-aleatorii generate sunt folosite pentru stabilirea unor conexiuni securizate în diverse rețele, pentru generarea cheilor criptografice, pentru echilibrarea sarcinii, pentru controlul integrității și pentru multe alte aplicații. Securitatea multor protocoale depinde de capacitatea de a genera un random fiabil, imprevizibil din exterior, de a-l păstra și de a nu-l dezvălui până în următorul pas al protocolului, altfel securitatea va fi pusă în pericol. Atacul asupra generatorului de valori pseudo-aleatorii este extrem de periculos și pune în pericol toate programele software care utilizează generarea de random.
Toate acestea ar trebui să le știți, dacă ați parcurs un curs de bază de criptografie, așa că vom continua cu rețelele descentralizate.
Răspuns aleatoriu în blockchain-uri
În primul rând, voi discuta despre blockchain-urile care suportă contracte inteligente; acestea pot valorifica pe deplin capacitățile oferite de un răspuns aleatoriu de calitate. În continuare, pentru scurtete, voi numi această tehnologie “Publicly Verifiable Random Beacons” sau PVRB. Deoarece blockchain-urile sunt rețele a căror informație poate fi verificată de orice participant, o parte esențială a denumirii este “Publicly Verifiable”, adică oricine poate, prin calcule, obține dovezi că numărul generat, plasat în blockchain, are următoarele proprietăți:
- Rezultatul trebuie să aibă o distribuție dovedit uniformă, adică să se bazeze pe criptografie dovedit rezistentă.
- Nu se pot controla niciunul dintre biții rezultatului. Ca urmare, rezultatul nu poate fi prezis în avans.
- Nu se poate sabota protocolul de generare prin neparticiparea la protocol sau prin supraîncărcarea rețelei cu mesaje de atac.
- Toate cele menționate anterior trebuie să fie rezistente la conspirațiile unui număr permisibil de participanți necinstit (de exemplu, 1/3 din participanți).
Orice posibilitate ca un grup minor de participanți să genereze chiar și un răspuns aleatoriu controlat par/inpar – este o vulnerabilitate de securitate. Orice posibilitate ca un grup să oprească furnizarea de răspuns aleatoriu – este o vulnerabilitate de securitate. În general, sunt multe probleme, iar această sarcină nu este ușoară...
Se pare că cea mai importantă aplicare pentru PVRB este în diverse jocuri, loterii și, în general, orice formă de gambling pe blockchain. Într-adevăr, aceasta este o direcție importantă, dar răspunsul aleatoriu în blockchain-uri are aplicații și mai semnificative. Să le analizăm.
Algoritmi de consens
PVRB pentru organizarea consensus-ului de rețea joacă un rol uriaș. Tranzacțiile în blockchain-uri sunt protejate prin semnătura electronică, așadar, „atacarea unei tranzacții” se referă întotdeauna la includerea/excluderea unei tranzacții în bloc (sau în mai multe blocuri). Principalul scop al algoritmului de consens este de a conveni asupra ordinii acestor tranzacții și a ordinii blocurilor care includ aceste tranzacții. De asemenea, o proprietate necesară pentru blockchain-urile reale este finalitatea — capacitatea rețelei de a conveni că lanțul până la blocul finalizat este definitiv și nu va fi exclus din cauza apariției unui nou fork. De obicei, pentru a conveni că un bloc este valid și, cel mai important, final, este necesar să se colecteze semnăturile de la majoritatea producătorilor de blocuri (BP — block producers), ceea ce necesită cel puțin transmiterea lanțului de blocuri la toate BP și distribuirea semnăturilor între toate BP. Odată cu creșterea numărului de BP, numărul mesajelor necesare în rețea crește exponențial, prin urmare, algoritmii de consens care necesită finalitate, folosiți, de exemplu, în consensul pBFT de la Hyperledger, nu funcționează cu viteza necesară, începând deja cu câteva zeci de BP, necesitând un număr uriaș de conexiuni.
Dacă în rețea există un PVRB indiscutabil și onest, chiar și în cele mai simple aproximații, se poate, pe baza lui, alege unul dintre block producers și desemna un „lider” pentru o rundă din protocol. Dacă avem N producători de blocuri, dintre care M: M > 1/2 N sunt onesti, nu cenzurează tranzacțiile și nu construiesc forks ale lanțului cu scopul de a efectua un atac „double spend”, atunci utilizarea unui PVRB indiscutabil distribuit uniform va permite alegerea unui lider onest cu o probabilitate de M / N (M / N > 1/2). Dacă fiecărui lider i se atribuie un interval de timp propriu, în care poate produce un bloc și valida lanțul, iar aceste intervale sunt egale ca timp, atunci lanțul blocurilor corecte BP va fi mai lung decât lanțul format de BP rău intenționați, iar algoritmul de consens, bazat pe lungimea lanțului, va respinge pur și simplu „cel rău”. Acest principiu de alocare a unor cuanturi egale de timp fiecărui BP a fost aplicat pentru prima dată în Graphene (predecesorul EOS) și permite majorității blocurilor să fie închise cu o singură semnătură, ceea ce reduce semnificativ sarcina rețelei și permite acestui consens să funcționeze extrem de rapid și stabil. Cu toate acestea, rețelele EOS trebuie acum să folosească blocuri speciale (Last Irreversible Block), care sunt confirmate prin semnături de 2/3 BP. Aceste blocuri servesc pentru a asigura finalitatea (imposibilitatea apariției unui fork al lanțului, începând de la ultimul Last Irreversible Block).
De asemenea, în implementările reale, schema protocolului este mai complexă - voturile pentru blocurile propuse se desfășoară în mai multe etape, pentru a menține funcționarea rețelei în cazul omisiunii blocurilor și a problemelor de rețea, dar chiar și cu toate acestea, algoritmii de consens care folosesc PVRB necesită cu mult mai puține mesaje între BP, ceea ce îi face mai rapizi decât PВFT tradițional sau diferitele sale modificări.
Cel mai reprezentativ astfel de algoritm: de la echipa Cardano, care, după cum s-a declarat, are o rezistență demonstrabilă matematic la existența conspirației între BP.
În Ouroboros, PVRB este folosit pentru a determina așa-numitul „BP schedule” - programul conform căruia fiecărui BP i se atribuie un slot de timp pentru publicarea blocului. Un avantaj major al utilizării PVRB este „egalitatea” totală a BP (în funcție de dimensiunile soldurilor lor). Corectitudinea PVRB garantează că BP rău intenționați nu pot controla programul sloturilor de timp și, prin urmare, nu pot manipula lanțul, pregătind și analizând anticipat fork-uri ale lanțului, iar pentru a alege un fork este suficient să ne bazăm pur și simplu pe lungimea lanțului, fără a folosi metode ingenioase de calculare a „utilității” BP și „greutății” blocurilor sale.
În toate cazurile în care este necesar să alegi un participant aleator într-o rețea descentralizată, aproape întotdeauna cea mai bună alegere va fi PVRB, și nu o variantă deterministă bazată, de exemplu, pe hash-ul blocului. Fără PVRB, posibilitatea de a influența alegerea participantului duce la apariția atacurilor, în care atacatorul poate, alegând din mai multe opțiuni de viitor, să selecteze următorul participant corupt sau chiar mai mulți pentru a asigura o pondere mai semnificativă în luarea deciziilor. Utilizarea PVRB discreditează aceste tipuri de atacuri.
Scalarea și echilibrarea încărcăturii
PVRB poate aduce beneficii semnificative și în sarcini pentru reducerea încărcăturii, scalarea plăților. Pentru început, are sens să te familiarizezi cu Rivesta „Bilete de loterie electronice ca micropayments”. Esența generală este că, în loc să faci 100 de plăți de 1c de la plătitor către beneficiar, poți juca o loterie corectă cu un premiu de 1$ = 100c, unde plătitorul, la fiecare plată de 1c, transferă băncii unul dintre cele 100 de „bilete de loterie”. Unul dintre aceste bilete câștigă băncii 1$, și exact acest bilet poate fi înregistrat în blockchain de către beneficiar. Cel mai important este că celelalte 99 de bilete sunt transferate între beneficiar și plătitor fără nici o participație externă, pe un canal privat și cu orice viteză necesară. O descriere bună a protocolului bazat pe acest schema în rețeaua Emercoin poate fi citită .
Această schemă are câteva probleme, de exemplu, beneficiarul poate înceta să deservească plătitorul imediat după primirea biletului câștigător, dar pentru numeroase aplicații speciale, cum ar fi tarifarea pe minut sau abonamentele electronice la servicii, acestea pot fi ignorate. Principalul cerințe este, desigur, corectitudinea loteriei realizate, iar pentru desfășurarea acesteia este complet necesar PVRB.
Alegerea aleatorie a participanților este extrem de importantă și pentru protocoalele de shardare, al căror scop este scalarea orizontală a lanțului de blocuri, permițând diferitelor BP să proceseze doar domeniul lor de tranzacții. Aceasta este o sarcină extrem de complexă, în special în ceea ce privește securitatea la combinarea shardurilor. Alegerea corectă a unui BP aleatoriu cu scopul de a-l desemna responsabil pentru un anumit shard, la fel ca în algoritmii de consens — este de asemenea o sarcină a PVRB. În sistemele centralizate, shardurile sunt desemnate de un balansator, care pur și simplu calculează un hash din cerere și îl trimite executantului necesar. În blockchainuri, posibilitatea de a influența această desemnare poate duce la atacuri asupra consensului. De exemplu, conținutul tranzacțiilor poate fi controlat de un atacator, care poate controla ce tranzacții ajung în shardul pe care îl controlează și poate manipula lanțul de blocuri din acesta. Discuția despre problema utilizării numerelor aleatoare pentru sarcinile de shardare în Ethereum poate fi citită
Shardarea este una dintre cele mai ambițioase și serioase sarcini în domeniul blockchain-ului, iar soluționarea acesteia va permite construirea de rețele descentralizate cu performanțe și volum fantastic. PVRB este doar unul dintre blocurile importante pentru rezolvarea acesteia.
Jocuri, protocoale economice, arbitraj
Rolul numerelor aleatorii în industria jocurilor este greu de supraestimat. Utilizarea lor evidentă în cazinourile online și cea implicită în calcularea efectelor fiecărei acțiuni a jucătorului reprezintă probleme extrem de complexe pentru rețelele descentralizate, unde nu există posibilitatea de a se baza pe o sursă centrală de aleatoritate. Totuși, selecția aleatorie poate rezolva multe probleme economice și poate ajuta la construirea de protocoale mai simple și mai eficiente. Să presupunem că în protocolul nostru există dispute legate de plata unor servicii ieftine, iar aceste dispute apar destul de rar. În acest caz, dacă există un PVRB incontestabil, clienții și vânzătorii pot conveni asupra unei soluționări aleatorii a disputelor, dar cu o probabilitate determinată. De exemplu, cu o probabilitate de 60% câștigă clientul, iar cu 40% — vânzătorul. Această abordare, care poate părea absurdă la prima vedere, permite soluționarea automată a disputelor cu o proporție de câștiguri/pierderi exact predictibilă, care satisface ambele părți fără a implica o terță parte și fără risipa de timp. Mai mult, raportul probabilităților poate fi dinamic și poate depinde de anumite variabile globale. De exemplu, dacă afacerea companiei merge bine, se observă un număr scăzut de dispute și o rentabilitate ridicată, compania poate schimba automat probabilitatea de soluționare a disputei în favoarea orientării spre client, de exemplu la 70/30 sau 80/20, și invers, dacă disputele costă mult și sunt frauduloase sau inadecvate, probabilitatea poate fi mutată în cealaltă direcție.
O mulțime de protocoale descentralizate interesante, cum ar fi registrele curatate de token-uri, piețele de predicție, curbele de legare și multe altele, constituie jocuri economice în care comportamentul bun este recompensat, iar cel rău este sancționat. Acestea întâmpină adesea probleme de securitate, ale căror soluții se contrazic între ele. Ceea ce este protejat împotriva atacurilor „whale” cu miliarde de token-uri („big stake”) este vulnerabil la atacuri din parte a mii de conturi cu solduri mici („sybil stake”), iar măsurile luate împotriva unei astfel de atacuri, cum ar fi comisioanele non-liniare destinate să facă lucrul cu un staked mare nerentabil, sunt de obicei compromise de o altă atac. Deoarece este vorba despre un joc economic, greutățile statistice corespunzătoare pot fi calculate dinainte și comisioanele pot fi înlocuite pur și simplu cu unele randomizate cu o distribuție corespunzătoare. Astfel de comisioane probabilistice sunt implementate extrem de simplu, dacă blockchain-ul dispune de o sursă de randomizare fiabilă și nu necesită calcule complexe, complicând viața atât pentru balene, cât și pentru sybil.
Este important să ne amintim că controlul asupra unui singur bit din această randomizare permite manipularea, reducând și crescând probabilitățile de două ori, astfel încât un PVRB corect este o componentă esențială a acestor protocoale.
Unde pot găsi randomizarea corectă?
În teorie, o selecție aleatorie corectă în rețele descentralizate permite asigurarea unei securități demonstrabile împotriva conspirațiilor pentru aproape orice protocol. Justificarea este destul de simplă - dacă rețeaua căde în acord asupra unui bit 0 sau 1, iar în rândul participanților mai puțin de jumătate sunt necinstiti, atunci, cu un număr suficient de iterații, rețeaua va ajunge în mod garantat la un consens privind acest bit cu o probabilitate fixă. Pur și simplu pentru că randomizarea corectă va alege 51 din 100 de participanți în 51% din cazuri. Dar aceasta este teoria, deoarece în rețelele reale, pentru a asigura un astfel de nivel de securitate ca în articole, este necesar un număr mare de mesaje între gazde, criptografie complexă pe mai multe etape, iar orice complicare a protocolului adaugă imediat noi vectori de atac.
De aceea, în prezent nu observăm în blockchain-uri un PVRB dovedit robust, care să fi fost utilizat deja suficient timp pentru a trece prin teste realizate de aplicații reale, audituri multiple, sarcini și, desigur, atacuri reale, fără de care este greu să numim produsul cu adevărat sigur.
Cu toate acestea, există mai multe abordări promițătoare, acestea se diferențiază prin mulțimea detaliilor, iar una dintre ele va rezolva cu siguranță problema. Cu resursele computaționale actuale, teoria criptografică se poate transforma destul de agil în aplicații practice. În continuare, ne face plăcere să discutăm despre implementările PVRB: sunt acum câteva, fiecare având propriul set de trăsături importante și particularități de realizare, iar în spatele fiecărei idei stă o propunere bună. Nu sunt foarte multe echipe care se ocupă de randomizare, iar experiența fiecărei echipe este extrem de valoroasă pentru toate celelalte. Sperăm că informațiile noastre vor ajuta celelalte echipe să avanseze mai repede, având în vedere experiențele predecesorilor.
Sursa: habr.com
