Aleatoriedad pública y balizas de aleatoriedad

Aleatoriedad pública es un componente esencial de muchos protocolos de seguridad del mundo real. En algunas aplicaciones, como los juegos de apuestas y multijugador, la aleatoriedad agrega diversión. En otras aplicaciones, la aleatoriedad proporciona una forma justa de asignar recursos no divisibles, que van desde tarjetas verdes hasta la asignación de jueces de tribunales de circuito a casos, hasta clasificación en torneos deportivos. También se utiliza para asignar negativas recursos, como auditorías fiscales o controles de seguridad secundarios en el aeropuerto.

Tradicionalmente, hemos dependido de autoridades confiables para generar aleatoriedad para estos protocolos, pero en el mundo web3, tendremos que hacerlo mejor. En esta publicación, exploraremos enfoques para generar aleatoriedad verificable públicamente mediante balizas de aleatoriedad distribuida y luego discuta algunas aplicaciones en cadena. (La Parte II, que se publicará próximamente, se centrará específicamente en la elección de líderes, al tiempo que proporciona una evaluación de los enfoques de elección de líderes suplentes). 

Propiedades deseadas

Generar números aleatorios es una tarea notoriamente sutil. Por ejemplo, se han filtrado muchas claves criptográficas porque se basó en un generador de números aleatorios defectuoso (para lo cual el muro de Cloudflare de lámparas de lava habría servido como una mitigación creativa). eso es solo aleatoriedad privada, sin embargo, donde solo una parte necesita generarlo y usarlo.

La aleatoriedad pública, por el contrario, es un proceso de múltiples partes, lo que aumenta considerablemente la dificultad. Un buen protocolo para producir aleatoriedad pública tendrá las siguientes propiedades de seguridad:

• Imparcial: Ningún atacante, o coalición de atacantes, debería poder sesgar la salida. 
• Confiable: Ningún atacante debería poder evitar que el protocolo produzca resultados.
• Verificable: Cualquiera puede verificar fácilmente la salida del protocolo y debería ver la misma salida que todos los demás.
• Imprevisible: si el protocolo produce una salida en el momento T₁, nadie debería poder predecir nada sobre la salida antes de algún tiempo T₀<T₁, idealmente con T₀ Muy cerca de T₁.

La falta de sesgo es una propiedad más débil que la imprevisibilidad porque cualquier protocolo que sea impredecible debe serlo. Los informáticos dirían imparcialidad reduce a la imprevisibilidad, porque si puedes sesgar, puedes predecir. Pero a veces querremos razonar sobre ellos por separado porque pueden basarse en suposiciones diferentes; por ejemplo, una mayoría deshonesta podría predecir el resultado, pero no sesgarlo.

Además de estas propiedades, el protocolo debe ser eficiente para ejecutarse y producir una gran cantidad de bits aleatorios. (En la práctica, a menudo es suficiente que las aplicaciones produzcan 128 bits aleatorios, usándolos para generar un generador de números pseudoaleatorios [PNRG] para generar más bits según sea necesario. Sin embargo, la imprevisibilidad debe mantenerse para que cada bit individual de la salida pueda usarse para tal aplicaciones como loterías o asignaciones de recursos). Idealmente, el protocolo también debería ser eficiente en términos de costos de comunicación y computación.

Diferentes protocolos pueden lograr estas propiedades bajo diferentes condiciones. Por ejemplo, algunos protocolos pueden ser imparciales por cualquier coalición de f₁ nodos maliciosos e impredecibles por cualquier coalición de f₂<f₁ nodos maliciosos. También hay diferentes grados de sesgo. Por ejemplo, en algunos protocolos, un participante podría sesgar la salida en "un bit", lo que significa que puede elegir entre una de dos salidas posibles. Otros ataques podrían permitirles arreglar la salida por completo. Sin embargo, normalmente no queremos tolerar ningún sesgo (o previsibilidad) en absoluto.

El ideal criptográfico: Rbalizas de soledad

Los criptógrafos a menudo comienzan pensando en una solución ideal para sus problemas. En el caso de la aleatoriedad pública, un baliza de aleatoriedad es un servicio idealizado que produce regularmente resultados aleatorios que satisfacen todos los requisitos de seguridad necesarios.

