Nota del editor: a16z crypto ha tenido una larga serie de "pistolas” — forma nuestro nuestro original Cripto canon para nuestro canon DAO y canon NFT a, más recientemente, nuestro Canon de conocimiento cero. A continuación, ahora hemos seleccionado un conjunto de recursos para aquellos que buscan comprender, profundizar y construir con consenso: los sistemas de acuerdo que permiten el funcionamiento de las criptomonedas, determinando la validez de las transacciones y la gobernanza de la cadena de bloques.

Los protocolos de consenso son una pieza central de todo lo que sucede en el mundo de la cadena de bloques. Desafortunadamente, la literatura puede ser difícil de manejar. Aquí proporcionamos una lista de enlaces que deberían ponerlo al día con lo último en investigaciones recientes.

Clasificaremos los enlaces a continuación según el tipo de protocolo discutido. Primero, sin embargo, una lista de algunos recursos generales, que brindan una excelente descripción general de la investigación existente. 

Recursos generales

Pensamientos descentralizados. Este blog está dirigido por Ittai Abraham y Kartik Nayak, pero también cuenta con muchas contribuciones de otros investigadores destacados. Comienza desde lo básico, pero también puede encontrar explicaciones simples de artículos recientes. 

Consenso en 50 páginas. Notas de Andrew Lewis-Pye que cubren los resultados clave de la literatura clásica de consenso. La versión en este enlace está en construcción y se actualiza con frecuencia. Vea también los seminarios de criptografía a16z basados ​​en estas notas (Parte I, Parte II). 

Fundamentos del Consenso Distribuido y Blockchains. Un borrador preliminar del libro de texto de Elaine Shi.

Fundamentos de Blockchains. Una serie de conferencias en YouTube por Tim Roughgarden. 

Fundamentos de la cadena de bloques. Notas de clase centradas en los protocolos de prueba de trabajo y prueba de participación por David Tse. 

Definición de consenso

Los tres problemas de consenso más estudiados son Transmisión bizantina, Acuerdo bizantinoy Replicación de máquinas de estado (el problema que resuelven los protocolos blockchain). Para obtener una explicación de la relación entre estos problemas, consulte Consenso en 50 páginas (enumerados anteriormente) o estos blogs en Pensamientos descentralizados: “¿Qué es el consenso? y Consenso para la replicación de máquinas de estado."

El problema de los generales bizantinos (1982) de Leslie Lamport, Robert Shostak y Marshall Pease.
Este artículo presenta el conocido “Problema de los generales bizantinos”. Todavía vale la pena leerlo, pero se pueden encontrar mejores versiones de algunas de las pruebas en otros lugares. Para la prueba de que se puede resolver el problema de cualquier número de procesadores defectuosos con una infraestructura de clave pública (PKI), se puede encontrar una versión más simple y eficiente en el artículo de Dolev y Strong (ver más abajo en la sección sobre “sistemas síncronos”). protocolos”). Para el famoso resultado de imposibilidad de que, en ausencia de una PKI, el problema es irresoluble a menos que menos de un tercio de los procesadores muestren fallas bizantinas, se puede encontrar una prueba más comprensible en el artículo de Fischer, Lynch y Merritt (también a continuación) . 

Implementación de servicios tolerantes a fallas utilizando el enfoque de máquina de estado: un tutorial (1990) de Fred Schneider.
También debería echar un vistazo a este documento anterior, que trata el problema de State-Machine-Replication (SMR), el problema resuelto por los protocolos de cadena de bloques.

Protocolos síncronos

Estamos en la configuración "sincrónica" cuando la entrega de mensajes es confiable, es decir, los mensajes siempre se entregan y existe un límite conocido finito en el tiempo máximo para la entrega de mensajes. Para una definición formal, vea los enlaces dados arriba. 

Algoritmos autenticados para acuerdos bizantinos (1983) de Danny Dolev y H. Raymond Strong.
Hay dos pruebas significativas aquí. Hay una prueba de que uno puede resolver la transmisión bizantina para cualquier número de procesadores defectuosos dada una infraestructura de clave pública (PKI). Para otra exposición de esto, ver “Difusión autenticada Dolev-Strong” en Pensamientos descentralizados. También hay una prueba de que f + 1 rondas son necesarias para resolver la transmisión bizantina si hasta f los procesadores pueden estar defectuosos. Para una prueba más simple ver Una prueba simple de bivalencia de que el consenso t-Resilient requiere t+1 rondas de Marcos Aguilera y Sam Toueg. 

Pruebas fáciles de imposibilidad para problemas de consenso distribuido (1986) de Michael Fischer, Nancy Lynch y Michael Merritt.
Ver también charlas recientes que cubren esto, por Andrew Lewis-Pye y tim jardín áspero. 

Límites del intercambio de información para el acuerdo bizantino (1985) de Danny Dolev y Rüdiger Reischuk.
No hay esa muchas formas de prueba de imposibilidad en la literatura de consenso. Este es uno importante que muestra cómo poner un límite inferior a la cantidad de mensajes que deben enviarse para resolver problemas de consenso. 

"El Protocolo Phase King", del artículo Consenso distribuido de bits óptimos (1992) de Piotr Berman, Juan Garay y Kenneth Perry.
Si desea ver un protocolo que resuelve el Acuerdo bizantino en la configuración síncrona sin PKI, este es probablemente el más informativo. Para una publicación de blog reciente que explica esto claramente, consulte “Phase-King a través de la lente de Gradecast: un acuerdo bizantino sincrónico simple no autenticado” en Pensamientos descentralizados.

Protocolos parcialmente síncronos

Aproximadamente, estamos en la configuración "parcialmente síncrona" cuando la entrega de mensajes a veces es confiable ya veces no. Se requieren protocolos para garantizar la "seguridad" en todo momento, pero solo deben estar "en vivo" durante los intervalos en los que la entrega de mensajes es confiable. La forma estándar de modelar esto es asumir la existencia de un "Tiempo de estabilización global" (GST) desconocido después del cual los mensajes siempre se entregarán dentro de un límite de tiempo conocido. Para una definición formal, vea los enlaces en el cuadro de arriba. 

Consenso en presencia de sincronía parcial (1988) de Cynthia Dwork, Nancy Lynch y Larry Stockmeyer.
Este es el artículo clásico que presenta la configuración parcialmente síncrona y demuestra muchos de los resultados clave. 

El último chisme sobre el consenso BFT (2018) de Ethan Buchman, Jae Kwon y Zarko Milosevic.
Dada la presentación correcta, el protocolo Tendermint (descrito en este documento) es lo suficientemente simple como para que sea una buena manera de aprender State-Machine-Replication en la configuración parcialmente sincrónica. Se puede encontrar una presentación muy simple en Consensus en 50 páginas (ver arriba), y también hay presentaciones claras en charlas de Andrew Lewis-Pye y tim jardín áspero. 

Streamlet: cadenas de bloques simplificadas de libros de texto (2020) de Benjamin Chan y Elaine Shi.
Este documento describe un protocolo de cadena de bloques que está específicamente diseñado para ser fácil de enseñar. Puedes encontrar una conferencia de Elaine Shi al respecto. esta página. 

Casper, el gadget de finalización amistoso (2017) de Vitalik Buterin y Virgil Griffith.
Este es el protocolo que forma la columna vertebral del enfoque actual de Ethereum para la prueba de participación. Es esencialmente una versión "encadenada" de Tendermint. Para obtener una explicación del "encadenamiento", consulte el documento Hotstuff que se detalla a continuación. 

HotStuff: Consenso BFT en la lente de Blockchain (2018) de Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta e Ittai Abraham.
Este fue esencialmente el protocolo que el proyecto Libra de Facebook (rebautizado como Diem) originalmente pretendía implementar. La ventaja sobre Tendermint es que el protocolo es optimistamente receptivo, lo que significa que los bloques confirmados se pueden producir a la "velocidad de la red" cuando los líderes son honestos, es decir, no hay ningún requisito para dedicar un tiempo mínimo predefinido a la producción de cada bloque confirmado. También puede ver una charla de Ittai Abraham sobre este esta página. 

Sincronización de ronda lineal esperada: el eslabón perdido para SMR bizantino lineal (2020) de Oded Naor e Idit Keidar.
Este documento aborda el problema con Hotstuff de que no establece ningún mecanismo eficiente para la "sincronización de vistas". Esto blog por Dahlia Malkhi y Oded Naor ofrece una descripción general del trabajo sobre el problema de sincronización de vistas. Ver también esta mayor optimización por Andrew Lewis-Pye e Ittai Abraham.

