Das Stellar-Konsensprotokoll wurde erstmals in einem wissenschaftlichen Artikel von David Mazier aus dem Jahr 2015 beschrieben. Dies ist ein „föderales System des byzantinischen Abkommens“, das es dezentralen Computernetzwerken ohne Führungskräfte ermöglicht, effektiv einen Konsens über eine Entscheidung zu erzielen. Das Stellar-Abrechnungsnetzwerk verwendet das Stellar Consensus Protocol (SCP), um einen konsistenten Transaktionsverlauf aufrechtzuerhalten, den alle Mitglieder sehen.

Konsensprotokolle gelten als schwer verständlich. SCP ist einfacher als die meisten von ihnen, teilt aber dennoch diesen Ruf - auch aufgrund der falschen Vorstellung, dass die „Bundesabstimmung“, der die erste Hälfte des wissenschaftlichen Artikels gewidmet ist, SCP ist. Aber das ist nicht so! Dies ist nur ein wichtiger Baustein, mit dem in der zweiten Hälfte des Artikels das eigentliche Stellar-Konsensprotokoll erstellt wird.

In diesem Artikel beschreiben wir kurz, was ein "System von Vereinbarungen" ist, was es "byzantinisch" machen kann und warum das byzantinische System "föderalistisch" wird. Anschließend erläutern wir das im SCP-Artikel beschriebene föderierte Abstimmungsverfahren und schließlich das SCP-Protokoll selbst.

Vereinbarung Systeme

Das System der Vereinbarungen ermöglicht es einer Gruppe von Teilnehmern, einen Konsens über ein Thema zu erzielen, beispielsweise darüber, was zum Mittagessen bestellt werden soll.

Wir bei Interstellar haben unser eigenes Arrangementsystem implementiert: Wir bestellen, was unser Betriebsleiter John sagt. Dies ist ein einfaches und effektives Vereinbarungssystem. Wir alle vertrauen John und glauben, dass er jeden Tag etwas Interessantes und Nährwertiges finden wird.

Aber was ist, wenn John unser Vertrauen missbraucht? Er kann im Alleingang entscheiden, dass wir alle Veganer werden sollen. In ein oder zwei Wochen werden wir ihn wahrscheinlich stürzen und die Autorität an Elizabeth übergeben. Aber plötzlich liebt sie Avocados mit Sardellen und meint, dass jeder so werden sollte. Strom korrumpiert. Daher ist es besser, eine demokratischere Methode zu finden: eine Möglichkeit, um sicherzustellen, dass unterschiedliche Präferenzen berücksichtigt werden, und gleichzeitig ein zeitnahes und eindeutiges Ergebnis zu gewährleisten, damit niemand das Mittagessen bestellt oder fünf Personen unterschiedliche Bestellungen aufgeben oder die Diskussion bis zum Abend andauert.

Es scheint, dass die Lösung einfach ist: abstimmen! Dies ist jedoch ein irreführender Eindruck. Wer sammelt die Stimmzettel und meldet die Ergebnisse? Und warum sollte der Rest glauben, was er sagt? Vielleicht können wir zuerst für den Führer stimmen, dem wir vertrauen, um die Abstimmung zu leiten - aber wer wird diese erste Abstimmung führen? Was ist, wenn wir uns nicht auf einen Führer einigen können? Oder wenn wir uns einig sind und dieser Anführer in einer Besprechung festsitzt oder krankgeschrieben wird?

Ähnliche Probleme treten in verteilten Computernetzwerken auf. Alle Teilnehmer oder Knoten müssen sich beispielsweise auf eine Lösung einigen, deren Aufgabe es ist, die gemeinsam genutzte Datei zu aktualisieren oder die Aufgabe aus der Verarbeitungswarteschlange zu übernehmen. In einem Kryptowährungsnetzwerk müssen Knoten wiederholt auswählen, wie die gesamte Story aus mehreren möglichen Versionen aussehen soll, die manchmal in Konflikt stehen. Diese Netzwerkvereinbarung gibt dem Empfänger die Garantie, dass die Münze (a) gültig (nicht gefälscht) und (b) noch nicht anderweitig ausgegeben ist. Es stellt auch sicher, dass er in Zukunft Münzen ausgeben kann, da der neue Empfänger aus den gleichen Gründen die gleichen Garantien hat.

Jedes übereinstimmende System in einem verteilten Computernetzwerk muss fehlertolerant sein: Es muss trotz Fehlern wie langsamen Kommunikationsleitungen, nicht reagierenden Knoten und falscher Nachrichtenreihenfolge konsistente Ergebnisse liefern. Das byzantinische System von Vereinbarungen ist außerdem resistent gegen „byzantinische“ Fehler: Knoten, die falsche Informationen liefern, sei es aufgrund eines Fehlers oder bei einem absichtlichen Versuch, das System zu untergraben oder einen Vorteil zu erzielen. Die „byzantinische“ Widerstandsfähigkeit - die Fähigkeit, einer Gruppenentscheidung zu vertrauen, selbst wenn einige Mitglieder der Gruppe lügen oder auf andere Weise die Regeln der Entscheidungsfindung nicht befolgen - wird als Gleichnis der Generäle des Byzantinischen Reiches bezeichnet, die versuchten, den Angriff zu koordinieren. Anthony Stevens hat eine gute Beschreibung .

Betrachten Sie die Besitzerin der Kryptomünze Alice, die sich zwischen dem Kauf eines köstlichen Eises von Bob und der Bezahlung von Carols Schulden entscheiden muss. Vielleicht möchte Alice beide gleichzeitig bezahlen und betrügerisch dieselbe Münze ausgeben. Dazu muss sie Bobs Computer davon überzeugen, dass die Münze niemals an Carol gezahlt wurde, und Carols Computer davon überzeugen, dass die Münze niemals an Bob gezahlt wurde. Das byzantinische Konventionssystem macht dies mit einer Form der Mehrheitsregel, die als Quorum bezeichnet wird, praktisch unmöglich. Ein Knoten in einem solchen Netzwerk weigert sich, zu einer bestimmten Version des Verlaufs zu wechseln, bis er feststellt, dass eine ausreichende Anzahl von Peer-Knoten - ein Quorum - einem solchen Übergang zustimmt. Sobald dies geschieht, bilden sie einen ausreichend großen Wahlblock, um die verbleibenden Netzwerkknoten zu zwingen, ihrer Entscheidung zuzustimmen. Alice kann einige Knoten in ihrem Namen liegen lassen, 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? Zumindest eine Mehrheit oder vielmehr eine qualifizierte Mehrheit, um Fehler und Betrug zu bekämpfen. Um die Mehrheit zu berechnen, müssen Sie jedoch die Gesamtzahl der Teilnehmer kennen. In Interstellars Büro oder bei Distriktwahlen sind diese Zahlen leicht zu erkennen. Wenn Ihre Gruppe jedoch ein schlecht definiertes Netzwerk ist, in das Knoten nach Wunsch ohne Abstimmung mit dem Zentrum ein- und ausgehen können, benötigen Sie ein byzantinisches Bundesvereinbarungssystem , das Quoren nicht aus einer vorgegebenen Liste von Knoten, sondern dynamisch aus einer sich ständig ändernden und unvermeidlich unvollständigen Liste bestimmen kann Momentaufnahme von Knoten zu einem bestimmten Zeitpunkt.

Es scheint möglicherweise nicht möglich zu sein, ein Quorum für einen einzelnen Knoten in einem umfangreichen Netzwerk zu erstellen, aber es ist möglich. Ein solches Quorum kann sogar die Ergebnisse einer dezentralen Abstimmung garantieren. Das SCP-Whitepaper zeigt, wie dies mithilfe eines Verfahrens namens Verbundabstimmung erfolgt .

Für die Ungeduldigen

Der Rest des Artikels beschreibt die Bundesabstimmung und das Stellar-Konsensprotokoll. Wenn Sie nicht an den Details interessiert sind, finden Sie hier eine allgemeine Übersicht über den Prozess.

1. Die Knoten führen Abstimmungsrunden des Bundes über die „Nominierten“ durch. Eine Runde der Bundesabstimmung bedeutet:
   
   • Der Knoten stimmt für jede Aussage, zum Beispiel "Ich schlage den Wert von V vor";
     
   • Der Knoten hört auf die Stimmen der Feste, bis er eine findet, die „empfangen“ kann.
     
   • Der Knoten sucht nach einem „Quorum“ für diese Anweisung. Das Quorum „bestätigt“ den Kandidaten.
2. Sobald ein Knoten einen oder mehrere Kandidaten bestätigen kann, versucht er, einen Stimmzettel durch mehrere Abstimmungsrunden des Bundes vorzubereiten.
   
3. Sobald der Knoten in der Lage ist, die Bereitschaft des Stimmzettels zu überprüfen, versucht er, ihn mit noch mehr Runden der föderierten Abstimmung zu versorgen.
   
4. Sobald eine Site ein Newsletter-Commit bestätigen kann, kann sie den Wert dieses Newsletters „externalisieren“ und ihn als Ergebnis eines Konsenses verwenden.

Diese Schritte umfassen mehrere Abstimmungsrunden, die zusammen eine Runde SCP bilden. Wir werden genauer untersuchen, was bei jedem Schritt passiert.

Föderierte Abstimmung

Bei der föderierten Abstimmung wird festgestellt, ob sich ein Netzwerk auf einen Vorschlag einigen kann. In einer Abstimmungsrunde muss jeder Knoten einen von möglicherweise vielen möglichen Werten auswählen. Er kann dies erst tun, wenn er sicher ist, dass andere Knoten im Netzwerk kein anderes Ergebnis auswählen. Um dies sicherzustellen, tauschen die Knoten eine Reihe von Nachrichten hin und her aus, sodass jeder bestätigt, dass das Quorum der Knoten dieselbe Entscheidung trifft . Der Rest dieses Abschnitts erklärt die Begriffe in diesem Satz und wie das gesamte Verfahren abläuft.

Quorums und Quorum Slices

Beginnen wir mit der Definition eines Quorums. Wie oben erläutert, ist es in einem dezentralen Netzwerk mit dynamischer Mitgliedschaft unmöglich, die Anzahl der Knoten im Voraus zu kennen und daher zu wissen, wie viel für die meisten benötigt wird. Federated Voting löst dieses Problem, indem eine neue Idee für Quorum Slice eingeführt wird: eine kleine Gruppe von Peer-Knoten, denen der Knoten vertraut, um Abstimmungsstatusinformationen im Rest des Netzwerks zu übertragen. Jeder Knoten definiert sein eigenes Quorum Slice (von dem er tatsächlich Mitglied wird).

Die Quorumbildung beginnt mit einem Quorumschnitt. Für jeden Knoten werden Knoten seines Slice hinzugefügt. Dann werden Slicer-Mitglieder dieser Knoten hinzugefügt und so weiter. Im weiteren Verlauf stoßen Sie auf immer mehr Knoten, die Sie nicht hinzufügen können, da sie bereits im Slice enthalten sind. Wenn keine neuen Knoten mehr hinzugefügt werden müssen, wird der Prozess gestoppt: Wir haben ein Quorum durch „Transitive Closure“ gebildet, indem wir das Quorum des ursprünglichen Knotens abgeschnitten haben.


So finden Sie das Quorum von diesem Knoten ...


... Mitglieder zu seinem Slice hinzufügen ...


... dann fügen Sie diesen Knoten Slicer-Mitglieder hinzu.


Fahren Sie fort, bis keine Knoten mehr hinzuzufügen sind.




Keine Knoten mehr zum Hinzufügen. Dies ist ein Quorum.

Tatsächlich kann jeder Knoten in mehr als eine Schicht gehen. Um ein Quorum zu bilden, wählen Sie nur einen der Slices aus und fügen Sie Mitglieder hinzu. Wählen Sie dann ein beliebiges Slice für jedes Mitglied aus und fügen Sie diesem Slice Mitglieder hinzu und so weiter. Dies bedeutet, dass jeder Knoten Mitglied vieler möglicher Quorums ist.


Wählen Sie bei jedem Schritt nur eine Quorumscheibe aus.






Ein mögliches Quorum. Oder eine Alternative ...


... andere Scheiben auswählen ...




... (wenn möglich) ...


... schafft ein weiteres Quorum.

Woher weiß ein Knoten, in welchen Slices sich die anderen Knoten befinden? Auf die gleiche Weise wie andere Informationen zu anderen Knoten: von den Übertragungen, die jeder Knoten an das Netzwerk sendet, wenn sich sein Abstimmungsstatus ändert. Jede Sendung enthält Informationen über Slices des sendenden Knotens. Das technische Dokument von SCP spezifiziert keinen Kommunikationsmechanismus. Implementierungen verwenden normalerweise das Klatschprotokoll , um Broadcast-Nachrichten über das Netzwerk zu gewährleisten.

Denken Sie daran, dass in einem nicht-föderalen byzantinischen System von Vereinbarungen ein Quorum als die Mehrheit aller Knoten definiert ist. Das byzantinische Abkommenssystem wurde unter dem Gesichtspunkt der Frage entwickelt: Wie viele unehrliche Knoten kann das System aushalten? In einem System von N Knoten, die darauf ausgelegt sind, f Fehler (Tricks) zu überleben, sollte der Knoten in der Lage sein, Fortschritte zu erzielen, indem er eine Antwort von N - f Peers erhält, da f von ihnen möglicherweise nicht funktioniert. Nachdem wir jedoch eine Antwort von N - f Peers erhalten haben, können wir davon ausgehen, dass alle f Peers (von denen der Knoten keine Antwort erhalten hat) tatsächlich ehrlich sind. Somit sind f von N - f Peers (von denen eine Antwort empfangen wird) böswillig. Damit die Knoten zu demselben Konsens gelangen, muss die Mehrheit der verbleibenden Knoten ehrlich sein, dh N - f muss größer als 2f oder N> 3f sein. Normalerweise hat ein System, das für das Überleben von f Fehlern ausgelegt ist, insgesamt N = 3f + 1 Knoten und eine Quorumgröße von 2f + 1. Sobald der Vorschlag die Quorumschwelle überschreitet, ist der Rest des Netzwerks davon überzeugt, dass konkurrierende Vorschläge scheitern werden. Das Netzwerk konvergiert also zum Ergebnis.

Aber in einem föderalen byzantinischen Abkommenssystem kann es nicht nur keine Mehrheit geben (weil niemand die Gesamtgröße des Netzwerks kennt), sondern das Konzept einer Mehrheit ist im Allgemeinen nutzlos! Wenn die Mitgliedschaft im System offen ist, kann jemand die Mehrheit erhalten, indem er einfach den sogenannten Sibyl-Angriff durchführt: indem er sich wiederholt über mehrere Knoten dem Netzwerk anschließt. Warum kann der transitive Abschluss eines Slice als Quorum bezeichnet werden und wie kann er konkurrierende Angebote unterdrücken?

Technisch auf keinen Fall! Stellen Sie sich ein Netzwerk von sechs Knoten vor, in dem zwei Tripel in Schichten des jeweils anderen Quorums isoliert sind. Die erste Untergruppe kann eine Entscheidung treffen, von der die zweite niemals hören wird, und umgekehrt. Es gibt keine Möglichkeit für dieses Netzwerk, einen Konsens zu erzielen (außer durch Zufall).

