Merkle-Baum

Um zu belegen, dass ein Datenelement zur Menge gehört, genügt ein Inklusionsnachweis (Merkle Proof): die minimale Menge der Geschwister-Hashes entlang des Pfads vom Blatt bis zur Wurzel. Der Prüfer berechnet die Hashes bis zur Wurzel neu und vergleicht, mit logarithmischem Aufwand in der Größenordnung von log n Hashes für n Elemente, ohne die vollständige Menge zu benötigen. Das Konzept stammt von Ralph Merkle, der es in seiner Patentanmeldung von 1979 zu digitalen Signaturen schützen ließ, und beruht vollständig auf kryptografischen Hashfunktionen.

Es ist eine grundlegende Struktur der Blockchain-Technologie: Sie erlaubt es, Integrität und Zugehörigkeit großer Datenmengen mit minimalen Daten zu verifizieren. Sie ermöglicht Light Clients (SPV), die eine Transaktion gegen die Wurzel des Blocks prüfen, ohne den gesamten Block herunterzuladen, was entscheidend ist, damit auch leistungsschwache Geräte dem Netzwerk vertrauen können.

In Bitcoin speichert jeder Blockheader die Merkle-Wurzel seiner Transaktionen, und SPV-Nodes verwenden Merkle Proofs. Ethereum nutzt eine Variante, den Merkle-Patricia-Trie, für Zustand, Transaktionen und Receipts. Viele Airdrops, etwa die von Uniswap (UNI) oder Optimism (OP), hinterlegen die Berechtigungsliste als Merkle-Wurzel, und jeder Nutzer beansprucht seine Zuteilung mit seinem Inklusionsnachweis. Der Merkle-Baum ist außerdem die interne Commitment-Struktur der zk-STARKs und eine gängige Grundlage für Zugehörigkeitsnachweise in zk-SNARKs.