introducción
"La generación de números aleatorios es demasiado importante para dejarla al azar".
Robert Cavue, 1970
Este artículo está dedicado a la aplicación práctica de soluciones que utilizan la generación colectiva de números aleatorios en un entorno que no es de confianza. En resumen, cómo y por qué se usa el azar en blockchains, y un poco sobre cómo distinguir el azar "bueno" del "malo". Generar un número verdaderamente aleatorio es un problema extremadamente difícil, incluso en una sola computadora, y los criptógrafos lo han estudiado durante mucho tiempo. Pues bien, en las redes descentralizadas, la generación de números aleatorios es aún más compleja e importante.
Es en redes donde los participantes no confían entre sí donde la capacidad de generar un número aleatorio indiscutible nos permite resolver de manera efectiva muchos problemas críticos y mejorar significativamente los esquemas existentes. Además, los juegos de azar y las loterías no son el objetivo número uno aquí, como podría parecerle en un principio a un lector inexperto.
Generación de números aleatorios
Las computadoras no pueden generar números aleatorios por sí mismas; necesitan ayuda externa para hacerlo. La computadora puede obtener algún valor aleatorio, por ejemplo, de los movimientos del mouse, la cantidad de memoria utilizada, las corrientes parásitas en los pines del procesador y muchas otras fuentes llamadas fuentes de entropía. Estos valores en sí no son completamente aleatorios, ya que se encuentran en un rango determinado o tienen un patrón de cambios predecible. Para convertir dichos números en un número verdaderamente aleatorio dentro de un rango determinado, se les aplican criptotransformaciones para producir valores pseudoaleatorios distribuidos uniformemente a partir de los valores distribuidos de manera desigual de la fuente de entropía. Los valores resultantes se denominan pseudoaleatorios porque no son verdaderamente aleatorios, sino que se derivan de manera determinista de la entropía. Cualquier buen algoritmo criptográfico, al cifrar datos, produce textos cifrados que deberían ser estadísticamente indistinguibles de una secuencia aleatoria, por lo que para producir aleatoriedad se puede tomar una fuente de entropía, que solo proporciona una buena repetibilidad e imprevisibilidad de los valores incluso en rangos pequeños, el resto del trabajo es dispersar y mezclar bits. El valor resultante será asumido por el algoritmo de cifrado.
Para completar un breve programa educativo, agregaré que generar números aleatorios incluso en un solo dispositivo es uno de los pilares para garantizar la seguridad de nuestros datos. Los números pseudoaleatorios generados se utilizan al establecer conexiones seguras en varias redes, para generar claves criptográficas, para equilibrio de carga, monitoreo de integridad y para muchas más aplicaciones. La seguridad de muchos protocolos depende de la capacidad de generar datos aleatorios confiables y externamente impredecibles, almacenarlos y no revelarlos hasta el siguiente paso del protocolo; de lo contrario, la seguridad se verá comprometida. Un ataque a un generador de valores pseudoaleatorios es extremadamente peligroso y amenaza inmediatamente a todo software que utilice generación aleatoria.
Todo esto debes saberlo si tomaste un curso básico de criptografía, así que sigamos con las redes descentralizadas.
Aleatorio en blockchains
En primer lugar, hablaré de blockchains con soporte para contratos inteligentes; son ellos los que pueden aprovechar plenamente las oportunidades que brinda la aleatoriedad innegable y de alta calidad. Además, por brevedad, llamaré a esta tecnología "Balizas aleatorias verificables públicamente”o PVRB. Dado que las cadenas de bloques son redes en las que cualquier participante puede verificar la información, la parte clave del nombre es "Publicly Verifiable", es decir. Cualquiera puede utilizar cálculos para obtener pruebas de que el número resultante publicado en la cadena de bloques tiene las siguientes propiedades:
- El resultado debe tener una distribución demostrablemente uniforme, es decir, basarse en una criptografía demostrablemente sólida.
- No es posible controlar ninguno de los bits del resultado. En consecuencia, el resultado no se puede predecir de antemano.
- No se puede sabotear el protocolo de generación no participando en el protocolo o sobrecargando la red con mensajes de ataque.
- Todo lo anterior debe ser resistente a la colusión de un número permitido de participantes deshonestos en el protocolo (por ejemplo, 1/3 de los participantes).
Cualquier posibilidad de que un grupo menor de participantes en connivencia produzca incluso un azar par/impar controlado es un agujero de seguridad. Cualquier capacidad del grupo para detener la emisión aleatoria es un agujero de seguridad. En general, hay muchos problemas, y esta tarea no es fácil...
Parece que la aplicación más importante de PVRB son varios juegos, loterías y, en general, cualquier tipo de juego en blockchain. De hecho, esta es una dirección importante, pero la aleatoriedad en las cadenas de bloques tiene aplicaciones aún más importantes. Mirémoslos.
Algoritmos de consenso
PVRB juega un papel muy importante en la organización del consenso de la red. Las transacciones en blockchains están protegidas por una firma electrónica, por lo que un “ataque a una transacción” es siempre la inclusión/exclusión de una transacción en un bloque (o varios bloques). Y la tarea principal del algoritmo de consenso es acordar el orden de estas transacciones y el orden de los bloques que incluyen estas transacciones. Además, una propiedad necesaria para las cadenas de bloques reales es la finalidad: la capacidad de la red de aceptar que la cadena hasta el bloque finalizado es definitiva y nunca será excluida debido a la aparición de una nueva bifurcación. Por lo general, para acordar que un bloque es válido y, lo más importante, definitivo, es necesario recolectar firmas de la mayoría de los productores de bloques (en adelante, BP - productores de bloques), lo que requiere al menos entregar la cadena de bloques. a todos los BP y distribuir firmas entre todos los BP. A medida que crece el número de BP, el número de mensajes necesarios en la red crece exponencialmente, por lo que los algoritmos de consenso que requieren finalidad, utilizados por ejemplo en el consenso Hyperledger pBFT, no funcionan a la velocidad requerida, a partir de varias docenas de BP, lo que requiere una gran cantidad de conexiones.
Si hay un PVRB innegable y honesto en la red, entonces, incluso en la aproximación más simple, uno puede elegir a uno de los productores de bloques basándose en él y nombrarlo "líder" durante una ronda del protocolo. si tenemos N productores de bloques, de los cuales M: M > 1/2 N son honestos, no censuran las transacciones y no bifurcan la cadena para llevar a cabo un ataque de “doble gasto”, entonces el uso de un PVRB uniformemente distribuido e indiscutible permitirá elegir un líder honesto con probabilidad M / N (M / N > 1/2). Si a cada líder se le asigna su propio intervalo de tiempo durante el cual puede producir un bloque y validar la cadena, y estos intervalos son iguales en tiempo, entonces la cadena de bloques de BP honestos será más larga que la cadena formada por BP maliciosos, y el consenso El algoritmo se basa en la longitud de la cadena y simplemente descartará la “mala”. Este principio de asignar intervalos de tiempo iguales a cada BP se aplicó por primera vez en Graphene (el predecesor de EOS) y permite cerrar la mayoría de los bloques con una sola firma, lo que reduce en gran medida la carga de la red y permite que este consenso funcione extremadamente rápido y continuamente. Sin embargo, la red EOS ahora tiene que utilizar bloques especiales (Último Bloque Irreversible), que están confirmados por las firmas de 2/3 BP. Estos bloques sirven para asegurar la finalidad (la imposibilidad de que una bifurcación de la cadena comience antes del último último bloque irreversible).
Además, en implementaciones reales, el esquema del protocolo es más complicado: la votación de los bloques propuestos se lleva a cabo en varias etapas para mantener la red en caso de que falten bloques y problemas con la red, pero incluso teniendo esto en cuenta, los algoritmos de consenso que utilizan PVRB requieren significativamente menos mensajes entre BP, lo que permite hacerlos más rápidos que el PVFT tradicional, o sus diversas modificaciones.
El representante más destacado de tales algoritmos: del equipo Cardano, que se dice que es matemáticamente demostrable contra la colusión de BP.
En Ouroboros, PVRB se utiliza para definir el llamado "cronograma de BP", un cronograma según el cual a cada BP se le asigna su propio intervalo de tiempo para publicar un bloque. La gran ventaja de utilizar PVRB es la completa “igualdad” de los BP (según el tamaño de sus balances). La integridad del PVRB garantiza que los BP maliciosos no puedan controlar la programación de los intervalos de tiempo y, por lo tanto, no puedan manipular la cadena preparando y analizando las bifurcaciones de la cadena con antelación, y para seleccionar una bifurcación basta simplemente con confiar en la longitud de la misma. cadena, sin utilizar métodos complicados para calcular la “utilidad” de BP y el “peso” de sus bloques.
En general, en todos los casos en los que es necesario elegir un participante aleatorio en una red descentralizada, PVRB es casi siempre la mejor opción, en lugar de una opción determinista basada, por ejemplo, en un hash de bloque. Sin PVRB, la capacidad de influir en la elección de un participante conduce a ataques en los que el atacante puede elegir entre múltiples futuros para elegir al siguiente participante corrupto o varios a la vez para garantizar una mayor participación en la decisión. El uso de PVRB desacredita este tipo de ataques.
Escalado y equilibrio de carga
PVRB también puede resultar de gran beneficio en tareas como la reducción de carga y el escalamiento de pagos. Para empezar, tiene sentido familiarizarse con Rivesta “Billetes de Lotería Electrónica como Micropagos”. La idea general es que en lugar de hacer pagos de 100 1c del pagador al destinatario, se puede jugar una lotería honesta con un premio de 1$ = 100c, donde el pagador le da al banco uno de sus 1 "billetes de lotería" por cada Pago de 100c. Uno de estos boletos gana un frasco de $1, y es este boleto el que el destinatario puede registrar en la cadena de bloques. Lo más importante es que los 99 billetes restantes se transfieren entre el destinatario y el pagador sin ninguna participación externa, a través de un canal privado y a la velocidad que se desee. Se puede leer una buena descripción del protocolo basado en este esquema en la red Emercoin. .
Este esquema tiene algunos problemas, como que el destinatario puede dejar de atender al pagador inmediatamente después de recibir un boleto ganador, pero para muchas aplicaciones especiales, como la facturación por minuto o las suscripciones electrónicas a servicios, estos pueden descuidarse. El principal requisito, por supuesto, es la integridad de la lotería, y para su implementación es absolutamente necesario un PVRB.
La elección de un participante aleatorio también es extremadamente importante para los protocolos de fragmentación, cuyo propósito es escalar horizontalmente la cadena de bloques, permitiendo que diferentes BP procesen solo su alcance de transacciones. Esta es una tarea extremadamente difícil, especialmente en términos de seguridad al fusionar fragmentos. La selección justa de un BP aleatorio con el fin de asignar a los responsables de un fragmento específico, como en los algoritmos de consenso, también es tarea del PVRB. En los sistemas centralizados, los fragmentos son asignados por un balanceador; simplemente calcula el hash de la solicitud y lo envía al ejecutor requerido. En blockchains, la capacidad de influir en esta tarea puede conducir a un ataque al consenso. Por ejemplo, un atacante puede controlar el contenido de las transacciones, puede controlar qué transacciones van al fragmento que controla y manipular la cadena de bloques que contiene. Puede leer una discusión sobre el problema del uso de números aleatorios para tareas de fragmentación en Ethereum
La fragmentación es uno de los problemas más ambiciosos y serios en el campo de blockchain; su solución permitirá construir redes descentralizadas de fantástico rendimiento y volumen. PVRB es sólo uno de los bloques importantes para resolverlo.
Juegos, protocolos económicos, arbitraje.
Es difícil sobreestimar el papel de los números aleatorios en la industria del juego. El uso explícito en los casinos en línea y el uso implícito al calcular los efectos de la acción de un jugador son problemas extremadamente difíciles para las redes descentralizadas, donde no hay forma de confiar en una fuente central de aleatoriedad. Pero la selección aleatoria también puede resolver muchos problemas económicos y ayudar a construir protocolos más simples y eficientes. Supongamos que en nuestro protocolo hay disputas sobre el pago de algunos servicios económicos, y estas disputas ocurren con bastante poca frecuencia. En este caso, si existe un PVRB indiscutible, los clientes y vendedores pueden acordar resolver las disputas de forma aleatoria, pero con una probabilidad determinada. Por ejemplo, con un 60% de probabilidad gana el cliente y con un 40% de probabilidad gana el vendedor. Este enfoque, absurdo desde el primer punto de vista, permite resolver disputas automáticamente con una proporción exactamente predecible de ganancias/pérdidas, lo que conviene a ambas partes, sin la participación de un tercero y sin una pérdida de tiempo innecesaria. Además, el índice de probabilidad puede ser dinámico y depender de algunas variables globales. Por ejemplo, si a una empresa le va bien, tiene un número bajo de disputas y una alta rentabilidad, la empresa puede automáticamente cambiar la probabilidad de resolver una disputa hacia el enfoque en el cliente, por ejemplo 70/30 u 80/20, y viceversa. Si las disputas requieren mucho dinero y son fraudulentas o inadecuadas, puedes cambiar la probabilidad en la otra dirección.
Una gran cantidad de protocolos descentralizados interesantes, como registros seleccionados de tokens, mercados de predicción, curvas de vinculación y muchos otros, son juegos económicos en los que se recompensa el buen comportamiento y se penaliza el mal comportamiento. A menudo contienen problemas de seguridad cuyas protecciones entran en conflicto entre sí. Lo que está protegido de un ataque de "ballenas" con miles de millones de tokens ("gran apuesta") es vulnerable a ataques de miles de cuentas con saldos pequeños ("sybil-stake") y a las medidas tomadas contra un solo ataque, como no Las tarifas lineales creadas para hacer que trabajar con una gran participación no sea rentable suelen quedar desacreditadas por otro ataque. Dado que estamos hablando de un juego económico, los pesos estadísticos correspondientes se pueden calcular de antemano y simplemente sustituir las comisiones por otras aleatorias con la distribución adecuada. Estas comisiones probabilísticas se implementan de manera extremadamente simple si la cadena de bloques tiene una fuente confiable de aleatoriedad y no requieren cálculos complejos, lo que dificulta la vida tanto a las ballenas como a las sibilas.
Al mismo tiempo, es necesario seguir recordando que el control sobre un solo bit en esta aleatoriedad permite hacer trampa, reduciendo y aumentando las probabilidades a la mitad, por lo que un PVRB honesto es el componente más importante de dichos protocolos.
¿Dónde encontrar el azar correcto?
En teoría, una selección aleatoria justa en redes descentralizadas hace que casi cualquier protocolo sea demostrablemente seguro contra la colusión. El razonamiento es bastante simple: si la red acuerda un solo bit 0 o 1, y menos de la mitad de los participantes son deshonestos, entonces, dadas suficientes iteraciones, se garantiza que la red alcanzará un consenso sobre ese bit con una probabilidad fija. Simplemente porque un azar honesto elegirá a 51 de 100 participantes el 51% de las veces. Pero esto es en teoría, porque... en redes reales, para garantizar un nivel de seguridad como el de los artículos, se requieren muchos mensajes entre hosts, una criptografía compleja de múltiples pasos y cualquier complicación del protocolo agrega inmediatamente nuevos vectores de ataque.
Es por eso que todavía no vemos un PVRB resistente y probado en blockchains, que se habría utilizado durante el tiempo suficiente para ser probado por aplicaciones reales, múltiples auditorías, cargas y, por supuesto, ataques reales, sin los cuales es difícil llamar un Producto realmente seguro.
Sin embargo, existen varios enfoques prometedores, se diferencian en muchos detalles y uno de ellos definitivamente resolverá el problema. Con los recursos informáticos modernos, la teoría criptográfica puede traducirse hábilmente en aplicaciones prácticas. En el futuro, estaremos encantados de hablar sobre las implementaciones de PVRB: ahora hay varias, cada una tiene su propio conjunto de propiedades y características de implementación importantes, y detrás de cada una hay una buena idea. No hay muchos equipos involucrados en la aleatorización y la experiencia de cada uno de ellos es extremadamente importante para todos los demás. Esperamos que nuestra información permita a otros equipos avanzar más rápido, teniendo en cuenta la experiencia de sus predecesores.
Fuente: habr.com