Aprender

Prueba de Acuerdo

Si has pasado suficiente tiempo en la red de Stellar, quizás uno de los misterios en los que reflexionas es cómo funciona el algoritmo de consenso único de Acuerdo de Stellar (PoA). Después de todo, esto no es Prueba de Participación o Prueba de Trabajo – entonces, ¿qué podría ser?

El Mecanismo

El mecanismo de Prueba de Acuerdo es una toma muy interesante e individual sobre el problema de alcanzar consenso en un sistema distribuido sin permisos (“sin permisos” significa que ninguna autoridad central controla quién se une a la red). Lee y todo será revelado... ¡usando ejemplos de cómo la Prueba de Acuerdo puede funcionar en la vida real!

Ejemplo 1

El Regalo de Aniversario de Amy

Bob debe elegir un regalo de aniversario para su esposa Amy: flores o chocolate?

Bob confía en sus amigos Cal y Cam, y en su suegra Deb. Podemos decir que tiene dos quórums para tomar una decisión sobre asuntos concernientes a Amy:

Bob, Cal y Cam, y
Bob y Deb.

Para que Bob decida sobre un regalo de aniversario, se requiere el acuerdo dentro de al menos uno de estos quórums. Es decir:

O bien Bob, Cal y Cam están de acuerdo,
O Bob y Deb están de acuerdo.

También podría ser que Bob, Cal, Cam y Deb estén todos de acuerdo, pero esto no es necesario para decidir sobre un regalo.

Nota que avanzar es obligatorio; no es una opción para Bob rendirse y explicarle a Amy que no obtuvo su regalo de aniversario porque no pudo decidir qué conseguir.

Así que para avanzar hacia la compra de un regalo adecuado, Bob necesita establecer las opiniones de Cal y Cam, y/o de Deb.

Pensemos como programadores y listemos todos los casos posibles:

Cal y Cam recomiendan flores. Deb recomienda flores también.

Bob tiene que estar de acuerdo con al menos uno de sus quórums, y dado que ambos quórums dicen lo mismo, Bob no tiene elección: para avanzar, debe estar de acuerdo con ellos y comprar flores.
Cal y Cam recomiendan chocolate. Deb recomienda flores.

Aquí, Bob tiene una elección: puede avanzar con flores o chocolate. En cualquier caso, uno de sus quórums estará de acuerdo.
Bob toma su decisión lanzando una moneda, o podría usar conocimiento previo.
Cal recomienda chocolate, Cam recomienda flores. Deb recomienda flores.

A menos que Bob pueda convencer a Cal o Cam de cambiar de opinión, Bob tiene que ir con flores.

Esto es porque el quórum Cal, Cam, Bob no puede estar de acuerdo sin importar lo que Bob haga (porque Cal y Cam no están de acuerdo), pero Bob puede formar un quórum con Deb comprando flores.
Cal recomienda chocolate, Cam recomienda flores. Deb recomienda chocolate.

Como en el caso 3, Bob no tiene elección: tiene que estar de acuerdo con Deb y comprar chocolate.

Pensemos Como Programadores

Casos Posibles

Cal y Cam recomiendan flores. Deb recomienda flores también.

Bob tiene que estar de acuerdo con al menos uno de sus quórums, y dado que ambos quórums dicen lo mismo, Bob no tiene elección: para avanzar, debe estar de acuerdo con ellos y comprar flores.¹

Cal y Cam recomiendan chocolate. Deb recomienda flores.

Aquí, Bob tiene una elección: puede avanzar con flores o chocolate. En cualquier caso, uno de sus quórums estará de acuerdo.
Bob toma su decisión lanzando una moneda, o podría usar conocimiento previo.

Cal recomienda chocolate, Cam recomienda flores. Deb recomienda flores.

A menos que Bob pueda convencer a Cal o Cam de cambiar de opinión, Bob tiene que ir con flores.

Esto es porque el quórum Cal, Cam, Bob no puede estar de acuerdo sin importar lo que Bob haga (porque Cal y Cam no están de acuerdo), pero Bob puede formar un quórum con Deb comprando flores.

