Introducción a los algoritmos de conocimiento común

En un sistema asincrónico, se requiere replicación de estado entre hosts para garantizar que cada host pueda lograr un estado de conciencia consistente. En un sistema asincrónico, pueden ocurrir fallas entre hosts, por lo que es necesario definir protocolos tolerantes a fallas en la red asincrónica, que no es confiable de manera predeterminada, para garantizar que cada host pueda lograr un estado de conciencia segura y confiable.

*** El algoritmo de conocimiento es en realidad un conjunto de reglas que establecen una serie de condiciones para filtrar los nodos representativos. En el sistema blockchain, existen muchas soluciones de detección de este tipo, como POW, Pos, DPOS, etc. en la cadena pública o en la cadena privada que no requiere un sistema monetario, existe una demanda de confianza absoluta. La alta eficiencia de los nodos es algo que el algoritmo de mejor conocimiento de la cadena pública no puede proporcionar. Para dicha cadena de bloques, los algoritmos de mejor conocimiento de consistencia tradicional se han convertido en la primera opción, como PBFT, PAXOS, RAFT, etc.

Contenidos

I. BFT (Tecnología de tolerancia a fallos bizantinos)

II.PBFT (Algoritmo práctico de tolerancia a fallos bizantinos)

III. PAXOS

IV.Raft

V.POW (Prueba de Trabajo)

VI.POS (Prueba de Equidad)

vii. Prueba DPOS (Delegación de Equidad)

viii.Ripple

La búsqueda de fallas bizantinas es un tipo de tecnología tolerante a fallas en el campo de la informática distribuida. Byzantium supone 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. Se utiliza la tolerancia a fallas bizantinas para manejar este comportamiento inusual y cumplir con las especificaciones del problema a resolver.

Un sistema bizantino tolerante a fallos es un sistema con n nodos, en el que cada solicitud de todo el sistema satisface las siguientes condiciones:

1) Todos los nodos no bizantinos utilizan el mismo ingrese información para generar el mismo resultado;

2) Si la información de entrada es correcta, entonces todos los nodos no bizantinos deben recibir la 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, en la que la información puede perderse, codificarse y retrasarse, pero la mayoría de los protocolos asumen que la información llegará al destino en un tiempo limitado. ;

4) Los mensajes pasados ​​entre servidores pueden ser rastreados por terceros, pero no pueden alterarlos, falsificar el contenido del mensaje ni verificar la integridad del mensaje.

La tolerancia a fallos bizantinos carece de practicidad debido a su viabilidad teórica. Además, requiere mecanismos de sincronización de reloj adicionales para soportarlo, y la complejidad del algoritmo aumenta exponencialmente a medida que aumenta el número de nodos.

La tolerancia práctica a fallos bizantinos reduce la complejidad operativa del acuerdo bizantino desde un nivel exponencial a un nivel polinómico.

PBFT es un algoritmo de replicación de máquina de estados donde un servicio se modela como una máquina de estados y la máquina de estados se replica en diferentes nodos del sistema distribuido. 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. El protocolo de coherencia contiene al menos varias etapas: solicitud, asignación de números de secuencia (preparación previa) y respuesta (respuesta), y también puede incluir interacción mutua (preparación), confirmación de números de secuencia (envío) y otras etapas.

En el modelo de comunicación PBFT, cada solicitud de un cliente pasa por cinco etapas. Dado que el cliente no puede obtener ninguna información del servidor sobre el estado operativo del servidor, el servidor solo puede monitorear el maestro PBFT en busca de errores. Si el servidor no puede satisfacer la solicitud del cliente durante 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 un protocolo trifásico y transmite 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, después de recibir el mensaje PRE-PREPARACIÓN del nodo esclavo, transmite el mensaje PRE-PREPARACIÓN a otros nodos de servicio.

[2.3] En la fase de confirmación de secuencia, cada nodo verifica la solicitud y la secuencia en la vista, y luego transmite un mensaje COMMIT para ejecutar la solicitud recibida del cliente y darle una respuesta.

3) El cliente espera respuestas de diferentes nodos. Si m+1 respuestas son iguales, la respuesta es el resultado de la operación.

