Besser Skalieren mit Wäldern aus Hash-Bäumen

Der Lightning-Miterfinder Thaddeus Dryja stellt ein Konzept vor, um einen Bitcoin-Full-Node zu betreiben, der nur einige Kilobyte an Speicher benötigt. Wir schauen uns an, was dahintersteckt. Und ja, dabei werden wir über Merkle-Bäume und das UTXO-Set reden.

Unter allen, die technisch etwas tiefer in Bitcoin eingestiegen sind, dürfte sich mittlerweile eines herumgesprochen haben: Die Skalierung einer Blockchain ist nicht ganz unproblematisch. Je nachdem, was man von einer Blockchain möchte, ist sie sogar ganz und gar unmöglich.

Oder? Thaddeus Dryja, bekannt als Ko-Autor des Lighning-Network-Papers, hat vor einiger Zeit ein interessantes Konzept vorgeschlagen, um eine Blockchain wie Bitcoin zumindest besser zu skalieren. Dryja forscht daran am MIT, wo er ein Bitcoin- bzw. Blockchain-Stipendium innehat. Sein Konzept heißt “Utreexo” und wurde vor kurzem in einem Blogpost relativ anschaulich beschrieben. Es verspricht, eine neue Art von Bitcoin Full Node einzuführen, den Compact Node, der mit einem Speicherbedarf von einigen Kilobyte, auskommt. Bisher braucht ein Full Node gut 300 Gigabyte Festplattenspeicher. Man kann zwar etwas Platz freiräumen, indem man alte Transaktionen löscht. Aber weniger als etwa 3,7 Gigabyte geht nicht. Denn dies ist die Größe des sogenannten “UTXO-Sets“: des minimalen Datenbestand eines Bitcoin-Nodes.

Das UTXO-Set ist ein wesentlicher Bestandteil von Blockchains wie von Bitcoin. Wir haben es in diesem Artikel ausführlich erklärt. Daher hier nur so viel: Das UTXO-Set ist die Summe aller Transaktionen mit einem Output, der noch nicht ausgegeben wurde. Es stellt die Menge aller Bitcoins dar, die ausgegeben werden können. Eine Transaktion ist nur dann gültig, wenn die Bitcoins in ihr Teil des UTXO-Sets sind. Daher braucht ein Knoten das gesamte UTXO-Set, um zu prüfen, ob eine Transaktion valide ist.

Und wie es aussieht, wird das UTXO-Set unvermeidlich wachsen. Daran ändern auch Skalierungs-Lösungen wie Lightning nichts: Schließlich benötigt jeder Bitcoin-User mindestens ein UTXO. Ansonsten hat er keine Bitcoins. Falls Bitcoin also weiterhin mehr Nutzer bekommt, wird das UTXO-Set weiter anschwellen.

Außer man skaliert mit Utreexo. Das verspricht nämlich, dass ein Full Node nicht mehr das gesamte UTXO-Set braucht. Stattdessen reichen ihm einige Kilobyte. Aber wie soll das gehen? Die Antwort liegt darin, dass Thaddeus Dryja dasselbe mit dem UTXO-Set macht, was Satoshi mit den Transaktionen in einem Block gemacht hat. Und damit wären wir mitten im Thema.

Merkle-Bäume

Ich weiß, das wird jetzt kompliziert. Aber wir müssen ein weiteres Konzept ins Spiel bringen: Die Merkle-Trees bzw. Hashbäume. Falls ihr noch nie davon gehört habt, wird es jetzt Zeit. Ein Merkle-Tree ist ein kryptographisches Konzept, das von dem Mathematiker Ralph Merkle erfunden wurde. Es erlaubt, die Authentizität großer Datenmengen mit einer einzigen Hash zu prüfen.

Am besten, wir beginnen mit diesem Bild hier:

