Das Stellar-Konsensprotokoll wurde erstmals in in einem wissenschaftlichen Artikel 2015 von David Mazier beschrieben. Es handelt sich um ein „föderatives System des byzantinischen Konsenses“, das dezentralen Berechnungsnetzwerken ohne Führer ermöglicht, effizient einen Konsens über eine Entscheidung zu erreichen. Das Zahlungssystem Stellar nutzt das Stellar Consensus Protocol (SCP), um eine konsistente Historie von Transaktionen zu führen, die von allen Teilnehmern eingesehen werden kann.

Es wird angenommen, dass Konsensprotokolle schwer zu verstehen sind. SCP ist einfacher als die meisten von ihnen, teilt jedoch dennoch diesen Ruf – teilweise aufgrund der falschen Vorstellung, dass das „föderative Abstimmen“, dem die erste Hälfte des wissenschaftlichen Artikels gewidmet ist, SCP ist. Aber das ist es nicht! Es ist lediglich ein wichtiger Baustein, der in der zweiten Hälfte des Artikels zur Schaffung verwendet wird des tatsächlichen Stellar-Konsensprotokolls.

In diesem Artikel werden wir kurz erklären, was ein „Zustimmungssystem“ ist, was sie „byzantinisch“ machen kann und warum es ratsam ist, ein byzantinisches System „föderativ“ zu gestalten. Danach werden wir das föderative Abstimmungsverfahren beschreiben, das im SCP-Artikel erläutert wird, und schließlich das Protokoll SCP selbst erklären.

Zustimmungssysteme

Ein Zustimmungssystem ermöglicht es einer Gruppe von Teilnehmern, einen Konsens über ein bestimmtes Thema zu erzielen, zum Beispiel, was man zum Mittagessen bestellen soll.

In unserem Unternehmen Interstellar haben wir unser eigenes System für das Mittagsessen eingeführt: Wir bestellen das, was unser Betriebsleiter John sagt. Es ist ein einfaches und effektives Zustimmungssystem. Wir alle vertrauen John und glauben, dass er jeden Tag etwas Interessantes und Nahrhaftes finden wird.

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 Macht an Elizabeth übertragen. Aber was, wenn sie Avocados mit Sardellen liebt und denkt, dass alle so werden sollten? Macht verdirbt. Daher ist es besser, eine demokratischere Methode zu finden: eine Möglichkeit, sicherzustellen, dass unterschiedliche Vorlieben berücksichtigt werden und gleichzeitig ein zeitgerechtes und eindeutiges Ergebnis erzielt wird, damit es nicht so endet, dass niemand das Mittagessen bestellt oder fünf Personen unterschiedliche Bestellungen aufgeben oder das Gespräch bis zum Abend dauert.

Auf den ersten Blick scheint die Lösung einfach zu sein: eine Abstimmung durchzuführen! Doch dieser Eindruck ist trügerisch. Wer wird die Wahlzettel sammeln und die Ergebnisse bekanntgeben? Und warum sollten die anderen dem Glauben schenken, was er sagt? Vielleicht können wir zunächst für einen Führer stimmen, dem wir vertrauen, das Abstimmungsverfahren zu leiten – aber wer wird dieses Votum leiten? Was ist, wenn wir uns nicht auf einen Führer einigen können? Oder wenn wir uns einigen, dieser Führer aber in einem Meeting feststeckt oder krank wird? zuerst Ähnliche Probleme treten in verteilten Computersystemen auf. Alle Teilnehmer oder Knoten müssen sich auf eine Entscheidung einigen, zum Beispiel, wessen Reihe es ist, eine gemeinsame Datei zu aktualisieren oder eine Aufgabe aus der Warteschlange abzuholen. In einem Kryptowährungsnetzwerk stehen die Knoten wiederholt vor der Aufgabe, aus mehreren möglichen Versionen, die manchmal widersprüchlich sind, zu wählen, wie die vollständige Geschichte aussieht. Dieses Netzwerkabkommen garantiert dem Empfänger, dass die Münze (a) gültig (nicht gefälscht) und (b) noch nicht an anderer Stelle ausgegeben wurde. Es stellt auch sicher, dass er die Münzen in Zukunft ausgeben kann, da der neue Empfänger die gleichen Garantien aus den gleichen Gründen hat.

Jedes Konsenssystem in einem verteilten Computernetzwerk muss ausfallsicher sein: Es muss konsistente Ergebnisse liefern, trotz Fehler wie langsamen Kommunikationsleitungen, nicht reagierenden Knoten und falscher Reihenfolge von Nachrichten.

Das byzantinische Konsenssystem ist zusätzlich gegen "byzantinische" Fehler resistent: Knoten, die falsche Informationen bereitstellen, sei es aufgrund von Fehlern oder in einem absichtlichen Versuch, das System zu untergraben oder sich einen Vorteil zu verschaffen. "Byzantinische" Ausfallsicherheit – die Fähigkeit, einer Gruppenentscheidung zu vertrauen, selbst wenn einige Gruppenmitglieder lügen oder anderweitig die Entscheidungsregeln nicht befolgen – erhält ihren Namen von der Geschichte der Generäle des Byzantinischen Reiches , die versuchten, einen Angriff zu koordinieren.Eine gute Beschreibung findet sich bei Anthony Stevens. bei Anthony Stevens.

