¿Qué es el método Phragmén secuencial? #

El método Phragmén secuencial es un método de elección de varios ganadores introducido por Edvard Phragmén en la década de 1890. Aunque el Phragmén secuencial se utiliza actualmente en Polkadot y Kusama, en el futuro se utilizará una mejora del método Phragmén secuencial denominada Phragmms (ver infra).

La cita siguiente, tomada del documento de referencia de Phragmén (ver Recursos Externos infra), resume el propósito del método Phragmén secuencial:

• El problema que los métodos de Phragmén intentan resolver es el de la elección de un conjunto de un número determinado de personas de un conjunto mayor de candidatos. Phragmén lo planteó en el contexto de una elección parlamentaria en una circunscripción de varios miembros; por supuesto, el mismo problema puede darse también en las elecciones locales, pero también en muchas otras situaciones, como la elección de una junta directiva o un comité en una organización.

¿Dónde se utiliza el método Phragmén en Polkadot? #

NPoS: Elecciones de Validadores #

El método Phragmén secuencial se utiliza en el esquema Nominated Proof-of-Stake para elegir a los validadores basándose en su propio Stake y en el stake que les votan los nominadores. También trata de igualar los pesos entre los validadores después de cada ronda de elección. Dado que los validadores cobran por igual en Polkadot, es importante que el stake de cada validador esté repartido. Polkadot intenta optimizar tres métricas en sus elecciones:

1. Maximizar la cantidad total en stake.
2. Maximizar el stake detrás del validador con mínimo staking.
3. Minimizar la varianza del stake en el conjunto.

Phragmén fuera de la cadena

Dado el gran conjunto de nominadores y validadores, el método de Phragmén es un problema de optimización difícil. Polkadot utiliza trabajadores fuera de la cadena para calcular el resultado fuera de la cadena y presentar una transacción para proponer el conjunto de ganadores. La razón para realizar este cálculo fuera de la cadena es mantener un tiempo de bloqueo constante de seis segundos y evitar largos tiempos de bloqueo al final de cada era, cuando tiene lugar la elección del validador.

Dado que ciertas acciones del usuario, como el cambio de nominaciones, pueden cambiar el resultado de la elección de Phragmén, el sistema prohíbe las llamadas a estas funciones durante el último cuarto de la sesión antes de un cambio de era. Estas funciones no están permitidas:

• bondExtra
• unbond
• withdrawUnbonded
• validate
• nominate
• chill
• payoutStakers
• rebond

Elecciones del Consejo #

El método Phragmén también se utiliza en el mecanismo de elección del consejo. Cuando votas a los miembros del consejo, puedes seleccionar hasta 16 candidatos diferentes, y luego colocar una vinculación reservada como peso de tu voto. Phragmén se ejecutará una vez en cada elección para determinar los principales candidatos a asumir los puestos del consejo y luego otra vez entre los principales candidatos para igualar el peso de los votos detrás de ellos tanto como sea posible.

¿Qué significa para los operadores de nodos? #

Phragmén es algo que se ejecuta en segundo plano y no requiere ningún esfuerzo adicional por tu parte. Sin embargo, es bueno entender cómo funciona, ya que significa que no todo stake que nominaste terminará en tu validador después de una elección. Es probable que los nominadores nominen a varios validadores diferentes en los que confíen para hacer un buen trabajo en sus nodos.

Puedes utilizar el script offline-phragmén para predecir el resultado de una elección de validador antes de una nueva elección.

Entender Phragmén #

En esta sección se explica en profundidad el método secuencial Phragmén y se muestran ejemplos.

Phragmén Básico #

Fundamentos #

Para entender el método Phragmén ponderado, primero debemos entender el método Phragmén básico. Debe haber un grupo de candidatos, un grupo de escaños por los que compiten (que es menor que el tamaño del grupo de candidatos) y un grupo de votantes. Los votantes pueden emitir un voto de aprobación, es decir, pueden señalar su aprobación a cualquier subconjunto de los candidatos.