Das ist ein Merkle-Tree. Die untere Reihe mit den Blöcken 01-07 sind die Hashes von Datensätzen. Etwa von Bitcoin-Transaktionen. In einem ersten Schritt werden jeweils zwei Hashes von Transaktionen verbunden und erneut gehasht. Das sind dann die Blöcke 08-11. Im nächsten Schritt werden diese Blöcke ebenfalls in Zweierpaaren verbunden und gehasht. Das geht solange weiter, bis nur noch ein einziger Hash übrig bleibt. Den nennt man die “Merkle Root”, sozusagen die Wurzel des Baumes. Mit dieser Wurzel hat man nun eine sehr kompakte Datenmenge, durch die man alle “Blätter” des Baums validieren kann.

Bei Bitcoin benutzen die Miner tatsächlich einen solchen Merkle Tree. Sie bilden aus allen Transaktionen, die in einen Block kommen, die Root. Diese nehmen sie dann zur Grundlage, um einen gültigen Blockheader zu finden. Das ist praktisch, weil man dadurch die alten Transaktionen wieder wegwerfen kann. Das erklärt Satoshi im Whitepaper:

Sobald die letzte Transaktion eines Coins unter ausreichend Blöcken begraben ist, können die verbrauchten Transaktionen davor gelöscht werden, um Speicherplatz zu sparen. Um dies zu ermöglichen, ohne den Hash des Blocks zu brechen, werden die Transaktionen in einem Merkle-Tree gehasht, und lediglich die Root in die Hash des Blocks aufgenommen. Alte Blöcke können dann komprimiert werden, indem Zweige des Baumes gekappt werden. Die internen Hashes müssen nicht gespeichert werden.

Dass Bitcoin eine Merkle Root anstatt aller Transaktionen für den Blockheader verwendet, hat noch einen weiteren Vorteil: Man kann dadurch auch Zahlungen mit sogenannten SPV-Nodes validieren. Solche Nodes haben niemals die komplette Blockchain heruntergeladen. Satoshi erklärt dies ebenfalls im Whitepaper:

Ein Nutzer muss lediglich eine Kopie der Blockheader der längsten Proof-of-Work-Kette aufbewahren, die er erhalten kann, indem er andere Netzwerk-Knoten solange abfragt, bis er überzeugt ist, dass er die längste Kette hat, und den Merkle-Zweig beziehen, der die Transaktion mit dem Block verknüpft, durch den sie einen Zeitstempel erhalten hat. Er kann die Transaktion nicht selbst prüfen, aber indem er sie mit einer Stelle in der Kette verknüpft, kann er sehen, dass sie von einem Netzwerk-Node akzeptiert wurde, und Blöcke, die danach angefügt wurden, bestätigen weiter, dass sie vom Netzwerk akzeptiert wurde.

Aber zurück zu Utreexo.

Ein Full Node mit einer einzigen Hash

Utreexo macht nämlich etwas sehr ähnliches – allerdings für das UTXO-Set. “Gegenwärtig muss ein Bitcoin Full Node alle UTXOs speichern, die es gibt,” erklärt das Blogpost,  “mit Utreexo kann man ein Full Node sein und nur die Root der UTXOs speichern.” Das sieht dann so aus:

Aus 3,3 Gigabyte UTXO wird nun also lediglich eine einzige Hash. “Alle Hashes 00 bis 13 werden weggeworfen, nachdem sie validiert wurden, und nur die 14, die Root, wird behalten.” Woher aber weiß ein Node, dass die UTXO 07 aus dem Bild oben gültig ist? Dazu muss der User, der sie ausgibt, beweisen, dass die Transaktion existiert, indem “er die Hashes 06, 07, 10 und 12 bereitstellt.”

Diese Hashes reichen aus, um die Root zu berechnen. Wenn – und nur wenn – alle beteiligten Transaktionen korrekt sind, geht die Root auf. Damit weiß ein Knoten, der lediglich die Root verifiziert hat, dass eine UTXO gültig ist.