Cal recomienda chocolate, Cam recomienda flores. Deb recomienda chocolate.

Como en el caso 3, Bob no tiene elección: tiene que estar de acuerdo con Deb y comprar chocolate.

Comentarios

El Regalo de Aniversario de Amy

El ejemplo del aniversario captura algunos aspectos útiles de cómo funciona Stellar:

La acción básica es transferencia de propiedad: de tokens en el caso de Stellar; de flores o chocolate en el caso de Bob arriba.
Avanzar es obligatorio: Bob tiene que darle a Alice un regalo (asumiendo que quiere seguir casado), y Stellar tiene que hacer progresos (asumiendo que quiere retener usuarios).

También hay diferencias. El ejemplo del aniversario tiene un número fijo de (cuatro) participantes, dos quórums fijos y solo una decisión. Stellar tiene docenas de nodos validadores, toma decisiones cada dos a cinco segundos – y, al menos en principio, nuevos nodos validadores pueden unirse en cualquier momento.

¿Cómo se gestiona este proceso?

Ejemplo 2

La Lista de Bodas de Amy y Bob

Cuando un nuevo nodo validador se une a la red de Stellar, nombra un conjunto de rebanadas (también llamado un testigo). Un quórum es entonces cualquier conjunto de validadores tal que para cada validador en ese conjunto, una de sus rebanadas también está en ese conjunto.

Para ilustrar cómo funciona esto, volvamos a cuando Amy y Bob estaban planeando su boda. Estaban redactando su lista de invitados a la boda…

Amy quería invitar a Bob (por supuesto), a su mejor amiga Che y a su padre Dee.
Así que Amy tiene una rebanada, que escribimos en notación de conjuntos matemáticos de la siguiente manera:
‍{Bob, Che, Dee}.
Bob quería invitar a Amy (por supuesto), a sus padres Hal e Ivy, y al menos a uno de sus amigos Gia o Guy.
Así que Bob tiene dos rebanadas:
‍{Amy, Hal, Ivy, Gia}
y {Amy, Hal, Ivy, Guy}.
Che está bien viniendo solo.
Así que Che tiene una rebanada vacía:
{}
(o una rebanada, que es {Che}; es lo mismo).
Dee solo vendrá si su esposa Deb también puede venir, y viceversa. Cada uno tiene una rebanada, que es el otro.
Ivy solo vendrá si su hermana Kay también viene.
Guy quiere traer a Jan o Joe. Así que Guy tiene dos rebanadas:
{Jan}, y {Joe}.
Jan y Joe están bien viniendo por su cuenta.

La lista de invitados tiene que ser un quórum: cada invitado debe tener al menos una de sus rebanadas en la boda.

Así que, por ejemplo: Amy debe traer a Che y Dee, pero Bob puede traer (al menos) uno de: Hal, Ivy y Gia; o Hal, Ivy y Guy. Haciendo los cálculos vemos que las posibles listas de invitados/quórum (empezando por Amy y Bob) son:

{Amy, Che, Dee, Hal, Ivy, Gia, Deb, Kay}
{Amy, Che, Dee, Hal, Ivy, Guy, Deb, Kay, Jan}
{Amy, Che, Dee, Hal, Ivy, Guy, Deb, Kay, Joe}

Para entender cómo funciona esto, ten en cuenta que:

Una vez que añadimos a Amy, tenemos que añadir a Bob (ya está), Che y Dee.
Una vez que añadimos a Bob, tenemos que añadir a Amy (ya está) y Hal e Ivy – porque están en todas las rebanadas de Bob – pero podemos elegir si añadir a Gia o Guy.
Una vez que añadimos a Guy, tenemos que añadir al menos uno de Jan y Joe.
Una vez que añadimos a Dee, tenemos que añadir a Deb, y viceversa (pero Dee ya está).

Continuando de esta manera, crecemos la lista de invitados hasta alcanzar lo que los matemáticos llaman un punto fijo. Este es nuestro quórum.