Paxos simplificado (2001) de Leslie Lamport.
Si no desea saltar directamente a los protocolos de cadena de bloques recientes como Tendermint, una alternativa es comenzar con Paxos (que no se ocupa de las fallas bizantinas) y luego pasar a PBFT, que es el siguiente enlace en nuestra lista. (y cuál lo hace). 

Tolerancia de falla bizantina práctica (1999) de Miguel Castro y Bárbara Liskov.
Este es el protocolo PBFT clásico. Se puede encontrar una gran charla sobre el protocolo de Barbara Liskov esta página.

Protocolos asíncronos

En la configuración "asincrónica", se garantiza que los mensajes llegarán, pero pueden demorar una cantidad de tiempo finita. Para una definición formal, vea los enlaces en el cuadro de arriba. 

Imposibilidad de consenso distribuido con un proceso defectuoso (1985) de Michael Fischer, Nancy Lynch y Michael Paterson.
El teorema FLP (llamado así por los autores) es probablemente el resultado de imposibilidad más famoso en la literatura sobre protocolos de consenso: ningún protocolo determinista resuelve el acuerdo bizantino (o SMR) en la configuración asíncrona cuando incluso un único procesador desconocido puede estar defectuoso. Puede encontrar una buena presentación en una conferencia de Tim Roughgarden esta página. 

"Transmisión de Bracha", apareció por primera vez en el periódico Protocolos de acuerdos bizantinos asincrónicos (1987) de Gabriel Bracha.
Una forma de eludir el teorema de imposibilidad de FLP es debilitar el requisito de terminación. La transmisión de Bracha es un protocolo determinista que funciona en la configuración asíncrona al resolver una forma más débil de transmisión bizantina que no requiere terminación en caso de que la transmisión falle. Si bien la transmisión de Bracha aparece por primera vez en el documento anterior, el documento también muestra cómo usar el protocolo de transmisión para resolver el acuerdo bizantino con la ayuda de la aleatoriedad. Si solo desea aprender la transmisión de Bracha, puede encontrar una presentación clara esta página.

FastPay: liquidación tolerante a fallas bizantinas de alto rendimiento (2020) de Mathieu Baudet, George Danezis y Alberto Sonnino.
Este artículo describe cómo implementar un sistema de pago en el entorno asíncrono utilizando una transmisión confiable (y sin la necesidad de establecer una ordenación total). 

Si realmente necesita resolver el acuerdo bizantino o SMR en la configuración asíncrona, entonces el resultado de FLP significa que tendrá que usar alguna forma de aleatoriedad. Además del artículo de Bracha (mencionado arriba), los siguientes dos enlaces son clásicos de la literatura que describen cómo resolver el acuerdo bizantino usando la aleatoriedad: 

1. Otra Ventaja de la Libre Elección: Protocolos de Acuerdo Completamente Asincrónicos (1983) de Michael Ben-Or
2. Oráculos aleatorios en Constantinopla: Acuerdo bizantino asíncrono práctico utilizando Criptografía (2005) de Christian Cachin, Klaus Kursawe y Victor Shoup

Acuerdo bizantino asíncrono validado con resiliencia óptima y comunicación asintóticamente óptima de tiempo y palabra (2018) de Ittai Abraham, Dahlia Malkhi y Alexander Spiegelman.
Una ruta alternativa para comprender cómo resolver SMR (y el acuerdo bizantino) en la configuración asincrónica es saltar con el documento anterior, que modifica Hotstuff. Si ya entiende Hotstuff, entonces la modificación es bastante simple. Uno no puede ejecutar Hotstuff estándar en la configuración asincrónica porque, después de seleccionar un líder, el adversario puede simplemente retener los mensajes de ese líder. Dado que las partes honestas no saben si el líder es deshonesto y no está enviando mensajes, o si el líder es honesto y sus mensajes se retrasan, eventualmente se ven obligados a intentar avanzar de otra manera. Para resolver el problema, simplemente hacemos que todas las partes actúen como líderes simultáneamente. Una vez que una gran mayoría de partes completa con éxito una "vista" estándar del protocolo Hotstuff, seleccionamos retrospectivamente un líder al azar. Si han producido un bloque confirmado, entonces usamos ese, descartando el resto. 

Dumbo-MVBA: acuerdo bizantino asíncrono validado multivalor óptimo, revisado (2020) de Yuan Lu, Zhenliang Lu, Qiang Tang y Guiling Wang.
Este artículo optimiza el anterior de Abraham, Malkhi y Spiegelman, reduciendo la complejidad esperada de la comunicación. 