PBFT suele ser adecuado para cadenas privadas y cadenas de consorcios que requieren una gran coherencia. Por ejemplo, en el proyecto blockchain Hyperledger liderado por IBM, PBFT es un protocolo de conocimiento opcional. En el proyecto Fabric de Hyperledger, el módulo de conocimiento superior está diseñado como un módulo conectable y admite algoritmos de conocimiento superior como PBFT y Raft.

En algunos escenarios de aplicaciones distribuidas, se supone que no es necesario considerar las fallas bizantinas, sino que solo se deben manejar las fallas de interbloqueo generales. En este caso, sería más eficaz utilizar un protocolo como Paxos. .PAXOS es un algoritmo de consenso basado en el paso de mensajes y altamente tolerante a fallas.

Hay tres roles en PAXOS: proponente, aceptador y alumno. La interacción principal es entre el proponente y el aceptador. El proceso del algoritmo se divide en dos etapas:

La primera etapa

a) El proponente envía información de preparación a más de la mitad de los destinatarios de la red

b) En circunstancias normales, el aceptador responde con el mensaje de compromiso

La segunda etapa

a) Después de que suficientes destinatarios respondan con el mensaje de compromiso, el proponente envía el mensaje de aceptación

b) En circunstancias normales, el destinatario responde para aceptar la información

El diagrama de flujo se muestra en la figura:

PaxosStore de WeChat utiliza el protocolo PAXOS, que llama el protocolo Paxos cada minuto Miles de millones de veces. Procesamiento del orden de miles de millones de veces.

Paxos es un protocolo diseñado por Lamport para mantener la coherencia de los sistemas distribuidos.

Raft es un algoritmo de consenso más comprensible propuesto por la Universidad de Stanford, con el objetivo de reemplazar el algoritmo Paxos actualmente ampliamente utilizado.

Raft era originalmente un algoritmo compatible con **** para administrar registros replicados. Es un protocolo de coherencia fuerte compatible con **** en condiciones de falla no bizantinas. Raft logra el conocimiento de **** de la siguiente manera: primero elige un líder, quien recibe la solicitud de contabilidad del cliente, completa la operación contable, genera el bloque y lo copia a otros nodos en la contabilidad. En Raft, cada uno El nodo estará en uno de los siguientes tres estados:

(1) Seguidor: todos los nodos están en el estado de seguidor al principio. Si no recibe el mensaje del líder, se convertirá en candidato;

(2) Candidato: "sondeará" los votos de otros nodos y, si obtiene la mayoría de votos, se convertirá en líder. Este proceso se llama elección de líder;

(3) Candidato: todos los nodos comienzan desde el estado seguidor. Este proceso se llama elección de líder;

(3) Líder: todas las modificaciones al sistema pasarán primero por el líder.

El líder recibe solicitudes de modificación de la siguiente manera: Este proceso se llama replicación de registros

1) Copie el registro en todos los nodos seguidores

2) Copie el registro en todos los nodos seguidores

3) Copiar registros a todos los nodos siguientes

4) Copiar registros a todos los nodos siguientes

2) Enviar registros solo cuando la mayoría de los nodos respondan

3 ) Notificar a todos los nodos siguientes que se ha enviado el registro

4) Todos los nodos siguientes también envían el registro

5) Todo el sistema ahora está en un estado consistente

La fase Raft se divide en dos partes principales: primero el proceso de elección del líder y luego las operaciones normales, como la replicación de registros y la contabilidad.

La fase Raft se divide en dos partes principales: primero es el proceso de elección del líder y luego realiza operaciones normales basadas en el líder elegido, como replicación 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, pasará al estado candidato. En el sistema Raft:

1) Cualquier servidor puede convertirse en candidato siempre que envíe una solicitud a los seguidores de otros servidores 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 de elección, el candidato puede elegirse a sí mismo en ese momento. Siempre que se alcance una mayoría de N/2+1, el candidato aún puede convertirse en LÍDER.

3) Este candidato se convierte en el líder LÍDER y puede emitir comandos a los votantes que son SEGUIDORES, como la contabilidad.

4) La contabilidad será notificada a través de información de latido más tarde.

5) Una vez que el líder colapsa, uno de los seguidores se convierte en candidato y emite una invitación a votar.

6) Una vez que el seguidor acepta, se convierte en líder y continúa realizando tareas de orientación como la contabilidad.

(2) Replicación de registros

Los pasos contables son los siguientes:

1) Suponiendo que el líder ha sido elegido, el cliente emitirá una solicitud para agregar registros;

2) El líder requiere que los seguidores sigan sus instrucciones y agreguen el contenido del nuevo registro a sus respectivos registros

3) La mayoría de los servidores de seguidores escriben registros de transacciones después; al ingresar al libro mayor, se confirmará la adición exitosa y se enviará un mensaje de confirmación de éxito.

4) En el siguiente mensaje, el líder notificará a todos los seguidores sobre el elemento de confirmación actualizado.

Repita el proceso anterior para cada nuevo registro de transacción.

Durante este proceso, si se produce una falla en la comunicación de la red y el líder no puede acceder a la mayoría de los seguidores, el líder solo puede actualizar los servidores de los seguidores a los que se puede acceder normalmente. Si el mundo exterior requiere que el líder agregue nuevos registros de transacciones, el líder actuará como representante externo y notificará a la mayoría de los servidores seguidores. Cuando se restablezca la comunicación de la red, el líder original se convertirá en seguidor. Durante la fase de desconexión, cualquier actualización del líder anterior no se puede contar como confirmaciones y todas deben revertirse para recibir nuevas actualizaciones del nuevo líder.

En el sistema de contabilidad descentralizado, cada nodo que se une al sistema debe guardar un libro de contabilidad completo, pero cada nodo no puede guardar el libro de contabilidad al mismo tiempo, porque el entorno del nodo es diferente y la información recibida es diferente. También es diferente. Si se guarda al mismo tiempo, inevitablemente provocará inconsistencias en el libro mayor. Por lo tanto, se decide al mismo tiempo qué nodo tiene derecho a llevar la contabilidad.

En el sistema Bitcoin, se lleva a cabo una competencia informática aproximadamente cada 10 minutos. El ganador de la competencia obtendrá un derecho de contabilidad y sincronizará la nueva información del libro mayor con otros nodos.

La característica principal de los sistemas PoW es la asimetría de la informática. El trabajador debe completar una cierta cantidad de trabajo duro para producir resultados, y el verificador puede verificar fácilmente si el trabajador ha completado el trabajo correspondiente a través de los resultados. La carga de trabajo requiere concatenar una cadena de valor entero llamada nonce después de una cadena, realizar una operación hash SHA256 en la cadena concatenada y, si el resultado hash resultante (en formato hexadecimal) comienza con cero, luego verificar.

Para que cualquier nodo de la red Bitcoin genere un nuevo bloque y lo escriba en la blockchain, el problema de PoW debe resolverse fuera de la red Bitcoin. Los 3 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 del problema, el bloque determina los datos de entrada del problema y el valor de dificultad determina la cantidad de cálculo requerido para el problema.

(1) La función de prueba de trabajo es SHA256 <

Un bloque en Bitcoin consta de Consiste en un encabezado de bloque y una lista de transacciones contenidas en el bloque. El encabezado del bloque tiene una longitud fija de 80 bytes y es la cadena de entrada utilizada para la prueba de trabajo de Bitcoin.

(2) Cada nodo completo ajustará la dificultad de forma independiente y automática. Cada 2016 bloques generados, todos los nodos ajustan automáticamente la dificultad de acuerdo con una fórmula unificada. Si la velocidad de generación de bloques es superior a 10 minutos, aumente la dificultad; si es inferior a 10 minutos, disminuya la dificultad.

La fórmula se puede resumir como: nuevo valor de dificultad = valor de dificultad anterior x (tiempo invertido en el último bloque de 2016 / 20160 minutos)

La prueba de trabajo requiere un valor objetivo. Fórmula de cálculo del valor objetivo de prueba de trabajo de Bitcoin: valor objetivo = valor objetivo máximo/valor de dificultad

Entre ellos, el valor objetivo máximo es una constante: