Elección de líder a partir de balizas de aleatoriedad y otras estrategias

La elección de líder en una configuración de cadena de bloques tiene como objetivo seleccionar al participante que determinará el próximo bloque que se agregará a la cadena de bloques. Por lo general, se elige un validador por ranura del conjunto de validadores y obtiene el derecho de extender la cadena con un nuevo bloque en esa ranura. (Suponemos que los validadores mantienen la hora exacta y acuerdan el número de ranura actual). En este artículo exploramos estrategias para elección aleatoria de líder en protocolos de consenso. (Para obtener más información sobre la aleatoriedad en general, consulte nuestro artículo anterior, Aleatoriedad pública y balizas de aleatoriedad, Donde investigamos protocolos independientes para generar aleatoriedad impredecible y verificable públicamente). 

Por qué es importante la elección del líder

Elegir líderes honestos y activos es crucial para el crecimiento saludable de la cadena. Los validadores malintencionados no deberían poder sesgar el proceso de elección de líderes para convertirse en líderes con más frecuencia. De lo contrario, la producción de bloques podría caer en manos de partes que pueden censurar transacciones o detener la cadena de bloques por completo. En los protocolos de consenso de estilo de cadena más larga, un líder que produce un bloque no válido (o ningún bloque en absoluto) podría hacer que la cadena se bifurque temporalmente. En los protocolos de consenso de estilo BFT, un mal líder desencadena un subprotocolo de cambio de vista que incurrirá en una sobrecarga de comunicación. 

La alternativa de elección del comité

La elección del comité es un problema relacionado, donde el objetivo es seleccionar un subconjunto uniformemente aleatorio de los validadores de algún tamaño fijo k. Esta funcionalidad es útil por derecho propio porque a menudo se necesitan subcomités en la configuración de blockchain para reducir el tamaño del conjunto de validadores para hacer que el consenso se ejecute más rápido (entre muchos ejemplos están Sorteo de Algorand y Selección del comité de Ethereum). Pero la elección del comité también es útil para la elección del líder, lo que permite que los validadores eviten volver a ejecutar un protocolo de elección de líder si el líder electo no se presenta. Si, en lugar de un líder, se elige un comité con un orden fijo, el segundo miembro del comité puede convertirse en líder si el primero no está disponible. 

Las propiedades de un buen protocolo electoral

En un protocolo de elección de líderes, los líderes deben ser impredecibles. Si un atacante se entera de quién es el próximo líder, podría lanzar un ataque de denegación de servicio (DoS) para evitar que publique un bloque. El atacante podría derribar al siguiente líder y así sucesivamente, deteniendo la cadena de bloques. La imprevisibilidad también podría fortalecerse para garantizar que el validador mismo no sepa cuándo va a liderar, lo que podría ser importante para la prevención del soborno.

El proceso de elección de líder debe tener las siguientes tres propiedades:

• Justicia: cada validador honesto tiene una probabilidad de 1/N ser elegido de un conjunto de N validadores (una noción relajada de la equidad teórica del juego permite construir la elección del líder incluso en presencia de una mayoría malintencionada, aunque con un límite inferior no constante en el número de rondas).
• La imprevisibilidad: el adversario no conoce al próximo líder hasta algún tiempo T antes de que el líder anuncie el siguiente bloque.
• Exclusividad: se elige exactamente un líder en cada ranura.

Elección de líder secreto

La elección del líder secreto es una elección impredecible con T = 0. En este proceso, el líder no es conocido por nadie hasta que publica el bloque. Esto elimina por completo la ventana para un ataque DoS: antes de que el líder se revele, el atacante no sabe a quién atacar, por lo que su mejor estrategia es una suposición aleatoria. Y después de que el líder publica su bloque, es demasiado tarde para atacar porque el líder ya cumplió con su responsabilidad ante el protocolo. 

Sin embargo, la noción de "después de que el líder publica su bloque" es en realidad una simplificación, porque no tenemos transmisión instantánea en el mundo real. Un atacante con una sólida posición en la red podría notar que un líder transmite un bloque primero y podría corromper rápidamente al líder, crear un bloque diferente y adelantar la transmisión original. 

