(NOTA: esta serie de consenus está HECHO, para su legibilidad, puede obtener la serie completa (con un mejor formato) en formato PDF)
La siguiente publicación es una adaptación de la descripción del protocolo PaLa del Whitepaper de ThunderCore. Se amplía con más detalles, diagramas y explicaciones.
PaLa es un protocolo de consenso de basado en suposiciones de red parcialmente sincrónicas y tolera hasta ⅓ corrupciones. A continuación, describimos una versión simplificada del protocolo llamado Pala básica para ilustrar su simplicidad y efectividad. Basic Pala es la base para comprender la versión completa de nuestro protocolo que se describe a continuación. Los detalles completos del protocolo PaLa están disponibles en el documento de investigación de PaLa.
Asumir un fijo comité de votantes. La forma en que se eligen estos nodos se describe más adelante. Cada nodo mantiene un época local contador e y una vista local de . Cada bloque contiene un número de época, una lista de transacciones y el hash de su bloque padre. El número de época de una cadena se define como el número de época del último bloque de la cadena. Cada época tiene un único único proponente que todos los nodos de la red conocen. En esta versión simplificada, cada votante es también un proponente para algunas épocas.
El consenso avanza un bloque a la vez. Los proponentes proponen un bloque si son elegibles para proponer en la época actual. Los votantes votan en bloques si se cumple un conjunto de condiciones. Una colección de ⅔ de los votos del comité en un solo bloque es un notarización para ese bloque Si hay una notarización para un bloque, el bloque es notariado. Cada bloque tiene una época que avanza monotónicamente. Si un bloque epoch e tiene un padre epoch e-1, el bloque es un bloqueo normal de lo contrario es un bloque de tiempo de espera. Un bloque es finalizado si es el padre de un bloque normal notariado. Un bloque finalizado es parte de la historia inmutable de la cadena de bloques e indica que se ha logrado un consenso.
Cada nodo mantiene su actual local Fresco. Cada vez que ve una cadena de bloques válida que es novato que su cadena actual, tiene un número de época más alto que el número de época de su cadena actual, cambian a esta cadena. Una cadena de bloques válida debe cumplir las siguientes condiciones:
Los números de época de todos los bloques deben aumentar estrictamente. Cada bloque en la cadena de bloques está notarizado
Además, cada nodo hará lo siguiente:
Aumente el contador de época local a e si
Su época local actual es más pequeña que e Y (ven una cadena certificada ante notario para la época e-1 O Ven mensajes de reloj (e) firmados válidamente al menos "miembros del comité")
Si han permanecido en la época e-1 por más de un tiempo fijo
Difundir el reloj del mensaje (e).
Si son los proponentes de la época e
Si su cadena actual termina con el bloque de la época e-1, proponga inmediatamente un nuevo bloque para la época e extendiendo su propia cadena notarial actual Si el número de la época de su cadena de bloques actual es e (debido a un tiempo de espera), espere un período fijo de tiempo (con la esperanza de recibir una cadena notariada más fresca) y proponer un nuevo bloque para la época e extender su propia cadena actual. Tenga en cuenta que es posible que un bloque notariado quede huérfano si llega después del retraso fijo.
Al recibir una propuesta de bloque para la época e del proponente de la época e, firme la propuesta y multidifundir la firma si se cumplen las siguientes condiciones:
Han visto la notarización para el bloque principal de la propuesta. El bloque es al menos tan reciente como su cadena actual al comienzo de la época e. No han firmado ningún otro bloque para la época e.
Un nodo informa un bloque como finalizado si es el padre de un bloque notarizado
Con estas reglas simples, el protocolo de consenso de PaLa logra vitalidad y consistencia. El protocolo PaLa es simple y rigurosamente probado. PaLa está diseñado en base a suposiciones de red parcialmente sincrónicas. Es inherentemente tolerante a la partición y sensible. Si alguna vez hay una partición de red, solo hay una interrupción temporal en la vida. Se reanudará el progreso cuando la partición se cure sin conflicto de estado.
En una cadena de bloques de prueba de participación del mundo real, queremos cambiar periódicamente los comités a medida que la participación cambia de manos en el sistema. El algoritmo de consenso PaLa admite cambios de comité rápidos y sin problemas. La idea básica es que el comité anterior debe finalizar un especial bloque de reconfiguración antes de que el próximo comité pueda servir para garantizar una continuidad constante.
Lo siguiente supone una comprensión madura del protocolo de consenso de PaLa, así que no se alarme si lo está leyendo por primera vez. No obstante, se publica aquí para que los lectores lo revisen como referencia en el futuro.
Hasta ahora, PaLa solo garantiza un historial de coherencia con un comité fijo. Es posible, justo antes de una reconfiguración, que el comité anterior pueda finalizar una extensión del bloque de reconfiguración. Recuerde que se necesitan 2 bloques normales notariados seguidos para que se complete el primero. Por lo tanto, los tiempos de espera permiten que se notifiquen y finalicen varios bloques seguidos de una vez cuando se cumple la condición de 2 bloques normales. Si las próximas sesiones se extienden desde el bloque de reconfiguración, la cadena finalizada extendida desde el bloque de reconfiguración se pierde y perdemos consistencia. No hay garantía de que el nuevo comité verá esta cadena finalizada extendida y, por lo tanto, no podemos exigir que se extiendan desde ella.
La implementación de ThunderCore siempre se extiende desde el bloque de reconfiguración y requiere que todos los bloques después del bloque de reconfiguración estén vacíos. Solo sirven para finalizar el bloque de reconfiguración, y no importa si se pierde su contenido.
Otra solución es tener bloques después de que el próximo comité finalice un bloque de reconfiguración.
El protocolo completo de PaLa descrito en el documento se llama Pala doblemente canalizada que apoya el tubería de propuesta característica. Esta versión permite que el consenso proceda k bloques en un momento donde k es un parámetro de conjunto de protocolos. La canalización de la propuesta permite que los bloques más nuevos se almacenen mientras los más antiguos aún se votan. Con base en pruebas empíricas, descubrimos que cuando la latencia de la red es alta en relación con los tiempos de bloqueo, un valor k más alto puede mejorar el volumen de rendimiento.
Dado que un único proponente puede proponer múltiples bloques en secuencia, se necesita un esquema de numeración de bloques más matizado. Los bloques ahora tienen una época y un número de secuencia. Los proponentes se eligen en función de la época como antes y cada nueva propuesta de la misma secuencia avanza el número de secuencia que comienza desde 0 al comienzo de cada época. Ahora se finaliza un bloque si su késimo hijo en la misma época está notarizado.
El resto del protocolo es muy similar a PaLa. Las pruebas de consistencia y vitalidad también siguen a la suite. Nos sumergiremos en los detalles de esto en una futura publicación de blog comparando PaLa y Hotstuff.
Desde el punto de vista del rendimiento, PaLa es una mejora significativa en los protocolos de consenso clásicos anteriores que requieren dos rondas de votación por bloque y mensajes O (n²). PaLa utiliza la idea de BFT canalizada donde la segunda ronda de votación en este protocolo de consenso clásico está respaldada en la primera ronda de votación para el siguiente bloque. El proponente activo utiliza firmas múltiples de BLS para recopilar votos y distribuir notarizaciones. Junto con una topología de red de múltiples concentradores y radios, PaLa puede lograr un consenso con solo mensajes O (n).
PaLa es la culminación de décadas de investigación de consenso distribuido (rechazado y financiado por el emergente paradigma de la criptomoneda). Reúne ideas audaces de muchos protocolos combinándolas elegantemente en un solo protocolo eficiente y simple. Esto debería ser evidente a partir de la breve descripción del algoritmo presentado anteriormente. El documento de investigación de PaLa proporciona pruebas simples y rigurosas de sus propiedades de seguridad basadas en suposiciones de red realistas.
Los algoritmos de consenso BFT más nuevos, como Tendermint, FBFT, Casper FFG y Hotstuff, utilizan muchas de las mismas innovaciones que PaLa. Sin embargo, ninguno de estos algoritmos es tan simple, elegante y óptimo como PaLa.
Esperamos que el consenso de BFT se equipare con PaLa de la misma manera que la Tabla Distribuida de Hash (DHT) se equipara con Kademlia.
La implementación de referencia del protocolo de consenso PaLa ya está publicada y contiene documentación exhaustiva y material educativo.