Introducció
"La generació de números aleatoris és massa important per deixar-la a l'atzar".
Robert Cavue, 1970
Aquest article està dedicat a l'aplicació pràctica de solucions que utilitzen la generació de números aleatoris col·lectius en un entorn no fiable. En resum, com i per què s'utilitza l'atzar a les cadenes de blocs, i una mica sobre com distingir "bo" aleatori de "dolent". Generar un nombre realment aleatori és un problema extremadament difícil, fins i tot en un sol ordinador, i ha estat estudiat durant molt de temps pels criptògrafs. Bé, a les xarxes descentralitzades, la generació de números aleatoris és encara més complexa i important.
És a les xarxes on els participants no confien entre ells que la capacitat de generar un nombre aleatori indiscutible ens permet resoldre eficaçment molts problemes crítics i millorar significativament els esquemes existents. A més, els jocs d'atzar i les loteries no són l'objectiu número u aquí, com pot semblar al principi al lector sense experiència.
Generació de números aleatoris
Els ordinadors no poden generar nombres aleatoris ells mateixos; necessiten ajuda externa per fer-ho. L'ordinador pot obtenir algun valor aleatori de, per exemple, els moviments del ratolí, la quantitat de memòria utilitzada, els corrents dispersos als pins del processador i moltes altres fonts anomenades fonts d'entropia. Aquests valors en si mateixos no són completament aleatoris, ja que es troben en un rang determinat o tenen un patró de canvis previsible. Per convertir aquests nombres en un nombre realment aleatori dins d'un rang determinat, se'ls apliquen criptotransformacions per produir valors pseudoaleatoris distribuïts uniformement a partir dels valors distribuïts desigualment de la font d'entropia. Els valors resultants s'anomenen pseudoaleatoris perquè no són realment aleatoris, sinó que es deriven determinísticament de l'entropia. Qualsevol bon algorisme criptogràfic, quan xifra dades, produeix textos xifrats que haurien de ser estadísticament indistinguibles d'una seqüència aleatòria, de manera que per produir aleatorietat es pot prendre una font d'entropia, que només proporciona una bona repetibilitat i impredictibilitat dels valors fins i tot en intervals petits, el la resta del treball s'està dispersant i barrejant bits El valor resultant serà assumit per l'algorisme de xifratge.
Per completar un breu programa educatiu, afegiré que generar números aleatoris fins i tot en un dispositiu és un dels pilars per garantir la seguretat de les nostres dades. Els números pseudoaleatoris generats s'utilitzen quan s'estableixen connexions segures en diverses xarxes, per generar claus criptogràfiques, per equilibrar la càrrega, controlar la integritat i per a moltes més aplicacions. La seguretat de molts protocols depèn de la capacitat de generar una aleatoria fiable i impredictible externament, emmagatzemar-la i no revelar-la fins al següent pas del protocol, en cas contrari la seguretat es veurà compromesa. Un atac a un generador de valor pseudoaleatori és extremadament perillós i amenaça immediatament tot el programari que utilitza la generació aleatòria.
Tot això ho hauríeu de saber si heu fet un curs bàsic de criptografia, així que continuem amb les xarxes descentralitzades.
Aleatori en blockchains
En primer lloc, parlaré de les cadenes de blocs amb suport per a contractes intel·ligents; són les que poden aprofitar plenament les oportunitats que ofereix una aleatorietat d'alta qualitat i innegable. A més, per concisió, anomenaré aquesta tecnologia "Balises aleatòries verificables públicament” o PVRB. Com que les cadenes de blocs són xarxes en les quals qualsevol participant pot verificar la informació, la part clau del nom és "Verificable públicament", és a dir. Qualsevol pot utilitzar els càlculs per obtenir la prova que el número resultant publicat a la cadena de blocs té les propietats següents:
- El resultat ha de tenir una distribució prou uniforme, és a dir, basar-se en una criptografia prou forta.
- No és possible controlar cap dels bits del resultat. Com a conseqüència, el resultat no es pot predir amb antelació.
- No podeu sabotejar el protocol de generació no participant en el protocol o sobrecarregant la xarxa amb missatges d'atac
- Tot l'anterior ha de ser resistent a la connivència d'un nombre admissible de participants del protocol deshonestos (per exemple, 1/3 dels participants).
Qualsevol possibilitat que un grup menor de participants en col·lusió produeixi fins i tot un aleatori parell/senir controlat és un forat de seguretat. Qualsevol capacitat del grup per aturar l'emissió de l'atzar és un forat de seguretat. En general, hi ha molts problemes, i aquesta tasca no és fàcil...
Sembla que l'aplicació més important de PVRB són diversos jocs, loteries i, en general, qualsevol tipus de joc a la cadena de blocs. De fet, aquesta és una direcció important, però l'atzar a les cadenes de blocs té aplicacions encara més importants. Mirem-los.
Algoritmes de consens
PVRB té un paper important en l'organització del consens de la xarxa. Les transaccions en blockchains estan protegides per una signatura electrònica, de manera que un "atac a una transacció" sempre és la inclusió/exclusió d'una transacció en un bloc (o diversos blocs). I la tasca principal de l'algoritme de consens és acordar l'ordre d'aquestes transaccions i l'ordre dels blocs que inclouen aquestes transaccions. A més, una propietat necessària per a les cadenes de blocs reals és la finalitat: la capacitat de la xarxa d'acordar que la cadena fins al bloc finalitzat és definitiva i mai s'exclourà a causa de l'aparició d'una nova bifurcació. Normalment, per acordar que un bloc és vàlid i, el més important, definitiu, cal recollir signatures de la majoria de productors de blocs (d'ara endavant BP - productors de blocs), que requereix almenys lliurar la cadena de blocs. a tots els BP, i repartint signatures entre tots els BP. A mesura que el nombre de BP creix, el nombre de missatges necessaris a la xarxa creix exponencialment, per tant, els algorismes de consens que requereixen finalitat, utilitzats per exemple en el consens Hyperledger pBFT, no funcionen a la velocitat requerida, a partir de diverses desenes de BP, que requereixen un gran nombre de connexions.
Si hi ha un PVRB innegable i honest a la xarxa, aleshores, fins i tot en l'aproximació més simple, es pot triar un dels productors de blocs a partir d'ell i nomenar-lo com a "líder" durant una ronda del protocol. Si tenim N productors de blocs, dels quals M: M > 1/2 N siguin honestos, no censureu les transaccions i no bifurqueu la cadena per dur a terme un atac de "doble despesa", aleshores utilitzar un PVRB sense qüestionar distribuït uniformement permetrà triar un líder honest amb probabilitat. M / N (M / N > 1/2). Si a cada líder se li assigna el seu propi interval de temps durant el qual pot produir un bloc i validar la cadena, i aquests intervals són iguals en el temps, aleshores la cadena de blocs de BP honestos serà més llarga que la cadena formada per BP maliciosos i el consens. L'algorisme es basa en la longitud de la cadena, simplement descartarà el "dolent". Aquest principi d'assignació de parts iguals de temps a cada BP es va aplicar per primera vegada a Graphene (el predecessor d'EOS), i permet tancar la majoria de blocs amb una sola signatura, la qual cosa redueix molt la càrrega de la xarxa i permet que aquest consens funcioni de manera extremadament ràpida i ràpida. constantment. Tanmateix, la xarxa EOS ara ha d'utilitzar blocs especials (Last Irreversible Block), que es confirmen amb les signatures de 2/3 BP. Aquests blocs serveixen per assegurar la finalitat (la impossibilitat que una bifurcació de cadena comenci abans de l'últim bloc irreversible).
A més, en les implementacions reals, l'esquema del protocol és més complicat: la votació dels blocs proposats es duu a terme en diverses etapes per mantenir la xarxa en cas que faltin blocs i problemes amb la xarxa, però fins i tot tenint-ho en compte, els algorismes de consens que utilitzen PVRB requereixen significativament menys missatges entre BP, cosa que permet fer-los més ràpids que els PVFT tradicionals o les seves diverses modificacions.
El representant més destacat d'aquests algorismes: de l'equip de Cardano, que es diu que és demostrable matemàticament contra la connivència BP.
A Ouroboros, PVRB s'utilitza per definir l'anomenat "programa BP": un calendari segons el qual a cada BP se li assigna la seva pròpia franja horària per publicar un bloc. El gran avantatge d'utilitzar PVRB és la "igualtat" completa dels BP (segons la mida dels seus balanços). La integritat del PVRB garanteix que els BP maliciosos no poden controlar la programació de les franges horàries i, per tant, no poden manipular la cadena preparant i analitzant les bifurcacions de la cadena per endavant, i per seleccionar una bifurcació n'hi ha prou amb confiar simplement en la longitud de la cadena. cadena, sense utilitzar maneres complicades de calcular la "utilitat" de BP i el "pes" dels seus blocs.
En general, en tots els casos en què cal escollir un participant aleatori en una xarxa descentralitzada, PVRB és gairebé sempre la millor opció, en lloc d'una opció determinista basada, per exemple, en un hash de bloc. Sense PVRB, la capacitat d'influir en l'elecció d'un participant condueix a atacs en què l'atacant pot triar entre diversos futurs per triar el següent participant corrupte o diversos alhora per garantir una major participació en la decisió. L'ús de PVRB desacredita aquest tipus d'atacs.
Escalat i equilibri de càrrega
PVRB també pot ser de gran benefici en tasques com la reducció de càrrega i l'escala de pagaments. Per començar, té sentit familiaritzar-se Rivesta “Billets de loteria electrònica com a micropagaments”. La idea general és que en comptes de fer 100 pagaments 1c del pagador al destinatari, podeu jugar a una loteria honesta amb un premi d'1$ = 100c, on el pagador dóna al banc un dels 1 dels seus "tiquets de loteria" per a cadascun. 100c pagament. Un d'aquests bitllets guanya un pot d'1 $, i és aquest bitllet que el destinatari pot gravar a la cadena de blocs. El més important és que els 99 bitllets restants es transfereixin entre el destinatari i el pagador sense cap participació externa, a través d'un canal privat i a la velocitat que es vulgui. Es pot llegir una bona descripció del protocol basat en aquest esquema a la xarxa Emercoin .
Aquest esquema té alguns problemes, com ara que el destinatari pot deixar de servir al pagador immediatament després de rebre un bitllet guanyador, però per a moltes aplicacions especials, com ara la facturació per minut o les subscripcions electròniques als serveis, es poden descuidar. El principal requisit, per descomptat, és l'equitat de la loteria, i per a la seva implementació és absolutament necessari un PVRB.
L'elecció d'un participant aleatori també és extremadament important per als protocols de fragmentació, el propòsit dels quals és escalar horitzontalment la cadena de blocs, permetent que diferents BP processin només el seu abast de transaccions. Aquesta és una tasca extremadament difícil, sobretot pel que fa a la seguretat a l'hora de combinar fragments. La selecció justa d'un BP aleatori amb el propòsit d'assignar els responsables d'un fragment específic, com en els algorismes de consens, també és tasca del PVRB. En els sistemes centralitzats, els fragments són assignats per un equilibrador; simplement calcula el hash de la sol·licitud i l'envia a l'executor requerit. A les cadenes de blocs, la capacitat d'influir en aquesta missió pot provocar un atac al consens. Per exemple, el contingut de les transaccions pot ser controlat per un atacant, pot controlar quines transaccions van al fragment que controla i manipular la cadena de blocs que hi ha. Podeu llegir una discussió sobre el problema de l'ús de números aleatoris per a tasques de fragmentació a Ethereum
El fragmentació és un dels problemes més ambiciosos i greus en el camp de la cadena de blocs; la seva solució permetrà construir xarxes descentralitzades de rendiment i volum fantàstics. PVRB és només un dels blocs importants per resoldre'l.
Jocs, protocols econòmics, arbitratge
El paper dels números aleatoris a la indústria del joc és difícil de sobreestimar. L'ús explícit als casinos en línia i l'ús implícit a l'hora de calcular els efectes de l'acció d'un jugador són problemes extremadament difícils per a les xarxes descentralitzades, on no hi ha manera de confiar en una font central d'aleatorietat. Però la selecció aleatòria també pot resoldre molts problemes econòmics i ajudar a construir protocols més senzills i eficients. Suposem que al nostre protocol hi ha disputes sobre el pagament d'alguns serveis de baix cost, i aquestes disputes es produeixen molt poques vegades. En aquest cas, si hi ha un PVRB indiscutible, els clients i els venedors poden acordar resoldre els conflictes de manera aleatòria, però amb una probabilitat determinada. Per exemple, amb un 60% de probabilitat que guanyi el client, i amb un 40% de probabilitat que guanyi el venedor. Aquest plantejament, absurd des del primer punt de vista, permet resoldre automàticament les disputes amb una proporció de guanys/pèrdues precisament previsible, que s'adapta a les dues parts sense cap participació de tercers i una pèrdua de temps innecessària. A més, la relació de probabilitat pot ser dinàmica i dependre d'algunes variables globals. Per exemple, si una empresa va bé, té un nombre baix de disputes i una alta rendibilitat, l'empresa pot canviar automàticament la probabilitat de resoldre un conflicte cap al centrat en el client, per exemple 70/30 o 80/20, i viceversa, si les disputes requereixen molts diners i són fraudulentes o inadequades, podeu canviar la probabilitat en una altra direcció.
Un gran nombre de protocols descentralitzats interessants, com ara registres seleccionats per tokens, mercats de predicció, corbes d'enllaç i molts altres, són jocs econòmics en què es premia el bon comportament i es penalitza el mal comportament. Sovint contenen problemes de seguretat per als quals les proteccions entren en conflicte. El que està protegit d'un atac de "balenes" amb milers de milions de fitxes ("gran aposta") és vulnerable als atacs de milers de comptes amb saldos reduïts ("sybil stake") i les mesures preses contra un únic atac, com ara no Les tarifes lineals creades per fer no rendible treballar amb una gran participació solen quedar desacreditades per un altre atac. Com que estem parlant d'un joc econòmic, es poden calcular prèviament els pesos estadístics corresponents, i simplement substituir les comissions per unes aleatòries amb la distribució adequada. Aquestes comissions probabilístiques s'implementen de manera extremadament senzilla si la cadena de blocs té una font fiable d'aleatorietat i no requereix cap càlcul complex, cosa que dificulta la vida tant a les balenes com a les sibil·les.
Al mateix temps, cal seguir recordant que el control d'un únic bit en aquesta aleatorietat permet fer trampes, reduint i augmentant les probabilitats a la meitat, de manera que un PVRB honest és el component més important d'aquests protocols.
On trobar l'atzar adequat?
En teoria, la selecció aleatòria justa a les xarxes descentralitzades fa que gairebé qualsevol protocol sigui segur contra la col·lusió. La raó és bastant senzilla: si la xarxa està d'acord en un únic bit 0 o 1, i menys de la meitat dels participants són deshonestos, aleshores, donades prou iteracions, es garanteix que la xarxa arribarà a un consens sobre aquest bit amb una probabilitat fixa. Simplement perquè un aleatori honest triarà 51 de 100 participants el 51% del temps. Però això és en teoria, perquè... a les xarxes reals, per garantir un nivell de seguretat com en els articles, es requereixen molts missatges entre hosts, una criptografia complexa de múltiples passades i qualsevol complicació del protocol afegeix de seguida nous vectors d'atac.
És per això que encara no veiem un PVRB resistent provat a les cadenes de blocs, que s'hauria utilitzat durant prou temps per ser provat per aplicacions reals, auditories múltiples, càrregues i, per descomptat, atacs reals, sense els quals és difícil anomenar un producte realment segur.
No obstant això, hi ha diversos enfocaments prometedors, difereixen en molts detalls i un d'ells definitivament solucionarà el problema. Amb els recursos informàtics moderns, la teoria criptogràfica es pot traduir de manera molt intel·ligent a aplicacions pràctiques. En el futur, estarem encantats de parlar de les implementacions de PVRB: ara n'hi ha diverses, cadascuna té el seu propi conjunt de propietats importants i característiques d'implementació, i darrere de cadascuna hi ha una bona idea. No hi ha molts equips implicats en l'aleatorització, i l'experiència de cadascun d'ells és extremadament important per a tots els altres. Esperem que la nostra informació permeti a altres equips avançar més ràpidament, tenint en compte l'experiència dels seus predecessors.
Font: www.habr.com