Tal baliza de aleatoriedad idealizada, similar a otras abstracciones criptográficas, como los oráculos aleatorios o el modelo de grupo genérico, no existe en el mundo real. Pero es un objetivo útil por el que luchar y un modelo útil para razonar sobre los protocolos que se basan en la aleatoriedad pública. 

Podemos considerar algunas aproximaciones de una baliza de aleatoriedad ideal.

• Balizas centralizadas: El enfoque más fácil para generar buena aleatoriedad es a través de un tercero centralizado con servicios como baliza de aleatoriedad NIST or Random.org, que genera aleatoriedad a partir del ruido atmosférico y está acreditado para su uso en juegos de azar. Esta dependencia de un tercero socava por completo la filosofía de la descentralización. De hecho, en el ejemplo anterior, debemos confiar en que las organizaciones relevantes están generando correctamente la aleatoriedad, sin ninguna prueba criptográfica.
• Muestras de aleatoriedad física: Muchas loterías tradicionales se basan en una exhibición pública, que puede incluir, por ejemplo, que alguien alcance un contenedor de pelotas de ping pong con diferentes números. Desafortunadamente, estos son a menudo fácilmente manipulables. Por ejemplo, ciertas bolas se pueden colocar en un congelador y se le puede decir al selector que elija los fríos.
• balizas naturales: Una idea común es utilizar fenómenos naturales aleatorios como el clima o la radiación cósmica de fondo como baliza. Desafortunadamente, todas las fuentes propuestas no brindan un fuerte consenso. Diferentes observadores verán valores ligeramente diferentes, lo que requiere volver a presentar una parte confiable para tomar una medición oficial, con todos los inconvenientes de una baliza centralizada.
• Balizas semicentralizadas: Un mejor enfoque sería obtener la aleatoriedad de Encabezados de bloque de Bitcoin directamente o de precios de cierre de las acciones, que es más fácil de verificar públicamente y más difícil de controlar completamente para cualquiera de las partes. Sin embargo, todavía existen ataques sutiles en ambos aleatoriedad de blockchain de prueba de trabajo y aleatoriedad del precio de las acciones. Con los encabezados de blockchain, por ejemplo, los mineros pueden optar por retener bloques cuyos encabezados producen un valor de baliza que no les gusta. O pueden optar por romper los empates cuando se encuentran dos bloques en colisión en función de su salida de baliza preferida.

Balizas de aleatoriedad descentralizadas (DRB)

Un enfoque natural a los problemas de las balizas centralizadas es diseñar un protocolo criptográfico descentralizado para producir aleatoriedad pública. Este problema es algo así como diseñar protocolos de consenso descentralizados, solo que más difícil. No solo todos los participantes deben estar de acuerdo con un resultado (la aleatoriedad), sino que debería ser imposible que un participante malicioso en el protocolo sesgue o prediga el resultado.

Los protocolos diseñados para simular una baliza de aleatoriedad se denominan balizas de aleatoriedad distribuida (DRB). (Otros nombres incluyen "lanzamiento de monedas distribuido".) El problema se ha estudiado durante décadas, con famosos resultados de imposibilidad probados en la década de 1980, pero el interés se ha reavivado en la era de la cadena de bloques. Los DRB podrían usarse para proporcionar aleatoriedad en la cadena, lo que sería un ingrediente clave para aplicaciones en la cadena justas, seguras y transparentes.

El enfoque clásico: protocolos de confirmación y revelación

Un protocolo muy simple de dos rondas es suficiente para un DRB en el caso optimista. En la ronda 1, cada participante i genera un valor aleatorio r_i y publica un compromiso criptográfico c_i=Comprometerse(r_i). En esta aplicación, el compromiso puede ser simplemente una función hash como SHA-256. Después de que se publica el compromiso de cada participante, quedan bloqueados en su elección de r_i, pero los compromisos no revelan ninguna información sobre las contribuciones de otros participantes. En la ronda 2, cada participante “abre su compromiso” publicando r_i. A continuación, todos los valores aleatorios se combinan, por ejemplo, mediante XOR o (preferiblemente) mediante el hash de su concatenación.