Daher erfordert SCP, dass das Netzwerk über eine Eigenschaft namens Quorum Crossing für die Abstimmung im Verbund (und für die Anwendung wichtiger Artikelsätze) verfügt. In einem Netzwerk mit dieser Eigenschaft überlappen sich zwei beliebige Quorums, die erstellt werden können, immer in mindestens einem Knoten. Die vorherrschende Stimmung des Netzwerks zu bestimmen ist so gut wie die Mehrheit zu haben. Intuitiv bedeutet dies, dass, wenn ein Quorum mit Aussage X übereinstimmt, kein anderes Quorum jemals mit etwas anderem übereinstimmen kann, da es notwendigerweise einen Knoten aus dem ersten Quorum enthält, der bereits für X gestimmt hat.


Wenn das Netzwerk einen Schnittpunkt von Quoren hat ...


... dann können Sie zwei beliebige Quorums erstellen ...


... wird sich immer überschneiden.





(Natürlich können sich überlappende Knoten in anderer Hinsicht als byzantinisch oder schlecht herausstellen. In diesem Fall hilft die Überschneidung von Quoren dem Netzwerk überhaupt nicht, sich zu einigen. Aus diesem Grund basieren viele der Ergebnisse im technischen Dokument von SCP auf expliziten Annahmen, wie z. B. dem, was im Netzwerk verbleibt Schnittpunkt von Quoren auch nach dem Entfernen fehlerhafter Knoten . Der Einfachheit halber lassen wir diese Annahmen im Rest des Artikels implizit .

Es mag unangemessen erscheinen zu erwarten, dass in einem Netzwerk unabhängiger Knoten ein zuverlässiger Schnittpunkt von Quoren möglich ist. Dafür gibt es zwei Gründe.

Der erste Grund ist die Existenz des Internets selbst. Das Internet ist ein ideales Beispiel für ein Netzwerk unabhängiger Knoten mit Schnittpunkten von Quoren. Die meisten Websites im Internet stellen nur eine Verbindung zu wenigen anderen lokalen Websites her. Diese kleinen Gruppen überlappen sich jedoch so weit, dass jede Website von jeder anderen Website auf einer bestimmten Route aus zugänglich ist.

Der zweite Grund ist spezifisch für das Stellar-Zahlungsnetzwerk (die häufigste Verwendung von SCP). Jedes Asset im Stellar-Netzwerk verfügt über einen Emittenten. Laut Stellar-Empfehlungen muss jeder Emittent einen oder mehrere Knoten im Netzwerk für die Verarbeitung von Rückzahlungsanforderungen festlegen. Es liegt in Ihrem Interesse, diese Knoten für jedes Asset, an dem Sie interessiert sind, direkt oder indirekt in Quorum Slices aufzunehmen. Dann überlappen sich die Quoren für alle an diesem Vermögenswert interessierten Knoten zumindest in diesen Rückzahlungsknoten. Die Knoten, die an mehreren Vermögenswerten interessiert sind, werden alle Rückzahlungsknoten der jeweiligen Emittenten in ihre Quorumscheiben aufnehmen und sich bemühen, alle Vermögenswerte miteinander zu kombinieren. Darüber hinaus sind alle Vermögenswerte, die nicht auf diese Weise mit anderen im Netzwerk verbunden sind und nicht verbunden werden sollten, so, dass für dieses Netzwerk kein Quorum Crossing besteht (z. B. möchten Banken aus der Dollarzone manchmal mit Banken aus der Eurozone und Banken handeln von der Peso-Zone, also sind sie im selben Netzwerk, aber keiner von ihnen kümmert sich um ein separates Netzwerk von Kindern, die Baseballkarten verkaufen).

Das Warten auf die Überschneidung von Quoren ist natürlich keine Garantie . Andere byzantinische Abkommenssysteme verdanken einen großen Teil ihrer Komplexität der Gewährleistung von Quorums. Eine wichtige Neuerung von SCP besteht darin, dass die Verantwortung für die Erstellung von Quorums aus dem Konsensalgorithmus selbst entfernt und auf Anwendungsebene gebracht wird. Obwohl eine föderierte Abstimmung ausreichend allgemein ist, um über irgendwelche Fragen abzustimmen, hängt ihre Zuverlässigkeit in der Tat entscheidend von der breiteren Bedeutung dieser Werte ab. Einige hypothetische Anwendungen sind möglicherweise nicht so praktisch für den Aufbau gut verbundener Netzwerke wie andere.

Abstimmung, Annahme und Bestätigung

In der Runde der Verbundabstimmung beginnt der Knoten optional mit der Abstimmung für einen Wert von V. Dies bedeutet, dass die Nachricht an das Netzwerk gesendet wird: „Ich bin Knoten N, meine Quorumscheiben 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 dies niemals tun wird.

Bei Sendungen von Peer-to-Peer-Knoten sieht jeder Knoten, wie andere abstimmen. Sobald der Knoten eine ausreichende Anzahl solcher Nachrichten sammelt, kann er Quorum-Slices verfolgen und versuchen, Quorums zu finden. Wenn er ein Quorum von Kollegen sieht, die auch für V stimmen, kann er V akzeptieren und diese neue Nachricht an das Netzwerk senden: „Ich bin Knoten N, meine Slices sind Quorum Q und ich akzeptiere V“. Die Akzeptanz bietet eine stärkere Garantie als eine einfache Abstimmung. Wenn ein Knoten für V stimmt, kann er niemals für andere Optionen stimmen. Wenn ein Knoten jedoch V akzeptiert, akzeptiert kein Knoten im Web jemals eine andere Option (Satz 8 im technischen Whitepaper SCP beweist dies).

Natürlich ist es sehr wahrscheinlich, dass es nicht sofort ein Quorum von Knoten gibt, die mit V übereinstimmen. Andere Knoten können für andere Werte stimmen. Für die Website gibt es jedoch noch einen anderen Weg von der einfachen Abstimmung zur Akzeptanz. N kann einen anderen Wert von W annehmen, selbst wenn es nicht dafür gestimmt hat und selbst wenn es kein Quorum dafür sieht. Um zu entscheiden, ob Sie Ihre Stimme ändern möchten, reicht es aus, einen blockierenden Satz von Knoten zu sehen, die W akzeptiert haben. Ein blockierender Satz ist ein Knoten in jedem der Slices der Quorums von N. Wie der Name schon sagt, kann er jeden anderen Wert blockieren . Wenn alle Knoten in einer solchen Menge W annehmen, ist es (nach Satz 8) niemals möglich, ein Quorum zu bilden, das einen anderen Wert annimmt, und daher ist es auch sicher, W zu akzeptieren.


Knoten N mit drei Quorumscheiben.


BDF ist ein Blockierungssatz für N: Es enthält einen Knoten von jeder der N Schichten.


BE ist auch eine Blockierungsmenge für N, da E in zwei Schichten von N erscheint.

Eine Blockierungsmenge ist jedoch kein Quorum. Es wäre zu einfach, den Knoten N dazu zu bringen, den gewünschten Wert zu akzeptieren, wenn es ausreicht, nur einen Knoten in jeder der N Schichten zu knacken. Daher ist die Annahme des Wertes nicht das Ende der Abstimmung. Stattdessen muss N den Wert bestätigen, dh das Quorum der Knoten sehen, die ihn empfangen. Wenn er so weit geht, bestätigt der Rest des Netzwerks, wie das SCP-Whitepaper (in Satz 11) beweist, denselben Wert, sodass N die Abstimmung mit dem Verbund mit einem bestimmten Wert als Ergebnis beendet.


Föderierte Abstimmung.

Der Prozess der Abstimmung, Annahme und Bestätigung ist eine vollständige Runde der föderierten Abstimmung. Das Stellar Consensus Protocol vereint viele dieser Runden, um ein vollständiges Konsenssystem zu schaffen.

Stellar Consensus Protocol

Die beiden wichtigsten Merkmale eines Konsenssystems sind Sicherheit und Überlebensfähigkeit . Der Konsensalgorithmus ist „sicher“, wenn er verschiedenen Teilnehmern niemals unterschiedliche Ergebnisse liefern kann (eine Kopie von Bobs Geschichte wird Carol niemals widersprechen). "Vitalität" bedeutet, dass der Algorithmus immer ein Ergebnis liefert, das heißt, er bleibt nicht hängen.

Das beschriebene Verbundabstimmungsverfahren ist in dem Sinne sicher, dass, wenn ein Knoten den Wert von V bestätigt, kein anderer Knoten den anderen Wert bestätigt. Aber "bestätigt keine andere Bedeutung" - dies bedeutet nicht, dass er notwendigerweise etwas bestätigen wird. Die Teilnehmer können für so viele verschiedene Werte stimmen, dass nichts die Akzeptanzschwelle erreicht. Dies bedeutet, dass es keine Bundesabstimmung gibt.Überlebensfähigkeit .

Das Stellar Consensus Protocol verwendet föderierte Abstimmungen auf eine Weise, die sowohl Sicherheit als auch Überlebensfähigkeit garantiert. (Die Garantien für Sicherheit und Überlebensfähigkeit von SCP haben eine theoretische Grenze. Das Design wählt eine sehr starke Sicherheitsgarantie, die eine leichte Schwächung der Überlebensfähigkeit opfert, aber bei ausreichender Zeit wird wahrscheinlich ein Konsens erzielt.) Kurz gesagt, die Idee ist, mehrere föderierte Abstimmungen über mehrere Werte durchzuführen, bis eine von ihnen alle unten beschriebenen Phasen der SCP-Abstimmung vollständig durchläuft.

Die Werte, mit denen SCP nach Konsens strebt, können eine Transaktionshistorie oder eine Mittagsbestellung oder etwas anderes sein. Es ist jedoch wichtig zu beachten, dass dies nicht die Werte sind, die akzeptiert oder bestätigt werden. Stattdessen findet eine föderierte Abstimmung über Ansprüche dieser Werte statt .

Die ersten Abstimmungsrunden des Bundes finden in der Nominierungsphase mit einer Reihe von Anträgen „Ich nominiere V“ statt, möglicherweise für viele verschiedene Werte von V. Der Zweck der Nominierung besteht darin, einen oder mehrere Anträge zu finden, die angenommen und bestätigt werden.

Nach der Suche nach bestätigten Kandidaten geht SCP zur Abstimmungsphase über, in der das Ziel darin besteht, einen Stimmzettel zu finden(d. h. ein Container für den vorgeschlagenen Wert) und ein Quorum, das ein Commit dafür deklarieren kann (Commit). Wenn ein Quorum einen Stimmzettel festlegt, wird sein Wert als Konsens angesehen. Bevor der Knoten jedoch für die Stimmabgabe stimmen kann, muss er zunächst die Stornierung aller Stimmzettel mit einem niedrigeren Zählerwert bestätigen. Diese Schritte - das Abbrechen der Stimmzettel, um einen zu finden, für den Sie das Commit bestätigen können - umfassen mehrere Abstimmungsrunden des Bundes über mehrere Stimmzettelerklärungen.

In den folgenden Abschnitten werden die Nominierung und Abstimmung ausführlicher beschrieben.

Nominierung

Zu Beginn der Nominierungsphase kann jeder Knoten spontan den Wert V auswählen und für die Aussage „Ich nominiere V“ stimmen. Ziel in dieser Phase ist es, die Nominierung eines bestimmten Wertes durch eine Bundesabstimmung zu bestätigen.

Möglicherweise stimmt eine ausreichende Anzahl von Knoten für ziemlich unterschiedliche Aussagen, und keine Nominierung kann die Schwelle der Annahme erreichen. Daher „reflektieren“ die Knoten nicht nur ihre eigenen Nominierungsstimmen, sondern auch die Nominierungen ihrer Kollegen. Reflexion (Echo) bedeutet, dass wenn der Knoten für die Nominierung von V stimmt, aber eine Nachricht des Nachbarn sieht, der für die Nominierung von W stimmt, er jetzt für die Nominierung von V und W stimmt. (Nicht alle Peer-Stimmen werden während der Nominierung reflektiert, weil Dies kann zu einer Explosion verschiedener Kandidaten führen. SCP enthält einen Mechanismus zur Regulierung dieser Stimmen. Kurz gesagt, es gibt eine Formel zur Bestimmung der "Priorität" des Festes aus Sicht des Knotens, und nur die Stimmen von Knoten mit hoher Priorität werden reflektiert. Je länger die Erweiterung stattfindet, desto niedriger ist der Schwellenwert, daher erweitert sich der Knoten eine Reihe von Festen, deren Stimmen er reflektieren wird.Die Prioritätsformel als eine der Eingabedaten enthält die Steckplatznummer, sodass ein Peer mit hoher Priorität für einen Steckplatz für einen anderen eine niedrige Priorität haben kann und umgekehrt.

Konzeptionell handelt es sich bei der parallelen Nominierung von V und W um separate Bundesstimmen, die jeweils separat angenommen oder bestätigt werden können. In der Praxis packen SCP-Protokollnachrichten diese einzelnen Stimmen zusammen.

Obwohl die Abstimmung für die Nominierung V ein Versprechen ist, niemals gegen die Nominierung V zu stimmen, wird auf Antragsebene - in diesem Fall SCP - definiert, was „gegen“ bedeutet. SCP sieht keine Aussage, die der Abstimmung „Ich nominiere X“ widerspricht, dh es gibt keine Meldung „Ich bin gegen die Nominierung von X“, sodass der Knoten für die Nominierung von Werten stimmen kann. Viele dieser Nominierungen führen zu nichts, aber am Ende kann der Knoten einen oder mehrere Werte akzeptieren oder bestätigen. Sobald der Kandidat bestätigt ist, wird er ein Kandidat .


Nominierung von SCP durch Verbundabstimmung. Es kann viele "B" -Werte geben, die von Peers gepusht und vom Peer "reflektiert" werden.

Die Nominierung von Kandidaten kann zu mehreren bestätigten Kandidaten führen. Daher erfordert SCP, dass die Anwendungsschicht ein Verfahren zum Kombinieren von Kandidaten zu einem Verbund bereitstellt .(zusammengesetzt). Die Vereinigungsmethode kann alles sein. Die Hauptsache ist, dass, wenn diese Methode bestimmt wird, jeder Knoten die gleichen Kandidaten vereint. Im Abstimmungssystem für das Mittagessen kann „Vereinigung“ einfach die Ablehnung eines der beiden Kandidaten bedeuten. (Aber auf deterministische Weise: Jeder Knoten muss denselben Wert zum Zurücksetzen auswählen. Zum Beispiel eine frühere Auswahl in alphabetischer Reihenfolge). Im Stellar-Zahlungsnetzwerk, in dem über die Transaktionshistorie abgestimmt wird, umfasst das Kombinieren der beiden vorgeschlagenen Nominierten das Kombinieren der darin enthaltenen Transaktionen und des letzten ihrer beiden Zeitstempel.

Die technische Beschreibung von SCP beweist (Satz 12), dass das Netzwerk am Ende der Erweiterungsphase schließlich zu einem einzigen Verbund konvergiert. Es gibt jedoch ein Problem: Verbundabstimmung ist ein asynchrones Protokoll (wie SCP). Mit anderen Worten, die Knoten werden nicht zeitlich koordiniert, sondern nur gemäß den von ihnen gesendeten Nachrichten. Aus Sicht des Knotens ist unklar, wann die Erweiterungsphase beendet wurde . Und obwohl alle Knoten irgendwann zu demselben Verbund kommen, können sie verschiedene Routen entlang dieses Pfades auswählen und dabei verschiedene zusammengesetzte Kandidaten erstellen, und sie können nie sagen, welcher endgültig ist.

Das ist aber normal. Die Nominierung ist nur eine Vorbereitung. Die Hauptsache ist, die Anzahl der Kandidaten zu begrenzen, um einen Konsens zu erzielen, der während des Abstimmungsprozesses stattfindet .

Stimmzettel

Ein Newsletter ist ein Paar von <Zähler, Wert>, wobei Zähler eine Ganzzahl ist, die mit 1 beginnt, und Wert ein Kandidat aus der Nominierungsphase ist. Dies kann der eigene Kandidat eines Knotens oder ein von diesem Knoten angenommener Nachbarkandidat sein. Grob gesagt werden während des Laufs wiederholt Versuche unternommen, das Netzwerk zu zwingen, einen Konsens über einen Kandidaten in einem Wahlgang zu erzielen, indem möglicherweise viele Bundesstimmen über Wahlanträge gehalten werden. Die Zähler in den Stimmzetteln verfolgen die unternommenen Versuche, und die Stimmzettel mit höheren Zählern haben Vorrang vor den Stimmzetteln mit niedrigeren Zählern. Wenn der Stimmzettel <Zähler, Wert> stecken bleibt, beginnt eine neue Abstimmung, jetzt auf dem Stimmzettel <Zähler + 1, Wert>.

Es ist wichtig , zwischen Werten zu unterscheiden(zum Beispiel, was sollte die Reihenfolge für das Mittagessen sein: Pizza oder Salate), Stimmzettel (ein Paar Gegenwert) und Aussagen über die Stimmzettel. Die SCP-Runde umfasst mehrere Runden der föderierten Abstimmung, insbesondere zu solchen Aussagen:

• "Ich bin bereit, Bulletin B zu begehen" und
  
• "Ich erkläre eine Verpflichtung gegenüber Bulletin B"

Aus Sicht dieses Knotens wird ein Konsens erzielt, wenn er Bulletin B findet, für das es die Aussage „Ich erkläre ein Commit für Bulletin B“ bestätigen kann (dh ein Quorum finden kann, das dies akzeptiert). Von nun an können Sie sicher auf den in B angegebenen Wert reagieren - geben Sie beispielsweise diese Bestellung für das Mittagessen auf. Dies wird als Externalisierung des Werts bezeichnet. Sobald die Annahme des Stimmzettels bestätigt wurde, kann der Knoten sicher sein, dass jeder andere Knoten denselben Wert ausgelagert hat oder ihn definitiv in Zukunft festschreiben wird.

Obwohl konzeptionell viele Verbundstimmen auf Anträgen für viele verschiedene Stimmzettel gehalten werden, tauschen sie nicht so viele Nachrichten aus, da jede Nachricht eine Anzahl von Stimmzetteln enthält. Eine Botschaft fördert somit den Zustand vieler föderierter Stimmen gleichzeitig, zum Beispiel: „Ich akzeptiere Wahlprovisionen im Bereich von <min, V> bis <max, V>“.

Was bedeuten die Begriffe "vorbereitet" und "festschreiben"?

Ein Knoten stimmt für die Festlegung eines Stimmzettels, wenn er davon überzeugt ist, dass andere Knoten keine Stimmzettel mit anderen Werten festschreiben. Dies zu überzeugen ist der Zweck der Vorbereitung der Erklärung. Eine Abstimmung mit der Aufschrift „Ich bin bereit, Bulletin B zu begehen“ ist ein Versprechen, niemals ein Bulletin unter B, dh mit einem niedrigeren Zähler, zu begehen (SCP erfordert, dass die Werte in den Bulletins eine bestimmte Reihenfolge haben. Das Bulletin <N1, V1> ist kleiner als <N2, V2>, wenn N1 <N2 ist, und auch wenn N1 = N2 und V1 <V2). Diese kleineren Stimmzettel werden während der vorbereitenden Abstimmung „abgebrochen“, während B als „vorbereitet“ gilt.

Warum bedeutet "Ich bin bereit, Bulletin B zu begehen" "Ich verspreche, niemals Stimmzettel unter B zu begehen"? Weil SCP Abbruch als das Gegenteil von Commit definiert. Die Abstimmung für die Vorbereitung des Wahlgangs beinhaltet auch die Abstimmung, um einige andere Stimmzettel abzusagen, und wie wir zuvor besprochen haben, ist die Abstimmung für eine Sache ein Versprechen, niemals dagegen zu stimmen.

Vor dem Senden des Commits muss die Site zuerst das Bulletin finden, das sie als vorbereitet bestätigen kann. Mit anderen Worten, er hat eine föderierte Abstimmung über „Ich bin bereit, mich für Bulletin B zu verpflichten“, vielleicht für viele verschiedene Stimmzettel, bis er einen findet, der das Quorum akzeptiert.

Woher kommen die Stimmzettel für die Abstimmung? Zunächst sendet der Knoten die Vorbereitungen für die Abstimmung für <1, ​​C>, wobei C der zusammengesetzte Kandidat ist, der in der Nominierungsphase erstellt wurde. Die Nominierung kann jedoch auch nach Beginn der Vorbereitungen für die Abstimmung dazu führen, dass weitere Kandidaten erscheinen, die zu neuen Stimmzetteln werden. In der Zwischenzeit können Peers unterschiedliche Kandidaten haben und einen Blockierungssatz bilden, der "Ich bin bereit, ein B2-Bulletin zu schreiben" akzeptiert, wodurch der Knoten überzeugt wird, es ebenfalls zu akzeptieren. Schließlich gibt es einen Timeout-Mechanismus, der neue Abstimmungsrunden für neue Stimmzettel mit höheren Zählern generiert, wenn die aktuellen Stimmzettel stecken bleiben.

Sobald der Knoten Bulletin B findet, das er als vorbereitet bestätigen kann, sendet er eine neue Nachricht, "Bulletin B Commit". Diese Abstimmung teilt den Peers mit, dass der Knoten B niemals aufgeben wird. Wenn B ein Stimmzettel <N, C> ist, bedeutet „Commit Bulletin <N, C>“ die bedingungslose Zustimmung, für die Bereitschaft jedes Stimmzettels von <N, zu stimmen. C> bis <∞, s>. Dieser zusätzliche Wert hilft anderen Knoten, ein Commit nachzuholen, wenn sie sich noch in den früheren Phasen des Protokolls befinden.

In diesem Stadium ist noch einmal hervorzuheben, dass es sich um asynchrone Protokolle handelt. Nur weil ein Knoten Stimmen für ein Commit sendet, bedeutet dies nicht, dass seine Kollegen dies auch tun. Einige von ihnen können noch über Anträge zur Vorbereitung der Abstimmung abstimmen, andere haben die Bedeutung möglicherweise bereits externalisiert. SCP erklärt, wie ein Knoten jeden Peer-Nachrichtentyp unabhängig von seiner Phase verarbeiten soll.

Wenn die Nachricht "Ich erkläre ein Commit <N, C>" nicht akzeptiert oder bestätigt werden kann, dh die Wahrscheinlichkeit der Annahme oder Bestätigung der Nachricht <N + 1, C> oder <N + 2, C> - oder in jedem Fall eines Bulletins mit einem Wert von C und keinem anderen, da der Knoten bereits versprochen hat, <N, C> niemals abzubrechen. Wenn der Knoten die Stimmen für das Commit sendet, ist es C oder nichts, je nachdem, wie weit der Konsens geht. Dies reicht jedoch nicht aus, damit der Knoten C auslagert. Einige byzantinische Feste (weniger als ein Quorum, basierend auf unseren Annahmen zur Sicherheit) können den Knoten belügen. Die Annahme und anschließende Bestätigung eines bestimmten Stimmzettels (oder einer Reihe von Stimmzetteln) gibt dem Knoten das Vertrauen, C endgültig zu externalisieren.


SCP läuft durch föderierte Abstimmung. Nicht gezeigt: Es kann jederzeit ein Timer funktionieren, der den Zähler im Stimmzettel erhöht (und möglicherweise aus neuen nominierten Kandidaten ein neues Komposit erstellt).

Und das ist alles! Sobald das Netzwerk einen Konsens erreicht hat, ist es bereit, dies immer wieder zu tun. Im Stellar-Abrechnungsnetzwerk geschieht dies ungefähr alle 5 Sekunden: eine Leistung, die sowohl Sicherheit als auch Überlebensfähigkeit erfordert und von SCP garantiert wird.

SCP kann dies erreichen, indem es sich auf mehrere Abstimmungsrunden des Bundes stützt. Die föderierte Abstimmung wurde durch das Konzept der Quorum-Slices ermöglicht: Gruppen von Peer-Knoten, denen jeder Knoten als Teil seines (subjektiven) Quorums vertrauen wollte. Diese Konfiguration bedeutet, dass Sie auch in einem Netzwerk mit offener Mitgliedschaft und byzantinischer Täuschung einen Konsens erzielen können.

Weiterführende Literatur

• Das technische Originaldokument für SCP finden Sie hier . Hier finden Sie den Entwurf der Spezifikationen für die Implementierung.
  
• Der ursprüngliche Autor des SCP-Protokolls, David Mazier, vereinfacht es hier (aber technisch immer noch).
  
• Sie waren möglicherweise überrascht, die Begriffe „Bergbau“ oder „Arbeitsnachweis“ in diesem Artikel nicht zu finden. SCP verwendet diese Methoden nicht, einige andere Konsensalgorithmen jedoch. Zane Witherspoon schrieb eine zugängliche Übersicht über Konsensalgorithmen .
  
• Eine schrittweise Beschreibung eines einfachen Netzwerks, das in einer vollständigen Runde SCP einen Konsens erzielt.
  
• Für Leser, die an SCP-Implementierungen interessiert sind: Informationen zum besseren Verständnis von SCP finden Sie im C ++ - Code, der vom Stellar-Zahlungsnetzwerk verwendet wird, oder im Go-Code, den ich geschrieben habe.