El protocolo de consenso Stellar se describió por primera vez en David Mazier en 2015. Se trata de un “sistema de acuerdo bizantino federal” que permite que las redes informáticas descentralizadas y sin líderes lleguen de manera eficiente a un consenso sobre una decisión. La red de pagos Stellar utiliza el Protocolo de consenso Stellar (SCP) para mantener un historial de transacciones coherente que sea visible para todos los participantes.
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 la "votación federada", que es el tema de la primera mitad del artículo científico, es SCP. ¡Pero eso no es cierto! Este es solo un componente importante que la segunda mitad del artículo utiliza para crear actual Protocolo de consenso estelar.
En este artículo explicaremos brevemente qué es un “sistema de acuerdos”, qué puede convertirlo en “bizantino” y por qué hacer que el sistema bizantino sea “federal”. Luego explicaremos el procedimiento de votación federada descrito en el artículo del SCP y, finalmente, explicaremos el protocolo del SCP en sí.
Sistemas de acuerdos
Un sistema de acuerdos permite que un grupo de participantes llegue a un consenso sobre un tema, como qué pedir para el almuerzo.
En Interstellar, hemos implementado nuestro propio sistema de acuerdo de comidas: ordenamos lo que dice nuestro gerente de operaciones, John. Se trata de un sistema de acuerdos sencillo y eficaz. Todos confiamos en John y creemos que encontrará algo interesante y nutritivo todos los días.
Pero ¿qué pasa si John abusa de nuestra confianza? Él solo puede decidir que todos deberíamos convertirnos en veganos. En una o dos semanas, probablemente lo derroquemos y le entreguemos el poder a Isabel. Pero de repente le encantan los aguacates con anchoas y piensa que todo el mundo debería ser así. El poder corrompe. Por lo tanto, es mejor encontrar algún método más democrático: alguna forma de garantizar que se tengan en cuenta las diferentes preferencias, garantizando al mismo tiempo un resultado oportuno e inequívoco, de modo que nadie termine pidiendo el almuerzo, o que cinco personas hagan pedidos diferentes, o que la discusión se prolonga hasta la noche.
Parecería que la solución es sencilla: ¡votar! Pero ésta es una impresión engañosa. ¿Quién recogerá las papeletas e informará los resultados? ¿Y por qué otros deberían creer lo que dice? Quizás podamos al principio votar por un líder en quien confiamos para dirigir la votación, pero que la dirigirá primero ¿votando? ¿Qué pasa si no podemos ponernos de acuerdo sobre un líder? ¿O qué pasa si llegamos a un acuerdo, pero este líder se queda atrapado en una reunión o se va de baja por enfermedad?
Problemas similares ocurren en redes informáticas distribuidas. Todos los participantes o nodos deben acordar alguna decisión, como a quién le toca actualizar un archivo compartido o eliminar una 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 brinda al destinatario la seguridad de que la moneda es (a) válida (no falsa) y (b) aún no ha sido gastada en ningún otro lugar. Esto también asegura que podrá gastar las monedas en el futuro porque el nuevo destinatario tendrá las mismas garantías por los mismos motivos.
Cualquier sistema de consenso en una red informática distribuida debe ser tolerante a fallas: debe producir resultados consistentes a pesar de errores como enlaces lentos, nodos que no responden y ordenamiento incorrecto de mensajes. bizantino El sistema de acuerdos es además resistente a errores "bizantinos": nodos que dan información falsa, ya sea por un error o en un intento deliberado de socavar el sistema o obtener alguna ventaja. La tolerancia a fallos "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 quien intentó coordinar el ataque. en Anthony Stevens.
Consideremos a Alice, propietaria de criptomonedas, que debe elegir entre comprarle un delicioso helado a Bob o pagar la deuda de Carol. Quizás Alice quiera pagarles a ambos a la vez gastando fraudulentamente la misma moneda. Para hacer esto, debe convencer a la computadora de Bob de que la moneda nunca le fue pagada a Carol, y convencer a la computadora de Carol de que la moneda nunca le fue pagada a Bob. El sistema bizantino de acuerdos hace que esto sea prácticamente imposible, utilizando una forma de gobierno mayoritario llamado quórum. Un nodo en dicha red se niega a pasar a una versión particular de la historia hasta que vea que un número suficiente de pares (un quórum) está de acuerdo con dicha transición. Una vez que esto suceda, formarán un bloque de votación lo suficientemente grande como para obligar a los nodos restantes de la red a estar de acuerdo con su decisión. Alice puede obligar a algunos nodos a mentir en su nombre, pero si la red es lo suficientemente grande, su intento se verá abrumado por los votos de los nodos honestos.
¿Cuántos nodos se requieren para lograr quórum? Como mínimo, una mayoría, o mejor dicho, una mayoría cualificada para luchar contra los errores y el fraude. Pero para contar la mayoría, es necesario conocer el número total de participantes. En la oficina de Interstellar o en las elecciones de distrito, estos números son fáciles de averiguar. Pero si su grupo es una red vagamente definida en la que los nodos pueden entrar y salir a voluntad sin la aprobación del centro, entonces necesita federal un sistema de acuerdos bizantino capaz de determinar quórums no a partir de una lista predeterminada de nodos, sino dinámicamente, a partir de una instantánea en constante cambio e inevitablemente incompleta de nodos en un momento dado.
Puede parecer imposible crear un quórum desde la perspectiva de un único nodo en una vasta red, pero es posible. Un quórum así puede incluso garantizar los resultados de una votación descentralizada. El documento técnico de SCP muestra cómo hacer esto mediante un procedimiento llamado por voto federal.
Para los impacientes
El resto del artículo describe con más detalle la votación federada y el protocolo de consenso de Stellar. Si no está interesado en los detalles, aquí tiene una descripción general del proceso.
- Los nodos llevan a cabo rondas de votación federal sobre los “nominados”. Una ronda de votación federal significa:
- El nodo vota por alguna afirmación, por ejemplo, “propongo el valor de V”;
- El nodo escucha las voces de los pares hasta que encuentra uno que pueda "recibir";
- El nodo busca un "quórum" para esta afirmación. Un quórum “confirma” al candidato.
- Una vez que un nodo puede confirmar uno o más nominados, intenta "preparar" la "boleta" mediante varias rondas de votación federada.
- Una vez que un nodo puede verificar que la boleta está lista, intenta enviarla a través de más rondas de votación federada.
- Una vez que un nodo puede confirmar la confirmación de una boleta, puede "externalizar" el valor de esa boleta usándola como resultado de consenso.
Estos pasos implican múltiples rondas de votación federada, que en conjunto forman una ronda del SCP. Echemos un vistazo más de cerca a lo que sucede en cada paso.
Voto federado
La votación federada es un procedimiento para determinar si la red puede llegar a un acuerdo sobre una propuesta. En la ronda de votación, cada nodo debe elegir uno de entre muchos valores posibles. No puede hacer esto a menos que esté seguro de que otros nodos de la red no elegirán un resultado diferente. Para asegurarse de esto, los nodos intercambian una avalancha de mensajes de un lado a otro para que todos confirmadoQue quórum nudos toma lo mismo decisión. El resto de esta sección explica los términos de esta oración y cómo ocurre todo el procedimiento.
Quórumes y porciones de quórum
Comencemos por definir un quórum. Como comentamos anteriormente, en una red descentralizada con membresía dinámica, es imposible saber de antemano el número de nodos y, por tanto, cuántos se necesitan para la mayoría. El voto federado resuelve este problema introduciendo una nueva idea corte de quórum (porción de quórum): un pequeño conjunto de pares en los que un nodo confía para comunicar información del estado de la votación al resto de la red. Cada nodo define su propio segmento de quórum (del cual se convierte en miembro de facto).
La formación del quórum comienza con una reducción del quórum. Para cada nodo, se agregan sus nodos cortados. Luego se agregan los términos del segmento. estos nodos etcétera. A medida que continúa, hay 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: hemos formado un quórum mediante “cierre transitivo” de la porción de quórum del nodo inicial.
Para encontrar quórum de un nodo determinado...
... agregar miembros de su segmento...
... luego agregamos miembros de segmento de estos nodos.
Seguimos hasta que no queden nodos por añadir.
No quedan nodos por agregar. Este es un quórum.
De hecho, cada nodo puede aparecer 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 uno de los miembros y agregue miembros lo cortar y así sucesivamente. Esto significa que cada nodo es miembro de muchos quórums posibles.
Seleccione solo una porción de quórum en cada paso.
Un posible quórum. O una alternativa...
...seleccione otras porciones...
…(cuando sea posible)…
... crea otro quórum.
¿Cómo sabe un nodo en qué sectores se encuentran otros nodos? Del mismo modo que otra información sobre otros nodos: de las transmisiones que cada nodo emite a la red cuando cambia su estado de votación. Cada transmisión incluye información sobre los sectores del nodo emisor. El documento técnico de SCP no especifica un mecanismo de comunicación. Las implementaciones suelen utilizar para garantizar la difusión de mensajes en toda la red.
Recordemos que en el sistema bizantino de acuerdos no federal, el quórum se define como la mayoría de todos los nodos. El sistema de acuerdos bizantino está diseñado desde el punto de vista de la pregunta: ¿cuántos nodos deshonestos puede tolerar el sistema? En un sistema de N nodos diseñado para sobrevivir f fallas, un nodo debería poder progresar recibiendo retroalimentación de N-f pares, ya que f de ellos pueden estar inactivos. Pero habiendo 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 recibió la 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, normalmente un sistema diseñado para sobrevivir f fallas tendrá un total de N=3f+1 nodos y un tamaño de quórum de 2f+1. Una vez que una propuesta supera el umbral de quórum, el resto de la red está convencida de que cualquier propuesta competidora fracasará. Así es como la red converge al resultado.
Pero en un sistema de acuerdos federal bizantino, no sólo no puede haber una mayoría (porque nadie conoce el tamaño total de la red), sino que el concepto de mayoría es completamente inútil. Si la membresía en el sistema es abierta, entonces alguien puede obtener la mayoría simplemente realizando el llamado ataque Sybil: uniéndose repetidamente a la red a través de múltiples nodos. Entonces, ¿por qué se puede llamar cierre de corte transitivo? quórum¿Y cómo puede suprimir propuestas competidoras?
¡Técnicamente, de ninguna manera! Imagine una red de seis nodos, donde dos tripletes están aislados en los sectores de quórum del otro. El primer subgrupo puede tomar una decisión de la que el segundo nunca se enterará, y viceversa. No hay forma de que esta red llegue a un consenso (excepto por casualidad).
Por lo tanto, SCP requiere que para la votación federada (y para que se apliquen los importantes teoremas del documento), la red debe tener una propiedad llamada intersección de quórumes. En una red con esta propiedad, dos quórums cualesquiera que se puedan construir siempre se superponen en al menos un nodo. Para determinar el sentimiento predominante en la red, esto es tan bueno como tener una mayoría. Intuitivamente, esto significa que si algún quórum acepta la declaración X, ningún otro quórum podrá aceptar otra cosa, porque necesariamente incluirá algún nodo del primer quórum que ya votó por X.
Si hay una intersección de quórumes en la red...
...entonces dos quórums cualesquiera que puedas crear...
...siempre se cruzarán.
(Por supuesto, los nodos superpuestos pueden resultar bizantinos o malos. En este caso, la intersección del quórum no ayuda en absoluto a que la red llegue a un acuerdo. 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 el cruce del quórum de la red. incluso después de eliminar los nodos defectuosos. Para simplificar, dejemos estas suposiciones implícito en el resto del artículo).
Puede parecer poco razonable esperar que sea posible un cruce de quórum confiable en una red de nodos independientes. Pero hay dos razones por las que esto es así.
La primera razón es la existencia de Internet. Internet es un ejemplo perfecto de una red de nodos independientes con quórums que se cruzan. La mayoría de los nodos en Internet se conectan sólo a unos pocos nodos locales, pero estos pequeños conjuntos se superponen lo suficiente como para que se pueda llegar a cada nodo desde todos los demás nodos a lo largo de alguna ruta.
La segunda razón es específica de la red de pagos Stellar (el uso más común de SCP). Cada activo en la red Stellar tiene un emisor, y las pautas de Stellar requieren que cada emisor designe uno o más nodos en la red para procesar las solicitudes de canje. Le conviene incluir directa o indirectamente estos nodos en sectores de quórum para cada activo que le interese. Los quórums para todos los nodos interesados en un activo determinado se superpondrán al menos en esos nodos de canje. Los nodos interesados en múltiples activos incluirán todos los nodos de canje de los respectivos emisores en sus porciones de quórum y buscarán agrupar todos los activos. Además, cualquier activo que no esté vinculado de esta manera a otros en la red, y no debe estar conectado - esto está diseñado para que no haya superposición 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 del euro y bancos de la zona del peso, por lo que están en la misma red, pero ninguno de ellos se preocupan por la red separada de niños que venden tarjetas de béisbol).
Por supuesto, ожидание el cruce de quórum no es garantizar. Otros sistemas de acuerdos bizantinos deben gran parte de su complejidad a la garantía de quórum. Una innovación importante de SCP es que elimina la responsabilidad de crear quórums del propio algoritmo de consenso y lo lleva al nivel de aplicación. Por lo tanto, aunque el voto federado es lo suficientemente general como para votar sobre cualquier tema, su confiabilidad en realidad depende críticamente del significado más amplio de estos significados. Algunos usos hipotéticos pueden no ser tan propicios como otros para crear redes bien conectadas.
Votación, aceptación y confirmación
En una ronda de votación federada, un nodo opcionalmente comienza a votar por algún valor V. Esto significa transmitir un mensaje a la red: "Soy el nodo N, mis porciones de quórum son Q y estoy votando por V". Cuando un nodo vota de esta manera, promete que nunca ha votado en contra de V y que nunca lo hará.
En las transmisiones entre pares, cada nodo ve cómo votan los demás. Una vez que un nodo ha recopilado suficientes mensajes de este tipo, puede realizar un seguimiento de los sectores del quórum e intentar encontrar quórums. Si ve un quórum de pares que también votan por V, puede proceder a adopción V y transmite este nuevo mensaje a la red: "Soy el nodo N, mis porciones de quórum son Q y acepto V". La aceptación proporciona una garantía más fuerte que la simple votación. Cuando un nodo vota por V, nunca podrá votar por otras opciones. Pero si un nodo acepta V, ningún nodo de la Red aceptará jamás la otra opción (el Teorema 8 en el documento técnico de SCP lo demuestra).
Por supuesto, existe una alta probabilidad de que no haya inmediatamente un quórum de nodos que estén de acuerdo con V. Otros nodos pueden votar por otros valores. Pero hay otra manera de que un nodo pase de la simple votación a la aceptación. N puede aceptar un valor diferente para W, incluso si no votó a favor, e incluso si no ve quórum para ello. Para decidir cambiar su voto, sólo tiene que ver conjunto de bloqueo nodos que han aceptado W. Un conjunto de bloqueo es un nodo de cada uno de los sectores de quórum N. Como sugiere el nombre, puede para bloquear cualquier otro significado. Si todos los nodos en dicho conjunto aceptan W, entonces (según el Teorema 8) nunca será posible formar un quórum que tome un valor diferente y, por lo tanto, también es seguro que N acepte W.
Nodo N con tres sectores de quórum.
BDF es un conjunto de bloqueo para N: incluye un nodo de cada una de las porciones de N.
BE también es un conjunto de bloqueo para N porque E aparece en dos porciones de N.
Pero el 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 fuera suficiente piratear solo un nodo en cada una de las porciones de N. Por lo tanto, aceptar el valor no es el final de la votación. En cambio, N debe confirmar el valor, es decir, ver que un quórum de nodos lo acepte. Si llega tan lejos, entonces, como lo demuestra el documento técnico de SCP (en el Teorema 11), el resto de la red eventualmente también confirmará el mismo valor, por lo que N finalizará la votación federada con un cierto valor como resultado.
Voto federado.
El proceso de votación, aceptación y confirmación constituye una ronda completa de votación federada. El protocolo de consenso de Stellar combina muchas de estas rondas para crear un sistema de consenso completo.
Protocolo de consenso estelar
Las dos propiedades más importantes de un sistema de consenso son: seguridad и supervivencia. Un algoritmo de consenso es "seguro" si nunca puede dar resultados diferentes a diferentes participantes (la copia de la historia de Bob nunca contradecirá a Carol). "Habitabilidad" significa que el algoritmo siempre producirá un resultado, es decir, no se atascará.
Procedimiento de votación federal descrito a salvo en el sentido de que si un nodo confirma el valor de V, ningún otro nodo confirmará el otro valor. Pero “no confirmará otro significado” no significa que necesariamente confirmará algo. Los participantes pueden votar sobre tantos valores diferentes que nada alcanzará el umbral de aceptación. Esto significa que en la votación federal no hay supervivencia.
El protocolo de consenso de Stellar utiliza la votación federada de una manera que garantiza tanto la seguridad como la supervivencia. (Las garantías de seguridad y supervivencia de SCP tienen un límite teórico. El diseño elige una garantía de seguridad muy fuerte, sacrificando una pequeña mitigación de la supervivencia, pero dado el tiempo suficiente, es muy probable que se alcance un consenso). En pocas palabras, la idea es tener múltiples votos federados sobre múltiples valores hasta que uno de ellos supere todas las fases de votación del SCP que se describen a continuación.
Los valores sobre los cuales SCP busca consenso podrían ser el historial de transacciones o un pedido de almuerzo o cualquier otra cosa, pero es importante tener en cuenta que estos no son los valores que se aceptan o confirman. En cambio, la votación federal ocurre de acuerdo con declaraciones sobre estos valores.
Las primeras rondas de votación federal tendrán lugar el etapa de nominación (fase de nominación), sobre un conjunto de afirmaciones como “Yo nomino a V”, quizás para muchos valores diferentes de V. El propósito de la nominación es encontrar una o más afirmaciones que pasen por la aceptación y la confirmación.
Después de encontrar candidatos verificables, SCP pasa a la fase de votación, donde el objetivo es encontrar un candidato determinado. бюллетень (es decir, un contenedor para el valor propuesto) y un quórum que puede declarar comprometerse por ello (comprometerse). Si en una votación hay quórum, su valor se acepta como consenso. Pero antes de que un nodo pueda votar sobre un compromiso de votación, primero debe confirmar cancelación todas las papeletas con un valor de contador inferior. Estos pasos (cancelar boletas para encontrar una que pueda comprometerse) implican múltiples rondas de votación federada sobre múltiples reclamos de boletas.
Las siguientes secciones describen la nominación y la votación con más detalle.
Nominación
Al comienzo de la fase de nominación, cada nodo puede elegir espontáneamente un valor para V y votar por la afirmación "Yo nomino a V". El objetivo en esta etapa es confirmar la nominación de algún valor mediante una votación federada.
Quizás suficientes nodos voten sobre propuestas suficientemente diferentes como para que ninguna nominación pueda alcanzar el umbral de aceptación. Por lo tanto, además de transmitir sus propios votos de nominación, los nodos “reflejan” las nominaciones de sus pares. Eco significa que si un nodo vota por la nominación V, pero ve un mensaje de un vecino votando por la nominación W, ahora votará tanto por V como por W. (No todos los votos de los pares se repiten durante la nominación porque esto puede conducir a una explosión de diferentes nominados. SCP incluye un mecanismo para regular estos votos. En resumen, hay una fórmula para determinar la "prioridad" de un par desde el punto de vista de un nodo, y sólo se reflejan los votos de los nodos de alta prioridad. Cuanto más larga sea la nominación toma, menor es el umbral, por lo que el nodo expande el conjunto de pares cuyos votos reflejará. La fórmula de prioridad incluye el número de ranura como una de sus entradas, por lo que un par de alta prioridad para una ranura puede ser un par de baja prioridad para otro y viceversa).
Conceptualmente, la nominación es paralela, tanto V como W son votos federales separados, cada uno individualmente capaz de lograr aceptación o confirmación. En la práctica, los mensajes del protocolo SCP agrupan estos votos individuales.
Aunque votar por la nominación de V es una promesa de nunca votar en contra de la nominación de V, es en el nivel de solicitud - en este caso SCP - donde se determina qué significa "en contra". SCP no ve una declaración que contradiga el voto "Yo nomino a X", es decir, no hay ningún mensaje de "Estoy en contra de nominar a X", por lo que el nodo puede votar para nominar cualquier valor. Muchas de estas nominaciones no llegarán a ninguna parte, pero eventualmente el nodo podrá aceptar o confirmar uno o más valores. Una vez confirmado el nominado, éste se convierte en un candidato.
Nominación del SCP mediante votación federada. Puede haber muchos valores "B" propuestos por sus pares y "reflejados" por el nodo.
Las nominaciones pueden resultar en múltiples candidatos confirmados. Por lo tanto, SCP requiere que la capa de aplicación proporcione algún método para combinar los candidatos en uno. compuesto (compuesto). El método de unión puede ser cualquier cosa. Lo principal es que si este método es determinista, cada nodo combinará los mismos candidatos. En un sistema de votación durante el almuerzo, la "unificación" puede significar simplemente rechazar a uno de dos candidatos. (Pero de forma determinista: cada nodo debe seleccionar el mismo valor para restablecer. Por ejemplo, la selección anterior en orden alfabético). En la red de pagos Stellar, donde se vota el historial de transacciones, fusionar dos nominados propuestos implica fusionar las transacciones que contienen y la última de sus dos marcas de tiempo.
El documento técnico 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 por el tiempo, sino únicamente por los mensajes que envían. Desde el punto de vista del nodo, no está claro cuándo terminó fase de extensión. Y aunque todos los nodos eventualmente llegarán al mismo compuesto, pueden tomar diferentes rutas a lo largo del camino, creando diferentes candidatos compuestos a lo largo del camino, y nunca podrán decir cuál es el final.
Pero es normal. La nominación es sólo una preparación. Lo principal es limitar el número de candidatos para lograr el consenso, lo que ocurre en el proceso. corriendo (votación).
Correr
El boletín es una pareja. , donde contador es un número entero que comienza en 1 y valor es un candidato de la etapa de nominación. Puede ser el candidato propio de un nodo o el candidato de un nodo vecino aceptado por ese nodo. En términos generales, una votación implica intentos repetidos de obligar a la red a llegar a un consenso sobre algún candidato en alguna votación mediante la celebración potencialmente de muchos votos federados en las declaraciones electorales. Los contadores de las papeletas realizan un seguimiento de los intentos realizados y las papeletas con recuentos más altos tienen prioridad sobre las papeletas con recuentos más bajos. Si el boletín se atasca, comienza una nueva votación, ahora en la boleta .
Es importante distinguir significado (por ejemplo, cuál debería ser el pedido del almuerzo: pizza o ensaladas), boletines (par de contravalor) y declaraciones sobre las papeletas. La ronda del SCP incluye varias rondas de votación federal, en particular sobre las siguientes declaraciones:
- "Estoy dispuesto a votar en la papeleta B" y
- "Anuncio el compromiso de la papeleta B"
Desde la perspectiva de un nodo determinado, se alcanza el consenso cuando encuentra una boleta B para la cual puede confirmar (es decir, encontrar un quórum que acepte) la afirmación "Yo comprometo la boleta B". A partir de este momento, es seguro actuar según el valor especificado en B, por ejemplo, realizar este pedido para el almuerzo. Se llama externalización significados. Una vez confirmada la aceptación de la boleta, un nodo puede estar seguro de que cualquier otro nodo ha exteriorizado el mismo valor o lo hará en el futuro.
Aunque conceptualmente muchas votaciones federadas se llevan a cabo sobre la base de reclamaciones de muchas papeletas diferentes, no intercambian tantos mensajes porque cada mensaje encapsula una cantidad de papeletas. Así, un mensaje promueve el estado de muchos votos federados a la vez, por ejemplo: “Acepto comprometer votos que van desde antes "
¿Qué significan los términos “preparado” y “comprometerse”?
Un nodo vota para enviar una boleta cuando confía en que otros nodos no enviarán boletas con valores diferentes. Convencer de esto es el objetivo de preparar la solicitud. Una votación que dice "Estoy listo para emitir la boleta B" es una promesa de nunca emitir una boleta menor que B, es decir, con un conteo menor (SCP requiere que los valores en las boletas estén en un orden determinado. Por lo tanto, el boletín informativo menos , si N1
¿Por qué “Estoy dispuesto a comprometer la papeleta B” significa “Prometo no comprometer nunca papeletas menores que B”? Porque SCP define el aborto como lo opuesto a comprometerse. Una votación para preparar una papeleta también implica una votación para descalificar otras papeletas y, como comentamos anteriormente, votar a favor de una cosa es una promesa de no votar nunca en contra.
Antes de transmitir una confirmación, un nodo primero debe encontrar un boletín que pueda confirmar como preparado. En otras palabras, realiza una votación federada sobre el tema “Estoy listo para comprometer la boleta B”, posiblemente en muchas boletas diferentes, hasta que encuentra una que acepte el quórum.
¿De dónde salen las papeletas para preparar la votación? 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 de que comiencen los preparativos para la votación, las nominaciones pueden dar lugar a que aparezcan candidatos adicionales que se conviertan en nuevas papeletas. Mientras tanto, los pares pueden tener diferentes candidatos y pueden formar un conjunto de bloqueo que acepte "Estoy listo para enviar la boleta B2", lo que convencerá al nodo de que la acepte también. Finalmente, existe un mecanismo de tiempo de espera que genera nuevas rondas de votación federada sobre nuevas papeletas con recuentos más altos si las papeletas actuales están estancadas.
Tan pronto como el nodo encuentra una boleta B que puede confirmar como preparada, transmite un nuevo mensaje "Confirmar boleta B". Esta votación les dice a sus pares que el nodo nunca renunciará a B. De hecho, si B es una boleta , luego “Confirmar votación " significa el consentimiento incondicional para votar por la preparación de cada papeleta de a <∞, s>. Este valor adicional ayuda a otros pares a ponerse al día con el par comprometido si todavía se encuentran en etapas anteriores del protocolo.
En esta etapa, vale la pena enfatizar una vez más que se trata de protocolos asincrónicos. El hecho de que un nodo envíe votos positivos para una confirmación no significa que sus pares también lo hagan. Es posible que algunos de ellos todavía estén votando declaraciones en preparación para la votación, otros tal vez ya hayan exteriorizado el significado. SCP explica cómo un nodo debe procesar cada tipo de mensaje entre pares independientemente de su fase.
Si el mensaje "He anunciado un compromiso » no se puede recibir o confirmar, es decir, la probabilidad de que el mensaje sea aceptado o confirmado o - o, en todo caso, cualquier papeleta con el valor C, y no cualquier otro, ya que el nodo ya se ha comprometido a no cancelar nunca . Para cuando un nodo transmita los votos para un compromiso, será C o nada, dependiendo de hasta dónde llegue el consenso. Sin embargo, esto aún no es suficiente para que el nodo externalice C. Algunos pares bizantinos (que constituyen menos que un quórum, según nuestras suposiciones de seguridad) pueden mentirle al nodo. Aceptar y luego confirmar alguna boleta (o rango de boletas) es lo que le da al nodo la confianza para finalmente externalizar C.
Votación del SCP mediante votación federada. No se muestra: el cronómetro puede sonar en cualquier momento, aumentando el conteo en la boleta (y posiblemente produciendo una nueva combinación de candidatos nominados adicionales).
¡Y eso es todo! Una vez que la red ha llegado a un consenso, está lista para hacerlo una y otra vez. En la red de pagos Stellar, esto sucede aproximadamente una vez cada 5 segundos: una hazaña que requiere tanto la seguridad como la capacidad de supervivencia garantizadas por SCP.
SCP puede lograr esto confiando en múltiples rondas de votación federada. La votación federada es posible gracias al concepto de porciones de quórum: conjuntos de pares en los que cada nodo ha decidido confiar como parte de su quórum (subjetivo). Esta configuración significa que se puede alcanzar un consenso incluso en una red con membresía abierta y engaños bizantinos.
Otras lecturas
- El documento técnico original de SCP se puede encontrar Y proyecto de especificaciones para su implementación.
- El autor original del protocolo SCP, David Mazier, lo explica de forma simplificada (pero aún técnica). .
- Es posible que le haya sorprendido 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í lo hacen. Zane Witherspoon escribió accesible .
- una red simple que alcanza el consenso en una ronda completa de SCP.
- Para lectores interesados en implementaciones de SCP: consulte , utilizado por la red de pagos Stellar, o , que escribí para una mejor comprensión de SCP.
Fuente: habr.com