El subconjunto debe tener un tamaño mínimo de uno (es decir, no se puede votar por ningún candidato) y un tamaño máximo de uno menos que el número de candidatos (es decir, no se puede votar por todos los candidatos). Los usuarios pueden votar por todos los candidatos o por ninguno, pero esto no tendrá efecto en el resultado final, por lo que los votos de esta naturaleza no tienen sentido.

Nota que en este ejemplo se supone que todos los votantes tienen la misma voz (es decir, su voto no cuenta más o menos que el de los demás). El caso ponderado se estudiará más adelante. Sin embargo, la ponderación puede “simularse” haciendo que varios votantes voten por la misma lista de candidatos. Por ejemplo, cinco personas que votan por un candidato concreto es matemáticamente lo mismo que una sola persona con peso 5 que vota por ese candidato.

El algoritmo particular que llamamos aquí “Phragmén Básico” fue descrito por primera vez por Brill et al. en su artículo “Phragmén’s Voting Methods and Justified Representation”.

Algoritmo #

El método Phragmén itera, seleccionando un escaño cada vez, según las siguientes reglas:

1. Los candidatos presentan sus boletas, marcando los candidatos que aprueban. Las boletas no se modifican después de su presentación.
2. Se establece una carga inicial de 0 para cada boleta.
3. El candidato que gana el siguiente escaño disponible es aquel en el que las boletas de sus partidarios tendrían el menor costo medio (promedio) si ese candidato gana.
4. Las n boletas que aprobaron a ese candidato ganador obtienen 1/n agregado a su carga.
5. La carga de todas las boletas que apoyaron al ganador de esta ronda se promedian para que sean iguales.
6. Si hay más escaños, se vuelve al paso 3. En caso contrario, la selección termina.

Ejemplo #

Veamos un ejemplo con cuatro candidatos compitiendo por tres escaños y cinco votantes.

En este ejemplo, podemos ver que el votante V1 aprueba sólo al candidato B, el votante V2 aprueba a los candidatos C y D, etc. Los votantes pueden aprobar cualquier número de candidatos entre 1 y number_of_candidates - 1. Se establece una “carga” inicial de 0 para cada boleta (L0 = carga después de la ronda 0, es decir, la “ronda” anterior a la primera ronda). Veremos en breve cómo se actualiza esta carga y se utiliza para seleccionar a los candidatos.

A continuación, vamos a ejecutar un algoritmo iterativo, en el que cada iteración corresponde a un “escaño”. Como hay tres escaños, recorreremos tres rondas.

Para la primera ronda, el ganador será simplemente el candidato con más votos. Como todas las cargas son iguales, la carga media más baja será la del candidato con el mayor n, ya que 1/n se hará más pequeño a medida que aumente n. Para esta primera ronda de ejemplo, por ejemplo, el candidato A sólo tuvo un voto a su favor. Por lo tanto, la carga media para el candidato A es 1/1, o sea 1. El candidato C tiene dos boletas que lo aprueban, por lo que la carga media es 1/2. El candidato B tiene la carga media más baja, con 1/4, y obtiene el primer escaño. Las cargas de las boletas se promedian ahora, aunque para la primera iteración, esto no tendrá ningún efecto.

Ahora nos quedamos con los candidatos A, C y D para dos puestos vacantes. Sólo hay un votante (V4) para A, con carga 1/4. C tiene dos votantes, V2 y V5, con cargas de 0 y 1/4. D tiene tres votantes que lo aprueban, V2, V3 y V5, con cargas de 0, 1/4 y 1/4, respectivamente.

Si gana el candidato A, la carga promedio sería (1/4 + 1/1) / 1, es decir, 5/4. Si gana el candidato C, la carga promedio sería ((0 + 1/2) + (1/4 + 1/2)) / 2, es decir, 5/8. Si gana el candidato D, la carga promedio sería ((0 + 1/3) + (1/4 + 1/3) + (1/4 + 1/3)) / 3, es decir, 1/2. Como 1/2 es la carga promedio más baja, el candidato D gana la segunda vuelta.

Ahora todos los que han votado al candidato D tienen su carga ajustada al promedio, 1/2 de todas las cargas.

Ahora hay un escaño abierto y dos candidatos, A y C. El votante V4 es el único que vota por A, por lo que si A gana la carga promedio sería (1/4 + 1/1) / 1, o sea 5/4. Los votantes V2 y V5 (ambos con carga 1/2) apoyan a C, por lo que si C gana la carga promedio sería ((1/2 + 1/2) + (1/2 + 1/2)) / 2, o 1. Como la carga promedio sería menor con C, C gana el escaño final.

Una característica interesante de este cálculo es que la carga total de todos los votantes siempre será igual al número de escaños cubiertos en esa ronda. En la ronda 0, la carga comienza en 0 y no hay escaños ocupados. Después de la primera ronda, el total de todas las cargas es 1, después de la segunda ronda es 2, etc.

Phragmén Ponderado #

Justificación #

Aunque este método funciona bien si todos los votantes tienen el mismo peso, no es el caso en Polkadot. Las elecciones tanto de validadores como de candidatos al Consejo de Polkadot se ponderan por el número de tokens que tienen los votantes. Esto hace que las elecciones se parezcan más a una elección de accionistas de una empresa que a una elección política tradicional, en la que algunos miembros tienen más tracción que otros. Alguien con un solo token tendrá mucho menos poder de voto que alguien con 100. Aunque esto pueda parecer antidemocrático, en un sistema de seudónimos, es trivial que alguien con 100 tokens cree 100 cuentas diferentes y reparta su riqueza entre todos sus seudónimos.

Por lo tanto, no sólo queremos permitir a los votantes que sus preferencias se expresen en el resultado, sino hacerlo manteniendo una distribución lo más equitativa posible de su staking y expresar los deseos de las minorías tanto como sea posible. El método Phragmén Ponderado nos permite alcanzar estos objetivos.

Algoritmo #

El Phragmén Ponderado es similar al Phragmén Básico en el sentido de que selecciona a los candidatos de forma secuencial, uno por ronda, hasta que se elige el máximo número de candidatos. Sin embargo, tiene características adicionales para asignar también un peso (stake) detrás de los candidatos.

NOTA: en términos de selección de validadores, para el siguiente algoritmo, puedes pensar en los “votantes” como “nominadores” y en los “candidatos” como “validadores”.

1. Los candidatos son elegidos, uno por ronda, y se añaden al conjunto de candidatos aprobados (han ganado un “puesto”). Este aspecto del algoritmo es muy similar al algoritmo “básico de Phragmén” descrito anteriormente.
2. Sin embargo, a medida que se eligen los candidatos, se construye un mapeo ponderado que define los pesos de cada selección de un validador por parte de cada nominador.

En mayor profundidad, el algoritmo funciona así:

1. Crea una lista de todos los votantes, su cantidad total de stake y los validadores que apoyan.
2. Genera un mapeo inicial de gráficos ponderados por bordes de los votantes a los candidatos, donde el peso de cada borde es el peso potencial total (stake) dado por ese votante. La suma de todos los pesos potenciales de un candidato determinado se denomina su stake de aprobación.
3. Ahora empezamos a elegir a los candidatos. Para la lista de todos los candidatos que no han sido elegidos, se obtiene su puntuación, que es igual a 1 / approval_stake.
4. Para cada votante, actualiza la puntuación de cada candidato que apoye sumando su presupuesto total (stake) multiplicado por la carga del votante y luego dividiéndolo por el stake de aprobación de ese candidato (voter_budget * voter_load / candidate_approval_stake).
5. Determina el candidato con la menor puntuación y lo elige. Elimina el candidato elegido del conjunto de candidatos potenciales.
6. La carga de cada borde que conecta con el candidato ganador se actualiza, con la carga del borde ajustada a la puntuación del candidato menos la carga del votante, y la carga del votante ajustada a la puntuación del candidato.
7. Si hay más candidatos para elegir, va al paso 3. En caso contrario, continúa con el paso 8.
8. Ahora el stake se distribuye entre cada nominador que respaldó al menos a un candidato elegido. El stake de apoyo de cada candidato se calcula tomando el presupuesto del votante y multiplicándolo por la carga de bordes y dividiéndolo por la carga del candidato (voter_budget * edge_load / candidate_load).

Ejemplo #

Nota: Todos los números de este ejemplo están redondeados a tres decimales.

En el siguiente ejemplo, hay cinco votantes y cinco candidatos compitiendo por tres posibles escaños. Cada votante V1 - V5 tiene una cantidad de stake igual a su número (por ejemplo, V1 tiene un stake de 1, V2 tiene un stake de 2, etc.). Cada votante también tendrá una carga, que inicialmente comienza en 0.

Calculemos ahora el stake de aprobación de cada uno de los candidatos. Recordemos que se trata simplemente de la cantidad de todos los apoyos a ese candidato por parte de todos los votantes.

El primer paso es fácil: el candidato E tiene 0 stake de aprobación y puede ser ignorado de aquí en adelante. Nunca será elegido.

Ahora podemos calcular la puntuación inicial de los candidatos, que es 1 / approval_stake:

Para cada borde, vamos a calcular la puntuación, que es la puntuación actual más el presupuesto total * la carga del votante dividida por el stake de aprobación del candidato. Sin embargo, dado que la carga de cada votante comienza en 0, y cualquier cosa multiplicada por 0 es 0, cualquier adición será 0 / x, o 0. Esto significa que este paso puede ser ignorado con seguridad para la ronda inicial.

Por lo tanto, la mejor puntuación (la más baja) para la ronda 0 es el candidato A, con una puntuación de 0,091.

El candidato A está ahora a salvo; no hay forma de que pierda su escaño. Antes de pasar a la siguiente ronda, tenemos que actualizar las puntuaciones en los bordes de nuestro gráfico de los candidatos que aún no han sido elegidos.

Hemos eludido este detalle en la ronda anterior, ya que no suponía ninguna diferencia en las puntuaciones finales, pero debemos profundizar aquí para ver cómo se actualizan las puntuaciones. Primero debemos calcular las nuevas cargas de los votantes, y luego calcular las nuevas puntuaciones de los candidatos.

Cualquier votante al que una de sus opciones de candidato haya ocupado el escaño en esta ronda (es decir, los votantes V1, V2, V3 y V5, que han votado todos por A) verá incrementada su carga. Este aumento de la carga atenuará el impacto de su voto en futuras rondas, y el borde (que se utilizará para determinar la asignación de stake más adelante) se fija en la puntuación del candidato elegido menos la carga actual del votante.

En este caso, la puntuación del candidato elegido es 0,091 y las cargas de los votantes son todas 0. Así que para cada votante que haya votado por A, calcularemos una nueva carga de borde Voter -> A de:

y una nueva carga de votantes de:

Como recordatorio, aquí están las puntuaciones actuales. Las cargas de los votantes son todas 0.

Ahora, recorremos el gráfico ponderado y actualizamos la puntuación del candidato y la carga del borde, utilizando el algoritmo:

candidate_score = candidate_score + ((voter_budget * voter_load) / candidate_approval_stake)

Sin recorrer cada paso, esto nos da las siguientes modificaciones en las puntuaciones de los diferentes candidatos.

Una vez actualizadas las puntuaciones, las puntuaciones finales de los candidatos para esta ronda son:

D, con la puntuación más baja, es elegido. Puedes observar que, aunque el candidato B tenía más votantes que lo apoyaban, el candidato D ganó la elección debido a su menor puntuación. Esto se debe directamente al hecho de que tenía la puntuación más baja, por supuesto, pero la razón fundamental de que tuviera una puntuación más baja era tanto la mayor cantidad de stake que lo respaldaban como que los votantes que no consiguieron una de sus opciones en una ronda anterior (en este ejemplo, el votante V4) corresponden a una mayor probabilidad de que un candidato sea elegido.

