Introducción
«La generación de números aleatorios es demasiado importante para dejarla al azar»
Robert Cavyu, 1970
Este artículo se centra en la aplicación práctica de soluciones que utilizan la generación colectiva de números aleatorios en un entorno no confiable. En resumen, cómo y para qué se utiliza el azar en las blockchains, y un poco sobre cómo distinguir entre un “buen” azar y un “mal” azar. La generación de un número aleatorio verdaderamente es un problema muy complicado incluso en una sola computadora, y ha sido estudiada por criptógrafos desde hace tiempo. En las redes descentralizadas, la generación de números aleatorios es aún más difícil y crucial.
Precisamente en redes donde los participantes no confían entre sí, la capacidad de generar un número aleatorio indiscutible permite resolver eficazmente múltiples tareas importantes y mejorar significativamente los esquemas existentes. Cabe señalar que los juegos de azar y las loterías no son en absoluto el objetivo principal, como podría parecer inicialmente a un lector no experimentado.
Generación de números aleatorios
Los ordenadores no pueden generar números aleatorios por sí mismos, necesitan ayuda externa para ello. Un ordenador puede obtener un valor aleatorio utilizando, por ejemplo, el movimiento del ratón, la cantidad de memoria utilizada, los ruidos eléctricos en los contactos del procesador y muchas otras fuentes, conocidas como fuentes de entropía. Estos valores no son del todo aleatorios, ya que están dentro de un rango específico o tienen un patrón predecible en su variación. Para convertir tales números en un número verdaderamente aleatorio en un rango determinado, se aplican transformaciones criptográficas, con el fin de obtener valores pseudoaleatorios uniformemente distribuidos a partir de valores de fuente de entropía que no están distribuidos uniformemente. Los valores obtenidos se llaman pseudoaleatorios, ya que no son realmente aleatorios, sino que se producen de manera determinista a partir de la entropía. Cualquier buen algoritmo criptográfico, al cifrar datos, produce textos cifrados que estadísticamente deberían ser indistinguibles de una secuencia aleatoria, por lo que se puede utilizar una fuente de entropía que solo ofrezca una buena irrepetibilidad y aleatoriedad de los valores, incluso dentro de rangos pequeños; el algoritmo de cifrado se encargará del resto de la dispersión y mezcla de bits en el valor resultante.
Para terminar este breve repaso, añadiré que la generación de 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 para establecer conexiones seguras en diversas redes, para generar claves criptográficas, para equilibrar la carga, controlar la integridad y para muchas otras aplicaciones. La seguridad de muchos protocolos depende de la capacidad de generar un 'random' fiable e impredecible desde el exterior, conservarlo y no revelarlo hasta el siguiente paso del protocolo; de lo contrario, la seguridad se verá comprometida. Un ataque al generador de valores pseudoaleatorios es extremadamente peligroso y pone en riesgo todo el software que utiliza la generación de aleatoriedad.
Todo esto debe saberlo si ha realizado un curso básico de criptografía, así que continuemos con las redes descentralizadas.
Aleatorio en blockchains
Primero hablaré sobre blockchains que soportan contratos inteligentes, ya que son los que pueden aprovechar al máximo las capacidades que ofrece un aleatorio innegable de calidad. A partir de ahora, por brevedad, denominaré a esta tecnología “Faros Aleatorios Verificables Públicamente” o PVRB. Dado que las blockchains son redes cuya información puede ser verificada por cualquier participante, una parte clave del nombre es “Verificable Públicamente”, es decir, cualquier persona puede, mediante cálculos, obtener pruebas de que el número generado, almacenado en la blockchain, tiene las siguientes propiedades:
- El resultado debe tener una distribución demostrablemente uniforme, es decir, estar basado en criptografía demostrablemente resistente.
- No se puede controlar ninguno de los bits del resultado. Como consecuencia, el resultado no puede ser predicho de antemano.
- No se puede sabotear el protocolo de generación por no participar en el protocolo o mediante la sobrecarga de la red con mensajes agresivos.
- Todo lo anterior debe ser resistente a conspiraciones de un número aceptable de participantes deshonestos en el protocolo (por ejemplo, 1/3 de los participantes).
Cualquier posibilidad de que un grupo minoritario conspirador produzca un aleatorio controlado par/impar es una vulnerabilidad de seguridad. Cualquier posibilidad de que un grupo detenga la emisión de aleatorios es una vulnerabilidad 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 los diversos juegos, loterías y en general cualquier tipo de apuestas en la blockchain. De hecho, esta es una dirección importante, pero el aleatorio en blockchains tiene aplicaciones aún más significativas. Examinemos estas.
Algoritmos de consenso
El PVRB para la organización del consenso en la red juega un papel crucial. Las transacciones en las cadenas de bloques están protegidas por una firma electrónica, por lo que un “ataque a la transacción” siempre implica incluir/excluir una transacción en un bloque (o en varios bloques). La principal tarea del algoritmo de consenso es acordar el orden de estas transacciones y el orden de los bloques que las incluyen. Además, una característica necesaria para las cadenas de bloques reales es la finalización: la capacidad de la red para acordar que la cadena hasta el bloque finalizado es definitiva y nunca será excluida debido a un nuevo fork. Por lo general, para acordar que un bloque es válido y, lo más importante, final, se requiere recoger firmas de la mayoría de los productores de bloques (en adelante BP — block-producers), lo que requiere al menos entregar la cadena de bloques a todos los BP y difundir las firmas entre todos los BP. A medida que crece el número de BP, la cantidad de mensajes necesarios en la red crece exponencialmente, por lo que los algoritmos de consenso que requieren finalización, como el consenso pBFT de Hyperledger, no funcionan a la velocidad necesaria a partir de unas pocas decenas de BP, exigiendo un número enorme de conexiones.
Si en la red hay un PVRB indiscutible y honesto, entonces, incluso en el caso más simple, se puede usar como base para seleccionar a uno de los productores de bloques y designarlo como “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 transacciones y no crean forks de la cadena con el objetivo de llevar a cabo un ataque de “doble gasto”, entonces el uso de un PVRB indiscutible uniformemente distribuido permitirá seleccionar un líder honesto con una probabilidad de M / N (M / N > 1/2). Si se asigna a cada líder un intervalo de tiempo propio durante el cual puede generar un bloque y validar la cadena, y estos intervalos son iguales en duración, entonces la cadena de bloques de los BP honestos será más larga que la cadena formada por los BP maliciosos, y el algoritmo de consenso que se basa en la longitud de la cadena simplemente descartará la "mala". Este principio de asignar intervalos de tiempo iguales a cada BP fue utilizado por primera vez en Graphene (el precursor de EOS), y permite que la mayoría de los bloques se cierren con una sola firma, lo que reduce significativamente la carga en la red y permite que este consenso funcione de manera extremadamente rápida y estable. Sin embargo, las redes EOS ahora tienen que utilizar bloques especiales (Last Irreversible Block), que son confirmados por las firmas de 2/3 de los BP. Estos bloques sirven para asegurar la finalización (la imposibilidad de que aparezca un fork en la cadena que comience antes del último Last Irreversible Block).
Además, en implementaciones reales, el esquema del protocolo es más complejo: las votaciones sobre los bloques propuestos se realizan en varias etapas para mantener el funcionamiento de la red en caso de que se pierdan bloques y surjan problemas en la red, pero incluso teniendo en cuenta esto, los algoritmos de consenso que utilizan PVRB requieren significativamente menos mensajes entre los BP, lo que permite que sean más rápidos que el tradicional PВFT, o sus diversas modificaciones.
El representante más notable de tales algoritmos es: del equipo de Cardano, que, según se ha declarado, posee una resistencia matemáticamente demostrable ante la colusión entre BP.
En Ouroboros, PVRB se utiliza para determinar el llamado "BP schedule" — calendario en el que se asigna a cada BP su hueco temporal para publicar un bloque. Una gran ventaja del uso de PVRB es la "igualdad total" entre los BP (según los tamaños de sus balances). La honradez de PVRB garantiza que los BP maliciosos no pueden controlar el calendario de los huecos temporales y, por lo tanto, no pueden manipular la cadena, preparando y analizando forks de la cadena de antemano, y para elegir un fork es suficiente basarse simplemente en la longitud de la cadena, sin recurrir a ingeniosas formas de calcular la "utilidad" de los BP y el "peso" de sus bloques.
En general, en todos los casos en que se necesita seleccionar un participante al azar en una red descentralizada, casi siempre la mejor opción será PVRB, en lugar de una variante determinista basada, por ejemplo, en el hash de un bloque. Sin PVRB, la posibilidad de influir en la elección del participante lleva a la aparición de ataques, donde el atacante puede, al elegir entre varias opciones futuras, seleccionar al siguiente participante corrupto o a varios a la vez para asegurar una mayor participación en la toma de decisiones. El uso de PVRB desacredita este tipo de ataques.
Escalabilidad y balanceo de carga
PVRB también puede ser de gran beneficio en tareas para reducir la carga y escalar pagos. Para empezar, tiene sentido familiarizarse con Rivesta "Boletos Electrónicos de Lotería como Micropagos". La idea general es que, en lugar de hacer 100 pagos de 1c del pagador al receptor, se puede jugar a una lotería justa con un premio de 1$ = 100c, donde el pagador, en cada pago de 1c, transfiere al banco uno de sus 100 "boletos de lotería". Uno de estos boletos gana al banco 1$, y precisamente este boleto puede ser registrado en la blockchain por el receptor. Lo más importante es que los otros 99 boletos se transfieren entre el receptor y el pagador sin ningún tipo de participación externa, a través de un canal privado y a cualquier velocidad deseada. Se puede leer una buena descripción del protocolo basado en este esquema en la red Emercoin. .
Este esquema tiene varios problemas, por ejemplo, el receptor puede dejar de atender al pagador inmediatamente después de recibir el boleto ganador, pero para muchas aplicaciones específicas, como la tarificación por minuto o las suscripciones electrónicas a servicios, se pueden desestimar. El principal requisito, por supuesto, es la honestidad de la lotería que se lleva a cabo, y para su realización es absolutamente necesario PVRB.
La selección aleatoria de un participante es extremadamente importante para los protocolos de sharding, cuyo objetivo es la escalabilidad horizontal de la cadena de bloques, permitiendo que diferentes BP procesen únicamente su propio ámbito de transacciones. Esta es una tarea muy compleja, especialmente en cuestiones de seguridad al integrar shards. La selección justa de un BP aleatorio para designarlo responsable de un shard específico, al igual que en los algoritmos de consenso, es también una tarea de PVRB. En los sistemas centralizados, los shards son asignados por un equilibrador, que simplemente calcula un hash de la solicitud y lo envía al ejecutor correspondiente. En las cadenas de bloques, la capacidad de influir en esta asignación puede llevar a un ataque al consenso. Por ejemplo, el contenido de las transacciones puede ser controlado por un atacante, quien puede controlar qué transacciones ingresan a su shard controlado y manipular la cadena de bloques dentro de él. Se puede leer sobre el problema del uso de números aleatorios para las tareas de sharding en Ethereum.
El sharding es una de las tareas más ambiciosas y serias en el ámbito de la blockchain; su solución permitirá construir redes descentralizadas de rendimiento y volumen fantásticos. PVRB es solo uno de los componentes importantes para su solución.
Juegos, protocolos económicos, arbitraje
El papel de los números aleatorios en la industria del juego es difícil de sobreestimar. Su uso explícito en los casinos en línea y su uso implícito al calcular los efectos de las acciones de un jugador son problemas complejos para las redes descentralizadas, donde no se puede confiar en una fuente central de aleatoriedad. Sin embargo, la selección aleatoria 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 poca frecuencia. En este caso, si hay un PVRB irrefutable, los clientes y los vendedores pueden acordar una resolución aleatoria de las disputas, pero con una probabilidad establecida. Por ejemplo, con una probabilidad del 60%, gana el cliente, y con una probabilidad del 40%, gana el vendedor. Este enfoque, que puede parecer absurdo al principio, permite resolver automáticamente las disputas con una proporción de ganancias/pérdidas predecible que satisface a ambas partes, sin la necesidad de un tercero y sin perder tiempo. Además, la relación de probabilidades puede ser dinámica y depender de algunas variables globales. Por ejemplo, si la empresa va bien, con un bajo número de disputas y alta rentabilidad, puede ajustar automáticamente la probabilidad de resolución de disputas hacia una mayor orientación al cliente, por ejemplo, 70/30 o 80/20, y viceversa; si las disputas son costosas y fraudulentas o inadecuadas, puede mover la probabilidad en la dirección opuesta.
Una gran cantidad de protocolos descentralizados interesantes, como los registros de tokens curados, los mercados de predicción, las curvas de vinculación y muchos otros, representan juegos económicos que recompensan el buen comportamiento y castigan el malo. Estos a menudo enfrentan problemas de seguridad, donde las soluciones a menudo son contradictorias. Lo que está protegido contra ataques de "ballenas" con miles de millones de tokens ("gran participación") es vulnerable a ataques de miles de cuentas con saldos pequeños ("participación sybil"), y las medidas adoptadas contra un tipo de ataque, como las comisiones no lineales diseñadas para hacer que la participación grande no sea rentable, a menudo son desbordadas por otro ataque. Dado que se trata de un juego económico, los pesos estadísticos correspondientes se pueden calcular con antelación y simplemente sustituir las comisiones por comisiones aleatorias con la distribución correspondiente. Tales comisiones probabilísticas se implementan extremadamente simple, si hay una fuente confiable de aleatoriedad en la blockchain y no requieren cálculos complejos, complicando la vida tanto a las ballenas como a los sybils.
Sin embargo, es importante recordar que controlar un solo bit de esa aleatoriedad permite hacer trampas, reduciendo y aumentando las probabilidades al doble, por lo que un PVRB honesto es una parte esencial de tales protocolos.
¿Dónde encontrar la aleatoriedad correcta?
En teoría, una selección aleatoria honesta en redes descentralizadas permite asegurar la seguridad demostrable de casi cualquier protocolo contra conspiraciones. La justificación es bastante simple: si la red conviene en un bit de 0 o 1, y entre los participantes menos de la mitad son deshonestos, entonces, tras un número suficiente de iteraciones, la red llegará a un consenso sobre ese bit con una probabilidad fija. Simplemente porque la aleatoriedad honesta seleccionará a 51 de 100 participantes en el 51% de los casos. Pero eso es en teoría, ya que en redes reales, para garantizar un nivel de seguridad como se describe en los artículos, se requiere un gran número de mensajes entre hosts, criptografía compleja de múltiples pasos, y cualquier complicación del protocolo inmediatamente añade nuevos vectores de ataque.
Es por eso que aún no vemos en las blockchains un PVRB probado y resistente, que haya sido utilizado el tiempo suficiente para superar las pruebas de aplicaciones reales, múltiples auditorías, cargas de trabajo y, por supuesto, ataques reales, sin los cuales es difícil llamar a un producto verdaderamente seguro.
Sin embargo, hay varios enfoques prometedores, diferenciándose en muchos detalles, y alguno de ellos seguramente resolverá el problema. Con los recursos de computación actuales, la teoría criptográfica puede transformarse con bastante agilidad en aplicaciones prácticas. Más adelante, con gusto hablaremos sobre las implementaciones de PVRB: hay varias en la actualidad, cada una con su propio conjunto de propiedades importantes y características de implementación, y detrás de cada una hay una buena idea. No hay muchos equipos que se dediquen a la aleatoriedad, y la experiencia de cada uno de ellos es extremadamente valiosa para 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