Este protocolo es simple y produce una salida de baliza aleatoria siempre que uno de los participantes elija su r_i al azar Desafortunadamente, adolece de un defecto clásico: cuando todos menos uno de los participantes han revelado su valor aleatorio, el último participante puede calcular la salida putativa de la baliza. Si no les gusta, pueden negarse a publicar su valor, abortando el protocolo. Ignorar la contribución de un participante defectuoso no soluciona el problema, porque eso aún le da al atacante la opción entre dos salidas de baliza (una calculada con su contribución y otra sin ella).

Las cadenas de bloques ofrecen un remedio natural a este problema: a cada participante se le puede solicitar que deposite algunos fondos en depósito que se incautan si no revelan su contribución aleatoria. Este fue exactamente el enfoque adoptado por el clásico RANDAO baliza en Ethereum. La desventaja de este enfoque es que la salida aún puede estar sesgada, lo que puede valer la pena financieramente para el atacante si el dinero en depósito es menor que la cantidad de dinero que depende del resultado de la baliza. Una mejor seguridad contra los ataques de sesgo requiere poner más monedas en custodia.

Protocolos de compromiso-revelación-recuperación

En lugar de intentar obligar a todas las partes a revelar su contribución aleatoria, algunos protocolos incluyen un mecanismo de recuperación para que, incluso si una minoría de los participantes se retira, el resto puede completar el protocolo. Es importante que el protocolo produzca el mismo resultado en cualquier caso, para que las partes no puedan sesgar el resultado eligiendo si abandonar o no.

Un enfoque para lograr esto es hacer que cada participante proporcione a los demás partes de su secreto, de modo que la mayoría de ellos pueda reconstruirlo, utilizando, por ejemplo, El secreto compartido de Shamir. Sin embargo, una propiedad importante es que los demás pueden verificar que el secreto comprometido se ha compartido correctamente, lo que requiere el uso de un primitivo más fuerte llamado intercambio de secreto verificable públicamente (PVSS).

Son posibles varios otros mecanismos de recuperación, pero todos tienen la misma limitación. Si hay N participantes, y queremos resiliencia si cualquier grupo de hasta f nodos, entonces debe darse el caso de que cualquier grupo de N.f. los participantes pueden calcular el resultado final. Pero eso también significa una coalición maliciosa de N.f. los participantes pueden predecir el resultado por adelantado simulando en privado el mecanismo de recuperación. Esto también puede ocurrir durante la primera ronda del protocolo, durante la cual dicha coalición podría modificar sus propias elecciones de aleatoriedad y sesgar el resultado. 

Dicho de otra manera, esto significa que cualquier coalición de N.f. los nodos deben incluir al menos un nodo honesto. Por álgebra simple, Nf > f, asi que f < N/2, y estos protocolos requieren inherentemente una mayoría honesta. Esta es una diferencia significativa con el modelo de seguridad original de confirmación-revelación, que solo requiere f<N (al menos un participante honesto).

Estos protocolos a menudo también requieren costos de comunicación significativos para compartir la información adicional de PVSS entre todos los nodos en cada ejecución del protocolo. La comunidad de investigación ha realizado un trabajo considerable sobre este problema en los últimos años, con propuestas de investigación que incluyen RandCompartir, Raspar, segundo, HIERBASo Albatros, pero ninguno parece haber visto una implementación en el mundo real.

Protocolos verificables basados ​​en funciones aleatorias

Al darse cuenta de que un grupo de N.f. los participantes pueden calcular el valor de la baliza aleatoria en el protocolo anterior conduce a un enfoque algo más simple: compartir una clave secreta a largo plazo entre N partes y hacer que lo usen para evaluar un función aleatoria verificable (VRF). La clave secreta se comparte a través de un t-fuera de-N esquema de umbral, de modo que cualquier t los participantes pueden calcular el VRF (pero una coalición más pequeña no puede). Para t=N.f., esto proporciona la misma resistencia a f nodos maliciosos como los protocolos de compromiso-revelación-recuperación discutidos anteriormente.

DFINITY fue pionero en este enfoque como parte de su protocolo de consenso utilizando firmas BLS de umbral (que funcionan como un VRF). el independiente dibujar baliza de aleatoriedad utiliza esencialmente el mismo enfoque, con un conjunto de participantes umbral-BLS-firmando un contador en cada ronda. los Liga de la Entropía es una instancia de código abierto de drand que produce aleatoriedad cada 30 segundos utilizando 16 nodos participantes (a partir de septiembre de 2022), administrado por una combinación de empresas y grupos de investigación universitarios. 

