El protocolo de consenso estelar se describió por primera vez en un artículo científico de 2015 de David Mazier. Este es un "sistema federal del acuerdo bizantino", que permite a las redes informáticas descentralizadas sin líderes llegar a un consenso efectivo sobre cualquier decisión. La red de facturación Stellar utiliza el Protocolo de Consenso Stellar (SCP) para mantener un historial de transacciones consistente que todos los miembros ven.

Los protocolos de consenso se consideran difíciles de entender. SCP es más simple que la mayoría de ellos, pero aún comparte esta reputación, en parte debido a la idea errónea de que el "voto federal", al que se dedica la primera mitad del artículo científico, es SCP. ¡Pero esto no es así! Este es solo un componente importante, que en la segunda mitad del artículo se utiliza para crear el protocolo de consenso Stellar real .

En este artículo, describimos brevemente qué es un "sistema de acuerdos", qué puede hacerlo "bizantino" y por qué hacer que el sistema bizantino sea "federal". Luego explicamos el procedimiento de votación federada descrito en el artículo de SCP, y finalmente explicamos el protocolo de SCP.

Sistemas de acuerdo

El sistema de acuerdos permite a un grupo de participantes llegar a un consenso sobre un tema, por ejemplo, qué pedir para el almuerzo.

En Interstellar hemos implementado nuestro propio sistema de organización de comidas: ordenamos lo que dice nuestro gerente de operaciones John. Este es un sistema de acuerdo simple y efectivo. Todos confiamos en John y creemos que cada día encontrará algo interesante y nutritivo.

Pero, ¿y si John abusa de nuestra confianza? Él solo puede decidir que todos deberíamos convertirnos en veganos. En una o dos semanas, probablemente lo derrocaremos y le entregaremos la autoridad a Elizabeth. Pero de repente le encantan los aguacates con anchoas y piensa que todos deberían ser así. El poder corrompe. Por lo tanto, es mejor encontrar un método más democrático: alguna forma de asegurarse de que se tengan en cuenta las diferentes preferencias, al tiempo que se garantiza un resultado oportuno y sin ambigüedades para que nadie ordene el almuerzo o cinco personas hagan diferentes pedidos, o la discusión se prolongue hasta la noche.

Parece que la solución es simple: ¡votar! Pero esta es una impresión engañosa. ¿Quién recogerá las boletas e informará los resultados? ¿Y por qué el resto debería creer lo que dice? Tal vez podamos votar primero por el líder en el que confiamos para liderar la votación, pero ¿quién liderará esta primera votación? ¿Qué pasa si no podemos acordar un líder? ¿O si estamos de acuerdo y este líder se queda atrapado en una reunión o se va a una licencia por enfermedad?

Se encuentran problemas similares en las redes informáticas distribuidas. Todos los participantes o nodos deben acordar alguna solución, por ejemplo, cuyo turno es actualizar el archivo compartido o tomar la tarea de la cola de procesamiento. En una red de criptomonedas, los nodos tienen que elegir repetidamente cómo se ve la historia completa entre varias versiones posibles que a veces entran en conflicto. Este acuerdo de red le da al receptor una garantía de que la moneda es (a) válida (no falsificada) y (b) aún no se ha gastado en otro lugar. También asegura que puede gastar monedas en el futuro porque el nuevo destinatario tendrá las mismas garantías por los mismos motivos.

Cualquier sistema coincidente en una red informática distribuida debe ser tolerante a fallas: debe dar resultados consistentes, a pesar de errores, como líneas de comunicación lentas, nodos que no responden y un orden de mensajes incorrecto. El sistema de acuerdos bizantinos es además resistente a los errores "bizantinos": nodos que proporcionan información falsa, ya sea debido a un error o en un intento deliberado de socavar el sistema u obtener alguna ventaja. La capacidad de recuperación "bizantina", la capacidad de confiar en una decisión grupal, incluso cuando algunos miembros del grupo pueden mentir o no seguir las reglas de la toma de decisiones, se llama la parábola de los generales del Imperio Bizantino que intentaron coordinar el ataque. Anthony Stevens tiene una buena descripción .

