Blockchain Sharding

Hallo allerseits, ich bin einer der Entwickler von Near Protocol, das unter anderem Sharding implementiert. In diesem Artikel möchte ich detailliert erläutern, was Sharding in der Blockchain im Allgemeinen ist, wie es funktioniert, und eine Reihe von Problemen ansprechen, die beim Erstellen auftreten.

Es ist bekannt, dass Ethereum, die beliebteste dApps-Plattform, weniger als 20 Transaktionen pro Sekunde verarbeitet. Aufgrund dieser Einschränkung sind der Preis für Transaktionen und die Zeit für deren Bestätigung sehr hoch: Trotz der Tatsache, dass ein Block alle 10-12 Sekunden einmal in Ethereum veröffentlicht wird, beträgt die Zeit zwischen dem Senden einer Transaktion und dem tatsächlichen Fall in den Block laut ETH-Tankstelle durchschnittlich 1,2 Minuten. Aufgrund der geringen Bandbreite, der hohen Preise und der langen Transaktionsbestätigung können keine Hochleistungsdienste auf Ethereum gestartet werden.

Der Hauptgrund dafür, dass Ethereum nicht mehr als 20 Transaktionen pro Sekunde verarbeiten kann, ist, dass jeder Knoten in Ethereum jede Transaktion überprüfen muss. In den fünf Jahren seit der Veröffentlichung von Ethereum wurden viele Ideen vorgeschlagen, um dieses Problem zu lösen. Diese Lösungen können grob in zwei Gruppen unterteilt werden: diejenigen, die anbieten, Transaktionen an eine kleine Gruppe von Knoten mit sehr guter Hardware zu delegieren, und diejenigen, die jedem Knoten anbieten, nur eine Teilmenge aller Transaktionen zu verarbeiten. Ein Beispiel für den ersten Ansatz ist Thunder , bei dem Blöcke nur von einem Knoten erstellt werden, wodurch nach Angaben der Entwickler 1200 Transaktionen pro Sekunde empfangen werden können, was 100-mal mehr ist als bei Ethereum. Weitere Beispiele aus der ersten Kategorie sind Algorand , SpaceMesh , Solana . Alle diese Protokolle verbessern verschiedene Aspekte des Protokolls und ermöglichen es Ihnen, mehr Transaktionen als in Ethereum auszuführen. Alle Protokolle sind jedoch durch die Geschwindigkeit eines (wenn auch sehr leistungsfähigen) Computers begrenzt.

Der zweite Ansatz, bei dem jeder Knoten nur eine Teilmenge von Transaktionen verarbeitet, wird als Sharding bezeichnet. Auf diese Weise plant die Ethereum Foundation, die Bandbreite von Ethereum zu erhöhen.

In diesem Beitrag werde ich Ihnen am Beispiel mehrerer Protokolle, die derzeit entwickelt werden, erklären, wie Sharding in Blockchain funktioniert.

Das einfachste Splittern

In der einfachsten Implementierung werden wir anstelle einer Blockchain mehrere unterstützen und jede solche Blockchain als "Shard" bezeichnen. Jeder Shard wird von einer unabhängigen Gruppe von Knoten unterstützt, die Transaktionen überprüfen und Blöcke erstellen. Im Folgenden werde ich solche Knoten als Validatoren bezeichnen.

Jeder Shard ist für eine Teilmenge von Verträgen und Konten verantwortlich. Nehmen Sie vorerst an, dass Transaktionen immer nur mit Verträgen und Konten innerhalb desselben Shards ausgeführt werden. Ein derart vereinfachtes Design reicht aus, um einige interessante Probleme und Merkmale des Splitterns aufzuzeigen.

Termin für Validatoren und zentrale Blockchain

Das erste Problem mit der Tatsache, dass jeder Shard seine eigenen Validatoren hat, ist, dass wenn wir 10 Shadras haben, jeder Shard jetzt 10-mal weniger zuverlässig ist als eine Blockchain. Wenn also eine Blockchain mit X-Validatoren beschließt, eine harte Gabel in einem Shard-System mit 10 Shards zu erstellen und die X-Validatoren zwischen 10 Shards aufteilt, gibt es jetzt nur noch X / 10-Validatoren in jedem Shard. Um die Kontrolle über den Shard zu erlangen, müssen Sie die Kontrolle über 5,1% erlangen (51) % / 10) Validatoren.

Was zu der ersten interessanten Frage führt: Wer weist Shards Validatoren zu? Die Kontrolle über 5,1% der Validatoren ist nur dann ein Problem, wenn sich alle 5,1% der Validatoren im selben Shard befinden. Wenn die Validatoren selbst nicht auswählen können, welchem ​​Shard sie zugewiesen sind, können sie keine Kontrolle über 5,1% der Validatoren erlangen, bevor sie den Shards zugewiesen werden.

Fast alle vorhandenen vorgeschlagenen Sharding-Designs verwenden eine Zufallszahlenquelle, um Shards Validatoren zuzuweisen. Das Erhalten von Zufallszahlen in einem verteilten System, in dem sich die Teilnehmer nicht gegenseitig vertrauen, ist heute kein vollständig gelöstes Problem, das wir in diesem Artikel nicht ansprechen werden, und nehmen einfach an, dass wir eine solche Quelle von Zufallszahlen haben.

Sowohl der Empfang von Zufallszahlen als auch die Ernennung von Validatoren sind systemweite Berechnungen, die für keinen bestimmten Shard spezifisch sind. Für solche Berechnungen verfügen moderne Shard-Blockchain-Designs über eine zusätzliche dedizierte Blockchain, die ausschließlich zur Durchführung systemweiter Berechnungen vorhanden ist. Zusätzlich zu Zufallszahlen und der Ernennung von Validatoren können solche Berechnungen das Abrufen von Hashes der letzten Blöcke aus Shards und deren Speicherung umfassen. Verarbeitung von Sicherheiten in Proof-of-Stake-Systemen und Untersuchung von Hinweisen auf unangemessenes Verhalten mit der damit verbundenen Auswahl solcher Sicherheiten; Shards neu ausgleichen, wenn eine solche Funktion bereitgestellt wird. Eine solche Blockchain wird in Ethereum 2.0 und Near Protocol als Beacon-Kette, in PolkaDot als Relay-Kette und in Cosmos als Cosmos Hub bezeichnet.

In diesem Beitrag werden wir eine solche Blockchain die "zentrale Blockchain" nennen. Die Existenz einer zentralen Blockchain führt uns zum nächsten interessanten Thema - dem quadratischen Sharding.

Quadratisches Splittern

Sharding wird oft als eine Lösung dargestellt, die mit zunehmender Anzahl von Knoten unendlich skaliert. Wahrscheinlich können Sie mit dieser Eigenschaft wirklich ein System erstellen, aber Systeme mit einer zentralen Blockchain haben eine Obergrenze für die Anzahl der Shards und daher keine unendliche Skalierbarkeit. Es ist leicht zu verstehen, warum: Die zentrale Blockchain führt einige Berechnungen durch, z. B. das Zuweisen von Validatoren und das Beibehalten der neuesten Shard-Zustände, deren Komplexität proportional zur Anzahl der Shards ist. Da die zentrale Blockchain selbst nicht sharded ist und ihr Durchsatz durch den Durchsatz jedes Knotens begrenzt ist, ist die Anzahl der Shards, die sie unterstützen kann, begrenzt.

Mal sehen, wie sich der Durchsatz des gesamten Systems ändert, wenn sich die Leistung der Knoten, die es unterstützen, k-mal erhöht. Jeder Shard kann k-mal mehr Transaktionen verarbeiten, und die zentrale Blockchain kann k-mal mehr Shards unterstützen. Somit wächst der Durchsatz des gesamten Systems um das k ^ 2-fache. Daher der Name "quadratisches Sharding".

Es ist schwer vorherzusagen, wie viel Shard heute die zentrale Blockchain unterstützen kann, aber höchstwahrscheinlich werden wir in naher Zukunft nicht an das Transaktionslimit für eine Sharded-Blockchain mit quadratischem Sharding herankommen. Höchstwahrscheinlich werden wir bald an die Grenze stoßen, wie viele Knoten benötigt werden, um eine solche Anzahl von Shards zu unterstützen.

Staatliche Scherbe

Der Status enthält alle Informationen zu allen Konten und Verträgen. Bisher haben wir über Sharding im Allgemeinen gesprochen, ohne genau anzugeben, was Sharding ist. Knoten in der Blockchain führen die folgenden drei Aufgaben aus: 1) Transaktionen ausführen 2) Transaktionen und Blöcke an andere Knoten weiterleiten und 3) den Status und den Verlauf der Blockchain speichern. Jede dieser drei Aufgaben ist mit einer ständig zunehmenden Belastung der Knoten verbunden:

1. Die Notwendigkeit, Transaktionen durchzuführen, erfordert mehr Rechenleistung mit einer Zunahme der Anzahl von Transaktionen;
2. Die Notwendigkeit, Transaktionen weiterzuleiten, erfordert mehr Netzwerkbandbreite, wenn die Transaktionen zunehmen.
3. Die Notwendigkeit, Status und Verlauf beizubehalten, erfordert mehr Speicherplatz, wenn die Größe des Status und / oder des Verlaufs zunimmt. Es ist wichtig zu beachten, dass im Gegensatz zu den ersten beiden Punkten der erforderliche Speicherplatz zunimmt, auch wenn sich die Anzahl der Transaktionen pro Zeiteinheit nicht ändert.

Aus der obigen Liste geht hervor, dass der Speicherplatz das größte Problem darstellt, da nur der Speicherplatz wächst, selbst wenn die Anzahl der Transaktionen nicht wächst, in der Praxis jedoch nicht. Heutzutage belegt der Status von Ethereum etwa 100 GB, was auf jedem modernen Computer problemlos gespeichert werden kann. Die Anzahl der Transaktionen, die Ethereum verarbeiten kann, ist jedoch auf mehrere zehn pro Sekunde begrenzt und hängt von der Rechenleistung und dem Netzwerk ab.

Zilliqa ist das bekannteste Projekt, das Computer und Netzwerk zerstört, aber keinen Staat. Das Berechnen von Sharding ist einfacher als das Sharding-Status, da alle Knoten alle Status haben und dennoch problemlos Verträge ausführen können, die andere Verträge verursachen oder Konten auf verschiedenen Shards beeinflussen. In dieser Hinsicht ist das Design von Zilliqa zu vereinfacht, Kritik am Design auf Englisch kann hier gelesen werden .

Obwohl State Sharding ohne Shading-Berechnungen vorgeschlagen wurde, sind mir keine Projekte bekannt, die dies wirklich tun. Daher gehen wir davon aus, dass State Sharding Sharding-Berechnungen impliziert.

In der Praxis isoliert die Tatsache, dass der Zustand auf irgendeine Weise zerplatzt ist, die Scherben und ermöglicht es ihnen, unabhängige Blockchains zu sein, wie wir oben definiert haben. Validatoren in Shards speichern nur einen für ihren Shard spezifischen Status, und nur Transaktionen, die diesen Status betreffen, werden ausgeführt und weitergeleitet. Dies reduziert die Belastung des Prozessors, der Festplatte und des Netzwerks linear mit der Anzahl der Shards, bringt jedoch neue Probleme mit sich, wie z. B. Inter-Shard-Transaktionen.

Inter-Shard-Transaktionen

Bisher haben wir Shards als unabhängige Blockchains in Bezug auf die Ausführung von Transaktionen gesehen. Mit diesem Design ist es beispielsweise unmöglich, eine Transaktion abzuschließen, bei der Geld zwischen zwei Konten auf zwei verschiedenen Shards übertragen wird, oder einen Kontakt auf einem Shard aus einem Vertrag mit einem anderen herzustellen. Ich möchte beide Szenarien unterstützen.

Der Einfachheit halber betrachten wir nur Transaktionen, die Geld überweisen, und wir gehen davon aus, dass jeder Teilnehmer ein Konto auf genau einem Shard hat. Wenn ein Teilnehmer auf einem Shard Geld an einen Teilnehmer auf demselben Shard überweisen möchte, können die Validatoren dieses Shards diese Transaktion verarbeiten und auf den Staat anwenden. Aber wenn Alice zum Beispiel ein Konto auf Shard Nr. 1 hat und sie Geld mit einem Konto auf Shard Nr. 2 an Bob senden möchte, weder Shard-Validatoren Nr. 1 (die Bob kein Geld hinzufügen können) noch Shard-Validatoren Nr. 2 (die Alice nicht bekommen können) ) kann die Transaktion nicht abschließen und den Status nicht aktualisieren.

Es gibt zwei große Gruppen von Ansätzen zur Lösung dieses Problems:

1. Synchron : Bei jeder Transaktion mit mehreren Shards werden Blöcke in Shards mit Statusaktualisierungen für diese Transaktion gleichzeitig erstellt, und Validatoren in diesen Shards arbeiten zusammen, um solche Blöcke zu erstellen. Das aufwendigste Design dieses Ansatzes, das mir bekannt ist, sind Merge Blocks, die hier (auf Englisch) beschrieben werden .

   
   

2. Asynchron : Eine Inter-Shard-Transaktion wird in Shards ausgeführt, die davon betroffen sind. Asynchron: Der Teil der Transaktion, der Bob Geld hinzufügt, wird in Shard 2 ausgeführt, wenn die Validatoren im Shard Beweise dafür haben, dass der Teil der Transaktion, der Geld von Alice abzieht, in ausgeführt wurde Scherbe # 1. Dieser Ansatz ist in den heute entwickelten Systemen populärer, da für die Blockproduktion keine zusätzliche Synchronisation zwischen Shards erforderlich ist. Solche Systeme werden heute in Cosmos, Ethereum Serenity, Near Protocol, Kadena und anderen angeboten. Das Problem bei diesem Ansatz besteht darin, dass, wenn die Blöcke unabhängig voneinander erstellt werden, wahrscheinlich einer der Blöcke, die die Statusaktualisierung für die Transaktion enthalten, nicht in der kanonischen Kette in ihrem Shard enthalten ist und die Transaktion daher nur teilweise abgeschlossen wird. Betrachten Sie zum Beispiel die folgende Abbildung. Es zeigt zwei Shards, in denen die Gabeln aufgetreten sind, und eine Inter-Shard-Transaktion, deren Statusaktualisierung sich in den Blöcken A bzw. X 'widerspiegelt. Wenn sich herausstellt, dass die Ketten AB und V'-X'-Y'-Z 'in ihren Scherben kanonisch sind, ist die Transaktion vollständig abgeschlossen. Wenn die Ketten A'-B'-C'-D 'und VX kanonisch sind, wird die Transaktion vollständig abgebrochen, was akzeptabel ist. Wenn beispielsweise AB und VX kanonisch werden, wird ein Teil der Transaktion abgeschlossen, der andere abgebrochen und die Transaktion teilweise abgeschlossen.

   
   

Das oben beschriebene Szenario ist eines der großen Probleme beim Sharding, bei dem nicht alle vorgeschlagenen Lösungen optimal sind. Wir werden es weiter unten ansprechen.

Schlechtes Benehmen

Nachdem wir herausgefunden haben, wie Shard-Blockchains funktionieren, und die Konzepte der zentralen Blockchain, die Ernennung von Validatoren und Cross-Shard-Transaktionen untersucht haben, werden wir uns am Ende dieses Artikels mit einem weiteren interessanten Thema befassen: Was kann ein Teilnehmer, der versucht, das System anzugreifen, tun, wenn er es schafft? Kontrolle über eine ausreichend große Anzahl von Validatoren in einem Shard.

Gezielte Gabeln

Wenn der Teilnehmer genügend Kontrolle über die Scherbe hat, kann er gezielt Gabeln erstellen. Bei der Erstellung von Gabeln spielt es keine Rolle, welcher Konsens in Shards verwendet wird. Insbesondere spielt es keine Rolle, ob es sich um BFT handelt oder nicht. Wenn eine ausreichende Anzahl von Validatoren unter der Kontrolle eines Angreifers steht, kann eine Gabel erstellt werden. Das Ziel der Abzweigung könnte beispielsweise darin bestehen, eine Transaktion zurückzusetzen, die für etwas außerhalb der Blockchain bezahlt hat.

Es wird behauptet, dass es einfacher ist, die Kontrolle über 50% des Shards zu erlangen als über 50% des gesamten Netzwerks (zum Beispiel, weil ein Teilnehmer versuchen kann, Validatoren zu hacken oder zu bestechen, nachdem sie dem Shard zugewiesen wurden). Per Definition ändern Inter-Shard-Transaktionen den Status in mehreren Shards. Solche Änderungen fallen in einige Blöcke in den Blockketten der entsprechenden Shards. Es ist notwendig, dass entweder alle derartigen Blöcke finalisiert werden (d. H. Zur kanonischen Kette in ihren jeweiligen Scherben gehörten) oder dass nicht alle finalisiert werden sollten (d. H. Nicht zur kanonischen Kette in ihren Scherben gehörten). Da wir davon ausgehen, dass einige Teilnehmer mit schlechten Absichten im Prinzip die Kontrolle über den Shard erlangen können, können wir nicht davon ausgehen, dass Gabeln nicht auftreten, selbst wenn ein byzantinischer Konsens erreicht wurde oder eine große Anzahl von Blöcken auf einem Block mit einer Transaktion aufgebaut wurde.

Dieses Problem hat viele Lösungen, von denen die einfachste manchmal darin besteht, den Hash des letzten Blocks im Shard in der zentralen Blockchain zu speichern. Der kanonische Kettenauswahlalgorithmus in Shards wird dann so geändert, dass kein Ziel den letzten Block enthält, der in der zentralen kanonischen Blockchain gespeichert ist. Um Situationen vollständig zu vermeiden, in denen eine Transaktion teilweise abgeschlossen ist, weil sich einige der Blöcke, die ihre Statusaktualisierung enthalten, außerhalb der kanonischen Ketten befinden, können Sie den Algorithmus zum Ausführen von Inter-Shard-Transaktionen so ändern, dass Shard A den Beweis der Transaktion in Shard B erst im Block akzeptiert Das Status-Update für die Transaktion in Shard B wurde nicht in der zentralen Blockchain gespeichert.

Ungültige Blöcke erstellen

Wenn der Teilnehmer die Kontrolle über eine ausreichend große Anzahl von Validatoren im Shard erlangen konnte, kann er versuchen, einen vollständig ungültigen Block zu erstellen. Angenommen, der Status vor dem Block war so, dass Alice 10 Token hatte, und in Bob - 0 enthält der Block nur eine Transaktion, die 10 Token von Alices Konto an Bobs Konto sendet, im neuen Status jedoch 0 Token von Alice und 1000 mit Bob.

In einer klassischen, nicht gesplitteten Blockchain ist das Erstellen eines solchen Blocks unmöglich, da alle Teilnehmer, wie diejenigen, die Blöcke erstellen, und diejenigen, die einfach die Blockchain verwenden, alle Blöcke überprüfen und jeden Block, der solche Fehler enthält, sofort verwerfen. Selbst wenn die vom Angreifer kontrollierten Validatoren die Kette schneller erstellen können, können sie die längere Kette mit dem ungültigen Block nicht als kanonische übergeben, da alle Netzwerkteilnehmer den ungültigen Block und alle darauf erstellten Blöcke sofort verwerfen. Ehrliche Validatoren bauen weiterhin auf dem letzten gültigen Block auf, und alle Netzwerkteilnehmer sehen ihre Kette als kanonisch an.

Die obige Abbildung zeigt fünf Validatoren, von denen drei unter der Kontrolle des Angreifers stehen. Sie erstellten den ungültigen Block A 'und bauten dann die Kette weiter auf. Zwei private Prüfer verwarfen Block A 'sofort als ungültig und bauten weiter auf dem letzten gültigen Block auf, den sie kannten, wodurch eine Gabelung erstellt wurde. Da es in einer ehrlichen Kette weniger Validatoren gibt als in einer unehrlichen, ist ihre Kette kürzer. In der klassischen Blockchain ohne Hardware validieren jedoch alle Teilnehmer des Systems alle Blöcke, die sie sehen. Somit sieht jeder Teilnehmer, der die Blockchain verwendet, dass A 'ungültig ist, verwirft es und verwirft daher B', C 'und D' als auf dem ungültigen Block aufgebaut, und somit sehen alle Teilnehmer AB als eine kanonische Kette.

In einem Shard-Design kann kein Teilnehmer alle Blöcke in allen Blockchains validieren. Daher benötigen wir einen Mechanismus, mit dem Validatoren in einem bestimmten Shard sicherstellen können, dass zu keinem Zeitpunkt in der Vergangenheit ein ungültiger Block in einem anderen Shard erstellt wurde, von dem sie eine Inter-Shard-Transaktion erhalten haben.

, , . , , ( ).

, :

1. - . , 2/3 . , , , . , , , - , . , .
2. - , , , , , . , zk-SNARKs ( zk, zero-knowledge, , non-zk SNARKs). , zk-SNARKs , .

, , , , . — .

Ich schreibe viel über Blockchain und Sharding auf Englisch. Wir interviewen auch regelmäßig Autoren anderer Protokolle wie Cosmos und Solana und vertiefen uns in technische Details. Wenn Sie sich für das Thema interessieren, können Sie neuen Posts und Videos folgen, indem Sie meinen Twitter @AlexSkidanov abonnieren .