É posible xerar números aleatorios se non confiamos uns nos outros? Parte 1

Ola Habr!

Neste artigo falarei sobre a xeración de números pseudoaleatorios por parte dos participantes que non confían entre si. Como veremos a continuación, implementar un xerador "case" bo é bastante sinxelo, pero un moi bo é difícil.

Por que sería necesario xerar números aleatorios entre os participantes que non confían uns nos outros? Unha das áreas de aplicación son as aplicacións descentralizadas. Por exemplo, unha aplicación que acepta unha aposta dun participante e duplica a cantidade cunha probabilidade do 49 % ou quita cunha probabilidade do 51 % só funcionará se pode recibir un número aleatorio de forma imparcial. Se un atacante pode influír no resultado do xerador de números aleatorios, e incluso aumentar lixeiramente as súas posibilidades de recibir un pago na aplicación, devasalo facilmente.

Cando deseñamos un protocolo de xeración de números aleatorios distribuídos, queremos que teña tres propiedades:

1. Debe ser imparcial. Noutras palabras, ningún participante debería influír de ningún xeito no resultado do xerador de números aleatorios.

2. Debe ser imprevisible. Noutras palabras, ningún participante debería poder predicir que número se xerará (ou inferir algunha das súas propiedades) antes de que se xere.

3. O protocolo debe ser viable, é dicir, resistente ao feito de que unha determinada porcentaxe de participantes se desconecte da rede ou intente deter o protocolo deliberadamente.

Neste artigo veremos dous enfoques: RANDAO + VDF e o enfoque de códigos de borrado. Na seguinte parte, examinaremos en detalle o enfoque baseado nas sinaturas de limiar.

Pero primeiro, vexamos un algoritmo sinxelo e de uso común que é viable, imprevisible, pero tendencioso.

RANDAO

RANDAO é un enfoque moi sinxelo e, polo tanto, bastante usado para xerar aleatoriedade. Todos os participantes da rede seleccionan primeiro localmente un número pseudoaleatorio, despois cada participante envía un hash do número seleccionado. A continuación, os participantes por quendas revelan os seus números escollidos e realizan unha operación XOR sobre os números revelados, e o resultado desta operación convértese no resultado do protocolo.

O paso de publicar os hash antes de revelar os números é necesario para que o atacante non poida escoller o seu número despois de ver os números dos outros participantes. Isto permitiríalle determinar practicamente só a saída do xerador de números aleatorios.

Durante o transcurso do protocolo, os participantes deben tomar unha decisión común (o chamado consenso) dúas veces: cando comezar a revelar os números seleccionados e, polo tanto, deixar de aceptar hash, e cando deixar de aceptar os números seleccionados e calcular o aleatorio resultante. número. Tomar tales decisións entre participantes que non confían uns nos outros non é unha tarefa fácil en si mesma, e volveremos sobre ela en artigos futuros; neste artigo asumiremos que este algoritmo de consenso está dispoñible para nós.

Cales das propiedades que describimos anteriormente ten RANDAO? É imprevisible, ten a mesma vitalidade que o protocolo de consenso subxacente, pero é sesgado. En concreto, un atacante pode observar a rede, e despois de que outros participantes revelan os seus números, pode calcular o seu XOR e decidir se revela ou non o seu número para influír no resultado. Aínda que isto impide que o atacante determine por si só a saída do xerador de números aleatorios, aínda lle dá 1 bit de influencia. E se os atacantes controlan varios participantes, entón o número de bits que controlan será igual ao número de participantes baixo o seu control.

A influencia dos atacantes pódese reducir moito esixindo que os participantes revelen os números en orde. Entón, o atacante poderá influír no resultado só se abre o último. Aínda que a influencia é significativamente menor, o algoritmo aínda está sesgado.

RANDAO+VDF

Unha forma de facer que RANDAO sexa imparcial é esta: despois de que se revelan todos os números e se calcula o XOR, o seu resultado introdúcese na entrada dunha función, o que leva moito tempo calculalo, pero permite comprobar a corrección da función. cálculo moi rápido.

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

Esta función chámase Función de retardo verificable ou VDF. Se o cálculo do resultado final leva máis tempo que a fase de revelación do número, entón o atacante non poderá predicir o efecto de mostrar ou ocultar o seu número e, polo tanto, perderá a oportunidade de influír no resultado.

Desenvolver bos VDF é moi difícil. Houbo varios avances recentemente, por exemplo. isto и isto, o que fixo que VDF fose máis práctico na práctica, e Ethereum 2.0 planea usar RANDAO con VDF como fonte de números aleatorios a longo prazo. Ademais de que este enfoque é imprevisible e imparcial, ten a vantaxe adicional de ser viable se hai polo menos dous participantes dispoñibles na rede (asumindo que o protocolo de consenso utilizado é viable cando se trata cun número tan reducido de participantes).