Una desventaja de estos enfoques es que la inicialización de la clave de umbral es relativamente compleja, al igual que la reconfiguración de la clave cuando los nodos se unen o se van. En el caso común, sin embargo, los protocolos son muy eficientes. 

Como se describió anteriormente, simplemente firmar un valor de contador no agrega ninguna nueva aleatoriedad por ronda, por lo que si se compromete una cantidad suficiente de claves de participantes, entonces el protocolo será predecible en cada ronda futura.

Eslabón de cadena VRF combina este enfoque (usando el NSEC5 VRF) con una fuente externa de aleatoriedad especificada por las partes que solicitan la aleatoriedad, generalmente un encabezado de cadena de bloques reciente en la práctica. Luego, estos datos se alimentan a través de un VRF que ejecuta una parte o se asigna a un grupo.

Ethereum Cadena de faro actualmente usa VRF basados ​​en BLS: el proponente de cada ronda agrega su valor de VRF a la mezcla. Esto ahorra una ronda de comunicación en comparación con el paradigma de revelación de confirmación (suponiendo que una clave pública BLS a largo plazo se registra una vez), aunque este diseño hereda algunas advertencias del enfoque de revelación de confirmación, incluida la posibilidad de sesgar la salida de la baliza reteniendo la salida. .

Protocolos basados ​​en funciones de retardo verificables

Finalmente, una nueva dirección prometedora es el uso de criptografía basada en el tiempo, específicamente funciones de retardo verificables (VDF). Este enfoque promete proporcionar una buena eficiencia y robustez de comunicación con resiliencia a N-1 nodos maliciosos. 

Volviendo al protocolo original de confirmación y revelación, los compromisos tradicionales se pueden reemplazar con compromisos cronometrados para eliminar el problema de los participantes que se niegan a revelar su contribución aleatoria. Los compromisos cronometrados pueden ser abiertos de manera eficiente por el autor original o por cualquiera que esté dispuesto a calcular una función lenta (esencialmente, un VDF). Por lo tanto, si algún participante abandona un protocolo de compromiso-revelación, otros aún pueden abrir su compromiso. Es esencial que el tiempo mínimo para abrir el compromiso sea lo suficientemente largo como para que no se pueda realizar durante la primera ronda (la fase de compromiso) del protocolo, de lo contrario, los participantes maliciosos podrían abrir los compromisos de otros lo suficientemente rápido como para modificar su propia contribución y sesgar el resultado. .

Un protocolo de una ronda aún más elegante es posible con los VDF modernos: abandone el compromiso por completo. Cada participante puede simplemente publicar su contribución aleatoria r_i, y el resultado final es una combinación de la contribución de cada participante, ejecutada a través de un VDF. El retraso de tiempo en el cómputo del VDF asegura que nadie pueda elegir su compromiso de una manera que sesgue el resultado final. Este enfoque fue propuesto como UNICORNIO por Arjen Lenstra y Benjamin Wesolowski en 2015, y de hecho fue una aplicación motivadora clave en el desarrollo de VDF.

Este enfoque ha tenido cierto despliegue práctico. Chia implementa una versión de esto como parte de su protocolo de consenso, utilizando VDF de cuadrados repetidos en grupos de clase. Starkware implementó un baliza de prueba de concepto basada en VDF utilizando VDF basados ​​en SNARK. Ethereum también planes que se utilizará Este enfoque, construyendo un ASIC dedicado para calcular VDF para generar aleatoriedad en la capa de consenso.

***

La aleatoriedad pública es un componente esencial de muchos protocolos, pero aún carecemos de un DRB estándar que proporcione una alta seguridad. El espacio de diseño es grande y son posibles muchos híbridos y combinaciones de los enfoques anteriores. Por ejemplo, es posible combinar un protocolo basado en VRF con un protocolo basado en VDF, que agrega entropía fresca, por ejemplo, como lo propone RandRunner. Beacon Chain de Ethereum actualmente usa VRF, aunque puede agregar VDF en el futuro para eliminar la posibilidad de sesgo de los ataques de retención de bloques.

