Sharding-Grundlagen

Beginnen wir mit dem einfachsten Sharding-Ansatz. Bei diesem Ansatz statt Wenn wir einen blockchain ausführen, werden wir mehrere ausführen und jeden solchen blockchain a nennen „Scherbe“. Jeder Shard verfügt über einen eigenen Satz von validators. Hier und unten verwenden wir ein allgemeiner Begriff „validator“, der sich auf Teilnehmer bezieht, die Transaktionen verifizieren und Produzieren Sie Blöcke, entweder durch Mining, wie zum Beispiel beim Proof of Work, oder über eine abstimmungsbasierte Methode 1Dieser Abschnitt wurde zuvor unter https://near.ai/shard1. veröffentlicht. Wenn Sie ihn schon einmal gelesen haben, Fahren Sie mit dem nächsten Abschnitt fort.

Mechanismus. Nehmen wir zunächst an, dass die Shards niemals miteinander kommunizieren andere. Obwohl dieser Entwurf einfach ist, reicht er aus, um einige erste große Herausforderungen beim Sharding zu skizzieren. 1.1 Validator-Partitionierung und Beacon-Ketten Angenommen, das System besteht aus 10 Shards. Die erste Herausforderung besteht bei jedem darin Da der Shard seine eigenen validators hat, ist jeder Shard jetzt zehnmal weniger sicher als der gesamte Kette. Wenn sich also eine nicht-shardierte Kette mit X validators für einen Hard Fork entscheidet in eine Shard-Kette und teilt X validators auf 10 Shards auf, jetzt jeden Shard hat nur X/10 validators und die Beschädigung eines Shards erfordert nur eine Beschädigung 5,1 % (51 % / 10) der Gesamtzahl der validators (siehe Abbildung 1), Abbildung 1: Aufteilen der validators auf Shards Das bringt uns zum zweiten Punkt: Wer wählt validators für jeden Shard aus? Die Kontrolle von 5,1 % der validators ist nur dann schädlich, wenn alle diese 5,1 % der validators vorhanden sind befinden sich im selben Shard. Wenn validators nicht auswählen können, welchen Shard sie validieren sollen Es ist höchst unwahrscheinlich, dass ein Teilnehmer, der 5,1 % der validators kontrolliert, alle bekommt ihre validators im selben Shard, was ihre Fähigkeit, Kompromisse einzugehen, stark einschränkt das System. Heutzutage basieren fast alle Sharding-Designs auf einer Zufallsquelle Weisen Sie Shards validators zu. Zufälligkeit bei blockchain an sich ist ein sehr herausforderndes Thema und wird in diesem Dokument nicht behandelt. Nehmen wir zunächst einmal an, dass dies der Fall ist eine Zufallsquelle, die wir nutzen können. Wir werden die Aufgabe von validators behandeln Weitere Einzelheiten finden Sie in Abschnitt 2.1. Sowohl die Zufälligkeit als auch die validator-Zuweisung erfordern eine Berechnung, die nicht erfolgt spezifisch für einen bestimmten Shard. Für diese Berechnung sind praktisch alle vorhanden Designs verfügen über einen separaten blockchain, der mit der Durchführung von Vorgängen beauftragt ist für die Aufrechterhaltung des gesamten Netzwerks notwendig. Neben der ZufallsgenerierungNummern und Zuweisen von validators zu den Shards, diese Vorgänge oft auch Dazu gehören das Empfangen von Aktualisierungen von Shards, das Erstellen von Snapshots davon und die Verarbeitung Einsätze und Kürzungen in Proof-of-Stake-Systemen und die Neuausrichtung der Shards in diesem Fall Funktion wird unterstützt. Eine solche Kette wird in Ethereum, einem Relay, als Beacon-Kette bezeichnet Kette in PolkaDot und der Cosmos Hub in Cosmos. In diesem Dokument bezeichnen wir eine solche Kette als Beacon-Kette. Die Existenz der Beacon-Kette bringt uns zum nächsten interessanten Thema, dem Quadratisches Sharding. 1.2 Quadratisches Sharding Sharding wird oft als eine Lösung beworben, die mit der Zahl unendlich skaliert der am Netzwerkbetrieb beteiligten Knoten. Obwohl es theoretisch möglich ist Entwerfen Sie eine solche Sharding-Lösung, jede Lösung, die das Konzept eines Beacons hat Die Kette ist nicht unbegrenzt skalierbar. Um zu verstehen, warum, beachten Sie, dass das Beacon Die Kette muss einige Buchhaltungsberechnungen durchführen, z. B. die Zuweisung von validators Shards oder Snapshot-Shard-Chain-Blöcke, die proportional zur Anzahl sind von Shards im System. Da die Beacon-Kette selbst eine einzelne blockchain ist, mit Berechnung, die durch die Rechenkapazitäten der Knoten, die sie betreiben, begrenzt ist, die Anzahl der Shards ist natürlich begrenzt. Die Struktur eines Sharded-Netzwerks verleiht jedoch einen Multiplikativ Auswirkungen auf alle Verbesserungen an seinen Knoten haben. Betrachten Sie den Fall, in dem ein willkürlicher Die Effizienz der Knoten im Netzwerk wird verbessert, was dies ermöglicht ihnen schnellere Transaktionsverarbeitungszeiten. Wenn die Knoten, die das Netzwerk betreiben, einschließlich der Knoten in der Beacon-Kette, Wenn die Shards viermal schneller werden, kann jeder Shard viermal mehr verarbeiten Transaktionen und die Beacon-Kette wird in der Lage sein, viermal mehr Shards zu verwalten. Der Durchsatz im gesamten System erhöht sich um den Faktor 4 × 4 = 16 – daher der Name quadratisches Sharding. Es ist schwierig, eine genaue Messung der Anzahl der Scherben zu liefern heute machbar, aber es ist unwahrscheinlich, dass der Durchsatz in absehbarer Zukunft erreicht wird Die Anforderungen der blockchain-Benutzer werden über die Einschränkungen des quadratischen Shardings hinauswachsen. Die schiere Anzahl an Knoten, die erforderlich sind, um eine solche Menge an Shards sicher zu betreiben ist wahrscheinlich um Größenordnungen höher als die Anzahl der Knoten, die insgesamt betrieben werden blockchains heute zusammen. 1.3 State-Sharding Bisher haben wir nicht genau definiert, was genau getrennt ist und was nicht wenn ein Netzwerk in Shards unterteilt ist. Insbesondere Knoten im blockchain erfüllen drei wichtige Aufgaben: Sie verarbeiten nicht nur 1) Transaktionen, sie außerdem 2) validierte Transaktionen und abgeschlossene Blöcke an andere Knoten weiterleiten und 3) Speichern Sie den Status und den Verlauf des gesamten Netzwerk-Ledgers. Jeder dieser drei Aufgaben stellen eine wachsende Anforderung an die Knoten dar, die das Netzwerk betreiben:1. Die Notwendigkeit, Transaktionen zu verarbeiten, erfordert mehr Rechenleistung die erhöhte Anzahl der verarbeiteten Transaktionen; 2. Die Notwendigkeit, Transaktionen und Blöcke weiterzuleiten, erfordert mehr Netzwerkbandbreite mit der zunehmenden Anzahl weitergeleiteter Transaktionen; 3. Die Notwendigkeit, Daten zu speichern, erfordert mit dem Wachstum des Staates mehr Speicherplatz. Wichtig ist, dass im Gegensatz zur Rechenleistung und zum Netzwerk der Speicherbedarf wächst, selbst wenn die Transaktionsrate (Anzahl der verarbeiteten Transaktionen) steigt pro Sekunde) bleibt konstant. Aus der obigen Liste könnte es scheinen, dass der Speicherbedarf hoch wäre am dringendsten, da es das einzige ist, das im Laufe der Zeit erhöht wird Auch wenn sich die Anzahl der Transaktionen pro Sekunde nicht ändert, aber in der Praxis Die dringendste Anforderung ist heute die Rechenleistung. Der gesamte Staat Ethereum ist zum jetzigen Zeitpunkt 100 GB groß und kann von den meisten Knoten problemlos verwaltet werden. Aber die Anzahl der Transaktionen, die Ethereum verarbeiten kann, beträgt etwa 20, Bestellungen von Größenordnung kleiner als das, was für viele praktische Anwendungsfälle benötigt wird. Zilliqa ist das bekannteste Projekt, das die Verarbeitung, nicht aber die Speicherung shardt. Das Sharding der Verarbeitung ist ein einfacheres Problem, da jeder Knoten das Ganze hat Zustand, was bedeutet, dass Verträge sich frei auf andere Verträge berufen und beliebige Daten lesen können aus dem blockchain. Um Aktualisierungen sicherzustellen, ist eine sorgfältige Planung erforderlich Die Aktualisierung derselben Teile des Zustands durch mehrere Shards verursacht keinen Konflikt. In In dieser Hinsicht verfolgt Zilliqa einen relativ einfachen Ansatz2. Obwohl eine Aufteilung des Speichers ohne Aufteilung der Verarbeitung vorgeschlagen wurde, ist dies der Fall äußerst ungewöhnlich. In der Praxis erfolgt also das Sharding des Speichers oder State Sharding. Impliziert fast immer eine Aufteilung der Verarbeitung und eine Aufteilung des Netzwerks. Praktisch gesehen bauen beim State Sharding die Knoten in jedem Shard ihre eigenen auf besitzen blockchain, das Transaktionen enthält, die sich nur auf den lokalen Teil auswirken globalen Status, der diesem Shard zugewiesen ist. Daher sind die validators in der Shard muss nur seinen lokalen Teil des globalen Status speichern und nur ausführen. und als solche nur Weiterleitungstransaktionen, die sich auf ihren Teil des Staates auswirken. Dies Die Partition reduziert linear den Bedarf an Rechenleistung, Speicher usw Netzwerkbandbreite, bringt aber auch neue Probleme mit sich, wie z. B. Datenverfügbarkeit und Cross-Shard-Transaktionen, die wir beide im Folgenden behandeln werden. 1.4 Shardübergreifende Transaktionen Das bisher beschriebene Sharding-Modell ist nicht sehr nützlich, da es individuell ist Shards können nicht miteinander kommunizieren, sie sind nicht besser als mehrere unabhängige blockchains. Auch heute noch, wenn Sharding nicht verfügbar ist, gibt es eine großer Bedarf an Interoperabilität zwischen verschiedenen blockchains. Betrachten wir zunächst nur einfache Zahlungstransaktionen, bei denen jeder Teilnehmer ein Konto auf genau einem Shard hat. Wenn man Geld überweisen möchte 2Unsere Analyse ihres Ansatzes finden Sie hier: https://medium.com/nearprotocol/ 8f9efae0ce3bVon einem Konto zu einem anderen innerhalb desselben Shards kann die Transaktion verarbeitet werden vollständig von den validators in diesem Shard. Wenn jedoch Alice, liegt das auf Shard

1 möchte Geld an Bob senden, der sich auf Shard #2 befindet, und auch nicht an validators