Betrachten wir die Besitzerin der Kryptowährung, Alice, die zwischen dem Kauf von leckerem Eis bei Bob und der Begleichung einer Schuld bei Carol wählen muss. Vielleicht möchte Alice beiden gleichzeitig bezahlen und betrügerisch dieselbe Münze ausgeben. Dazu muss sie Bobs Computer überzeugen, dass die Münze niemals Carol ausgezahlt wurde, und Carol's Computer überzeugen, dass die Münze niemals Bob ausgezahlt wurde. Ein byzantinisches Einigungssystem macht dies praktisch unmöglich, indem es eine Form der Mehrheitsregel verwendet, die als Quorumbezeichnet wird. Ein Knoten in einem solchen Netzwerk weigert sich, zu einer bestimmten Version der Geschichte überzugehen, solange er nicht sieht, dass eine ausreichende Anzahl gleichgestellter Knoten – das Quorum – mit diesem Übergang einverstanden ist. Sobald dies geschieht, bilden sie einen ausreichend großen Wählerblock, um die verbleibenden Knoten im Netzwerk dazu zu bringen, ihre Entscheidung zu akzeptieren. Alice kann einige Knoten dazu bringen, in ihrem Namen zu lügen, aber wenn das Netzwerk groß genug ist, wird ihr Versuch von den Stimmen ehrlicher Knoten überwältigt.

Wie viele Knoten sind für ein Quorum erforderlich? Mindestens die Mehrheit, genauer gesagt eine qualifizierte Mehrheit zur Bekämpfung von Fehlern und Betrug. Aber um die Mehrheit zu zählen, muss man die Gesamtzahl der Teilnehmer kennen. In einem Büro wie Interstellar oder bei regionalen Wahlen sind diese Zahlen leicht zu ermitteln. Aber wenn Ihre Gruppe ein schwach definiertes Netzwerk ist, in dem Knoten nach Belieben ein- und austreten können, ohne sich mit einem Zentrum abzustimmen, dann wird ein föderatives byzantinisches Einigungssystem benötigt, das in der Lage ist, Quoren nicht aus einer vorher festgelegten Liste von Knoten zu bestimmen, sondern dynamisch aus einem ständig wechselnden und zwangsläufig unvollständigen Snapshot der Knoten zu einem bestimmten Zeitpunkt.

Es mag unmöglich erscheinen, aus der Sicht eines Knotens in einem umfassenden Netzwerk ein Quorum zu bilden, aber es ist möglich. Ein solches Quorum kann sogar die Ergebnisse dezentraler Abstimmungen garantieren. Das technische Dokument SCP zeigt, wie dies durch eine als föderierte Abstimmung.

bezeichnete Prozedur erreicht werden kann.

Der Rest des Artikels beschreibt die föderierte Abstimmung und das Konsensprotokoll von Stellar detaillierter. Wenn Sie nicht an Einzelheiten interessiert sind, finden Sie hier einen allgemeinen Überblick über den Prozess.

1. Knoten führen Runden der föderalen Abstimmung über "Nominierungen" durch. Eine Runde der föderalen Abstimmung bedeutet:
   • Der Knoten stimmt über eine bestimmte Behauptung ab, z. B. "Ich schlage den Wert V vor";
   • Der Knoten hört die Stimmen der anderen, bis er eine findet, die "akzeptieren" kann;
   • Der Knoten sucht nach einem "Quorum" für diese Behauptung. Das Quorum "bestätigt" den Nominierten.
2. Sobald der Knoten einen oder mehrere Nominierte bestätigen kann, versucht er, das "Wahlblatt" durch mehrere Runden der föderalen Abstimmung "vorzubereiten".
3. Sobald der Knoten in der Lage ist, die Bereitstellung des Wahlblatts zu überprüfen, versucht er, es durch noch mehr Runden der föderalen Abstimmung zu committen.
4. Sobald der Knoten das Commit des Wahlblatts bestätigen kann, kann er den Wert dieses Wahlblatts "externalisieren", indem er ihn als Konsensergebnis verwendet.

Diese Schritte umfassen mehrere Runden der föderalen Abstimmung, die zusammen eine Runde SCP bilden. Lassen Sie uns genauer untersuchen, was in jedem Schritt passiert.

Föderale Abstimmung

Föderale Abstimmung ist das Verfahren zur Bestimmung, ob das Netzwerk einen Vorschlag abstimmen kann. In der Abstimmungsrunde muss jeder Knoten einen der potenziell vielen möglichen Werte auswählen. Er kann dies nicht tun, bis er sich sicher ist, dass die anderen Knoten im Netzwerk nicht ein anderes Ergebnis wählen. Um sich dessen sicher zu sein, tauschen die Knoten eine Flut von Nachrichten hin und her aus, damit jeder die Teilnahme der "Buffetts" am geschlossenen Verkauf von TON., dass Quota Knoten das gleiche auswählt. LösungDer restliche Teil dieses Abschnitts erklärt die Begriffe in dieser Aussage und wie das gesamte Verfahren abläuft.

