Merkle Tree

Was ist Merkle Tree?

Merkle Tree ist eine Datenstruktur, die eine große Sammlung von Einträgen zu einem kurzen Fingerabdruck verdichtet. Sie erlaubt es, nachzuweisen, dass ein Element in einer riesigen Liste enthalten ist, indem nur wenige kleine Teile geprüft werden, nicht die ganze Liste. Stell dir einen Stammbaum vor, bei dem jeder Elternknoten eine Zusammenfassung seiner Kinder ist und alles zu einem einzigen Vorfahren führt.

Wie Merkle Tree funktioniert

Stell dir einen Block mit Zahlungen vor, der eine schnelle, verifizierbare Zusammenfassung benötigt. So funktioniert Merkle Tree in einfachen Worten:

• Schritt 1: Beginne mit einer Liste von Einträgen wie Transaktionen, jeder davon ist ein Blatt im Baum.
• Schritt 2: Verwandle jeden Eintrag in einen kurzen Fingerabdruck mit einer Hashfunktion.
• Schritt 3: Paare benachbarte Fingerabdrücke, kombiniere jedes Paar und hashe es erneut, um den übergeordneten Knoten zu erzeugen.
• Schritt 4: Wiederhole das Paaren und Hashen, bis ein einzelner oberster Fingerabdruck übrig bleibt. Das ist die Merkle Wurzel dieses Satzes.
• Schritt 5: Um zu beweisen, dass ein Element in der Menge ist, braucht man nur dieses Element plus einen kurzen Pfad von Geschwisterfingerabdrücken. Schnell und klein.

Das ist die Idee: kleine Beweise, große Sicherheit.

Warum Merkle Tree wichtig ist

Indem es große Mengen an Transaktionsdaten in einen kompakten Fingerabdruck zusammenfasst, macht Merkle Tree die Verifikation schnell und kostengünstig.

• Vorteil: Man kann die Zugehörigkeit prüfen, ohne den ganzen Block herunterzuladen, was Zeit und Bandbreite spart.
• Perspektive: Es entspricht dem aktuellen Motto im Netz: vertrauen, aber prüfen, Luxus trifft Community.
• Relevanz: Du triffst darauf in Bitcoin Blöcken, Ethereum Belegen, NFT Allowlists, Airdrops und Rollups.

Wichtige Eigenschaften von Merkle Tree

Das macht es besonders und praktisch:

• Effizienz: Beweise bleiben klein, auch wenn der Datensatz stark wächst, sodass Light Clients leicht bleiben.
• Integrität: Ändert sich ein Byte in einem Blatt, schlägt sich die Änderung bis zur Spitze durch, sodass Manipulationen offensichtlich werden.
• Root: Alles läuft auf eine einzige Merkle Wurzel hinaus, die gespeichert oder signiert werden kann für spätere Prüfungen.

Varianten

Merkle Tree hat einige gängige Varianten, auf die du stoßen wirst:

1. Binär: Der klassische paarbasierte Baum, verwendet in Bitcoin Blöcken.
2. Merkle Patricia: Ein trie basierter Ansatz für Key Value Daten, verwendet im Ethereum State und bei Belegen.
3. Sparse: Ein riesiger indexierter Baum, bei dem die meisten Blätter leer sind, geeignet für kompakte Belege für Mitgliedschaft und Nichtmitgliedschaft.
4. Verkle: Ein neuerer Verwandter mit kürzeren Beweisen bei sehr hoher Verzweigung, der für mögliche zukünftige Upgrades untersucht wird.

Beispiel

Eine Bitcoin ähnliche Light Wallet kann deine Zahlung verifizieren, indem sie einen kurzen Pfad von Hashes von deiner Transaktion bis zum Blockheader prüft, ohne die gesamte Transaktionshistorie herunterzuladen.

Interessante Tatsache

Ralph Merkle skizzierte diese Idee Ende der siebziger Jahre als Studentenprojekt, und sie blieb jahrelang in akademischen Kreisen, bevor Satoshi sie in Bitcoin nutzte. Ein Beweis dafür, dass gute Ideen lange halten.

Fazit

Fazit: Merkle Tree liefert schnelle, kleine Beweise dafür, dass etwas zu einer großen Menge gehört, ohne Aufwand und ohne große Downloads.