Detalles de Dios V: cómo lograr un consenso tolerante a fallas del 99 %

Hemos estado escuchando durante mucho tiempo que es posible lograr un consenso tolerante a fallas del 50 % en redes síncronas. En una red síncrona, se garantiza que un mensaje transmitido por cualquier nodo confiable será recibido por todos los demás nodos confiables dentro de un período de tiempo conocido.

Si el atacante supera el 50%, puede realizar un "ataque del 51%", que es similar a cualquier algoritmo del mismo tipo en la cadena de bloques.

También lo hemos escuchado todo el tiempo: si desea relajar la suposición de sincronicidad y tener un algoritmo "async-safe", la tolerancia a fallas máxima alcanzable cae al 33% (PBFT, Casper FFG, etc. todos caen en este categoría).

Sin embargo, si agrega más suposiciones (específicamente, no solo necesita observadores para seguir a los usuarios que no participan activamente en el consenso pero que se preocupan por su resultado, sino que también siguen activamente el consenso, no solo descargan su resultado después de que sale), ¿Puede esto aumentar la tasa de tolerancia a fallas hasta el 99%?

De hecho, esto se sabe desde hace mucho tiempo. El famoso artículo de 1982 de Leslie Lamport sobre "Problemas generales bizantinos" contiene una descripción del algoritmo. A continuación intentaré volver a describir y expresar este algoritmo de forma simplificada.

Suponiendo que haya N nodos participando en el consenso, todos acuerdan de antemano a quién representan estos nodos (según el contexto, pueden ser elegidos por una parte de confianza o, si se requiere un mayor grado de descentralización, alguna prueba de trabajo o participación). demostrar).

Etiquetamos estos nodos como 0...N-1. Suponga también un límite D conocido en el retraso de la red y la variación del reloj. (por ejemplo, D = 8 segundos). Cada nodo tiene la capacidad de publicar valores en el momento T (por supuesto, los nodos maliciosos pueden publicar valores antes de T o después de T).

Todos los nodos esperan (N - 1)∙D segundos y ejecutan el siguiente proceso. Defina x:i como "valor x firmado por el nodo i", x:i:j como "valor x firmado por el nodo i, y x firmado con j", etc. Las propuestas publicadas en la primera fase tomarán la forma de v:i para algunos v e i, que incluye la firma del nodo que realizó la propuesta.

Si un verificador i recibe algún mensaje v:i:...:i[k], donde  i:...:i[k] es una lista de índices que han firmado los mensajes en orden (solo v ser contado como k = 0, y k = 1 para v:i), entonces los verificadores verificarán (i) por menos de T + k∙D mientras aún no hayan visto un mensaje válido que contenga; si ambas verificaciones pasan, entonces v : i:…: i[k]: seré publicado.

En T + (N - 1)∙D, el nodo deja de escuchar. En este punto, se garantiza que todos los nodos de confianza hayan "visto efectivamente" el mismo conjunto de valores.

La circulación del USDC supera los 30 000 millones de dólares estadounidenses: Jinse Finance informó que el CEO de Circle, Jeremy Allaire, tuiteó que la circulación del USDC superó los 30 000 millones de dólares estadounidenses. [2021/9/23 16:59:43]

Si la pregunta pide elegir un valor, se puede usar alguna función de "elección" para elegir un valor de los valores que ven (por ejemplo, tomar el valor con el hash más bajo). Luego, los nodos pueden llegar a un consenso sobre ese valor.

Ahora, exploremos por qué funciona este enfoque. Lo que necesitamos probar es que si un nodo honesto (efectivamente) ve un valor particular, entonces otros nodos honestos también ven ese valor (si demostramos esto, entonces sabemos que todos los nodos honestos ven el mismo conjunto de valores, así que si todos los nodos honestos ejecutan la misma función de selección, elegirán el mismo valor).

Supongamos que cualquier nodo honesto recibe un mensaje v:i:...i[k], que considera válido. Llegó antes del tiempo T + k∙D), suponiendo que x es el índice de otro nodo honesto. x es parte de i: ... o no.

En el primer caso (para este mensaje, x = i[j]), sabemos que el nodo honesto x ha emitido el mensaje, lo hizo en respuesta a su recepción antes del tiempo T + (j - 1) D Mensaje con j- 1 firma. En este momento transmiten su mensaje, entonces todos los nodos honestos deben recibir el mensaje antes del tiempo T + j∙D.

En el segundo caso, dado que los nodos honestos vieron el mensaje antes del tiempo T + k∙D, propagan el mensaje con sus propias firmas y garantizan que todos, incluido x, lo vieron antes en el tiempo T + (k + 1)∙D.

Tenga en cuenta que el algoritmo usa el acto de agregar su propia firma como una especie de "golpe" para los tiempos de espera de los mensajes. Es esta capacidad la que garantiza que si un nodo honesto ve un mensaje a tiempo, también puede garantizar que todos los demás nodos vean el mensaje a tiempo, porque la definición de "a tiempo" aumenta más que el retraso de la red por cada firma agregada. .

En el caso de que un nodo sea honesto, ¿podemos garantizar que los observadores pasivos (como los nodos participantes sin consenso que se preocupan por el resultado) también pueden ver el resultado?

Como estaba previsto, hay un problema. Supongamos que un comandante y algún subconjunto de validadores k (maliciosos) generan un mensaje v: i:...i[k] y lo transmiten a algunas víctimas antes de T + k∙D, quienes consideran el mensaje "a tiempo", pero cuando son reenviados, el mensaje solo llegará a todos los nodos honestos que hayan accedido después de T + k∙D, y todos los nodos honestos que hayan accedido lo rechazarán.

