Uno de la serie de algoritmos de consenso: algoritmo de balsa de cadena privada y algoritmo pbft de cadena de alianza.
Implementación del algoritmo pbft en Fabic
Actualmente, * * * los algoritmos de identificación se pueden dividir en tres categorías: cadena pública, cadena de alianza y cadena privada.
Cadena privada, todos los nodos son confiables
Cadena de consorcio, hay nodos punto a punto que no son de confianza.
Cadena privada: el * * * algoritmo de identificación de la cadena privada es el * * algoritmo de identificación en el sistema distribuido tradicional antes de que el concepto de blockchain se hiciera popular. Por ejemplo, el protocolo zab del cuidador del zoológico es uno de los paxos. -como algoritmos. El entorno aplicable de las cadenas privadas generalmente no considera la existencia de nodos malignos en el clúster, sino que solo considera los nodos defectuosos causados por razones del sistema o de la red.
Cadena de consorcio: en la cadena de consorcio, el proyecto representativo clásico es el proyecto Fabric bajo la organización Hyperledger Fabric versión 0.6 que utiliza el algoritmo pbft. El entorno aplicable de la cadena de alianza no solo debe considerar la existencia de nodos defectuosos en el clúster, sino que también debe considerar la existencia de nodos defectuosos en el clúster. Para la cadena de alianza, cada nodo recién agregado debe ser verificado y auditado.
Cadena pública: la cadena pública no solo debe considerar los nodos defectuosos en la red, sino también los nodos malvados, similar a la cadena de alianza. La mayor diferencia con la cadena de alianza es que los nodos de la cadena pública pueden unirse o salir libremente sin una verificación y revisión estrictas.
Los más utilizados en las cadenas públicas son el algoritmo Pow y el algoritmo POS. Estos algoritmos están directamente relacionados con los intereses de los participantes, limitan el trabajo honesto de los nodos a través de intereses y resuelven problemas bizantinos en sistemas distribuidos. El algoritmo de tolerancia a fallas bizantinas es un algoritmo de replicación de máquinas de estados. A través de múltiples rondas de mensajes que pasan entre nodos, todos los nodos honestos de la red pueden llegar a un entendimiento consistente.
El algoritmo bizantino tolerante a fallas no requiere la emisión de criptomonedas, pero solo puede usarse en cadenas privadas o cadenas de consorcio, y es necesario controlar el acceso a los nodos. No se puede utilizar en la cadena pública, porque todos los nodos de la cadena pública pueden unirse y salir a voluntad y no pueden resistir el ataque de las brujas.
El algoritmo Raft incluye tres roles: seguidor, candidato y líder. Un nodo en el clúster solo puede estar en uno de estos tres estados en un momento determinado, y estos tres roles pueden cambiar a medida que cambian el tiempo y las condiciones.
El algoritmo Raft tiene principalmente dos procesos: uno es la elección del líder y el otro es la replicación de registros. El proceso de replicación de registros se divide en dos etapas: registro de registros y envío de datos. La cantidad máxima de nodos tolerantes a fallas admitidos por el algoritmo raft es (N-1)/2, donde N es la cantidad total de nodos en el clúster.
Hay una animación en el extranjero que presenta detalladamente el algoritmo de la balsa. La dirección del enlace es:/raft/. Esta animación consta principalmente de tres partes. La primera parte presenta una versión simple del proceso de elección de líder y replicación de registros. La segunda parte presenta una versión detallada del proceso de elección de líder y replicación de registros. La tercera parte presenta el algoritmo de balsa en el caso de partición de red (cerebro dividido). Cómo restaurar la coherencia de la red.
El algoritmo pbft se utiliza principalmente para resolver el problema bizantino.
Para solucionar este problema existe un prerrequisito muy importante, es decir, que el canal debe ser fiable. Si no se puede garantizar que el canal sea confiable, entonces el problema bizantino no tiene solución. En cuanto a la fiabilidad del canal, planteará dudas para ambos ejércitos. La conclusión del problema entre los dos ejércitos es que tratar de llegar a un acuerdo mediante la comunicación a través de un enlace de comunicación poco confiable es básicamente imposible o muy difícil.
El problema de los generales bizantinos fue propuesto por primera vez por Leslie Lamport y otros dos en el artículo "El problema de los generales bizantinos" publicado en 1982. Demostró que cuando el número total de generales es mayor que 3f y el número de traidores es F o menor, los generales leales pueden llegar a un acuerdo sobre el orden, es decir, 3F+1
Primero, pensemos sobre un problema. ¿Por qué el número máximo de nodos tolerantes a fallas del algoritmo pbft es (n-1)/3, mientras que el número máximo de nodos tolerantes a fallas del algoritmo raft es (n-1)/2?
Para el algoritmo de balsa, la tolerancia a fallas del algoritmo de balsa solo admite nodos tolerantes a fallas y no nodos malvados tolerantes a fallas. ¿Qué es un nodo fallido? Significa que el nodo no responde debido a otras situaciones anormales como actividad del sistema, tiempo de inactividad o problemas de red. El nodo en esta situación es el nodo defectuoso.
¿Qué es el nodo maligno? Además de no responder deliberadamente a las solicitudes de otros nodos en el clúster, los nodos malignos también pueden enviar deliberadamente datos incorrectos o enviar datos diferentes a otros nodos diferentes, lo que hace que los nodos de todo el clúster finalmente no puedan alcanzar el objetivo. Estos nodos son nodos malignos.
El algoritmo Raft solo admite nodos tolerantes a fallos. Suponga que el número total de nodos en el clúster es n y el número de nodos fallidos es F. Según el principio de decimales que obedecen a la mayoría, los nodos normales en el clúster solo necesitan un nodo más que F nodos, es decir, f +1 nodos. La cantidad de nodos correctos será mayor que la cantidad de nodos fallidos. Si hay más, entonces el clúster puede lograr * * * conocimiento. Por lo tanto, el número máximo de nodos tolerantes a fallas admitidos por el algoritmo raft es (n-1)/2.
Para el algoritmo pbft, porque el algoritmo pbft necesita admitir nodos de falla tolerantes a fallas y nodos malignos tolerantes a fallas. Supongamos que el número de nodos en el clúster es n y el nodo en cuestión es f. El nodo en cuestión puede ser un nodo defectuoso o un nodo defectuoso, o simplemente un nodo defectuoso o simplemente un nodo defectuoso. Entonces ocurrirán las siguientes dos situaciones extremas:
En la primera situación, F nodos problemáticos son tanto nodos defectuosos como nodos malos. Luego, de acuerdo con el principio de que los decimales obedecen a la mayoría, solo los nodos normales del clúster. Requiere un nodo más que F nodos, es decir, f+1 nodos. El número de nodos confirmados será mayor que el número de nodos defectuosos, para que el clúster pueda lograr la identificación * * *. En otras palabras, el número máximo de nodos tolerantes a fallos admitidos en este caso es (n-1)/2.
En el segundo caso, el nodo defectuoso y el nodo malo son nodos diferentes. Entonces habrá F nodos problemáticos y F nodos defectuosos. Cuando se descubre que los nodos son nodos problemáticos, se excluyen del clúster, lo que deja F nodos defectuosos. Luego, de acuerdo con el principio de que los decimales obedecen a la mayoría, los nodos normales en el clúster solo necesitan tener un nodo más que el nodo F, es decir, f + 1 nodos El número de nodos confirmados será mayor que el número de defectuosos. nodos, de modo que el clúster pueda ser * conocido. Por lo tanto, el número total de nodos de todos los tipos es f+1 nodos correctos, f nodos fallidos y f nodos problemáticos, es decir, 3f+1 = n.
Combinando las dos situaciones anteriores, el número máximo de nodos tolerantes a fallas admitidos por el algoritmo pbft es (n-1)/3.
El proceso básico del algoritmo pbft incluye principalmente los siguientes cuatro pasos:
El cliente envía una solicitud al nodo maestro.
El nodo maestro transmite solicitudes a otros nodos y los nodos ejecutan el proceso de identificación de tres etapas del algoritmo pbft.
Después de procesar el proceso de tres etapas, el nodo devuelve el mensaje al cliente.
Después de que el cliente recibe el mismo mensaje del nodo f+1, significa que la identificación * * * se ha completado correctamente.
¿Por qué se recibe el mismo mensaje desde el nodo f+1, indicando que el conocimiento * * * se ha completado correctamente? Como se puede ver en la derivación de la sección anterior, en el mejor o peor caso, si el cliente recibe el mismo mensaje de f+1 nodos, significa que han llegado suficientes nodos correctos * * * reconocidos y procesados.
3. El proceso central de tres etapas del algoritmo
Las tres etapas principales del algoritmo son la etapa de preparación previa, la etapa de preparación y la etapa de envío.
Comparando el proceso, para la elección de líder, la esencia del algoritmo raft es quién puede elegir al más rápido, mientras que el algoritmo pbft se turna para ser el nodo maestro según la cantidad de personas. Con respecto al proceso de conocimiento * * * y el mecanismo de reelección del líder, para describir estos dos algoritmos de manera más vívida, comparamos el proceso de conocimiento * * * de raft y pbft con el proceso de cómo un equipo ejecuta órdenes. , entendemos balsa y La diferencia entre pbft.
Un equipo debe tener un jefe y miembros comunes y corrientes. Para el algoritmo de la balsa, el proceso de conocimiento * * * es: mientras el jefe siga vivo, nosotros (los miembros comunes del equipo) haremos lo que dice el jefe y lo implementaremos resueltamente. ¿Cuándo volverás a ser el jefe? Solo cuando el jefe muere se puede reelegir; de lo contrario, la persona que se convierta en jefe será el fantasma del jefe.
Para el algoritmo pbft, el proceso de conocimiento * * * es: cuando el jefe me envía una orden, cuando creo que hay un problema con la orden del jefe, me negaré a ejecutarla. Incluso si creo que la orden del jefe es correcta, preguntaré a otros miembros del equipo si la orden del jefe es correcta. Ejecutaré la orden sólo si la mayoría de las personas (2f+1) piensan que la orden del jefe es correcta. ¿Cuándo será reelegido el jefe? Por supuesto, si el jefe muere, tenemos que reelegir.
Si la mayoría de la gente piensa que el jefe es incompetente o tiene problemas, lo reelegiremos.
Cuatro. Conclusión
El algoritmo Raft y el algoritmo pbft son algoritmos clásicos en cadenas privadas y cadenas de consorcio. Este artículo presenta principalmente el proceso y las diferencias entre el algoritmo raft y el algoritmo pbft. Hay dos diferencias básicas entre los algoritmos Raft y pbft:
El nodo esclavo del algoritmo Raft no rechazará la solicitud del nodo maestro, mientras que el nodo esclavo del algoritmo pbft rechazará la solicitud del nodo maestro bajo ciertas circunstancias; p>
El algoritmo Raft solo puede tolerar nodos defectuosos, y el número máximo de nodos tolerantes a fallas es (n-1)/2, mientras que el algoritmo pbft puede tolerar nodos defectuosos y nodos malvados, y el número máximo de fallas -los nodos tolerantes son (n-1)/3.
El algoritmo Pbft obtiene * * * conocimiento a través de la votación, lo que puede resolver problemas, incluidas las bifurcaciones, al tiempo que mejora la eficiencia. Pero solo es aplicable a la cadena privada de la cadena de alianza, porque el tráfico entre dos nodos es O (n ^ 2) (se puede reducir mediante optimización) y generalmente no es adecuado para más de 100 nodos.
La premisa de la solución pbft es que el canal debe ser confiable, pero el problema es la escasa escalabilidad.
Parte de esto proviene de:/kojhliang/article/details/80270223.
Blockchain está diseñado para BFT.