Entendiendo el Protocolo de Consenso Estelar



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.

Source: https://habr.com/ru/post/444710/


All Articles