Pero podemos tapar este agujero y proponer una nueva restricción: se requiere que D sea el doble del retraso de la red más la diferencia horaria. Luego le damos al observador un tiempo de espera diferente: el observador acepta que v: i:...i[k] debe estar antes de T + (k - 0.5)∙D.

Ahora, supongamos que el observador ve un mensaje y lo acepta. Pueden transmitirlo a un nodo honesto antes de tiempo T + k∙D, y el nodo honesto publicará un mensaje firmado, que llegará a todos los demás observadores antes de T + D (k + 0.5) con Mensajes con k+1 firmas se agotará el tiempo.

Mejorar otros algoritmos de consenso

Teóricamente, el algoritmo anterior podría usarse como un algoritmo de consenso independiente, o incluso para ejecutar una cadena de bloques de prueba de participación.

El conjunto de validadores para la ronda de consenso N+1 puede decidirse en la ronda de consenso N (por ejemplo, cada ronda de consenso también puede aceptar transacciones de "depósito" y "retiro", y si se aceptan y se firman correctamente, se agregarán o eliminarán validadores entrar en la siguiente ronda).

El principal ingrediente adicional que debe agregarse es otro mecanismo para decidir qué nominadores pueden proponer bloques (por ejemplo, cada ronda puede tener un nominador designado). También se puede modificar para usarse como una cadena de bloques de prueba de trabajo, lo que permite que los nodos que participan en el consenso publiquen soluciones de prueba de trabajo a través de claves públicas mientras se "declaran" en tiempo real a través de firmas.

Sin embargo, la suposición de sincronía es muy sólida, por lo que esperamos que funcione sin la suposición de sincronía en los casos en los que no necesitamos más de un 33 % o un 50 % de tolerancia a fallas. hay una forma de hacer esto.

Supongamos que tenemos algún otro algoritmo de consenso (p. ej., PBFT, Casper FFG, PoS basado en cadena) cuya salida puede ser vista ocasionalmente por observadores en línea (llamamos a este algoritmo de consenso dependiente del umbral, y al mencionado anteriormente El algoritmo que llamamos retraso -algoritmo de consenso dependiente).

Suponiendo que el algoritmo de consenso dependiente del umbral se ejecuta continuamente, en un modo "finalizará" constantemente nuevos bloques en la cadena. Por ejemplo: cada valor final apuntará a un "padre"; si hay una secuencia de punteros a→...→B, llamamos a A un descendiente de B.

Podemos mejorar los algoritmos dependientes de la latencia en esta estructura, brindando a los observadores siempre activos acceso a un "resultado probable" en los puntos de control con aproximadamente un 95 % de tolerancia a fallas (también es posible agregando más controlador de validación y requiere un proceso que lleve más tiempo para impulsar la tolerancia a fallas al 100%).

Siempre que el tiempo alcanza un múltiplo de 4096 segundos, ejecutamos el algoritmo dependiente de la latencia, seleccionando 512 nodos aleatorios para participar en el algoritmo.

Una propuesta válida es cualquier cadena de valores válida finalizada por el algoritmo de correlación de umbral. Si un nodo ve algún valor final con k firmas antes del tiempo T + k∙D (D = 8 segundos), acepta la cadena en su conjunto de cadenas conocidas y agrega su propia firma para retransmitirla; el observador usa un umbral de T + (k - 0.5)∙D como antes.

La función "seleccionar" utilizada al final es simple:

Ignorar valores de descendientes que no sean valores finalizados que hayan sido acordados en rondas anteriores

Ignorar valor final no válido

Al elegir entre dos valores finales válidos, elija el que tenga el valor hash más bajo

Si el 5% de los validadores son honestos, entonces solo hay una probabilidad de 1 en un billón de que 512 nodos seleccionados al azar sean honestos, por lo que cuando el algoritmo anterior funcione, coordinará los nodos que lleguen a un único valor final.

Si se cumple la tolerancia a fallas del algoritmo de consenso dependiente del umbral (generalmente, el 50 % o el 67 % de los nodos son honestos), entonces el algoritmo de consenso dependiente del umbral no determinará ningún punto de control nuevo, o determinará otros nuevos que eventualmente sean compatibles con Puntos de control (por ejemplo, cada punto de control apunta al punto de control anterior como padre).

Así, los nodos que participan en un algoritmo dependiente de la latencia no se ponen de acuerdo en los valores que aceptan, que siguen formando parte de la misma cadena sin divergencia real. Una vez que la latencia vuelva a la normalidad en alguna ronda futura, el consenso dependiente de la latencia volverá a "sincronizarse".

Si los supuestos de los algoritmos de consenso dependientes del umbral y de la latencia se rompen simultáneamente (o en dos rondas consecutivas), entonces el algoritmo falla. Por ejemplo, suponga que en una ronda, el consenso dependiente del umbral finaliza Z → X → Y, y dado que la demora en el consenso no está de acuerdo entre X e Y, entonces el consenso terminará sin acuerdo. La siguiente ronda de consenso dependiente del umbral terminará cuando finalmente se determine que W no se origina en X y X no se origina en Y; en el consenso dependiente del retraso, los nodos que están de acuerdo con Y no aceptarán W, mientras que los nodos que estar de acuerdo con la voluntad de X. Sin embargo, esto es inevitable, el consenso seguro bajo asincronía es imposible.

La tolerancia a fallas es una consecuencia bien conocida de la teoría bizantina de tolerancia a fallas que, como muchos eventos imposibles, permite suposiciones de sincronización incluso cuando los observadores están fuera de línea.

Autor: Vitalik Buterin (V Dios)

Traductor | Editado por Katie | Jin Zhaoyu

Enlace original:

https://hackernoon.com/how-to-achieve-99percent-fault-tolerant-consensus-n25b31m

Tags：

Huobi