¿Es posible generar números aleatorios si no confiamos unos en otros? Parte 1

¡Hola, Habr!

En este artículo hablaré sobre la generación de números pseudoaleatorios por parte de participantes que no confían entre sí. Como veremos a continuación, implementar un generador “casi” bueno es bastante sencillo, pero uno muy bueno es difícil.

¿Por qué sería necesario generar números aleatorios entre los participantes que no confían entre sí? Un área de aplicación son las aplicaciones descentralizadas. Por ejemplo, una aplicación que acepta una apuesta de un participante y duplica la cantidad con un 49% de probabilidad o la quita con un 51% de probabilidad solo funcionará si puede recibir de manera imparcial un número aleatorio. Si un atacante puede influir en el resultado del generador de números aleatorios e incluso aumentar ligeramente sus posibilidades de recibir un pago en la aplicación, fácilmente lo devastará.

Cuando diseñamos un protocolo de generación distribuida de números aleatorios, queremos que tenga tres propiedades:

1. Debe ser imparcial. En otras palabras, ningún participante debe influir de ninguna manera en el resultado del generador de números aleatorios.

2. Debe ser impredecible. En otras palabras, ningún participante debería poder predecir qué número se generará (o inferir cualquiera de sus propiedades) antes de que se genere.

3. El protocolo debe ser viable, es decir, resistente al hecho de que un cierto porcentaje de participantes se desconecte de la red o intente detener deliberadamente el protocolo.

En este artículo veremos dos enfoques: RANDAO + VDF y el enfoque de códigos de borrado. En la siguiente parte, examinaremos en detalle el enfoque basado en firmas de umbral.

Pero primero, veamos un algoritmo simple y de uso común que es viable, impredecible, pero sesgado.

RANDAO

RANDAO es un enfoque muy simple y, por lo tanto, de uso bastante común para generar aleatoriedad. Todos los participantes de la red primero seleccionan localmente un número pseudoaleatorio, luego cada participante envía un hash del número seleccionado. A continuación, los participantes se turnan para revelar los números elegidos y realizar una operación XOR en los números revelados, y el resultado de esta operación se convierte en el resultado del protocolo.

El paso de publicar los hashes antes de revelar los números es necesario para que el atacante no pueda elegir su número después de haber visto los números de los demás participantes. Esto le permitiría determinar prácticamente por sí solo la salida del generador de números aleatorios.

Durante el transcurso del protocolo, los participantes deben llegar a una decisión común (el llamado consenso) dos veces: cuándo comenzar a revelar los números seleccionados y, por lo tanto, dejar de aceptar hashes, y cuándo dejar de aceptar los números seleccionados y calcular el resultado aleatorio. número. Tomar tales decisiones entre participantes que no confían entre sí no es una tarea fácil en sí misma, y ​​volveremos a ello en artículos futuros; en este artículo asumiremos que dicho algoritmo de consenso está disponible para nosotros.

¿Cuál de las propiedades que describimos anteriormente tiene RANDAO? Es impredecible, tiene la misma vitalidad que el protocolo de consenso subyacente, pero está sesgado. Específicamente, un atacante puede observar la red y, después de que otros participantes revelen sus números, puede calcular su XOR y decidir si revela o no su número para influir en el resultado. Si bien esto evita que el atacante determine por sí solo la salida del generador de números aleatorios, todavía le da 1 bit de influencia. Y si los atacantes controlan a varios participantes, entonces la cantidad de bits que controlan será igual a la cantidad de participantes bajo su control.

La influencia de los atacantes se puede reducir en gran medida exigiendo que los participantes revelen los números en orden. Entonces el atacante sólo podrá influir en el resultado si se abre en último lugar. Si bien la influencia es significativamente menor, el algoritmo sigue estando sesgado.

RANDAO+VDF

Una forma de hacer que RANDAO sea imparcial es la siguiente: después de que se revelan todos los números y se calcula el XOR, su resultado se ingresa en la entrada de una función, que lleva mucho tiempo calcular, pero le permite verificar la exactitud del cálculo muy rápidamente.

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

Esta función se llama función de retardo verificable o VDF. Si calcular el resultado final lleva más tiempo que la etapa de divulgación del número, entonces el atacante no podrá predecir el efecto de mostrar u ocultar su número y, por lo tanto, perderá la oportunidad de influir en el resultado.

Desarrollar buenos VDF es extremadamente difícil. Ha habido varios avances recientemente, p.e. este и este lo que hizo que VDF fuera más práctico en la práctica, y Ethereum 2.0 planea usar RANDAO con VDF como fuente de números aleatorios a largo plazo. Aparte del hecho de que este enfoque es impredecible e imparcial, tiene el beneficio adicional de ser viable si al menos dos participantes están disponibles en la red (suponiendo que el protocolo de consenso utilizado sea viable cuando se trata de un número tan pequeño de participantes).