El tejón de miel de los protocolos BFT (2016) de Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi y Dawn Song.

En busca de un acuerdo bizantino autenticado óptimo (2020) de Alexander Spiegelmann.
La ventaja de los protocolos asincrónicos es que pueden progresar incluso cuando la entrega de mensajes no es confiable. Una desventaja es que los costos de comunicación no son óptimos (en varios sentidos) cuando las condiciones de la red son buenas. El documento anterior aborda la pregunta "hasta qué punto podemos obtener lo mejor de ambos mundos". 

protocolos DAG

Hay una oleada de trabajos recientes sobre protocolos basados ​​en DAG autorizados. Estos son protocolos en los que el conjunto de bloques confirmados forma un gráfico acíclico dirigido, en lugar de estar ordenado linealmente. En general, estos funcionan en configuraciones asíncronas o parcialmente síncronas. 

En este seminario criptográfico a16z, Andrew Lewis-Pye da una visión general de consenso basado en DAG.

Los siguientes cuatro documentos describen los protocolos DAG que logran un ordenamiento total eficiente en las transacciones. DAG-Rider opera en la configuración asincrónica y es similar a Cordial Miners, pero tiene una latencia más alta y una complejidad de comunicación esperada (amortizada) más baja. Narwhal es un protocolo mempool y Tusk es un protocolo SMR que opera sobre Narwhal y mejora la eficiencia de DAG-Rider en ciertos aspectos. Bullshark es similar pero está optimizado para aprovechar las buenas condiciones de la red cuando ocurren en la configuración parcialmente síncrona. 

Todo lo que necesitas es DAG (2021) de Idit Keidar, Lefteris Kokoris-Kogias, Oded Naor y Alexander Spiegelman.
Este es el documento que presenta el protocolo DAG-Rider. 

Narwhal y Tusk: un Mempool basado en DAG y un consenso de BFT eficiente (2022) de George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino y Alexander Spiegelman.

Bullshark: Protocolos DAG BFT hechos prácticos (2022) de Alexander Spiegelman, Neil Giridharan, Alberto Sonnino y Lefteris Kokoris-Kogias.

Cordial Miners: protocolos de consenso de pedidos basados ​​en Blocklace para cada eventualidad (2022) de Idit Keidar, Oded Naor y Ehud Shapiro.
Es un hecho divertido que en realidad no se necesita una cadena de bloques para implementar un sistema de pagos descentralizado; este último es una tarea estrictamente más fácil (ver este documento para una prueba). Antes de analizar cómo establecer un ordenamiento total en las transacciones, el artículo anterior de Cordial Miners describe primero un protocolo DAG determinista (y muy elegante) que implementa con éxito los pagos en la configuración asincrónica. 

Protocolos sin permiso 

Los protocolos sin permiso son aquellos con entrada sin permiso: cualquiera es libre de unirse al proceso de llegar a un consenso, y el conjunto de participantes puede incluso ser desconocido en cualquier momento durante la ejecución del protocolo. 

Bitcoin: un sistema de efectivo electrónico punto a punto (2008) de Satoshi Nakamoto.
Has oído hablar de este. Aquí también hay un del blog por Kartik Nayak que analiza intuitivamente la necesidad de diferentes aspectos del protocolo, como la prueba de trabajo, y cómo la sincronización de la red juega un papel en el protocolo. 

Bitcoin y criptomoneda Tecnologías (2016) de Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller y Steven Goldfeder.
Este libro de texto brinda una buena introducción a Bitcoin para aquellos que son nuevos en el espacio. También hay un asociado curso de Coursera gratis. 

En un nivel más técnico, los siguientes tres documentos analizan la seguridad y la vida de Bitcoin, utilizando supuestos de modelado ligeramente diferentes. El documento "Bitcoin Backbone" es el más famoso. La notación pesada dificulta la lectura, pero la idea básica detrás de la prueba no es tan complicada como parece inicialmente. La prueba de Dongning Guo y Ling Ren explica las ideas básicas y es más breve y sencilla. 

1. El Protocolo Backbone de Bitcoin: Análisis y Aplicaciones (2015) de Juan Garay, Aggelos Kiayias y Nikos Leonardos.
2. Análisis del Protocolo Blockchain en Redes Asíncronas (2017) de Rafael Pass, Lior Seeman y Abhi Shelat.
3. Análisis de latencia y seguridad de Bitcoin simplificado (2022) de Dongning Guo y Ling Ren.

