Algoritmo de consenso de Tendermint
Los algoritmos de consenso distribuido generalmente se pueden dividir en dos categorías: tolerancia a fallas bizantinas y tolerancia a fallas no bizantinas.
Los algoritmos tolerantes a fallas no bizantinos como Paxos, Raft, etc. se han utilizado ampliamente en los sistemas distribuidos actuales, pero el alcance de aplicación real de los algoritmos tolerantes a fallas bizantinos es relativamente pequeño (especialmente antes de la llegada de cadena de bloques).
Tendermint es un algoritmo bizantino tolerante a fallas. Está optimizado para el algoritmo PBFT tradicional. Solo requiere dos rondas de votación para lograr el consenso. Actualmente, el algoritmo Tendermint se usa principalmente en sistemas blockchain. El artículo presenta el mecanismo de conocimiento de Tendermint desde una perspectiva de principios.
Aquí encontrará una descripción completa del algoritmo Tendermint.
Aquí primero presentamos el proceso del algoritmo. Después de comprender el proceso del algoritmo, explicaremos la Prueba de seguridad y la Prueba de vida del algoritmo.
La siguiente imagen es el diagrama de transición de estado de tendermint.
El algoritmo incluye principalmente NewHeigh -gt; Propose -gt; Prevote -gt Precommit -gt; .
Cada uno de los estados anteriores se llama Paso. Los dos Pasos NewHeigh y Commit al principio y al final se llaman Pasos especiales, y los tres Pasos en negrita en el medio se llaman Ronda. etapa del conocimiento, y también es el principio central del algoritmo.
Cabe señalar que el envío final (Commit) de un bloque puede requerir múltiples procesos de Ronda. Esto se debe a que hay muchas razones que pueden hacer que la Ronda actual no tenga éxito (como el nodo de producción del bloque). Fuera de línea, el bloque propuesto es un bloque inválido, el número de votos Prevote o Precommit recibidos no es suficiente (2/3, etc.). Si se dan estas situaciones, la solución es pasar a la siguiente ronda o aumentar el tiempo de espera. ).
Aquí también debemos introducir un concepto importante: PoLC, que significa Prueba de cambio de bloqueo. Significa que a una altura y número de rondas específicos (altura, ronda), para un determinado bloque o. nil (bloque vacío) ) Conjunto de votación previa que excede 2/3 del punto de resumen En pocas palabras, PoLC es el conjunto de votación previa.
Hay dos tipos de nodos en Tendermint, nodos Validadores y nodos No Validadores. Como su nombre lo indica, solo los nodos Validadores participarán en la votación, mientras que los nodos ordinarios, como nodos No Validadores, no participarán. en la votación. *La votación identificada, solo ayuda a pasar el estado o enviar solicitudes de transacción a los nodos Validador.
En el estado inicial (bloque de génesis), la altura es 0. En este momento, el sistema seleccionará un Validador según el principio de Round Robin (cada Validador tiene un cierto poder de voto), y este Validador lo empaquetará. Se emite un nuevo bloque a todos los nodos. Los nodos validadores restantes votan la propuesta y finalmente llegan a un consenso.
A continuación, se explica cada etapa por etapas:
Cuando finalice la ronda anterior de Compromiso, aparecerá un nuevo nivel y es necesario ingresar a la siguiente ronda de conocimiento. En otras palabras, este es el comienzo de una nueva ronda de proceso de conocimiento. En este momento, es necesario seleccionar un Proponente. El algoritmo de selección es Round Robin, basado en su Poder de Voto (el nodo Validador seleccionado en la ronda anterior restará el Poder de Voto Total de su valor de Poder de Voto, lo que significa que el Poder de Voto del Validador en la ronda anterior cambiará en esta ronda).
Al comienzo del nodo Proponer, el proponente designado de esta ronda debe transmitir una propuesta a todos sus pares a través de chismes. Si el proponente está bloqueado en un bloque en la ronda anterior, propone directamente ese bloque y contiene una prueba de información de bloqueo.
Después de recibir la información de la propuesta, el nodo Validador ingresa a la etapa de votación previa. Al votar, si el Validador está bloqueado en el bloque anterior, seguirá votando por el bloque anterior; de lo contrario, votará por el bloque actual. Al mismo tiempo, continuará recopilando votos previos para este bloque y empaquetándolos en PoLC cuando sea su turno de proponer.
Nota:
Si tiene un Lock-Block, recibe un nuevo PoLC para otro bloque y satisface LastLockRound lt; PoLC-Round Current Round; El bloque está desbloqueado.
Si la propuesta no se recibe durante el período de tiempo de espera, o la propuesta recibida no es válida, entonces vote nulo.
No se bloqueará ningún bloque durante la fase de Prevoto.
Cuando se agota el tiempo de Prevote o se reciben más de 2/3 de los votos nulos recibidos para Prevote, se ingresa a la fase de Precommit.
Si se reciben 2/3 de los votos previos en este momento, se transmitirá un voto previo a la confirmación y, al mismo tiempo, se bloqueará en el bloque actual (liberará todos los anteriores). Un nodo sólo puede bloquear un bloque a la vez.
Si se reciben 2/3 de votos nulos, entonces se libera el bloqueo.
Cuando un nodo se bloquea en un bloque (con PoLC), establecerá LastLockRound en la Ronda actual y votará Precommit para el bloque.
Si hay un PoLC para votos nulos, desbloquee y vote Precommit por nulo; de lo contrario, mantenga el Lock-Block sin cambios y vote por nulo;
Si se reciben suficientes 2/3 de los votos (ya sea prevoto o nulo) para un determinado bloque durante el período de tiempo de espera, no se hará nada.
Finalmente, si un nodo recibe 2/3 de los votos de precompromiso, entra en la fase de compromiso. De lo contrario, continúe con la siguiente ronda de la fase de propuesta.
La fase de compromiso es una fase especial con dos condiciones paralelas que deben cumplirse:
En cualquier momento durante el proceso de consenso, si un nodo recibe más de 2/3 de los compromisos para un bloque particular, ingresa inmediatamente al paso de Confirmación si aún no lo ha hecho. Por lo tanto, hay dos formas de ingresar al paso de Confirmación para un bloque en la ronda R cuenta como prevotos y precompromisos para todas las rondas R0 donde R lt; R0. Los votos de compromiso se comunican en segundo plano a los pares vecinos, independientemente de la ronda o paso actual.
En cualquier momento durante el proceso de consenso, si un nodo está bloqueado en un bloque de la ronda R pero recibe una prueba de bloqueo para una ronda R0 donde R lt; >
La seguridad de Tendermint significa que después de alcanzar el conocimiento completo del bloque con altura H, es imposible que aparezca un nuevo bloque con altura H. En otras palabras, Tendermint garantiza que no se bifurcará y que sí. no La función principal de la bifurcación es Lock-Block.
Veamos primero la descripción de la wiki de la prueba de seguridad:
Supongamos que como máximo -1/3 del poder de voto de los validadores es bizantino si un validador confirma el bloque B en.
ronda R, es porque vio 2/3 de las confirmaciones previas en la ronda R. Esto implica que 1/3 de los nodos honestos todavía están
bloqueados en la ronda R' gt; Estos validadores bloqueados permanecerán bloqueados hasta que vean un PoLC en R' gt; R, pero esto
no sucederá porque 1/3 están bloqueados y son honestos, por lo que como máximo -2/3 están disponibles para vote por cualquier otra cosa que no sea B.
Traducción:
Suponga que hay como máximo nodos bizantinos más pequeños que 1/3 del punto de resumen. Si un nodo confirma un bloque en la ronda R, significa que el nodo recibió más de 2/3 de los votos de precompromiso para este bloque en la ronda R.
Esto también significa que más de 1/3 de los nodos honestos todavía están bloqueados en este bloque en la ronda R' (R' gt; R) (porque más de 2/3 de los votos de Precommit deben contener más de 1/3 de los votos de Precommit voto de nodos honestos). Solo se desbloqueará cuando se encuentre un PoLC para otro bloque, pero es imposible tener un PoLC para un determinado bloque en la ronda R' porque más de 1/3 de los nodos honestos ya han sido bloqueados en este bloque. es imposible tener un voto Prevoto para otro bloque mayor a 2/3
.
A continuación se proporciona un proceso de prueba más detallado, suponiendo que el bloque b con una altura de H alcanza la conciencia *** en la ronda R. Se dan las siguientes condiciones:
Es necesario demostrar que después de que x nodos se comprometan, los nodos restantes (es decir, y z) que no se comprometan en el bloque b no llegarán a un consenso en otro bloque.
En otras palabras, es necesario probar: y z - z0 lt; 2/3. Suponiendo que todos los nodos bizantinos hayan votado Precommit por b, entonces satisface: x y z0 gt;
En resumen, demuestre y z - z0 lt;
Probamos por contradicción:
Supongamos y z - z0 gt; 2/3, es decir, es posible causar bifurcación después de la r-ésima ronda, entonces:
x y z - z0 gt; 2/3 x = gt 1 - z0 gt;
Como mencionamos anteriormente, debido a que el nodo x tiene el bloque de confirmación b, entonces x y z0 gt 2/3 e y lt, significa que x z0 debe ser mayor que 1/3; . Se demuestra que y z - z0 lt; se establece 1/3. Después de la ronda R, no se puede alcanzar ningún conocimiento de otro bloque y no se puede producir una bifurcación.
La prueba de vida es relativamente simple, asumiendo que más de 1/3 de los nodos están bloqueados en diferentes bloques, las condiciones en la fase de Prevoto aseguran que el que tiene la ronda más pequeña se desbloqueará al final. , y la propuesta El tiempo de espera aumentará a medida que aumente el número de rondas.
En el proceso de prueba de seguridad, se mencionó que es posible que algunos nodos no puedan comprometerse porque no han recibido suficientes votos de precompromiso. En este momento, se puede utilizar la sincronización para mantener el estado de cada nodo. Lo más consistente posible. Los conceptos de JSet y VSet se mencionan en la wiki. Cuando un nodo se ha comprometido, puede transmitir un mensaje que lleva el VSet a otros nodos, y otros nodos verifican si la confirmación del bloque es válida. En realidad, esto es similar al enfoque de bft-raft (otro algoritmo bizantino tolerante a fallas, una variante del algoritmo Raft).