El mayor desafío de este enfoque es configurar el VDF de manera que incluso un participante con hardware especializado muy costoso no pueda calcular el VDF antes del final de la fase de descubrimiento. Idealmente, el algoritmo debería tener incluso un margen de seguridad significativo, digamos 10x. La siguiente figura muestra un ataque de un actor que tiene un ASIC especializado que le permite ejecutar un VDF más rápido que el tiempo asignado para revelar la confirmación de RANDAO. Dicho participante aún puede calcular el resultado final utilizando o no su número y luego, basándose en el cálculo, elegir si mostrarlo o no.

Para la familia VDF mencionada anteriormente, el rendimiento de un ASIC dedicado puede ser 100 veces mayor que el del hardware convencional. Entonces, si la fase de implementación dura 10 segundos, entonces el VDF calculado en dicho ASIC debe tardar más de 100 segundos para tener un margen de seguridad 10 veces mayor y, por lo tanto, el mismo VDF calculado en hardware básico debe tardar 100 x 100 segundos = ~3 horas.

La Fundación Ethereum planea resolver este problema creando sus propios ASIC gratuitos y disponibles públicamente. Una vez que esto suceda, todos los demás protocolos también podrán aprovechar esta tecnología, pero hasta entonces el enfoque RANDAO+VDF no será tan viable para los protocolos que no pueden invertir en el desarrollo de sus propios ASIC.

Se han recopilado muchos artículos, vídeos y otra información sobre VDF en este sitio.

Usamos códigos de borrado.

En esta sección, veremos un protocolo de generación de números aleatorios que utiliza borrando codigos. Puede tolerar hasta ⅓ de atacantes sin dejar de ser viable, y permite que existan hasta ⅔ de atacantes antes de que puedan predecir o influir en el resultado.

La idea principal del protocolo es la siguiente. Para simplificar, supongamos que hay exactamente 100 participantes. Supongamos también que todos los participantes localmente tienen alguna clave privada y que todos los participantes conocen las claves públicas de todos los participantes:

1. Cada participante crea localmente una cadena larga, la divide en 67 partes, crea códigos de borrado para obtener 100 acciones, de modo que 67 sean suficientes para recuperar la cadena, asigna cada una de las 100 acciones a uno de los participantes y las cifra con la clave pública del mismo participante. Luego se publican todos los recursos compartidos codificados.

2. Los participantes utilizan algún tipo de consenso para llegar a un acuerdo sobre conjuntos codificados de 67 participantes específicos.

3. Una vez que se alcanza el consenso, cada participante toma las acciones codificadas en cada uno de los 67 conjuntos cifrados con su clave pública, descifra todas esas acciones y las publica todas las acciones descifradas.

4. Una vez que 67 participantes hayan completado el paso (3), todos los conjuntos acordados se pueden decodificar y reconstruir completamente debido a las propiedades de los códigos de borrado, y el número final se puede obtener como un XOR de las filas iniciales con las que comenzaron los participantes en (1). .

Se puede demostrar que este protocolo es imparcial e impredecible. El número aleatorio resultante se determina después de alcanzar el consenso, pero nadie lo conoce hasta que dos tercios de los participantes decodifican las partes cifradas con su clave pública. Por lo tanto, el número aleatorio se determina antes de que se publique información suficiente para reconstruirlo.

¿Qué sucede si en el paso (1) uno de los participantes envió archivos compartidos codificados a los demás participantes que no son el código de borrado correcto para alguna cadena? Sin cambios adicionales, diferentes participantes no podrán recuperar la cadena en absoluto o recuperarán cadenas diferentes, lo que dará como resultado que diferentes participantes reciban un número aleatorio diferente. Para evitar esto, puede hacer lo siguiente: cada participante, además de las acciones codificadas, también calcula árbol de merkla todas esas acciones, y envía a cada participante tanto la acción codificada como la raíz del árbol merkle, y una prueba de la inclusión de la acción en el árbol merkle. En el consenso del paso (2), los participantes no sólo se ponen de acuerdo sobre un conjunto de conjuntos, sino también sobre un conjunto de raíces específicas de dichos árboles (si algún participante se desvió del protocolo y envió diferentes raíces de árboles merkle a diferentes participantes, y dos de esas raíces se muestran durante el consenso, su fila no se incluye en el conjunto de resultados). Como resultado del consenso, tendremos 67 líneas codificadas y las correspondientes raíces del árbol merkle de manera que haya al menos 67 participantes (no necesariamente los mismos que propusieron las líneas correspondientes), quienes para cada una de las 67 líneas tienen un mensaje con una parte del código de borrado y una prueba de la aparición de su parte en el árbol correspondiente se desvaneció.