Todo es una carrera y Nakamoto siempre gana (2020) de Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang y Ofer Zeitouni.
En este documento, los autores realizan un elegante análisis de seguridad para Bitcoin que funciona al mostrar que el ataque más obvio de carreras para construir una cadena más larga es el más efectivo. El análisis también se extiende a Ouroboros, SnowWhite y Chia (todos enumerados a continuación). 

Luego, los tres artículos siguientes describen diferentes formas de ataque contra Bitcoin y la antigua prueba de trabajo Ethereum. 

La mayoría no es suficiente: la minería de Bitcoin es vulnerable (2014) de Ittay Eyal y Emin Güun Sirer.
Este es el conocido documento de “minería egoísta”. 

Ataques de Eclipse a la red punto a punto de Bitcoin (2015) de Ethan Heilman, Alison Kendler, Aviv Zohar y Sharon Goldberg.

Ataques de Eclipse de bajos recursos en la red punto a punto de Ethereum (2018) de Yuval Marcus, Ethan Heilman y Sharon Goldberg.

FruitChains: una cadena de bloques justa (2017) de Rafael Pass y Elaine Shi.
El artículo anterior es una respuesta al tema de la minería egoísta. Los autores describen un protocolo tal que la estrategia honesta para los mineros es una forma de equilibrio aproximado. 

Prisma: deconstruyendo la cadena de bloques para acercarse a los límites físicos (2019) de Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti y Pramod Viswanath.
En Bitcoin, los bloques juegan múltiples roles en el sentido de que se usan para listar transacciones pero también para llegar a un consenso en la ordenación de bloques. En el artículo anterior, los autores deconstruyen la cadena de bloques de Nakamoto en sus funcionalidades básicas y muestran cómo construir un protocolo de prueba de trabajo con alto rendimiento y baja latencia.

Los dos documentos siguientes muestran cómo implementar protocolos de prueba de participación de la cadena más larga con garantías demostrables. 

1. Ouroboros: un protocolo de cadena de bloques de prueba de participación comprobable (2017) de Aggelos Kiayias, Alexander Russell, Bernardo David y Roman Oliynykov.
2. Blancanieves: Consenso y aplicaciones sólidamente reconfigurables para asegurar de forma comprobable la prueba de participación (2019) de Phil Daian, Rafael Pass y Elaine Shi.

Algorand: escalando acuerdos bizantinos para criptomonedas (2017) de Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos y Nickolai Zeldovich.
Este documento muestra cómo implementar un protocolo de estilo BFT clásico como un protocolo de prueba de participación. Aquí está una charla sobre Algorand de Silvio Micali.

Combinando GHOST y Casper (2020) de Vitalik Buterin, Diego Hernández, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang y Yan X Zhang.

Tres ataques contra Ethereum de prueba de participación (2022) de Caspar Schwarz-Schilling, Joachim Neu, Barnabé Monnot, Aditya Asgaonkar, Ertem Nusret Tas y David Tse.
La versión actual de Ethereum necesita más análisis. Este documento describe algunos ataques. 

La cadena de bloques de Chia Network (2019) de Bram Cohen y Krzysztof Pietrzak.
Este documento muestra cómo construir un protocolo de cadena más larga usando prueba de espacio y tiempo.

Generales bizantinos en el entorno sin permiso (2021) de Andrew Lewis-Pye y Tim Roughgarden.
En este documento, los autores desarrollan un marco para el análisis de protocolos sin permiso que permite hacer cosas como probar resultados de imposibilidad para protocolos sin permiso y delinear claramente las capacidades generales de los protocolos de prueba de trabajo y prueba de participación. . 

***

Andrew Lewis-Pye es profesor en la London School of Economics. Ha trabajado en varios campos, incluida la lógica matemática, la ciencia de redes, la genética de poblaciones y la cadena de bloques. Durante los últimos cuatro años, su investigación se ha centrado en blockchain, donde sus principales intereses son los protocolos de consenso y la tokenómica. Puedes encontrarlo en Twitter @AndrewLewisPye .

Agradecimientos: Muchas tGracias a Ling Ren, Abraham, Kartik Nayak, Valeria Nikolaenko, alexander spiegelmanny Mathieu Baudet para sugerencias útiles. 

***

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.

• Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
• Platoblockchain. Inteligencia del Metaverso Web3. Conocimiento amplificado. Accede Aquí.
• Fuente: https://a16zcrypto.com/consensus-canon/