Datenarchitektur der Libra Blockchain – Teil 6 – extension node

In unseren bisherigen Beiträgen zur Datenarchitektur der Libra Blockchain haben wir unsere Leser wiederholt mit dem Hinweis «Wir werden darauf zurückkommen ...» auf später vertröstet. In diesem Blog-Eintrag nehmen wir einen dieser Fäden wieder auf. Wir werden auf eine der beiden Optimierungsmassnahmen in der Datenarchitektur des ledger states eingehen.

Wir haben bereits gesehen, dass die Libra Blockchain die Knoten des sparse merkle trees eines ledger states im key value store speichert. Ein sparse merkle tree ist dünn belegt. Nur ein verschwindend kleiner Anteil aller denkbaren accounts existieren tatsächlich jemals in der Libra Blockchain. Damit legt sie auch nur einen verschwindend kleinen Anteil der theoretisch möglichen inneren Knoten und leaf nodes an. Entsprechend kann man über diese gespeicherten Knoten nur einen Bruchteil aller Pfade durch den Baum verfolgen.

Als Konsequenz bieten Pfade von der Wurzel zu einem leaf node oft keine Möglichkeit zum Abzweigen, oder zumindest bestehen sie aus einzelnen Segmenten, in denen es keine Möglichkeit zum Abzweigen gibt.

Im allerersten ledger state der Libra Blockchain sieht man deutlich, was damit gemeint ist. Er entstand als Ergebnis der ersten Transaktion, die den account 0x00 angelegt hat. Er setzt sich aus einem account state, einem leaf node und einem einzigen Pfad mit 256 inneren Knoten im sparse merkle tree zusammen. Diese inneren Knoten bilden einen Pfad ohne Abzweigungsmöglichkeiten. Bei jedem der inneren Knoten kann man in diesem Beispiel nur den linken Ast hinuntersteigen. Der rechte Ast ist eine Sackgasse, weil der rechte Unterbaum (noch) leer ist.

Die Libra Blockchain rollt Folgen von inneren Knoten ohne Verzweigungsmöglichkeit auf, fasst sie in einem speziellen neuen Knoten zusammen und speichert die ganze Sequenz als ein einziges Schlüssel/Wert-Paar im key value store ab. Sie bezeichnet diese Art von inneren Knoten als extension node (bzw. ExtensionNode im Quellcode der Libra Blockchain).

Statt 256 Schlüssel/Wert-Paare für innere Knoten speichert sie in unserem Beispiel nur ein Schlüssel/Wert-Paar mit den serialisierten Nutzdaten des extension nodes.

Die Nutzdaten eines extension nodes sind wesentlicher kompakter als die Nutzdaten der einzelnen inneren Knoten, die sie zusammenfasst! Sie umfassen nur einen Hash-Wert: den Hash-Wert des nächsten inneren Knotens oder leaf nodes, zu dem der Pfad führt. Zusätzlich enthalten sie eine Bit-Folge als Wegbeschreibung für den aufgerollten Pfad. Der Quellcode der Libra Blockchain bezeichnet diese Wegbeschreibung als NibblePath.

Die Hash-Werte der inneren Knoten des zusammengerollten Pfades muss die Libra Blockchain nicht abspeichern. Der Hash-Wert des Folge-Knotens und die Wegbeschreibung reichen als Grundlage, um die Sequenz der Hash-Werte zu berechnen,die letztlich zum Hash-Wert des extension nodes führen.

Die Facebook-Ingenieure haben diese Technik von ihren Kollegen der Schwester-Blockchain ethereum übernommen. Dort ist der gleiche Ansatz bereits seit einiger Zeit im Einsatz und im Anhang D des berüchtigten – caution! math ahead!Ethereum Yellow Papers beschrieben.