Das Stellar-Konsensprotokoll wurde erstmals beschrieben von David Mazieres im Jahr 2015. Es handelt sich um ein „federiertes System des byzantinischen Konsenses“, das es dezentralen Rechennetzen ohne führende Instanzen ermöglicht, effektiv einen Konsens über Entscheidungen zu erreichen. Das Zahlungsnetzwerk Stellar verwendet das Stellar Consensus Protocol (SCP), um eine konsistente Historie von Transaktionen zu führen, die allen Teilnehmern sichtbar ist.
Es wird angenommen, dass Konsensprotokolle schwer zu verstehen sind. SCP ist einfacher als die meisten, hat jedoch dennoch diesen Ruf, teilweise aufgrund der irreführenden Vorstellung, dass „federierte Abstimmung“, die in der ersten Hälfte der wissenschaftlichen Arbeit behandelt wird, SCP ist. Das ist jedoch nicht der Fall! Es ist lediglich ein wichtiger Baustein, der in der zweiten Hälfte der Arbeit verwendet wird, um das tatsächliche Stellar-Konsensprotokoll zu erstellen.
In diesem Artikel werden wir kurz erläutern, was ein „Abkommenssystem“ ist, was es „byzantinisch“ machen kann und warum man ein byzantinisches System „federiert“ gestalten sollte. Dann erklären wir das federative Abst verfahren, das in der SCP-Arbeit beschrieben wird, und schließlich erläutern wir das Protokoll SCP selbst.
Abkommenssysteme
Das Vereinbarungssystem ermöglicht es einer Gruppe von Teilnehmern, zu einem Konsens zu kommen, beispielsweise dazu, was wir zum Mittagessen bestellen sollten.
Wir bei Interstellar haben unser eigenes Mittagessen-Vereinbarungssystem eingeführt: Wir bestellen das, was unser Operationsmanager John vorschlägt. Es ist ein einfaches und effektives System. Wir vertrauen John und glauben, dass er jeden Tag etwas Interessantes und Nahrhaftes findet.
Aber was, wenn John unser Vertrauen missbraucht? Er könnte einseitig entscheiden, dass wir alle Veganer werden sollten. In ein oder zwei Wochen würden wir ihn wahrscheinlich stürzen und die Verantwortung an Elizabeth übergeben. Aber was ist, wenn sie Avocado mit Sardellen liebt und denkt, dass das für alle das Richtige ist? Macht verdirbt. Daher wäre es besser, eine demokratischere Methode zu finden: eine Möglichkeit sicherzustellen, dass verschiedene Vorlieben berücksichtigt werden, während ein zeitnahes und eindeutiges Ergebnis erzielt wird, damit nicht am Ende niemand das Mittagessen bestellt oder fünf verschiedene Bestellungen aufgegeben werden, oder die Diskussion bis zum Abend dauert.
Es scheint eine einfache Lösung zu sein: eine Abstimmung durchzuführen! Doch dieser Eindruck täuscht. Wer wird die Stimmzettel einsammeln und die Ergebnisse mitteilen? Und warum sollten die anderen dem, was er sagt, glauben? Vielleicht können wir zuerst für einen vertrauenswürdigen Führer stimmen, der die Abstimmung leitet – aber wer wird diese erste Abstimmung leiten? Was ist, wenn wir uns nicht auf einen Führer einigen können? Oder wenn wir uns einig sind, dieser Führer aber in einem Meeting festhängt oder krank wird?
Ähnliche Probleme treten in verteilten Computersystemen auf. Alle Teilnehmer oder Knoten müssen eine Entscheidung treffen, beispielsweise, wer den gemeinsamen Datei aktualisieren oder eine Aufgabe aus der Warteschlange abrufen darf. In einem Kryptowährungsnetzwerk müssen die Knoten wiederholt auswählen, wie die vollständige Geschichte aus mehreren möglichen Versionen aussieht, die manchmal miteinander in Konflikt stehen. Dieses Netzwerkprotokoll stellt dem Empfänger sicher, dass die Münze (a) gültig (nicht gefälscht) ist und (b) noch nicht an anderer Stelle ausgegeben wurde. Es garantiert auch, dass er die Münzen in der Zukunft ausgeben kann, da der neue Empfänger die gleichen Garantien aus den gleichen Gründen haben wird.
Jedes Konsenssystem in einem verteilten Rechennetzwerk muss ausfallsicher sein: Es muss konsistente Ergebnisse liefern, trotz Fehlern wie langsamen Kommunikationsleitungen, nicht reagierenden Knoten und falscher Reihenfolge der Nachrichten. Byzantinisch Das Konsenssystem ist zusätzlich resistent gegenüber »byzantinischen« Fehlern: Knoten, die falsche Informationen liefern, sei es durch einen Fehler oder in einem absichtlichen Versuch, das System zu untergraben oder sich einen Vorteil zu verschaffen. Die »byzantinische« Fehlertoleranz – die Fähigkeit, einer Gruppenzusammenkunft zu vertrauen, selbst wenn einige Mitglieder der Gruppe lügen oder die Entscheidungsregeln nicht einhalten – hat ihren Namen von , die versuchten, einen Angriff zu koordinieren. von Anthony Stevens.
Betrachten wir die Krypto-Besitzerin Alice, die zwischen dem Kauf von leckerem Eis bei Bob und der Begleichung einer Schuld bei Carol wählen muss. Möglicherweise möchte Alice beide gleichzeitig bezahlen, indem sie dieselbe Münze betrügerisch ausgibt. Dazu muss sie den Computer von Bob überzeugen, dass die Münze niemals an Carol ausgezahlt wurde, und den Computer von Carol überzeugen, dass die Münze niemals an Bob ausgezahlt wurde. Das byzantinische Konsenssystem macht dies praktisch unmöglich, indem es eine Form der Mehrheitsregel verwendet, die als Quorum. Ein Knoten in einem solchen Netzwerk weigert sich, auf eine bestimmte Version der Historie zu wechseln, bis er sieht, dass eine ausreichende Anzahl von Peer-Knoten — ein Quorum — diesem Wechsel zustimmt. Sobald dies geschieht, bilden sie einen ausreichend großen Wahlblock, um die verbleibenden Knoten im Netzwerk zu zwingen, ihrer Entscheidung zuzustimmen. Alice kann einige Knoten dazu bringen, in ihrem Namen zu lügen, aber wenn das Netzwerk groß genug ist, wird ihr Versuch durch die Stimmen ehrlicher Knoten unterdrückt.
Wie viele Knoten sind für ein Quorum erforderlich? Mindestens die Mehrheit, genauer gesagt eine qualifizierte Mehrheit, um Fehler und Betrug zu bekämpfen. Um jedoch die Mehrheit zu zählen, muss man die Gesamtzahl der Teilnehmer kennen. Im Büro Interstellar oder bei Kommunalwahlen sind diese Zahlen leicht zu ermitteln. Aber wenn Ihre Gruppe ein schwach definiertes Netzwerk ist, in das Knoten nach Belieben ein- und austreten können, ohne mit einem Zentrum abzustimmen, dann benötigt man eine föderative Ein System von byzantinischen Vereinbarungen, das in der Lage ist, Quoren nicht aus einer vorab definierten Liste von Knoten zu bestimmen, sondern dynamisch aus einem ständig wechselnden und unvermeidlich unvollständigen Snapshot von Knoten zu einem bestimmten Zeitpunkt.
Es mag unmöglich erscheinen, ein Quorum aus der Sicht eines einzelnen Knotens in einem umfassenden Netzwerk zu schaffen, aber das ist möglich. Ein solches Quorum kann sogar die Ergebnisse einer dezentralen Abstimmung garantieren. Das technische Dokument SCP zeigt, wie dies mit einem Verfahren namens föderativer Abstimmung.
Für Ungeduldige
Der Rest des Artikels beschreibt genauer die föderative Abstimmung und das Stellar-Konsensprotokoll. Wenn Sie an Details nicht interessiert sind, finden Sie hier einen allgemeinen Überblick über den Prozess.
- Knoten führen Runden der föderativen Abstimmung über „Nominierungen“ durch. Eine Runde der föderativen Abstimmung bedeutet:
- Ein Knoten stimmt über eine Behauptung ab, wie z.B. „Ich schlage den Wert V vor“;
- Ein Knoten hört die Stimmen der Peers, bis er einen findet, der „annehmen“ kann;
- Ein Knoten sucht nach einem „Quorum“ für diese Behauptung. Das Quorum „bestätigt“ den Nominanten.
- Sobald der Knoten einen oder mehrere Nominierte bestätigen kann, versucht er, den "Wahlzettel" durch mehrere Runden föderativer Abstimmung "vorzubereiten".
- Sobald der Knoten in der Lage ist, die Bereitschaft des Wahlzettels zu überprüfen, versucht er, ihn durch noch mehr Runden föderativer Abstimmung zu committen.
- Sobald der Knoten den Commit des Wahlzettels bestätigen kann, kann er den Wert dieses Wahlzettels "externeren", indem er ihn als Ergebnis des Konsenses verwendet.
Diese Schritte beinhalten mehrere Runden föderativer Abstimmung, die zusammen eine Runde SCP bilden. Lassen Sie uns näher betrachten, was in jedem Schritt passiert.
Föderative Abstimmung
Die föderative Abstimmung ist ein Verfahren zur Feststellung, ob das Netzwerk einem Vorschlag zustimmen kann. In der Abstimmungsrunde muss jeder Knoten einen aus potenziell vielen möglichen Werten auswählen. Er kann dies nicht tun, solange er sich nicht sicher ist, dass andere Knoten im Netzwerk nicht ein anderes Ergebnis wählen. Um sicherzustellen, dass dies der Fall ist, tauschen die Knoten eine Flut von Nachrichten hin und her, sodass jeder hat bestätigt, dass Quorum Knoten nimmt dasselbe wählt. Lösung. Der restliche Teil dieses Abschnitts erklärt die Begriffe in diesem Satz und wie das gesamte Verfahren abläuft.
Quoren und Quorum-Slices
Fangen wir mit der Definition des Quorums an. Wie oben diskutiert, ist es in einem dezentralisierten Netzwerk mit dynamischer Mitgliedschaft unmöglich, im Voraus die Anzahl der Knoten zu kennen und somit zu bestimmen, wie viele für die Mehrheit erforderlich sind. Das föderierte Abstimmen löst dieses Problem, indem es eine neue Idee präsentiert. Quorum-Slice (quorum slice): eine kleine Menge von gleichrangigen Knoten, denen ein Knoten vertraut, um Informationen über den Abstimmungsstatus im Rest des Netzwerks zu übertragen. Jeder Knoten definiert sein eigenes Quorum-Slice (dem er faktisch angehört).
Die Bildung des Quorums beginnt mit dem Quorum-Slice. Zu jedem Knoten werden die Knoten seines Slices hinzugefügt. Dann werden die Mitglieder der Slices dieser Knoten usw. Im Verlauf des Prozesses werden immer mehr Knoten erreicht, die Sie nicht hinzufügen können, weil sie bereits im Slice enthalten sind. Wenn es keine neuen Knoten mehr zum Hinzufügen gibt, wird der Prozess gestoppt: Wir haben ein Quorum durch 'transitive Closure' des Quorum-Slices des ursprünglichen Knotens gebildet.
Um ein Quorum aus diesem Knoten zu finden…
… fügen wir Mitglieder seines Slices hinzu…
… dann fügen wir Mitglieder der Slices dieser Knoten hinzu.
Wir machen weiter, bis keine Knoten mehr hinzuzufügen sind.
Es sind keine Knoten mehr zum Hinzufügen vorhanden. Das ist das Quorum.
Tatsächlich kann jeder Knoten in mehr als einem Slice sein. Um ein Quorum zu bilden, wählen Sie nur einen der Slices aus und fügen Sie Mitglieder hinzu; wählen Sie dann einen Slice für jedes Mitglied und fügen Sie Mitglieder hinzu dieses Ergebnis herauskommt des Slices usw. Das bedeutet, dass jeder Knoten Teil vieler möglicher Quoren ist.
Wählen Sie bei jedem Schritt nur einen Slice des Quorums aus.
Ein mögliches Quorum. Oder eine alternative Option…
… wählen wir andere Slices aus…
… (wenn möglich)…
… erzeugt ein anderes Quorum.
Wie erkennt ein Knoten, in welchen Slices andere Knoten enthalten sind? Genau wie andere Informationen über andere Knoten: aus Übertragungen, die jeder Knoten ins Netzwerk sendet, wenn sich sein Abstimmungsverhalten ändert. Jede Übertragung enthält Informationen über die Slices des sendenden Knotens. Im technischen Dokument SCP wird der Kommunikationsmechanismus nicht angegeben. Implementierungen verwenden in der Regel für die garantierte Übertragung von Nachrichten im gesamten Netzwerk.
Wir erinnern daran, dass in einem nicht-föderativen byzantinischen Konsenssystem das Quorum als die Mehrheit aller Knoten definiert ist. Das byzantinische Konsenssystem wurde mit der Frage entwickelt: Wie viele unehrliche Knoten kann das System tolerieren? In einem System mit N Knoten, das auf das Überleben bei f Ausfällen (Betrügereien) ausgelegt ist, muss ein Knoten in der Lage sein, Fortschritte zu erzielen, indem er Antworten von N−f Peer-Knoten erhält, da f von ihnen möglicherweise nicht funktionsfähig sind. Wenn der Knoten Antworten von N−f Peers erhält, kann man annehmen, dass alle f Peers (von denen der Knoten keine Antwort erhalten hat) tatsächlich ehrlich sind. So sind die schädlichen Knoten f aus den N−f Peers (von denen eine Antwort erhalten wurde). Damit die Knoten zu einem konsistenten Konsens kommen, muss die Mehrheit der restlichen Knoten ehrlich sein; das bedeutet, dass wir benötigen, dass N−f größer ist als 2f oder N > 3f. Daher hat ein System, das auf Überleben bei f Ausfällen ausgelegt ist, normalerweise insgesamt N=3f+1 Knoten und eine Quorumgröße von 2f+1. Sobald ein Vorschlag die Quorumgrenze überschreitet, sind die anderen Mitglieder des Netzwerks davon überzeugt, dass alle konkurrierenden Vorschläge scheitern werden. So konvergiert das Netzwerk zu einem Ergebnis.
In einem föderativen byzantinischen System von Vereinbarungen kann es nicht nur keine Mehrheit geben (weil niemand die Gesamtgröße des Netzwerks kennt), sondern das Konzept der Mehrheit ist completamente nutzlos! Wenn die Mitgliedschaft im System offen ist, kann jemand die Mehrheit einfach erlangen, indem er einen sogenannten Sybil-Angriff durchführt: mehrmals durch verschiedene Knoten dem Netzwerk beitritt. Warum kann also die transitive Schließung eines Schnitts genannt werden Quorum, und wie ist sie in der Lage, konkurrierende Vorschläge zu unterdrücken?
Technisch gesehen, überhaupt nicht! Stellen Sie sich ein Netzwerk mit sechs Knoten vor, in dem zwei Gruppen jeweils in den Quorum-Schnitten des anderen isoliert sind. Die erste Untergruppe kann eine Entscheidung treffen, von der die zweite niemals erfahren wird, und umgekehrt. Für dieses Netzwerk gibt es keinen Weg, Konsens zu erreichen (außer zufällig).
Deshalb verlangt SCP, dass für eine föderative Abstimmung (und zur Anwendung wichtiger Theoreme des Artikels) das Netzwerk über eine Eigenschaft verfügen muss, die genannt wird Quorum-Schnitte.. In einem Netzwerk mit dieser Eigenschaft überschneiden sich immer mindestens zwei Quoren an einem Knotenpunkt. Um die vorherrschenden Meinungen im Netzwerk zu bestimmen, ist dies ebenso effektiv wie eine Mehrheit zu haben. Intuitiv bedeutet dies, dass, wenn ein Quorum einer Aussage X zustimmt, kein anderes Quorum jemals etwas anderes zustimmen kann, da es zwangsläufig einen Knoten aus dem ersten Quorum enthält, der bereits für X abgestimmt hat.
Wenn es im Netzwerk Überschneidungen von Quoren gibt…
…dann überschneiden sich immer beide Quoren, die Sie bilden können…
…und werden stets überlappen.
(Natürlich können sich die überlappenden Knoten als byzantinisch-falsch oder in anderer Hinsicht fehlerhaft herausstellen. In diesem Fall hilft das Überschneiden von Quoren dem Netzwerk überhaupt nicht, sich zu verständigen. Aus diesem Grund basieren viele Ergebnisse im technischen Dokument SCP auf expliziten Annahmen, dass im Netzwerk auch nach dem Entfernen von schlechten Knoten ein Überschneidungsquorum verbleibt. Um der Einfachheit willen lassen wir diese Annahmenin der restlichen Artikel unkenntlich über.
Es mag unvernünftig erscheinen, zu erwarten, dass in einem Netzwerk von unabhängigen Knoten eine zuverlässige Quorum-Überschneidung möglich ist. Doch es gibt zwei Gründe, warum dies der Fall ist.
Der erste Grund liegt in der Existenz des Internets selbst. Das Internet ist ein ideales Beispiel für ein Netzwerk unabhängiger Knoten mit Quorum-Überschneidungen. Die meisten Knoten im Internet verbinden sich nur mit einigen wenigen anderen lokalen Knoten, aber diese kleinen Mengen überschneiden sich ausreichend, sodass jeder Knoten von jedem anderen Knoten über einen bestimmten Weg erreichbar ist.
Der zweite Grund ist spezifisch für das Zahlungsnetzwerk Stellar (die häufigste Anwendung von SCP). Jedes Asset im Stellar-Netzwerk hat einen Emittenten, und die Empfehlungen von Stellar verlangen, dass jeder Emittent einen oder mehrere Knoten im Netzwerk bestimmt, um Rückzahlungsanfragen zu bearbeiten. Es liegt in Ihrem Interesse, diese Knoten direkt oder indirekt in die Quorum-Schnitte für jedes interessierende Asset aufzunehmen. Die Quoren für alle Knoten, die an einem bestimmten Asset interessiert sind, werden sich dann mindestens in diesen Rückzahlungsknoten überlappen. Knoten, die an mehreren Assets interessiert sind, werden in ihren Quorum-Schnitten alle Rückzahlungsknoten der entsprechenden Emittenten aufnehmen und versuchen, alle Assets zusammenzuführen. Zudem sollten alle Assets, die nicht auf diese Weise mit anderen im Netzwerk verbunden sind, nicht verbunden sein — so ist es beabsichtigt, dass es für dieses Netzwerk keine Quorum-Überlappungen gibt (zum Beispiel möchten Banken aus dem Dollarraum manchmal mit Banken aus dem Euroraum und Banken aus dem Peso-Raum handeln, daher befinden sie sich im selben Netzwerk, aber es interessiert keinen von ihnen, dass es ein separates Netzwerk von Kindern gibt, die mit Baseballkarten handeln).
Natürlich Warten Die Überschneidungen von Quoren sind kein Garantie. Andere byzantinische Konsenssysteme verdanken ihre Komplexität weitgehend der Garantie von Quoren. Eine wichtige Neuerung von SCP besteht darin, dass es die Verantwortung für die Schaffung von Quoren vom Konsensalgorithmus auf die Anwendungsebene verlagert. Daher hängt die Zuverlässigkeit des föderierten Abstimmens, obwohl es allgemein für die Abstimmung über verschiedene Fragen verwendet wird, stark von den umfassenderen Bedeutungen dieser Werte ab. Bestimmte hypothetische Nutzungsszenarien könnten sich als weniger geeignet erweisen, um gut vernetzte Netzwerke zu erstellen, als andere.
Abstimmung, Annahme und Bestätigung
In der Runde des föderierten Abstimmens beginnt der Knoten wahlweise für einen bestimmten Wert V zu stimmen. Das bedeutet, dass eine Nachricht ins Netzwerk gesendet wird: „Ich bin Knoten N, meine Quoren-Schnitte sind Q, und ich stimme für V.“ Wenn ein Knoten auf diese Weise abstimmt, verspricht er, dass er niemals gegen V gestimmt hat und auch niemals dagegen stimmen wird.
In Peer-to-Peer-Übertragungen sieht jeder Knoten, wie andere abstimmen. Sobald ein Knoten genügend dieser Nachrichten gesammelt hat, kann er die Quorum-Schnitte verfolgen und versuchen, Quoren zu finden. Wenn er ein Quorum von Peers sieht, die ebenfalls für V stimmen, kann er zu der Annahme von V übergehen und diese neue Nachricht ins Netzwerk übertragen: «Ich bin Knoten N, meine Quorum-Schnitte Q, und ich nehme V an». Die Annahme bietet eine stärkere Garantie als einfaches Abstimmen. Wenn ein Knoten für V stimmt, kann er nie für andere Optionen stimmen. Aber wenn ein Knoten V annimmt, wird kein Knoten im Netzwerk jemals eine andere Option annehmen (Theorem 8 im technischen Dokument SCP beweist dies).
Natürlich besteht eine hohe Wahrscheinlichkeit, dass sofort kein Knotenquorum gefunden wird, das mit V übereinstimmt. Andere Knoten könnten für andere Werte stimmen. Aber es gibt für den Knoten einen weiteren Weg, um von einfacher Abstimmung zur Annahme überzugehen. N kann einen anderen Wert W annehmen, auch wenn er nicht dafür gestimmt hat und selbst wenn er kein Quorum dafür sieht. Um seine Stimme zu ändern, reicht es aus, zu sehen, dass eine blockierende Menge existiert. Knoten, die W akzeptieren. Eine blockierende Menge besteht aus einem Knoten jeder Quorum-Scheibe von N. Wie der Name schon sagt, ist sie in der Lage, zu blockieren jeden anderen Wert. Wenn alle Knoten in einer solchen Menge W akzeptieren, dann kann (nach Theorem 8) nie ein Quorum gebildet werden, das einen anderen Wert akzeptiert, und daher ist es für N auch sicher, W zu akzeptieren.
Knoten N mit drei Quorum-Schnitten.
B-D-F ist eine blockierende Menge für N: Sie umfasst einen Knoten jeder Scheibe von N.
B-E ist ebenfalls eine blockierende Menge für N, da E in zwei Scheiben von N erscheint.
Ein blockierendes Set stellt jedoch kein Quorum dar. Es wäre zu einfach, einen Knoten N zu täuschen, sodass er den gewünschten Wert annimmt, wenn es ausreicht, nur einen Knoten in jedem Schnitt N zu kompromittieren. Daher ist die Annahme eines Wertes noch nicht das Ende der Abstimmung. Stattdessen muss N den Wert bestätigen, das heißt, er muss ein Quorum von Knoten sehen, die ihn akzeptieren. Wenn er so weit kommt, wird, wie im technischen Dokument SCP (in Theorem 11) nachgewiesen, der Rest des Netzwerks letztendlich denselben Wert bestätigen, sodass N die föderative Abstimmung mit einem bestimmten Wert als Ergebnis abschließt.
Föderative Abstimmung.
Der Prozess der Abstimmung, Annahme und Bestätigung bildet eine vollständige Runde der föderativen Abstimmung. Das Stellar-Konsensprotokoll kombiniert viele solcher Runden, um ein vollständiges Konsenssystem zu schaffen.
Stellar-Konsensprotokoll
Die zwei wichtigsten Eigenschaften eines Konsenssystems sind Sicherheit und Robustheit. Der Konsensalgorithmus ist «sicher», wenn er niemals unterschiedlichen Teilnehmern unterschiedliche Ergebnisse liefern kann (die Kopie von Bobs Geschichte wird niemals mit Carols widersprechen). „Robustheit“ bedeutet, dass der Algorithmus immer ein Ergebnis liefert, also nicht hängen bleibt.
Das beschriebene Verfahren der föderierten Abstimmung ist sicher im Sinne, dass, wenn ein Knoten den Wert V bestätigt, kein anderer Knoten einen anderen Wert bestätigen wird. Aber „nicht einen anderen Wert bestätigen“ bedeutet nicht, dass er unbedingt etwas bestätigen wird. Die Teilnehmer können für so viele verschiedene Werte stimmen, dass keiner den Annahmegrenzwert erreicht. Das bedeutet, dass bei der föderierten Abstimmung eine Abwesenheit von Robustheit.
Das Stellar-Konsensprotokoll verwendet föderatives Abstimmen, um sowohl Sicherheit als auch Resilienz zu gewährleisten. (Die Sicherheits- und Resilienzgarantien des SCP haben theoretische Grenzen. Das Design wählt eine sehr starke Sicherheitsgarantie und opfert dabei ein wenig Resilienz, aber bei ausreichender Zeit wird mit hoher Wahrscheinlichkeit ein Konsens erreicht.) Kurz gesagt, die Idee besteht darin, mehrere föderative Abstimmungen über mehrere Werte durchzuführen, bis einer von ihnen alle Phasen des SCP-Abstimmungsverfahrens vollständig durchläuft, die weiter unten beschrieben sind.
Die Werte, zu denen SCP Konsens anstrebt, können eine Transaktionshistorie, eine Bestellung zum Mittagessen oder etwas anderes sein, aber es ist wichtig zu beachten, dass dies nicht die Werte sind, die akzeptiert oder bestätigt werden. Stattdessen erfolgt das föderative Abstimmen über Aussagen über diese Werte..
Die ersten Runden des föderativen Abstimmens finden in der Nominierungsphase statt. (Nominierungsphase), bei der eine Vielzahl von Erklärungen des Typs „Ich schlage V vor“ gesammelt wird, möglicherweise für viele verschiedene Bedeutungen von V. Das Ziel der Nominierung ist es, eine oder mehrere Erklärungen zu finden, die eine Annahme und Bestätigung durchlaufen.
Nach der Identifizierung bestätigbarer Kandidaten geht SCP in die Abstimmungsphase über, wo das Ziel darin besteht, einen Wahlzettel (also einen Container für den vorgeschlagenen Wert) und ein Quorum zu finden, das ihn bekannt geben kann (commit). Wenn das Quorum den Wahlzettel commit, wird dessen Wert als Konsens akzeptiert. Aber bevor ein Knoten für das Commit des Wahlzettels stimmen kann, muss er zuerst die Commit für ihn (commit). Wenn das Quorum den Bulletin-Commit macht, wird dessen Wert als Konsens akzeptiert. Doch bevor ein Knoten für den Bulletin-Commit stimmen kann, muss er ihn zuerst bestätigen. Stornierung aller Wahlzettel mit geringerem Zählerwert bestätigen. Diese Schritte – die Stornierung der Wahlzettel, um den zu finden, für den ein Commit bestätigt werden kann – beinhalten mehrere Runden föderativer Abstimmungen über verschiedene Wahlzettel-Erklärungen.
In den folgenden Absätzen werden Nominierung und Abstimmung ausführlicher behandelt.
Nominierung
Zu Beginn der Abstimmungsphase kann jeder Knoten spontan einen Wert V wählen und für die Aussage „Ich schlage V vor“ stimmen. Ziel in dieser Phase ist es, die Nominierung eines bestimmten Wertes durch föderatives Abstimmen zu bestätigen.
Es ist möglich, dass eine ausreichende Anzahl von Knoten für ausreichend unterschiedliche Vorschläge stimmt und kein Vorschlag die Schwelle zur Annahme erreichen kann. Daher reflektieren Knoten neben ihren eigenen Nominierungsstimmen auch die Nominierungen ihrer Nachbarn. Die Reflexion bedeutet, dass, wenn ein Knoten für den Vorschlag V stimmt, aber eine Nachricht von einem Nachbarn sieht, der für den Vorschlag W stimmt, er nun sowohl für den Vorschlag V als auch für den Vorschlag W stimmen wird. (Nicht alle Stimmen der Nachbarn werden während der Nominierung reflektiert, da dies zu einer Explosion verschiedener Nominierten führen könnte. SCP umfasst einen Mechanismus zur Regulierung dieser Stimmen. Kurz gesagt, es gibt eine Formel zur Bestimmung der „Priorität“ eines Nachbarn aus der Sicht eines Knotens, und es werden nur die Stimmen von hochpriorisierten Knoten reflektiert. Je länger die Nominierung dauert, desto niedriger ist die Schwelle, sodass der Knoten den Satz von Nachbarn erweitert, deren Stimmen er reflektieren wird. Die Prioritätsformel enthält als einen der Eingabewerte die Slotnummer, sodass ein hochpriorisierter Peer für einen Slot für einen anderen niedrigpriorisiert sein kann und umgekehrt).
Das gleichzeitige Einbringen von V und W ist konzeptionell als separate föderative Stimmen zu verstehen, die jeweils unabhängig zur Annahme oder Bestätigung fähig sind. In der Praxis verpackt das SCP-Protokoll diese einzelnen Stimmen zusammen.
Obwohl die Abstimmung für die Nominierung von V ein Versprechen ist, niemals gegen die Nominierung von V zu stimmen, wird auf Anwendungsebene – in diesem Fall SCP – festgelegt, was 'dagegen' bedeutet. SCP erkennt keine Erklärung, die der Abstimmung 'Ich nenne X' widerspricht, das heißt, es gibt keine Nachricht 'Ich bin gegen die Nominierung von X', weswegen der Knoten für jede Nominierung stimmen kann. Viele dieser Nominierungen werden zu nichts führen, aber letztendlich kann der Knoten einen oder mehrere Werte annehmen oder bestätigen. Sobald der Nominierte bestätigt ist, wird er ein Kandidat.
Die Nominierung von SCP mit föderativer Abstimmung. Es können viele Werte "B" von gleichrangigen Knoten vorgeschlagen und vom Knoten "reflektiert" werden.
Die Nominierung von Kandidaten kann zu mehreren bestätigbaren Kandidaten führen. Daher verlangt SCP, dass die Anwendungsebene eine Methode zur Zusammenführung der Kandidaten in eine Einheit bereitstellt. komposit (composite). Die Methode der Zusammenführung kann beliebig sein. Wichtig ist, dass wenn diese Methode deterministisch ist, jeder Knoten dieselben Kandidaten zusammenführt. In einem Abstimmungssystem für Mittagessen könnte „Zusammenführung“ einfach bedeuten, dass einer von zwei Kandidaten abgelehnt wird. (Aber deterministisch: Jeder Knoten muss denselben Wert für die Ablehnung auswählen. Zum Beispiel die frühere Wahl in alphabetischer Reihenfolge). In der Zahlungsnetzwerk Stellar, wo über die Historie von Transaktionen abgestimmt wird, bedeutet die Zusammenführung von zwei vorgeschlagenen Nominierungen die Zusammenführung der Transaktionen, die sie enthalten, sowie der letzten ihrer beiden Zeitstempel.
Die technische Beschreibung von SCP beweist (Theorem 12), dass das Netzwerk am Ende der Phase der Kandidatenbildung schließlich zu einem einzigen Komposit konvergiert. Doch es gibt ein Problem: das föderale Abstimmen ist ein asynchrones Protokoll (wie auch SCP). Mit anderen Worten, die Knoten sind nicht zeitlich koordiniert, sondern nur durch die gesendeten Nachrichten. Aus der Perspektive eines Knotens ist unklar, wann die Phase der Kandidatenbildung abgeschlossen ist. Und obwohl alle Knoten letztlich zu demselben Komposit gelangen, können sie unterschiedliche Wege auf diesem Pfad wählen, was zu verschiedenen Kandidaten führt, und sie können nie sicher sagen, welcher von ihnen der endgültige ist.
Aber das ist in Ordnung. Die Kandidatenbildung ist nur eine Vorbereitung. Es ist wichtig, die Anzahl der Kandidaten zu begrenzen, um den Konsens zu erreichen, der im Prozess der Abstimmung erreicht wird.
Abstimmung
Ein Bulletin ist ein Paar , wobei counter eine ganze Zahl ist, die bei 1 beginnt, und value der Kandidat aus der Nominierungsphase. Dies kann ein eigener Knoten-Kandidat oder ein Nachbarkandidat sein, der von diesem Knoten angenommen wird. Grob gesagt, beim Wählen werden wiederholt Versuche unternommen, das Netzwerk dazu zu bringen, Konsens über einen bestimmten Kandidaten in einem bestimmten Bulletin zu erreichen, indem potenziell viele föderale Abstimmungen über die Bulletinanträge durchgeführt werden. Die Zähler in den Bulletinen verfolgen die unternommenen Versuche, und Bulletins mit höheren Zählern haben Vorrang vor Bulletins mit niedrigeren Zählern. Wenn das Bulletin feststeckt, beginnt eine neue Abstimmung, jetzt über das Bulletin .
Es ist wichtig zu unterscheiden zwischen den Werten (zum Beispiel, was die Bestellungen zum Mittagessen betreffen: Pizza oder Salate), Bulletinen (Paar counter-value) und Anträgen zu Bulletins. Eine SCP-Runde umfasst mehrere Runden föderaler Abstimmungen, insbesondere zu solchen Anträgen:
- "Ich bin bereit, das Bulletin B zu committen" und
- "Ich erkläre das Commit des Bulletins B".
Aus der Sicht dieses Knotens wird Konsens erreicht, wenn er das Bulletin B findet, für das er bestätigen kann (d.h. ein Quorum finden kann, das annehmbare Aussagen trifft) "Ich erkläre das Commit für das Bulletin B". Ab diesem Punkt kann man sicher nach der Bedeutung von B handeln – beispielsweise die Bestellung des Mittagessens aufgeben. Dies wird genannt Externalisierung von Werten. Sobald die Annahme des Bulletins bestätigt ist, kann der Knoten sich darauf verlassen, dass jeder andere Knoten diesen Wert externisiert hat oder dies in Zukunft sicher tun wird.
Obwohl konzeptionell viele föderale Abstimmungen zu Erklärungen zu zahlreichen verschiedenen Bulletins stattfinden, tauschen sie nicht so viele Nachrichten aus, weil jede Nachricht eine Reihe von Bulletins verkapselt. Eine Nachricht fördert somit den Status vieler föderaler Abstimmungen gleichzeitig, z.B.: "Ich akzeptiere das Commit der Bulletins im Bereich von bis ".
Was bedeuten die Begriffe „prepared“ (vorbereitet) und „commit“ (commit)?
Ein Knoten stimmt für das Commit eines Protokolls, wenn er überzeugt ist, dass andere Knoten nicht Protokolle mit anderen Werten committen werden. Diese Überzeugung ist das Ziel der Vorbereitungserklärung. Eine Abstimmung, die besagt: „Ich bin bereit, ein Protokoll B zu commiten“, ist ein Versprechen, niemals ein Protokoll mit einem niedrigeren Wert als B zu committen, d. h. mit einem niedrigeren Zähler (SCP verlangt, dass die Werte in den Protokollen eine bestimmte Reihenfolge haben. So ist das Protokoll kleiner als , wenn N1<N2, oder auch wenn N1=N2 und V1<V2). Diese kleineren Protokolle werden während der vorbereitenden Abstimmung „abgebrochen“ (aborted), während B als „vorbereitet“ gilt.
Warum bedeutet „Ich bin bereit, ein Protokoll B zu commiten“, dass ich verspreche, niemals Protokolle mit einem Wert kleiner als B zuzulassen? Weil SCP abort als das Gegenteil von commit definiert. Die Abstimmung zur Vorbereitung eines Protokolls impliziert auch eine Abstimmung zum Widerruf anderer Protokolle, und, wie bereits erwähnt, ist das Abstimmen für etwas ein Versprechen, niemals dagegen zu stimmen.
Bevor ein Knoten einen Commit überträgt, muss er zunächst eine Abstimmung finden, die er als vorbereitet bestätigen kann. Mit anderen Worten, er führt eine föderative Abstimmung zum Thema „Ich bin bereit, das Abstimmungsbulletin B zu committen“, möglicherweise für viele verschiedene Abstimmungsbulletins, bis er eines findet, das ein Quorum akzeptiert.
Woher stammen die Abstimmungsbulletins für die Vorbereitung der Abstimmung? Zunächst überträgt der Knoten die Vorbereitung für die Abstimmung über , wobei C der Kandidat-Komposit ist, der in der Nominierungsphase erstellt wurde. Allerdings kann das Nominierungsverfahren, selbst nachdem die Vorbereitungen für die Abstimmung begonnen haben, zusätzliche Kandidaten hervorbringen, die neue Abstimmungsbulletins werden. In der Zwischenzeit können die Peers unterschiedliche Kandidaten haben und ein blockierendes Set bilden, das „Ich bin bereit, das Abstimmungsbulletin B2 zu committen“ akzeptiert, was den Knoten überzeugt, dies ebenfalls zu akzeptieren. Schließlich gibt es einen Timer-Mechanismus, der neue Runden der föderativen Abstimmung mit neuen Abstimmungsbulletins und höheren Zählern generiert, falls die aktuellen Abstimmungsbulletins feststecken.
Sobald ein Knoten das Bulletin B findet, das als vorbereitet bestätigt werden kann, sendet er die neue Nachricht "Commit Bulletin B". Diese Abstimmung signalisiert den Peers, dass der Knoten niemals von B abweichen wird. Tatsächlich bedeutet, wenn B ein Bulletin darstellt, dass "Commit Bulletin " uneingeschränkte Zustimmung signalisiert, für die Bereitschaft jedes Bulletins von bis . Diese zusätzliche Bedeutung hilft anderen Knoten, mit dem Commit des Peers aufzuholen, falls sie sich noch in früheren Phasen des Protokolls befinden.
An dieser Stelle sollte erneut betont werden, dass dies asynchrone Protokolle sind. Nur weil ein Knoten Stimmen für den Commit sendet, bedeutet das nicht, dass seine Kollegen das ebenfalls tun. Einige von ihnen könnten noch über Anträge für die Abstimmung abstimmen, während andere möglicherweise bereits den Wert externalisiert haben. SCP erklärt, wie ein Knoten jeden Typ von Peermessaging unabhängig von seiner Phase verarbeiten sollte.
Wenn die Nachricht „Ich gebe den Commit <N,C> bekannt“ nicht angenommen oder bestätigt werden kann, besteht die Möglichkeit, die Nachricht <N+1,C> oder <N+2,C> anzunehmen oder zu bestätigen – oder, in jedem Fall, jedes Bulletin mit dem Wert C und nicht mit einem anderen, da der Knoten bereits versprochen hat, <N,C> niemals zurückzunehmen. Zu dem Zeitpunkt, zu dem der Knoten Stimmen für den Commit überträgt, wird es C oder nichts sein, je nachdem, wie weit der Konsens geht. Allerdings reicht das noch nicht aus, um C extern zu machen. Einige byzantinische Piraten (die weniger als das Quorum bilden, basierend auf unseren Sicherheitsannahmen) könnten den Knoten täuschen. Die Annahme und anschließende Bestätigung eines bestimmten Bulletins (oder eines Bereichs von Bulletins) gibt dem Knoten schließlich das Vertrauen, C extern zu machen.
Abstimmung SCP durch föderierte Abstimmung. Nicht gezeigt: jederzeit kann ein Timer ausgelöst werden, wodurch der Zähler im Bulletin erhöht wird (und möglicherweise ein neuer Komposit aus zusätzlichen vorgeschlagenen Kandidaten erzeugt wird).
Und das war's! Sobald das Netzwerk einen Konsens erreicht hat, ist es bereit, dies immer wieder zu tun. Im Stellar-Zahlungsnetzwerk geschieht dies alle 5 Sekunden: eine Leistung, die sowohl Sicherheit als auch Widerstandsfähigkeit erfordert, die durch SCP gewährleistet wird.
SCP erreicht dies durch mehrere Runden föderativer Abstimmung. Föderative Abstimmungen wurden durch das Konzept der Quorum-Slices möglich: Sätze von gleichrangigen Knoten, denen jeder Knoten als Teil seines (subjektiven) Quorums vertrauen möchte. Diese Konfiguration bedeutet, dass Konsens auch in einem Netzwerk mit offener Mitgliedschaft und byzantinischen Fehlern erreicht werden kann.
Weiterführende Lektüre
- Das ursprüngliche technische Dokument zu SCP finden Sie , und Projektbeschreibung für dessen Implementierung.
- Der ursprüngliche Autor des SCP-Protokolls, David Mazieres, erklärt es vereinfacht (aber dennoch technisch) .
- Vielleicht waren Sie überrascht, in diesem Artikel keine Begriffe wie "Mining" oder "Proof of Work" zu finden. SCP verwendet diese Methoden nicht, aber einige andere Konsensalgorithmen tun dies. Zayn Wizerzpoon hat einen zugänglichen .
- ein einfaches Netzwerk, das Konsens in einem vollständigen SCP-Round erzielt.
- Für Leser, die sich für Implementierungen von SCP interessieren: siehe. , der von dem Zahlungsnetzwerk Stellar genutzt wird, oder , den ich geschrieben habe, um das SCP besser zu verstehen.
Quelle: habr.com