A continuación, actualizamos las cargas de los votantes y de los bordes, tal y como se especificó anteriormente, para los votantes que hayan votado al candidato D (es decir, V4 y V5) utilizando la misma fórmula anterior.

Siguiendo un proceso similar para la Ronda 2, partimos de unas puntuaciones iniciales de los candidatos de:

A continuación, podemos actualizar las puntuaciones de los dos candidatos restantes según el algoritmo descrito anteriormente.

Con la puntuación más baja de 0,274, el candidato B reclama el último puesto vacante. Los candidatos A, D y B fueron elegidos, y los candidatos C y E no.

Antes de seguir adelante, debemos realizar un último ajuste de carga para los votantes y el gráfico.

Ahora tenemos que determinar cuanto stake debe asignar cada votante a cada candidato. Esto se hace tomando la carga de cada borde y dividiéndola por la carga del votante, y luego multiplicándola por el presupuesto total del votante.

En este ejemplo, el gráfico ponderado quedó así:

Por ejemplo, el presupuesto de V1 es 1, la carga del borde hacia A es 0,091 y la carga del votante es 0,274. Utilizando nuestra ecuación:

Podemos completar estas variables con:

Para V1 backing stake de B, puedes simplemente reemplazar el valor de la carga del borde y volver a calcular.

Nota que la cantidad total de todo el stake de apoyo para un votante dado será igual al presupuesto total del votante, a menos que ese votante no haya tenido candidatos elegidos, en cuyo caso será 0.

Los resultados finales son:

Notarás que el importe total del stake para los candidatos A, D y B es igual (aparte de los errores de redondeo) al importe total del stake de todos los votantes (1 + 2 + 3 + 4 + 5 = 15). Esto se debe a que cada votante tenía al menos uno de sus candidatos para ocupar un escaño. Cualquier votante que no haya tenido ninguno de sus candidatos seleccionados tampoco tendrá ninguna participación en ninguno de los candidatos elegidos.

Optimizaciones #

Los resultados de las nominaciones de los validadores se optimizan aún más con varios fines:

1. Para reducir el número de bordes, es decir, para minimizar el número de validadores que cualquier nominador selecciona
2. Garantizar, en la medida de lo posible, una distribución uniforme del stake entre los validadores
3. Reducir el tiempo de cálculo de los bloques

Descripción de Alto Nivel #

Después de ejecutar el algoritmo de Phragmén ponderado, se ejecuta un proceso que redistribuye el voto entre el conjunto de elegidos. Este proceso nunca agrega o elimina un candidato elegido del conjunto. En su lugar, reduce la desviación en la lista de stake de apoyo de los votantes a los candidatos elegidos. La equiparación perfecta no siempre es posible, pero el algoritmo intenta equiparar todo lo posible. A continuación, ejecuta un algoritmo de reducción de bordes para minimizar el número de validadores por nominador, dando idealmente a cada nominador un único validador para nominar por era.

Para minimizar el tiempo de cálculo de los bloques, el proceso de staking se ejecuta como un trabajador fuera de la cadena. Para dar tiempo a que se ejecute este trabajador fuera de la cadena, no se permiten los comandos de staking (vinculación, nominación, etc.) en el último cuarto de cada era.

Estas optimizaciones no se tratarán en profundidad en esta página. Para más detalles, puedes ver la implementación de Rust de las elecciones en Substrate, la implementación de Rust en staking en Substrate, o el método seqPhragménwithpostprocessing en la implementación de referencia de Python. Si quieres profundizar aún más, puedes revisar la Página de Investigación de W3F sobre el Método Secuencial de Phragmén.

Justificación para Minimizar el Número de Validadores por Nominador #

