Datenarchitektur der Libra Blockchain – Teil 3: leaf nodes

In unserem letzten Blog-Beitrag haben wir betont, dass der account state nicht direkt unter der account address im key value store der Libra Blockchain abgelegt wird. Die Facebook-Ingenieure haben sich an das Bonmot von David Wheeler erinnert: „All problems in computer science can be solved by another level of indirection.“. Sie haben eine zusätzliche Datenstruktur eingeführt, um die account address explizit mit einem bestimmten account state zu verknüpfen.

Wir brauchen für diese Datenstruktur im Folgenden den Namen, den ihr die Libra Blockchain im Quellcode gegeben hat: leaf node (Blattknoten). Wer etwas mit Informatik-Jargon vertraut ist, wird sich sofort fragen: Blattknoten wovon? Von welchem Baum? Tatsächlich sind diese leaf nodes die Blätter einer Baumstruktur in der Libra Blockchain, aber dazu werden wir erst in einem der folgenden Blog-Beiträge kommen.

Hier beschränken wir uns darauf, welche Rolle die leaf nodes beim Speichern des account states spielen: Sie sind das entscheidende Mittel, um account states historisiert speichern zu können.

Die Libra Blockchain hat ein Elefantengedächtnis. Sie vergisst nichts. Wenn auf einem Libra account 0xABCD mit einem Libra-Saldo von 10 durch eine Transaktion beispielsweise 5 Libra eingehen, dann ersetzt die Libra Blockchain nicht einfach den bisherigen Saldo 10 mit dem neuen Saldo 15. Sie bewahrt den bisherigen account state mit dem Saldo 10 auf, legt eine Kopie davon an und ersetzt den Saldo in der Kopie mit 15. Nachdem die Transaktion ausgeführt wurde, gibt es für den account 0xABCD in der Libra Blockchain also zwei account states.

Was wir hier konkret für den Libra-Saldo eines accounts beschrieben haben, gilt für den ganzen account state. Jede Veränderung einer resource oder eines modules (resources und modules haben wir in diesem Blog-Beitrag beschrieben) wird unter einer Kopie gespeichert und der Vorgängerzustand bleibt erhalten.

Zwischen einer account address und account states gibt es also konzeptionell eine 1:n-Beziehung.

Mit einem leaf node hält die Libra Blockchain die Verbindung zwischen einer account address und einem bestimmten account state fest. Die Nutzdaten des Knotens (siehe Quellcode) bestehen aus zwei Hash-Werten: einerseits aus der account address und andererseits aus dem Hash-Wert über den serialisierten account storage.

Die Libra Blockchain speichert einen bestimmten account state nun wie folgt:

  1. Sie konvertiert den account state in eine rohe Byte-Sequenz und berechnet darüber einen Hash mit SHA-3. Anschliessend legt sie das Byte-Paket im key value store unter dem berechneten Hash als Schlüssel ab.

  2. Sie legt einen neuen leaf node an, trägt dort die account address und den berechneten Hash des account states ein, konvertiert das ganze ebenfalls in eine rohe Byte-Sequenz, berechnet darüber erneut einen Hash mit SHA-3 und legt den leaf node unter diesem Hash als Schlüssel im key value store ab.

Die folgende Abbildung zeigt diesen Ansatz schematisch.

Wenn der account state nun durch eine Transaktion verändert wird, legt sie eine Kopie an, nimmt dort die Veränderungen vor und speichert den neuen account state und einen zusätzlichen leaf node im key value store nach dem gleichen Verfahren ab. Der bereits abgelegte Vorgängerzustand zusammen mit dem bereits existierenen leaf node bleiben unverändert in key value store erhalten.

Eine Sorge bleibt: Funktioniert dieses Verfahren über die Zeit wirklich verlässlich? Falls für einen account state und einen leaf node unter unglücklichen Umständen der gleiche Hash berechnet würde, überschrieben sich die beiden im key value store wechselseitig. Die Sorgen sind aber unbegründet.

Auch ein ausgefuchster Angreifer wäre nicht in der Lage, zwei unterschiedliche account states oder leaf nodes in die Libra Blockchain einzuspeisen, die unter dem gleichen Hash im key value store kollidieren würden. Das ist die beruhigende Konsequenz aus der Tatsache, dass kryptographischen Hash-Funktionen wie SHA-3 kollisionsresistent sind.

Die Facebook-Ingenieure haben zudem weitere Massnahmen ergriffen, um alle Sorgen aus der Welt zu schaffen. Sie «salzen» namentlich einen account state und einen leaf node unterschiedlich, bevor sie den Standard-Hashalgorithmus SHA-3 anwenden. Wer einen Blick in den Quellcode wagen will: Hinweise zum «Salzen» eines account states findet man hier, zum «Salzen» eines leaf node hier.

Wir haben damit die Frage beantworten können, wie die Libra Blockchain den account state (mehrere davon) in ihrem key value store speichert. Das Ganze wirkt aber noch etwas unbefriedigend, denn: Was nützt es, account states historisiert speichern zu können, wenn man sie anschliessend nicht mehr findet? Wie kann die Libra Blockchain mit den bisher vorgestellten Datenstrukturen die Frage «Was ist der aktuelle Libra-Saldo des accounts 0xABCD?­» beantworten? Oder noch etwas anspruchsvoller: «Was war der Libra-Saldo des accounts 0xABCD vor zwei Wochen?­» .

Wenn man eine SQL-Abfrage

SELECT account_state
FROM leaf_nodes
WHERE account_address = 0xABCD

gegen den key value store absetzen könnte, würde sich die Frage kaum stellen, aber der key value store der Libra Blockchain ist keine relationale Datenbank und hat keine SQL-Schnittstelle.

Darauf werden wir in unserem nächsten Blog-Eintrag eingehen. Wir werden die Baumstruktur vorstellen, in die die leaf nodes eingehängt sind und über die die Libra Blockchain account states wiederfindet.