Considere al dueño de la criptomoneda Alice, que debe elegir entre comprar un delicioso helado de Bob y pagar la deuda de Carol. Tal vez Alice quiera pagar ambos a la vez, gastando fraudulentamente la misma moneda. Para hacer esto, debe convencer a la computadora de Bob de que la moneda nunca fue pagada a Carol, y convencer a la computadora de Carol de que la moneda nunca fue pagada a Bob. El sistema bizantino de convenciones hace que esto sea prácticamente imposible usando una forma de gobierno mayoritario llamada quórum . Un nodo en dicha red se niega a cambiar a una determinada versión del historial hasta que vea que un número suficiente de nodos pares, un quórum, está de acuerdo con dicha transición. Tan pronto como esto suceda, formarán un bloque electoral lo suficientemente grande como para obligar a los nodos de red restantes a estar de acuerdo con su decisión. Alice puede hacer que algunos nodos descansen en su nombre, pero si la red es lo suficientemente grande, entonces su intento será suprimido por las voces de nodos honestos.

¿Cuántos nodos se requieren para un quórum? Como mínimo, una mayoría, o mejor dicho, una mayoría calificada, para combatir errores y fraudes. Pero para calcular la mayoría, necesita saber el número total de participantes. En la oficina de Interstellar o en las elecciones de distrito, estos números son fáciles de reconocer. Pero si su grupo es una red mal definida en la que los nodos pueden entrar y salir como se desee sin coordinación con el centro, entonces necesita un sistema de acuerdo bizantino federal que pueda determinar quórumes no a partir de una lista predeterminada de nodos, sino dinámicamente, a partir de un cambio constante e inevitablemente incompleto Instantánea de nodos en un determinado momento.

Puede que no parezca posible crear un quórum en términos de un solo nodo en una red extensa, pero es posible. Tal quórum puede incluso garantizar los resultados de un voto descentralizado. El documento técnico de SCP muestra cómo hacerlo mediante un procedimiento denominado votación federada .

Para los impacientes

El resto del artículo detalla la votación federal y el protocolo de consenso estelar. Si no está interesado en los detalles, aquí hay una descripción general del proceso.

1. Los nodos realizan rondas de votación federal sobre los "nominados". Una ronda de votación federal significa:
   
   • El nodo vota por cualquier declaración, por ejemplo, "Propongo el valor de V";
     
   • El nodo escucha las voces de las fiestas hasta encontrar una que pueda "recibir";
     
   • El nodo está buscando un "quórum" para esta declaración. El quórum "confirma" al nominado.
2. Tan pronto como un nodo pueda confirmar uno o más nominados, intenta "preparar" una "boleta" a través de varias rondas de votación federal.
   
3. Tan pronto como el nodo pueda verificar la preparación de la boleta, intenta alimentarla con aún más rondas de votación federada.
   
4. Una vez que un sitio puede confirmar la confirmación de un boletín, puede "externalizar" el valor de este boletín, utilizándolo como resultado del consenso.

Estos pasos incluyen varias rondas de votación federada, que juntas forman una ronda de SCP. Examinaremos con más detalle lo que sucede en cada paso.

Voto federado

La votación federada es el proceso de determinar si una red puede acordar una propuesta. En una ronda de votación, cada nodo debe seleccionar uno de los posibles valores posibles. No puede hacer esto hasta que esté seguro de que otros nodos en la red no elegirán un resultado diferente. Para estar seguros de esto, los nodos intercambian una ráfaga de mensajes de un lado a otro para que todos confirmen que el quórum de nodos toma la misma decisión . El resto de esta sección explica los términos en esta oración y cómo funciona todo el procedimiento.

Quórums y rebanadas de quórum