Cuando en el paso (4) el participante descifra 67 tiempos para una determinada cuerda e intenta reconstruir la cuerda original a partir de ellos, es posible una de las opciones:

1. La cadena se restaura y, si luego se vuelve a codificar para borrarla y se calcula el árbol Merkle para las acciones calculadas localmente, la raíz coincide con aquella sobre la que se alcanzó el consenso.

2. La fila se restaura, pero la raíz calculada localmente no coincide con aquella en la que se alcanzó el consenso.

3. La fila no se restaura.

Es fácil demostrar que si la opción (1) sucedió para al menos uno de los participantes anteriores, entonces la opción (1) sucedió para todos los participantes, y viceversa, si la opción (2) o (3) sucedió para al menos un participante, entonces para todos los participantes se aplicará la opción (2) o (3). Por lo tanto, para cada fila del conjunto, todos los participantes la recuperarán con éxito o todos los participantes no podrán recuperarla. El número aleatorio resultante es entonces un XOR de solo las filas que los participantes pudieron recuperar.

Firmas de umbral

Otro enfoque de la aleatoriedad es utilizar las llamadas firmas de umbral BLS. Un generador de números aleatorios basado en firmas de umbral tiene exactamente las mismas garantías que el algoritmo basado en códigos de borrado descrito anteriormente, pero tiene un número asintótico significativamente menor de mensajes enviados a través de la red para cada número generado.

Las firmas BLS son un diseño que permite a varios participantes crear una firma común para un mensaje. Estas firmas se utilizan a menudo para ahorrar espacio y ancho de banda al no requerir el envío de varias firmas. 

Una aplicación común para las firmas BLS en los protocolos blockchain, además de generar números aleatorios, es la firma en bloque en los protocolos BFT. Digamos que 100 participantes crean bloques y un bloque se considera definitivo si 67 de ellos lo firman. Todos pueden enviar sus partes de la firma BLS y utilizar algún algoritmo de consenso para acordar 67 de ellas y luego fusionarlas en una firma BLS. Se pueden usar 67 (o más) partes para crear la firma final, lo que dependerá de qué 67 firmas se combinaron y, por lo tanto, puede variar, aunque las diferentes elecciones de los 67 participantes crearán una firma diferente, cualquier firma será válida. firma del bloque. Los participantes restantes solo necesitan recibir y verificar una sola firma por bloque, en lugar de 67, a través de la red, lo que reduce significativamente la carga en la red.

Resulta que si las claves privadas que utilizan los participantes se generan de cierta manera, entonces no importa qué 67 firmas (o más, pero no menos) se agreguen, la firma resultante será la misma. Esto se puede utilizar como fuente de aleatoriedad: los participantes primero acuerdan algún mensaje que firmarán (esto podría ser el resultado de RANDAO o simplemente el hash del último bloque, en realidad no importa siempre y cuando cambie cada vez). y es consistente) y crear una firma BLS para ello. El resultado de la generación será impredecible hasta que 67 participantes proporcionen sus partes, y después de eso el resultado ya estará predeterminado y no puede depender de las acciones de ningún participante.

Este enfoque de aleatoriedad es viable siempre que al menos ⅔ de los participantes en línea sigan el protocolo, y es imparcial e impredecible siempre que al menos ⅓ de los participantes sigan el protocolo. Es importante tener en cuenta que un atacante que controla más de ⅓ pero menos de ⅔ de los participantes puede detener el protocolo, pero no puede predecir ni influir en su resultado.

Las firmas de umbral en sí mismas son un tema muy interesante. En la segunda parte del artículo, analizaremos en detalle cómo funcionan y exactamente cómo es necesario generar claves de participante para que las firmas de umbral puedan usarse como generador de números aleatorios.

en conclusión

Este artículo es el primero de una serie de artículos técnicos del blog. NEAR. NEAR es un protocolo y una plataforma blockchain para desarrollar aplicaciones descentralizadas con énfasis en la facilidad de desarrollo y uso para los usuarios finales.

El código del protocolo está abierto, nuestra implementación está escrita en Rust, se puede encontrar aquí.

Puedes ver cómo es el desarrollo para NEAR y experimentar en el IDE en línea. aquí.

Puedes seguir todas las novedades en ruso en grupo de telegramas y grupo en VKontakte, y en inglés en el oficial twitter.

Hasta pronto!

Fuente: habr.com