Datenarchitektur der Libra Blockchain – Teil 4 – sparse merkle tree

In unserem letzten Blog-Beitrag haben wir gezeigt, wie die Libra Blockchain account adresses mit account states verknüpft und als leaf nodes im key value store speichert. Im Folgenden werden wir die Baumstruktur vorstellen, in die die leaf nodes eingehängt sind.

Wir müssen vorausschicken, dass wir uns in diesem Beitrag etwas naiv anstellen. Wir werden so tun, als ob die Anzahl Zugriffe auf den key value store und das Datenvolumen, das im key value store gespeichert wird, für den effizienten Betrieb der Libra Blockchain belanglos sind. Diesen Luxus hatten die Facebook-Ingenieure natürlich nicht. Sie haben die Baumstruktur, die wir anschliessend vorstellen werden, mit zwei Massnahmen wirkungsvoll optimiert. Darauf werden wir aber erst später in einem weiteren Blog-Beitrag eingehen.

sparse merkle tree der Libra Blockchain

Wir haben bereits früher beschrieben, dass die Libra Blockchain theoretisch eine Kapazität von 2256 account addresses hat. Eine gigantische Anzahl accounts dieser Grössenordnung wird sie selbstverständlich in der Praxis nie bewirtschaften. In der Realität wird es immer bei einem verschwindend kleinen Anteil dieser theoretischen Gesamtkapazität bleiben.

Zumindest gedanklich kann man aber alle möglichen account adresses durchnummerieren und für jede einen leaf node anlegen. Das würde etwa so aussehen:

Über den leaf nodes kann man zumindest gedanklich einen binären Baum wie folgt aufbauen:

Dieser Baum hat eine Tiefe von 256. Auf dem Weg von der Wurzel des Baums bis zu einem der leaf nodes besucht man also 256 innere Knoten und zuletzt den leaf node. Er weist zusätzlich zu den 2256 Blattknoten weitere (rund) 2256 innere Knoten auf. Bei diesen gigantischen Zahlen ist es erneut undenkbar, die inneren Knoten tatsächlich als Datenobjekte anzulegen und zu speichern.

Trotzdem baut die Libra Blockchain in ihren logischen Datenobjekten einen derartigen Baum auf. Sie legt dabei aber nur die Blattknoten und inneren Knoten an, die sie auch tatsächlich benötigt, das heisst:

Der Baum, den die Libra Blockchain bewirtschaftet ist also sehr dünn (engl: sparse) besetzt. Für den überwiegenden Teil der theoretisch vorgesehenen Knoten gibt es keine Datenobjekte in der Libra Blockchain. Sie baut diesen Baum als sogenannten Hash-Baum (oder merkle tree, nach dem Erfinder Ralph Merkle) auf. Weil der Baum so dünn besetzt ist, bezeichnet man ihn auch als sparse merkle tree.

Die inneren Knoten sind die Schlüsselelemente für einen sparse merkle tree. Schematisch besteht die Nutzlast eines inneren Knotens aus zwei Dingen:

  1. aus einem Hash-Wert für die Wurzel des linken Unterbaums

  2. aus einem Hash-Wert für die Wurzel des rechten Unterbaums

Die Libra Blockchain konvertiert einen inneren Knoten in eine rohe Byte-Sequenz, berechnet darüber erneut mit dem Standard-Hashalgorithmus SHA-3 einen Hash-Wert und speichert ihn unter diesem Hash-Wert als Schlüssel im key value store ab.

Wenn der linke oder der rechte Unterbaum leer sind, trägt sie im inneren Knoten als Hash-Wert eine vordefinierte Konstante ein. Die Bezeichnung dafür im Quellcode der Libra Blockchain ist SPARSE_MERKLE_PLACEHOLDER_HASH. Falls sowohl der linke als auch der rechte Unterbaum leer sind, legt die Libra Blockchain keinen inneren Knoten an, speichert ihn also auch nicht im key value store.

account state mit Hilfe des sparse merkle trees finden

Unseren letzten Blog-Beitrag haben wir mit der Frage beendet, wie die Libra Blockchain den account storage für eine bestimmte account address findet. Sie nutzt dazu den sparse merkle tree, den wir eben beschrieben haben. Bevor wir zeigen, wie sie dabei vorgeht, werfen wir einen zweiten Blick auf das Format der account address.

Die Hexadezimal-Darstellung einer account address haben wir bereits ausführlich verwendet. Alternativ kann man sie auch als Binärzahl darstellen, zum Beispiel so:

Wenn man die Binärdarstellung der account address um 90 Grad dreht und neben den sparse merkle tree stellt, kann sie als Wegbeschreibung durch den Baum interpretiert werden:

Steig man den Baum von der Wurzel entlang dieser Wegbeschreibung ab, erreicht man den leaf node für diese account address und dort ist der Hash-Wert eingetragen, unter dem man den account storage für diesen account im key value store findet. Falls man entlang dieses Weges in einer Sackgasse landet, falls man also einen Hash-Wert SPARSE_MERKLE_PLACEHOLDER_HASH in einem inneren Knoten erreicht, gibt es unter der account address keinen account storage.

Ausblick auf den ledger state

In unserem letzten Blog-Beitrag haben wir bereits gezeigt, dass die Libra Blockchain den account storage historisiert bewirtschaftet. Im nächsten Blog-Beitrag werden wir zeigen, dass sie ebenso den ganzen sparse merkle tree historisiert ablegt. Wir werden dann erstmals den ledger state der Libra Blockchain beschreiben können: Die Gesamtheit aller historisiert abgelegten storages aller accounts, zusammen mit allen historisiert abgelegten sparse merkle trees.