Comencemos definiendo un quórum. Como discutimos anteriormente, en una red descentralizada con membresía dinámica es imposible saber de antemano el número de nodos y, por lo tanto, cuánto se necesita para la mayoría. La votación federada resuelve este problema al introducir una nueva idea para el segmento de quórum: un pequeño conjunto de nodos pares en los que el nodo confía para transmitir información de estado de votación en el resto de la red. Cada nodo define su propio segmento de quórum (del cual se convierte en miembro de hecho).

La formación de quórum comienza con un corte de quórum. Para cada nodo, se agregan los nodos de su segmento. Luego, se agregan los miembros de corte de estos nodos, y así sucesivamente. A medida que continúa, se encuentran más y más nodos que no puede agregar, porque ya están incluidos en el segmento. Cuando no hay más nodos nuevos para agregar, el proceso se detiene: formamos un quórum por "cierre transitivo" cortando el quórum del nodo inicial.


Para encontrar el quórum de este nodo ...


... agregar miembros a su segmento ...


... luego agregue miembros de segmentación a estos nodos.


Continúe hasta que no haya nodos para agregar.




No hay nodos para agregar a la izquierda. Este es un quórum.

De hecho, cada nodo puede entrar en más de un segmento. Para formar un quórum, seleccione solo uno de los sectores y agregue miembros; luego seleccione cualquier segmento para cada miembro y agregue miembros a ese segmento y así sucesivamente. Esto significa que cada nodo es miembro de muchos quórumes posibles.


Seleccione solo una porción de quórum en cada paso.






Un posible quórum. O una alternativa ...


... seleccione otras rebanadas ...




... (cuando sea posible) ...


... crea otro quórum.

¿Cómo sabe un nodo en qué sectores están los otros nodos? De la misma manera que otra información sobre otros nodos: desde las transmisiones que cada nodo transmite a la red cuando cambia su estado de votación. Cada transmisión incluye información sobre segmentos del nodo emisor. El documento técnico de SCP no especifica un mecanismo de comunicación. Las implementaciones suelen utilizar el protocolo de chismes para garantizar la transmisión de mensajes a través de la red.

Recuerde que en un sistema bizantino no federal de acuerdos, un quórum se define como la mayoría de todos los nodos. El sistema bizantino de acuerdos se desarrolló desde el punto de vista de la pregunta: ¿cuántos nodos deshonestos puede soportar el sistema? En un sistema de N nodos diseñado para sobrevivir con fallas f (trucos), el nodo debería poder avanzar al recibir una respuesta de N - f pares, ya que f de ellos puede no funcionar. Pero al haber recibido una respuesta de N - f pares, podemos suponer que todos los f pares (de los cuales el nodo no recibió una respuesta) son realmente honestos. Por lo tanto, f de N - f pares (de los cuales se recibe una respuesta) son maliciosos. Para que los nodos lleguen al mismo consenso, la mayoría de los nodos restantes deben ser honestos, es decir, necesitamos que N - f sea mayor que 2f o N> 3f. Por lo tanto, un sistema diseñado para sobrevivir a fallas tendrá un total de N = 3f + 1 nodos y un tamaño de quórum de 2f + 1. Tan pronto como la propuesta cruza el umbral del quórum, el resto de la red está convencida de que cualquier propuesta competitiva fallará. Entonces la red converge al resultado.

Pero en un sistema federal de acuerdos bizantinos, no solo no puede haber una mayoría (porque nadie conoce el tamaño general de la red), ¡sino que el concepto de mayoría es generalmente inútil! Si la membresía en el sistema está abierta, entonces alguien puede obtener la mayoría simplemente llevando a cabo el llamado ataque Sibyl: uniéndose repetidamente a la red a través de varios nodos. Entonces, ¿por qué el cierre transitivo de un segmento puede llamarse quórum y cómo puede suprimir ofertas competidoras?

Técnicamente, de ninguna manera! Imagine una red de seis nodos, donde dos triples están aislados en sectores del quórum del otro. El primer subgrupo puede tomar una decisión sobre la cual el segundo nunca escuchará, y viceversa. No hay forma de que esta red llegue a un consenso (excepto por casualidad).