Las listas de invitados anteriores son los quórum más pequeños posibles. Quórum más grandes pueden hacer que la fiesta de boda sea más agradable, pero también más costosa. A menudo, las parejas resuelven el problema del quórum de la fiesta de boda invitando a todos, lo cual es una solución matemáticamente válida, aunque consume muchos recursos (para usar otro término de programación).

Dejamos como ejercicio al lector crear un conjunto de rebanadas para el ejemplo del aniversario anterior. (¡La respuesta está en una nota al pie!²)

Stellar construye quórum a partir de rebanadas, justo como Amy y Bob hicieron cuando construyeron su lista de invitados.

Empieza con algunos participantes (por ejemplo, Amy y Bob); luego
para cada miembro del conjunto, añade una de sus rebanadas; y
repite hasta que cada participante esté acompañado por (al menos) una de sus rebanadas.

En Stellar, las rebanadas representan confianza. Cuando te unes a la red como validador, tienes que decir qué rebanadas de los validadores existentes confías. Un quórum es un conjunto que puede progresar, en el sentido de que si está de acuerdo, entonces todos en el quórum están de acuerdo con al menos un grupo confiable.

Ejemplo 2

Residencias Romas' AGM

Repasemos la historia hasta ahora:

Cuando un validador se une a la red Stellar, nomina algunas rebanadas de confianza.
Un quórum es un conjunto de validadores que tiene al menos una rebanada de cada validador en el quórum.
Cuando un quórum está de acuerdo, puede progresar (por ejemplo, al comprometer una transacción en el libro mayor).

¿Qué impide que tal sistema se disuelva en caos, con diferentes validadores en diferentes quórum comprometiendo diferentes transacciones? Para esto, necesitamos una definición técnica.

Definiciones

Entrelazado & Topen

Llama a dos participantes p y q entrelazados cuando cada quórum P de p intersecta con cada quórum Q de q.
Un topen es un quórum de participantes entrelazados.

En el Ejemplo 1 anterior, todos los participantes Cal, Cam, Bob y Deb están entrelazados, y el sistema consiste en un solo topen.

Volvamos a Amy y Bob. Viven en un bloque de pisos llamado Residencias Roma. Residencias Roma es uno de los tres bloques en el vecindario, los otros dos siendo Residencias Londres y Residencias París.

En la AGM (asamblea general anual) de Roma, las decisiones se toman por mayoría de votos. Así que los quórum son mayorías de participantes, y todos los residentes de Roma están entrelazados porque todos los conjuntos de mayoría se intersectan (de lo contrario no sería una mayoría). Igualmente para Londres y París. Sin embargo, los quórum de Roma no se intersectan con los quórum de Londres o París, ni viceversa.

Así que este sistema se particiona en tres topen disjuntos, cada uno capaz de progresar independientemente: los consejos de AGM de Residencias Roma, Londres y París respectivamente. Esto es muy intuitivo: nosotros esperamos que estos comités actúen de manera autónoma y coherente dentro de sí mismos, y en terminología matemática simplemente decimos que estos son tres conjuntos de topen disjuntos.

Veamos dos ejemplos más concretos, para tener una idea de cómo funciona el estar entrelazado:

El ejemplo superior tiene cuatro quórum (etiquetados A, B, C y D) y todos los participantes están entrelazados.

En el ejemplo inferior el lector puede comprobar que 3 y 4 están entrelazados solo con ellos mismos, y -1, 1, 2 y 0 están entrelazados entre sí. Hay tres conjuntos de topen: 3; 4; y -1, 1, 2 (pero no -1, 1, 2, 0).3

El ejemplo de Roma/Londres/París es canónico, porque se puede probar (usando matemáticas que no están en este post del blog) que:

Definiciones

Lema

Cualquier sistema de quórum se particionará en topen disjuntos (más quizás algunos puntos aislados).

El consenso está garantizado dentro de cada topen, por la propiedad entrelazada: si cada participante está de acuerdo con su quórum, y todos los quórums en el topen se intersectan, entonces cada participante en el topen debe estar de acuerdo.

