Newsticker

Ethereum, Staking und der verflixte Zufall

Roter Würfel. Bild von Steve Johnson via flickr.com. Lizenz: Creative Commons

Mit dem Umstieg auf Proof of Stake hat Ethereum eine perfekte Quelle des Zufalls verloren – die Miner. An ihrer statt soll nun die RANDAO Zufall generieren. Aber wie schafft sie dies? Und welche neuen Angriffe entstehen dabei? Wir gehen der Technik auf den Grund.

Zufall: Warum Blockchains ihn brauchen

Eine Blockchain braucht Zufall. Sie braucht Werte, die man nachweislich nicht vorhersehen kann. Wenn diese fehlen, kann die Blockchain nicht sicher sein.

Ein Beispiel ist die Auswahl der Akteure, die einen Block bilden. Bei Bitcoin sind das die Miner, bei Ethereum die Staker. Diese Auswahl muss unvorhersehbar, aber fair und transparent sein. Wenn schon im Voraus bekannt wäre, wer wann an der Reihe ist, einen Block zu produzieren, würden verschiedene Angriffe möglich: DoS-Angriffe, Bestechungen, Manipulationen und mehr. Dies wäre nicht einfach nur ein Angriffsfenster – es würde einen grundlegenden Parameter der Sicherheit herabstufen.

Die Auswahl der Miner oder Staker muss nicht nur zufällig, sondern fair und transparent sein: Die Chance, einen Block zu bilden, muss nachweislich dem entsprechen, was man an Arbeit (Hashes) oder Stake (Ether) einbringt.

All dies kann nur ein starker Zufall leisten.

Proof of Stake und Proof of Work

Bei Proof-of-Work-Blockchains wie Bitcoin bringen die Miner den Zufall ins System. Mining ist wie eine Lotterie, bei der jede produzierte Hash ein Los ist, und es ist unmöglich, vorherzusagen, welches gewinnt. Man könnte das Mining als gigantischen Zufallsgenerator beschreiben.

Anders ist es bei Proof of Stake, wie es Ethereum verwendet. Dort gibt es keine Miner, keine Hasher, keine Arbeit. Das System hat keinen natürlichen, starken, nachweisbaren Zufall aus einer externen Quelle. Aber da es ihn braucht, muss er anders geschaffen werden.

So, wie Proof of Stake das Mining quasi simuliert, muss es auch den Zufall simulieren. Und dies leistet die RANDAO.

Die RANDAO

Die RANDAO ist ein Mechanismus, durch den die Staker kollektiv und dezentral einen „Pseudozufall“ generieren. Kein computergenerierter Zufall ist perfekt, aber er ist, so die Hoffnung, ausreichend zufällig.

Daher der Name „DAO“: Die Staker bilden eine dezentrale autonome Organisation (DAO), die den Zufall schafft, den Proof of Stake nicht nativ besitzt.

Dieser „Zufall“ wird als Folge von Bits in einem bestimmten Feld in einem Block gespeichert und mit jedem neuen Block aktualisiert. Man kann sich die RANDAO wie einen Kartenstapel vorstellen, der am Tisch umgeht und den jede Person neu mischt. Im Idealfall wird der Zufall mit jdem Block zufälliger.

Der Wert der RANDAO wird schließlich zur Basis der Formel, durch die Staker auswählt werden, um die folgenden Blocke vorzuschlagen und zu validieren.

Das ist das grobe Konzept. Aber es bleiben viele Fragen ofen: Auf welche Weise generieren die Staker den Zufall? Wie sorgt man dafür, dass jedes Mitglied der RANDAO gleichwertig beiträgt – und wie beweist man, dass es wirklich Zufall ist? Wie hindert man einzelne – womöglich mächtige – Mitglieder daran, den Prozess zu ihren Gunsten zu manipulieren?

Die Antworten auf diese Fragen werden etwas technisch. Das liegt in der Natur der Sache. Aber wir versuchen, sie so anschaulich wie möglich zu beschreiben, und es müsste mit dem Teufel zugehen, wenn ihr am Ende des Textes nicht ein bißchen besser verstehen würdet, wie Ethereum funktioniert.

XOR und Hashes

Die Kernidee ist der RANDAO ist diese: Jeder ausgewählte Staker generiert eine zufällige Zahl. Die Zahlen werden dann auf eine Weise gemischt, die jedem Mitglied denselben Einfluss gibt.

Eine „Zahl“ meint hier nicht eine Zahl im strengen Sinn, sondern eine beliebige Kette von 256 Bits, also von Nullen oder Einsen.

Um die Zahlen zu verbinden, verwendet die RANDAO die XOR-Funktion. XOR – als logisches Zeichen ⊕ – addiert die Bits der einen mit der der anderen Zahl. Sind beide gleich, also 0 oder 1, ist das Ergebnis 0, sind sie unterschiedlich, ist es 1.

Ein einfaches Beispiel: Ich habe die Zahl 10 (in Bits: 1010) und verbinde sie per XOR mit der Zahl 13 (in Bits: 1101). So wird daraus 0111: sieben. XOR ist eine exzellente Methode, um Zufall zu generieren.

Die Methode ist an sich elegant, hat aber eine Schwäche: Sie ist trivial anzugreifen. Denn der letzte Teilnehmer der RANDAO, also derjenige, der den Stapel Karten als letztes mischt, kann jede ihm genehme Zahl erzeugen. Er muss nur die passende Ziffer hinzufügen. Würde ich wollen, dass anstatt der 7 (0111) am Ende die 8 steht (1000), müsste ich auf die 10 (1010) nicht die 13 (1101) setzen, sondern die 15 (1111). Das System ist beliebig zu manipulieren.

Doch dank einer kryptographischen Methode kann die RANDAO das Problem lösen.

Epochen und Blöcke

Wir müssen an der Stelle kurz etwa ausholen: Jeder Blockproduzent einer Epoche wird zum Mitglied der aktuellen RANDAO.

Eine Epoche meint bei Ethereum eine Folge von 32 Slot, die mit je einem Block besetzt werden können. Eine Epoche dauert etwa 6,4 Minuten. An ihrem Ende wird auf Basis des Zufalls entschieden, welche Staker welche Aufgaben in einer späteren Epoche zugewiesen bekommen: Die einen schlagen Blöcke vor, die anderen validieren diese. Mit unserem eben genannten Angriff könnte der letzte Blockproduzent also genau den „Zufall“ generieren, der ihm in späteren Epochen lukrative Jobs gibt.

Dies verhindert ein kryptographisches Verfahren mit BLS-Schlüsseln. Das Boneh–Lynn–Shacham-Verfahren ist eine Methode der asymetrischen Kryptographie, in der geheime und öffentliche Schlüssel korrespondieren. So wie bei PGP, mit dem man E-Mails verschlüssel und signiert, oder bei ECDSA, der Kryptographie, die eure Bitcoins schützt.

Jeder Staker ist mit einem öffentlichen BLS-Schlüssel angemeldet. Dieser öffentlichen Schlüssel ist den anderen Blockproduzenten bekannt, den zugrundeliegenden privaten Schlüssel hält er geheim.

Um eine zufällige Zahl zu generieren, signiert der Produzent eines Blocks nun eine bestimmte Zahl mit seinem geheimen Schlüssel. Diese Zahl ist nicht zufällig: Sie muss die Nummer der aktuellen Epoche sein. Die Signatur setzt er dann in das „reveal_randao“-Feld in seinem Block.

Die Methode erfüllt alle Voraussetzungen: Da niemand anderes den privaten Schlüssel kennt, kann niemand diesen Wert vorausahnen. Er ist also unvorhersehbar. Da aber jeder die Epochennummer und den öffentlichen Schlüssel kennt, kann jeder prüfen, ob der Wert korrekt ist. Da es schließlich nur einen gültigen Wert gibt, kann man ihn nicht manipulieren.

Danach bindet der Blockproduzent die Hash dieser Signatur in den RANDAO-Status der Beacon-Chain durch XOR ein. So fügt jeder Blockproduzent diesem Status ein Stückchen Zufall hinzu. Am Ende der Epoche wird der RANDAO-Status konsensrelevant aktualisiert und dafür genutzt, um die Validatoren für die folgenden Epochen auszuwählen.

Eine Schwäche bleibt allerdings

Das Verfahren ist ziemlich elegant. Es schafft mit geringem Aufwand einen Mechanismus, um einen starken und verifizierbaren Zufallswert zu generieren, der nicht manipulierbar ist.

Zumindest fast. Denn es bliebt eine Art von Angriff: Jemand kann einen Block zurückhalten. Denn ein Slot kann auch leer bleiben; eine Epoche hat zwar 32 Slots, kann aber weniger Blöcke beinhalten.

Wenn jemand nun eine Epoche abschließt, kann er sich entscheiden, den Block mit der entsprechenden Nummer zu veröffentlichen – oder es zu lassen. Er kann also zwischen zwei Möglichkeiten wählen, wie der RANDAO-Wert am Ende einer Epoche aussieht, und sich für die entscheiden, die seinen maliziösen Absichten am besten dient.

Wenn ein Staker gar die letzten beiden Blöcke einer Epoche bildet, hat er vier Optionen. Bei den letzten drei Blöcken acht, und so weiter.

Die Ethereum-Entwickler wissen um diese Schwäche der RANDAO. Sie sagen aber, dass dies kein grundsätzliches Problem ist, da sie weiterhin sicher genug sei.

Aber ist dem so? Wir schauen uns dafür den konkreten Angriff an.