auf Shard Nr. 1 (sie können Bobs Konto nicht gutschreiben) und auch nicht auf den validators Shard Nr. 2 (sie können Alices Konto nicht belasten) kann den gesamten Vorgang verarbeiten Transaktion. Es gibt zwei Familien von Ansätzen für Cross-Shard-Transaktionen: • Synchron: Wann immer eine Cross-Shard-Transaktion ausgeführt werden muss, die Blöcke in mehreren Shards, die Zustandsübergänge im Zusammenhang mit dem enthalten Transaktionen werden alle gleichzeitig erzeugt, und die validators mehrerer Shards arbeiten bei der Ausführung solcher Transaktionen zusammen.3 • Asynchron: eine Shard-übergreifende Transaktion, die mehrere Shards betrifft wird in diesen Shards asynchron ausgeführt, wobei der „Credit“-Shard ausgeführt wird seine Hälfte, sobald hinreichende Beweise dafür vorliegen, dass der „Debit“-Shard seinen Teil ausgeführt hat. Dieser Ansatz ist aufgrund seiner Tendenz häufiger anzutreffen Einfachheit und einfache Koordination. Dieses System wird heute in Cosmos, Ethereum Serenity, Near, Kadena und anderen vorgeschlagen. Ein Problem dabei Der Ansatz besteht darin, dass, wenn Blöcke unabhängig voneinander erstellt werden, eine Wahrscheinlichkeit ungleich Null besteht, dass einer der mehreren Blöcke verwaist wird und somit erstellt wird die Transaktion kam nur teilweise zustande. Betrachten Sie Abbildung 2, die zwei zeigt Shards, die beide auf einen Fork und eine Cross-Shard-Transaktion gestoßen sind das wurde entsprechend in den Blöcken A und X‘ aufgezeichnet. Wenn die Ketten A-B und V’-X’-Y’-Z’ sind in den entsprechenden Shards am Ende kanonisch Die Transaktion ist vollständig abgeschlossen. Wenn A’-B’-C’-D’ und V-X kanonisch werden, dann wird die Transaktion vollständig abgebrochen, was akzeptabel ist. Aber wenn, z Wenn beispielsweise A-B und V-X kanonisch werden, wird ein Teil der Transaktion abgeschlossen und ein anderer Teil abgebrochen, was zu einem Atomizitätsfehler führt. Wir Im zweiten Teil wird erläutert, wie dieses Problem in den vorgeschlagenen Protokollen angegangen wird, wobei Änderungen an den Fork-Choice-Regeln und dem Konsens behandelt werden Für Sharded-Protokolle vorgeschlagene Algorithmen. Beachten Sie, dass die Kommunikation zwischen Ketten außerhalb von Shard-blockchains nützlich ist auch. Die Interoperabilität zwischen Ketten ist ein komplexes Problem, das viele Projekte betrifft versuchen zu lösen. In Sharded-blockchains ist das Problem seitdem etwas einfacher Die Blockstruktur und der Konsens sind in allen Shards gleich und es gibt eine Beacon-Kette, die zur Koordination verwendet werden kann. In einem Shard blockchain jedoch Alle Shard-Ketten sind gleich, während sie im globalen blockchains-Ökosystem vorhanden sind Es gibt viele verschiedene blockchains mit unterschiedlichen Zielanwendungsfällen und Dezentralisierung und Datenschutzgarantien. Aufbau eines Systems, in dem eine Reihe von Ketten unterschiedliche Eigenschaften hat, aber Die Verwendung einer ausreichend ähnlichen Konsens- und Blockstruktur und eine gemeinsame Beacon-Kette könnten ein Ökosystem heterogener blockchains ermöglichen, die über eine verfügen 3Die die meisten detailliert Vorschlag bekannt zu die Autoren von dies Dokument ist Zusammenführen Blöcke, beschrieben hier: https://ethresear.ch/t/ merge-blocks-and-synchronous-cross-shard-state-execution/1240Abbildung 2: Asynchrone Cross-Shard-Transaktionen funktionierendes Interoperabilitätssubsystem. Es ist unwahrscheinlich, dass ein solches System über eine validator-Rotation verfügt, daher müssen einige zusätzliche Maßnahmen ergriffen werden, um die Sicherheit zu gewährleisten. Beides Cosmos und PolkaDot sind faktisch solche Systeme4 1.5 Böswilliges Verhalten In diesem Abschnitt werden wir untersuchen, welches gegnerische Verhalten schädliche validators auslösen kann Übung, wenn es ihnen gelingt, einen Splitter zu beschädigen. Wir werden klassische Ansätze überprüfen zur Vermeidung beschädigter Shards in Abschnitt 2.1. 1.5.1 Schädliche Forks Eine Reihe bösartiger validators könnte versuchen, einen Fork zu erstellen. Beachten Sie, dass dies nicht der Fall ist Es spielt keine Rolle, ob der zugrunde liegende Konsens BFT ist oder nicht, wodurch eine ausreichende Anzahl beschädigt wird von validators wird es immer möglich sein, einen Fork zu erstellen. Es ist deutlich wahrscheinlicher, dass mehr als 50 % eines einzelnen Shards beschädigt sind, als dass mehr als 50 % des gesamten Netzwerks beschädigt sind (wir werden es tun). Gehen Sie in Abschnitt 2.1 näher auf diese Wahrscheinlichkeiten ein. Wie in Abschnitt 1.4 besprochen, Shard-übergreifende Transaktionen beinhalten bestimmte Zustandsänderungen in mehreren Shards und die entsprechenden Blöcke in solchen Shards, die solche Zustandsänderungen anwenden müssen entweder alle abgeschlossen sein (d. h. in den ausgewählten Ketten auf der entsprechenden Seite erscheinen). Shards) oder alle verwaist sein (d. h. nicht in den ausgewählten Ketten auf ihren entsprechenden Shards erscheinen). Da im Allgemeinen die Wahrscheinlichkeit, dass Shards beschädigt werden, höher ist 4Siehe diesen Artikel von Zaki Manian aus Cosmos: https://forum.cosmos.network/ t/polkadot-vs-cosmos/1397/2 und dieser Tweet-Sturm vom Erstautor dieses Dokuments: https://twitter.com/AlexSkidanov/status/1129511266660126720 für einen detaillierten Vergleich der beiden

nicht vernachlässigbar ist, können wir nicht davon ausgehen, dass die Forks nicht stattfinden, selbst wenn ein byzantinischer Konsens unter den Shard-validators erreicht wurde oder viele Blöcke dies taten wird mit der Zustandsänderung oben auf dem Block erzeugt. Für dieses Problem gibt es mehrere Lösungen, die häufigste tritt gelegentlich auf Vernetzung des neuesten Shard-Chain-Blocks mit der Beacon-Kette. Die Gabel Die Auswahlregel in den Shard-Ketten wird dann dahingehend geändert, dass immer die entsprechende Kette bevorzugt wird vernetzt und wenden die Shard-spezifische Fork-Choice-Regel nur für Blöcke an, die vernetzt waren veröffentlicht seit der letzten Querverlinkung. 1.5.2 Ungültige Blöcke genehmigen Eine Gruppe von validators könnte versuchen, einen Block zu erstellen, der die Zustandsübergangsfunktion falsch anwendet. Beginnen wir zum Beispiel mit einem Zustand, in dem Alice Hat 10 tokens und Bob hat 0 tokens, könnte der Block eine Transaktion enthalten, die sendet 10 tokens von Alice an Bob, landet aber in einem Zustand, in dem sich Alice befindet 0 tokens und Bob hat 1000 tokens, wie in Abbildung 3 dargestellt. Abbildung 3: Ein Beispiel für einen ungültigen Block Bei einem klassischen Non-Sharded blockchain ist ein solcher Angriff nicht möglich, da alle Der Teilnehmer im Netzwerk validiert alle Blöcke und den Block damit ein ungültiger Zustandsübergang wird von beiden anderen Blockproduzenten abgelehnt und die Teilnehmer des Netzwerks, die keine Blöcke erstellen. Auch wenn das böswillig ist validators erstellen schneller weiterhin Blöcke auf einem solchen ungültigen Block Ehrliche validators bilden die richtige Kette und haben somit die Kette mit dem Ungültigen Block länger ist, spielt es keine Rolle, da jeder Teilnehmer, der den verwendet blockchain validiert für jeden Zweck alle Blöcke und verwirft alle Blöcke auf dem ungültigen Block aufgebaut. Auf der Abbildung 4 gibt es fünf validators, von denen drei böswillig sind. Sie erstellte einen ungültigen Block A‘ und fuhr dann mit dem Aufbau neuer Blöcke darüber fort davon. Zwei ehrliche validators verwarfen A‘ als ungültig und bauten darauf aufAbbildung 4: Versuchen Sie, einen ungültigen Block in einem nicht fragmentierten blockchain zu erstellen. des letzten ihnen bekannten gültigen Blocks, wodurch ein Fork entsteht. Da es weniger sind validators in der ehrlichen Gabelung, ihre Kette ist kürzer. Im klassischen Non-Sharded blockchain gilt dies jedoch für jeden Teilnehmer, der blockchain für einen beliebigen Zweck verwendet Verantwortlich für die Validierung aller empfangenen Blöcke und die Neuberechnung des Status. Daher würde jede Person, die Interesse an blockchain hat, feststellen, dass A‘ ungültig ist, und daher auch B‘, C‘ und D‘ sofort verwerfen und als solche übernehmen Kette A-B als aktuell längste gültige Kette. In einem Shard blockchain kann jedoch kein Teilnehmer alle Transaktionen auf allen Shards validieren, daher muss er eine Möglichkeit haben, dies zu bestätigen Zu jedem Zeitpunkt im Verlauf eines Shards des blockchain war kein ungültiger Block enthalten. Beachten Sie, dass im Gegensatz zu Forks die Vernetzung mit der Beacon-Kette keine ausreichende Lösung ist, da die Beacon-Kette nicht über die Kapazität zur Validierung verfügt Blöcke. Es kann nur validiert werden, dass sich in diesem Shard eine ausreichende Anzahl von validators befindet den Block unterzeichnet (und damit seine Richtigkeit bestätigt). Wir werden Lösungen für dieses Problem im folgenden Abschnitt 2.2 diskutieren.

Statusgültigkeit und Datenverfügbarkeit

Die Kernidee bei Sharded blockchains ist, dass die meisten Teilnehmer, die bzw Durch die Nutzung des Netzwerks können Blöcke in allen Shards nicht validiert werden. Also wann immer Jeder Teilnehmer muss mit einem bestimmten Shard interagieren, was ihm im Allgemeinen nicht möglich ist Laden Sie den gesamten Verlauf des Shards herunter und validieren Sie ihn. Der Partitionierungsaspekt des Shardings birgt jedoch ein erhebliches Potenzial Problem: ohne den gesamten Verlauf einer bestimmten Datei herunterzuladen und zu validieren Shard Der Teilnehmer kann nicht unbedingt sicher sein, dass der Staat mit dem 5Dieser Abschnitt, mit Ausnahme von Unterabschnitt 2.5.3, wurde zuvor unter https://near.ai/ veröffentlicht. shard2. Wenn Sie es schon einmal gelesen haben, fahren Sie mit dem nächsten Abschnitt fort.

Ihre Interaktion ist das Ergebnis einer gültigen Folge von Blöcken und dieser Folge der Blöcke ist tatsächlich die kanonische Kette im Shard. Ein Problem, das nicht der Fall ist existieren in einem nicht fragmentierten blockchain. Wir werden zunächst eine einfache Lösung für dieses vorgeschlagene Problem vorstellen durch viele Protokolle und analysieren Sie dann, wie diese Lösung kaputt gehen kann und was Es wurden Versuche unternommen, das Problem anzugehen. 2.1 Rotation der Validatoren Die naive Lösung zur Staatsgültigkeit ist in Abbildung 5 dargestellt: Nehmen wir an, wir nehmen an dass das gesamte System in der Größenordnung von Tausenden validators hat, davon nicht mehr als 20 % sind böswillig oder werden auf andere Weise scheitern (z. B. indem sie es nicht tun). online, um einen Block zu erstellen). Wenn wir dann 200 validators abtasten, ist die Wahrscheinlichkeit von mehr als 1 3 Aus praktischen Gründen kann davon ausgegangen werden, dass der Wert null ist. Abbildung 5: Probenahme validators 1 3 ist ein wichtiger Schwellenwert. Es gibt eine Familie von Konsensprotokollen, genannt BFT Konsensprotokolle, die dies für weniger als 1 garantieren 3 von Teilnehmer scheitern, entweder durch einen Absturz oder durch ein Verhalten, das gegen die Regeln verstößt Protokoll wird der Konsens erzielt. Mit dieser Annahme ehrlicher validator Prozent, wenn der aktuelle Satz von Die naive Lösung geht davon aus, dass validators in einem Shard uns einen Block geben dass der Block gültig ist und dass er auf dem aufbaut, was die validators glaubten die kanonische Kette für diesen Shard, als sie mit der Validierung begannen. Die validators lernte die kanonische Kette aus dem vorherigen Satz von validators, die von demselben Annahme, die auf dem Block aufgebaut ist, der der Kopf der kanonischen Kette war davor. Durch Induktion ist die gesamte Kette gültig, und da keine Menge von validators An jedem Punkt, an dem Gabeln hergestellt werden, ist die naive Lösung auch sicher, dass der Strom vorhanden ist Kette ist die einzige Kette im Shard. Eine Visualisierung finden Sie in Abbildung 6.

Abbildung 6: Ein blockchain, bei dem jeder Block über einen BFT-Konsens abgeschlossen wird Diese einfache Lösung funktioniert nicht, wenn wir davon ausgehen, dass die validators möglich sind adaptiv korrumpiert, was keine unvernünftige Annahme ist6. Adaptiv Die Beschädigung eines einzelnen Shards in einem System mit 1000 Shards ist deutlich günstiger als das gesamte System zu beschädigen. Daher nimmt die Sicherheit des Protokolls linear mit der Anzahl der Shards ab. Um Gewissheit über die Gültigkeit zu haben Um einen Block zu erstellen, müssen wir wissen, dass es zu keinem Zeitpunkt in der Geschichte einen Shard im System gibt eine Mehrheit der validators konspiriert; Mit adaptiven Gegnern haben wir das nicht mehr solche Gewissheit. Wie wir in Abschnitt 1.5 besprochen haben, können konspirative validators Ausübung ausüben zwei grundlegende böswillige Verhaltensweisen: Forks erstellen und ungültige Blöcke erzeugen. Schädliche Forks können dadurch bekämpft werden, dass Blöcke mit der Beacon-Kette vernetzt werden, die im Allgemeinen für eine deutlich höhere Sicherheit ausgelegt ist die Scherbenketten. Das Erzeugen ungültiger Blöcke ist jedoch ein wesentlich größerer Aufwand herausforderndes Problem, das es zu bewältigen gilt. 2.2 Staatliche Gültigkeit Betrachten Sie Abbildung 7, in der Shard Nr. 1 beschädigt ist und ein böswilliger Akteur produziert ungültiger Block B. Angenommen, in diesem Block B wurden 1000 tokens aus dem Nichts geprägt Luft auf Alices Konto. Der böswillige Akteur erstellt dann einen gültigen Block C (in a (das Gefühl, dass die Transaktionen in C korrekt angewendet werden) auf B, was verschleiert den ungültigen Block B und initiiert eine Shard-übergreifende Transaktion zu Shard Nr. 2 überweist diese 1000 tokens auf Bobs Konto. Von diesem Moment an ist das falsch Die erstellten tokens befinden sich auf einem ansonsten vollständig gültigen blockchain in Shard Nr. 2. Einige einfache Ansätze zur Lösung dieses Problems sind: 6Lesen dies Artikel für Details auf wie adaptiv Korruption kann sein getragen aus: https://medium.com/nearprotocol/d859adb464c8. Für mehr Details auf adaptiv Korruption, lesen https://github.com/ethereum/wiki/wiki/Sharding-FAQ# Was sind die Sicherheitsmodelle, nach denen wir arbeiten?Abbildung 7: Eine Shard-übergreifende Transaktion aus einer Kette, die einen ungültigen Block hat 1. Für validators von Shard Nr. 2, um den Block zu validieren, von dem aus die Transaktion erfolgt wird eingeleitet. Dies wird auch im obigen Beispiel nicht funktionieren, da Block C scheint völlig gültig zu sein. 2. Damit validators in Shard Nr. 2 eine große Anzahl von Blöcken vor dem Block validieren, von dem aus die Transaktion initiiert wird. Natürlich, z Eine beliebige Anzahl von Blöcken N wird vom empfangenden Shard des Böswilligen validiert validators können N+1 gültige Blöcke zusätzlich zu dem ungültigen Block erstellen, den sie verwenden produziert. Eine vielversprechende Idee zur Lösung dieses Problems wäre die Anordnung von Shards in einer ungerichteter Graph, in dem jeder Shard mit mehreren anderen Shards verbunden ist, und Lassen Sie nur Cross-Shard-Transaktionen zwischen benachbarten Shards zu (z. B. so geht's). Das Sharding von Vlad Zamfir funktioniert im Wesentlichen7, und eine ähnliche Idee wird bei Kadena verwendet Chainweb [1]). Wenn eine Shard-übergreifende Transaktion zwischen Shards erforderlich ist keine Nachbarn, eine solche Transaktion wird über mehrere Shards geleitet. In diesem Design Es wird erwartet, dass ein validator in jedem Shard alle Blöcke in seinem Shard validiert sowie alle Blöcke in allen benachbarten Shards. Betrachten Sie die folgende Abbildung mit 10 Shards, von denen jeder vier Nachbarn hat und keine zwei Shards, die mehr erfordern mehr als zwei Hops für eine Shard-übergreifende Kommunikation, wie in Abbildung 8 dargestellt. Shard Nr. 2 validiert nicht nur seine eigene blockchain, sondern auch blockchains von alle Nachbarn, einschließlich Shard #1. Wenn es sich also um einen böswilligen Akteur auf Shard Nr. 1 handelt versucht, einen ungültigen Block B zu erstellen und dann Block C darauf aufzubauen und eine Cross-Shard-Transaktion initiieren, eine solche Cross-Shard-Transaktion wird nicht durchgeführt durch, da Shard Nr. 2 die gesamte Geschichte von Shard Nr. 1 validiert hat führt dazu, dass der ungültige Block B identifiziert wird. 7Lesen Sie hier mehr über das Design: https://medium.com/nearprotocol/37e538177ed9

Abbildung 8: Eine ungültige Cross-Shard-Transaktion in einem Chainweb-ähnlichen System entdeckt werden Während das Korrumpieren eines einzelnen Shards kein brauchbarer Angriff mehr ist, ist das Korrumpieren eines Shards kein brauchbarer Angriff mehr Wenig Scherben bleiben ein Problem. In Abbildung 9 korrumpiert ein Gegner beide Shards

1 und Shard #2 führen erfolgreich eine Cross-Shard-Transaktion zu Shard #3 aus

mit Mitteln aus einem ungültigen Block B: Abbildung 9: Eine ungültige Cross-Shard-Transaktion in einem Chainweb-ähnlichen System nicht erkannt werden Shard Nr. 3 validiert alle Blöcke in Shard Nr. 2, jedoch nicht in Shard Nr. 1, und hat keine Möglichkeit, den bösartigen Block zu erkennen. Es gibt zwei Hauptrichtungen zur ordnungsgemäßen Lösung der Staatsvalidität: Fischer

und kryptografische Rechennachweise. 2.3 Fischer Die Idee hinter dem ersten Ansatz ist die folgende: Immer wenn ein Blockheader angezeigt wird wird zwischen Ketten zu irgendeinem Zweck kommuniziert (z. B. zur Vernetzung mit dem B. einer Beacon-Kette oder einer Cross-Shard-Transaktion), gibt es einen Zeitraum während womit jeder ehrliche validator einen Beweis dafür liefern kann, dass der Block ungültig ist. Da Es gibt verschiedene Konstruktionen, die sehr prägnante Beweise dafür ermöglichen, dass es sich um Blöcke handelt ungültig, sodass der Kommunikationsaufwand für die empfangenden Knoten viel geringer ist als das Erhalten eines vollständigen Blocks. Mit diesem Ansatz, solange es mindestens einen ehrlichen validator in der Shard, das System ist sicher. Abbildung 10: Fischer Dies ist der vorherrschende Ansatz (neben der Behauptung, dass das Problem nicht existiert) unter den heute vorgeschlagenen Protokollen. Dieser Ansatz hat jedoch zwei Hauptnachteile: 1. Der Herausforderungszeitraum muss für den ehrlichen validator ausreichend lang sein Um zu erkennen, dass ein Block erstellt wurde, laden Sie ihn herunter, überprüfen Sie ihn vollständig und bereiten Sie ihn vor die Challenge, wenn der Block ungültig ist. Die Einführung eines solchen Zeitraums würde verlangsamen die Cross-Shard-Transaktionen erheblich. 2. Die Existenz des Challenge-Protokolls schafft einen neuen Angriffsvektor wenn bösartige Knoten mit ungültigen Herausforderungen spammen. Eine naheliegende Lösung Dieses Problem besteht darin, die Herausforderer dazu zu bringen, einen bestimmten Betrag an tokens einzuzahlen werden zurückgegeben, wenn die Challenge gültig ist. Dies ist nur eine Teillösung, wie es heißt könnte für den Angreifer immer noch von Vorteil sein, das System zu spammen (und zu verbrennen). der Einlagen) mit ungültigen Anfechtungen, beispielsweise zur Verhinderung der gültigenHerausforderung von einem ehrlichen validator vom Durchgehen. Diese Angriffe sind sogenannte Trauerattacken. Eine Möglichkeit, den letztgenannten Punkt zu umgehen, finden Sie in Abschnitt 3.7.2. 2.4 Prägnante, nicht interaktive Wissensargumente Die zweite Lösung für die Beschädigung mehrerer Shards besteht darin, kryptografische Konstruktionen zu verwenden, mit denen man beweisen kann, dass eine bestimmte Berechnung (z. B (z. B. die Berechnung eines Blocks aus einer Reihe von Transaktionen) wurde korrekt durchgeführt. Es gibt solche Konstruktionen, z.B. zk-SNARKs, zk-STARKs und einige andere, und einige werden heute aktiv in blockchain-Protokollen für private Zahlungen verwendet, vor allem ZCash. Das Hauptproblem bei solchen Grundelementen besteht darin, dass sie sind notorisch langsam zu berechnen. Z.B. Coda-Protokoll, das zk-SNARKs verwendet Insbesondere um zu beweisen, dass alle Blöcke in blockchain gültig sind, in einem Aus den Interviews geht hervor, dass die Erstellung eines Beweises 30 Sekunden pro Transaktion dauern kann (Diese Zahl ist wahrscheinlich mittlerweile kleiner). Interessanterweise muss ein Beweis nicht von einer vertrauenswürdigen Partei berechnet werden Der Beweis bescheinigt nicht nur die Gültigkeit der Berechnung, für die er erstellt wurde, sondern auch die Gültigkeit des Beweises selbst. Daher kann die Berechnung solcher Beweise aufgeteilt werden unter einer Gruppe von Teilnehmern mit deutlich geringerer Redundanz, als es der Fall wäre notwendig, um eine vertrauenswürdige Berechnung durchzuführen. Es ermöglicht auch Teilnehmern die zk-SNARKs berechnen, um auf spezieller Hardware zu laufen, ohne die zu reduzieren Dezentralisierung des Systems. Die Herausforderungen von zk-SNARKs sind neben der Leistung: 1. Abhängigkeit von weniger erforschten und weniger bewährten kryptografischen Grundelementen; 2. „Giftiger Abfall“ – zk-SNARKs sind auf ein vertrauenswürdiges Setup angewiesen, in dem eine Gruppe vorhanden ist der Leute führt eine Berechnung durch und verwirft dann das Zwischenprodukt Werte dieser Berechnung. Wenn alle Verfahrensbeteiligten Absprachen treffen und die Zwischenwerte beibehalten, können gefälschte Beweise erstellt werden; 3. Zusätzliche Komplexität im Systemdesign; 4. zk-SNARKs funktionieren nur für eine Teilmenge möglicher Berechnungen, also ein Protokoll mit einer Turing-vollständigen smart contract-Sprache wäre dies nicht möglich SNARKs zum Beweis der Gültigkeit der Kette. 2.5 Datenverfügbarkeit Das zweite Problem, das wir ansprechen werden, ist die Datenverfügbarkeit. Im Allgemeinen Knoten Betrieb eines bestimmten blockchain sind in zwei Gruppen unterteilt: Vollständige Knoten, diejenigen, die jeden vollständigen Block herunterladen und jede Transaktion validieren, und Light Knoten, die nur Blockheader herunterladen und Merkle-Proofs für Teile verwenden des Zustands und der Transaktionen, an denen sie interessiert sind, wie in Abbildung 11 dargestellt.

Abbildung 11: Merkle-Baum Wenn nun die Mehrheit der vollständigen Knoten zusammenarbeitet, können sie einen Block erzeugen, gültig oder ungültig, und senden Sie seine hash an die Lichtknoten, geben Sie jedoch niemals den vollständigen Inhalt preis des Blocks. Es gibt verschiedene Möglichkeiten, wie sie davon profitieren können. Zum Beispiel, Betrachten Sie Abbildung 12: Abbildung 12: Problem mit der Datenverfügbarkeit Es gibt drei Blöcke: Der vorherige, A, wird von ehrlichen validators erzeugt; der Strom, B, hat validators, die konspirieren; und das nächste, C, wird ebenfalls produziert von ehrlichen validators (der blockchain ist in der unteren rechten Ecke abgebildet). Sie sind ein Händler. Die validators des aktuellen Blocks (B) empfangenen Blocks Ein aus den vorherigen validators berechneter Block, in dem Sie Geld erhalten,und habe Ihnen einen Header dieses Blocks mit einem Merkle-Beweis für den Zustand geschickt, in dem er sich befindet Sie haben Geld (oder einen Merkle-Nachweis einer gültigen Transaktion, die das Geld sendet). für dich). Im Vertrauen darauf, dass die Transaktion abgeschlossen ist, erbringen Sie den Service. Allerdings verteilen die validators niemals den gesamten Inhalt des Blocks B an irgendjemand. Daher können die ehrlichen validators von Block C den Block nicht abrufen, und sind entweder gezwungen, das System zum Stillstand zu bringen oder auf A aufzubauen, wodurch Sie als a benachteiligt werden Geldhändler. Wenn wir das gleiche Szenario auf Sharding anwenden, ergeben sich die Definitionen von vollständig und Light-Knoten gelten im Allgemeinen pro Shard: validators in jedem Shard-Download alle Blockieren Sie diesen Shard und validieren Sie jede Transaktion in diesem Shard, außer anderen Knoten im System, einschließlich derjenigen, die Snapshot-Shard-Ketten in den Status aufnehmen Beacon-Kette, laden Sie nur die Header herunter. So lauten die validators im Shard effektiv vollständige Knoten für diesen Shard, während andere Teilnehmer im System, einschließlich der Beacon-Kette, fungieren als Lichtknoten. Damit der oben besprochene Fisherman-Ansatz funktioniert, sind ehrliche validators erforderlich Sie müssen in der Lage sein, Blöcke herunterzuladen, die mit der Beacon-Kette vernetzt sind. Wenn böswillige validators einen Header eines ungültigen Blocks vernetzten (oder ihn dazu nutzten). eine Cross-Shard-Transaktion initiieren), aber niemals den Block verteilen, das ehrlich validators haben keine Möglichkeit, eine Herausforderung zu gestalten. Wir werden drei Ansätze zur Lösung dieses Problems behandeln, die sich ergänzen einander. 2.5.1 Sorgerechtsnachweise Das unmittelbarste zu lösende Problem ist, ob ein Block einmal verfügbar ist es wird veröffentlicht. Eine vorgeschlagene Idee besteht darin, so genannte Notare einzusetzen, die rotieren zwischen Shards häufiger als validators, deren einzige Aufgabe darin besteht, a herunterzuladen blockieren und bestätigen, dass sie es herunterladen konnten. Das können sie sein häufiger rotiert, da nicht der gesamte Bundesstaat heruntergeladen werden muss des Shards, im Gegensatz zu den validators, die seitdem nicht häufig rotiert werden können Sie müssen bei jeder Drehung den Status des Shards herunterladen, wie in der Abbildung dargestellt 13. Das Problem bei diesem naiven Ansatz ist, dass es unmöglich ist, ihn später zu beweisen ob der Notar den Block herunterladen konnte oder nicht, also ein Notar können sich dafür entscheiden, immer zu bestätigen, dass sie den Block auch ohne herunterladen konnten sogar versucht, es wiederzubekommen. Eine Lösung hierfür ist die Bereitstellung durch Notare einige Beweise oder eine gewisse Menge an tokens einzusetzen, die belegen, dass der Block vorhanden war heruntergeladen. Eine solche Lösung wird hier diskutiert: https://ethresear.ch/t/ 1-bit-aggregation-freundliche-custody-bonds/2236. 2.5.2 Löschcodes Wenn ein bestimmter Lichtknoten einen hash eines Blocks empfängt, um den Knoten zu erhöhen Wenn Sie sicher sind, dass der Block verfügbar ist, können Sie versuchen, einige zufällige herunterzuladen Stücke des Blocks. Dies ist keine vollständige Lösung, da es sich nicht um die Lichtknoten handelt Laden Sie gemeinsam den gesamten Block herunter, den die böswilligen Blockproduzenten auswählen können

Abbildung 13: Validatoren müssen den Status herunterladen und können daher nicht rotiert werden häufig um die Teile des Blocks zurückzuhalten, die von keinem Lichtknoten heruntergeladen wurden, Dadurch ist der Block immer noch nicht verfügbar. Eine Lösung besteht darin, eine Konstruktion namens Erasure Codes zu verwenden, um dies zu ermöglichen um den gesamten Block wiederherzustellen, auch wenn nur ein Teil des Blocks verfügbar ist, wie gezeigt auf Abbildung 14. Abbildung 14: Merkle tree basiert auf löschcodierten Daten Sowohl Polkadot als auch Ethereum Serenity haben Designs rund um diese Idee Bieten Sie Lichtknoten die Möglichkeit, einigermaßen sicher zu sein, dass die Blöcke verfügbar sind. Eine ausführliche Beschreibung des Ethereum Serenity-Ansatzes finden Sie in [2].2.5.3 Polkadots Ansatz zur Datenverfügbarkeit In Polkadot erstellt, wie in den meisten Shard-Lösungen, jeder Shard (Parachain genannt) einen Snapshot seiner Blöcke in der Beacon-Kette (Relay-Kette genannt). Angenommen, es gibt 2f + 1 validators in der Relaiskette. Die Blockproduzenten der Parachain-Blöcke, genannt Collatoren berechnen nach der Erstellung des Parachain-Blocks eine löschcodierte Version des Blocks, die aus 2f +1 Teilen besteht, sodass alle f-Teile ausreichen um den Block zu rekonstruieren. Anschließend verteilen sie einen Teil an jeden validator auf der Relaiskette. Eine bestimmte Relay-Kette validator würde sich nur an einer Relay-Kette anmelden Block, wenn sie ihren Teil für jeden Parachain-Block haben, auf den ein Snapshot erstellt wird ein solcher Relaiskettenblock. Wenn also ein Relay-Chain-Block Signaturen von 2f + 1 hat validators und solange jeweils nicht mehr als f von ihnen gegen das Protokoll verstoßen haben Der Parachain-Block kann durch Abrufen der Teile aus den validators rekonstruiert werden die dem Protokoll folgen. Siehe Abbildung 15. Abbildung 15: Datenverfügbarkeit von Polkadot 2.5.4 Langfristige Datenverfügbarkeit Beachten Sie, dass alle oben diskutierten Ansätze nur die Tatsache bestätigen, dass ein Block vorliegt wurde überhaupt veröffentlicht und ist jetzt verfügbar. Blöcke können später nicht mehr verfügbar sein Aus verschiedenen Gründen: Knoten gehen offline, Knoten löschen absichtlich historische Daten Daten und andere. Ein erwähnenswertes Whitepaper, das sich mit diesem Problem befasst, ist Polyshard [3], das Löschcodes verwendet, um Blöcke über Shards hinweg verfügbar zu machen, auch wenn es mehrere sind Shards verlieren ihre Daten vollständig. Leider erfordert ihr spezifischer Ansatz Alle Shards, um Blöcke von allen anderen Shards herunterzuladen, was unerschwinglich ist teuer. Die langfristige Verfügbarkeit ist kein so dringendes Problem: da kein Teilnehmer Es wird erwartet, dass das System in der Lage ist, alle Ketten in allen zu validieren

Shards, die Sicherheit des Shard-Protokolls muss so gestaltet sein So ist das System sicher, auch wenn einige alte Blöcke in einigen Shards beschädigt werden völlig nicht verfügbar.

Nightshade

3.1 Von Splitterketten bis hin zu Splitterbrocken Das Sharding-Modell mit Shard-Ketten und einer Beacon-Kette ist jedoch sehr leistungsfähig hat gewisse Komplexitäten. Insbesondere muss die Fork-Choice-Regel ausgeführt werden in jeder Kette separat, die Fork-Choice-Regel in den Shard-Ketten und das Beacon Die Kette muss unterschiedlich aufgebaut und separat getestet werden. In Nightshade modellieren wir das System als ein einzelnes blockchain, in dem jedes Der Block enthält logisch alle Transaktionen für alle Shards und ändert die Gesamtzustand aller Scherben. Physisch lädt jedoch kein Teilnehmer das herunter Vollständiger Zustand oder vollständiger logischer Block. Stattdessen nur jeder Teilnehmer des Netzwerks behält den Zustand bei, der den Shards entspricht, für die sie Transaktionen validieren, und die Liste aller Transaktionen im Block wird in physische Transaktionen aufgeteilt Chunks, ein Chunk pro Shard. Unter idealen Bedingungen enthält jeder Block genau einen Chunk pro Shard Block, der in etwa dem Modell mit Shard-Ketten entspricht, in dem die Shard-Ketten produzieren Blöcke mit der gleichen Geschwindigkeit wie die Beacon-Kette. Allerdings Aufgrund von Netzwerkverzögerungen könnten einige Chunks fehlen, also in der Praxis jeder Block enthält entweder einen oder keinen Chunk pro Shard. Einzelheiten dazu finden Sie in Abschnitt 3.3 Blöcke entstehen. Abbildung 16: Ein Modell mit Splitterketten auf der linken Seite und mit einer Kette auf der linken Seite Auf der rechten Seite sind die Blöcke in Stücke aufgeteilt

3.2 Konsens Die beiden vorherrschenden Konsensansätze in den blockchains sind heute die längste (oder schwerste) Kette, in der die Kette die meiste Arbeit oder den größten Anteil hat Es gilt als kanonisch, um es zu erstellen, und BFT, in dem für jeden Block einige Satz von validators erreichen einen BFT Konsens. In den kürzlich vorgeschlagenen Protokollen ist letzterer ein dominanterer Ansatz. da es sofortige Endgültigkeit bietet, während in der längsten Kette mehr Blöcke benötigt werden auf dem Block aufgebaut werden, um die Endgültigkeit zu gewährleisten. Oftmals für eine sinnvolle Sicherheit: Die Zeit, die benötigt wird, um eine ausreichende Anzahl von Blöcken zu erstellen, nimmt auf Reihenfolge der Stunden. Die Verwendung des BFT-Konsenses für jeden Block hat auch Nachteile, wie zum Beispiel: 1. BFT Konsens erfordert einen erheblichen Kommunikationsaufwand. Während Die jüngsten Fortschritte ermöglichen es, den Konsens in linearer Zeit in Zahlen zu erreichen der Teilnehmer (siehe z. B. [4]), ist der Overhead pro Block immer noch spürbar; 2. Es ist nicht möglich, dass alle Netzwerkteilnehmer am BFT teilnehmen. Konsens pro Block, daher erreicht normalerweise nur eine zufällig ausgewählte Teilmenge der Teilnehmer den Konsens. Eine zufällig ausgewählte Menge kann im Prinzip sein: adaptiv korrumpiert, und theoretisch kann eine Abzweigung erstellt werden. Das System Beides muss modelliert werden, um für ein solches Ereignis bereit zu sein, und somit still haben neben dem BFT-Konsens eine Fork-Choice-Regel oder sind so konzipiert, dass sie geschlossen werden in einem solchen Fall niedergeschlagen. Es ist erwähnenswert, dass einige Designs, wie z Algorand [5], reduzieren die Wahrscheinlichkeit einer adaptiven Korruption erheblich. 3. Am wichtigsten ist, dass das System blockiert, wenn 1 3 oder mehr aller Teilnehmer sind offline. Daher kann jeder vorübergehende Netzwerkfehler oder eine Netzwerkaufteilung das System vollständig zum Stillstand bringen. Im Idealfall muss das System weiterhin in der Lage sein funktionieren, solange mindestens die Hälfte der Teilnehmer online ist (am schwersten). Kettenbasierte Protokolle funktionieren auch dann weiter, wenn weniger als die Hälfte der Teilnehmer online ist, aber die Zweckmäßigkeit dieser Eigenschaft ist umstrittener innerhalb der Gemeinschaft). Ein Hybridmodell, bei dem der verwendete Konsens am stärksten ist Kette, aber einige Blöcke werden regelmäßig mit einem BFT Finalitäts-Gadget finalisiert, um die Vorteile beider Modelle beizubehalten. Solche BFT Endgültigkeits-Gadgets sind Casper FFG [6] verwendet in Ethereum 2.0 8, Casper CBC (siehe https://vitalik. ca/general/2018/12/05/cbc_casper.html) und GRANDPA (siehe https:// medium.com/polkadot-network/d08a24a021b5) verwendet in Polkadot. Nightshade verwendet den stärksten Kettenkonsens. Insbesondere wenn ein Block Der Produzent erzeugt einen Block (siehe Abschnitt 3.3), von dem er Signaturen sammeln kann andere Blockproduzenten und validators, die den vorherigen Block bestätigen. Siehe Abschnitt 3.8 für Einzelheiten, wie eine so große Anzahl von Signaturen aggregiert wird. Das Gewicht 8Sehen Sie sich auch die Whiteboard-Sitzung mit Justin Drake an, um einen detaillierten Überblick über Casper zu erhalten FFG und wie es in den GHOST-Konsens über die schwerste Kette integriert ist, finden Sie hier: https://www. youtube.com/watch?v=S262StTwkmoeines Blocks ist dann der kumulative Einsatz aller Unterzeichner, deren Unterschriften vorhanden sind im Block enthalten. Das Gewicht einer Kette ist die Summe der Blockgewichte. Zusätzlich zum schwersten Kettenkonsens verwenden wir ein Finalitäts-Gadget, das verwendet die Bescheinigungen zur Fertigstellung der Blöcke. Um die Komplexität des Systems zu reduzieren, Wir verwenden ein Finalitäts-Gadget, das die Fork-Choice-Regel in keiner Weise beeinflusst. und führt stattdessen nur zusätzliche Slashing-Bedingungen ein, so dass einmal ein Block vorhanden ist Durch das Finalitäts-Gadget finalisiert, ist eine Abzweigung unmöglich, es sei denn, es handelt sich um einen sehr großen Prozentsatz des Gesamteinsatzes wird gekürzt. Casper CBC ist so ein Endgültigkeits-Gadget, und wir derzeit Modell mit Blick auf Casper CBC. Wir arbeiten auch an einem separaten BFT-Protokoll namens TxFlow. Zur Zeit von Beim Schreiben dieses Dokuments ist unklar, ob TxFlow anstelle von Casper verwendet wird CBC. Wir stellen jedoch fest, dass die Wahl des Endgültigkeits-Gadgets weitgehend orthogonal zum Rest des Designs ist. 3.3 Blockproduktion In Nightshade gibt es zwei Rollen: Blockproduzenten und validators. Auf jeden Fall Punkt enthält das System w Blockproduzenten, w = 100 in unseren Modellen und wv validators, in unserem Modell v = 100, wv = 10.000. Das System ist Proof-of-Stake, Dies bedeutet, dass sowohl Blockproduzenten als auch validators über eine gewisse Anzahl interner verfügen Währung (bezeichnet als „tokens“) für einen Zeitraum gesperrt, der weit über den hinausgeht Zeit, die sie mit der Erfüllung ihrer Aufgaben zum Aufbau und zur Validierung der Kette verbringen. Wie bei allen Proof-of-Stake-Systemen sind nicht alle W-Blockproduzenten und nicht Alle wv validators sind unterschiedliche Entitäten, da dies nicht erzwungen werden kann. Jeder der w-Blockproduzenten und die wv validators haben jedoch eine separate Pfahl. Das System enthält n Shards, in unserem Modell ist n = 1000. Wie erwähnt in Abschnitt 3.1: In Nightshade gibt es keine Shard-Ketten, stattdessen erstellen alle Blockproduzenten und validators ein einziges blockchain, das wir als das bezeichnen Hauptkette. Der Zustand der Hauptkette ist in n Shards und jeden Block aufgeteilt Produzent und validator haben zu jedem Zeitpunkt nur eine Teilmenge von lokal heruntergeladen der Zustand, der einer Teilmenge der Shards entspricht, und nur verarbeiten und Validierung von Transaktionen, die diese Teile des Staates betreffen. Um ein Blockproduzent zu werden, sperrt ein Teilnehmer des Netzwerks einige große Blöcke Betrag von tokens (ein Einsatz). Die Wartung des Netzwerks erfolgt in Epochen, wobei eine Epoche ein Zeitraum in der Größenordnung von Tagen ist. Die Teilnehmer mit den w größten Einsätzen zu Beginn einer bestimmten Epoche sind der Block Produzenten für diese Epoche. Jedem Blockproduzenten sind SW-Shards zugewiesen (z. B sw = 40, was sww/n = 4 Blockproduzenten pro Shard ergeben würde. Der Block Der Produzent lädt den Status des Shards herunter, dem er vor der Epoche zugewiesen ist beginnt und sammelt im Laufe der Epoche Transaktionen, die sich auf diesen Shard auswirken. und wendet sie auf den Staat an. Für jeden Block b in der Hauptkette und für jeden Shard s gibt es einen davon s Blockproduzenten zugewiesen, die für die Produktion des Teils von b verantwortlich sind zur Scherbe. Der Teil von b, der sich auf Shard s bezieht, wird als Chunk bezeichnet und enthält die Liste der Transaktionen für den Shard, die in b aufgenommen werden sollen, sowie das MerkleWurzel des resultierenden Zustands. b wird letztendlich nur einen sehr kleinen Header von enthalten der Chunk, nämlich die Merkle-Wurzel aller angewendeten Transaktionen (siehe Abschnitt 3.7.1 für genaue Details) und die Merkle-Wurzel des Endzustands. Im weiteren Verlauf des Dokuments beziehen wir uns häufig auf den Blockproduzenten Das ist dafür verantwortlich, zu einem bestimmten Zeitpunkt einen Chunk für einen bestimmten Shard zu produzieren als Chunk-Produzent. Der Chunk-Produzent ist immer einer der Blockproduzenten. Die Blockproduzenten und die Chunk-Produzenten rotieren jeden Block entsprechend nach einem festen Zeitplan. Die Blockproduzenten haben einen Auftrag und produzieren wiederholt Blöcke in dieser Reihenfolge. Z.B. wenn es 100 Blockproduzenten gibt, der erste Block Der Hersteller ist für die Produktion der Blöcke 1, 101, 201 usw. verantwortlich, der zweite verantwortlich für die Produktion von 2, 102, 202 usw.). Da die Chunk-Produktion im Gegensatz zur Blockproduktion eine Wartung erfordert den Status, und für jeden Shard behalten nur sww/n-Blockproduzenten den Status bei Pro Shard rotieren dementsprechend nur die SWW/N-Blockproduzenten, um sie zu erstellen Brocken. Z.B. mit den oben genannten Konstanten mit vier zugewiesenen Blockproduzenten Jeder Shard und jeder Blockproduzent erstellt alle vier Blöcke einmal Chunks. 3.4 Sicherstellung der Datenverfügbarkeit Um die Datenverfügbarkeit sicherzustellen, verwenden wir einen ähnlichen Ansatz wie Polkadot beschrieben in Abschnitt 2.5.3. Sobald ein Blockproduzent einen Block produziert, erstellt er ihn eine löschcodierte Version davon mit einem optimalen (w, ⌊w/6 + 1⌋) Blockcode des Brocken. Anschließend senden sie einen Teil des löschcodierten Blocks (wir nennen solche Teile). Chunk-Teile oder nur Teile) an jeden Blockproduzenten. Wir berechnen einen Merkle-Baum, der alle Teile wie die Blätter und die enthält Der Header jedes Blocks enthält die Merkle-Wurzel dieses Baums. Die Teile werden über Onepart-Nachrichten an die validators gesendet. Jede solche Nachricht enthält den Chunk-Header, die Ordnungszahl des Teils und den Teilinhalt. Die Die Nachricht enthält auch die Signatur des Blockproduzenten, der sie erstellt hat Chunk und den Merkle-Pfad, um zu beweisen, dass der Teil dem Header entspricht und wird vom richtigen Blockproduzenten produziert. Sobald ein Blockproduzent einen Hauptkettenblock erhält, prüft er zunächst, ob dies der Fall ist Für jeden im Block enthaltenen Block gibt es einteilige Nachrichten. Wenn nicht, die Sperre wird erst verarbeitet, wenn die fehlenden Onepart-Nachrichten abgerufen wurden. Sobald alle einteiligen Nachrichten empfangen wurden, ruft der Blockproduzent die ab Die restlichen Teile werden von den Peers abgezogen und die Chunks rekonstruiert, die sie enthalten der Staat. Der Blockproduzent verarbeitet keinen Hauptkettenblock, wenn es sich um mindestens einen handelt Wenn ein im Block enthaltener Chunk nicht über die entsprechende Onepart-Nachricht verfügt, oder wenn für mindestens einen Shard, für den sie den Status aufrechterhalten, dies nicht der Fall ist den gesamten Block rekonstruieren. Damit ein bestimmter Block verfügbar ist, reicht es aus, dass ⌊w/6⌋+1 des Blocks Produzenten haben ihre Teile und bedienen sie. Also solange die Zahl der böswillige Akteure überschreiten nicht ⌊w/3⌋keine Kette, die mehr als einen halben Block hat Hersteller, die es bauen, können nicht verfügbare Teile haben.Abbildung 17: Jeder Block enthält einen oder keinen Chunk pro Shard und jeden Chunk ist löschcodiert. Jeder Teil des löschcodierten Blocks wird an eine bestimmte Adresse gesendet Blockproduzent über eine spezielle Onepart-Nachricht 3.4.1 Umgang mit faulen Blockproduzenten Wenn ein Blockproduzent einen Block hat, für den eine Onepart-Nachricht fehlt, wird er Vielleicht entscheiden Sie sich trotzdem dafür, ihn zu signieren, denn wenn der Block am Ende in der Kette landet, ist er es maximiert die Belohnung für den Blockproduzenten. Für den Block besteht kein Risiko Der Blockproduzent war nicht der einzige Blockproduzent, da es später unmöglich ist, zu beweisen, dass der Blockproduzent ihn nicht hatte die einteilige Nachricht. Um dies zu beheben, machen wir jeden Chunk zum Produzenten, wenn wir den Chunk erstellen Wählen Sie eine Farbe (Rot oder Blau) für jeden Teil des zukünftigen codierten Blocks und speichern Sie ihn die Bitmaske der zugewiesenen Farbe im Block, bevor er codiert wird. Jeweils ein Teil Die Nachricht enthält dann die dem Teil zugewiesene Farbe, und die Farbe wird verwendet, wenn Berechnen der Merkle-Wurzel der codierten Teile. Wenn der Chunk-Produzent abweicht Aus dem Protokoll lässt sich dies leicht beweisen, da dies bei der Merkle-Wurzel nicht der Fall ist entsprechen einteiligen Nachrichten oder den Farben in den einteiligen Nachrichten die der Merkle-Wurzel entsprechen, stimmt nicht mit der Maske im Block überein. Wenn ein Blockproduzent einen Block anmeldet, fügt er eine Bitmaske aller Blöcke hinzu rote Teile erhielten sie für die im Block enthaltenen Chunks. Veröffentlichung einer Eine falsche Bitmaske ist ein streichbares Verhalten. Wenn ein Blockproduzent keine erhalten hat Bei einer einzelnen Nachricht haben sie keine Möglichkeit, die Farbe der Nachricht zu kennen, und Daher besteht eine Wahrscheinlichkeit von 50 %, dass sie gekürzt werden, wenn sie versuchen, das Dokument blind zu unterschreiben blockieren. 3.5 Antrag auf Staatsübergang Die Chunk-Produzenten wählen lediglich aus, welche Transaktionen in den Chunk aufgenommen werden sollen Wenden Sie den Zustandsübergang nicht an, wenn sie einen Block erzeugen. Dementsprechend

Der Chunk-Header enthält die Merkle-Wurzel des merkelisierten Zustands wie zuvor Die Transaktionen im Block werden angewendet. Die Transaktionen werden nur angewendet, wenn ein vollständiger Block den Block enthält verarbeitet wird. Ein Teilnehmer bearbeitet einen Block nur, wenn 1. Der vorherige Block wurde empfangen und verarbeitet; 2. Für jeden Block behält der Teilnehmer nicht den Status bei, den er hat habe die einteilige Nachricht gesehen; 3. Für jeden Block behält der Teilnehmer den Status bei, den er hat volles Stück. Sobald der Block verarbeitet wird, für jeden Shard, für den der Teilnehmer zuständig ist behält den Zustand bei, wendet die Transaktionen an und berechnet den neuen Zustand ab dem Zeitpunkt, an dem die Transaktionen angewendet wurden, und sind danach zur Produktion bereit die Chunks für den nächsten Block, wenn sie einem Shard zugewiesen sind, da sie dies getan haben die Merkle-Wurzel des neuen merkelisierten Staates. 3.6 Shardübergreifende Transaktionen und Belege Wenn eine Transaktion mehr als einen Shard betreffen muss, muss sie nacheinander erfolgen wird in jedem Shard separat ausgeführt. Die vollständige Transaktion wird an den ersten Shard gesendet betroffen, und sobald die Transaktion im Chunk für diesen Shard enthalten ist, und Wird angewendet, nachdem der Block in einen Block eingefügt wurde, wird eine sogenannte Quittung generiert Transaktion, die an den nächsten Shard weitergeleitet wird, in dem die Transaktion ausgeführt werden muss ausgeführt werden. Wenn weitere Schritte erforderlich sind, erfolgt die Ausführung der Empfangstransaktion generiert eine neue Belegtransaktion und so weiter. 3.6.1 Lebensdauer der Quittungstransaktion Es ist wünschenswert, dass die Empfangstransaktion in dem Block angewendet wird, der unmittelbar auf den Block folgt, in dem sie generiert wurde. Die Quittungstransaktion ist nur generiert, nachdem der vorherige Block empfangen und von Blockproduzenten angewendet wurde die den ursprünglichen Shard verwalten und zum Zeitpunkt des bekannt sein müssen Der Block für den nächsten Block wird von den Blockproduzenten des Ziels erstellt Scherbe. Daher muss der Empfang vom Quell-Shard an den übermittelt werden Ziel-Shard in dem kurzen Zeitrahmen zwischen diesen beiden Ereignissen. Sei A der zuletzt produzierte Block, der eine Transaktion t enthält, die eine Quittung r generiert. Sei B der nächste produzierte Block (d. h. ein Block, der A als hat). sein vorheriger Block), den wir r enthalten wollen. Lass es in der Scherbe a und r sein in der Scherbe b. Die Lebensdauer des Belegs, ebenfalls in Abbildung 18 dargestellt, ist wie folgt: Erstellen und Aufbewahren der Belege. Der Chunk-Produzenten-CPA für Shard a empfängt den Block A, wendet die Transaktion t an und generiert die Quittung r. cpa Anschließend speichert es alle derart erstellten Belege in seinem indizierten internen persistenten Speicher nach der Quell-Shard-ID.Verteilen der Quittungen. Sobald CPA bereit ist, den Chunk zu produzieren Wenn Sie Shard a für Block B verwenden, rufen sie alle Belege ab, die durch die Anwendung der Transaktionen von Block A für Shard a generiert wurden, und fügen sie in den Block für Shrad ein a in Block B. Sobald ein solcher Block generiert ist, erzeugt cpa seinen Löschcode Version und alle zugehörigen Onepart-Nachrichten. cpa weiß, welche Blockproduzenten den vollständigen Status für welche Shards beibehalten. Für einen bestimmten Blockproduzenten bp cpa umfasst die Einnahmen, die aus der Anwendung von Transaktionen in Block A resultierten für Shard a, der einen der Shards hat, die bp als Ziel interessieren in der einteiligen Nachricht, als sie den Block für Shard a in Block B verteilten (siehe Abbildung 17, die die in der Onepart-Nachricht enthaltenen Quittungen zeigt). Erhalt der Quittungen. Denken Sie daran, dass die Teilnehmer (sowohl Blockproduzenten als auch validators) Blöcke erst verarbeiten, wenn sie einteilige Nachrichten haben für jeden im Block enthaltenen Block. Wenn also ein bestimmter Teilnehmer den Block B anwendet, verfügt er über alle entsprechenden Onepart-Nachrichten Chunks in B, und somit verfügen sie über alle eingehenden Belege, die die Shards enthalten Der Teilnehmer behält den Status als Ziel bei. Bei der Anwendung der Beim Zustandsübergang für einen bestimmten Shard wendet der Teilnehmer beide Quittungen an dass sie für den Shard in den Onepart-Nachrichten sowie allen gesammelt haben die im Chunk selbst enthaltenen Transaktionen. Abbildung 18: Die Lebensdauer einer Empfangstransaktion 3.6.2 Umgang mit zu vielen Belegen Es ist möglich, dass die Anzahl der Belege, die auf einen bestimmten Shard in einem abzielen Ein bestimmter Block ist zu groß, um verarbeitet zu werden. Betrachten Sie zum Beispiel Abbildung 19, in wobei jede Transaktion in jedem Shard eine Quittung generiert, die auf Shard 1 abzielt. Bis zum nächsten Block beträgt die Anzahl der Belege, die Shard 1 verarbeiten muss vergleichbar mit der Last, die alle Scherben zusammen während der Handhabung verarbeitet haben den vorherigen Block.

Abbildung 19: Wenn alle Belege auf denselben Shard abzielen, ist dies möglicherweise nicht der Fall die Fähigkeit, sie zu verarbeiten Um dieses Problem anzugehen, verwenden wir eine Technik, die der in QuarkChain 9 verwendeten ähnelt. Konkret gilt für jeden Shard der letzte Block B und der letzte Shard darin Es wird der Block erfasst, aus dem die Belege übernommen wurden. Wenn der neue Shard ist erstellt, die Quittung wird in der Reihenfolge zuerst aus den verbleibenden Shards in B angewendet, und dann in Blöcken, die auf B folgen, bis der neue Block voll ist. Unter normal Bei ausgeglichener Belastung kommt es in der Regel zu allen Einnahmen angewendet wird (und somit wird der letzte Shard des letzten Blocks aufgezeichnet jedes Stück), aber zu Zeiten, in denen die Last nicht ausgeglichen ist, und ein bestimmtes Da Shard überproportional viele Belege erhält, ist dies mit dieser Technik möglich unter Einhaltung der Beschränkungen für die Anzahl der enthaltenen Transaktionen verarbeitet werden. Beachten Sie, dass die Verzögerung abnimmt, wenn eine solche unausgeglichene Belastung über einen längeren Zeitraum anhält Die Belegerstellung bis zur Anwendung kann unbegrenzt weiter wachsen. Eins Eine Möglichkeit, das Problem zu lösen, besteht darin, jede Transaktion zu verwerfen, die eine Quittung für a erstellt Shard, dessen Verarbeitungsverzögerung eine bestimmte Konstante überschreitet (z. B. eine Epoche). Betrachten Sie Abbildung 20. Durch Block B kann der Shard 4 nicht alle Belege verarbeiten. es verarbeitet also nur Quittungsursprünge von bis zu Shard 3 in Block A und zeichnet es auf. In Block C sind die Belege bis Shard 5 in Block B enthalten, und Dann holt der Shard bei Block D auf und verarbeitet alle verbleibenden Belege Block B und alle Belege aus Block C. 3.7 Chunks-Validierung Ein für einen bestimmten Shard erstellter Chunk (oder ein für eine bestimmte Shard-Kette im Modell mit Shard-Ketten erstellter Shard-Block) kann nur von validiert werden 9Sehen Sie sich hier die Whiteboard-Folge mit QuarkChain an: https://www.youtube.com/watch? v=opEtG6NM4x4, in dem unter anderem der Ansatz für Cross-Shard-Transaktionen diskutiert wird DingeAbbildung 20: Verzögerte Belegverarbeitung Teilnehmer, die den Staat aufrechterhalten. Sie können Blockproduzenten sein, validators, oder nur externe Zeugen, die den Status heruntergeladen und den Shard darin validiert haben in dem sie Vermögenswerte speichern. In diesem Dokument gehen wir davon aus, dass die Mehrheit der Teilnehmer nicht speichern kann der Staat für einen großen Teil der Scherben. Es ist jedoch erwähnenswert, dass es Shard-blockchains gibt, die unter der Annahme entworfen wurden, dass Die meisten Teilnehmer verfügen über die Kapazität, den Zustand zu speichern und die meisten davon zu validieren die Shards, wie zum Beispiel QuarkChain. Da nur ein Bruchteil der Teilnehmer den Status hat, den Shard zu validieren Chunks ist es möglich, adaptiv nur die Teilnehmer zu korrumpieren, die das haben Zustand ändern und einen ungültigen Zustandsübergang anwenden. Es wurden mehrere Sharding-Designs vorgeschlagen, die alle paar validators abtasten Tage und innerhalb eines Tages jeder Block in der Shard-Kette, der mehr als 2/3 hat der diesem Shard zugewiesenen Signaturen der validators werden sofort berücksichtigt endgültig. Mit einem solchen Ansatz muss ein adaptiver Gegner nur 2n/3+1 korrumpieren der validators in einer Shard-Kette, um einen ungültigen Zustandsübergang anzuwenden, der, Auch wenn es wahrscheinlich schwer zu bewerkstelligen ist, ist das Sicherheitsniveau für die Öffentlichkeit nicht ausreichend blockchain. Wie in Abschnitt 2.3 besprochen, besteht der übliche Ansatz darin, nach der Erstellung eines Blocks für jeden Teilnehmer, der über den Status (ob) verfügt, ein bestimmtes Zeitfenster einzuräumen es ist ein Blockproduzent, ein validator oder ein externer Beobachter), um seine Gültigkeit in Frage zu stellen. Solche Teilnehmer werden Fischer genannt. Damit ein Fischer es kann Um einen ungültigen Block anzufechten, muss sichergestellt werden, dass ein solcher Block verfügbar ist sie. Die Datenverfügbarkeit in Nightshade wird in Abschnitt 3.4 erläutert. Sobald in Nightshade ein Block erstellt wurde, wurden die Chunks nicht validiert irgendjemand außer dem eigentlichen Chunk-Produzenten. Insbesondere der Blockproduzent schlug vor, dass der Block natürlich nicht den Status für die meisten Shards hatte, undkonnte die Chunks nicht validieren. Wenn der nächste Block produziert wird, enthält er Attestierungen (siehe Abschnitt 3.2) mehrerer Blockproduzenten und validators, aber da die Mehrheit der Blockproduzenten und validators den Status nicht aufrechterhalten Auch bei den meisten Shards sammelt ein Block mit nur einem ungültigen Chunk deutlich mehr als die Hälfte der Attestierungen und bleibt weiterhin am schwersten Kette. Um dieses Problem zu beheben, gestatten wir jedem Teilnehmer, den Status von beizubehalten Ein Shard, um in der Kette eine Herausforderung für jeden darin erzeugten ungültigen Chunk einzureichen Scherbe. 3.7.1 Staatliche Gültigkeitsherausforderung Sobald ein Teilnehmer feststellt, dass ein bestimmter Block ungültig ist, muss er einen Beweis dafür erbringen, dass der Block ungültig ist. Da die Mehrheit der Netzwerkteilnehmer den Zustand für den Shard, in dem sich der ungültige Chunk befindet, nicht aufrechterhalten Wenn der Beweis erstellt wird, muss er über ausreichende Informationen verfügen, um den Block zu bestätigen ungültig, ohne den Staat zu haben. Wir legen einen Grenzwert Ls für die Statusmenge (in Bytes) fest, die eine einzelne Transaktion umfasst kann kumulativ lesen oder schreiben. Jede Transaktion, die mehr als Ls berührt Zustand gilt als ungültig. Erinnern Sie sich aus Abschnitt 3.5 daran, dass der Chunk In einem bestimmten Block enthält B nur die anzuwendenden Transaktionen, jedoch nicht die neue Staatswurzel. Der im Block in Block B enthaltene Statusstamm ist der Status root, bevor Sie solche Transaktionen anwenden, aber nachdem Sie die Transaktionen angewendet haben der letzte Block im selben Shard vor dem Block B. Ein böswilliger Akteur Der Wunsch, einen ungültigen Zustandsübergang anzuwenden, würde einen falschen Zustandsstamm beinhalten in Block B entspricht das nicht der Zustandswurzel, die sich aus der Anwendung ergibt die Transaktionen im vorherigen Block. Wir erweitern die Informationen, die ein Chunk-Produzent in den Chunk einfügt. Anstatt nur den Status einzubeziehen, nachdem alle Transaktionen angewendet wurden, wird dieser stattdessen angezeigt Enthält eine Statuswurzel, nachdem jeder zusammenhängende Satz von Transaktionen angewendet wurde Lesen und schreiben Sie gemeinsam Ls Zustandsbytes. Mit diesen Informationen für die Fischer stellt eine Herausforderung dar, dass ein Zustandsübergang falsch angewendet wird reicht aus, um den ersten solchen ungültigen Zustandsstamm zu finden, und umfasst nur Ls Bytes davon Staaten, die von den Transaktionen zwischen dem letzten Stammstaat (der war) betroffen sind gültig) und die aktuelle Statuswurzel mit den Merkle-Beweisen. Dann jeder Teilnehmer kann die Transaktionen im Segment validieren und bestätigen, dass der Block vorhanden ist ungültig. Das Gleiche gilt, wenn der Blockproduzent versucht hat, lesende Transaktionen einzuschließen und mehr als Ls Statusbytes schreiben, für die Herausforderung reicht es aus, sie einzuschließen Die ersten Ls-Bytes berührt es mit den Merkle-Beweisen, was ausreichen wird Wenden Sie die Transaktionen an und bestätigen Sie, dass es einen Moment gibt, in dem ein Versuch dazu erfolgt Das Lesen oder Schreiben von Inhalten über Ls Bytes hinaus erfolgt.

3.7.2 Fischer und schnelle Cross-Shard-Transaktionen Wie in Abschnitt 2.3 besprochen, nehmen wir einmal an, dass die Shard-Chunks (oder Shard Blöcke im Modell mit Shard-Ketten) können ungültig sein und eine Herausforderung darstellen Dies wirkt sich negativ auf die Endgültigkeit und damit auf die Shard-übergreifende Kommunikation aus. In Insbesondere kann der Ziel-Shard einer Cross-Shard-Transaktion nicht sicher sein Der ursprüngliche Shard-Block oder -Block ist endgültig, bis der Herausforderungszeitraum abgelaufen ist (siehe Abbildung 21). Abbildung 21: Warten Sie den Herausforderungszeitraum ab, bevor Sie eine Quittung beantragen Die Art und Weise, es so anzugehen, dass die Cross-Shard-Transaktionen möglich sind Instantenious bedeutet, dass der Ziel-Shard nicht auf den Herausforderungszeitraum warten muss Nachdem die Quell-Shard-Transaktion veröffentlicht wurde, wenden Sie die Empfangstransaktion an sofort ausführen, aber dann den Ziel-Shard zusammen mit der Quelle zurücksetzen Shard, wenn sich später herausstellt, dass der ursprüngliche Chunk oder Block ungültig ist (siehe Abbildung). 22). Dies gilt ganz natürlich für das Nightshade-Design, in dem die Scherbe enthalten ist Ketten sind nicht unabhängig, stattdessen werden alle Shard-Blöcke veröffentlicht zusammen im selben Hauptkettenblock. Wenn sich herausstellt, dass ein Block ungültig ist, wird der Der gesamte Block mit diesem Block wird als ungültig betrachtet, ebenso alle darauf aufbauenden Blöcke oben drauf. Siehe Abbildung 23. Beide oben genannten Ansätze bieten Atomizität unter der Annahme, dass die Herausforderung besteht Der Zeitraum ist ausreichend lang. Wir verwenden den letzteren Ansatz, da die Bereitstellung schneller Cross-Shard-Transaktionen unter normalen Umständen die Unannehmlichkeiten überwiegt Der Ziel-Shard wird aufgrund eines ungültigen Zustandsübergangs in einem von ihnen zurückgesetzt die Quellsplitter, was ein äußerst seltenes Ereignis ist. 3.7.3 validators werden ausgeblendet Das Vorhandensein der Herausforderungen verringert bereits die Wahrscheinlichkeit erheblich Adaptive Korruption, da ein Block mit einem ungültigen Zustandsübergangsposten abgeschlossen werden mussAbbildung 22: Belege sofort anwenden und das Ziel zurücksetzen Kette, wenn die Quellkette einen ungültigen Block hatte Abbildung 23: Fischer-Herausforderung in Nightshade Der Herausforderungszeitraum, den der adaptive Gegner benötigt, um alle Teilnehmer zu korrumpieren die den Zustand des Shards beibehalten, einschließlich aller validators. Die Wahrscheinlichkeit eines solchen Ereignisses abzuschätzen ist äußerst komplex, da nein sharded blockchain ist schon so lange aktiv, dass ein solcher Angriff versucht werden kann. Wir argumentieren, dass die Wahrscheinlichkeit zwar äußerst gering, aber immer noch ausreichend ist groß für ein System, von dem erwartet wird, dass es mehrere Millionen Transaktionen ausführt Führen Sie ein weltweites Finanzgeschäft. Es gibt zwei Hauptgründe für diesen Glauben: 1. Die meisten validators der Proof-of-Stake-Ketten und Miner der

Der Anreiz für Proof-of-Work-Ketten besteht in erster Linie aus finanziellen Vorteilen. Wenn Ein adaptiver Gegner bietet ihnen mehr Geld als die erwartete Rendite Wenn man ehrlich vorgeht, kann man davon ausgehen, dass es viele validators gibt werde das Angebot annehmen. 2. Viele Unternehmen führen die Validierung von Proof-of-Stake-Ketten professionell durch Es wird erwartet, dass ein großer Prozentsatz der Anteile an jeder Kette liegen wird von solchen Einheiten. Die Anzahl solcher Entitäten ist für eine ausreichend klein adaptiver Gegner, um die meisten von ihnen persönlich kennenzulernen und zu haben gutes Verständnis für ihre Neigung, korrumpiert zu werden. Wir gehen einen Schritt weiter, um die Wahrscheinlichkeit der adaptiven Korruption zu verringern, indem wir verbergen, welche validators welchem ​​Shard zugewiesen sind. Die Idee ist entfernt ähnlich der Art und Weise, wie Algorand [5] validators verbirgt. Es ist wichtig zu beachten, dass selbst wenn die validators verborgen sind, wie in Algorand oder wie unten beschrieben, ist die adaptive Korruption theoretisch immer noch möglich. Während Der adaptive Gegner kennt die Teilnehmer nicht, die erstellen oder validieren Ob ein Block oder ein Brocken, die Teilnehmer wissen selbst, dass sie etwas leisten werden eine solche Aufgabe erfüllen und einen kryptografischen Beweis dafür haben. So kann der Gegner Machen Sie ihre Korruptionsabsicht öffentlich und zahlen Sie an jeden Teilnehmer, der dies bereitstellt so ein kryptografischer Beweis. Wir stellen jedoch fest, dass der Gegner dies nicht tut Sie kennen die validators, die dem Shard zugewiesen sind, den sie beschädigen möchten haben keine andere Wahl, als ihre Absicht, einen bestimmten Shard zu beschädigen, zu verbreiten die gesamte Gemeinschaft. An diesem Punkt ist es für jeden Ehrlichen wirtschaftlich vorteilhaft Der Teilnehmer muss einen vollständigen Knoten hochfahren, der diesen Shard validiert, da ein Hoch vorliegt Wahrscheinlichkeit, dass ein ungültiger Block in diesem Shard erscheint, was eine Gelegenheit dazu darstellt Erstellen Sie eine Herausforderung und sammeln Sie die zugehörige Belohnung. Um die validators, die einem bestimmten Shard zugewiesen sind, nicht preiszugeben, tun wir dies Folgendes (siehe Abbildung 24): Verwenden Sie VRF, um die Zuweisung zu erhalten. Zu Beginn jeder Epoche validator verwendet eine VRF, um eine Bitmaske der Shards abzurufen, denen validator zugewiesen ist. Die Bitmaske jedes validator wird Sw-Bits haben (Definition siehe Abschnitt 3.3). von Sw). Der validator ruft dann den Status der entsprechenden Shards ab und Während der Epoche werden für jeden empfangenen Block die entsprechenden Blöcke validiert zu den Shards, denen validator zugewiesen ist. Melden Sie sich in Blöcken statt in Blöcken an. Da die Shard-Zuweisung verborgen ist, kann validator keine Chunks anmelden. Stattdessen wird immer das Ganze unterschrieben blockieren, sodass nicht verraten wird, welche Shards validiert werden. Insbesondere wenn validator einen Block empfängt und alle Blöcke validiert, erstellt er entweder eine Nachricht Dies bestätigt, dass alle Chunks in allen Shards, denen validator zugewiesen ist, vorhanden sind gültig (ohne in irgendeiner Weise anzugeben, um welche Shards es sich handelt) oder eine Nachricht darüber enthält einen Beweis für einen ungültigen Zustandsübergang, wenn ein Block ungültig ist. Siehe die Einzelheiten zur Aggregation solcher Nachrichten finden Sie in Abschnitt 3.8, in Abschnitt 3.7.4 die Details, wie verhindert werden kann, dass validators Nachrichten von huckepack nehmen andere validators und Abschnitt 3.7.5 für Einzelheiten zur Belohnung und Bestrafung validators, falls tatsächlich eine erfolgreiche ungültige Zustandsübergangsherausforderung stattfindet.Abbildung 24: Die validators in Nightshade verbergen 3.7.4 Commit-Reveal Eines der häufigsten Probleme mit validators besteht darin, dass ein validator das Herunterladen des Status und die tatsächliche Validierung der Chunks und Blöcke überspringen kann und stattdessen Beobachten Sie das Netzwerk, sehen Sie, was die anderen validators einreichen, und wiederholen Sie dies Nachrichten. Ein validator, der einer solchen Strategie folgt, bietet keinen Mehrwert Sicherheit für das Netzwerk, kassiert aber Belohnungen. Eine übliche Lösung für dieses Problem besteht darin, für jeden validator einen Beweis bereitzustellen dass sie den Block tatsächlich validiert haben, beispielsweise durch Bereitstellung einer eindeutigen Ablaufverfolgung Die Anwendung des Zustandsübergangs ist zwar nicht möglich, aber solche Nachweise erhöhen die Kosten erheblich der Validierung. Abbildung 25: Commit-Enthüllung

Stattdessen veranlassen wir, dass die validators zuerst auf das Validierungsergebnis übertragen werden (entweder die Nachricht, die die Gültigkeit der Chunks bestätigt, oder der Beweis einer Ungültigkeit Warten Sie einen bestimmten Zeitraum und zeigen Sie erst dann das tatsächliche Validierungsergebnis an, wie in Abbildung 25 dargestellt. Der Festschreibungszeitraum überschneidet sich nicht mit der Enthüllungszeitraum, und daher kann ein fauler validator keine ehrlichen validators kopieren. Darüber hinaus, wenn ein unehrlicher validator sich zu einer Nachricht verpflichtet hat, die dies bestätigt Gültigkeit der zugewiesenen Chunks, und mindestens ein Chunk war ungültig, sobald dies der Fall ist gezeigt, dass der Block ungültig ist, kann validator den Schrägstrich nicht vermeiden, da Wie wir in Abschnitt 3.7.5 zeigen, ist dies der einzige Weg, in einer solchen Situation nicht aufgeschlitzt zu werden besteht darin, eine Nachricht zu präsentieren, die einen Beweis für den ungültigen Zustandsübergang enthält entspricht dem Commit. 3.7.5 Umgang mit Herausforderungen Wie oben erläutert, sobald ein validator einen Block mit einem ungültigen Block empfängt, Sie bereiten zunächst einen Beweis für den ungültigen Zustandsübergang vor (siehe Abschnitt 3.7.1) und dann verpflichten Sie sich zu einem solchen Beweis (siehe 3.7.4) und offenbaren Sie nach einiger Zeit die Herausforderung. Sobald die aufgedeckte Herausforderung in einen Block aufgenommen wird, passiert Folgendes: 1. Alle Zustandsübergänge, die von dem Block aus stattgefunden haben, der die enthält ungültiger Block, bis der Block, in dem die aufgedeckte Herausforderung enthalten ist, abgerufen wird für nichtig erklärt. Der Zustand vor dem Block, der die offenbarte Herausforderung enthält gilt als derselbe wie der Zustand vor dem enthaltenen Block der ungültige Block. 2. Innerhalb einer bestimmten Zeitspanne muss jeder validator seine Bitmaske offenlegen der Shards, die sie validieren. Da die Bitmaske über ein VRF erstellt wird, wenn Sie wurden dem Shard zugewiesen, der den ungültigen Zustandsübergang „they“ hatte kann nicht umhin, es zu enthüllen. Alle validator, bei denen die Bitmaske nicht angezeigt wird Es wird davon ausgegangen, dass es dem Shard zugewiesen ist. 3. Jeder validator, der nach diesem Zeitraum dem Shard zugeordnet ist, das hat zu einem Validierungsergebnis für den Block geführt, der das enthält ungültiger Block und das ergab keinen Beweis für einen ungültigen Zustandsübergang das ihrem Commit entspricht, wird gestrichen. 4. Jeder validator erhält eine neue Shard-Zuweisung und eine neue Epoche wird geplant um nach einiger Zeit zu beginnen, die ausreicht, damit alle validators das herunterladen können Zustand, wie in Abbildung 26 dargestellt. Beachten Sie, dass die validators ab dem Moment die ihnen zugewiesenen Shards offenlegen Bis zum Beginn der neuen Epoche ist die Sicherheit des Systems verringert, da die Die Shard-Zuordnung wird enthüllt. Die Teilnehmer des Netzwerks müssen es behalten Beachten Sie dies bei der Nutzung des Netzwerks in diesem Zeitraum. 3.8 Signaturaggregation Damit ein System mit Hunderten von Shards sicher funktioniert, möchten wir Folgendes haben: Größenordnung von 10.000 oder mehr validators. Wie in Abschnitt 3.7 besprochen, wollen wir jedesAbbildung 26: Die Herausforderung meistern validator um im Durchschnitt ein Commit für eine bestimmte Nachricht und eine Signatur zu veröffentlichen einmal pro Block. Selbst wenn die Commit-Nachrichten gleich wären, wäre eine solche Aggregation möglich BLS-Signatur und deren Validierung wären unerschwinglich teuer gewesen. Aber Natürlich sind die Commit- und Reveal-Nachrichten bei allen validators nicht gleich. und daher brauchen wir eine Möglichkeit, solche Nachrichten und die Signaturen in einem zusammenzufassen Dies ermöglicht eine spätere schnelle Validierung. Der spezifische Ansatz, den wir verwenden, ist der folgende: Validatoren schließen sich Blockproduzenten an. Die Blockproduzenten sind bekannt einige Zeit vor Beginn der Epoche, da sie einige Zeit zum Herunterladen benötigen Zustand vor Beginn der Epoche, und im Gegensatz zu den validators sind es die Blockproduzenten nicht verborgen. Jeder Blockproduzent verfügt über v validator Slots. Validatoren reichen ein Off-Chain-Vorschläge an die Blockproduzenten, als einer ihrer v validators. Wenn ein Blockproduzent einen validator einschließen möchte, reicht er einen ein Transaktion, die die erste Off-Chain-Anfrage von validator enthält, und die Signatur des Blockproduzenten, die dafür sorgt, dass validator dem Blockproduzenten beitritt. Beachten Sie, dass die den Blockproduzenten zugewiesenen validators dies nicht unbedingt tun Validieren Sie dieselben Shards, für die der Blockproduzent Chunks produziert. Wenn ein validator wird angewendet, um mehrere Blockproduzenten zu verbinden, nur die Transaktion von Der erste Blockproduzent wird erfolgreich sein. Blockproduzenten sammeln Commits. Der Blockproduzent sammelt ständig die Commit- und Reveal-Nachrichten von den validators. Sobald eine bestimmte Anzahl solcher Nachrichten angesammelt ist, berechnet der Blockproduzent ein Merkle Baum dieser Nachrichten und sendet an jeden validator die Merkle-Wurzel und die Merkle Weg zu ihrer Botschaft. Der validator validiert den Pfad und meldet sich an die Merkle-Wurzel. Der Blockproduzent sammelt dann eine BLS-Signatur auf dem Merkle Root aus den validators und veröffentlicht nur die Merkle Root und die gesammelte Unterschrift. Der Blockproduzent unterzeichnet auch die Gültigkeit des Multisignatur mit einer günstigen ECDSA-Signatur. Wenn die Multisignatur dies nicht tut Wenn Sie mit dem übermittelten Merkle-Stamm oder der Bitmaske der teilnehmenden validators übereinstimmen, handelt es sich um ein streichbares Verhalten. Beim Synchronisieren der Kette ein Teilnehmer Sie können wählen, ob alle BLS-Signaturen der validators validiert werden sollen (was extrem teuer ist, da die öffentlichen Schlüssel der validators aggregiert werden müssen) oder nurdie ECDMA-Signaturen von den Blockproduzenten und verlassen sich darauf, dass die Der Blockproduzent wurde nicht angefochten und gekürzt. Verwendung von On-Chain-Transaktionen und Merkle-Beweisen für Herausforderungen. Es Es kann festgestellt werden, dass es keinen Wert hat, Nachrichten von validators preiszugeben, wenn nein Es wurde ein ungültiger Zustandsübergang erkannt. Nur die Nachrichten, die das tatsächliche enthalten Beweise für einen ungültigen Zustandsübergang müssen offengelegt werden, und zwar nur für solche Nachrichten Es muss gezeigt werden, dass sie mit dem vorherigen Commit übereinstimmen. Die Nachricht muss zu zwei Zwecken offengelegt werden: 1. Um den Rollback der Kette tatsächlich auf den Moment vor dem einzuleiten ungültiger Zustandsübergang (siehe Abschnitt 3.7.5). 2. Um zu beweisen, dass der validator nicht versucht hat, die Gültigkeit des zu bestätigen Ungültiger Block. In beiden Fällen müssen wir uns mit zwei Problemen befassen: 1. Der eigentliche Commit war nicht in der Kette enthalten, sondern nur die Merkle-Wurzel des Commit aggregiert mit anderen Nachrichten. Der validator muss das verwenden Merkle-Pfad, der vom Blockproduzenten bereitgestellt wird, und dessen ursprüngliches Commit beweisen, dass sie sich der Herausforderung gestellt haben. 2. Es ist möglich, dass alle dem Shard zugewiesenen validators ungültig sind Zustandsübergänge werden zufällig beschädigten Blockproduzenten zugewiesen zensieren sie. Um dies zu umgehen, erlauben wir ihnen, ihre Enthüllungen einzureichen als reguläre Transaktion in der Kette und umgeht die Aggregation. Letzteres ist nur für die Nachweise eines ungültigen Zustandsübergangs zulässig äußerst selten und sollte daher nicht zum Spam der Blöcke führen. Das letzte Problem, das angegangen werden muss, besteht darin, dass die Blockproduzenten dies können sich dafür entscheiden, nicht an der Nachrichtenaggregation teilzunehmen oder bestimmte validators absichtlich zu zensieren. Wir machen es wirtschaftlich unvorteilhaft, indem wir den Block herstellen Produzentenbelohnung proportional zur Anzahl der ihnen zugewiesenen validators. Wir Beachten Sie auch, dass sich die Blockproduzenten zwischen den Epochen weitgehend überschneiden (seit Es sind immer die Top-W-Teilnehmer mit dem höchsten Einsatz), die validators können Bleiben Sie weitgehend bei der Zusammenarbeit mit denselben Blockproduzenten und reduzieren Sie so das Risiko dass sie einem Blockproduzenten zugewiesen wurden, der sie in der Vergangenheit zensiert hat. 3.9 Snapshots-Kette Da die Blöcke in der Hauptkette sehr häufig produziert werden, ist das Herunterladen erforderlich Die vollständige Historie könnte sehr schnell teuer werden. Darüber hinaus seit jedem Block eine BLS-Signatur einer großen Anzahl von Teilnehmern enthält, allein die Aggregation der öffentlichen Schlüssel zur Überprüfung der Signatur könnte unerschwinglich werden auch teuer. Schließlich wird Ethereum 1.0 in absehbarer Zukunft wahrscheinlich einer bleiben einer der am häufigsten verwendeten blockchains und bietet eine sinnvolle Möglichkeit, Vermögenswerte von dort zu übertragen

In der Nähe von Ethereum ist eine Anforderung, und heute ist die Überprüfung von BLS-Signaturen erforderlich, um dies sicherzustellen Die Gültigkeit naher Blöcke auf der Seite von Ethereum ist nicht möglich. Jeder Block in der Nightshade-Hauptkette kann optional einen Schnorr enthalten Multisignatur im Header des letzten Blocks, der einen solchen Schnorr enthielt Multisignatur. Wir nennen solche Blöcke Snapshot-Blöcke. Der allererste Block von Jede Epoche muss ein Snapshot-Block sein. Während ich an einer solchen Multisignatur arbeitete, Die Blockproduzenten müssen auch die BLS-Signaturen der validators sammeln auf dem letzten Snapshot-Block und aggregieren Sie sie auf die gleiche Weise wie in beschrieben Abschnitt 3.8. Da die Menge der Blockproduzenten während der gesamten Epoche konstant ist, ist eine Validierung erforderlich Nur die ersten Snapshot-Blöcke in jeder Epoche sind ausreichend, vorausgesetzt, dass bei Nr weisen darauf hin, dass ein großer Prozentsatz der Blockproduzenten und validators zusammengearbeitet und erstellt haben eine Gabel. Der erste Block der Epoche muss für die Berechnung ausreichende Informationen enthalten die Blockproduzenten und validators für die Epoche. Wir nennen die Unterkette der Hauptkette, die nur den Snapshot enthält blockiert eine Snapshot-Kette. Das Erstellen einer Schnorr-Multisignatur ist ein interaktiver Prozess, aber da wir Es muss nur selten durchgeführt werden, egal wie ineffizient der Prozess ist wird genügen. Die Schnorr-Multisignaturen können einfach unter Ethereum validiert werden, Dadurch werden entscheidende Grundelemente für eine sichere Durchführung von Cross-blockchain bereitgestellt. Kommunikation. Für die Synchronisierung mit der Near-Kette muss lediglich der gesamte Snapshot heruntergeladen werden blockiert und bestätigt, dass die Schnorr-Signaturen korrekt sind (optional auch Überprüfung der einzelnen BLS-Signaturen der validators) und dann nur die Synchronisierung Hauptkettenblöcke vom letzten Snapshot-Block.

Abschluss

In diesem Dokument haben wir Ansätze zum Erstellen von Shard-blockchains und besprochen deckte mit bestehenden Ansätzen zwei große Herausforderungen ab, nämlich die Zustandsvalidität und Datenverfügbarkeit. Anschließend präsentierten wir Nightshade, ein Sharding-Design Befugnisse NEAR Protokoll. Der Entwurf ist in Arbeit. Wenn Sie Kommentare, Fragen oder Feedback haben Zu diesem Dokument gehen Sie bitte zu https://near.chat.