Ejemplo 4

La Influencia Requiere Confianza Recíproca

Se supone que los sistemas de Blockchain deben ser resilientes bajo ataque. Veamos cómo funciona esto en Stellar.

Supongamos que los residentes de París quieren corromper la toma de decisiones en Residencias Roma. Los residentes de París pueden agregar a los residentes de Roma a sus propias rebanadas (y así crear nuevos quórums) – pero no pueden cambiar las rebanadas de los residentes de Roma (cada participante decide sus propias rebanadas y solo sus propias rebanadas). Esto significa que el topen de los residentes de Roma – su consejo de AGM – no se ve afectado por el ataque, y Roma puede continuar tomando decisiones y progresando, completamente no afectado por el hecho de que están en las rebanadas de partes externas cuya confianza no reciprocarn.

Este simple ejemplo importa particularmente porque es muy diferente de cómo funcionan blockchains como Ethereum, donde cualquiera en la red con computación o participación obtiene un asiento en la mesa de votación, no importa cuán desagradable pueda ser como persona u organización. En Stellar, solo obtienes un asiento en una mesa si puedes convencer a aquellos ya en esa mesa de que confíen en ti. O para poner esto en un lenguaje más técnico – la única manera de atacar la toma de decisiones de un topen es convencer a los miembros deese topenpara agregar al atacante a sus rebanadas. Un atacante no confiable no puede afectar su toma de decisiones, no importa cuán poderosos sean los ordenadores del atacante o cuán rico pueda ser el atacante.

En Stellar, la reputación – ser digno de confianza – es todo. En algunos aspectos, este es un sistema mejor que los sistemas basados en PoW o PoS (prueba de trabajo o prueba de participación): la confiabilidad es una construcción social, no una computacional, así que representar la confianza en el sistema da incentivos a los participantes para curar y mantener sureputación social– en otras palabras, para comportarse de una manera honesta y confiable. La reputación puede ser un predictor imperfecto de virtud, pero al menos, mientras cualquiera con recursos puede obtener hardware de minería o participación, no cualquiera puede ganar confianza y respeto.

Palabras Finales

Es un Poco Más Complejo

En la vida real, hacer que Stellar funcione es un poco más complejo que los ejemplos anteriores. No podemos entrar en detalles aquí pero nos gustaría dar al lector una idea de los problemas involucrados en aplicar estas ideas en la práctica.

El ejemplo relevante es bastante simple. Considera una elaboración del Ejemplo 1 anterior en la que todos los quórums tienen un tamaño de al menos tres:

Todo lo que hemos hecho es agregar a Dot, la madre de Bob, al quórum que contenía a Deb, la suegra de Bob.

Este es un cambio simple – pero significa que si Cal y Cam no están de acuerdo, y también Deb y Dot no están de acuerdo, entonces el acuerdo de quórum es imposible independientemente del voto de Bob (cualquier parecido con la vida real aquí es puramente coincidencial, por supuesto).

En la vida real lo que sucede es que los quórums debaten entre sí hasta que, con el tiempo, uno de los quórums (con suerte) llega a un acuerdo y puede progresar. (En la vida real esto siempre sucede de manera razonable, de buena fe, y sin disputas o rencor, por supuesto.) Algo similar se formaliza dentro del Protocolo de Consenso de Stellar, por un mecanismo computacional que logra confiablemente el consenso, en segundos. Esperamos con interés sumergirnos en este increíble logro técnico en otra publicación de blog.

1. Podrías estar preguntándote qué pasa si Bob va y compra chocolates de todos modos. Bueno, podría hacerlo, pero eso simplemente no estaría jugando según las reglas. La vida está llena de tales situaciones, y el inglés tiene palabras positivas para aquellos que juegan según las reglas (reputable, reliable, trustworthy) y palabras negativas para aquellos que no (disreputable, unreliable, untrustworthy).

2. Una posibilidad es:
Bob tiene dos rebanadas: