Ein Leitfaden zum Blockchain Sharding, Teil 2
Im ersten Teil dieser Serie von zwei Beiträgen haben wir die Motivation fürs Blockchain-Sharding beleuchtet und einige Kernkonzepte diskutiert. In diesem Beitrag werden wir einige fortgeschrittene Aspekte des Shardings diskutieren, einschließlich der zwei größten ungelösten Herausforderungen: Datenverfügbarkeit und Datenvalidität.
Einleitung
Die Kernidee in geshardeten Blockchains ist, dass die meisten Teilnehmer, die das Netzwerk betreiben oder verwenden, keine Blöcke in allen Shards validieren können. Wenn ein Teilnehmer mit einem bestimmten anderen Shard interagieren muss, kann er daher im Allgemeinen nicht den gesamten Verlauf des anderen Shards herunterladen und validieren.
Der Partitions-Aspekt des Shardings wirft jedoch ein erhebliches potenzielles Problem auf: Ohne Herunterladen und Validieren des gesamten Verlaufs des anderen Shards kann der Teilnehmer nicht unbedingt sicher sein, dass der State, also der Zustand der anderen Blockchain, mit dem er interagiert, das Ergebnis einer gültigen Sequenz von Blöcken ist und dass diese Reihenfolge der Blöcke in der Tat die kanonische (also gültige) Kette des Shards ist. Ein Problem, das in einer nicht geshardeten Blockchain nicht vorkommt.
Wir werden zunächst eine einfache Lösung für dieses Problem vorstellen, die von vielen Protokollen vorgeschlagen wurde. Daran anschließend, werden wir analysieren, wie diese Lösung überlistet werden kann und welche Versuche unternommen wurden, dies zu beheben.
Die vermeintlich einfache Lösung
Die naive Lösung für die Datenvalidität lautet wie folgt: Nehmen wir an, das gesamte System verfügt über Tausende von Validierern, von denen nicht mehr als 20% böswillig sind oder anderweitig versagen (z. B. weil sie nicht online sind, um neue Blöcke zu produzieren). Wenn wir dann ~200 Validierer befragen, kann angenommen werden, dass die Wahrscheinlichkeit, dass mehr als ⅓ aus genannten Gründen versagen, gegen Null geht.
Der Wert von ⅓ ist eine wichtige Schwelle. Es gibt eine Reihe von Konsens-Protokollen, die als BFT-Konsens-Protokolle bezeichnet werden und gewährleisten, dass der Konsens erreicht wird, wenn weniger als 1/3 der Teilnehmer durch Abstürzen oder durch Verhalten, das gegen das Protokoll verstößt, ausfallen. BFT steht für “Byantine Fault Tolerance”, ein wichtiges Prinzip in der Informatik.
Unter dieser Annahme eines Prozentsatzes an ehrlichen Validierern geht die naive Lösung davon aus, dass der Block gültig ist und auf dem basiert, was die Validierer als kanonische Kette für diesen Shard angesehen haben, als sie begannen zu validieren. Die Validierer erhielten die kanonische Kette aus der vorherigen Gruppe von Validierern, die nach derselben Annahme auf dem Block aufbauten, der zuvor der Kopf der kanonischen Kette war. Durch Induktion ist die gesamte Kette gültig und da an keinem Punkt ein Satz von Validierern Forks erzeugt, ist die naive Lösung auch sicher, dass die aktuelle Kette die einzige Kette im Shard ist.
Diese einfache Lösung funktioniert nicht, wenn wir davon ausgehen, dass die Validierer adaptiv beschädigt sein können, was eine in Betracht zu ziehende Annahme ist (siehe hier, um mehr über adaptive Korruption zu erfahren). Das adaptive Beschädigen eines einzelnen Shards in einem System mit 1000 Shards ist erheblich billiger als das Beschädigen des gesamten Systems. Daher nimmt die Sicherheit des Protokolls linear mit der Anzahl der Shards ab. Um Gewissheit über die Gültigkeit eines Blocks zu haben, müssen wir wissen, dass zu keinem Zeitpunkt in der Geschichte ein Teil des Systems eine Mehrheit von Validierern hat, die zusammenarbeiten. Mit adaptiven Gegnern haben wir keine Gewissheit mehr. Wie wir im vorherigen Teil besprochen haben, können Prüfer, die Absprachen treffen, zwei grundlegende böswillige Verhaltensweisen ausüben: Erstellen von Forks und Erzeugen ungültiger Blöcke.
Bösartige Forks können durch Quervernetzung von Blöcken mit der Beacon-Chain bekämpft werden, die im Allgemeinen eine wesentlich höhere Sicherheit als die Shard-Chains bietet. Ungültige Blöcke zu produzieren, ist jedoch ein wesentlich schwierigeres Problem.
Datengültigkeit
Betrachten wir die folgende Abbildung, in der Shard # 1 beschädigt ist, da ein böswilliger Akteur den ungültigen Block B erzeugt hat. Angenommen, in diesem Block B wurden 1000 Token aus dem Nichts auf dem Konto von Alice erzeugt. Der böswillige Akteur erzeugt dann einen gültigen Block C (in dem Sinne, dass die Transaktionen in C korrekt angewendet werden) über B, verschleiert den ungültigen Block B und initiiert eine Cross-Shard-Transaktion an Shard #2, die diese 1000 Token an Bob`s Konto überträgt. Ab diesem Moment befinden sich die nicht ordnungsgemäß erstellten Token in einer ansonsten vollständig gültigen Blockchain in Shard #2.
Einige einfache Ansätze zur Lösung dieses Problems sind:
- Validierer von Shard #2 validieren den Block, von dem aus die Transaktion initiiert wird. Dies funktioniert auch im obigen Beispiel nicht, da Block C vollständig gültig zu sein scheint.
- Validierer in Shard #2 validieren eine große Anzahl von Blöcken, die dem Block vorangehen, von dem aus die Transaktion initiiert wird. Natürlich können die böswilligen Validierer für eine beliebige Anzahl von Blöcken N, die vom empfangenden Shard validiert wurden, N + 1 gültige Blöcke zusätzlich zu dem ungültigen Block erstellen, den sie erzeugt haben.
Eine vielversprechende Idee, um dieses Problem zu lösen, besteht darin, Shards in einem ungerichteten Diagramm anzuordnen, in dem jeder Shard mit mehreren anderen Shards verbunden ist und nur Shard übergreifende Transaktionen zwischen benachbarten Shards zuzulassen (z. B. funktioniert Vlad Zamfir`s Sharding im Wesentlichen so und eine ähnliche Idee wird in Kadenas Chainweb verwendet). Wenn eine Shard übergreifende Transaktion zwischen Shards benötigt wird, die keine Nachbarn sind, wird diese Transaktion über mehrere Shards geleitet. Bei diesem Entwurf wird erwartet, dass ein Validierer in jedem Shard sowohl alle Blöcke in seinem Shard, als auch alle Blöcke in allen benachbarten Shards prüft. Betrachten wir die folgende Abbildung mit 10 Shards mit jeweils vier Nachbarn und keinen zwei Shards, die mehr als zwei Verbindungslinien für eine Cross-Shard-Kommunikation benötigen:
Shard #2 validiert nicht nur seine eigene Blockchain, sondern auch Blockchains aller Nachbarn, einschließlich Shard #1. Wenn also ein böswilliger Akteur auf Shard #1 versucht, einen ungültigen Block B zu erstellen, darauf Block C aufzubauen und eine Shard übergreifende Transaktion zu initiieren,wird diese Cross-Shard-Transaktion nicht durchkommen, da Shard #2 die gesamte Historie von Shard #1 validiert hat. Das führt dazu, dass der ungültige Block B identifiziert wird.
Während das Beschädigen eines einzelnen Shards kein gangbarer Angriff mehr ist, bleibt das Angreifen mehrerer Shards ein Problem. In der folgenden Abbildung führt ein Gegner, der sowohl Shard #1 als auch Shard #2 beschädigt, erfolgreich eine Cross-Shard-Transaktion zu Shard #3 mit Geldern aus einem ungültigen Block B aus:
Shard #3 überprüft alle Blöcke in Shard #2, jedoch nicht in Shard #1, und kann den bösartigen Block nicht erkennen.
Es gibt grundsätzlich zwei Ansätze für die ordnungsgemäße Lösung der Datengültigkeit: Fischer und kryptografische Berechnungsnachweise.
Fischer
Die Idee hinter dem ersten Ansatz ist die folgende: Wann immer ein Block-Header (die “Haushaltsdaten” des Blocks) zwischen Chains für irgendeinen Zweck (wie zum Beispiel das Vernetzen mit der Beacon-Chain oder eine Cross-Shard-Transaktion) kommuniziert wird, gibt es einen Zeitraum, in dem ein ehrlicher Validierer eine Anfechtung (in der Grafik “Challenge”) starten kann, dass der Block ungültig ist. Es gibt verschiedene Konstruktionen, die sehr prägnante Beweise dafür ermöglichen, dass die Blöcke ungültig sind, sodass der Kommunikationsaufwand für das Empfangen einer Anfechtung für die empfangenden Knoten viel geringer ist, als für den Empfang eines vollständigen Blocks.
Bei diesem Ansatz ist das System sicher, solange sich mindestens ein seriöser Prüfer im Shard befindet.
Dies ist der vorherrschende Ansatz (abgesehen davon so zu tun, als würde das Problem nicht existieren) unter den heute vorgeschlagenen Protokollen. Dieser Ansatz hat jedoch zwei große Nachteile:
- Der Zeitraum für eine Anfechtung muss ausreichend lang sein, damit der ehrliche Validierer Zeit hat zu erkennen, dass ein Block erstellt wurde, ihn herunterzuladen, vollständig zu überprüfen und die Anfechtung vorzubereiten, wenn der Block ungültig ist. Die Einführung eines solchen Zeitraums würde die Cross-Shard-Transaktionen erheblich verlangsamen.
- Das Vorhandensein des Anfechtungs-Protokolls erzeugt einen neuen Angriffsvektor, wenn böswillige Knoten mit ungültigen Anfechtungen Spam versenden. Eine naheliegende Lösung für dieses Problem besteht darin, die anfechtenden Validierer zu veranlassen, eine bestimmte Menge von Token einzuzahlen und als Pfand zu hinterlegen, die zurückgegeben werden, wenn die Anfechtung gültig ist. Dies ist nur eine Teillösung, da es für den Gegner immer noch von Vorteil sein kann, das System mit ungültigen Anfechtungen vollzuspammen (und das Pfand zu verlieren), um beispielsweise zu verhindern, dass die gültige Anfechtung von einem ehrlichen Validierer angenommen wird. Diese Angriffe werden als Trauerattacken (im Englischen “Griefing Attacks”) bezeichnet.
Keines der beiden Probleme der Fischer-Lösung besitzt bisher eine zufriedenstellende Lösung, aber die Verwendung des Fischers ist immer noch besser als die Möglichkeit, dass ein ungültiger Block erstellt wird.
Prägnante nicht-interaktive Argumente des Wissens
Die zweite Lösung für Multi-Shard-Korruption besteht darin, eine Art von kryptografischen Konstruktionen zu verwenden, mit denen nachgewiesen werden kann, dass eine bestimmte Berechnung (z. B. die Berechnung eines Blocks aus einer Reihe von Transaktionen) korrekt ausgeführt wurde. Solche Konstruktionen existieren, z.B. zk-SNARKs, zk-STARKs und einige andere, und einige werden heute in Blockchain-Protokollen aktiv für private Zahlungen verwendet, insbesondere bei ZCash. Das Hauptproblem bei solchen Ansätzen besteht darin, dass sie notorisch langsam zu berechnen sind. Z.B. Das Coda-Protokoll, das zk-SNARKs verwendet, um zu beweisen, dass alle Blöcke in der Blockchain gültig sind, sagte in einem der Interviews, dass die Erstellung eines Proofs pro Transaktion 30 Sekunden dauern kann (diese Zahl ist wahrscheinlich inzwischen geringer, aber immer noch viel zu lang).
Interessanterweise muss ein Beweis nicht von einer vertrauenswürdigen Partei berechnet werden, da der Beweis nicht nur die Gültigkeit der Berechnung bestätigt, für die er erstellt wurde, sondern auch die Gültigkeit des Beweises selbst. Auf diese Weise kann die Berechnung derartiger Beweise auf eine Gruppe von Teilnehmern mit erheblich weniger Redundanz aufgeteilt werden, als dies für eine vertrauenslose Berechnung erforderlich wäre. Außerdem können Teilnehmer, die zk-SNARKs berechnen, auf einer speziellen Hardware ausgeführt werden, ohne die Dezentralisierung des Systems zu beeinträchtigen.
Die Herausforderungen von zk-SNARKs sind neben der Leistung:
- Abhängigkeit von weniger erforschten und weniger zeitgetesteten, kryptografischen Methoden;
- „Giftmüll“ — zk-SNARKs hängen von einer vertrauenswürdigen Konfiguration ab, in der eine Gruppe von Personen eine Berechnung durchführt und dann die Zwischenwerte dieser Berechnung verwirft. Wenn alle Teilnehmer der Prozedur kollidieren und die Zwischenwerte einhalten, können gefälschte Beweise erstellt werden;
- Zusätzliche Komplexität beim Systemdesign;
- zk-SNARKs funktionieren nur für eine Teilmenge möglicher Berechnungen, sodass ein Protokoll mit einer Turing-fertigen Smart-Contract Programmiersprache SNARKs nicht zum Nachweis der Gültigkeit der Kette verwenden kann.
Während viele Protokolle die langfristige Verwendung von zk-SNARKs in Betracht ziehen, kenne ich bis jetzt keine Pläne, diese zu verwenden, außer bei Coda.
Datenverfügbarkeit
Das zweite Problem, das wir ansprechen, ist die Datenverfügbarkeit. Im Allgemeinen werden Knoten, die eine bestimmte Blockchain betreiben, in zwei Gruppen unterteilt: Vollständige Knoten (im Englischen “Full Nodes”), die jeden vollständigen Block herunterladen und jede Transaktion validieren, und leichte Knoten (“Light Nodes”), die nur die Überschriften der Blöcke herunterladen und Merkle-Beweise für Teile des State und der Transaktionen verwenden, an denen sie interessiert sind.
Wenn nun die Mehrheit der vollständigen Knoten kollidiert, können sie einen gültigen oder ungültigen Block erzeugen und seinen Hash an die Light Nodes senden, jedoch niemals den vollständigen Inhalt des Blocks offenlegen. Es gibt verschiedene Möglichkeiten, wie sie davon profitieren können. Betrachten wir zum Beispiel die folgende Abbildung:
Es gibt drei Blöcke: Der vorherige, A, wird von ehrlichen Validierern erstellt; beim aktuellen, B, sprechen sich böswillige Validierer ab; und der nächste, C, wird ebenfalls von ehrlichen Validierern produziert (die Blockchain ist in der unteren rechten Ecke abgebildet).
Du bist ein Kaufmann. Die Validierer des aktuellen Blocks (B) haben Block A von den vorherigen Validierern empfangen, einen Block berechnet, in dem Sie Geld erhalten haben und Ihnen die Überschrift dieses Blocks mit einem Merkle-Nachweis des States gesendet, in dem Du Geld hast (oder eine Merkle-Nachweis einer gültigen Transaktion, die das Geld an Dich sendet). Wenn Du sicher bist, dass die Transaktion abgeschlossen ist, stellst Du den Service bereit.
Die Validierer verteilen jedoch niemals den vollständigen Inhalt des Blocks B an irgendjemanden. Aus diesem Grund können die ehrlichen Validierer von Block C nicht den gesamten Block abrufen und sind entweder gezwungen, das System anzuhalten oder auf A aufzubauen, was Dich als Händler des Geldes beraubt.
Wenn wir dasselbe Szenario auf das Sharding anwenden, gelten die Definitionen für den vollständigen und den leichten Knoten im Allgemeinen für jeden Shard: Validierer in jedem Shard laden jeden Block in diesem Shard herunter und validieren jede Transaktion in diesem Shard. Aber auch andere Knoten im System, einschließlich derjenigen, die Momentaufnahmen von Shard-Chains erstellen und in die Beacon-Chain einfügen, laden nur die Blockheader herunter. Somit sind die Validierer in dem Shard effektiv Full Nodes für diesen Shard, während andere Teilnehmer in dem System, einschließlich der Beacon-Chain, als Light Nodes arbeiten.
Damit der oben diskutierte Fischer-Ansatz funktioniert, müssen ehrliche Validierer in der Lage sein, Blöcke herunterzuladen, die mit der Beacon-Chain vernetzt sind. Wenn böswillige Validierer eine Überschrift eines ungültigen Blocks vernetzt haben (oder ihn zum Initiieren einer Cross-Shard-Transaktion verwendeten), den Block jedoch nie verteilt haben, haben die ehrlichen Validierer keine Möglichkeit, eine Anfechtung zu erstellen.
Wir werden zwei Ansätze behandeln, um dieses Problem zu lösen, die sich gegenseitig ergänzen.
Nachweis durch Verwahrung
Das am schnellsten zu lösende Problem ist die Frage, ob ein Block verfügbar ist, sobald er veröffentlicht wurde. Eine vorgeschlagene Idee ist, sogenannte Notare zu haben, die häufiger zwischen Shards wechseln als Validierer, deren einzige Aufgabe es ist, einen Block herunterzuladen und zu bestätigen, dass sie ihn herunterladen konnten. Sie können häufiger die Shards wechseln, da im Gegensatz zu den Validierern nicht der gesamte State des Shards heruntergeladen werden muss.
Das Problem bei diesem naiven Ansatz ist, dass es unmöglich ist, später zu beweisen, ob der Notar den Block herunterladen konnte oder nicht. Theoretisch kann ein Notar bescheinigen, dass er den Block herunterladen konnte, ohne auch nur zu versuchen, ihn abzurufen. Eine Lösung hierfür besteht darin, dass Notare Beweise vorlegen oder eine bestimmte Menge von Token einsetzen, die bestätigen, dass der Block heruntergeladen wurde. Eine solche Lösung wird hier diskutiert.
Erasure Codes
Wenn ein bestimmter Light Node einen Hash eines Blocks empfängt, kann er versuchen, ein paar zufällige Teile des Blocks herunterzuladen, um die Sicherheit des Knotens zu erhöhen, dass der Block verfügbar ist. Dies ist keine vollständige Lösung, da die Hersteller von bösartigen Blöcken die Teile des Blocks, die nicht von einem Light Node heruntergeladen wurden, zurückhalten können, sofern die Light Nodes nicht gemeinsam den gesamten Block herunterladen, sodass der Block weiterhin nicht verfügbar ist.
Eine Lösung besteht darin, eine Konstruktion mit dem Namen “Erasure Codes” zu verwenden, um die Wiederherstellung des gesamten Blocks zu ermöglichen, auch wenn nur ein Teil des Blocks verfügbar ist:
Sowohl Polkadot als auch Ethereum Serenity haben Entwürfe basierend auf dieser Idee. Diese Entwürfe ermöglichen es Light Nodes, einigermaßen sicher zu sein, dass die Blöcke verfügbar sind. Der Ethereum Serenity-Ansatz wird in diesem Artikel ausführlich beschrieben. Beide Ansätze beruhen auf Anfechtungen und sind daher potenziell anfällig für Trauerangriffe.
Langzeitverfügbarkeit und Fazit
Beachten Sie, dass alle oben diskutierten Ansätze nur die Tatsache bestätigen, dass ein Block überhaupt veröffentlicht wurde und jetzt verfügbar ist. Blöcke können später aus verschiedenen Gründen nicht mehr verfügbar sein: Knoten, die offline gehen, Knoten, die absichtlich historische Daten löschen, und andere.
Erwähnenswertes Whitepaper zu diesem Thema ist Polyshard, das Erasure Codes verwendet, um Blöcke über Shards hinweg verfügbar zu machen, auch wenn mehrere Shards ihre Daten vollständig verlieren. Leider erfordert ihr spezifischer Ansatz, dass alle Shards Blöcke von allen anderen Shards herunterladen, was sehr teuer ist.
Zum Glück ist die Langzeitverfügbarkeit kein Problem: Da von keinem Systemteilnehmer erwartet wird, dass er alle Ketten in allen Shards validieren kann, muss die Sicherheit des geshardeten Protokolls so ausgelegt sein, dass das System sicher ist, auch wenn einige alte Blöcke in einigen Shards nicht mehr verfügbar sind.
Datenvalidität und Datenverfügbarkeit bleiben zwei Probleme beim Entwerfen sicherer Protokolle, für die noch keine zufriedenstellende Lösung gefunden wurde. Wir forschen aktiv an diesen Problemen. Bleib dabei für Updates!
Outro
Near Protocol arbeitet an einer geshardeten Allzweck-Blockchain, bei der die Benutzerfreundlichkeit im Vordergrund steht. Wenn Dir unsere Artikel gefallen, folge uns auf Twitter, um zu erfahren, wenn wir neue Inhalte veröffentlichen:
Wenn Du Dich stärker beteiligen möchtest, besuche unseren Discord-Kanal, in dem wir alle technischen und nichttechnischen Aspekte des Near Protocol wie Konsens, Wirtschaftlichkeit und Governance besprechen:
Near Protocol wird aktiv entwickelt und der Code ist Open Source. Verfolge unsere Fortschritte bei GitHub:
Zuletzt abonniere bitte unseren Newsletter. Wir senden alle zwei Wochen Updates. Dies ist der beste Kanal, um mehr über unsere Fortschritte bei der Einführung von Near Protocol zu erfahren.
.
Dieser Text wurde im Original im Englischen von Alex Skidanov verfasst und von Markus Koch ins Deutsche übersetzt.
NEAR Protocol Germany ist kein offizieller Account des NEAR Teams, sondern Teil des NEAR Ambassador Programms. Falls Du daran interessiert bist, selbst Teil dieses Programms zu werden, und zu erfahren, wie Du davon profitieren kannst, schreibe NEAR Protocol Germany oder Anaïs Urlichs hier auf Medium oder trete unserem NEAR Discord Kanal bei.
Außerdem findest Du hier alles was Du über das NEAR Ambassador Programm wissen solltest.
