P für Phragmén [Polkadot von A bis Z]

Phragmén sind eine Sammlung von Wahlmechanismen mit dem Schwerpunkt auf gerechter Repräsentation, die entweder von Lars Edvard Phragméns Arbeit geschaffen oder von ihm inspiriert wurden. Ende des 19. Jahrhunderts stellte er fest, dass die Sitze im schwedischen Parlament von der populärsten politischen Partei besetzt und Minderheitenparteien nicht vertreten waren. Um eine bessere Vertretung der Wählerinnen und Wähler im Parlament zu erreichen, entwickelte er eine Methode, mit der die Stimmen gerecht auf die Sitze verteilt werden sollten. Diese Methode wurde als Phragmén-Methode bekannt und funktioniert gut bei Wahlen, bei denen es mehrere Gewinner gibt. Da es mehrere Methoden gibt, die mit Lars Phragmén in Verbindung gebracht werden, werde ich in diesem Beitrag über die spezielle Methode sprechen, die in Polkadot verwendet wird, das sogenannte sequentielle Phragmén (seq-Phragmén), und eine neuere Optimierung, die die Sicherheitsqualitäten erhöht und die Repräsentation der Wahlberechtigten verbessert, genannt Phragmms.

Seq-Phragmén und wie wird es in Polkadot verwendet

Eine faire Vertretung ist wichtig, wenn du einen Pool von Validatoren beim Nominated Proof of Stake (NPoS) wählst. Oder bei der Wahl von Ratsmitgliedern. Bei beiden Wahlen gibt es viele Wahlberechtigte mit unterschiedlichem Einsatz, viele Kandidaten, die zu wählen oder zu nominieren sind, und viele verfügbare Sitze im Validator-Pool oder im Rat. Seq-Phragmén hat eine Eigenschaft, die als proportionale gerechtfertigte Repräsentation (PJR) bezeichnet wird und sicherstellt, dass kein Kandidat über- oder unterrepräsentiert ist; es ist eine Methode, die eine faire Verteilung des Einsatzes auf die Kandidaten mit dem höchsten Einsatz findet. Durch die Optimierung der gewählten Kandidaten und die Verteilung des Einsatzes auf die gewählten Kandidaten kommt der Algorithmus den Idealen näher, die eine hohe Sicherheit des Netzwerks, eine bessere Vertretung der Token-Inhaber bei den Wahlen und eine Dezentralisierung der Validatoren und Ratsmitglieder gewährleisten. Der Algorithmus hat zwei wichtige Aufgaben:

1. Wähle die am stärksten unterstützten Kandidaten
   1. Stelle sicher, dass nur die Kandidierenden mit dem größten Rückhalt in die aktive Gruppe der Validatoren oder den Rat gewählt werden.
2. Verteile den Einsatz gleichmäßig unter ihnen
   1. Achte darauf, dass alle eingesetzten DOTs für eine bestimmte Wahl so gleichmäßig wie möglich über die gewählte Gruppe verteilt sind.

NPoS-Validator-Wahlen

Für NPoS muss die Wahl so gestaltet werden, dass die Sicherheit maximiert wird. NPoS-Nominatoren setzen ihre DOTs ein, um Validatoren zu wählen, die Blöcke erzeugen. Da die Sicherheit eines Proof-of-Stake-Netzwerks zum Teil davon abhängt, wie viel Einsatz im System eingesetzt wird und wie dezentralisiert dieser Einsatz unter den Teilnehmern ist, muss eine seq-Phragmén drei Punkte berücksichtigen und diese bei einem gegebenen sinnvollen Berechnungsaufwand so weit wie möglich optimieren. Diese sind:

1. Maximiere den Gesamtbetrag, der auf dem Spiel steht
   1. Das heißt, wähle die Validatoren mit dem stärksten Rückhalt in dem aktiven Set
   2. Mehr eingesetzte DOTs = höhere Sicherheit
2. Maximiere den Einsatz hinter dem Validator mit minimalem Einsatz
   1. Das bedeutet, dass der gesamte Einsatz so gleichmäßig wie möglich auf die gewählten Validatoren verteilt werden soll
   2. Das ist ein NP-hartes Problem, d.h. es ist rechnerisch schwierig und erfordert eine Optimierung
3. Minimiere die Varianz des Einsatzes in der aktiven Menge
   1. Das bedeutet, dass der Unterschied im Einsatz zwischen dem am meisten unterstützten Validator und dem am wenigsten unterstützten Validator minimiert wird
   2. Erhöht die Sicherheit, indem er die Kosten für einen Angriff auf den Validator mit der geringsten Unterstützung erhöht

Die Optimierung dieser Eigenschaften des NPoS-Validator-Sets erhöht die Sicherheit des Netzwerks und den Gewinn, den die Validatoren und Nominatoren erzielen.

Hinweis: NP-harte Probleme sind in der Regel sehr rechenintensiv und erfordern Optimierungen. Bei der Entwicklung von Blockchain-Runtimes ist es wichtig, dass die Berechnungen auf der On-Chain so gering wie möglich gehalten werden oder die Blockproduktion nicht ins Stocken geraten kann.

Ratswahlen

Bei der Wahl der Ratsmitglieder wird ebenfalls das seq-Phragmén verwendet. In jedem Wahlzyklus werden 20 der am meisten unterstützten potenziellen Accounts gewählt, und dann werden die 13 besten in den aktiven Rat gewählt und 7 auf den zweiten Platz.

Hinweis: Die Abstimmung mit dem Einsatz mag auf den ersten Blick undemokratisch erscheinen, aber es ist sehr einfach, ein System ohne Stake-Backed-Voting auf einer pseudonymen Blockchain zu manipulieren. In einem System ohne Stake-Backed-Voting, in dem ein Account eine Stimme hat, könnte eine Person mehrere Accounts erstellen und ihre Stimme demselben Kandidaten geben, sodass es so aussieht, als würden viele Wähler hinter ihm stehen.

Off-Chain Phragmén

Da der Prozess sehr rechenintensiv ist, werden seq-Phragmén vorzugsweise Off-Chain ausgeführt und das Ergebnis über eine Transaktion an die Chain übermittelt. Dies wird von Off-Chain-Workern (OCW) erledigt. Und jeder Validator Node läuft standardmäßig als Off-Chain-Worker. Das bedeutet, dass die Berechnungen auf der Maschine/Hardware des Validators stattfinden und in der Verantwortung der Person liegen, die den Validator betreibt; die Berechnungen finden nicht auf der On-Chain statt. Ein Validator kann die OCW-Option deaktivieren, wenn er das möchte.

Phragmms

Eines der Risiken bei der Vermeidung von Unterrepräsentation ist, dass einige Minderheiten überrepräsentiert sein könnten, was für das Ziel der Dezentralisierung ebenfalls problematisch ist. Phragmms, die nächste Stufe der Verbesserungen, wird eine Wahl ermöglichen, die zu einer nachweislich fairen Vertretung der Kandidatinnen und Kandidaten auf der Grundlage der gegebenen Stimmen und des Einsatzes führt. Phragmms ist zwar immer noch sehr rechenintensiv, aber das Schöne an ihm sind seine starken Verifizierungseigenschaften, die es selbst einer nicht vertrauenswürdigen dritten Partei ermöglichen, die Wahlen privat und außerhalb der Kette durchzuführen und dem Netzwerk zu beweisen, dass die entsprechenden Wahlergebnisse fair und proportional sind. Damit eröffnet sich eine große Chance für die vertrauenslose Berechnung von Off-Chain-Wahlen.

Resources

Das NPoS-Problem mit Phragmén lösen, Video von Kian Paimani

Polkadot Wiki: Sequentielles Phragmén

W3F Forschung: Überblick über NPoS

Das Forschungspapier über Phragmms

Übersetzt von Daredevil3x7 und erstellt mit Unterstützung des Kusama Treasury via WagMedia

Mehr von der ELI5 Serie: Polkadot A bis Z

A für Account [Polkadot von A bis Z]

B for Brücken “Bridges” [Polkadot from A to Z]

C für “Collators” (Kollatoren) [Polkadot von A bis Z]

D für “Democracy” (Demokratie) [Polkadot von A bis Z]

E für Existentielle Einlage [Polkadot von A bis Z]

F für “Forkless” (Gabelfrei) [Polkadot von A bis Z]

G für GRANDPA [Polkadot von A bis Z]

H für Hash [Polkadot von A bis Z]

I für Interoperabilität [Polkadot von A bis Z]

J für Polkadot.js [Polkadot von A bis Z]

K für Kusama [Polkadot von A bis Z]

L für Polkadot Launch [Polkadot von A bis Z]

M für Multisig [Polkadot von A bis Z]

O für On-Chain Governance [Polkadot von A bis Z]

P für Phragmén [Polkadot von A bis Z]