Si bien este es un modelo de atacante muy fuerte, se han propuesto defensas contra él. Algorand propuso la modelo de borrados, en el que el líder puede borrar la clave necesaria para firmar el bloque en su ranura antes transmitiéndolo, por lo que realmente es demasiado tarde para atacar en el momento en que el líder realiza alguna acción pública. Thaddeus Dryja, Quanquan C. Liu y Neha Narula, tres investigadores del MIT Media Lab, propuesto que el líder calcule un VDF en su bloque antes de la transmisión, asegurando que un atacante adaptativo no pueda construir un bloque válido alternativo a tiempo para que sea aceptado para el espacio deseado.

Otros métodos de elección 

El proceso de elección de líder más simple es round-robin, donde los líderes son elegidos en orden determinista. A pesar de que este enfoque es predecible y, por lo tanto, propenso a ataques DoS, es adecuado para sistemas autorizados donde los validadores tienen una buena protección DoS.

También se puede elegir un líder utilizando un resultado de un baliza de aleatoriedad, si hay uno disponible y de confianza para estar seguro. Desafortunadamente, es complicado para los participantes del consenso ejecutar ellos mismos un protocolo de baliza de aleatoriedad distribuida (DRB), ya que generalmente asumen una noción de transmisión o consenso confiable, que a su vez requiere la elección del líder nuevamente, introduciendo una dependencia circular.

Current elección de líder en Ethereum es un buen caso de estudio. Cada nuevo líder calcula una salida de función de aleatoriedad verificable (VRF) (una firma BLS en el número de época) y XOR el valor en la mezcla. El valor de la mezcla al final de la época. i define los líderes y los subcomités para la duración de la época i+2. Los líderes y su horario son predecibles con una época de anticipación (actualmente ~6.4 min). El protocolo es propenso a los ataques de equidad, ya que el último líder puede optar por publicar o retener su contribución a la mezcla y, por lo tanto, influir un poco en el resultado de las próximas elecciones. si el ultimo  k los líderes se confabulan, pueden introducir k  fragmentos de sesgo y hacer más probable la elección de usuarios malintencionados. La Fundación Ethereum está trabajando activamente en técnicas más avanzadas para la elección de líderes que analizamos a continuación.

Elección de líder basada en VRF

Otro enfoque, promovido por Algorand, Es un Elección de líder basada en VRF, que implica que cada validador calcule de forma privada una salida VRF y verifique si la salida cae por debajo de un umbral. Este procedimiento ya filtra la mayoría de los validadores, ya que el umbral se elige de tal manera que es poco probable caer por debajo de él. Los pocos validadores restantes revelan sus salidas VRF y se elige el que tiene el valor VRF más bajo. Este enfoque logra una perfecta imprevisibilidad (o secreto), pero no garantiza la unicidad. Es posible que algunos de los validadores no reciban mensajes de todos los líderes potenciales y asuman que el líder equivocado ganó las elecciones, lo que provocó que estos validadores se bifurcaran de la cadena principal. 

La evaluación VRF se siembra periódicamente con la salida de una baliza de aleatoriedad para que sea menos predecible para los propios validadores ver qué espacios van a liderar. Esta propiedad evita que un atacante que compromete silenciosamente al validador aprenda la ranura cuando el validador se convertiría en líder y lance un ataque cuando el validador esté a punto de anunciar un bloqueo. Este enfoque también ayuda a prevenir los ataques de soborno, en los que un validador demuestra a partes externas que será un líder en un espacio en particular y obtiene sobornos a cambio de completar alguna tarea como líder (por ejemplo, bloquear una transacción).

Estos enfoques, en los que el número de líderes elegidos es una variable aleatoria, se denominan Elección de líder probabilístico (PLE). PLE puede resultar en que no se elijan líderes para un puesto determinado. Esto es equivalente a elegir a un líder que es malicioso o está fuera de línea en el sentido de que finalmente se omitirá el espacio, lo que reduce la eficiencia del protocolo de consenso.

