És possible generar números aleatoris si no ens confiem? Part 1

Hola Habr!

En aquest article parlaré de la generació de nombres pseudoaleatoris per part de participants que no confien entre ells. Com veurem a continuació, implementar un generador “quasi” bo és bastant senzill, però un de molt bo és difícil.

Per què caldria generar números aleatoris entre participants que no confien entre ells? Una àrea d'aplicació són les aplicacions descentralitzades. Per exemple, una aplicació que accepta una aposta d'un participant i duplica la quantitat amb una probabilitat del 49% o treu amb una probabilitat del 51% només funcionarà si pot rebre de manera imparcial un nombre aleatori. Si un atacant pot influir en el resultat del generador de números aleatoris, i fins i tot augmentar lleugerament les seves possibilitats de rebre un pagament a l'aplicació, el destruirà fàcilment.

Quan dissenyem un protocol de generació de números aleatoris distribuïts, volem que tingui tres propietats:

1. Ha de ser imparcial. En altres paraules, cap participant hauria d'influir de cap manera en el resultat del generador de números aleatoris.

2. Ha de ser impredictible. En altres paraules, cap participant hauria de poder predir quin número es generarà (o inferir cap de les seves propietats) abans que es generi.

3. El protocol ha de ser viable, és a dir, resistent al fet que un determinat percentatge de participants es desconnecti de la xarxa o intentin aturar el protocol deliberadament.

En aquest article analitzarem dos enfocaments: RANDAO + VDF i l'enfocament dels codis d'esborrat. A la següent part, examinarem en detall l'enfocament basat en les signatures de llindar.

Però primer, mirem un algorisme senzill i d'ús habitual que és viable, impredictible, però esbiaixat.

RANDAO

RANDAO és un enfocament molt senzill i, per tant, molt utilitzat per generar aleatorietat. Tots els participants de la xarxa primer seleccionen localment un número pseudoaleatori, després cada participant envia un hash del número seleccionat. A continuació, els participants, per torns, revelen els seus números escollits i realitzen una operació XOR sobre els números revelats, i el resultat d'aquesta operació es converteix en el resultat del protocol.

El pas de publicar els hash abans de revelar els números és necessari perquè l'atacant no pugui triar el seu número després d'haver vist els números dels altres participants. Això li permetria determinar pràcticament d'una sola mà la sortida del generador de números aleatoris.

Durant el transcurs del protocol, els participants han de prendre una decisió comuna (l'anomenat consens) dues vegades: quan començar a revelar els números seleccionats i, per tant, deixar d'acceptar hash, i quan deixar d'acceptar els números seleccionats i calcular l'atzar resultant. nombre. Prendre aquestes decisions entre participants que no confien entre ells no és una tasca fàcil en si mateixa, i hi tornarem en articles futurs; en aquest article assumirem que aquest algorisme de consens està disponible per a nosaltres.

Quines de les propietats que hem descrit anteriorment té RANDAO? És imprevisible, té la mateixa vitalitat que el protocol de consens subjacent, però és esbiaixat. Concretament, un atacant pot observar la xarxa i, després que altres participants revelin els seus números, pot calcular el seu XOR i decidir si revela o no el seu número per influir en el resultat. Tot i que això impedeix que l'atacant determini per si sol la sortida del generador de números aleatoris, encara li dóna 1 bit d'influència. I si els atacants controlen diversos participants, llavors el nombre de bits que controlen serà igual al nombre de participants sota el seu control.

La influència dels atacants es pot reduir en gran mesura exigint que els participants revelin els números en ordre. Aleshores, l'atacant només podrà influir en el resultat si s'obre l'últim. Tot i que la influència és significativament menor, l'algorisme encara està esbiaixat.

RANDAO+VDF

Una manera de fer que RANDAO sigui imparcial és aquesta: després de revelar tots els números i calcular el XOR, el seu resultat s'introdueix a l'entrada d'una funció, que triga molt de temps a calcular-se, però us permet comprovar la correcció de la funció. càlcul molt ràpid.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Aquesta funció s'anomena Funció de retard verificable o VDF. Si el càlcul del resultat final triga més que l'etapa de revelació del nombre, l'atacant no podrà predir l'efecte de mostrar o amagar el seu número i, per tant, perdrà l'oportunitat d'influir en el resultat.

Desenvolupar bons VDF és extremadament difícil. Darrerament hi ha hagut diversos avenços, p. aquest и això, cosa que va fer que VDF fos més pràctic a la pràctica, i Ethereum 2.0 té previst utilitzar RANDAO amb VDF com a font de números aleatoris a llarg termini. A més del fet que aquest enfocament és impredictible i imparcial, té l'avantatge afegit de ser viable si hi ha almenys dos participants disponibles a la xarxa (suposant que el protocol de consens utilitzat és viable quan es tracta d'un nombre tan reduït de participants).

El repte més gran d'aquest enfocament és configurar el VDF de manera que fins i tot un participant amb un maquinari especialitzat molt car no podrà calcular el VDF abans del final de la fase de descobriment. Idealment, l'algoritme hauria de tenir fins i tot un marge de seguretat important, per exemple 10x. La figura següent mostra un atac d'un actor que té un ASIC especialitzat que li permet executar un VDF més ràpid que el temps assignat per revelar la confirmació de RANDAO. Aquest participant encara pot calcular el resultat final utilitzant o no el seu número, i després, en funció del càlcul, triar si es mostra o no.

Per a la família VDF esmentada anteriorment, el rendiment d'un ASIC dedicat pot ser 100 vegades més gran que el maquinari convencional. Per tant, si la fase de desplegament dura 10 segons, aleshores el VDF calculat en aquest ASIC ha de trigar més de 100 segons a tenir un marge de seguretat 10x i, per tant, el mateix VDF calculat en maquinari bàsic ha de trigar 100x 100 segons = ~ 3 hores.

La Fundació Ethereum té previst resoldre aquest problema creant els seus propis ASIC gratuïts disponibles públicament. Un cop això passi, tots els altres protocols també poden aprofitar aquesta tecnologia, però fins aleshores l'enfocament RANDAO+VDF no serà tan viable per als protocols que no poden invertir en el desenvolupament dels seus propis ASIC.

S'han recopilat molts articles, vídeos i altra informació sobre VDF aquest lloc.

Utilitzem codis d'esborrat

En aquesta secció, veurem un protocol de generació de números aleatoris que utilitza esborrant codis. Pot tolerar fins a ⅓ atacants mentre es manté viable i permet que existeixin fins a ⅔ atacants abans que puguin predir o influir en el resultat.

La idea principal del protocol és la següent. Per simplificar, suposem que hi ha exactament 100 participants. Suposem també que tots els participants localment tenen alguna clau privada i les claus públiques de tots els participants són conegudes per tots els participants:

1. Cada participant crea localment una cadena llarga, la divideix en 67 parts, crea codis d'esborrat per obtenir 100 accions de manera que 67 són suficients per recuperar la cadena, assigna cadascuna de les 100 accions a un dels participants i les xifra amb la clau pública del mateix participant. Tot seguit es publiquen totes les accions codificades.

2. Els participants utilitzen algun tipus de consens per arribar a un acord sobre conjunts codificats de 67 participants específics.

3. Un cop arribat al consens, cada participant pren les accions codificades en cadascun dels 67 conjunts xifrats amb la seva clau pública, desxifra totes aquestes accions i publica totes aquestes accions desxifrades.

4. Un cop 67 participants hagin completat el pas (3), tots els conjunts acordats es poden descodificar i reconstruir completament a causa de les propietats dels codis d'esborrat, i el número final es pot obtenir com a XOR de les files inicials amb les quals els participants van començar a (1). .

Es pot demostrar que aquest protocol és imparcial i impredictible. El nombre aleatori resultant es determina després d'arribar al consens, però ningú no ho coneix fins que ⅔ dels participants descodifiquen les parts xifrades amb la seva clau pública. Així, el nombre aleatori es determina abans que es publiqui informació suficient per reconstruir-lo.

Què passa si al pas (1) un dels participants va enviar comparticions codificades als altres participants que no són el codi d'esborrat correcte per a alguna cadena? Sense canvis addicionals, els diferents participants no podran recuperar la cadena en absolut, o bé recuperaran diferents cadenes, cosa que farà que diferents participants rebin un nombre aleatori diferent. Per evitar-ho, podeu fer el següent: cada participant, a més de les accions codificades, també calcula Arbre Merkla totes aquestes accions, i envia a cada participant tant la pròpia quota codificada com l'arrel de l'arbre merkle, i una prova de la inclusió de la quota a l'arbre merkle. En el consens del pas (2), els participants no només es posen d'acord en un conjunt de conjunts, sinó en un conjunt d'arrels específiques d'aquests arbres (si algun participant es va desviar del protocol i va enviar diferents arrels d'arbre merkle a diferents participants, i dues d'aquestes arrels es mostren durant el consens, la fila no s'inclou al conjunt de resultats). Com a resultat del consens, tindrem 67 línies codificades i les arrels corresponents de l'arbre merkle de manera que hi hagi almenys 67 participants (no necessàriament els mateixos que van proposar les línies corresponents), que per a cadascuna de les 67 línies tenen un missatge amb una part del codi d'esborrat i una prova de l'aparició de la seva participació a l'arbre corresponent es va esvair.

Quan al pas (4) el participant desxifra 67 batecs per a una determinada corda i intenta reconstruir-ne la corda original, una de les opcions és possible:

1. La cadena es restaura, i si després es torna a codificar per esborrar i es calcula l'arbre de Merkle per a les accions calculades localment, l'arrel coincideix amb aquella sobre la qual s'ha arribat al consens.

2. La fila es restaura, però l'arrel calculada localment no coincideix amb la que s'ha arribat al consens.

3. La fila no es restaura.

És fàcil demostrar que si l'opció (1) es va produir com a mínim per a un participant anterior, llavors l'opció (1) es va produir per a tots els participants, i viceversa, si l'opció (2) o (3) es va produir per a almenys un participant, aleshores per a tots els participants es farà l'opció (2) o (3). Així, per a cada fila del conjunt, o bé tots els participants la recuperaran amb èxit, o bé tots els participants no la recuperaran. El nombre aleatori resultant és llavors un XOR de només les files que els participants van poder recuperar.

Signatures de llindar

Un altre enfocament de l'atzar és utilitzar el que s'anomenen signatures de llindar BLS. Un generador de números aleatoris basat en signatures de llindar té exactament les mateixes garanties que l'algorisme basat en codi d'esborrat descrit anteriorment, però té un nombre asimptòtic de missatges enviats a la xarxa significativament menor per a cada número generat.

Les signatures BLS són un disseny que permet a diversos participants crear una signatura comuna per a un missatge. Aquestes signatures s'utilitzen sovint per estalviar espai i amplada de banda ja que no requereixen que s'enviïn diverses signatures. 

Una aplicació habitual per a signatures BLS en protocols blockchain, a més de generar números aleatoris, és la signatura de blocs en protocols BFT. Suposem que 100 participants creen blocs i un bloc es considera definitiu si 67 d'ells el signen. Tots poden enviar les seves parts de la signatura BLS i utilitzar algun algorisme de consens per acordar-ne 67 i després combinar-les en una signatura BLS. Es poden utilitzar 67 parts (o més) per crear la signatura final, que dependrà de quines 67 signatures s'hagin combinat i, per tant, pot variar, encara que les diferents opcions dels 67 participants crearan una signatura diferent, qualsevol signatura d'aquest tipus serà vàlida. signatura del bloc. Aleshores, els participants restants només han de rebre i verificar només una signatura per bloc, en lloc de 67, a la xarxa, la qual cosa redueix significativament la càrrega a la xarxa.

Resulta que si les claus privades que utilitzen els participants es generen d'una manera determinada, no importa quines 67 signatures (o més, però no menys) s'agreguin, la signatura resultant serà la mateixa. Això es pot utilitzar com a font d'aleatorietat: els participants primer es posen d'acord en algun missatge que signaran (pot ser la sortida de RANDAO o només el hash de l'últim bloc, realment no importa sempre que canviï cada vegada). i és coherent) i creeu-hi una signatura BLS. El resultat de la generació serà impredictible fins que 67 participants proporcionin les seves parts, i després d'això la sortida ja està predeterminada i no pot dependre de les accions de cap participant.

Aquest enfocament de l'aleatorietat és viable sempre que almenys ⅔ dels participants en línia segueixin el protocol, i sigui imparcial i impredictible sempre que almenys ⅓ dels participants segueixin el protocol. És important tenir en compte que un atacant que controla més de ⅓ però menys de ⅔ dels participants pot aturar el protocol, però no pot predir ni influir en la seva sortida.

Les signatures de llindar en si són un tema molt interessant. A la segona part de l'article, analitzarem detalladament com funcionen i com és exactament necessari generar les claus dels participants perquè les signatures de llindar es puguin utilitzar com a generador de números aleatoris.

en conclusió

Aquest article és el primer d'una sèrie d'articles tècnics del bloc A PROP. NEAR és un protocol i una plataforma blockchain per desenvolupar aplicacions descentralitzades amb èmfasi en la facilitat de desenvolupament i la facilitat d'ús per als usuaris finals.

El codi del protocol és obert, la nostra implementació està escrita en Rust, es pot trobar aquí.

Podeu veure com és el desenvolupament de NEAR i experimentar a l'IDE en línia aquí.

Podeu seguir totes les notícies en rus a grup de telegrames i grup a VKontakte, i en anglès a l'oficial twitter.

Fins aviat!

Font: www.habr.com