Ein Vorteil für die nächsten Epochen

Ein Angreifer, der den letzten Block einer Epoche findet, kann also zwischen zwei abschließenden RANDAO-Werten wählen.

Da der RANDAO-Wert in die Gleichung einfließt, die die Aufgaben der folgenden Epochen verteilt, kann dies ein enormer Vorteil sein. Ein Angreifer kann kalkulieren, welche der beiden Optionen ihm mehr Aufgaben einbringen, wodurch er mehr Einfluss ausüben kann, als ihm durch sein Stake zustehen sollte.

In der Analogie des Kartenspiels: Er kann zwei Karten vom Stapel ziehen und eine wieder zurücklegen. Wenn er die letzten beiden Blöcke erhält, kann er sogar zwischen vier Karten auswählen. Ein ziemlich mächtiger Vorteil.

An sich wäre das nicht so schlimm. Jeder landet mal am Ende eines Slots, daher bleiben die Bedingungen für alle gleich. Allerdings bevorteiligt der Angriff Akteure mit einer größeren Staking-Rate: Wer mehr Ether staked, hat nicht nur die ihm zustehende größere Chance, einen Block zu produzieren – er hat auch die ihm eigentlich nicht zustehende Chance, einen Vorteil bei der Vergabe der nächsten Plätze in der Epoche zu erlangen.

Dieser kleine Vorteil verschiebt das Gleichgewicht des Zufalls ein Stück zugunsten der stärkeren Akteure, etwa der großen Pools, wie Lido, Coinbase oder Binance. Er erinnert damit ein wenig an den „Selfish-Minig“-Angriff, mit dem sich Bitcoin-Miner schon ab etwa 33 Prozent der Hashrate einen Vorteil verschaffen können.

Der Wissenschaftler Emin Gün Sirer entdeckte den Angriff 2013. Mathematisch gesehen ist er valide, doch was darauf folgt, ist unklar. Sirer behauptete, Bitcoin damit widerlegt zu haben. Doch Bitcoin lebt fort, obwohl das Problem nie repariert wurde.

Ist es mit dem Angriff auf die RANDAO genauso? Ist sie mathematisch valide, aber in der Praxis unbedeutend?

Der Übernahme-Angriff

Bisher ist kein Angriff auf die RANDAO bekannt. Man kann also nicht sagen, dass sie unsicher sei. Aber man kann auch nicht sagen, dass sie sicher sei. Dafür ist es noch zu früh.

Man kann lediglich die Zahlen zur Kenntnis nehmen. Wie groß ist der Vorteil für wen? Welchen Vorteil hat etwa Lido, der größte Pool, der knapp 30 Prozent der Stakes auf sich vereint?

Die Mathematik ist nicht ganz trivial. Ben Edgington bringt sie im ausgezeichneten ETH2book auf die folgende Fragestellung: Wenn man eine bestimmte Anzahl an Slots am Ende der Epoche erhält – wie viele Slots wird man dann am Ende der nächsten Epoche haben? Kann man sich auf diese Weise einen immer größeren, im Laufe der Zeit sukzessive anschwellenden Vorteil verschaffen, bis man schließlich die ganze RANDAO – und damit Ethereum – übernommen hat?

Im ersten Schritt muss man errechnet, wie viele Slot am Ende einer Epoche jemand mit einem bestimmten Anteil des Stakes erwartungsgemäß bekommt.

Ben kalkuliert dies durch eine Formel und leitet aus ihr diese Kurve ab:

Im zweiten Schritt rechnet er die Anzahl zu erwartender Slots am Ende der folgenden Epoche aus. Er nennt dies die „Länge des Tails“. Wie hoch ist die Chance, dass der Tail ebenso lang sein wird? Und wie bei den Epochen danach?

Die Mathematik ist erneut alles andere als einfach. Nach vielen Formeln, Tabellen und Kurven kommt Ben schließlich bei dieser Kurve raus:

Was bedeutet das? Wer weniger als 50 Prozent der Stakes kontrolliert, wird in der folgenden Epoche mit sehr großer Wahrscheinlichkeit weniger abschließende Slots bekommen als in der aktuellen. Das Tail schrumpft. Er „kann nicht erwarten, auf der Leiter […] nach oben zu klettern.“ Solange ein Pool keine 50 Prozent auf sich vereint, wird er die RANDAO also nicht übernehmen können.

Wenn der Angreifer dagegen mehr als 50 Prozent der Stakes besitzt, gelingt der Angriff mit großer Wahrscheinlichkeit. Er wird mit jeder Epoche mehr abschließende Slots ergattern, bis er schließlich alle Slots gewinnt.

Dies entspricht dem 51-Prozent-Angriff, den Satoshi schon im Bitcoin-Whitepaper beschrieben hat. Der Angriff ist zwar inhaltlich und in seinen Konsequenzen anders. Aber die Sicherheit der RANDAO basiert auf der exakt selben Annahme wie bei Bitcoin: dass ein Angreifer niemals mehr als 50 Prozent der Hashes (oder Stakes) akumuliert.

Der breite Konsens ist, dass es niemals soweit kommen soll und kann. Man könnte dies die „Nakamoto-These“ nennen. Sie ist das Fundament, auf dem das gesamte Ökosystem der Kryptowährungen erbaut wurde.

Der Staking-Turbo

Aber was, wenn ein Angreifer gar nicht so viel möchte? Es wäre irrational, mehr als 50 Prozent der gestakten Ether zu akumulieren, nur um dann das System – und damit den Wert der Ether – kaputt zu machen.

Die Anreize, keinen 51-Prozent-Angriff zu fahren, obwohl man in der Lage dazu ist, sind bei Ethereum sehr viel stärker als bei Bitcoin. Dort zerstört man potenziell ein paar künftige Mining-Erträge – hier Ether im Wert vieler Milliarden Euro (aktell etwa 75 Milliarden).

Rational hingegen wäre es, wenn ein Angreifer die Schwäche ausnutzt, um sich höhere Erträge zu erschwindeln: Also mehr Blöcke zu bilden, als ihm eigentlich zustehen. Er würde nicht das Spielbrett umwerfen, aber sich selbst einen Vorteil erschummeln.

Es ist relativ offensichtlich, dass dies möglich sein sollte. Aber wie bedrohlich ist es? Wird es zur Zentralisierung führen, weil man den Starken gibt und den Schwachen nimmt?

Ben Ardington berechnet die Effektivität des Angriffs auf Basis der schon vorher gewonnen Formeln. Er kommt dabei zu dieser Kurve:

Deutlicher zeigt diese Kurve die Vorteile, die sich große Staker verschaffen können:

Große Staking-Pools können also maximal 3,5 Prozent mehr Erträge erwirtschaften, als ihnen durch ihr Stake zusteht. Bei Lido dürften es bei der derzeitigen Rate knapp drei Prozent sein. Da der Vorteil desto größer wird, je weiter sich ein Pool der 50-Prozent-Marke nähert, könnte dies einen gewissen Druck dahin erzeugen, dass ein Pool diese erreicht – und dann den oben beschrieben Angriff fährt.

Ein Paper der Universität von Illinois kommt allerdings zu etwas anderen Zahlen: Die Wissenschaftler errechnen einen Vorteil von etwa 20 Prozent auf den Ertrag. Das wäre ein deutlich größerer Vorteil.

Allerdings gewinnen die Forscher die Werte durch eine Simulation in einem Modell. „Sie scheinen,“ kommentiert Ben, „nur 10 Slots je Epoche zu verwenden und gehen von einem sehr kleinen Set an Validatoren aus. Vermutlich eine Vereinfachung, damit die Simulation laufen kann.“

Seine eigene Analyse geht von den 32 Slots je Epoche aus, die es bei Ethereum eben gibt, und von einer zufälligen, aber großen Anzahl an Validatoren, beinahe eine halbe Million. „Ich nehme an, dass dies die Quelle der Diskrepanz ist, aber es ist schwierig, sich sicher zu sein.“

Sein Fazit bleibt unberührt: „Wennn ein Angreifer weniger als 50 Prozent der Validatoren kontrolliert, ist die RANDAO in Ordnung. Wenn ein Angriefer mehr als 50 Prozent der Validatoren besitzt, müssen wir über schlimmere Probleme sorgen.“


Anmerkung: Ben Edgington war eine unschätzbare Hilfe beim Verfassen dieses Artikels. Er hat mir mit großer Geduld und Kompetenz die vielen Fragen beantwortet, die während meiner Recherche entstanden sind, und mir dabei enorm geholfen, nicht nur die RANDAO, sondern auch Ethereum zu verstehen.

Über Christoph Bergmann (2443 Artikel)
Das Bitcoinblog wird von Bitcoin.de gesponsort, ist inhaltlich aber unabhängig und gibt die Meinung des Redakteurs Christoph Bergmann wieder ---

2 Kommentare zu Ethereum, Staking und der verflixte Zufall

  1. Sehr informativ. Vielen Dank für Deine ganzen Recherche-Bemühungen und vielen Dank an Ben Edgington. Es ist einfach schön zu sehen, wie Open Source es immer wieder ermöglicht, auch unabhängigen Beobachtern Einblick in die internen Abläufe zu geben. 🙂

  2. Cool Dankeschön. Es ist schon faszinierend wie viel Mathematik dahinter steht. Ethereum ist aber mehr als nur eine Währung und das finde ich auch spannend.

Kommentar verfassen

%d Bloggern gefällt das: