Das Stellar-Konsensprotokoll wurde erstmals in beschrieben David Mazier im Jahr 2015. Hierbei handelt es sich um ein „föderales byzantinisches Vereinbarungssystem“, das es dezentralen, führerlosen Computernetzwerken ermöglicht, effizient einen Konsens über eine Entscheidung zu erzielen. Das Stellar-Zahlungsnetzwerk nutzt das Stellar Consensus Protocol (SCP), um einen konsistenten Transaktionsverlauf zu pflegen, der für alle Teilnehmer sichtbar ist.
Konsensprotokolle gelten als schwer verständlich. SCP ist einfacher als die meisten von ihnen, teilt aber dennoch diesen Ruf – teilweise aufgrund der falschen Vorstellung, dass „federated vote“, um das es in der ersten Hälfte des wissenschaftlichen Artikels geht, SCP sei. Aber das ist nicht so! Dies ist nur ein wichtiger Baustein, der in der zweiten Hälfte des Artikels erstellt wird von tatsächlichen Stellar-Konsensprotokoll.
In diesem Artikel erklären wir kurz, was ein „System von Vereinbarungen“ ist, was es „byzantinisch“ machen kann und warum das byzantinische System „föderal“ ist. Anschließend erläutern wir das im SCP-Artikel beschriebene Verfahren der föderierten Abstimmung und schließlich das SCP-Protokoll selbst.
Vereinbarungssysteme
Ein System von Vereinbarungen ermöglicht es einer Gruppe von Teilnehmern, einen Konsens über ein Thema zu erzielen, beispielsweise darüber, was zum Mittagessen bestellt werden soll.
Bei Interstellar haben wir unser eigenes Restaurantvereinbarungssystem 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 Nahrhaftes finden wird.
Aber was ist, wenn John unser Vertrauen missbraucht? Er kann im Alleingang entscheiden, dass wir alle Veganer werden sollten. In ein oder zwei Wochen werden wir ihn wahrscheinlich stürzen und die Macht an Elizabeth übergeben. Doch plötzlich liebt sie Avocados mit Sardellen und findet, dass jeder so sein sollte. Macht korrumpiert. Daher ist es besser, eine demokratischere Methode zu finden: eine Möglichkeit, sicherzustellen, dass unterschiedliche Vorlieben berücksichtigt werden und gleichzeitig ein zeitnahes und eindeutiges Ergebnis gewährleistet wird, sodass am Ende niemand das Mittagessen bestellt oder fünf Personen unterschiedliche Bestellungen aufgeben oder diskutieren zieht sich bis in den Abend hinein.
Es scheint, dass die Lösung einfach ist: Stimmen Sie ab! Doch dieser Eindruck täuscht. Wer sammelt die Stimmzettel ein und meldet die Ergebnisse? Und warum sollten andere glauben, was er sagt? Vielleicht können wir das zuerst Wählen Sie einen Anführer, dem wir vertrauen, dass er die Abstimmung leitet – der sie aber auch leiten wird zuerst durch Abstimmung? Was ist, wenn wir uns nicht auf einen Anführer einigen können? Oder was ist, wenn wir eine Einigung erzielen, dieser Leiter aber in einer Besprechung stecken bleibt oder krankgeschrieben wird?
Ähnliche Probleme treten in verteilten Computernetzwerken auf. Alle Teilnehmer oder Knoten müssen sich auf eine Entscheidung einigen, beispielsweise darauf, wer an der Reihe ist, eine gemeinsam genutzte Datei zu aktualisieren oder eine Aufgabe aus der Verarbeitungswarteschlange zu entfernen. In einem Kryptowährungsnetzwerk müssen Knoten immer wieder aus mehreren möglichen Versionen auswählen, wie die vollständige Geschichte aussieht, was manchmal zu Konflikten führt. Diese Netzwerkvereinbarung bietet dem Empfänger die Gewissheit, dass die Münze (a) gültig (nicht gefälscht) und (b) noch nicht anderweitig ausgegeben wurde. Dadurch wird auch sichergestellt, dass er die Coins auch in Zukunft ausgeben kann, da der neue Empfänger aus den gleichen Gründen über die gleichen Garantien verfügt.
Jedes Konsenssystem in einem verteilten Computernetzwerk muss fehlertolerant sein: Es muss trotz Fehlern wie langsamen Verbindungen, nicht reagierenden Knoten und falscher Nachrichtenreihenfolge konsistente Ergebnisse liefern. Byzantinisch Das Vereinbarungssystem ist außerdem resistent gegen „byzantinische“ Fehler: Knoten, die falsche Informationen liefern, sei es aufgrund eines Fehlers oder in dem bewussten Versuch, das System zu untergraben oder sich einen Vorteil zu verschaffen. Als „byzantinische“ Fehlertoleranz wird die Fähigkeit bezeichnet, einer Gruppenentscheidung zu vertrauen, selbst wenn einige Gruppenmitglieder lügen oder sich anderweitig nicht an die Regeln der Entscheidungsfindung halten der versuchte, den Angriff zu koordinieren. bei Anthony Stevens.
Denken Sie an die Besitzerin der Kryptomünze Alice, die sich entscheiden muss, ob sie bei Bob leckeres Eis kauft oder Carols Schulden begleicht. Vielleicht möchte Alice beides auf einmal bezahlen, indem sie in betrügerischer Absicht dieselbe Münze ausgibt. Dazu muss sie Bobs Computer davon überzeugen, dass die Münze nie an Carol ausgezahlt wurde, und Carols Computer davon überzeugen, dass die Münze nie an Bob ausgezahlt wurde. Das byzantinische System der Vereinbarungen macht dies praktisch unmöglich, indem es eine Form der sogenannten Mehrheitsregel verwendet Quorum. Ein Knoten in einem solchen Netzwerk weigert sich, zu einer bestimmten Version des Verlaufs zu wechseln, bis er feststellt, dass eine ausreichende Anzahl von Peers – ein Quorum – einem solchen Übergang zustimmt. Sobald dies geschieht, bilden sie einen Abstimmungsblock, der groß genug ist, um die verbleibenden Netzwerkknoten zu zwingen, ihrer Entscheidung zuzustimmen. Alice kann einige Knoten dazu zwingen, 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 das Quorum erforderlich? Mindestens eine Mehrheit bzw. eine qualifizierte Mehrheit zur Bekämpfung von Fehlern und Betrug. Um die Mehrheit zu zählen, müssen Sie jedoch die Gesamtzahl der Teilnehmer kennen. Im Interstellar-Büro oder bei den Bezirkswahlen sind diese Zahlen leicht herauszufinden. Wenn es sich bei Ihrer Gruppe jedoch um ein lose definiertes Netzwerk handelt, in das Knoten nach Belieben und ohne Genehmigung des Zentrums eintreten und es verlassen können, dann benötigen Sie Folgendes föderal ein byzantinisches Vereinbarungssystem, das in der Lage ist, Quoren nicht anhand einer vorgegebenen Liste von Knoten, sondern dynamisch anhand einer sich ständig ändernden und zwangsläufig unvollständigen Momentaufnahme der Knoten zu einem bestimmten Zeitpunkt zu bestimmen.
Aus der Perspektive eines einzelnen Knotens in einem riesigen Netzwerk mag es unmöglich erscheinen, ein Quorum zu schaffen, aber es ist möglich. Ein solches Quorum kann sogar die Ergebnisse einer dezentralen Abstimmung garantieren. Das SCP-Whitepaper zeigt, wie dies mithilfe einer Prozedur namens „ durch Bundesabstimmung.
Für die Ungeduldigen
Der Rest des Artikels beschreibt die föderierte Abstimmung und das Stellar-Konsensprotokoll ausführlicher. Wenn Sie nicht an den Details interessiert sind, finden Sie hier einen allgemeinen Überblick über den Prozess.
- Die Knoten führen Bundesabstimmungsrunden über „Nominierte“ durch. Eine Bundesabstimmungsrunde bedeutet:
- Der Knoten stimmt für eine Aussage, zum Beispiel „Ich schlage den Wert von V vor“;
- Der Knoten lauscht den Stimmen der Peers, bis er einen findet, der „empfangen“ kann;
- Der Knoten sucht nach einem „Quorum“ für diese Behauptung. Ein Quorum „bestätigt“ den Kandidaten.
- Sobald ein Knoten einen oder mehrere Nominierte bestätigen kann, versucht er, die „Abstimmung“ durch mehrere Runden gemeinsamer Abstimmung „vorzubereiten“.
- Sobald ein Knoten in der Lage ist, zu überprüfen, ob der Stimmzettel bereit ist, versucht er, ihn durch noch weitere Runden gemeinsamer Abstimmungen zu bestätigen.
- Sobald ein Knoten die Zusage einer Abstimmung bestätigen kann, kann er den Wert dieser Abstimmung „externalisieren“, indem er ihn als Konsensergebnis verwendet.
Diese Schritte umfassen mehrere Runden der Verbundabstimmung, die zusammen eine SCP-Runde bilden. Schauen wir uns genauer an, was bei jedem Schritt passiert.
Föderierte Abstimmung
Beim Federated Voting handelt es sich um ein Verfahren zur Feststellung, ob sich das Netzwerk auf einen Vorschlag einigen kann. In der Abstimmungsrunde muss jeder Knoten einen von potenziell vielen möglichen Werten auswählen. Dies ist nicht möglich, es sei denn, es ist zuversichtlich, dass andere Knoten im Netzwerk kein anderes Ergebnis wählen. Um dies sicherzustellen, tauschen die Knoten eine Flut von Nachrichten hin und her, sodass jeder bestätigtDass Kollegium Knoten dauert gleiche Entscheidung. Im Rest dieses Abschnitts werden die Begriffe in diesem Satz und der Ablauf des gesamten Verfahrens erläutert.
Quoren und Quorum-Slices
Beginnen wir mit der Definition eines Quorums. Wie wir oben besprochen haben, ist es in einem dezentralen Netzwerk mit dynamischer Mitgliedschaft unmöglich, im Voraus zu wissen, wie viele Knoten es gibt und wie viele daher für die Mehrheit benötigt werden. Die föderierte Abstimmung löst dieses Problem durch die Einführung einer neuen Idee Quorum-Kürzung (Quorum-Slice): Eine kleine Gruppe von Peers, denen ein Knoten vertraut, um Abstimmungsstatusinformationen an den Rest des Netzwerks zu übermitteln. Jeder Knoten definiert seinen eigenen Quorum-Slice (dessen De-facto-Mitglied er wird).
Die Bildung des Kollegiums beginnt mit einem Kollegiumsschnitt. Für jeden Knoten werden seine Schnittknoten hinzugefügt. Dann werden die Slice-Terme hinzugefügt diese Knoten usw. Je weiter Sie fortfahren, desto mehr Knoten können Sie nicht hinzufügen, da sie bereits im Slice enthalten sind. Wenn keine neuen Knoten mehr hinzugefügt werden müssen, stoppt der Prozess: Wir haben ein Quorum durch „transitive Schließung“ des Quorum-Slice des ursprünglichen Knotens gebildet.
Um das Quorum eines bestimmten Knotens zu ermitteln ...
... Mitglieder seines Slice hinzufügen...
... dann fügen wir Slice-Mitglieder dieser Knoten hinzu.
Wir fahren fort, bis keine Knoten mehr hinzugefügt werden können.
Es sind keine Knoten mehr zum Hinzufügen vorhanden. Dies ist ein Quorum.
Tatsächlich kann jeder Knoten in mehr als einem Slice erscheinen. Um ein Quorum zu bilden, wählen Sie nur einen der Slices aus und fügen Sie Mitglieder hinzu. Wählen Sie dann für jedes Mitglied einen beliebigen Slice aus und fügen Sie Mitglieder hinzu sie schneiden und so weiter. Dies bedeutet, dass jeder Knoten Mitglied vieler möglicher Quoren ist.
Wählen Sie bei jedem Schritt nur ein Quorum-Slice aus.
Ein mögliches Quorum. Oder eine Alternative...
...andere Slices auswählen...
…(wenn es möglich ist)…
... schafft ein weiteres Quorum.
Woher weiß ein Knoten, in welchen Slices sich andere Knoten befinden? Genauso wie andere Informationen über andere Knoten: aus den Übertragungen, die jeder Knoten an das Netzwerk sendet, wenn sich sein Abstimmungsstatus ändert. Jeder Broadcast enthält Informationen über die Slices des sendenden Knotens. Das SCP-Whitepaper spezifiziert keinen Kommunikationsmechanismus. Implementierungen verwenden normalerweise für eine garantierte Übertragung von Nachrichten im gesamten Netzwerk.
Denken Sie daran, dass im nicht-föderalen byzantinischen Abkommenssystem ein Quorum als Mehrheit aller Knoten definiert ist. Das byzantinische Vertragssystem ist unter dem Gesichtspunkt der Frage konzipiert: Wie viele unehrliche Knoten kann das System tolerieren? In einem System von N Knoten, die darauf ausgelegt sind, f Ausfälle zu überstehen, sollte ein Knoten in der Lage sein, Fortschritte zu erzielen, indem er Feedback von N − f Peers erhält, da f von ihnen möglicherweise ausgefallen sind. 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 die Antwort empfangen wurde) böswillig. Damit Knoten zu demselben Konsens kommen, muss die Mehrheit der verbleibenden Knoten ehrlich sein, das heißt, wir müssen N−f größer als 2f oder N > 3f sein. Typischerweise verfügt ein System, das f-Ausfälle übersteht, über insgesamt N=3f+1 Knoten und eine Quorumgröße von 2f+1. Sobald ein Vorschlag die Quorumsschwelle erreicht, ist der Rest des Netzwerks davon überzeugt, dass alle konkurrierenden Vorschläge scheitern werden. So konvergiert das Netzwerk 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 auch völlig nutzlos! Wenn die Mitgliedschaft im System offen ist, kann jemand die Mehrheit erlangen, indem er einfach einen sogenannten Sybil-Angriff durchführt: wiederholten Beitritt zum Netzwerk über mehrere Knoten hinweg. Warum kann also ein transitiver Slice-Schließung aufgerufen werden? Quorum, und wie kann es konkurrierende Vorschläge unterdrücken?
Technisch gesehen auf keinen Fall! Stellen Sie sich ein Netzwerk aus sechs Knoten vor, in dem zwei Tripletts in den Quorum-Slices des jeweils anderen isoliert sind. Die erste Untergruppe kann eine Entscheidung treffen, von der die zweite nie erfahren wird, und umgekehrt. Es gibt für dieses Netzwerk keine Möglichkeit, einen Konsens zu erzielen (außer durch Zufall).
Daher verlangt SCP, dass das Netzwerk für eine föderierte Abstimmung (und für die Anwendung der wichtigen Theoreme des Papiers) über eine Eigenschaft namens verfügen muss Schnittpunkt der Kollegien. In einem Netzwerk mit dieser Eigenschaft überlappen sich zwei beliebige Quoren, die erstellt werden können, immer in mindestens einem Knoten. Um die vorherrschende Stimmung im Netzwerk zu bestimmen, ist dies genauso gut wie eine Mehrheit. Intuitiv bedeutet dies, dass, wenn irgendein Quorum der Aussage
Wenn es im Netzwerk eine Überschneidung der Quoren gibt ...
... dann können Sie zwei beliebige Kollegien aufbauen ...
...wird sich immer überschneiden.
(Natürlich kann sich herausstellen, dass überlappende Knoten byzantinisch lügen oder auf andere Weise schlecht sind. In diesem Fall trägt die Quorum-Schnittmenge überhaupt nicht dazu bei, dass das Netzwerk zustimmt. Aus diesem Grund basieren viele der Ergebnisse im SCP-Whitepaper auf explizite Annahmen, z. B. was beim Quorum-Crossing des Netzwerks übrig bleibt auch nach dem Entfernen fehlerhafter Knoten. Der Einfachheit halber belassen wir diese Annahmen implizit im Rest des Artikels).
Es mag unangemessen erscheinen, zu erwarten, dass in einem Netzwerk unabhängiger Knoten ein zuverlässiges Quorum-Crossing möglich ist. Dafür gibt es aber zwei Gründe.
Der erste Grund ist die Existenz des Internets selbst. Das Internet ist ein perfektes Beispiel für ein Netzwerk unabhängiger Knoten mit sich überschneidenden Quoren. Die meisten Knoten im Internet sind nur mit wenigen anderen lokalen Knoten verbunden, aber diese kleinen Gruppen überlappen sich so weit, dass jeder Knoten von jedem anderen Knoten entlang einer Route erreicht werden kann.
Der zweite Grund ist spezifisch für das Stellar-Zahlungsnetzwerk (die häufigste Verwendung von SCP). Jeder Vermögenswert im Stellar-Netzwerk hat einen Emittenten, und die Richtlinien von Stellar erfordern, dass jeder Emittent einen oder mehrere Knoten im Netzwerk für die Bearbeitung von Rücknahmeanträgen benennt. Es liegt in Ihrem Interesse, diese Knoten direkt oder indirekt in Quorum-Slices für jedes Asset, an dem Sie interessiert sind, einzubeziehen. Die Quoren für alle Knoten, die an einem bestimmten Vermögenswert interessiert sind, überschneiden sich dann zumindest an diesen Einlösungsknoten. Knoten, die an mehreren Vermögenswerten interessiert sind, werden alle Rücknahmeknoten der jeweiligen Emittenten in ihre Quorum-Slices aufnehmen und versuchen, alle Vermögenswerte zusammenzufassen. Darüber hinaus alle Vermögenswerte, die nicht auf diese Weise mit anderen im Netzwerk verknüpft sind, und sollte nicht angeschlossen werden - Dies ist so konzipiert, dass es für dieses Netzwerk keine Quorumsüberschneidungen gibt (z. B. möchten Banken aus der Dollarzone manchmal mit Banken aus der Eurozone und Banken aus der Pesozone handeln, sodass sie im selben Netzwerk sind, aber keines). von ihnen kümmern sich um das separate Netzwerk von Kindern, die Baseballkarten verkaufen).
Natürlich ожидание Quorum-Crossing ist nicht der Fall Garantie. Andere byzantinische Vertragssysteme verdanken einen Großteil ihrer Komplexität der Garantie von Quoren. Eine wichtige Neuerung von SCP besteht darin, dass es die Verantwortung für die Erstellung von Quoren vom Konsensalgorithmus selbst entfernt und auf die Anwendungsebene verlagert. Obwohl also die föderierte Abstimmung allgemein genug ist, um über jedes Thema abzustimmen, hängt ihre Zuverlässigkeit tatsächlich entscheidend von der breiteren Bedeutung dieser Bedeutungen ab. Einige hypothetische Verwendungen sind möglicherweise nicht so förderlich für die Schaffung gut vernetzter Netzwerke wie andere.
Abstimmung, Annahme und Bestätigung
In einer föderierten Abstimmungsrunde beginnt ein Knoten optional damit, für einen Wert V zu stimmen. Dies bedeutet, dass eine Nachricht an das Netzwerk gesendet wird: „Ich bin Knoten N, meine Quorum-Slices sind Q und ich stimme für V.“ Wenn ein Knoten auf diese Weise abstimmt, verspricht er, dass er nie gegen V gestimmt hat und auch nie gegen V gestimmt hat.
Bei Peer-to-Peer-Broadcasts sieht jeder Knoten, wie die anderen abstimmen. Sobald ein Knoten genügend dieser Nachrichten gesammelt hat, kann er Quorum-Slices verfolgen und versuchen, Quorums zu finden. Wenn er ein Quorum von Gleichaltrigen sieht, die ebenfalls für V stimmen, kann er fortfahren Annahme V und sende diese neue Nachricht an das Netzwerk: „Ich bin Knoten N, meine Quorum-Slices sind Q und ich akzeptiere V.“ Die Akzeptanz bietet eine stärkere Garantie als die einfache Abstimmung. Wenn ein Knoten für V stimmt, kann er niemals für andere Optionen stimmen. Aber wenn ein Knoten V akzeptiert, wird kein Knoten im Netzwerk jemals die andere Option akzeptieren (Theorem 8 im SCP-Whitepaper beweist dies).
Natürlich besteht eine hohe Wahrscheinlichkeit, dass es nicht sofort ein Quorum von Knoten gibt, die mit V übereinstimmen. Andere Knoten stimmen möglicherweise für andere Werte. Es gibt jedoch noch eine andere Möglichkeit für einen Knoten, von der einfachen Abstimmung zur Akzeptanz überzugehen. N kann einen anderen Wert für W akzeptieren, auch wenn er nicht dafür gestimmt hat und selbst wenn er kein Quorum dafür sieht. Um zu entscheiden, ob Sie Ihre Stimme ändern möchten, lesen Sie einfach Sperrsatz Knoten, die W akzeptiert haben. Ein Blockierungssatz ist ein Knoten aus jedem der Quorum-Slices N. Wie der Name schon sagt, ist dies möglich zu blockieren irgendeine andere Bedeutung. Wenn alle Knoten in einer solchen Menge W akzeptieren, dann wird es (nach Satz 8) niemals möglich sein, ein Quorum zu bilden, das einen anderen Wert annimmt, und daher ist es auch für N sicher, W zu akzeptieren.
Knoten N mit drei Quorum-Slices.
BDF ist eine Blockierungsmenge für N: Sie enthält einen Knoten aus jedem der Slices von N.
BE ist auch eine Blockierungsmenge für N, da E in zwei Scheiben von N vorkommt.
Der Sperrsatz ist jedoch nicht beschlussfähig. Es wäre zu einfach, Knoten N dazu zu bringen, den gewünschten Wert zu akzeptieren, wenn es ausreichen würde, nur einen Knoten in jedem der Slices von N zu hacken. Daher ist das Akzeptieren des Werts nicht das Ende der Abstimmung. Stattdessen muss N den Wert bestätigen, d. h. es muss ein Quorum von Knoten vorhanden sein, die ihn akzeptieren. Wenn es so weit kommt, dann wird, wie das SCP-Whitepaper (in Satz 11) beweist, auch der Rest des Netzwerks irgendwann denselben Wert bestätigen, sodass N die föderierte Abstimmung mit einem bestimmten Wert als Ergebnis beenden wird.
Föderierte Abstimmung.
Der Prozess der Abstimmung, Annahme und Bestätigung stellt eine vollständige Runde der gemeinsamen Abstimmung dar. Das Stellar-Konsensprotokoll kombiniert viele dieser Runden, um ein vollständiges Konsenssystem zu schaffen.
Stellar-Konsensprotokoll
Die beiden wichtigsten Eigenschaften eines Konsenssystems sind − Sicherheit и Vitalität. Ein Konsensalgorithmus ist „sicher“, wenn er verschiedenen Teilnehmern niemals unterschiedliche Ergebnisse liefern kann (Bobs Kopie der Geschichte wird Carol niemals widersprechen). „Livability“ bedeutet, dass der Algorithmus immer ein Ergebnis liefert, also nicht hängen bleibt.
Beschriebenes Bundeswahlverfahren sicher in dem Sinne, dass, wenn ein Knoten den Wert von V bestätigt, kein anderer Knoten den anderen Wert bestätigen wird. Aber „wird keine andere Bedeutung bestätigen“ bedeutet nicht, dass es notwendigerweise etwas bestätigt. Die Teilnehmer können über so viele verschiedene Werte abstimmen, dass nichts die Akzeptanzschwelle erreicht. Dies bedeutet, dass es bei Bundeswahlen keine gibt Vitalität.
Das Stellar-Konsensprotokoll nutzt die föderierte Abstimmung auf eine Weise, die sowohl Sicherheit als auch Überlebensfähigkeit gewährleistet. (SCP-Sicherheits- und Überlebensgarantien haben eine theoretische Grenze. Das Design wählt eine sehr starke Sicherheitsgarantie und opfert eine kleine Überlebensfähigkeitsminderung, aber mit genügend Zeit ist es sehr wahrscheinlich, dass ein Konsens erzielt wird.) Kurz gesagt besteht die Idee darin, mehrere gemeinsame Abstimmungen über mehrere Werte durchzuführen, bis einer von ihnen alle unten beschriebenen SCP-Abstimmungsphasen durchläuft.
Die Werte, über die SCP einen Konsens anstrebt, könnten der Transaktionsverlauf, 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 erfolgt die Bundesabstimmung gem Aussagen zu diesen Werten.
Die ersten Wahlgänge auf Bundesebene finden am statt Nominierungsphase (Nominierungsphase) auf einer Reihe von Aussagen wie „Ich nominiere V“, möglicherweise für viele verschiedene Werte von V. Der Zweck der Nominierung besteht darin, eine oder mehrere Aussagen zu finden, die Akzeptanz und Bestätigung durchlaufen.
Nachdem SCP überprüfbare Kandidaten gefunden hat, geht es mit der Abstimmungsphase weiter, in der das Ziel darin besteht, einen bestimmten Kandidaten zu finden Bulletin (d. h. ein Container für den vorgeschlagenen Wert) und ein Quorum, das erklärt werden kann verpflichten dafür (commit). Wenn ein Quorum eine Abstimmung vornimmt, wird sein Wert als Konsens akzeptiert. Doch bevor ein Knoten über eine Wahlzusage abstimmen kann, muss er zunächst bestätigen Stornierung alle Stimmzettel mit einem niedrigeren Zählerwert. Diese Schritte – das Annullieren von Stimmzetteln, um einen zu finden, der bestätigt werden kann – umfassen mehrere Runden gemeinsamer Abstimmung über mehrere Stimmzettelanträge.
In den folgenden Abschnitten werden Nominierung und Abstimmung ausführlicher beschrieben.
Nominierung
Zu Beginn der Nominierungsphase kann jeder Knoten spontan einen Wert für V wählen und für die Aussage „Ich nominiere V“ stimmen. Das Ziel in dieser Phase besteht darin, die Nominierung von gewissem Wert durch eine gemeinsame Abstimmung zu bestätigen.
Möglicherweise stimmen genügend Knoten über ausreichend unterschiedliche Vorschläge ab, sodass keine Nominierung die Annahmeschwelle erreichen kann. Daher „spiegeln“ Knoten zusätzlich zur Übertragung ihrer eigenen Nominierungsstimmen die Nominierungen ihrer Kollegen wider. Echo bedeutet, dass, wenn ein Knoten für Nominierung V stimmt, aber eine Nachricht von einem Nachbarn sieht, der für Nominierung W stimmt, er nun sowohl für V als auch für W stimmen wird. (Nicht alle Peer-Stimmen werden während der Nominierung wiedergegeben, da dies zu einer Explosion von führen kann verschiedene Nominierte. SCP enthält einen Mechanismus zur Regulierung dieser Stimmen. Kurz gesagt, es gibt eine Formel zur Bestimmung der „Priorität“ eines Peers aus Sicht eines Knotens, und nur die Stimmen von Knoten mit hoher Priorität werden reflektiert. Je länger die Nominierung dauert nimmt, desto niedriger ist der Schwellenwert, sodass der Knoten die Gruppe der Peers erweitert, deren Stimmen er widerspiegelt. Die Prioritätsformel umfasst die Slot-Nummer als eine ihrer Eingaben, sodass ein Peer mit hoher Priorität für einen Slot ein Peer mit niedriger Priorität sein kann ein anderer und umgekehrt).
Konzeptionell ist die Nominierung parallel, sowohl V als auch W sind separate Bundesstimmen, die jeweils einzeln angenommen oder bestätigt werden können. In der Praxis bündeln SCP-Protokollnachrichten diese einzelnen Stimmen.
Obwohl die Abstimmung für die Nominierung von V ein Versprechen ist, niemals gegen die Nominierung von V zu stimmen, wird auf der Antragsebene – in diesem Fall SCP – festgelegt, was „dagegen“ bedeutet. SCP sieht keine Aussage, die der Abstimmung „Ich nominiere X“ widerspricht, das heißt, es gibt keine „Ich bin gegen die Nominierung von X“-Nachricht, sodass der Knoten für die Nominierung beliebiger Werte stimmen kann. Viele dieser Nominierungen werden nirgendwohin führen, aber irgendwann wird der Knoten in der Lage sein, einen oder mehrere Werte zu akzeptieren oder zu bestätigen. Sobald ein Kandidat bestätigt ist, wird er Kandidat.
SCP-Nominierung mittels föderierter Abstimmung. Es kann viele „B“-Werte geben, die von Peers vorgeschlagen und vom Knoten „reflektiert“ werden.
Aus Nominierungen können mehrere bestätigte Kandidaten resultieren. Daher erfordert SCP, dass die Anwendungsschicht eine Methode zum Kombinieren der Kandidaten zu einem bereitstellt zusammengesetzt (zusammengesetzt). Die Verbindungsmethode kann beliebig sein. Die Hauptsache ist, dass, wenn diese Methode deterministisch ist, jeder Knoten dieselben Kandidaten kombiniert. In einem Mittagsabstimmungssystem kann „Vereinigung“ einfach die Ablehnung eines von zwei Kandidaten bedeuten. (Allerdings auf deterministische Weise: Jeder Knoten muss denselben Wert zum Zurücksetzen auswählen. Zum Beispiel die frühere Auswahl in alphabetischer Reihenfolge.) Im Stellar-Zahlungsnetzwerk, wo über den Transaktionsverlauf abgestimmt wird, umfasst die Zusammenführung zweier vorgeschlagener Kandidaten die Zusammenführung der darin enthaltenen Transaktionen und des neuesten ihrer beiden Zeitstempel.
Das SCP-Whitepaper beweist (Theorem 12), dass das Netzwerk am Ende der Erweiterungsphase schließlich zu einem einzigen Verbund konvergiert. Aber es gibt ein Problem: Federated Voting ist ein asynchrones Protokoll (wie SCP). Mit anderen Worten: Knoten werden nicht zeitlich koordiniert, sondern nur durch die von ihnen gesendeten Nachrichten. Aus Sicht des Knotens ist unklar, wann beendet Verlängerungsphase. Und obwohl alle Knoten letztendlich zum gleichen Verbund gelangen, können sie auf dem Weg unterschiedliche Routen einschlagen, wodurch auf dem Weg unterschiedliche Verbundkandidaten entstehen, und sie können nie sagen, welcher der endgültige ist.
Aber es ist normal. Die Nominierung ist nur eine Vorbereitung. Dabei geht es vor allem darum, die Anzahl der Kandidaten zu begrenzen, um einen Konsens zu erreichen, der im Prozess entsteht für ein Amt kandidieren (Abstimmung).
Läuft
Bulletin ist ein Paar , wobei counter eine Ganzzahl ist, die bei 1 beginnt, und value ein Kandidat aus der Nominierungsphase ist. Dies kann der eigene Kandidat eines Knotens oder der von diesem Knoten akzeptierte Kandidat eines benachbarten Knotens sein. Grob gesagt handelt es sich bei einer Abstimmung um wiederholte Versuche, das Netzwerk dazu zu zwingen, einen Konsens über einen Kandidaten auf einem Stimmzettel zu erzielen, indem potenziell viele gemeinsame Abstimmungen über Stimmzettelerklärungen durchgeführt werden. Zähler auf den Stimmzetteln verfolgen die durchgeführten Versuche, und Stimmzettel mit einer höheren Zählung haben Vorrang vor Stimmzetteln mit einer niedrigeren Zählung. Wenn der Newsletter bleibt stecken, eine neue Abstimmung beginnt, jetzt auf dem Stimmzettel .
Es ist wichtig zu unterscheiden Bedeutung (z. B. wie soll die Mittagsbestellung aussehen: Pizza oder Salate), Newsletter (Gegenwertpaar) und Aussagen über Stimmzettel. Die SCP-Runde umfasst mehrere Bundesabstimmungsrunden, insbesondere zu den folgenden Aussagen:
- „Ich bin bereit, Stimmzettel B zu begehen“ und
- „Ich verkünde die Durchführung von Wahlgang B“
Aus Sicht eines bestimmten Knotens wird ein Konsens erreicht, wenn er einen Stimmzettel B findet, für den er die Aussage „Ich verpflichte Stimmzettel B“ bestätigen kann (d. h. ein Quorum findet, das dies akzeptiert). Ab diesem Zeitpunkt ist es sicher, auf den in B angegebenen Wert zu reagieren – beispielsweise die Bestellung eines Mittagessens aufzugeben. Das heißt Externalisierung Bedeutungen. Sobald die Annahme des Stimmzettels bestätigt ist, kann ein Knoten sicher sein, dass jeder andere Knoten denselben Wert externalisiert hat oder dies in Zukunft tun wird.
Obwohl viele Verbundabstimmungen konzeptionell auf Ansprüchen für viele verschiedene Stimmzettel basieren, werden dabei nicht so viele Nachrichten ausgetauscht, da jede Nachricht eine Reihe von Stimmzetteln umfasst. Eine Botschaft wirbt somit für den Zustand vieler föderierter Abstimmungen gleichzeitig, zum Beispiel: „Ich akzeptiere verbindliche Stimmzettel von Vor "
Was bedeuten die Begriffe „vorbereitet“ und „festschreiben“?
Ein Knoten stimmt dafür, einen Stimmzettel zu begehen, wenn er sicher ist, dass andere Knoten keine Stimmzettel mit anderen Werten begehen werden. Dies zu überzeugen, ist das Ziel der Antragserstellung. Eine Abstimmung mit der Aufschrift „Ich bin bereit, Stimmzettel B abzugeben“ ist ein Versprechen, niemals einen Stimmzettel kleiner als B, d weniger , wenn N1
Warum bedeutet „Ich bin bereit, Stimmzettel B abzugeben“ „Ich verspreche, niemals Stimmzettel kleiner als B abzugeben“? Weil SCP Abort als das Gegenteil von Commit definiert. Eine Abstimmung zur Vorbereitung eines Stimmzettels beinhaltet auch eine Abstimmung, um andere Stimmzettel zu disqualifizieren, und wie wir bereits besprochen haben, ist die Abstimmung für eine Sache ein Versprechen, niemals dagegen zu stimmen.
Bevor ein Commit gesendet wird, muss ein Knoten zunächst ein Bulletin finden, das er als vorbereitet bestätigen kann. Mit anderen Worten: Es führt eine gemeinsame Abstimmung zum Thema „Ich bin bereit für Stimmzettel B“ durch, möglicherweise über viele verschiedene Stimmzettel, bis einer gefunden wird, der ein Quorum akzeptiert.
Woher kommen die Stimmzettel zur Vorbereitung der Abstimmung? Zunächst sendet der Knoten Vorbereitungen zur Abstimmung für <1,C>, wobei C der zusammengesetzte Kandidat ist, der in der Nominierungsphase ermittelt wurde. Allerdings kann es auch nach Beginn der Abstimmungsvorbereitungen dazu kommen, dass Nominierungen dazu führen, dass weitere Kandidaten zu neuen Kandidaten werden. In der Zwischenzeit können Peers unterschiedliche Kandidaten haben und einen Blockierungssatz bilden, der „Ich bin bereit, die B2-Abstimmung vorzunehmen“ akzeptiert, was den Knoten davon überzeugt, dies ebenfalls zu akzeptieren. Schließlich gibt es einen Timeout-Mechanismus, der neue Runden der gemeinsamen Abstimmung über neue Stimmzettel mit höheren Stimmenzahlen generiert, wenn die aktuellen Stimmzettel stecken bleiben.
Sobald der Knoten einen Stimmzettel B findet, den er als vorbereitet bestätigen kann, sendet er eine neue Nachricht „Commit ballot B.“ Diese Abstimmung sagt den Peers, dass der Knoten B niemals aufgeben wird. Tatsächlich handelt es sich bei B um eine Abstimmung , dann „Wählen Sie aus „bedeutet die bedingungslose Zustimmung zur Stimmabgabe für die Bereitschaft jedes einzelnen Stimmzettels zu <∞, s>. Dieser zusätzliche Wert hilft anderen Peers, mit dem Commit-Peer Schritt zu halten, wenn sie sich noch in früheren Phasen des Protokolls befinden.
An dieser Stelle sei noch einmal betont, dass es sich um asynchrone Protokolle handelt. Nur weil ein Knoten Upvotes für einen Commit sendet, heißt das nicht, dass seine Peers dies auch tun. Einige von ihnen stimmen möglicherweise noch über Erklärungen in Vorbereitung auf die Abstimmung ab, andere haben die Bedeutung möglicherweise bereits veräußerlicht. SCP erklärt, wie ein Knoten jede Art von Peer-Nachricht unabhängig von ihrer Phase verarbeiten soll.
Wenn die Meldung „Ich habe einen Commit angekündigt » kann nicht empfangen oder bestätigt werden, d. h. die Wahrscheinlichkeit, dass die Nachricht angenommen oder bestätigt wird oder - oder auf jeden Fall jeder Stimmzettel mit dem Wert C und kein anderer, da der Knoten bereits versprochen hat, niemals zu stornieren . Wenn ein Knoten seine Stimmen für ein Commit sendet, wird es entweder C oder nichts sein, je nachdem, wie weit der Konsens geht. Dies reicht jedoch noch nicht aus, damit der Knoten C externalisieren kann. Einige byzantinische Peers (die aufgrund unserer Sicherheitsannahmen weniger als ein Quorum darstellen) könnten den Knoten anlügen. Das Akzeptieren und anschließende Bestätigen eines Stimmzettels (oder einer Reihe von Stimmzetteln) gibt dem Knoten das Vertrauen, C schließlich zu externalisieren.
SCP-Abstimmung durch Verbundabstimmung. Nicht angezeigt: Der Timer kann jederzeit ablaufen, wodurch sich die Zahl auf dem Stimmzettel erhöht (und möglicherweise eine neue Zusammenstellung zusätzlicher nominierter Kandidaten entsteht).
Und das ist alles! Sobald das Netzwerk einen Konsens erreicht hat, ist es bereit, dies immer wieder zu tun. Im Stellar-Zahlungsnetzwerk geschieht dies etwa alle 5 Sekunden: eine Leistung, die sowohl die von SCP garantierte Sicherheit als auch Überlebensfähigkeit erfordert.
SCP kann dies erreichen, indem es sich auf mehrere Runden gemeinsamer Abstimmungen verlässt. Die föderierte Abstimmung wird durch das Konzept der Quorum-Slices ermöglicht: Gruppen von Peers, denen jeder Knoten als Teil seines (subjektiven) Quorums vertraut. Diese Konfiguration bedeutet, dass auch in einem Netzwerk mit offener Mitgliedschaft und byzantinischen Täuschungen ein Konsens erzielt werden kann.
Weiterführende Literatur
- Das Original-SCP-Whitepaper finden Sie hier Und Entwurf von Spezifikationen für die Umsetzung.
- Der ursprüngliche Autor des SCP-Protokolls, David Mazier, erklärt es auf vereinfachte (aber immer noch technische) Weise. .
- Möglicherweise waren Sie überrascht, dass in diesem Artikel die Begriffe „Mining“ oder „Proof of Work“ nicht vorkommen. SCP verwendet diese Methoden nicht, einige andere Konsensalgorithmen jedoch. Zane Witherspoon schrieb barrierefrei .
- ein einfaches Netzwerk, das in einer vollständigen SCP-Runde einen Konsens erreicht.
- Für Leser, die sich für SCP-Implementierungen interessieren: siehe , verwendet vom Stellar-Zahlungsnetzwerk, oder , das ich zum besseren Verständnis von SCP geschrieben habe.
Source: habr.com