La traducción del artículo fue preparada especialmente para los estudiantes del curso
"Arquitecto de alta carga" , que comienza este mes.
Blockchain es un sistema descentralizado que consta de varias entidades que actúan según sus incentivos y la información que tienen.
Cada vez que se transmite una nueva transacción a través de la red, los nodos pueden incluir esta transacción en una copia de su libro mayor o ignorarla. Cuando la mayoría de los participantes de la red deciden aceptar un determinado estado, se llega a un consenso.
Un problema fundamental en la
computación distribuida y
los sistemas de múltiples agentes es lograr la confiabilidad general del sistema en presencia de una serie de procesos inoperativos.
A menudo, esto requiere que los procesos coordinen entre ellos algún valor que se necesitará durante el cálculo.Estos procesos se describen como consenso.
- ¿Qué sucede cuando un participante decide no seguir las reglas e intervenir en el estado de su libro mayor?
- ¿Qué sucede cuando hay muchos de esos participantes en la red, pero no la mayoría?
Para que un protocolo de consenso sea seguro, debe ser tolerante a fallas.
Para comenzar, hablaremos brevemente sobre el problema insoluble de dos generales. Luego, considere el problema de los generales bizantinos y discuta la tolerancia a fallas bizantinas en sistemas distribuidos y descentralizados. Y al final, hablemos sobre cómo todo esto se relaciona con la tecnología blockchain.
La tarea de dos generales.
Esta
tarea, publicada por primera vez en 1975 y nombrada en 1978, describe un escenario en el que dos generales atacan a un enemigo común. El primer general se considera el líder, y el segundo es el seguidor. El ejército de cada general por sí solo no es suficiente para derrotar al ejército enemigo, por lo que deben cooperar y atacar al mismo tiempo. Este escenario parece simple, pero hay una advertencia:
Para que puedan comunicarse y acordar un horario, el primer general debe enviar un mensajero a través del campamento del enemigo, debe entregar un mensaje con el momento del inicio del ataque al segundo general. Sin embargo, es probable que el mensajero sea capturado por los oponentes y el mensaje no se entregue. Esto conducirá al hecho de que el ejército del primer general irá al ataque, y el segundo permanecerá en su lugar.
Incluso si se entrega el primer mensaje, el segundo general debe confirmar (ACK (confirmar), observar la similitud con el protocolo de enlace de tres vías en
TCP ) que recibió el mensaje, por lo que envía el mensajero de vuelta, reproduciendo así el escenario anterior donde el mensajero puede ser capturado . Esto fluye en ACK infinitos, y debido a esto, los generales no pueden llegar a un acuerdo.
No hay forma de garantizar la segunda condición, es decir, que cada general confía plenamente en que el otro está de acuerdo con el plan de ataque. Ambos generales siempre ignorarán si el mensajero ha llegado a su compañero.
Se demostró que la tarea de dos generales no tiene solución.
La tarea de los generales bizantinos
Descrita en 1982 por Lamport, Shostak y Piz, la versión de este problema resultó ser lo más destacado. Ella describe el mismo escenario, donde en lugar de dos generales, más generales deberían acordar el momento del ataque. Una complicación adicional es que uno o más generales pueden ser traidores, es decir, pueden mentir sobre sus intenciones (por ejemplo, el general dice que acepta atacar a las 09:00, pero no lo hace).
El paradigma del líder-seguidor descrito en la tarea de dos generales se transforma en una instalación comandante-subordinada. Para lograr un consenso aquí, el comandante y cada subordinado deben acordar la misma solución (ataque o retirada).
Traducción de imagen:
La tarea de los generales bizantinos. El comandante general debe enviar una orden a sus subordinados n-1, de modo que:
- Todos los generales subordinados leales obedecen una orden.
- Si el comandante general es leal, entonces todos sus subordinados leales obedecen sus órdenes.
Además del segundo punto, debe señalarse un hecho interesante: si el comandante es un traidor, entonces aún se debe llegar a un consenso. Como resultado, todos los lugartenientes tienen un voto mayoritario.
El algoritmo de consenso en este caso se basa en el significado de la mayoría de las decisiones que ven los subordinados.
Teorema: para cualquier
m , el algoritmo
OM (m) llega a un consenso con más de
3 m generales y un máximo de
m traidores.
Esto significa que el algoritmo puede llegar a un consenso, mientras que 2/3 de los participantes son honestos. Si los traidores son más de 1/3, no se alcanza el consenso, los ejércitos no pueden coordinar sus ataques y el enemigo gana.
Algoritmo OM (0)
- El comandante envía su valor a cada uno de los subordinados.
- Cada subordinado usa el valor que recibe del comandante, o usa el valor RETARDO si no recibe ningún valor.
Algoritmo OM (m), m> 0
- El comandante envía con su importancia a cada uno de los subordinados.
- Para cada i, sea vi el valor que el subordinado i-ésimo recibe del comandante, o el valor RESET se usará si el subordinado no recibe ningún valor. El i-ésimo subordinado actúa como comandante en el algoritmo OM (m-1) y envía un valor a cada uno de los n-2 subordinados restantes.
- Para cada i, siempre que ji, sea vj el valor que el iésimo subordinado recibió del jésimo subordinado en el paso (2) (usando el Algoritmo OM (m-1)), o usa el valor DESCONEXIÓN si no tiene ningún significado El i-ésimo esclavo usa el valor mayoritario (v1, ..., vn-1).
Cuando m = 0 no hay traidores, cada subordinado sigue el orden. Para m> 0, cada elección final de un subordinado procede de la parte predominante de la elección de todos los subordinados.Será más claro si observa la situación desde el punto de vista del segundo subordinado: deje que C sea el Comandante, y L {i} es el i-ésimo subordinado.
OM (1): Subordinado 3 es un traidor. La situación desde el punto de vista del segundo subordinado.Pasos:
- El comandante envía v a todos los subordinados.
- L1 envía a L2 el valor de v o L3 envía a L2 el valor de x.
- L2 ← mayoría (v, v, x) == v
La decisión final se toma de la mayoría de los votos de L1, L2 y L3 y, como resultado, se llega a un consenso.
Es importante recordar que el objetivo es que la mayoría de los subordinados elijan la misma solución, en lugar de una específica.
Veamos el caso cuando el comandante es un traidor.
OM (1): El comandante es un traidor.Pasos:
- El comandante envía a L1, L2, L3 los valores de x, y, z, respectivamente;
- L1 envía el valor de x a los esclavos L2, L3 | L2 envía a L1, L3 el valor de y | L3 envía a L1, L2 el valor de z;
- L1 ← mayoría (x, y, z) | L2 ← más (x, y, z) | L3 ← mayoría (x, y, z)
Todos tienen el mismo valor, por lo que se llega a un consenso. Tenga en cuenta que incluso si los valores de x, y, z son todos diferentes, el valor
mayoritario (x, y, z) es el mismo para los tres subordinados. Si x, y, z son órdenes completamente diferentes, podemos suponer que actuarán de acuerdo con el plan predeterminado: RESET.
Para ver un enfoque práctico de un ejemplo más complejo con 7 generales y 3 traidores, le sugiero que lea este
artículo .
Tolerancia de falla bizantina
La tolerancia a fallas bizantinas es una característica que define un sistema que permite una clase de fallas que pertenece a la tarea de generales bizantinos. La falla bizantina es la clase más compleja de
tipos de falla . No implica ninguna restricción y no hace suposiciones sobre qué tipo de comportamiento puede tener un nodo (por ejemplo, un nodo puede generar datos arbitrarios, haciéndose pasar por un participante honesto).
Los errores bizantinos son los más difíciles de solucionar. La tolerancia a las fallas bizantinas era necesaria en los sistemas de motores de aviones, en las centrales nucleares y en prácticamente cualquier sistema cuyas acciones dependen de los resultados de una gran cantidad de sensores. Incluso SpaceX lo ve como un
requisito potencial para sus sistemas.
El algoritmo mencionado en la sección anterior corresponde a la tolerancia de falla bizantina hasta que el número de traidores excede un tercio de todos los generales. Existen otras opciones para facilitar esta tarea, incluido el uso de firmas digitales o la introducción de restricciones en la comunicación entre pares.
¿Cómo se relaciona todo esto con la cadena de bloques?
Blockchain son libros de contabilidad descentralizados que, por definición, no están controlados por la autoridad central. Debido a los valores almacenados en ellos, los atacantes tienen un buen incentivo económico para intentar iniciar un error. Sin embargo, la tolerancia a fallas bizantinas y, por lo tanto, la solución del problema general bizantino para la cadena de bloques son simplemente necesarias.
En ausencia de Tolerancia Bizantina de Fallos, un par puede transmitir y publicar transacciones falsas, anulando por completo la fiabilidad de la cadena de bloques. Para empeorar las cosas, no existe una autoridad central que pueda asumir la responsabilidad y reparar los daños.
Cuando se inventó
Bitcoin , un gran avance fue el uso de evidencia
de la solución probabilística del problema de los generales bizantinos. Ha sido descrito en detalle por Satoshi Nakamoto en este
correo electrónico .
Conclusión
En este artículo, examinamos algunos conceptos básicos de consenso en sistemas distribuidos.