Pagar las recompensas por staking de cada validador a todos sus nominadores puede costar una cantidad no trivial de recursos de la cadena (en términos de espacio en la cadena y recursos para calcular). Supongamos un sistema con 200 validadores y 1000 nominadores, donde cada uno de los nominadores ha nominado a 10 validadores diferentes. Por tanto, el pago requeriría 1_000 * 10, o 10_000 transacciones. En un escenario ideal, si cada nominador selecciona un único validador, sólo habría que realizar 1_000 transacciones, un orden de magnitud menos. Empíricamente, la ralentización de la red al principio de una era se ha producido debido al gran número de pagos individuales de los validadores a los nominadores. En casos extremos, esto podría ser un vector de ataque al sistema, en el que los nominadores nominan a muchos validadores diferentes con pequeñas cantidades de stake con el fin de ralentizar el sistema en el siguiente cambio de era.

Aunque esto reduciría la carga de la red y de la cadena, el hecho de poder seleccionar sólo un validador conlleva algunos costos de diversificación. Si el único validador que un nominador ha nominado se desconecta o actúa de forma maliciosa, entonces el nominador incurre en el riesgo de una cantidad significativa de slashing. Por lo tanto, los nominadores pueden nominar hasta 16 validadores diferentes. Sin embargo, una vez ejecutado el algoritmo de reducción de bordes ponderado, se minimiza el número de validadores por nominador. Es probable que los nominadores se vean nominando a un único validador activo para una era.

En cada cambio de era, al ejecutarse de nuevo el algoritmo, es probable que los nominadores tengan un validador diferente al que tenían antes (suponiendo un número significativo de validadores seleccionados). Por lo tanto, los nominadores pueden diversificarse contra los validadores incompetentes o corruptos que provocan slashings en sus cuentas, incluso si sólo nominan a un único validador por era.

Justificación para Mantener una Distribución Uniforme del Staking #

Otra cuestión es que queremos garantizar una distribución de votos lo más equitativa posible entre los validadores o miembros del consejo elegidos. Esto nos ayuda a aumentar la seguridad del sistema asegurando que la cantidad mínima de tokens para formar parte del conjunto de validadores activos o del consejo sea lo más alta posible. Por ejemplo, supongamos un resultado de cinco validadores elegidos, donde los validadores tienen el siguiente stake: {1_000, 20, 10, 10, 10}, para un stake total de 1_050. En este caso, un atacante potencial podría unirse al conjunto de validadores activos con sólo 11 tokens, y podría obtener una mayoría de validadores con sólo 33 tokens (ya que el atacante sólo tiene que tener suficiente stake para “echar” a los tres validadores más bajos).

Por el contrario, imagina un resultado diferente con la misma cantidad de stake total, pero con ese stake perfectamente distribuida de forma equitativa: {210, 210, 210, 210, 210}. Con la misma cantidad de stake, un atacante necesitaría hacer stake de 633 tokens para conseguir una mayoría de validadores, una propuesta mucho más cara. Aunque obtener una distribución equitativa es poco probable, cuanto más equitativa sea la distribución, más alto será el umbral -y por tanto más caro- para que los atacantes consigan entrar en el conjunto.

Justificación para Reducir el Tiempo de Cálculo de los Bloques #

La ejecución del algoritmo de Phragmén requiere mucho tiempo, y a menudo no puede completarse dentro de los límites de tiempo de producción de un solo bloque. Esperar a que se complete el cálculo pondría en peligro el tiempo de producción de bloques constante de la red. Por lo tanto, se traslada todo el cálculo posible a un trabajador fuera de la cadena, cuyos validadores pueden trabajar en el problema sin afectar al tiempo de producción de bloques. Al restringir la capacidad de los usuarios de realizar cualquier modificación en el último 25% de una era, y ejecutar la selección de validadores por parte de los nominadores como un proceso offchain, los validadores tienen una cantidad de tiempo significativa para calcular el nuevo conjunto de validadores activos y asignar los nominadores de manera óptima.

Hay varias restricciones adicionales para limitar la complejidad de la elección y el pago. Como ya se mencionó, cualquier nominador sólo puede seleccionar hasta 16 validadores para nominar. A la inversa, un mismo validador sólo puede tener 256 nominadores. El inconveniente es que, si el número de nominadores es muy elevado o el número de validadores es muy bajo, es posible que todos los validadores disponibles estén “sobresuscriptos o saturados” y no puedan aceptar más nominaciones. En este caso, es posible que se necesite una cantidad mayor de stake para participar en el staking, ya que las nominaciones se clasifican por prioridad en función de la cantidad de stake.