También es una pregunta abierta cuándo son aceptables los protocolos de mayoría honesta. Para un grupo de participantes relativamente pequeño y examinado, como la Liga de la Entropía, una suposición de mayoría honesta es razonable. Por otro lado, los protocolos que solo requieren un único participante honesto tienen una ventaja inherente: más participantes solo pueden mejorar la seguridad. Esto significa que estos protocolos se pueden implementar potencialmente con una participación abierta y sin permiso.

En la Parte II, discutiremos la aplicación específica de la elección aleatoria de líderes en los protocolos de consenso, que tiene objetivos de diseño ligeramente diferentes y, como resultado, se han propuesto incluso más protocolos y enfoques.

***

José Bonneau es un socio de investigación en a16z crypto. Su investigación se centra en la criptografía aplicada y la seguridad blockchain. Ha impartido cursos de criptomonedas en la Universidad de Melbourne, NYU, Stanford y Princeton, y recibió un doctorado en ciencias informáticas de la Universidad de Cambridge y una licenciatura/maestría en ciencias de Stanford.

Valeria Nikolaenko es un socio de investigación en a16z crypto. Su investigación se centra en la criptografía y la seguridad de blockchain. También ha trabajado en temas como ataques de largo alcance en protocolos de consenso de PoS, esquemas de firma, seguridad poscuántica y computación multipartita. Tiene un doctorado en criptografía de la Universidad de Stanford bajo la asesoría del profesor Dan Boneh y trabajó en la cadena de bloques de Diem como parte del equipo de investigación principal.

***

Editor: Tim Sullivan

***

Las opiniones expresadas aquí son las del personal individual de AH Capital Management, LLC ("a16z") citado y no son las opiniones de a16z o sus afiliados. Cierta información contenida aquí se ha obtenido de fuentes de terceros, incluso de compañías de cartera de fondos administrados por a16z. Si bien se tomó de fuentes que se consideran confiables, a16z no ha verificado de forma independiente dicha información y no hace declaraciones sobre la precisión duradera de la información o su idoneidad para una situación determinada. Además, este contenido puede incluir anuncios de terceros; a16z no ha revisado dichos anuncios y no respalda ningún contenido publicitario incluido en ellos.

Este contenido se proporciona solo con fines informativos y no debe considerarse como asesoramiento legal, comercial, de inversión o fiscal. Debe consultar a sus propios asesores sobre estos asuntos. Las referencias a cualquier valor o activo digital son solo para fines ilustrativos y no constituyen una recomendación de inversión ni una oferta para proporcionar servicios de asesoramiento de inversión. Además, este contenido no está dirigido ni destinado a ser utilizado por ningún inversionista o posible inversionista, y bajo ninguna circunstancia se puede confiar en él al tomar una decisión de invertir en cualquier fondo administrado por a16z. (Una oferta para invertir en un fondo a16z se realizará solo mediante el memorando de colocación privada, el acuerdo de suscripción y otra documentación relevante de dicho fondo y debe leerse en su totalidad). Cualquier inversión o compañía de cartera mencionada, referida o descritos no son representativos de todas las inversiones en vehículos administrados por a16z, y no puede garantizarse que las inversiones serán rentables o que otras inversiones realizadas en el futuro tendrán características o resultados similares. Una lista de inversiones realizadas por fondos administrados por Andreessen Horowitz (excluyendo inversiones para las cuales el emisor no ha otorgado permiso para que a16z divulgue públicamente, así como inversiones no anunciadas en activos digitales que cotizan en bolsa) está disponible en https://a16z.com/investments /.

Los cuadros y gráficos proporcionados en el interior tienen únicamente fines informativos y no se debe confiar en ellos al tomar cualquier decisión de inversión. El rendimiento pasado no es indicativo de resultados futuros. El contenido habla sólo a partir de la fecha indicada. Todas las proyecciones, estimaciones, pronósticos, objetivos, perspectivas y/u opiniones expresadas en estos materiales están sujetas a cambios sin previo aviso y pueden diferir o ser contrarias a las opiniones expresadas por otros. Consulte https://a16z.com/disclosures para obtener información adicional importante.