Der Merkle-Baum ist nur eine vereinfachte Darstellung. Während bei den Bitcoin-Blöcken tatsächlich Merkle-Bäume zum Einsatz kommen, verwendet Utreexo einen sogenannten “Hash Accumulator”. Dieser baut auf einem Merkle-Baum auf, der “einen Wald von perfekten Merkle-Bäumen benutzt, und erweitert, was uns erlaubt, auf effiziente Weise Elemente zu entfernen und so die absolute Anzahl der Blätter im Wald zu reduzieren, wenn welche gelöscht werden,” erklärt das Utreexo-Whitepaper.

Aber vermutlich sind wir hier bereits zu tief in der Technologie. Anstatt der Merkle-Mathematik schauen wir uns stattdessen an, ob das Verfahren tatsächlich Sinn ergibt – und wenn ja, unter welchen Umständen und für welche Blockchains.

Sinn und Zweck der Übung

Thaddeus Dryja schlägt also “Compact Nodes” vor, die zwar ein Full Node sind, aber weder die gesamte Blockchain noch das gesamte UTXO-Set speichern, sondern lediglich eine einzige Hash: Die Root des Hash-Akkumulators aus einem Wald von Merkle-Bäumen.

Man darf sich das nicht falsch vorstellen: Ein solcher Compact Node muss, wie jeder Full Node, die gesamte Blockchain herunterladen. Es dauert unter Umständen sogar länger, wie das Medium-Post einräumt: Da der Full Node nicht nur die Transaktionen herunterladen muss, sondern noch weitere Beweise, erhöht sich die benötigte Bandbreite um 20 Prozent. Wenn Bandbreite also wie bei moderat starken Computern der Flaschenhals ist, dauert die Synchronisierung des Full Nodes länger.

Der Vorteil ist offensichtlich: Ein Full Node braucht weniger Festplattenspeicher. Dass 230 bis 300 Gigabyte oft zuviel sind, leuchtet rasch ein. Aber drei bis vier Gigabyte, wie sie ein “Pruned Node” benötigt, sind heute in der Regel kein Problem. Das passt in den Arbeitsspeicher von fast jedem PC, mehrfach auf die Festplatte jedes Smartphones, und auch auf jeden 10-Euro-Memory-Stick. Auf absehbare Zeit dürfte daraus kein Problem erwachsen.

Für normale User sind SPV- oder Light-Wallets weiterhin deutlich praktischer. Schließlich müssen sie nicht erst Tage oder Wochen synchronisieren. Im Whitepaper nennt Dryja einen etwas theoretischen Grund für seine Compact Nodes: “SPV reduziert zwar die Ressourcen, um einen Netzwerk-Knoten zu betreiben, hat aber gegenüber Full Nodes einige Schwächen in der Sicherheit und Privatsphäre. SPV-Knoten verlassen sich vollständig darauf, dass anderes Nodes die Regeln durchsetzen, weil sie das nicht selbst können.”

Wir haben hier, in gewisser Weise, einen Nachklang der alten Blocksize-Kriege, die in der Frage resultierten, ob die Miner oder Full Nodes die Hosen an haben.

Das Fundament für weitere Entwicklungen

Allerdings hat Utreexo noch weitere Vorteile. So erlaubt es etwa, mit einer einzigen Hash einen “UTXO-Snapshot” zu bilden. Ein solcher Snapshot bedeutet, dass Bitcoin sich an ein UTXO-Set zu einem bestimmten Moment erinnert, und, idealerweise, dieses zu einem Teil des Konsens macht. In dem Fall müssten neue Knoten nicht mehr die gesamte Blockchain synchronisieren, was für die Skalierung ein Jackpot wäre. Während solche Snapshots bei Bitcoin kein Thema sind, werden sie etwa bei Bitcoin Cash offen diskutiert.

Schließlich entbindet es den Konsens von der Art der Datenbank. Ein normaler Knoten prüft den Konsens des Netzwerks immer mit seiner Datenbank. Dies ist bei Bitcoin LevelDB, eine Datenbank, die zwar effizient arbeitet, aber auch anfällig für Korruptionen ist. Jeder, der schon mal ein wenig mit einem Full Node experimentiert hat, dürfte diese Erfahrung egmacht haben. Mit Utreexo kann man den Konsens auch ohne eine Datenbank validieren. Es reicht ja die kleine Root aus dem Hash-Akkumulator. Das wäre ein großer Schritt, um den Konsens zu erhalten, aber Bitcoin für andere Datenbanken zu öffnen.

Auch wenn der Sinn von Utreexo für den einzelnen User überschaubar ist, führt es doch einige neue Konzepte ein, die langfristig zum Pfeiler spannender und sinnvoller Entwicklungen werden können. Daher sollte es für Blockchain-Architekten und -Entwickler durchaus interessant sein.

Aber wie realistisch ist es, dass Utreexo es vom akademischen Whitepaper in die Bitcoin-Blockchain schafft?

Langfristig attraktiv, aber mittelfristig wenig wahrscheinlich

Das Post auf Medium sowie die Publikationen des MIT zielen klar darauf ab, Utreexo in Bitcoin zu bringen. Sie richten sich an die politischen Umstände bei Bitcoin. Das beginnt schon bei der Kernthese: Dass ein Compact-Node besser ist als ein SPV-Node, weil er auch die Regeln von Transaktionen prüfen kann. Das ist exakt die Ideologie, die bei Bitcoin als Fakt gilt.

Daneben wird Skalierbarkeit auf eine relativ eigenartige Weise verstanden. Das UTXO-Set gilt als langfristige Bedrohung für den Erhalt der Full Nodes, weshalb Utreexo helfen kann, diese trotz eines stetig wachsenden UTXO-Sets zu erhalten. Skalierung bedeutet also nicht, die Kapazität zu erhöhen, sondern die Full Nodes und damit die Dezentralisierung zu erhalten. Das Post wirbt auch damit, dass weder eine Soft- noch eine Hardfork notwendig sei, was der Tendenz bei Core entgegenkommt.

Dennoch verlangt Utreexo weitreichende Arbeit von den Core-Entwicklern. Denn das Konzept ist relativ schwierig umzusetzen. Um zu prüfen, ob eine Transaktion valide ist, braucht ein Compact Node nicht nur die Root, sondern alle Zweige, die zu dieser führen. Das werden selbst bei den “Wäldern” des Hash-Akkumulators relativ viele Daten sein. Die müsste man dann mit der Transaktion mitsenden, was eine vollkommen neue Wallet-Infrastruktur braucht, inklusive eines neu aufzubauenden Kommunikationskanals. Etwas einfacher ist die Umsetzung mit “Bridge-Nodes”, also Knoten, die darauf vorbereitet sind, den Compact-Nodes diese Informationen zu liefern. Das wäre machbar, ist aber dennoch ein ziemlich großer Aufwand. Ist das wirklich realistisch?

Vielleicht zielt das MIT daher schon bereits jetzt auch auf andere Kryptowährungen. Diese verstehen Skalierung nicht als Erhalt oder Steigerung der Full Nodes, sondern als Erhöhung der Kapazität. Und genau das ist der Punkt, bei dem Utreexo glänzt. Während die Compact Nodes eher ein Gimmick sind, das einen Full Node auf einen Computer mit einer winzigen Festplatte bringt, helfen UTXO-Snapshots sowie die dadurch mögliche Paralellisierung der Synchronisierung dabei, einen wichtigen Flaschenhals komplett zu beseitigen.

Dementsprechend ist es auch keine Bitcoin-Blockchain, die erste Schritte eingeleitet hat, um Utreexo zu implementieren. Stattdessen hat Stellar bereits die UTXO-Roots in die Blöcke gepflanzt. Allerdings ist man auch hier noch ein gutes Stück von einem konkreten Einsatz entfernt. Es wird also noch eine Weile dauern, bis Utreexo einen Einfluss auf die tatsächliche Skalierung von Blockchains haben wird. Wenn überhaupt.