Por lo tanto, SCP requiere que la red debe tener una propiedad llamada cruce de quórum para la votación federada (y para aplicar importantes teoremas de artículos). En una red con esta propiedad, dos quórums que se pueden construir siempre se superponen en al menos un nodo. Para determinar el estado de ánimo predominante de la red es tan bueno como tener la mayoría. Intuitivamente, esto significa que si un quórum está de acuerdo con la declaración X, ningún otro quórum puede estar de acuerdo con otra cosa, porque necesariamente incluirá algún nodo del primer quórum que ya haya votado por X.


Si la red tiene una intersección de quórums ...


... entonces dos quórums que puedes construir ...


... siempre se cruzan.





(Por supuesto, los nodos superpuestos pueden resultar mentirosos o bizantinos en otros aspectos. En este caso, la intersección de quórumes no ayuda a la red a ponerse de acuerdo en absoluto. Por esta razón, muchos de los resultados en el documento técnico de SCP se basan en suposiciones explícitas, como lo que queda en la red intersección de quórums incluso después de eliminar nodos defectuosos . Por simplicidad, dejamos estos supuestos implícitos en el resto del artículo).

Puede parecer irrazonable esperar que en una red de nodos independientes sea posible una intersección confiable de quórums. Pero hay dos razones por las cuales esto es así.

La primera razón es la existencia de Internet en sí. Internet es un ejemplo ideal de una red de nodos independientes con intersección de quórumes. La mayoría de los sitios en Internet se conectan solo a unos pocos sitios locales, pero estos pequeños conjuntos se superponen lo suficiente como para hacer que cada sitio sea accesible desde cualquier otro sitio en una ruta particular.

La segunda razón es específica de la red de pago Stellar (el uso más común de SCP). Cada activo en la red Stellar tiene un emisor, y las recomendaciones de Stellar requieren que cada emisor designe uno o más nodos en la red para procesar las solicitudes de reembolso. Le interesa incluir directa o indirectamente estos nodos en sectores de quórum para cada activo que le interese. Luego, los quórums para todos los nodos interesados ​​en este activo se superpondrán al menos en estos nodos de reembolso. Los nodos interesados ​​en varios activos incluirán en sus sectores de quórum todos los nodos de reembolso de los emisores respectivos, y se esforzarán por combinar todos los activos. Además, cualquier activo que no esté conectado de esa manera con otros en la red y no debería estar conectado , está destinado a que no haya cruce de quórum para esta red (por ejemplo, los bancos de la zona del dólar a veces quieren comerciar con bancos de la zona euro y los bancos de la zona del peso, por lo que están en la misma red, pero a ninguno de ellos le importa una red separada de niños que venden tarjetas de béisbol).

Por supuesto, esperar la intersección de los quórumes no es una garantía . Otros sistemas de acuerdos bizantinos deben gran parte de su complejidad a garantizar quórums. Una innovación importante de SCP es que elimina la responsabilidad de crear quórums desde el algoritmo de consenso y lo lleva al nivel de aplicación. Por lo tanto, aunque un voto federado es lo suficientemente general como para votar sobre cualquier tema, de hecho, su confiabilidad depende de manera crítica del significado más amplio de estos valores. Algunos usos hipotéticos pueden no ser tan convenientes para construir redes bien conectadas como otros.

Votación, aceptación y confirmación.

En la ronda de votación federal, el nodo opcionalmente comienza a votar por algún valor de V. Esto significa que el mensaje se envía a la red: "Soy el nodo N, mis segmentos de quórum son Q y voto por V". Cuando un nodo vota de esta manera, promete que nunca votó en contra de V y nunca lo hará.

