Ein VERKLE -Baum ist ein Verpflichtungsschema, das ähnlich einem Merkle -Baum funktioniert, aber viel kleinere Zeugen hat. Es ersetzt die Hashes in einem Merkle -Baum durch ein Vektor -Engagement, was breitere Verzweigungsfaktoren effizienter macht.
Vielen Dank an Kevaundray Wedderburn für Feedback zum Post.
Überblick
Details darüber, wie Kenkelbäume funktionieren, siehe:
Das Ziel dieses Beitrags ist es, das konkrete Layout der zu erklären Der Entwurf schließt Baum EIP. Es richtet sich an Kundenentwickler, die VERKLE -Bäume implementieren möchten und nach einer Einführung suchen, bevor sie tiefer in den EIP eintauchen.
VERKLE -Bäume führen eine Reihe von Änderungen an der Baumstruktur ein. Die bedeutendsten Änderungen sind:
- ein Schalter von 20 Byte -Schlüssel zu 32 Byteschlüssel (nicht mit 32 Byte -Adressen zu verwechseln, was eine separate Änderung ist);
- die Verschmelzung des Kontos und der Speicherversuche; und schließlich
- Die Einführung des Querle -Trie selbst, der Vektorverpflichtungen anstelle von Hashes verwendet.
Als Vektor -Verpflichtungsschema für den Leerkle -Baum verwenden wir Pedersen -Verpflichtungen. Pedersen -Verpflichtungen basieren auf elliptischen Kurven. Für eine Einführung in Pedersen -Verpflichtungen und zur Verwendung von polynomialen oder vektorischen Verpflichtungen unter Verwendung innerer Produktargumente siehe Hier.
Die Kurve, die wir verwenden, ist Bandersnatch. Diese Kurve wurde ausgewählt, weil sie leistungsfähig ist, und auch, weil sie in Zukunft effiziente Schnuppen in BLS12_381 ermöglicht. Dies kann für Rollups nützlich sein und ein Upgrade ermöglichen, bei dem alle Zeugen in einem Snark komprimiert werden können, sobald dies praktisch wird, ohne ein weiteres Engagement -Update zu benötigen.
Die Kurvenreihenfolge/Skalarfeldgröße von Bandersnatch ist P = 1310896879378154761986193512704649145930915589340570251786403306729687672801das ist ein 253 -Bit -Prime. Infolgedessen können wir uns nur sicher zu Bit -Saiten von höchstens 252 Bits verpflichten, ansonsten überläuft das Feld. Wir haben einen Verzweigungsfaktor (Breite) von 256 für den Leerzeichen ausgewählt, was bedeutet p – 1). Wir schreiben das als Commit (v₀, v₁, …, v₂₅₅) sich auf die Liste festlegen v von Länge 256.
Layout des Kenkelbaums
Eines der Konstruktionsziele mit dem EIP von Shle Tree Tree ist es, Zugriff auf benachbarte Positionen (z. Dazu besteht ein Schlüssel aus a Stängel von 31 Bytes und a Suffix von einem Byte für insgesamt 32 Bytes. Das Schlüsselschema ist so konzipiert, dass “enge” Speicherorte auf denselben Stamm und ein anderes Suffix abgebildet sind. Für Details finden Sie bitte die EIP -Entwurf.
Der VERKLE -Baum selbst besteht dann aus zwei Arten von Knoten:
- Verlängerungsknotendie 256 Werte mit demselben Stamm, aber unterschiedlichen Suffixen darstellen
- Innere KnotenDas haben bis zu 256 Kinder, die entweder andere innere Knoten oder Erweiterungsknoten sein können.
Das Engagement für einen Erweiterungsknoten ist eine Verpflichtung zu einem 4 -Elementvektor; Die verbleibenden Positionen sind 0. Es ist: es ist:
C₁ und C₂ sind zwei weitere Verpflichtungen, die sich auf alle Werte mit Stamm verpflichten Stängel. Der Grund, warum wir zwei Verpflichtungen brauchen, ist, dass Werte 32 Bytes haben, aber wir können nur 252 Bit pro Feldelement speichern. Eine einzige Verpflichtung würde daher nicht ausreichen, um 256 Werte zu speichern. Stattdessen speichert C₁ die Werte für Suffix 0 bis 127 und C₂ 128 bis 255, wobei die Werte in zwei aufgeteilt werden, um in die Feldgröße zu passen (wir werden später dazu kommen.)
Die Erweiterung zusammen mit den Verpflichtungen C₁ und C₂ wird als “Erweiterungs- und Suffixbaum” (kurz) bezeichnet.
Abbildung 1 Darstellung eines Spaziergangs durch einen Perkle -Baum für den Schlüssel 0xfe0002abcd..FF04: Der Pfad durchläuft 3 interne Knoten mit jeweils 256 Kindern (254, 0, 2), einem Erweiterungsknoten, der darstellt ABCD..FF und die beiden Suffix -Baum -Verpflichtungen, einschließlich des Wertes für 04v₄. Beachten Sie, dass Stängel ist eigentlich die ersten 31 Bytes des Schlüssels, einschließlich des Pfades durch die internen Knoten.
Verpflichtung zu den Wertenblattknoten
Jede Erweiterungs- und Suffix -Baumknoten enthält 256 Werte. Da ein Wert 256 Bit breit ist und wir nur 252 Bit in einem Feldelement sicher speichern können, würden vier Bit verloren gehen, wenn wir es einfach versuchen, einen Wert in einem Feldelement zu speichern.
Um dieses Problem zu umgehen, haben wir uns entschieden, die Gruppe von 256 Werten in zwei Gruppen von jeweils 128 Werten zu unterteilen. Jeder 32-Byte-Wert in einer Gruppe wird in zwei 16-Byte-Werte aufgeteilt. Ein Wert vᵢ∈ 𝔹₃₂ wird also in v⁽ˡᵒʷᵉʳ⁾ᵢ ∈ 𝔹₁₆ und v⁽ᵘᵖᵖᵉʳ⁾ᵢ∈ 𝔹₁₆ umgewandelt, so dass v⁽ˡᵒʷᵉʳ⁾ᵢ ++ v⁽ᵘᵖᵖᵉʳ⁾ᵢ = vᵢ.
Der V⁽ˡᵒʷᵉʳ⁾ᵢ wird ein “Blattmarker” hinzugefügt, um zwischen einem Blatt zu unterscheiden, auf das nie zugegriffen wurde, und einem Blatt, das mit 0s überschrieben wurde. Kein Wert wird jemals von einem Perkle -Baum gelöscht. Dies ist für die kommenden staatlichen Ablaufschemata erforderlich. Dieser Marker ist auf das 129. Bit eingestellt, dh v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = v⁽ˡᵒʷᵉʳ⁾ᵢ + 2¹²⁸, wenn Vᵢ zuvor zugegriffen wurde, und V⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = 0, wenn nie auf Vᵢ zugegriffen wurde.
Die beiden Verpflichtungen C₁ und C₂ werden dann definiert als
Engagement von Erweiterungsknoten
Die Verpflichtung zu einem Erweiterungsknoten besteht aus einem “Erweiterungsmarker”, der nur die Nummer 1, die beiden Subtree -Verpflichtungen C₁ und C₂ und die ist Stängel des Schlüssels, der zu diesem Erweiterungsknoten führt.
Im Gegensatz zu Erweiterungsknoten im Merkle-Patricia-Baum, der nur den Abschnitt des Schlüssels enthält, der den internen Knoten des Elternteils zum untergeordneten internen Knoten überbrückt, deckt der Stamm bis zu diesem Punkt den gesamten Schlüssel ab. Dies liegt daran, dass Perkle -Bäume mit staatsloser Beweise ausgelegt sind: Wenn ein neuer Schlüssel eingefügt wird, der die Erweiterung in zwei Teile “spaltet”, muss das ältere Geschwister nicht aktualisiert werden, was einen kleineren Beweis ermöglicht.
Verpflichtung interner Knoten
Interne Knoten haben die einfachere Berechnungsmethode für ihre Verpflichtungen: Der Knoten wird als Vektor von 256 Werten angesehen, nämlich die (Felddarstellung der) Wurzel -Verpflichtung jeder ihrer 256 Teilbäume. Die Verpflichtung für einen leeren Subtree beträgt 0. Wenn der Unterbaum nicht leer ist, ist die Verpflichtung für den internen Knoten
Wo die Cᵢ die Kinder des internen Knotens sind und 0, wenn ein Kind leer ist.
Einfügen in den Baum
Abbildung 2 ist ein Beispiel für den Prozess des Einfügens eines neuen Wertes in den Baum, der interessant wird, wenn die Stängel auf mehreren Anfangs Bytes kollidieren.
Abbildung 2 Der Wert V₁₉₂ wird am Standort eingefügt 0000010000 … 0000 In einem marga -Baum mit nur Wert V₁₂₇ am Standort enthalten 0000000000 … 0000. Da sich die Stängel am dritten Byte unterscheiden, werden zwei interne Knoten bis zum unterschiedlichen Byte hinzugefügt. Dann wird ein weiterer “Extension-and-Suffix” -Baum mit einem vollen 31-Byte-Stamm eingefügt. Der anfängliche Knoten ist unberührt und c²₀ hat den gleichen Wert wie C⁰₀ vor der Einfügung.
Flachere Bäume, kleinere Nachweise
Die VERKLE -Baumstruktur sorgt für flachere Bäume, wodurch die Menge der gespeicherten Daten reduziert wird. Seine wirkliche Macht beruht jedoch auf der Fähigkeit, kleinere Beweise zu erstellen, dh Zeugen. Dies wird im nächsten Artikel erklärt.