Phragmms (alias Balphragmms) #

Phragmms, antes conocido como Balphragmms, es una nueva regla de elección inspirada en Phragmén y desarrollada internamente para Polkadot. En general, las reglas de elección en blockchains son un tema de investigación activo. Esto se debe a los requisitos contradictorios de las reglas electorales y las blockchains: las elecciones son computacionalmente costosas, pero las blockchains son computacionalmente limitadas. Por lo tanto, este trabajo constituye el estado del arte en términos de optimización.

La representación proporcional es una propiedad muy importante que debe tener una red descentralizada para mantener un nivel suficiente de descentralización. Aunque esto ya lo proporciona el seqPhragmen actualmente implementado, esta nueva regla de elección ofrece la ventaja de la garantía de seguridad agregada que se describe a continuación. Por lo que sabemos, en el momento de escribir este artículo, Polkadot y Kusama son las únicas redes de blockchain que implementan una regla electoral que garantiza la representación proporcional.

La seguridad de un sistema distribuido y descentralizado como Polkadot está directamente relacionada con el objetivo de evitar la sobrerrepresentación de cualquier minoría. Esto contrasta fuertemente con los enfoques tradicionales de los axiomas de representación proporcional, que normalmente sólo buscan evitar la infrarrepresentación.

Objetivo de apoyo máximo y PJR

Esta nueva regla electoral pretende conseguir una garantía de aproximación de factor constante para el objetivo de apoyo máximo y la propiedad de representación proporcional justificada (PJR), estrechamente relacionada.

El objetivo de apoyo máximo se basa en maximizar el apoyo del candidato elegido menos apoyado o, en el caso de Polkadot y Kusama, en maximizar el menor monto de stake de apoyo entre los validadores elegidos. Este objetivo basado en la seguridad se traduce en una garantía de seguridad para NPoS y dificulta la elección de los nodos validadores de una ballena adversaria. La regla Phragmms, y las garantías que proporciona en términos de seguridad y proporcionalidad, se han formalizado en un artículo revisado por pares).

La propiedad PJR considera la proporcionalidad del poder de decisión del votante. La propiedad establece que un grupo de votantes con preferencias de candidatos cohesionados y una fuerza de voto agregada suficientemente grande merece tener un número de representantes proporcional a la fuerza de voto del grupo.

Comparación entre el Phragmén Secuencial, el MMS y los Phragmms

El Phragmén Secuencial (seqPhragmen) y el MMS son dos reglas electorales eficientes que consiguen el PJR.

Actualmente, Polkadot emplea el método seqPhragmen para las elecciones de validadores y consejos. Aunque seqPhramen tiene un tiempo de ejecución muy rápido, no proporciona una aproximación de factor constante para el problema de apoyo máximo. Esto se debe a que seqPhramen sólo realiza un reequilibrio aproximado de la distribución del stake.

Por el contrario, MMS es otro algoritmo codicioso estándar que logra simultáneamente la propiedad PJR y proporciona una aproximación de factor constante para el apoyo máximo, aunque con un tiempo de ejecución considerablemente más lento. Esto se debe a que, para una solución parcial dada, MMS calcula un vector de bordes ponderados equilibrado para cada posible comité aumentado cuando se agrega un nuevo candidato, lo que es computacionalmente caro.

Introducimos una nueva heurística inspirada en seqPhragmen, PhragMMS, que mantiene un tiempo de ejecución comparable al de seqPhragmen, ofrece una garantía de aproximación de factor constante para el objetivo de soporte máximo y satisface PJR. Este es el algoritmo más rápido que se conoce para lograr una garantía de factor constante para el soporte máximo.

La nueva regla electoral: Phragmms

Phragmms es un algoritmo iterativo codicioso que comienza con un comité vacío y alterna entre la heurística Phragmms para insertar un nuevo candidato y el rebalancear mediante la sustitución del vector de pesos por uno equilibrado. La principal diferencia entre Phragmms y seqPhragmen es que este último sólo realiza un reequilibrio aproximado. Los detalles se pueden encontrar en Distribución equilibrada de Stake (descripto supra).

El cómputo es ejecutado por trabajadores fuera de la cadena de forma privada y separada de la producción de bloques, y los validadores sólo necesitan presentar y verificar las soluciones en la cadena. En relación con un comité A, la puntuación de un candidato no elegido c es una estimación aproximada fácil de calcular de cuál sería el tamaño del respaldo del menor staking de apoyo si añadiéramos c al comité A. Observando en la cadena, sólo es necesario seguir una solución en un momento dado, y un productor de bloques puede presentar una nueva solución en el bloque sólo si éste pasa la prueba de verificación, que consiste en comprobar:

1. Viabilidad,
2. Equilibrio, y
3. Optimización local – El menor stake de apoyo de A es mayor que la mayor puntuación entre los candidatos no elegidos

Si la solución provisional supera las pruebas, sustituye a la solución actual como ganadora provisional. La solución ganadora oficial se declara al final de la ventana de elección.

Una característica poderosa de este algoritmo es el hecho de que tanto su garantía de aproximación para el apoyo máximo como la superación de las comprobaciones anteriores pueden verificarse de forma eficiente en tiempo lineal. Esto permite una solución más escalable para las elecciones de comités seguros y proporcionales. Mientras que seqPhragmen también tiene una noción de puntuación para los candidatos no elegidos, Phragmms puede verse como una complicación natural del algoritmo seqPhragmen, donde Phragmms siempre concede valores de puntuación más altos a los candidatos y, por tanto, los inserta con valores de apoyo más altos.

En resumen, las principales diferencias entre las dos reglas son:

• En seqPhragmen, las puntuaciones más bajas son mejores, mientras que en Phragmms, las puntuaciones más altas son mejores.
• Inspirado en seqPhragmen, el sistema de puntuación de Phragmms puede considerarse más intuitivo y hace un mejor trabajo al estimar el valor de agregar un candidato a la solución actual, y por lo tanto conduce a una mejor heurística de selección de candidatos.
• A diferencia de seqPhragmen, en Phragmms, el vector de pesos de bordes w se reequilibra completamente después de cada iteración del algoritmo.

La regla de elección de Phragmms se está implementando actualmente en Polkadot. Una vez completada, se convertirá en una de las reglas electorales más sofisticadas implementadas en una blockchain. Por primera vez, esta regla de elección proporcionará tanto representación justa (PJR) como seguridad (aproximación de factor constante para la objeción de soporte máximo) a una red de blockchain.

Algoritmo

El algoritmo Phragmms itera a través de los escaños disponibles, comenzando con un comité vacío de tamaño k:

1. Inicializa un comité vacío A y un vector de pesos de bordes cero w = 0.
2. Repite k veces:
   1. Encuentra el candidato no elegido con mayor puntuación y lo agrega al comité A.
   2. Reequilibra el vector de pesos w para el nuevo comité A.
3. Devuelve A y w.

Recursos Externos #

• Phragmms – Documento de investigación del W3F que amplía el método secuencial de Phragmén.
• Página de investigación de la W3F sobre NPoS – Una visión general de Nominated Proof of Stake aplicada a Polkadot.
• Implementaciones de referencia en Python – Implementaciones en Python de los métodos Phragmén Simple y Complicado.
• Implementación en Substrate – Implementación en Rust utilizada en Substrate.
• Phragmén’s and Thiele’s Election Methods – Documento de 95 páginas que explica los métodos de elección de Phragmén en detalle.
• Phragmén’s Voting Methods and Justified Representation – Este documento de Brill et al. es la fuente del método simple de Phragmén, junto con pruebas sobre sus propiedades.
• Phragmén offline – Script para generar el resultado de la elección del validador de Phragmén antes del inicio de una era.