En las transmisiones de nodos punto a punto, cada nodo ve cómo votan los demás. Tan pronto como el nodo recolecte una cantidad suficiente de tales mensajes, puede rastrear segmentos de quórum e intentar encontrar quórums. Si ve un quórum de pares que también votan por V, entonces puede proceder a aceptar V y transmitir este nuevo mensaje a la red: "Soy el nodo N, mis segmentos son quórum Q y acepto V". La aceptación ofrece una garantía más fuerte que un simple voto. Cuando un nodo vota por V, nunca puede votar por otras opciones. Pero si un nodo acepta V, ningún nodo en la Web aceptará otra opción (el Teorema 8 en el documento técnico SCP lo demuestra).

Por supuesto, es muy probable que no haya inmediatamente un quórum de nodos que estén de acuerdo con V. Otros nodos pueden votar por otros valores. Pero para el sitio hay otra manera de pasar de la simple votación a la aceptación. N puede tomar un valor diferente de W, incluso si no votó por él, e incluso si no ve quórum para él. Para decidir cambiar su voz, es suficiente ver un conjunto de nodos de bloqueo que han aceptado W. Un conjunto de bloqueo es un nodo en cada una de las secciones de los quórums de N. Como su nombre lo indica, puede bloquear cualquier otro valor. Si todos los nodos en dicho conjunto toman W, entonces (según el Teorema 8) nunca será posible formar un quórum que asuma un valor diferente, y por lo tanto también es seguro aceptar W.


Nodo N con tres rodajas de quórums.


BDF es un conjunto de bloqueo para N: incluye un nodo de cada una de las N secciones.


BE también es un conjunto de bloqueo para N porque E aparece en dos segmentos de N.

Pero un conjunto de bloqueo no es un quórum. Sería demasiado fácil engañar al nodo N para que acepte el valor deseado si es suficiente para romper un solo nodo en cada una de las rebanadas N. Por lo tanto, la adopción del valor no es el final de la votación. En cambio, N debe confirmar el valor, es decir, ver el quórum de los nodos que lo reciben. Si llega tan lejos, entonces, como lo prueba el informe técnico de SCP (en el Teorema 11), el resto de la red también terminará confirmando el mismo valor, por lo que N terminará el voto federado con un valor específico como resultado.


Voto federado.

El proceso de votación, aceptación y confirmación es una ronda completa de votación federada. El Protocolo de consenso estelar combina muchas de estas rondas para crear un sistema de consenso completo.

Protocolo de consenso estelar

Las dos características más importantes de un sistema de consenso son la seguridad y la supervivencia . El algoritmo de consenso es "seguro" si nunca puede dar resultados diferentes a diferentes participantes (una copia de la historia de Bob nunca contradecirá a Carol). "Vitalidad" significa que el algoritmo siempre producirá un resultado, es decir, no se atascará.

El procedimiento de votación federada descrito es seguro en el sentido de que si un nodo confirma el valor de V, ningún otro nodo confirma el otro valor. Pero "no confirma otro significado", esto no significa que él necesariamente confirmará algo. Los participantes pueden votar por tantos valores diferentes que nada alcanza el umbral de aceptación. Esto significa que no hay voto federal.capacidad de supervivencia .

El Protocolo de consenso estelar utiliza la votación federada de una manera que garantiza tanto la seguridad como la supervivencia. (Las garantías de seguridad y supervivencia de los SCP tienen un límite teórico. El diseño elige una garantía muy fuerte de seguridad, sacrificando un ligero debilitamiento de la supervivencia, pero dado el tiempo suficiente, es probable que se llegue a un consenso). En pocas palabras, la idea es llevar a cabo varios votos federados sobre múltiples valores hasta que uno de ellos pase por completo a través de todas las fases de votación SCP que se describen a continuación.

Los valores por los cuales SCP se esfuerza por lograr el consenso pueden ser un historial de transacciones o una orden de almuerzo, o algo más, pero es importante tener en cuenta que estos no son los valores que se aceptan o confirman. En cambio, la votación federada se lleva a cabo en reclamos de estos valores .

Las primeras rondas de votación federada se llevan a cabo en la fase de nominación, en un conjunto de solicitudes "Yo nomino V", posiblemente para muchos valores diferentes de V. El propósito de la nominación es encontrar una o más solicitudes que pasan por aceptación y confirmación.

Después de encontrar candidatos confirmados, SCP pasa a la fase de votación, donde el objetivo es encontrar una boleta electoral(es decir, un contenedor para el valor propuesto) y un quórum que puede declarar un compromiso para él (commit). Si un quórum realiza una votación, su valor se toma como consenso. Pero antes de que el nodo pueda votar por la confirmación de la boleta, primero debe confirmar la cancelación de todas las boletas con un valor de contador más bajo. Estos pasos, cancelar las boletas para encontrar una para la cual pueda confirmar el compromiso, incluyen varias rondas de votación federada en varias declaraciones de boletas.

Las siguientes secciones describen con más detalle la nominación y la votación.

Nominación

Al comienzo de la etapa de nominación, cada nodo puede seleccionar espontáneamente el valor V y votar por la declaración "Estoy nominando V". El objetivo en esta etapa es confirmar la nominación de un cierto valor por votación federal.

Quizás un número suficiente de nodos vote por declaraciones bastante diferentes, y ninguna nominación puede alcanzar el umbral de adopción. Por lo tanto, además de transmitir sus propios votos de nominados, los nodos "reflejan" las nominaciones de sus pares. Reflexión (eco) significa que si el nodo vota por la nominación de V, pero ve un mensaje del vecino votando por la nominación de W, ahora votará por la nominación de V y W. (No todos los votos de pares se reflejan durante la nominación porque esto puede conducir a una explosión de varios nominados. SCP incluye un mecanismo para regular estas voces. En resumen, hay una fórmula para determinar la "prioridad" de la fiesta desde el punto de vista del nodo, y solo se reflejan los votos de los nodos de alta prioridad. Cuanto más larga sea la extensión, menor será el umbral, por lo tanto, el nodo se expande un conjunto de fiestas cuyas voces reflejará.La fórmula de prioridad como uno de los datos de entrada incluye el número de ranura, por lo que un par de alta prioridad para una ranura puede tener baja prioridad para otra, y viceversa).

Conceptualmente, la nominación en paralelo de V y W son votos federales separados, cada uno por separado capaz de lograr aceptación o confirmación. En la práctica, los mensajes del protocolo SCP agrupan estas voces individuales.

Aunque votar por la nominación V es una promesa de nunca votar en contra de la nominación V, en el nivel de solicitud, en este caso, SCP, se define lo que significa "en contra". SCP no ve una declaración que contradiga el voto "Estoy nominando X", es decir, no hay un mensaje "Estoy en contra de nominar X", por lo que el nodo puede votar por nominar cualquier valor. Muchas de estas nominaciones no conducirán a nada, pero al final, el nodo podrá aceptar o confirmar uno o más valores. Una vez que se confirma el candidato, se convierte en candidato .


Nominando SCP usando votación federada. Puede haber muchos valores "B" empujados por pares y "reflejados" por los pares.

La nominación de candidatos puede resultar en varios candidatos confirmados. Por lo tanto, SCP requiere que la capa de aplicación proporcione algún método para combinar candidatos en un compuesto.(compuesto). El método de unión puede ser cualquier cosa. Lo principal es que si se determina este método, cada nodo unirá a los mismos candidatos. En el sistema de votación del almuerzo, "asociación" puede significar simplemente un rechazo de uno de los dos candidatos. (Pero de manera determinista: cada nodo debe elegir el mismo valor para restablecer. Por ejemplo, una selección anterior en orden alfabético). En la red de pagos Stellar, donde se vota el historial de transacciones, la combinación de los dos nominados propuestos implica combinar las transacciones que contienen y la última de sus dos marcas de tiempo.

La descripción técnica de SCP demuestra (Teorema 12) que al final de la fase de extensión, la red finalmente converge en un único compuesto. Pero hay un problema: la votación federada es un protocolo asincrónico (como SCP). En otras palabras, los nodos no están coordinados en el tiempo, sino solo de acuerdo con los mensajes que envían. Desde el punto de vista del nodo, no está claro cuándo finalizó la fase de extensión. Y aunque todos los nodos eventualmente llegarán al mismo compuesto, pueden elegir diferentes rutas a lo largo de este camino, creando diferentes candidatos compuestos a lo largo del camino, y nunca pueden decir cuál es el final.

Pero esto es normal. La nominación es solo preparación. Lo principal es limitar el número de candidatos para lograr un consenso que se produce durante el proceso de votación .

Balota

Un boletín es un par de <counter, value>, donde counter es un número entero que comienza con 1, y value es un candidato de la etapa de nominación. Puede ser el propio candidato de un nodo o un candidato vecino adoptado por ese nodo. Hablando en términos generales, durante la carrera, se hacen intentos repetidos para obligar a la red a alcanzar un consenso sobre algún candidato en una votación mediante la celebración de muchos votos federados en las solicitudes de votación. Los contadores en las papeletas registran los intentos realizados, y las papeletas con contadores más altos tienen prioridad sobre las papeletas con contadores más bajos. Si la boleta <counter, value> está atascada, comienza una nueva votación, ahora en la boleta <counter + 1, value>.

Es importante distinguir entre valores.(por ejemplo, cuál debería ser la orden para el almuerzo: pizza o ensaladas), papeletas (un par de contravalor) y declaraciones sobre las papeletas. La ronda SCP incluye varias rondas de votación federada, en particular sobre tales declaraciones:

• "Estoy listo para enviar el boletín B" y
  
• "Declaro un compromiso con el Boletín B"

Desde el punto de vista de este nodo, se alcanza un consenso cuando encuentra el Boletín B para el cual puede confirmar (es decir, encontrar un quórum que acepte) la declaración "Declaro un compromiso con el Boletín B". A partir de ahora, puede actuar de forma segura según el valor especificado en B; por ejemplo, haga este pedido para el almuerzo. Esto se llama externalizar el valor. Una vez que se ha confirmado la aceptación de la boleta, el nodo puede estar seguro de que cualquier otro nodo ha externalizado el mismo valor o lo confirmará definitivamente en el futuro.

Aunque conceptualmente muchas boletas federadas se mantienen en las solicitudes para muchas boletas diferentes, no intercambian tantos mensajes porque cada mensaje encapsula una cantidad de boletas. Por lo tanto, un mensaje promueve el estado de muchos votos federados a la vez, por ejemplo: "Acepto las comisiones de votación en el rango de <min, V> a <max, V>".

¿Qué significan los términos "preparado" y "compromiso"?

Un nodo vota para enviar una boleta cuando está convencido de que otros no van a enviar boletas con valores diferentes. Convencer de esto es el propósito de preparar la declaración. Un voto que diga "Estoy listo para enviar el boletín B" es una promesa de nunca enviar un boletín menor que B, es decir, con un contador más bajo (SCP requiere que los valores en los boletines tengan un cierto orden). El boletín <N1, V1> es menor que <N2, V2> si N1 <N2, y también si N1 = N2 y V1 <V2). Estas papeletas más pequeñas son "abortadas" durante la votación preparatoria, mientras que B se considera "preparada".

¿Por qué "Estoy listo para enviar el boletín B" significa "Prometo nunca enviar boletas con menos de B"? Porque SCP define aborto como lo opuesto a commit. Votar para la preparación de la boleta también implica votar para cancelar algunas otras boletas, y, como discutimos anteriormente, votar por una cosa es una promesa de nunca votar en contra.

Antes de transmitir el commit, el sitio primero debe encontrar el boletín, que puede confirmar como preparado. En otras palabras, tiene un voto federado sobre "Estoy listo para comprometerme con el Boletín B", tal vez para muchas boletas diferentes, hasta que encuentre uno que acepte el quórum.

¿De dónde vienen las papeletas para votar? Primero, el nodo transmite los preparativos para votar por <1, ​​C>, donde C es el candidato compuesto producido en la etapa de nominación. Sin embargo, incluso después del inicio de los preparativos para votar, la nominación puede dar lugar a la aparición de candidatos adicionales que se convertirán en nuevas papeletas. Mientras tanto, los pares pueden tener diferentes candidatos y pueden formar un conjunto de bloqueo que acepte "Estoy listo para enviar el boletín B2", lo que convencerá al nodo de que también lo acepte. Finalmente, hay un mecanismo de tiempo de espera que genera nuevas rondas de votación federada en nuevas boletas con contadores más altos si las boletas actuales están atascadas.

Tan pronto como el nodo encuentra el Boletín B, que puede confirmar como preparado, emite un nuevo mensaje, "Boletín B Comprometerse". Este voto les dice a los pares que el nodo nunca cederá B. De hecho, si B es una boleta <N, C>, entonces "Boletín de compromiso <N, C>" significa consentimiento incondicional para votar la disponibilidad de cada boleta desde <N, C> a <∞, s>. Este valor adicional ayuda a otros nodos a ponerse al día con una confirmación, si todavía están en las primeras etapas del protocolo.

En esta etapa, vale la pena enfatizar una vez más que estos son protocolos asincrónicos. El hecho de que un nodo envíe votos para una confirmación no significa que sus pares también lo hagan. Algunos de ellos aún pueden votar sobre las solicitudes en preparación para la votación, otros pueden ya haber externalizado el significado. SCP explica cómo un nodo debe procesar cada tipo de mensaje par independientemente de su fase.

Si el mensaje "Declaro un compromiso <N, C>" no puede ser aceptado o confirmado, es decir, la probabilidad de aceptación o confirmación del mensaje <N + 1, C> o <N + 2, C> - o, en cualquier caso, cualquier boletín con un valor de C, y no otro, ya que el nodo ya prometió nunca cancelar <N, C>. Para cuando el nodo difunda los votos para el compromiso, será C o nada, dependiendo de qué tan lejos llegue el consenso. Sin embargo, esto no es suficiente para que el nodo exteriorice C. Algunas fiestas bizantinas (menos de un quórum, basadas en nuestras suposiciones sobre la seguridad) pueden mentirle al nodo. La adopción y luego la confirmación de una determinada boleta (o rango de boletas) es lo que le da al nodo la confianza para finalmente externalizar C.


SCP a través de votación federada. No se muestra: en cualquier momento un temporizador puede funcionar, aumentando el contador en la boleta (y, posiblemente, produciendo un nuevo compuesto de candidatos nominados adicionales).

¡Y eso es todo! Una vez que la red ha alcanzado un consenso, está lista para hacerlo una y otra vez. En la red de facturación Stellar, esto ocurre aproximadamente cada 5 segundos: una hazaña que requiere seguridad y supervivencia, garantizada por SCP.

SCP puede lograr esto confiando en varias rondas de votación federada. La votación federada fue posible gracias al concepto de sectores de quórum: conjuntos de nodos pares en los que cada nodo decidió confiar como parte de su quórum (subjetivo). Esta configuración significa que puede llegar a un consenso incluso en una red con membresía abierta y engaño bizantino.

Lectura adicional

• El documento técnico original de SCP se puede encontrar aquí , y aquí están las especificaciones preliminares para su implementación.
  
• El autor original del protocolo SCP, David Mazier, simplifica (pero aún técnicamente) lo explica aquí .
  
• Es posible que se haya sorprendido de no encontrar los términos "minería" o "prueba de trabajo" en este artículo. SCP no utiliza estos métodos, pero algunos otros algoritmos de consenso sí. Zane Witherspoon escribió una revisión accesible de algoritmos de consenso .
  
• Una descripción paso a paso de una red simple que logra el consenso en una ronda completa de SCP.
  
• Para lectores interesados ​​en implementaciones de SCP: vea el código C ++ utilizado por la red de pago Stellar, o el código Go que escribí para una mejor comprensión de SCP.