Introduccion
"La generación de números aleatorios es demasiado importante para dejarla al azar"
Robert Cavyu, 1970
Este artículo está dedicado a la aplicación práctica de soluciones utilizando la generación colectiva de números aleatorios en un entorno no confiable. 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 computadora separada, y los criptógrafos lo han estudiado durante mucho tiempo. Bueno, en redes descentralizadas, la generación de números aleatorios es aún más compleja e importante.
Es en las redes donde los participantes no confían entre sí que la capacidad de generar un número aleatorio innegable puede resolver de manera efectiva muchos problemas importantes y mejorar significativamente los esquemas existentes. Además, los juegos de azar y las loterías aquí no son en absoluto el objetivo número uno, como puede parecer un lector inexperto al principio.
Generación de números aleatorios
Las computadoras no saben cómo producir números aleatorios por sí mismas, para esto necesitan ayuda externa. Una computadora puede obtener algún valor aleatorio usando, por ejemplo, movimientos del mouse, la cantidad de memoria utilizada, corrientes espurias en los contactos del procesador y muchas otras fuentes llamadas fuentes de entropía. Estos valores en sí mismos no son completamente al azar, ya que están en un cierto rango o tienen una naturaleza predecible de los cambios. Para convertir dichos números en un número verdaderamente aleatorio en un rango dado, se les aplican transformaciones criptográficas para obtener valores pseudoaleatorios distribuidos uniformemente a partir de los valores distribuidos de manera desigual de la fuente de entropía. Los valores obtenidos se denominan pseudoaleatorios, ya que no son verdaderamente aleatorios, sino que se derivan de forma determinista de la entropía. Cualquier buen algoritmo criptográfico, que encripta los datos, produce textos cifrados que no deberían ser estadísticamente indistinguibles de una secuencia aleatoria, por lo que para la producción de aleatoriedad puede tomar una fuente de entropía que proporcione solo una buena repetibilidad e imprevisibilidad de valores incluso en pequeños rangos, el resto del trabajo de dispersión y mezcla de bits en el algoritmo de cifrado asumirá el valor resultante.
Para completar el breve programa educativo, agregaré que la generación de números aleatorios incluso en un dispositivo es uno de los pilares para garantizar la seguridad de nuestros datos, los números pseudoaleatorios generados se utilizan para establecer conexiones seguras en varias redes, generar claves criptográficas, equilibrar la carga, controlar la integridad, y para muchos más usos. La seguridad de muchos protocolos depende de la capacidad de generar datos aleatorios confiables e impredecibles desde el exterior, guardarlos y no abrirlos 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 todo el software que utiliza la generación aleatoria a la vez.
Debe saber todo esto si ha tomado un curso básico de criptografía, así que continuemos con las redes descentralizadas.
Blockchain Random
En primer lugar, hablaré sobre blockchains con soporte para contratos inteligentes, son ellos quienes pueden aprovechar al máximo las oportunidades que brinda una aleatoriedad innegable 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 "Verificable públicamente", es decir Cualquier persona con la ayuda de los cálculos puede obtener pruebas de que el número resultante, colocado en la cadena de bloques, tiene las siguientes propiedades:
- El resultado debe tener una distribución demostrablemente uniforme, es decir, basada en una criptografía demostrablemente fuerte.
- No es posible controlar ninguno de los bits del resultado. Como resultado, el resultado no se puede predecir de antemano.
- No puede sabotear el protocolo de generación al no participar en el protocolo o al sobrecargar la red con mensajes de ataque
- Todo lo anterior debe ser resistente a la colusión del número permitido de participantes deshonestos en el protocolo (por ejemplo, 1/3 de los participantes).
Cualquier oportunidad para que un grupo menor de participantes conspiradores produzca incluso un azar controlado / impar es un agujero de seguridad. Cualquier oportunidad para que el grupo deje de emitir una casa al azar 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 para 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 casa aleatoria en blockchains tiene aplicaciones y más importante. Considéralos.
Algoritmos de consenso
PVRB es crucial para el consenso de redes. Las transacciones en blockchains están protegidas por una firma electrónica, por lo tanto, un "ataque a una transacción" es siempre la inclusión / exclusión de una transacción en un bloque (o en 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 al bloque finalizado sea final y nunca se excluirá 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, final, debe recolectar firmas de la mayoría de los productores de bloques (en adelante BP - productores de bloques), lo que requiere al menos entregar una cadena de bloques a todos los BP y distribuir firmas entre todos los BP . A medida que aumenta el número de BP, el número de mensajes requeridos en la red crece exponencialmente; por lo tanto, los algoritmos de consenso que requieren finalidad, como los utilizados en el consenso pBFT de Hyperledger, no funcionan a la velocidad correcta, comenzando desde varias docenas de BP, lo que requiere una gran cantidad de conexiones.
Si la red tiene un PVRB innegable y honesto, entonces, incluso en la aproximación más simple, uno puede seleccionar a uno de los productores de bloques sobre la base de este y designarlo como el "líder" para una ronda del protocolo. Si tenemos productores de bloques N , de los cuales M: M > 1/2 N son honestos, no censure las transacciones y no construya cadenas de horquillas para llevar a cabo un ataque de "doble gasto", luego usar un PVRB indiscutible distribuido uniformemente le 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 el tiempo, entonces la cadena de bloques de BP honestos será más larga que la cadena formada por el BP malicioso, y el algoritmo de consenso basado en la longitud de la cadena, simplemente descarte lo "malo". Este principio de asignar segmentos iguales de tiempo a cada BP se aplicó por primera vez en Graphene (el predecesor de EOS), y permite que la mayoría de los bloques se cierren con una sola firma, lo que reduce en gran medida la carga de la red y permite que este consenso funcione de manera extremadamente rápida y constante. Sin embargo, las redes EOS ahora tienen que usar bloques especiales (último bloque irreversible), que se confirman con 2/3 firmas de BP. Estos bloques se utilizan para garantizar la finalidad (la imposibilidad de que una cadena de horquilla comience antes que el último Último bloque irreversible).
Además, en implementaciones reales, el esquema de 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 bloques faltantes y problemas de red, pero incluso con esto en mente, los algoritmos de consenso PVRB requieren significativamente menos mensajes entre BP, lo que le permite hacerlos más rápido que el PBFT tradicional, o sus diversas modificaciones.
El representante más llamativo de tales algoritmos: Ouroboros del equipo Cardano, que, como se anunció, tiene una resistencia matemáticamente demostrable a la colusión entre BP.
En Ouroboros, PVRB se utiliza para definir el llamado "programa de BP", un programa según el cual a cada BP se le asigna su propio intervalo de tiempo para publicar un bloque. La gran ventaja de usar PVRB es la completa "igualdad de derechos" de BP (de acuerdo con el tamaño de sus saldos). La honestidad PVRB asegura que los BP maliciosos no pueden controlar el horario de los intervalos de tiempo y, por lo tanto, no pueden manipular la cadena preparando y analizando los tenedores de la cadena por adelantado, y para seleccionar un tenedor, simplemente puede confiar en la longitud de la cadena sin usar formas engañosas para calcular la "utilidad" de BP y "Pesos" de sus bloques.
En general, en todos los casos cuando un participante aleatorio necesita ser seleccionado 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 del participante lleva a la aparición de ataques en los que el atacante puede, eligiendo entre varias opciones para el futuro, elegir el siguiente participante corrupto o varios a la vez, para proporcionar una participación más significativa en la decisión. El uso de PVRB desacredita este tipo de ataques.
Escalado y equilibrio de carga
PVRB también puede ser de gran beneficio en tareas para reducir la carga de trabajo y escalar pagos. Para empezar, tiene sentido leer el artículo de Rivest "Billetes de lotería electrónicos como micropagos". La esencia general es que, en lugar de hacer 100 pagos de 1c del pagador al destinatario, puede jugar una lotería honesta con un premio de $ 1 = 100c, donde el pagador transfiere uno de sus 100 "boletos de lotería" al banco por cada pago en 1c. Uno de estos boletos le gana al banco $ 1, y es este boleto el que el destinatario puede arreglar en la cadena de bloques. Lo más importante, los 99 boletos restantes se transfieren entre el destinatario y el pagador sin ninguna participación externa, a través de un canal privado y a cualquier velocidad deseada. Aquí se puede encontrar una buena descripción del protocolo basado en este esquema en la red Emercoin.
Este esquema tiene varios problemas, por ejemplo, el destinatario puede dejar de servir al pagador inmediatamente después de recibir un boleto ganador, pero para muchas aplicaciones especiales, como facturación por minuto o suscripciones electrónicas a los servicios, se pueden descuidar. El requisito principal, por supuesto, es la honestidad de la lotería, y PVRB es absolutamente necesario para su celebración.
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 cuando se trata de seguridad al fusionar fragmentos. La elección honesta de un BP aleatorio para asignarlo a los responsables de un fragmento particular, como en los algoritmos de consenso, también es una tarea PVRB. En los sistemas centralizados, el equilibrador asigna fragmentos, simplemente calcula el hash a partir de la solicitud y lo envía al ejecutor necesario. En blockchains, la capacidad de influir en esta asignación puede conducir a un ataque al consenso. Por ejemplo, el contenido de las transacciones puede ser controlado por el atacante, puede controlar qué transacciones caen en el fragmento que controla y manipular la cadena de bloques en él. Aquí se puede encontrar una discusión sobre el problema del uso de números aleatorios para problemas de fragmentación en Ethereum .
Sharding es una de las tareas más ambiciosas y serias en el campo de blockchain, su solución le permitirá construir redes descentralizadas de fantástico rendimiento y volumen. PVRB es solo uno de los bloques importantes para resolverlo.
Juegos, protocolos económicos, arbitraje.
El papel de los números aleatorios en la industria del juego es difícil de sobreestimar. El uso explícito en los casinos en línea, e implícito en el cálculo de 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, una elección aleatoria puede resolver muchos problemas económicos y ayudar a construir protocolos más simples y más eficientes. Supongamos que en nuestro protocolo hay disputas sobre el pago de algunos servicios de bajo costo, y estas disputas son bastante raras. En este caso, si hay un PVRB innegable, los clientes y vendedores pueden acordar una resolución aleatoria de disputas, pero con una probabilidad dada. Por ejemplo, con una probabilidad del 60%, el cliente gana, y con una probabilidad del 40%, el vendedor gana. Un enfoque tan absurdo, desde el primer punto de vista, le permite a uno resolver automáticamente las disputas con una proporción predecible de victorias / pérdidas, que se adapta a ambas partes sin la participación de terceros y la pérdida innecesaria de tiempo. Además, la razón de probabilidad puede ser dinámica y depender de algunas variables globales. Por ejemplo, si a una empresa le está yendo bien, hay un bajo número de disputas y una alta rentabilidad, la compañía puede cambiar automáticamente la probabilidad de que una disputa se resuelva hacia la orientación al cliente, por ejemplo 70/30 u 80/20, y viceversa, si las disputas requieren mucho dinero y son fraudulentas o inadecuadas, puede cambiar la probabilidad en la otra dirección.
Una gran cantidad de protocolos descentralizados interesantes, como registros con fichas simbólicos, mercados de predicción, curvas de vinculación y muchos otros, son juegos económicos que recompensan el buen comportamiento y los malos. A menudo se encuentran con problemas de seguridad, cuya protección se contradice entre sí. Lo que está protegido de un ataque de "ballenas" con miles de millones de tokens ("gran apuesta") es vulnerable a los ataques de miles de cuentas con pequeños saldos ("estaca simbólica"), y medidas tomadas contra un ataque, por ejemplo, comisiones no lineales creadas para para hacer que un bistec grande funcione de manera desventajosa, generalmente son desacreditados por otro ataque. Como se trata de un juego económico, los pesos estadísticos correspondientes se pueden calcular por adelantado y simplemente reemplazar las comisiones por otras aleatorias con la distribución adecuada. Dichas comisiones probabilísticas se implementan de manera extremadamente simple si la cadena de bloques tiene una fuente confiable de aleatoriedad y no requiere ningún cálculo complejo, lo que dificulta la vida de las ballenas y las crías.
Es necesario continuar recordando que el control sobre un solo bit en esta aleatorización le permite hacer trampa, reducir y duplicar las probabilidades, por lo que PVRB honesto es el componente más importante de dichos protocolos.
¿Dónde encontrar el azar correcto?
En teoría, las elecciones aleatorias honestas en redes descentralizadas proporcionan la seguridad comprobable de casi cualquier protocolo contra la colusión. La justificación es bastante simple: si la red está de acuerdo con un bit 0 o 1, y entre los participantes menos de la mitad son deshonestos, entonces, con un número suficiente de iteraciones, se garantiza que la red llegue a un consenso sobre este bit con una probabilidad fija. Solo porque un azar honesto elegirá a 51 de cada 100 participantes en el 51% de los casos. Pero esto es en teoría, porque en redes reales, para garantizar un nivel de seguridad tal como en los artículos, se requieren muchos mensajes entre hosts, criptografía compleja de múltiples pasadas y cualquier complicación del protocolo agrega inmediatamente nuevos vectores de ataque.
Es por eso que todavía no vemos en las cadenas de bloques un PVRB probado que se hubiera utilizado el tiempo suficiente para ser probado por aplicaciones reales, auditorías múltiples, cargas y, por supuesto, ataques reales, sin los cuales es difícil llamar al producto realmente seguro.
Sin embargo, hay varios enfoques prometedores a la vez, difieren en muchos detalles y algunos de ellos definitivamente resolverán el problema. Con los recursos computacionales modernos, la teoría criptográfica puede convertirse con bastante habilidad en aplicaciones prácticas. En el futuro, estaremos encantados de hablar sobre la implementación de PVRB: hay varios de ellos ahora, cada uno tiene su propio conjunto de propiedades y características importantes en la implementación, y cada uno tiene una buena idea. No hay muchos equipos involucrados en el azar, y la experiencia de cada uno de ellos es extremadamente importante para todos los demás. Esperamos que nuestra información permita que otros equipos se muevan más rápido, teniendo en cuenta la experiencia de sus predecesores.