O maior reto deste enfoque é configurar o VDF de forma que nin sequera un participante cun hardware especializado moi caro non poida calcular o VDF antes do final da fase de descubrimento. O ideal é que o algoritmo teña unha marxe de seguridade importante, digamos 10x. A seguinte figura mostra un ataque dun actor que ten un ASIC especializado que lle permite executar un VDF máis rápido que o tempo asignado para revelar a confirmación de RANDAO. Este participante aínda pode calcular o resultado final utilizando ou non o seu número e, a continuación, en función do cálculo, escoller se quere mostralo ou non.

Para a familia VDF mencionada anteriormente, o rendemento dun ASIC dedicado pode ser máis de 100 veces superior ao do hardware convencional. Polo tanto, se a fase de implantación dura 10 segundos, entón o VDF calculado nun ASIC debe tardar máis de 100 segundos en ter unha marxe de seguridade 10x e, polo tanto, o mesmo VDF calculado en hardware básico debe tardar 100x 100 segundos = ~3 horas.

A Fundación Ethereum planea resolver este problema creando os seus propios ASIC gratuítos dispoñibles para o público. Unha vez que isto ocorra, todos os demais protocolos tamén poden aproveitar esta tecnoloxía, pero ata entón o enfoque RANDAO+VDF non será tan viable para os protocolos que non poden investir no desenvolvemento dos seus propios ASIC.

Recopiláronse moitos artigos, vídeos e outra información sobre VDF este sitio.

Usamos códigos de borrado

Nesta sección, analizaremos un protocolo de xeración de números aleatorios que utiliza borrando códigos. Pode tolerar ata ⅓ atacantes mentres segue sendo viable, e permite que existan ata ⅔ atacantes antes de que poidan predicir ou influír no resultado.

A idea principal do protocolo é a seguinte. Para simplificar, supoñamos que hai exactamente 100 participantes. Supoñamos tamén que todos os participantes teñen localmente algunha clave privada e que as claves públicas de todos os participantes son coñecidas por todos os participantes:

1. Cada participante crea localmente unha cadea longa, divídea en 67 partes, crea códigos de borrado para obter 100 accións de tal forma que as 67 son suficientes para recuperar a cadea, asígnalle cada unha das 100 partes a un dos participantes e cífraas con a chave pública do mesmo participante. Despois publícanse todas as accións codificadas.

2. Os participantes usan algún tipo de consenso para chegar a un acordo sobre conxuntos codificados de 67 participantes específicos.

3. Unha vez que se alcanza o consenso, cada participante toma as accións codificadas en cada un dos 67 conxuntos cifradas coa súa chave pública, descifra todas esas accións e publica todas as accións descifradas.

4. Unha vez que 67 participantes completaron o paso (3), todos os conxuntos acordados poden ser completamente decodificados e reconstruídos debido ás propiedades dos códigos de borrado, e o número final pódese obter como XOR das filas iniciais coas que comezaron os participantes en (1). .

Pódese demostrar que este protocolo é imparcial e imprevisible. O número aleatorio resultante determínase despois de alcanzar o consenso, pero ninguén o coñece ata que ⅔ dos participantes descodifique as partes cifradas coa súa clave pública. Así, o número aleatorio determínase antes de que se publique a información suficiente para reconstruílo.

Que ocorre se no paso (1) un dos participantes enviou contido compartido codificado aos outros participantes que non son o código de borrado correcto para algunha cadea? Sen cambios adicionais, os diferentes participantes non poderán recuperar a cadea en absoluto ou recuperarán diferentes cadeas, o que provocará que os diferentes participantes reciban un número aleatorio diferente. Para evitalo, podes facer o seguinte: cada participante, ademais das accións codificadas, tamén calcula Merkla árbore todas esas accións, e envía a cada participante tanto a propia acción codificada como a raíz da árbore merkle, e unha proba da inclusión da participación na árbore merkle. No consenso no paso (2), os participantes non só acordan un conxunto de conxuntos, senón un conxunto de raíces específicas de tales árbores (se algún participante se desviou do protocolo e enviou diferentes raíces de árbores merkle a diferentes participantes, e dúas tales raíces móstranse durante o consenso, a fila non está incluída no conxunto de resultados). Como resultado do consenso, teremos 67 liñas codificadas e as raíces correspondentes da árbore de merkle de forma que haxa polo menos 67 participantes (non necesariamente os mesmos que propuxeron as liñas correspondentes), que para cada unha das 67 liñas teñen desapareceu unha mensaxe cunha parte do código de borrado e unha proba da aparición da súa participación na árbore correspondente.

Cando no paso (4) o participante descifra 67 pulsacións para unha determinada corda e intenta reconstruír a cadea orixinal a partir delas, é posible unha das opcións:

1. A cadea restablece e se volve a codificar mediante o borrado e calcúlase a árbore de Merkle para as accións calculadas localmente, a raíz coincide coa que se chegou ao consenso.

2. Restaurase a fila, pero a raíz calculada localmente non coincide coa que se chegou ao consenso.

3. Non se restaura a fila.

É fácil demostrar que se a opción (1) ocorreu para polo menos un participante anterior, entón a opción (1) ocorreu para todos os participantes, e viceversa, se a opción (2) ou (3) ocorreu para polo menos un participante, entón para todos os participantes terá lugar a opción (2) ou (3). Así, para cada fila do conxunto, ou ben todos os participantes a recuperarán con éxito, ou todos os participantes non poderán recuperala. O número aleatorio resultante é entón un XOR de só as filas que os participantes puideron recuperar.

Sinaturas de limiar

Outra aproximación á aleatoriedade é usar o que se chama sinaturas de limiar BLS. Un xerador de números aleatorios baseado en sinaturas de limiar ten exactamente as mesmas garantías que o algoritmo baseado en código de borrado descrito anteriormente, pero ten un número asintótico significativamente menor de mensaxes enviadas pola rede para cada número xerado.

As sinaturas BLS son un deseño que permite a varios participantes crear unha sinatura común para unha mensaxe. Estas sinaturas úsanse a miúdo para aforrar espazo e ancho de banda ao non esixir que se envíen varias sinaturas. 

Unha aplicación común para sinaturas BLS nos protocolos blockchain, ademais de xerar números aleatorios, é a firma de bloques nos protocolos BFT. Digamos que 100 participantes crean bloques e un bloque considérase definitivo se o asinan 67 deles. Todos poden enviar as súas partes da sinatura BLS e usar algún algoritmo de consenso para acordar 67 delas e, a continuación, fusionalas nunha soa sinatura BLS. Pódense usar 67 (ou máis) partes para crear a sinatura final, que dependerá das 67 sinaturas combinadas e, polo tanto, pode variar, aínda que as diferentes opcións dos 67 participantes crearán unha sinatura diferente, calquera sinatura deste tipo será válida. sinatura para o bloque. Os participantes restantes só necesitan recibir e verificar só unha sinatura por bloque, en lugar de 67, a través da rede, o que reduce significativamente a carga na rede.

Acontece que se as claves privadas que usan os participantes se xeran dun xeito determinado, sen importar que 67 sinaturas (ou máis, pero non menos) estean agregadas, a sinatura resultante será a mesma. Isto pódese usar como fonte de aleatoriedade: os participantes primeiro acordan algunha mensaxe que van asinar (esta podería ser a saída de RANDAO ou só o hash do último bloque, non importa sempre que cambie cada vez). e é consistente) e crea unha sinatura BLS para iso. O resultado da xeración será imprevisible ata que 67 participantes proporcionen as súas partes, e despois diso a saída xa está predeterminada e non pode depender das accións de ningún participante.

Este enfoque da aleatoriedade é viable sempre que polo menos ⅔ dos participantes en liña sigan o protocolo, e é imparcial e imprevisible sempre que polo menos ⅓ dos participantes siga o protocolo. É importante ter en conta que un atacante que controla máis de ⅓ pero menos de ⅔ dos participantes pode deter o protocolo, pero non pode predicir nin influír na súa saída.

As sinaturas de limiar son un tema moi interesante. Na segunda parte do artigo analizaremos en detalle como funcionan, e como é exactamente necesario xerar claves de participantes para que as sinaturas de limiar se poidan utilizar como xerador de números aleatorios.

En conclusión

Este artigo é o primeiro dunha serie de artigos de blog técnico PRÓXIMO. NEAR é un protocolo e unha plataforma blockchain para desenvolver aplicacións descentralizadas con énfase na facilidade de desenvolvemento e de uso para os usuarios finais.

O código do protocolo está aberto, a nosa implementación está escrita en Rust, pódese atopar aquí.

Podes ver como é o desenvolvemento de NEAR e experimentar no IDE en liña aquí.

Podes seguir todas as novidades en ruso en grupo telegrama e grupo en VKontakte, e en inglés no oficial twitter.

Vémonos pronto!

Fonte: www.habr.com