Introducere
„Generarea numerelor aleatorii este prea importantă pentru a fi lăsată la voia întâmplării.”
Robert Cavue, 1970
Acest articol este dedicat aplicării practice a soluțiilor care utilizează generarea colectivă de numere aleatoare într-un mediu neîncrezat. Pe scurt, cum și de ce este folosit aleatoriu în blockchains și puțin despre cum să distingem aleatoriu „bun” de „rău”. Generarea unui număr cu adevărat aleatoriu este o problemă extrem de dificilă, chiar și pe un singur computer, și a fost mult timp studiată de criptografi. Ei bine, în rețelele descentralizate, generarea numerelor aleatoare este și mai complexă și mai importantă.
În rețelele în care participanții nu au încredere unii în alții, capacitatea de a genera un număr aleator incontestabil ne permite să rezolvăm eficient multe probleme critice și să îmbunătățim semnificativ schemele existente. Mai mult, jocurile de noroc și loteriile nu sunt obiectivul numărul unu aici, așa cum ar putea părea la început pentru cititorul neexperimentat.
Generarea numerelor aleatorii
Calculatoarele nu pot genera ele însele numere aleatoare; au nevoie de ajutor extern pentru a face acest lucru. Calculatorul poate obține o valoare aleatorie din, de exemplu, mișcările mouse-ului, cantitatea de memorie utilizată, curenții paraziți pe pinii procesorului și multe alte surse numite surse de entropie. Aceste valori în sine nu sunt complet aleatorii, deoarece se află într-un anumit interval sau au un model previzibil de schimbări. Pentru a transforma astfel de numere într-un număr cu adevărat aleatoriu într-un interval dat, li se aplică criptotransformări pentru a produce valori pseudoaleatoare distribuite uniform din valorile distribuite neuniform ale sursei de entropie. Valorile rezultate sunt numite pseudoaleatoare deoarece nu sunt cu adevărat aleatoare, ci sunt derivate determinist din entropie. Orice algoritm criptografic bun, la criptarea datelor, produce texte cifrate care nu ar trebui să fie distinse din punct de vedere statistic de o secvență aleatorie, astfel încât pentru a produce aleatorie puteți lua o sursă de entropie, care oferă doar o bună repetabilitate și imprevizibilitate a valorilor chiar și în intervale mici, restul muncii este dispersarea și amestecarea biților în Valoarea rezultată va fi preluată de algoritmul de criptare.
Pentru a finaliza un scurt program educațional, voi adăuga că generarea de numere aleatoare chiar și pe un singur dispozitiv este unul dintre pilonii asigurării securității datelor noastre.Numerele pseudoaleatoare generate sunt folosite la stabilirea conexiunilor securizate în diverse rețele, pentru a genera chei criptografice, pentru echilibrarea încărcăturii, monitorizarea integrității și pentru multe alte aplicații. Securitatea multor protocoale depinde de capacitatea de a genera o aleatorie fiabilă, imprevizibilă din exterior, de a o stoca și de a nu-l dezvălui până la următorul pas al protocolului, altfel securitatea va fi compromisă. Un atac asupra unui generator de valori pseudoaleatoare este extrem de periculos și amenință imediat toate programele care utilizează generarea aleatoriei.
Ar trebui să știi toate acestea dacă ai urmat un curs de bază de criptografie, așa că hai să continuăm despre rețelele descentralizate.
Aleatoriu în blockchains
În primul rând, voi vorbi despre blockchain-urile cu suport pentru contractele inteligente; aceștia sunt cei care pot profita din plin de oportunitățile oferite de aleatorietatea de înaltă calitate, de netăgăduit. Mai mult, pentru concizie, voi numi această tehnologie „Indicatoare aleatorii verificabile public” sau PVRB. Deoarece blockchain-urile sunt rețele în care informațiile pot fi verificate de către orice participant, partea cheie a numelui este „Verificabil public”, adică. Oricine poate folosi calcule pentru a obține dovada că numărul rezultat postat pe blockchain are următoarele proprietăți:
- Rezultatul trebuie să aibă o distribuție uniformă dovedit, adică să se bazeze pe o criptografie puternică.
- Nu este posibil să controlați niciunul dintre biții din rezultat. În consecință, rezultatul nu poate fi prevăzut în avans.
- Nu puteți sabota protocolul de generare neparticipând la protocol sau supraîncărcând rețeaua cu mesaje de atac
- Toate cele de mai sus trebuie să fie rezistente la coluziunea unui număr permis de participanți la protocol necinstiți (de exemplu, 1/3 dintre participanți).
Orice posibilitate ca un grup minor de participanți de a produce chiar și un control aleatoriu par/impar este o gaură de securitate. Orice capacitate a grupului de a opri emiterea aleatorie este o gaură de securitate. În general, există multe probleme, iar această sarcină nu este una ușoară...
Se pare că cea mai importantă aplicație pentru PVRB sunt diversele jocuri, loteriile și, în general, orice tip de jocuri de noroc pe blockchain. Într-adevăr, aceasta este o direcție importantă, dar aleatorietatea în blockchains are aplicații și mai importante. Să ne uităm la ele.
Algoritmi de consens
PVRB joacă un rol uriaș în organizarea consensului rețelei. Tranzacțiile în blockchain sunt protejate de o semnătură electronică, așa că un „atac asupra unei tranzacții” este întotdeauna includerea/excluderea unei tranzacții într-un bloc (sau mai multe blocuri). Și sarcina principală a 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 fi de acord că lanțul până la blocul finalizat este definitiv și nu va fi niciodată exclus din cauza apariției unui nou fork. De obicei, pentru a fi de acord că un bloc este valabil și, cel mai important, definitiv, este necesar să se colecteze semnături de la majoritatea producătorilor de blocuri (denumite în continuare BP - block-producers), ceea ce necesită cel puțin livrarea lanțului de blocuri. tuturor BP și distribuirea semnăturilor între toate BP . Pe măsură ce numărul de BP crește, numărul de mesaje necesare în rețea crește exponențial, prin urmare, algoritmii de consens care necesită finalitate, utilizați de exemplu în consensul Hyperledger pBFT, nu funcționează la viteza necesară, pornind de la câteva zeci de BP, necesitând un număr mare de conexiuni.
Dacă în rețea există un PVRB de netăgăduit și onest, atunci, chiar și în cea mai simplă aproximare, se poate alege unul dintre producătorii de bloc pe baza acestuia și îl poate numi ca „lider” în timpul unei runde a protocolului. Daca avem N producători de bloc, dintre care M: M > 1/2 N sunteți cinstiți, nu cenzurați tranzacțiile și nu deformați lanțul pentru a efectua un atac de „cheltuire dublă”, apoi folosirea unui PVRB necontestat distribuit uniform va permite alegerea unui lider onest cu probabilitate M / N (M / N > 1/2). Dacă fiecărui lider i se atribuie propriul interval de timp în care poate produce un bloc și valida lanțul, iar aceste intervale sunt egale în timp, atunci lanțul de blocuri al BP-urilor onești va fi mai lung decât lanțul format din BP-uri rău intenționate, iar consensul. algoritmul se bazează pe lungimea lanțului, pur și simplu îl va arunca pe cel „rău”. Acest principiu de alocare a intervalelor egale de timp pentru fiecare BP a fost aplicat pentru prima dată în Graphene (predecesorul EOS) și permite ca majoritatea blocurilor să fie închise cu o singură semnătură, ceea ce reduce foarte mult încărcarea rețelei și permite acestui consens să funcționeze extrem de rapid și în mod constant. Cu toate acestea, rețeaua EOS trebuie acum să folosească blocuri speciale (Last Irreversible Block), care sunt confirmate de semnăturile lui 2/3 BP. Aceste blocuri servesc la asigurarea finalității (imposibilitatea ca o furcăre a lanțului să pornească înainte de ultimul Ultimul Bloc ireversibil).
De asemenea, în implementările reale, schema de protocol este mai complicată - votul pentru blocurile propuse se efectuează în mai multe etape pentru a menține rețeaua în caz de lipsă de blocuri și probleme cu rețeaua, dar chiar și ținând cont de acest lucru, algoritmii de consens care utilizează PVRB necesită semnificativ mai puține mesaje între BP, ceea ce face posibilă realizarea lor mai rapidă decât PVFT tradițională sau diferitele sale modificări.
Cel mai proeminent reprezentant al unor astfel de algoritmi: de la echipa Cardano, despre care se spune că poate fi demonstrată matematic împotriva coluziunii BP.
În Ouroboros, PVRB este folosit pentru a defini așa-numitul „program BP” - un program conform căruia fiecărui BP îi este atribuit propriul interval orar pentru publicarea unui bloc. Marele avantaj al utilizării PVRB este „egalitatea” completă a BP (în funcție de dimensiunea bilanțurilor lor). Integritatea PVRB asigură că BP-urile rău intenționate nu pot controla programarea intervalelor de timp și, prin urmare, nu pot manipula lanțul prin pregătirea și analizarea fork-urilor lanțului în prealabil, iar pentru a selecta o furcă este suficient să se bazeze pur și simplu pe lungimea lanțului. lanț, fără a folosi modalități complicate de a calcula „utilitatea” BP și „greutatea” blocurilor sale.
În general, în toate cazurile în care un participant aleatoriu trebuie să fie ales într-o rețea descentralizată, PVRB este aproape întotdeauna cea mai bună alegere, mai degrabă decât o opțiune deterministă bazată, de exemplu, pe un bloc hash. Fără PVRB, capacitatea de a influența alegerea unui participant duce la atacuri în care atacatorul poate alege din mai multe viitoare pentru a alege următorul participant corupt sau mai multe simultan pentru a asigura o mai mare parte a deciziei. Utilizarea PVRB discreditează aceste tipuri de atacuri.
Scalare și echilibrare a sarcinii
PVRB poate fi, de asemenea, de mare beneficiu în sarcini precum reducerea sarcinii și scalarea plăților. Pentru început, este logic să te familiarizezi cu Rivesta „Bilete de loterie electronice ca microplăți”. Ideea generală este că, în loc să faceți 100 de plăți 1c de la plătitor către destinatar, puteți juca o loterie cinstită cu un premiu de 1$ = 100c, în care plătitorul dă băncii unul din 1 de „bilete de loterie” sale pentru fiecare. 100c plată. Unul dintre aceste bilete câștigă un borcan de 1 USD și este acest bilet pe care destinatarul îl poate înregistra în blockchain. Cel mai important lucru este că restul de 99 de bilete sunt transferate între destinatar și plătitor fără nicio participare externă, printr-un canal privat și cu orice viteză dorită. Se poate citi o descriere bună a protocolului bazat pe această schemă în rețeaua Emercoin .
Această schemă are câteva probleme, cum ar fi destinatarul poate înceta să mai servească plătitorul imediat după ce a primit un bilet câștigător, dar pentru multe aplicații speciale, cum ar fi facturarea pe minut sau abonamentele electronice la servicii, acestea pot fi neglijate. Cerința principală, desigur, este corectitudinea loteriei, iar pentru implementarea acesteia este absolut necesar un PVRB.
Alegerea unui participant aleatoriu este, de asemenea, extrem de importantă pentru protocoalele de sharding, al căror scop este de a scala pe orizontală lanțul de blocuri, permițând diferitelor BP să proceseze numai domeniul lor de tranzacții. Aceasta este o sarcină extrem de dificilă, mai ales în ceea ce privește securitatea la îmbinarea fragmentelor. Selecția corectă a unui BP aleatoriu în scopul atribuirii celor responsabili pentru un anumit fragment, ca în algoritmii de consens, este, de asemenea, sarcina PVRB. În sistemele centralizate, shard-urile sunt atribuite de un echilibrator; pur și simplu calculează hash-ul din cerere și îl trimite executorului necesar. În blockchain-uri, capacitatea de a influența această misiune poate duce la un atac la consens. De exemplu, conținutul tranzacțiilor poate fi controlat de un atacator, acesta poate controla ce tranzacții ajung la ciobul pe care îl controlează și poate manipula lanțul de blocuri din acesta. Puteți citi o discuție despre problema utilizării numerelor aleatoare pentru sarcini de fragmentare în Ethereum
Sharding-ul este una dintre cele mai ambițioase și serioase probleme din domeniul blockchain-ului; soluția sa va permite construirea de rețele descentralizate de performanță și volum fantastice. PVRB este doar unul dintre blocurile importante pentru a o rezolva.
Jocuri, protocoale economice, arbitraj
Rolul numerelor aleatoare în industria jocurilor de noroc este greu de supraestimat. Utilizarea explicită în cazinourile online și utilizarea implicită atunci când se calculează efectele acțiunii unui jucător sunt toate probleme extrem de dificile pentru rețelele descentralizate, unde nu există nicio modalitate de a te baza pe o sursă centrală de aleatorie. Dar selecția aleatorie poate rezolva și multe probleme economice și poate ajuta la construirea de protocoale mai simple și mai eficiente. Să presupunem că în protocolul nostru există dispute cu privire la 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 să rezolve litigiile în mod aleatoriu, dar cu o probabilitate dată. De exemplu, cu o probabilitate de 60% clientul să câștige, iar cu o probabilitate de 40% să câștige vânzătorul. Această abordare, care este absurdă din primul punct de vedere, vă permite să rezolvați automat litigiile cu o pondere precis previzibilă a câștigurilor/pierderilor, ceea ce se potrivește ambelor părți fără nicio participare a unui terț și pierdere inutilă de timp. Mai mult, raportul de probabilitate poate fi dinamic și depinde de unele variabile globale. De exemplu, dacă o companie se descurcă bine, are un număr redus de dispute și o rentabilitate ridicată, compania poate schimba automat probabilitatea de a rezolva o dispută către centrarea pe client, de exemplu 70/30 sau 80/20 și invers, dacă disputele necesită o mulțime de bani și sunt frauduloase sau inadecvate, puteți muta probabilitatea în cealaltă direcție.
Un număr mare de protocoale descentralizate interesante, cum ar fi registrele cu token, piețele de predicții, curbele de legare și multe altele, sunt jocuri economice în care comportamentul bun este recompensat și comportamentul rău este penalizat. Acestea conțin adesea probleme de securitate pentru care protecțiile sunt în conflict între ele. Ceea ce este protejat de un atac al „balenelor” cu miliarde de jetoane („miză mare”) este vulnerabil la atacurile a mii de conturi cu solduri mici („miza sibilă”) și la măsurile luate împotriva unui singur atac, cum ar fi non- taxele liniare create pentru a face ca lucrul cu o miză mare să fie neprofitabilă sunt de obicei discreditate de un alt atac. Întrucât vorbim de un joc economic, ponderile statistice corespunzătoare pot fi calculate în avans și pur și simplu înlocuiți comisioanele cu unele randomizate cu distribuția corespunzătoare. Astfel de comisioane probabilistice sunt implementate extrem de simplu dacă blockchain-ul are o sursă de încredere de aleatorie și nu necesită calcule complexe, ceea ce face viața dificilă atât pentru balene, cât și pentru sibile.
În același timp, este necesar să ne amintim în continuare că controlul asupra unui singur bit în această aleatorie vă permite să trișați, reducând și mărind probabilitățile la jumătate, așa că un PVRB onest este cea mai importantă componentă a unor astfel de protocoale.
Unde să găsești aleatoria potrivită?
În teorie, selecția aleatorie corectă în rețelele descentralizate face ca aproape orice protocol să fie sigur împotriva coluziei. Rațiunea este destul de simplă - dacă rețeaua este de acord cu un singur bit 0 sau 1 și mai puțin de jumătate dintre participanți sunt necinstiți, atunci, având în vedere suficiente iterații, rețeaua este garantată să ajungă la un consens asupra bitului respectiv cu o probabilitate fixă. Pur și simplu pentru că un aleatoriu sincer va alege 51 din 100 de participanți în 51% din timp. Dar asta este în teorie, pentru că... în rețelele reale, pentru a asigura un asemenea nivel de securitate ca în articole, sunt necesare multe mesaje între gazde, criptografie complexă multi-pass, iar orice complicație a protocolului adaugă imediat noi vectori de atac.
De aceea nu vedem încă un PVRB rezistent dovedit în blockchain-uri, care ar fi fost folosit suficient timp pentru a fi testat de aplicații reale, audituri multiple, încărcări și, bineînțeles, atacuri reale, fără de care este dificil să se numească un produs cu adevărat sigur.
Cu toate acestea, există mai multe abordări promițătoare, diferă în multe detalii și una dintre ele va rezolva cu siguranță problema. Cu resursele de calcul moderne, teoria criptografică poate fi tradusă destul de inteligent în aplicații practice. În viitor, vom fi bucuroși să vorbim despre implementările PVRB: acum există câteva dintre ele, fiecare are propriul său set de proprietăți importante și caracteristici de implementare, iar în spatele fiecăreia există o idee bună. Nu sunt multe echipe implicate în randomizare, iar experiența fiecăreia dintre ele este extrem de importantă pentru toți ceilalți. Sperăm că informațiile noastre vor permite altor echipe să se miște mai repede, ținând cont de experiența predecesorilor lor.
Sursa: www.habr.com