Quoren und Quorum-Slices

Beginnen wir mit der Definition eines Quorums. Wie oben diskutiert, ist es in einem dezentralen Netzwerk mit dynamischer Mitgliedschaft unmöglich, im Voraus die Anzahl der Knoten zu kennen und somit zu wissen, wie viele für die Mehrheit benötigt werden. Die föderale Abstimmung löst dieses Problem, indem sie eine neue Idee einführt, Quorum-Slice (quorum slice): Eine kleine Gruppe von gleichrangigen Knoten, denen der Knoten vertraut, um Informationen über den Abstimmungsstatus an den Rest des Netzwerks zu übermitteln. Jeder Knoten definiert seinen eigenen Quorum-Slice (dem er faktisch angehört).

Die Bildung des Quorums beginnt mit dem Quorum-Slice. Für jeden Knoten werden die Knoten seines Slices hinzugefügt. Dann werden die Mitglieder der Slices hinzugefügt. diese Knoten und so weiter. Mit Fortschreiten treten immer mehr Knoten auf, die Sie nicht hinzufügen können, weil sie bereits im Quorum-Schnitt enthalten sind. Wenn keine neuen Knoten mehr zum Hinzufügen übrig sind, wird der Prozess gestoppt: Wir haben ein Quorum durch "transitive Schließung" des Quorum-Schnitts des Ausgangsknotens gebildet.

Um ein Quorum von einem gegebenen Knoten zu finden...

... fügen wir Mitglieder seines Schnitts hinzu...

... dann fügen wir Mitglieder der Schnitte dieser Knoten hinzu.

Wir machen weiter, bis keine Knoten mehr zum Hinzufügen übrig sind.

Es sind keine Knoten mehr zum Hinzufügen übrig. Das ist das Quorum.

In der Tat kann jeder Knoten Mitglied von mehr als einem Schnitt sein. Um ein Quorum zu bilden, wählen Sie nur einen der Schnitte und fügen Sie Mitglieder hinzu; dann wählen Sie für jedes Mitglied einen beliebigen Schnitt und fügen Sie Mitglieder hinzu dieses des Schnitts und so weiter. Das bedeutet, dass jeder Knoten Mitglied einer Vielzahl möglicher Quoren ist.

Wählen Sie bei jedem Schritt nur einen Quorum-Schnitt aus.

Ein mögliches Quorum. Oder eine alternative Option...

... wählen wir andere Schnitte...

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

... erzeugt ein anderes Quorum.

Wie erfährt ein Knoten, in welchen Schnitten andere Knoten enthalten sind? Genau wie andere Informationen über andere Knoten: aus den Übertragungen, die jeder Knoten ins Netzwerk sendet, wenn sich sein Abstimmungsverhalten ändert. Jede Übertragung enthält Informationen über die Schnitte des sendenden Knotens. Im technischen Dokument SCP wird der Kommunikationsmechanismus nicht angegeben. Implementierungen verwenden in der Regel das Gossip-Protokoll für die garantierte Übertragung von Nachrichten durch das gesamte Netzwerk.

Wir erinnern daran, dass in einem nicht-föderativen byzantinischen Konsenssystem das Quorum als Mehrheit aller Knoten definiert ist. Das byzantinische Konsenssystem wurde unter dem Gesichtspunkt entwickelt, wie viele unehrliche Knoten das System aushalten kann. In einem System aus N Knoten, das auf Ü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 Peers erhält, da f von ihnen möglicherweise nicht funktionsfähig sind. Wenn man jedoch 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. Somit sind f von N−f Peers, von denen eine Antwort erhalten wurde, böswillig. Damit die Knoten einen Konsens erreichen, müssen die meisten der verbleibenden Knoten ehrlich sein, was bedeutet, dass wir benötigen, dass N−f größer als 2f ist oder N > 3f. Normalerweise wird ein System, das auf Überlebensfähigkeit bei f Ausfällen ausgelegt ist, insgesamt N=3f+1 Knoten und eine Quorumgröße von 2f+1 haben. Sobald der Vorschlag den Quorum-Schwellenwert überschreitet, sind die übrigen Mitglieder des Netzwerks davon überzeugt, dass alle konkurrierenden Vorschläge scheitern werden. So konvergiert das Netzwerk zu einem Ergebnis.

In einem föderativen byzantinischen Konsenssystem kann es nicht nur keine Mehrheit geben (da niemand die Gesamtgröße des Netzwerks kennt), sondern das Konzept der Mehrheit ist völlig nutzlos! Wenn die Mitgliedschaft im System offen ist, kann jemand die Mehrheit erlangen, indem er einen sogenannten Sybil-Angriff durchführt: sich mehrfach über verschiedene Knoten mit dem Netzwerk verbindet. Warum kann das transitive Schließen eines Schnitts dann genannt werden Quorum, und wie ist es in der Lage, konkurrierende Vorschläge zu unterdrücken?

Technisch gesehen, gar nicht! Stellen Sie sich ein Netzwerk aus sechs Knoten vor, in dem zwei Gruppen von je drei Knoten in den Quorum-Schnitten der jeweils 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 keine Möglichkeit, Konsens zu erreichen (außer zufällig).

Daher erfordert das SCP, dass für die föderative Abstimmung (und für die Anwendung wichtiger Theoreme des Artikels) das Netzwerk über eine Eigenschaft verfügt, die als Schnittpunkten von Quoren bezeichnet wird. In einem Netzwerk mit dieser Eigenschaft überlappen sich immer zwei Quoren, die man bilden kann, in mindestens einem Knoten. Für die Bestimmung der vorherrschenden Stimmungen im Netzwerk ist dies ebenso gut, wie eine Mehrheit zu haben. Intuitiv bedeutet dies, dass, wenn irgendein Quorum einer Aussage X zustimmt, kein anderes Quorum jemals mit etwas anderem zustimmen kann, da es zwangsläufig einen Knoten aus dem ersten Quorum enthalten wird, das bereits für X gestimmt hat.

Wenn es in einem Netzwerk Überschneidungen von Quoren gibt…

… dann werden immer zwei Quoren, die Sie bilden können…

… sich überschneiden.

(Natürlich können sich überschneidende Knoten als byzantinisch oder aus anderen Gründen fehlerhaft erweisen. In diesem Fall hilft die Überschneidung der Quoren dem Netzwerk überhaupt nicht, sich zu einigen. Aus diesem Grund basieren viele Ergebnisse im technischen Dokument SCP auf klaren Annahmen, wie z.B., dass im Netzwerk weiterhin Überschneidungen der Quoren bestehen selbst nach dem Entfernen von fehlerhaften Knoten. Zur Vereinfachung lassen Sie diese Annahmen unausgesprochen im restlichen Teil des Artikels).

Es mag unvernünftig erscheinen, von einem Netzwerk aus unabhängigen Knoten zu erwarten, dass zuverlässige Überschneidungen von Quoren möglich sind. Aber es gibt zwei Gründe, warum das so ist.

Der erste Grund ist die Existenz des Internets. Das Internet ist ein perfektes Beispiel für ein Netzwerk unabhängiger Knoten mit Überschneidungen von Quoren. Die meisten Knoten im Internet verbinden sich nur mit einigen wenigen anderen lokalen Knoten, aber diese kleinen Mengen überlappen sich ausreichend, damit jeder Knoten von jedem anderen Knoten über irgendeinen Weg erreicht werden kann.

Der zweite Grund ist spezifisch für das Zahlungssystem Stellar (das am häufigsten genutzte Anwendungsbeispiel 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 zur Verarbeitung von Rückzahlungsanfragen benannt. In Ihrem Interesse ist es, diese Knoten direkt oder indirekt in die Quorum-Schnitte für jedes relevanten Asset einzubeziehen. Dann werden die Quoren aller Knoten, die an diesem Asset interessiert sind, in diesen Rückzahlungsknoten zumindest überlappen. Knoten, die an mehreren Assets interessiert sind, werden in ihren Quorum-Schnitten alle Rückzahlungsknoten der entsprechenden Emittenten einbeziehen und versuchen, alle Assets zusammenzufassen. Darüber hinaus werden alle Assets, die nicht auf diese Weise mit anderen im Netzwerk verbunden sind, nicht verbunden sein – so ist es vorgesehen, dass in diesem Netzwerk keine Überlappung der Quoren stattfindet (zum Beispiel möchten Banken aus dem Dollarraum manchmal mit Banken aus dem Euroraum und Banken aus dem Peso-Raum handeln, weshalb sie sich im selben Netzwerk befinden, aber niemand unter ihnen interessiert sich für ein separates Netzwerk von Kindern, die mit Baseballkarten handeln).

Natürlich, Die Erwartung einer Überlappung der Quoren ist keine Garantie. Andere byzantinische Konsenssysteme verdanken ihre Komplexität zu einem großen Teil der Garantie von Quoren. Eine wichtige Neuerung von SCP besteht darin, dass es die Verantwortung für die Bildung von Quoren vom eigentlichen Konsensalgorithmus auf die Anwendungsebene verlagert. Daher hängt die Zuverlässigkeit des föderalen Abstimmens, obwohl sie im Allgemeinen für die Abstimmung über beliebige Fragen recht weit verbreitet ist, tatsächlich kritisch von dem breiteren Kontext dieser Bedeutungen ab. Einige hypothetische Anwendungsarten könnten sich als weniger bequem erweisen, um gut verbundene Netzwerke zu schaffen als andere.

Abstimmung, Annahme und Bestätigung

Im Zuge der föderalen Abstimmung beginnt ein Knoten optional, für einen Wert V zu stimmen. Das bedeutet, dass er eine Nachricht ins Netzwerk überträgt: „Ich bin Knoten N, meine Quorum-Schnitte Q und ich stimme für V.“ Wenn ein Knoten auf diese Weise stimmt, verspricht er, dass er niemals gegen V gestimmt hat und niemals tun wird.

In den Übertragungen von Peer-Knoten sieht jeder Knoten, wie die anderen abstimmen. Sobald ein Knoten genügend solcher 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 das einfache 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 Quorum an Knoten gefunden wird, die mit V einverstanden sind. Andere Knoten können für andere Werte stimmen. Aber für den Knoten gibt es einen weiteren Weg, um vom einfachen Abstimmen zur Annahme überzugehen. N kann einen anderen Wert W annehmen, auch wenn er nicht dafür gestimmt hat und auch wenn er kein Quorum dafür sieht. Um zu entscheiden, seine Stimme zu ändern, reicht es, zu sehen eine blockierende Menge von Knoten, die W angenommen haben. Eine blockierende Menge besteht aus je einem Knoten aus jedem der Quorum-Schnitte von N. Wie der Name schon sagt, ist sie in der Lage, jede andere Option zu blockieren. Wenn alle Knoten in dieser Menge W annehmen, dann ist es (nach Theorem 8) unmöglich, ein Quorum zu bilden, das eine andere Option annimmt, und daher ist es für N auch sicher, W anzunehmen. Knoten N mit drei Quorum-Schnitten.

B-D-F ist eine blockierende Menge für N: sie umfasst je einen Knoten aus jedem der Schnitte von N.

B-E ist ebenfalls eine blockierende Menge für N, da E in zwei Schnitten von N erscheint.

Aber eine blockierende Menge ist kein Quorum. Es wäre zu einfach, Knoten N dazu zu bringen, den gewünschten Wert anzunehmen, wenn es reicht, einen einzigen Knoten in jedem der Schnitte von N zu hacken. Daher ist die Annahme eines Wertes noch nicht das Ende des Abstimmens. Stattdessen muss N den Wert bestätigen, das heißt, er muss ein Quorum von Knoten sehen, die ihn annehmen. Wenn er so weit kommt, dann wird, wie das technische Dokument SCP (im Theorem 11 beweist) zeigt, der Rest des Netzwerks letztlich auch denselben Wert bestätigen, und somit wird N das föderative Abstimmen mit einem bestimmten Wert als Ergebnis abschließen.

Föderatives Abstimmen.

Föderatives Abstimmen.

Der Abstimmungsprozess, die Annahme und die Bestätigung bilden einen vollständigen Rundgang durch die föderative Abstimmung. Das Stellar-Konsensprotokoll vereint viele solcher Runden, um ein vollständiges Konsenssystem zu schaffen.

Stellar-Konsensprotokoll

Die zwei wichtigsten Eigenschaften eines Konsenssystems sind Sicherheit und Robustheit. Ein Konsensalgorithmus ist „sicher“, wenn er niemals unterschiedlichen Teilnehmern unterschiedliche Ergebnisse liefern kann (Bobs Geschichtskopie wird niemals im Widerspruch zu Carol stehen). „Robustheit“ bedeutet, dass der Algorithmus immer ein Ergebnis liefert, das heißt, er hängt nie fest.

Das beschriebene Verfahren der föderativen Abstimmung ist sicher im Sinne davon, 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 notwendigerweise etwas bestätigt. Die Teilnehmer können für so viele verschiedene Werte abstimmen, dass nichts die Annahmeschwelle erreicht. Das bedeutet, dass in der föderativen Abstimmung nichts Robustheit.

Das Stellar-Konsensprotokoll verwendet föderative Abstimmung auf eine Weise, die sowohl Sicherheit als auch Robustheit gewährleistet. (Die Sicherheits- und Robustheitsgarantien von SCP haben eine theoretische Grenze. Die Konstruktion wählt eine sehr starke Sicherheitsgarantie und opfert dabei ein geringes Maß an Robustheit, aber unter Berücksichtigung eines ausreichenden Zeitrahmens wird mit hoher Wahrscheinlichkeit Konsens erreicht). Kurz gesagt, die Idee ist es, mehrere föderative Abstimmungen zu mehreren Werten durchzuführen, bis einer von ihnen vollständig durch alle Phasen der SCP-Abstimmung, die im Folgenden beschrieben werden, gegangen ist.

Die Werte, um die SCP Konsens sucht, können eine Transaktionshistorie oder eine Bestellung zum Mittagessen oder etwas anderes sein, aber es ist wichtig zu beachten, dass es nicht die Werte sind, die angenommen oder bestätigt werden. Stattdessen erfolgt die föderative Abstimmung über Aussagen über diese Werte.

Die ersten Runden der föderativen Abstimmung finden in der Nominierungsphase statt, wobei eine Reihe von Aussagen des Typs „Ich nominiere V“ gemacht werden, möglicherweise für viele verschiedene Werte V. Ziel der Nominierung ist es, eine oder mehrere Aussagen zu finden, die die Annahme und Bestätigung durchlaufen.

Nachdem die bestätigbaren Kandidaten gefunden wurden, geht SCP zur Abstimmungsphase über, in der das Ziel darin besteht, einen gewissen Wahlzettel (also einen Behälter für den vorgeschlagenen Wert) und ein Quorum zu finden, das verkünden kann Commits (commit). Wenn das Quorum den Wahlzettel committet, wird dessen Wert als Konsens akzeptiert. Bevor jedoch ein Knoten für den Commit des Wahlzettels abstimmen kann, muss er zuerst die Stornierung aller Wahlzettel mit einem niedrigeren Zählerwert bestätigen. Diese Schritte – das Stornieren von Wahlzetteln, um denjenigen zu finden, für den der Commit bestätigt werden kann – umfassen mehrere Runden federativer Abstimmungen zu verschiedenen Wahlzettelbehauptungen.

In den folgenden Abschnitten werden Wahlvorschläge und Abstimmungen ausführlicher beschrieben.

Wahlvorschlag

Zu Beginn der Vorschlagsphase kann jeder Knoten spontan einen Wert V wählen und für die Aussage 'Ich schlage V vor' stimmen. Das Ziel in dieser Phase besteht darin, den Vorschlag eines bestimmten Wertes durch federative Abstimmung zu bestätigen.

Es ist möglich, dass eine ausreichende Anzahl von Knoten für ausreichend unterschiedliche Behauptungen stimmt und kein Vorschlag die Annahmeschwelle erreicht. Daher reflektieren die Knoten neben der Übertragung ihrer eigenen Nominierungsstimmen die Nominierungen ihrer Nachbarn. 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 dann sowohl für den Vorschlag V als auch für W stimmen wird. (Nicht alle Stimmen der Nachbarn werden während des Vorschlags reflektiert, da dies zu einer Explosion unterschiedlicher Nominierungen führen kann. SCP beinhaltet einen Mechanismus zur Regulierung dieser Stimmen. Kurz gesagt, es gibt eine Formel zur Bestimmung der 'Priorität' eines Nachbarn aus der Sicht des Knotens, und es werden nur die Stimmen hochpriorisierter Knoten reflektiert. Je länger der Vorschlag dauert, desto niedriger wird die Schwelle, sodass der Knoten den Satz von Nachbarn erweitert, deren Stimmen er reflektieren wird. Die Prioritätsformel beinhaltet als eines der Eingabewerte die Slotnummer, sodass ein hochpriorisierter Peer für einen Slot für einen anderen niedrigpriorisiert sein kann und umgekehrt.

Konzeptionell ist die gleichzeitige Nominierung von V und W eine separate föderative Stimme, die jeweils unabhängig Annahme oder Bestätigung erreichen kann. In der Praxis packen die Nachrichten des SCP-Protokolls diese einzelnen Stimmen zusammen.

Obwohl die Abstimmung für die Nominierung von V das Versprechen beinhaltet, niemals gegen die Nominierung von V zu stimmen, wird auf Anwendungsebene – in diesem Fall SCP – definiert, was „dagegen“ bedeutet. SCP erkennt keine Aussage, die der Abstimmung „Ich nominieren X“ widerspricht, d. h. es gibt keine Nachricht „Ich bin gegen die Nominierung von X“, sodass der Knoten für die Nominierung beliebiger Werte stimmen kann. Viele dieser Nominierungen führen zu nichts, aber letztendlich kann der Knoten eines oder mehrere Werte annehmen oder bestätigen. Sobald der Nominierte bestätigt ist, wird er Kandidat.

Die Nominierung durch SCP unter Verwendung von föderativer Abstimmung. Es kann viele Werte "B" geben, die von gleichrangigen Knoten nominiert und von einem Knoten „reflektiert“ werden.

Die Nominierung von Kandidaten kann zur Entstehung mehrerer bestätigbarer Kandidaten führen. Daher verlangt SCP, dass die Anwendungsebene eine Methode bereitstellt, um Kandidaten in einen Kontrast (composite) zu vereinigen. Die Methode zur Vereinigung kann beliebig sein. Wichtig ist, dass, wenn diese Methode deterministisch ist, jeder Knoten dieselben Kandidaten vereint. Im Abstimmungssystem für das Mittagessen kann „Vereinigung“ einfach bedeuten, einen von zwei Kandidaten abzulehnen. (Aber deterministisch: Jeder Knoten muss denselben Wert für den Ausschluss wählen. Zum Beispiel eine frühere Wahl in alphabetischer Reihenfolge). Im Stellar-Zahlungsnetzwerk, wo die Abstimmung über Transaktionshistorien stattfindet, bedeutet die Vereinigung zweier vorgeschlagener Nominierter die Vereinigung der Transaktionen, die sie enthalten, und der letzten der beiden Zeitstempel. Technische Beschreibung von SCP beweist (Theorem 12), dass das Netzwerk am Ende der Nominationsphase auf einen einzigen Kontrast konvergiert. Aber es gibt ein Problem: Föderative Abstimmung ist ein asynchrones Protokoll (wie auch SCP). Mit anderen Worten, Knoten sind nicht zeitlich koordiniert, sondern nur durch die Nachrichten, die sie senden. Aus der Sicht eines Knotens ist unklar, wann

Die technische Beschreibung des SCP beweist (Theorem 12), dass das Netzwerk am Ende der Vorlagephase schließlich zu einem einzigen Komposit convergiert. Aber es gibt ein Problem: Das föderative Abstimmungssystem ist ein asynchrones Protokoll (wie auch SCP). Mit anderen Worten, die Knoten sind nicht zeitlich koordiniert, sondern nur durch die gesendeten Nachrichten. Aus der Sicht eines Knotens ist es unklar, wann die Unterstützung Phase der Kandidatenauswahl. Und obwohl alle Knoten letztendlich zu demselben Komposit gelangen, können sie auf diesem Weg unterschiedliche Routen wählen, wobei sie unterwegs verschiedene Kandidaten bilden und niemals sagen können, welcher von ihnen final ist.

Aber das ist in Ordnung. Die Kandidatenauswahl ist nur eine Vorbereitung. Es ist wichtig, die Anzahl der Kandidaten zu begrenzen, um einen Konsens zu erreichen, der im Prozess entsteht. Wahlvorgang (Wahlvorgang).

Wahlvorgang

Ein Wahlzettel ist ein Paar , wobei counter eine ganze Zahl ist, die mit 1 beginnt, und value ein Kandidat aus der Phase der Kandidatenauswahl ist. Es kann sich um den eigenen Kandidaten des Knotens oder um einen Kandidaten des benachbarten Knotens handeln, der von diesem Knoten angenommen wurde. Grob gesagt unternimmt der Wahlvorgang wiederholte Versuche, das Netzwerk dazu zu bringen, einen Konsens über einen bestimmten Kandidaten auf einem bestimmten Wahlzettel durch die Durchführung von potenziell vielen föderativen Abstimmungen über Wahlzettelaussagen zu erreichen. Die Zähler auf den Wahlzetteln verfolgen die unternommenen Versuche, und Wahlzettel mit höheren Zählern haben Vorrang vor solchen mit niedrigeren Zählern. Wenn der Wahlzettel feststeckt, beginnt eine neue Abstimmung, nun über den Wahlzettel .

Es ist wichtig zu unterscheiden Werte (zum Beispiel, was die Bestellung zum Mittagessen angeht: Pizza oder Salate), Wahlzettel (Paar counter-value) und Aussagen zu Wahlzetteln. Eine SCP-Runde umfasst mehrere Runden föderativer Abstimmungen, insbesondere zu solchen Aussagen:

• "Ich bin bereit, den Wahlzettel B zu genehmigen" und
• "Ich kündige die Genehmigung des Wahlzettels B an"

Aus Sicht dieses Knotens wird Konsens erreicht, wenn er den Wahlzettel B findet, für den er die Aussage "Ich kündige die Genehmigung des Wahlzettels B an" bestätigen kann (das heißt, einen Quorum finden, das dies annimmt). Ab diesem Moment kann sicher mit dem Wert, der in B angegeben ist, gehandelt werden – zum Beispiel diese Bestellung zum Mittagessen aufgegeben werden. Dies wird als Externalisierung des Wertes bezeichnet. Sobald die Annahme des Wahlzettels bestätigt ist, kann der Knoten sicher sein, dass jeder andere Knoten dieser gleichen Wert ebenfalls externisiert hat oder dies in der Zukunft zwangsläufig tun wird.

Obwohl konzeptionell viele föderative Abstimmungen auf Erklärungen zu zahlreichen verschiedenen Abstimmungsunterlagen stattfinden, erfolgt der Austausch nicht mit allzu vielen Nachrichten, da jede Nachricht eine Reihe von Abstimmungen verkapselt. Eine Nachricht fördert somit den Zustand vieler föderativer Abstimmungen gleichzeitig, zum Beispiel: „Ich akzeptiere das Commit der Abstimmung von bis .“

Was bedeuten die Begriffe „vorbereitet“ (prepared) und „commit“ (commit)?

Ein Knoten stimmt für das Commit eines Abstimmungsunterlagens, wenn er überzeugt ist, dass andere Knoten keine Commit für Abstimmungen mit anderen Werten vornehmen werden. Diese Überzeugung ist das Ziel der Vorbereitung der Erklärung. Eine Abstimmung, in der gesagt wird: „Ich bin bereit für das Commit der Abstimmung B“, ist das Versprechen, niemals ein Commit für eine Abstimmung mit einem Wert kleiner als B vorzunehmen, d. h. mit einem kleineren Zähler (SCP verlangt, dass die Werte in den Abstimmungen eine bestimmte Reihenfolge haben. Somit ist die Abstimmung kleiner als , wenn N1<N2, und auch wenn N1=N2 und V1<V2). Diese kleineren Abstimmungen werden im Rahmen der vorbereitenden Abstimmung „abgebrochen“ (aborted), während B als „vorbereitet“ gilt.

Warum bedeutet „Ich bin bereit für das Commit der Abstimmung B“, dass ich verspreche, niemals ein Commit für Abstimmungen kleiner B zuzulassen? Weil SCP abort als das Gegenteil von commit definiert. Das Abstimmen zur Vorbereitung der Abstimmung impliziert auch das Abstimmen zum Abbrechen anderer Abstimmungen, und, wie bereits besprochen, ist das Abstimmen für etwas ein Versprechen, niemals gegen es zu stimmen.

Bevor ein Commit übertragen wird, muss der Knoten zuerst eine Abstimmung finden, die er als vorbereitet bestätigen kann. Mit anderen Worten, er führt eine föderative Abstimmung zur Frage „Ich bin bereit für das Commit der Abstimmung B“ durch, möglicherweise für viele verschiedene Abstimmungen, bis er eine findet, die das Quorum akzeptiert.

Woher kommen die Stimmzettel für die Abstimmungsvorbereitung? Zunächst überträgt der Knoten die Vorbereitung zur Abstimmung für , wobei C der Kandidat-Komposit ist, der in der Phase der Nominierung erstellt wurde. Selbst nach Beginn der Abstimmungsvorbereitung kann die Nominierung jedoch zur Entstehung zusätzlicher Kandidaten führen, die neue Stimmzettel werden. In der Zwischenzeit kann es unterschiedliche Kandidaten unter den Peers geben, und sie können eine blockierende Menge bilden, die akzeptiert: „Ich bin bereit, das Commit des Stimmzettels B2 vorzunehmen“, was den Knoten überzeugt, dies ebenfalls zu akzeptieren. Schließlich gibt es einen Timeout-Mechanismus, der neue Runden der föderierten Abstimmung mit neuen Stimmzetteln und höheren Zählern generiert, falls die aktuellen Stimmzettel feststecken.

Sobald der Knoten einen Stimmzettel B findet, der als vorbereitet bestätigt werden kann, sendet er eine neue Nachricht: „Commit des Stimmzettels B“. Dieses Abstimmungsergebnis sagt den Peers, dass der Knoten B niemals aufgeben wird. Tatsächlich bedeutet, wenn B ein Stimmzettel darstellt, dass „Commit des Stimmzettels “ bedingungslose Zustimmung bedeutet, für die Bereitwilligkeit jedes Stimmzettels von bis zu stimmen. Dieser zusätzliche Wert hilft anderen Knoten, den Peer mit dem Commit einzuholen, wenn 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 gegen ein Commit stimmt, bedeutet das nicht, dass seine Peers dies ebenfalls tun. Einige von ihnen können immer noch über Aussagen abstimmen, um sich auf die Abstimmung vorzubereiten, während andere möglicherweise den Wert bereits externalisiert haben. SCP erklärt, wie ein Knoten jede Art von Peer-to-Peer-Nachricht unabhängig von seiner Phase verarbeiten sollte.

Wenn die Nachricht „Ich kündige die Abstimmung <N,C>“ nicht angenommen oder bestätigt werden kann, besteht die Möglichkeit, dass die Nachricht <N+1,C> oder <N+2,C> angenommen oder bestätigt wird – oder in jedem Fall irgendein Bulletin mit dem Wert C und nicht einem anderen, da der Knoten bereits versprochen hat, <N,C> niemals zurückzunehmen. Bis zu dem Zeitpunkt, an dem der Knoten Stimmen für die Abstimmung überträgt, wird es C oder nichts sein, je nachdem, wie weit der Konsens voranschreitet. Allerdings reicht dies dem Knoten noch nicht aus, um C zu externalisieren. Einige byzantinische Piraten (die weniger als die erforderliche Anzahl an Quoren basierend auf unseren Sicherheitsannahmen ausmachen) könnten den Knoten anlügen. Die Annahme und danach die Bestätigung eines bestimmten Bulletins (oder eines Bereichs von Bulletins) ist es, was dem Knoten das Vertrauen gibt, schließlich C zu externalisieren.

Die Abstimmung von SCP durch föderierte Abstimmung. Nicht angezeigt: Jederzeit kann ein Timer ausgelöst werden, der den Zähler im Bulletin erhöht (und möglicherweise einen neuen Komposit aus zusätzlichen nominierten Kandidaten erzeugt).

Und das ist alles! Sobald das Netzwerk zu einem Konsens gelangt ist, ist es bereit, dies immer wieder zu tun. Im Zahlungsnetzwerk Stellar geschieht dies ungefähr alle 5 Sekunden: ein Kunststück, das sowohl Sicherheit als auch Widerstandsfähigkeit erfordert, die durch SCP garantiert sind.

SCP kann dies erreichen, indem es sich auf mehrere Runden föderierter Abstimmung stützt. Föderierte Abstimmung wurde durch das Konzept der Quoren-Slices möglich: Gruppen von gleichwertigen Knoten, denen jeder Knoten beschlossen hat, als Teil seines (subjektiven) Quorums zu vertrauen. Diese Konfiguration bedeutet, dass ein Konsens sogar in einem Netzwerk mit offener Mitgliedschaft und byzantinischen Betrügereien erreicht werden kann.

Weitere Lektüre

• Das originale technische Dokument zu SCP finden Sie unter hier, und hier Projekt zur Spezifikation für seine Implementierung.
• Der ursprüngliche Autor des SCP-Protokolls, David Mazieres, erklärt es vereinfacht (aber dennoch technisch) hier.
• Vielleicht waren Sie überrascht, in diesem Artikel die Begriffe „Mining“ oder „Proof of Work“ nicht zu finden. SCP verwendet diese Methoden nicht, aber einige andere Konsensalgorithmen tun dies. Zane Wiserspoon hat einen zugänglichen Überblick über Konsensalgorithmen.
• Schritt-für-Schritt-Beschreibung eines einfachen Netzwerks, das in einer vollständigen Runde SCP Konsens erreicht.
• Für Leser, die sich für Implementierungen von SCP interessieren: siehe C++-Code, der von dem Zahlungsnetzwerk Stellar verwendet wird, oder Go-Code, den ich zum besseren Verständnis des SCP erstellt habe.

Quelle: habr.com