Pero la mayor advertencia con el PLE es que se pueden elegir varios líderes, lo que requiere algún tipo de procedimiento de desempate. Los empates representan un riesgo para el consenso, ya que un validador con una entrada ganadora puede informarlo solo a la mitad de la red, lo que podría causar desacuerdo en el líder elegido. Además, los procesos para resolver vínculos pueden requerir más tiempo y comunicación, lo que perjudica la eficiencia. Dfinity, discutido con más detalle en la primera publicación de esta serie, utiliza una baliza de aleatoriedad basada en VRF para elegir un solo líder; sin embargo, sacrifica la imprevisibilidad para hacerlo. Idealmente, cualquier proceso para elegir un líder debería evitar los lazos por completo y seguir siendo impredecible, lo que nos lleva al santo grial de esta área de investigación: la elección de un líder secreto único.

Elección de líder secreto único 

El objetivo de la Elección de líder secreto único (SSLE) es seleccionar un líder único de un conjunto de validadores manteniendo la equidad y la imprevisibilidad. Protocol Labs presentó la noción como una problema de investigación, y Dan Boneh, el científico informático de Stanford y asesor de investigación criptográfica de a16z, con Saba Eskandarian, Lucjan Hanzlik y Nicola Greco, ofrecieron más tarde una definición formal de SSLE. Esta propiedad de unicidad evita los riesgos de consenso y los costos de eficiencia derivados de los procedimientos de desempate. En concreto, Sarah Azouvi, de Protocol Labs, y Danielle Cappelletti, del Politecnico di Torino, Mostrar que cuando se usa SSLE en comparación con PLE en un protocolo de cadena más larga, los bloques se pueden finalizar significativamente más rápido (25 por ciento más rápido con un adversario que controla un tercio de la participación). Por lo tanto, desarrollar un protocolo SSLE práctico es un problema importante.

En el enfoque más común, que llamaremos basado en la reproducción aleatoria (utilizado tanto en el papel SSLE original como en una propuesta SSLE de Ethereum), cada validador registra un nuncio apostólico que parece aleatorio, pero que pueden probar que les pertenece. Los nonces luego se compilan en una lista. La lista se baraja de tal manera que los nonces se desvinculan de los validadores que los enviaron; es decir, dada la lista mezclada, ningún adversario puede decir qué validador envió qué nonce. A continuación, se elige un índice de lista de acuerdo con un público baliza de aleatoriedad, y el líder se revela demostrando que el nonce en ese índice de la lista barajada les pertenece. 

Dado que solo se elige un índice, el protocolo basado en la reproducción aleatoria siempre genera un único líder. Debido a que la baliza aleatoria está diseñada para generar valores aleatorios uniformes, el protocolo también es feria: cada validador tiene las mismas posibilidades de ser elegido. Además, si la mezcla se realiza correctamente (es decir, uniformemente al azar) y los nonces se vuelven desvinculables de las identidades de los validadores, este protocolo también logra impredecibilidad.

La reorganización es necesaria porque, si bien la simple elección de un índice de la lista no reorganizada basada en una baliza aleatoria ya brindaría singularidad y equidad, la imprevisibilidad es más difícil de lograr: si un adversario sabe qué validador envió qué nonce, sabe quién envió el nonce en el elegido. índice y puede identificar al líder. 

Estos dos enfoques siguientes barajan la lista de diferentes maneras. Cuanto más simple es el Propuesta Ethereum SSLE, En el que n los validadores envían sus nonces a través de Tor para desvincular las identidades de los validadores de sus nonces. Una vez que todos los validadores se han registrado, la lista se baraja utilizando una baliza de aleatoriedad pública y los validadores se convierten en líderes en el orden de la lista barajada. Si bien este esquema es práctico, la elección debe realizarse solo una vez por n tragamonedas: esta dependencia de Tor puede ser indeseable (como es el caso de confiar en la seguridad de cualquier protocolo externo). Además, no es perfectamente impredecible: después de la primera n-1 líderes se revelan, la final nth líder es conocido.

En lugar de usar Tor, el documento SSLE original tiene todos los registros de validación para la elección en secuencia agregando su nonce a la lista, barajando la lista y volver a aleatorizar los nonces. Esta nueva aleatorización significa que cada nonce se asigna a una nueva cadena no vinculable, de modo que el validador al que pertenece todavía puede probar la propiedad del nonce re-aleatorizado. La re-aleatorización hace que un adversario no pueda saber en qué posición terminó un nonce en particular después del barajado, suponiendo que al menos uno de los barajadores sea honesto.

Si bien este enfoque de barajado secuencial del documento SSLE original evita la dependencia de Tor y logra las propiedades formales de SSLE, es costoso: cada vez que se registra un nuevo validador, debe publicar la lista barajada completa en la cadena de bloques, volver a aleatorizar todos los nonces y proporcionar una prueba de que lo hicieron con honestidad, lo que da como resultado una cantidad lineal de comunicación por validador. Con un conjunto invariable de validadores, esto debe hacerse (amortizarse) una vez por elección, ya que el líder se vuelve a registrar una vez que ha revelado la prueba para el nonce. El documento ofrece una compensación ajustable entre eficiencia y previsibilidad: en su lugar, podemos barajar solo un subconjunto más pequeño de la lista, lo que reduce los costos, si estamos dispuestos a permitir una pequeña cantidad de previsibilidad. Lograr un buen equilibrio entre eficiencia y seguridad es un desafío y, como resultado, los protocolos SSLE aún no se utilizan ampliamente en la práctica. 

Convenientemente, este enfoque de barajado secuencial también se puede usar para resolver el problema de la elección del comité, usando la baliza aleatoria para elegir k índices distintos de la lista como miembros del comité. Este es un buen logro, ya que el problema no se resuelve trivialmente con enfoques basados ​​en VRF, ya que se ejecuta un protocolo basado en VRF probabilístico k veces puede elegir un tamaño de comité variable dependiendo de la aleatoriedad. 

Otros enfoques de SSLE

Otro enfoque basado en la reproducción aleatoria es SSLE seguro adaptativo de DDH. Esta construcción es un poco más complicada pero logra una noción más fuerte de seguridad, protegiendo contra un adversario adaptativo en el modelo de borrados de Algorand. Este adversario es adaptativo en el sentido de que puede elegir qué validadores corromper durante el protocolo, a diferencia de antes de que comience el protocolo. 

Otro desafío en SSLE es elegir cada validador con probabilidad proporcional a su apuesta, en lugar de uniformemente al azar. Los protocolos basados ​​en barajar pueden lograr esto de manera ingenua al permitir que cada validador registre múltiples nonces: un nonce por cada unidad de participación que tengan. Sin embargo, el costo de barajar aumenta linealmente con el número de unidades de apuesta. S, volviéndose muy caro incluso para distribuciones de participación realistas. Un elegante SSLE basado en MPC el enfoque tiene una complejidad que aumenta solo con log S, y también evita la necesidad de una configuración confiable o una baliza de aleatoriedad. Sin embargo, en comparación con los enfoques basados ​​en barajar, requiere más rondas de comunicación (logarítmicas en el número de participantes) por líder electo.

***

Hemos resumido nuestro análisis en esta práctica tabla.

	Justicia	Imprevisibilidad/ Secreto*	Exclusividad
Round-robin	✓	✗	✓
Baliza de aleatoriedad ideal	✓	✗	✓
Elección del líder de Ethereum (actual)	✗	✗	✓
Elección de líder basada en VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* La baliza round-robin es totalmente predecible, pero en el resto de balizas ✗ significa que la noción se logra hasta un cierto grado limitado: la baliza de aleatoriedad ideal es impredecible, pero el adversario aprende la salida al mismo tiempo que el líder electo, por lo tanto, el líder electo puede ser atacado antes de que anuncie un bloque; La baliza de Etherum es impredecible hasta ~6 minutos y puede estar ligeramente sesgada para dañar la equidad; Algorand elige múltiples líderes con una pequeña probabilidad.

SSLE es una dirección prometedora, que logra equidad, imprevisibilidad y singularidad. Dos desafíos destacados que enfrenta su adopción son la eficiencia y la capacidad de acomodar distribuciones de participación no uniformes. Además, los enfoques SSLE basados ​​en la reproducción aleatoria que destacamos asumen la existencia de una baliza aleatoria imparcial, lo que no es sencillo de lograr en la práctica. Dado que SSLE se definió formalmente recientemente, es probable que veamos protocolos mejorados que aborden sus desafíos en un futuro cercano. 

***

miranda cristo es estudiante de doctorado en Ciencias de la Computación en la Universidad de Columbia, donde es miembro del Theory Group y Presidential Fellow. También es pasante de investigación en a16z crypto.

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.