Introducción a los algoritmos de consenso comunes
El algoritmo de consenso es en realidad un conjunto de reglas, establece un conjunto de condiciones y selecciona nodos representativos. En el sistema blockchain, existen muchos esquemas de detección, como POW, PoS, DPOS, etc. En las cadenas públicas, pero en las cadenas autorizadas o privadas que no requieren un sistema monetario, los algoritmos de consenso de la cadena pública no pueden proporcionar nodos absolutamente confiables ni requisitos eficientes. Para este tipo de blockchains, los algoritmos de consenso tradicionales se convierten en la primera opción, como PBFT, PAXOS, RAFT, etc.
Índice
BFT (Tecnología de tolerancia a fallas bizantinas)
2. PBFT (Algoritmo práctico de tolerancia a fallas bizantinas)
En tercer lugar, PAXOS
p>Cuarto, balsa
Verbo (abreviatura de verbo) power (prueba de trabajo)
6. >
7 . DPOS (certificado de derechos de oficina)
8. Ripple
La tecnología de corrección de errores bizantina es una tecnología tolerante a fallas en el campo de la informática distribuida. La hipótesis bizantina es que las computadoras y las redes se comportan de manera impredecible debido a errores de hardware, congestión o interrupciones de la red y ataques maliciosos. La tolerancia a fallos bizantinos se utiliza para hacer frente a este comportamiento anormal y cumplir con las especificaciones del problema a resolver.
Un sistema bizantino tolerante a fallas es un sistema con n nodos. Para cada solicitud, todo el sistema satisface las siguientes condiciones:
1) Todos los nodos no bizantinos usan la misma entrada. información y generar el mismo resultado;
2) Si la información de entrada es correcta, todos los nodos no bizantinos deben recibir esta información y calcular los resultados correspondientes.
Las suposiciones comúnmente utilizadas en los sistemas bizantinos incluyen:
1) El comportamiento de los nodos bizantinos puede ser arbitrario y los nodos bizantinos pueden confabularse entre sí;
2 ) Los errores entre nodos son irrelevantes;
3) Los nodos están conectados a través de una red asíncrona y los mensajes en la red pueden perderse, desordenarse y retrasarse, pero la mayoría de los protocolos asumen que los mensajes se pueden entregar dentro de un tiempo limitado Llega al destino en 4 segundos
4) La información transmitida entre servidores puede ser rastreada por un tercero, pero no puede ser manipulada ni falsificada, y se puede verificar la integridad de la información. .
La tolerancia a fallos bizantinos es teóricamente posible, pero en la práctica no es práctico y requiere soporte adicional para el mecanismo de sincronización del reloj. La complejidad del algoritmo también aumenta exponencialmente con el número de nodos.
La práctica tolerancia a fallos bizantinos reduce la complejidad computacional de la concordancia bizantina desde un nivel exponencial a un nivel polinómico.
PBFT es un algoritmo de replicación de máquinas de estados, que modela servicios como máquinas de estados, y las máquinas de estados se replican en diferentes nodos del sistema distribuido. PBFT enseña que debemos trabajar juntos para salvaguardar un país. Es necesario ejecutar tres protocolos básicos, incluido el protocolo de coherencia, el protocolo de punto de control y el protocolo de reemplazo de vista.
Protocolo de coherencia. Un protocolo de conformidad consta de al menos varias fases: solicitud, preparación previa y respuesta, y también puede incluir preparación mutua, presentación y otras fases.
En el modelo de comunicación PBFT, la solicitud de cada cliente debe pasar por cinco etapas. Debido a que el cliente no puede obtener ninguna información sobre el estado de ejecución del servidor del servidor, solo el servidor puede monitorear si ocurre un error en el nodo maestro PBFT. Si el servidor no puede completar la solicitud del cliente dentro de un período de tiempo, se activa el protocolo de reemplazo de vista.
El proceso básico de todo el protocolo es el siguiente:
1) El cliente envía una solicitud para activar la operación del servicio del nodo maestro.
2) Cuando el nodo maestro recibe la solicitud, inicia el protocolo de tres niveles para transmitir la solicitud al nodo esclavo.
[2.1] En la fase de asignación del número de secuencia, el nodo maestro asigna un número de secuencia n a la solicitud, transmite el mensaje de asignación del número de secuencia y el mensaje de solicitud del cliente m, y construye un mensaje PRE-PREPARACIÓN para cada nodo esclavo;
[2.2] En la fase de interacción, recibe el mensaje de preparación previa del nodo y transmite el mensaje de preparación a otros nodos de servicio
[2.3] Fase de confirmación del número de secuencia, verificar en la vista Después de la solicitud y la secuencia, cada nodo transmite un mensaje de confirmación, ejecuta la solicitud recibida del cliente y responde al cliente.
3) El cliente espera respuestas de diferentes nodos. Si hay m 1 respuestas idénticas, entonces la respuesta es el resultado de la operación.
PBFT generalmente es adecuado para cadenas privadas y cadenas de alianzas que requieren una gran coherencia. Por ejemplo, en el proyecto Hyperledger blockchain liderado por IBM, PBFT es un protocolo de consenso opcional. En el proyecto Fabric de Hyperledger, el módulo de consenso está diseñado como un módulo conectable y admite algoritmos de consenso como PBFT y Raft.
En algunos escenarios distribuidos, se supone que no es necesario considerar las fallas bizantinas y solo se manejan las fallas generales. En este caso, sería más eficiente adoptar un protocolo como Paxos. . PAXOS es un algoritmo de consenso basado en el paso de mensajes con alta tolerancia a fallos.
Hay tres roles en PAXOS: proponente, aceptador y alumno. El principal proceso de interacción es entre el proponente y el aceptador. El proceso del algoritmo se divide en dos etapas:
Fase 1
a) El proponente envía un mensaje de preparación a más de la mitad de los destinatarios de la red.
b) El destinatario suele responder al mensaje de promesa.
Segunda fase
a) Cuando suficientes destinatarios responden al mensaje de compromiso, el proponente envía un mensaje de aceptación.
b) En circunstancias normales, el destinatario responde al mensaje aceptado.
El diagrama de flujo se muestra en la figura:
WeChat PaxosStore utiliza el protocolo PAXOS y el proceso de llamar al protocolo Paxos es miles de millones de veces por minuto.
Paxos es un protocolo diseñado por Lamport para mantener la coherencia de los sistemas distribuidos. Pero debido a que Paxos es muy complejo y difícil de entender, desde entonces han surgido varias implementaciones y variaciones. Raft es un algoritmo de consenso más comprensible propuesto por Stanford y está destinado a reemplazar el algoritmo Paxos actualmente ampliamente utilizado.
Raft era originalmente un algoritmo de consenso para gestionar registros replicados. Es un protocolo de consenso fuerte que logra consenso bajo fallas no bizantinas. El proceso para que Raft llegue a un consenso es: primero seleccione un líder, el líder recibe la solicitud de contabilidad del cliente, completa la operación de contabilidad, genera bloques y los copia a otros nodos de contabilidad. Los líderes tienen plenos derechos de gestión y contabilidad. Por ejemplo, el líder puede decidir si acepta nuevos registros de transacciones sin considerar otros nodos contables, y el líder puede dejar de ser válido o perder contacto con otros nodos. En este momento, se reeligieron nuevos líderes.
En Raft, cada nodo estará en uno de los siguientes tres estados:
(1) seguidor: todos los nodos comienzan en el estado de seguidor. Si no se recibe ningún mensaje de líder, se convertirá en un estado candidato;
(2) Candidato: "extraerá votos" de otros nodos. Si obtiene la mayor cantidad de votos, se convertirá en el líder. Este proceso se llama elección de líder;
(3) Liderazgo: todas las modificaciones al sistema deben pasar primero por el líder. Se escribe una entrada de registro para cada modificación. El proceso después de que el líder recibe la solicitud de modificación es el siguiente: Este proceso se denomina replicación de registros.
1) Copie el registro a todos los nodos seguidores.
2) La mayoría de los nodos solo envían registros cuando responden.
3) Notificar a todos los registros de nodos seguidores que se han enviado.
4) Todos los seguidores también envían registros.
5) Todo el sistema ahora se encuentra en un estado consistente.
La etapa de la balsa se divide principalmente en dos etapas: la primera es el proceso de elección del líder, y luego se realizan las operaciones normales basadas en la elección del líder, como copia de registros, contabilidad, etc.
(1) Elección del líder
Cuando un seguidor no recibe un mensaje del líder dentro del tiempo de elección, se convertirá al estado candidato. En un sistema balsa:
1) Cualquier servidor puede convertirse en servidor candidato siempre que envíe solicitudes a otros servidores seguidores para que se elijan a sí mismo.
2) Si otros servidores están de acuerdo, emita OK. Si un seguidor cae durante este proceso y no recibe una solicitud para participar en la elección, el candidato puede hacer su propia elección en este momento. Un candidato aún puede convertirse en favorito siempre que alcance una mayoría de N/2 1 votos.
3) De esta forma, el candidato se convierte en el líder ***, que puede dar instrucciones a los votantes, es decir, a los seguidores, como la contabilidad.
4) La contabilidad será notificada mediante mensajes de latido en el futuro.
5) Una vez que el líder colapsa y uno de los seguidores se convierte en candidato, se emite una invitación a votar.
6) Con el consentimiento de sus seguidores, se convierte en líder y continúa siendo responsable de la contabilidad y otras labores de orientación.
(2) Replicación de registros
Los pasos contables son los siguientes:
1) Suponiendo que el líder ha sido seleccionado, el cliente envía una solicitud para agregar un registro;
p>
2) El líder requiere que los seguidores sigan sus instrucciones y agreguen este nuevo contenido de registro a sus respectivos registros
3) La mayoría de los servidores de seguidores escribirán; registros de transacciones Después de ingresar al libro mayor, confirme la adición exitosa y envíe un mensaje de confirmación.
4) En el siguiente mensaje, el líder notificará a todos los seguidores para que actualicen los elementos confirmados.
Repita el proceso anterior para cada nueva transacción.
Durante este proceso, si se produce una falla en la comunicación de la red de manera que el líder no puede acceder a la mayoría de los seguidores, el líder solo puede actualizar aquellos servidores de seguidores a los que puede acceder normalmente. Debido a que la mayoría de los seguidores del servidor no tienen un líder, reelegirán a un candidato como líder y luego el líder actuará como representante para tratar con el mundo exterior. Si el mundo exterior les exige que agreguen nuevos registros de transacciones, el nuevo líder notificará a la mayoría de los seguidores de acuerdo con los pasos anteriores. Cuando se restablezca la comunicación de la red, el líder original se convertirá en seguidor. Durante la etapa de pérdida de contacto, cualquier actualización del líder anterior no se puede considerar confirmada y todas deben revertirse para recibir nuevas actualizaciones del nuevo líder.
En un sistema de contabilidad descentralizado, cada nodo que se une al sistema debe mantener un libro de contabilidad completo, pero cada nodo no puede llevar cuentas al mismo tiempo, porque los nodos se encuentran en entornos diferentes y la información que reciben también es diferente. Si llevan cuentas al mismo tiempo, inevitablemente se producirán inconsistencias en el libro mayor. Por lo tanto, se determina al mismo tiempo qué nodo tiene los derechos contables.
En el sistema Bitcoin, se lleva a cabo una competencia de energía aproximadamente cada 10 minutos. El ganador de la competencia obtiene el derecho de conservar la cuenta y agregar información del libro mayor a otros nodos simultáneamente.
La principal característica de los sistemas de potencia es la asimetría computacional. El trabajador tiene que realizar un trabajo difícil para obtener un resultado, pero el verificador puede comprobar fácilmente si el trabajador ha realizado el trabajo correspondiente a través de los resultados. El requisito de esta carga de trabajo es concatenar una cadena de valor entero denominada nonce después de una cadena determinada y realizar una operación hash SHA256 en la cadena concatenada. Si el resultado hash (expresado en forma hexadecimal) comienza con varios ceros, la verificación pasa.
Si algún nodo de la red Bitcoin quiere generar un nuevo bloque y escribirlo en la blockchain, debe resolver el problema de PoW en la red Bitcoin. Los tres elementos clave son la función de prueba de trabajo, los bloques y el valor de dificultad. La función de prueba de carga de trabajo es el método de cálculo de esta pregunta, el bloque determina los datos de entrada de esta pregunta y el valor de dificultad determina la cantidad de cálculo requerido para esta pregunta.
(1) La función de prueba de carga de trabajo es
El bloque de Bitcoin consta de un encabezado de bloque y una lista de transacciones contenidas en el bloque. El encabezado del bloque de 80 bytes de longitud fija es la cadena de entrada utilizada para demostrar el trabajo de Bitcoin.
(2) El ajuste de la dificultad se produce de forma independiente y automática en cada nodo completo.
Cada 2016 bloques, todos los nodos ajustarán automáticamente la dificultad de acuerdo con una fórmula unificada. Si la velocidad de generación de bloques es superior a 10 minutos, la dificultad aumenta; si es inferior a 10 minutos, la dificultad disminuye.
La fórmula se puede resumir como: nuevo valor de dificultad = valor de dificultad anterior × (tiempo invertido en los últimos 2016 bloques/20160 minutos).
La certificación de carga de trabajo requiere un valor objetivo. La fórmula de cálculo para el valor objetivo de la prueba de trabajo de Bitcoin es: valor objetivo = valor objetivo máximo/valor de dificultad.
El valor objetivo máximo es un valor constante:
0x 000000000 ffffffffffffffffffffffffffffffffffffffffffffffffffffff
El valor objetivo es inversamente proporcional al valor de dificultad. Una consecuencia de la prueba de trabajo de Bitcoin es que el hash del bloque calculado por el minero debe ser menor que el valor objetivo.
(3)3) ¿Podrá PoW resolver el problema de los generales bizantinos?
El algoritmo de consenso de poder de Bitcoin es un acuerdo probabilístico bizantino.
Cuando la potencia informática deshonesta es inferior al 50% de la capacidad final de la red y es difícil minar al mismo tiempo (alrededor de un bloque de 10 minutos), surge el concepto de lograr coherencia en Bitcoin. La red aumentará con el área de confirmación. Crece exponencialmente con el aumento del número de bloques. Pero cuando la potencia informática deshonesta alcanza una cierta escala, incluso si no se acerca a 50, el algoritmo de consenso de Bitcoin no puede garantizar la corrección, es decir, no puede garantizar que la mayoría de los bloques sean proporcionados por nodos honestos.
El algoritmo de consenso de Bitcoin no es adecuado para cadenas privadas y cadenas de consorcios. La primera razón es que es un algoritmo de consenso final, no un algoritmo de consenso fuerte. La segunda razón es su baja eficiencia de consenso.
Conocimiento ampliado: Coherencia
La coherencia estricta solo se puede lograr en condiciones ideales donde el sistema no tiene fallas y la comunicación entre todos los nodos no lleva tiempo. En este momento, todo el sistema equivale a una máquina. Esto es imposible de lograr en la realidad.
Fuerte coherencia: cuando se completa la operación de actualización en el sistema distribuido, cualquier proceso o subproceso múltiple obtendrá el valor más reciente al acceder al sistema.
La consistencia débil significa que el sistema no garantiza que los accesos posteriores por procesos o subprocesos devolverán el último valor actualizado. Una vez que los datos se escriben correctamente, el sistema no promete leer inmediatamente el último valor escrito, ni promete específicamente con qué frecuencia leerlo. Pero después de un cierto período de tiempo, el nivel (Nivel 2) estará lo más garantizado posible. Los datos se pueden llevar a un estado consistente.
La consistencia eventual es una forma específica de consistencia débil. El sistema garantiza que eventualmente devolverá el valor de la última operación de actualización sin actualizaciones posteriores. En otras palabras, si es necesario acceder a datos actualizados después de un tiempo, esto es coherencia eventual.
En el modelo PoS de certificados de acciones, hay un término llamado antigüedad de la moneda, y cada moneda genera 1 antigüedad de la moneda cada día. Por ejemplo, si posee 65.438.000 monedas durante un total de 30 días, la antigüedad de su moneda en este momento es 3000. Si encuentra un bloqueo de PoS en este momento, la antigüedad de su moneda se borrará a 0. Cada vez que elimines 365 monedas, obtendrás un interés de 0,05 monedas del bloque (suponiendo que el interés pueda entenderse como una tasa de interés anual de 5), entonces, en este caso, el interés = 3000 * 5/365 = 0,41 monedas, lo cual es muy interesante. Tener monedas genera intereses.
Peercoin es la primera moneda en adoptar prueba de participación. El mecanismo de prueba de participación del conteo de monedas combina los conceptos de aleatorización y antigüedad de la moneda. Las monedas que no se hayan utilizado durante al menos 30 días pueden competir por el siguiente bloque. Cuanto más largo y grande sea el portamonedas, mayores serán las posibilidades de firmar una pieza. Una vez que utilice su valor monetario para firmar un bloque, la antigüedad de la moneda se restablecerá a cero, por lo que deberá esperar al menos 30 días antes de poder firmar otro bloque.
Aunque el mecanismo PoS tiene en cuenta las deficiencias de PoW, elegir según el equilibrio de capital hará que la cuenta más rica tenga mayor poder y pueda dominar los derechos contables. El surgimiento de la prueba de participación autorizada se basa en resolver las deficiencias del mecanismo PoW y el mecanismo PoS.
Bitshare es una criptomoneda que utiliza el mecanismo DPoS.
Su principio es permitir que todos los que poseen acciones voten para generar 101 representantes, que podemos entender como 101 supernodos o grupos de minería. Estos 101 supernodos tienen derechos completamente iguales entre sí. Si un representante no puede cumplir con sus funciones (no puede generar bloques cuando le toca), será eliminado de la lista y la red seleccionará nuevos supernodos para reemplazarlos.
Bitshares introduce el concepto de testigos. Los testigos pueden generar bloques y todos los que poseen Bitshares pueden votar por los testigos. Los primeros n (n generalmente se define como 101) candidatos que obtengan el total de votos de aprobación pueden ser elegidos como testigos. El número de testigos elegidos (n) debe satisfacer: al menos la mitad de los votantes creen que n ha sido completamente descentralizado.
La lista de candidatos a testigos se actualiza una vez cada período de mantenimiento (1 día). Luego, los testigos se organizan aleatoriamente y cada testigo tiene 2 segundos para generar bloques en orden. Si el servidor testigo no puede generar un bloque en un intervalo de tiempo determinado, el permiso de generación de bloque se otorgará al servidor testigo correspondiente en el siguiente intervalo de tiempo.
Bit Shares también diseñó otro movimiento para representar el movimiento. Los representantes electos tienen el poder de proponer cambios en los parámetros de la red, incluidos los costos de transacción, el tamaño de los bloques, las tarifas de los testigos y los intervalos de los bloques. Si la mayoría de los representantes está de acuerdo con los cambios propuestos, los accionistas tienen un período de revisión de dos semanas durante el cual pueden destituir a los representantes y derogar los cambios propuestos. Este diseño garantiza que los representantes técnicamente no tengan derecho a modificar directamente los parámetros, y todos los cambios en los parámetros de la red requieren la aprobación de los accionistas.
Ripple (Ripple) es un protocolo de pago de código abierto basado en Internet. En la red de Ripple, las transacciones las inician los clientes (aplicaciones) y se transmiten a toda la red a través de nodos de seguimiento o nodos de validación.
La función principal del nodo de seguimiento es publicar información de transacciones y responder a las solicitudes del libro de cuentas de los clientes. El nodo de verificación no solo contiene todas las funciones del nodo de seguimiento, sino que también puede agregar nuevos datos de instancia del libro de cuentas al libro de cuentas mediante consenso.
El consenso de Ripple se alcanza entre los nodos de verificación. Cada nodo de verificación está preconfigurado con una lista de nodos confiables llamada UNL (Lista de nodos únicos). Los nodos de la lista pueden votar sobre transacciones. Cada pocos segundos, la red Ripple pasará por el siguiente proceso de consenso:
1) Cada nodo de verificación recibirá continuamente las transacciones enviadas por la red. Después de la verificación con los datos del libro mayor local, las transacciones ilegales se descartarán directamente, mientras que las transacciones legítimas se agregarán en un conjunto de candidatos. El conjunto de candidatos a transacciones también incluye transacciones sobrantes de procesos de consenso anteriores.
2) Cada nodo de verificación envía su propio conjunto de candidatos a transacciones como recomendaciones a otros nodos de verificación.
3) Después de recibir una propuesta de otros nodos, si la propuesta no es de un nodo en UNL, el nodo de verificación ignora la propuesta; si es de un nodo en UNL, entonces la transacción en la propuesta; Se comparará con el conjunto de candidatos de transacciones locales y, si hay una transacción idéntica, la transacción obtendrá un voto. Dentro de un cierto período de tiempo, cuando una transacción recibe más de 50 votos, la transacción avanza a la siguiente ronda. En el próximo proceso de consenso no se confirmarán más de 50 transacciones.
4) El nodo de verificación envía transacciones con más de 50 votos como propuestas a otros nodos, y al mismo tiempo aumenta el umbral de votos requeridos a 60, y repite los pasos 3) y 4) hasta alcanzar el umbral. llega a 80.
5) El nodo de verificación escribe formalmente la transacción confirmada por el nodo 80UNL en los datos del libro mayor local, que se denomina último libro mayor cerrado, es decir, el último (último) estado del libro mayor. .
En el algoritmo de consenso de Ripple, las identidades de los nodos de votación se conocen de antemano. Este algoritmo de consenso sólo funciona en el caso de cadenas autorizadas. La capacidad de tolerancia a fallas bizantinas (BFT) del algoritmo de consenso de Ripple es (n-1)/5, lo que significa que 20 nodos en toda la red pueden tolerar fallas bizantinas sin afectar la consistencia correcta.
En las redes blockchain, debido a diferentes escenarios de aplicación y diferentes objetivos de diseño, diferentes sistemas blockchain utilizan diferentes algoritmos de consenso.
En términos generales, en el caso de las cadenas privadas y de consorcios, existen fuertes requisitos de coherencia y corrección. En términos generales, se debe utilizar un algoritmo de consenso con una gran coherencia. Sin embargo, en el caso de las cadenas públicas, generalmente es imposible lograr el 100% de coherencia y corrección, y generalmente se utiliza el algoritmo de consenso de coherencia final.
La elección del algoritmo de consenso está muy relacionada con el escenario de aplicación. paxos o raft se usan en entornos confiables, pbft se puede usar en alianzas autorizadas y el consenso pow, pos y ripple se puede usar en cadenas no autorizadas. El mecanismo de consenso se puede seleccionar libremente en función del nivel de confianza del oponente.