Merkle-Trees: Datenintegrität kryptografisch beweisen | heise online

Stellen Sie sich folgendes Szenario vor: Sie betreiben eine Plattform mit Millionen von Nutzerinnen und Nutzern. Eine Auditorin kommt mit einer konkreten Anfrage:

„Zeigen Sie mir den Nachweis, dass Sie am 15. März 2024 eine DSGVO-Einwilligung für Nutzerin #12847 erfasst haben.“

Sie wissen, dass der Datensatz existiert, er liegt in Ihrer Datenbank. Aber hier liegt das Problem: Sie können nicht einfach Ihren kompletten Datenbestand aushändigen. Dieser enthält Millionen von Einträgen mit sensiblen Kundendaten, Finanztransaktionen, Geschäftsgeheimnissen und persönlichen Informationen von Tausenden anderer Nutzerinnen und Nutzer.

Was also tun? Alles teilen geht nicht. Ein Screenshot ist nicht vertrauenswürdig, denn jeder mit grundlegenden Bildbearbeitungskenntnissen könnte den fälschen. Ein einzelner exportierter Datensatz beweist nichts, schließlich könnten Sie ihn gerade eben erst erstellt haben. Was Sie benötigen, ist eine Möglichkeit, zu beweisen, dass ein bestimmter Eintrag zu einem definierten Zeitpunkt existierte, ohne etwas anderes preiszugeben.

Das ist kein hypothetisches Problem. Es ist eine reale Herausforderung bei Audits, Compliance-Anforderungen, B2B-Verträgen oder Rechtsstreitigkeiten. Und die Lösung liegt in der Kryptografie, genauer gesagt in einer Datenstruktur namens Merkle-Tree.

Was ist ein Merkle-Tree?

Ein Merkle-Tree, benannt nach dem Informatiker Ralph Merkle, der das Konzept 1979 patentieren ließ, ist eine hierarchische Datenstruktur, die auf kryptografischen Hash-Funktionen basiert. Sie kennen Merkle-Trees vielleicht aus Bitcoin, wo sie Transaktionen verifizieren, oder aus Git, wo sie Änderungen in Ihrer Codebasis nachverfolgen.

Die Grundidee ist elegant: Aus einer beliebig großen Datenmenge wird ein einziger Fingerabdruck berechnet, der sogenannte Merkle-Root. Dieser Fingerabdruck hat eine entscheidende Eigenschaft: Ändert sich auch nur ein einziges Bit in den zugrundeliegenden Daten, ändert sich der Merkle-Root vollständig. Gleichzeitig lässt sich für jedes einzelne Element mathematisch beweisen, dass es Teil der ursprünglichen Datenmenge war, ohne die anderen Elemente offenzulegen.

Das funktioniert, weil kryptografische Hash-Funktionen eine entscheidende Eigenschaft haben: Es ist praktisch unmöglich, Daten zu fälschen, die einen bestimmten Hash erzeugen. Ändert sich auch nur ein einzelnes Bit in der Eingabe, ist der resultierende Hash komplett anders. Das macht Merkle-Trees perfekt für den Nachweis von Datenintegrität und Zugehörigkeit, ohne die Daten selbst preiszugeben.

Die Bausteine: Hashes und Baumstruktur

Schauen wir uns Schritt für Schritt an, wie das funktioniert. Und keine Sorge – Sie brauchen keine komplexe Mathematik, es geht nur um die Kernkonzepte, die Sie verstehen müssen.

Schritt 1: Jedes Element bekommt einen Hash

Jedes Datenelement in Ihrer Menge bekommt einen eindeutigen kryptografischen Hash, typischerweise mit SHA-256. Denken Sie an einen Hash wie an einen Fingerabdruck: eine Zeichenkette fester Länge, die das Element eindeutig repräsentiert. Das Ergebnis ist eine 64 Zeichen lange hexadezimale Zeichenkette.

Beispiel: Ein Datensatz könnte den Hash a3f7b2c8d4e9f1a6b5c7d8e9f0a1b2c3… erzeugen. Ändern Sie auch nur ein einziges Zeichen in den Daten, erhalten Sie einen völlig anderen Hash.

Schritt 2: Paarweise kombinieren

Jetzt kommt der clevere Teil. Wir nehmen diese Element-Hashes und organisieren sie in einer binären Baumstruktur. Nehmen Sie die ersten beiden Hashes, verketten Sie sie und hashen Sie das Ergebnis. Das ergibt einen neuen Hash, der beide Elemente repräsentiert. Machen Sie dasselbe für das nächste Paar. Dann nehmen Sie diese kombinierten Hashes und hashen sie wieder zusammen. Fahren Sie fort, bis Sie einen einzigen Hash an der Spitze haben: den Merkle-Root.

Gehen wir ein einfaches Beispiel mit vier Elementen durch: Element 1 hat Hash H1, Element 2 hat H2, Element 3 hat H3 und Element 4 hat H4. Wir kombinieren H1 und H2, hashen das Ergebnis und erhalten H12. Wir kombinieren H3 und H4, hashen das und erhalten H34. Schließlich kombinieren wir H12 und H34 und hashen sie zusammen zu H1234. Dieser finale Hash, H1234, ist Ihr Merkle-Root: ein einzelner Wert, der kryptografisch alle vier Elemente repräsentiert.

Falls Sie eine ungerade Anzahl von Elementen auf einer Ebene haben, duplizieren Sie das letzte, um Paare zu bilden. Das stellt sicher, dass Sie immer mit einem vollständigen Binärbaum und einem einzelnen Root enden.

Merkle-Proofs: Beweisen ohne Offenlegen

Nun wird es richtig interessant. Um zu beweisen, dass Element 3 Teil der ursprünglichen Datenmenge war, müssen Sie nicht alle Elemente teilen. Sie brauchen nur drei Dinge: den Hash von Element 3 (H3), die Geschwister-Hashes entlang des Pfades von Element 3 zum Root (H4 und H12) und den Merkle-Root an sich (H1234). Das war’s. Drei Hash-Werte, und Sie können die Zugehörigkeit in einer Datenmenge von potenziell Millionen von Elementen beweisen.

Jeder kann jetzt verifizieren, dass Element 3 Teil der ursprünglichen Datenmenge war: Nehmen Sie H3 und H4 (das Geschwister auf Ebene 0), hashen Sie sie zusammen, und Sie sollten H34 erhalten. Nehmen Sie dieses Ergebnis und H12 (das Geschwister auf Ebene 1), hashen Sie sie zusammen, und Sie sollten H1234 erhalten. Vergleichen Sie dieses Ergebnis mit dem bereits bekannten Merkle-Root. Stimmt es überein, ist der Beweis gültig.

Hier ist der entscheidende Punkt: Die verifizierende Person sieht nur drei Hashes. Sie erfährt nichts über Element 1, Element 2 oder Element 4. Sie kann diese Elemente nicht rekonstruieren. Sie kann nicht einmal sagen, wie viele Elemente in der Datenmenge sind. Sie weiß nur, dass Element 3 mit seinem spezifischen Hash Teil des Baums war, der diesen Merkle-Root erzeugt hat.

Den Merkle-Root veröffentlichen

Der Merkle-Root allein ist bereits wertvoll, aber er wird noch mächtiger, wenn Sie ihn veröffentlichen. Stellen Sie sich vor, es ist der 31. Dezember 2024. Sie wollen einen verifizierbaren Snapshot Ihres Datensatzes für das Jahr erstellen. Sie berechnen den Merkle-Root und veröffentlichen diesen Hash: auf Ihrer Website, in Ihrem jährlichen Transparenzbericht, in einer Blockchain-Transaktion oder in einem Certificate-Transparency-Log.

Warum? Weil Sie später, wenn Sie etwas über Ihre Daten beweisen müssen, auf diesen veröffentlichten Hash verweisen können. Sie können sagen: So sah mein Datensatz am 31. Dezember 2024 aus. Jeder kann verifizieren, dass ich ihn danach nicht verändert habe.

Jetzt ist Januar 2026. Die Auditorin fragt nach einem Beweis, dass Eintrag #12847 (die DSGVO-Einwilligung) in Ihrem Dezember-2024-Datensatz existierte. Sie generieren einen Proof, übergeben die notwendigen Daten und die Auditorin verifiziert sie. Die Auditorin prüft den veröffentlichten Merkle-Root, den Sie im Dezember 2024 gepostet haben. Stimmt er mit dem Root im Proof überein, ist der Beweis erbracht.

Die Auditorin weiß dann mit kryptografischer Sicherheit, dass Eintrag #12847 in Ihrem Datensatz vom 31. Dezember 2024 existierte und dass der Eintrag seitdem nicht verändert wurde. Aber sie hat weder den Inhalt des Eintrags erfahren (nur seinen Hash) noch irgendetwas über andere Einträge in Ihrem System.

Praktische Anwendungsfälle

Wo ist das tatsächlich nützlich? Schauen wir uns einige konkrete Szenarien an.

Compliance und Audits: Bei DSGVO und Datenschutzvorschriften ermöglichen Merkle-Proofs den Nachweis, dass Einwilligungen, Löschanfragen oder Datenverarbeitungsprotokolle zu bestimmten Zeitpunkten erfasst wurden. Sie können Compliance demonstrieren, ohne personenbezogene Daten von Nutzerinnen und Nutzern preiszugeben. Bei SOC2- und ISO-Audits können Sie zeigen, dass Sicherheitsereignisse, Zugriffsprotokolle oder Systemänderungen ordnungsgemäß aufgezeichnet wurden.

B2B-Verträge und SLAs: Der Satz „Wir garantieren, alle Transaktionen zu tracken“ wird beweisbar. Veröffentlichen Sie tägliche Merkle-Roots, die zeigen, dass Sie die komplette Transaktionshistorie pflegen, die Sie versprochen haben. Wenn eine Kundin oder ein Kunde behauptet, etwas sei passiert oder nicht passiert, liefern Sie den kryptografischen Beweis basierend auf Ihren Protokollen.

Forensik nach Datenpannen: Nach einem Sicherheitsvorfall helfen Merkle-Proofs bei der Timeline-Rekonstruktion. Sie können beweisen, welche Einträge vor dem Vorfall existierten, was entscheidend ist für forensische Analysen und um Regulierungsbehörden zu demonstrieren, dass Sie ordnungsgemäßes Logging hatten. Sie können auch Nicht-Manipulation zeigen: Ein vor dem Vorfall veröffentlichter Merkle-Root beweist den Zustand Ihrer Daten zu diesem Zeitpunkt.

Supply-Chain-Transparenz: Beweisen Sie, dass ein Produkt bestimmte Schritte in Ihrer Lieferkette durchlaufen hat, ohne Lieferantenbeziehungen, Preise oder andere wettbewerbsrelevante Details preiszugeben. Teilen Sie Nachweise über ethische Beschaffung oder Compliance-Zertifizierungen für spezifische Produkte, ohne Ihr gesamtes Lieferkettennetzwerk offenzulegen.

Geistiges Eigentum: Merkle-Proofs liefern Zeitstempelnachweise. Beweisen Sie, dass Sie eine Information hatten oder einen Entwicklungsmeilenstein zu einem konkreten Datum abgeschlossen haben. Das ist nützlich für Patent-Prior-Art-Claims oder den Nachweis von Innovationszeitplänen.

Der gemeinsame Nenner in all diesen Szenarien: Sie müssen beweisen, dass Sie bestimmte Daten haben, ohne alles andere preiszugeben. Merkle-Proofs machen das möglich.

Das Snapshot-Problem und warum Event Sourcing die Lösung ist

So praktisch und vielseitig Merkle-Trees also sind, haben sie allerdings auch eine Eigenschaft, die in der Praxis schnell zum Problem wird: Jede Änderung an den zugrundeliegenden Daten invalidiert den Merkle-Root. Das bedeutet, dass Sie für jeden Zeitpunkt, zu dem Sie etwas beweisen wollen, den kompletten Datenbestand als Snapshot aufbewahren müssen. Bei großen Datensätzen wird das schnell unpraktikabel. Wollen Sie monatliche Snapshots über mehrere Jahre? Dann speichern Sie denselben Datenbestand dutzende Male, mit minimalen Unterschieden.

Hier kommt Event Sourcing ins Spiel. Bei diesem Architekturmuster speichern Sie nicht den aktuellen Zustand, sondern die Abfolge aller Änderungen, die zu diesem Zustand geführt haben. Statt „Kunde X hat Adresse Y“ speichern Sie „Kunde X ist am 15. März an folgende Adresse umgezogen“. Der entscheidende Vorteil: Sie können den Zustand zu jedem beliebigen Zeitpunkt rekonstruieren, indem Sie die Änderungen bis zu diesem Punkt abspielen.

Für Merkle-Trees ist das ideal. Event-Streams modifizieren niemals historische Daten, sie fügen nur neue Einträge an. Sobald Sie einen Merkle-Root berechnet haben, wissen Sie, dass sich die Einträge, die er repräsentiert, niemals ändern werden. Ihre Proofs bleiben unbegrenzt gültig. Einträge in einem Event-Stream sind unveränderliche Fakten. Sie werden niemals gelöscht oder aktualisiert.

Einträge in einem Event-Stream haben außerdem eine klare chronologische Ordnung. Jeder Eintrag hat eine Position im Stream. Das macht den Merkle-Tree-Aufbau deterministisch: Jeder, der einen Baum aus denselben Einträgen baut, erhält denselben Root. Es gibt keine Mehrdeutigkeit darüber, welche Einträge wohin gehören.

Event Sourcing war schon immer gut für Auditing. Sie konnten immer Ihre Historie durchspielen, sehen, was passierte, und verstehen, wie Sie zum aktuellen Zustand kamen. Merkle-Trees gehen jedoch einen Schritt weiter: Sie machen Ihre Historie kryptografisch beweisbar. Nicht nur „hier ist, was unsere Logs sagen“, sondern „hier ist der mathematische Beweis, dass dieser Eintrag zu diesem Zeitpunkt existierte, und hier ist, wie Sie es selbst verifizieren können“.

Implementierung in der Praxis

Das Konzept eines Merkle-Tree ist relativ einfach zu implementieren. Die Kernoperationen (Hashing, Baumaufbau, Proof-Generierung und -Verifikation) lassen sich in wenigen Hundert Zeilen Code umsetzen. SHA-256 ist in praktisch jeder Programmiersprache verfügbar, und der rekursive Aufbau des Baums ist ein klassisches Informatikproblem.

Eine konkrete Implementierung des Musters findet sich beispielsweise im npm-Paket eventsourcingdb-merkle, das wir für die EventSourcingDB entwickelt haben. Das CLI-Tool demonstriert die typischen Operationen: Berechnung des Merkle-Roots für einen Datensatz, Generierung von Proofs für einzelne Elemente und Verifikation dieser Proofs ohne Zugriff auf die ursprünglichen Daten. Der Quellcode ist unter MIT-Lizenz auf GitHub verfügbar und kann als Referenz für eigene Implementierungen dienen.

Die wesentlichen Designentscheidungen bei jeder Implementierung sind: welche Hash-Funktion verwendet wird (SHA-256 ist wie bereits erwähnt der De-facto-Standard), wie mit ungeraden Elementzahlen umgegangen wird (üblicherweise durch Duplizieren des letzten Elements), und wie die Proof-Struktur serialisiert wird (JSON ist praktisch für Interoperabilität). Wichtig ist auch, dass die Reihenfolge der Elemente beim Baumaufbau konsistent ist, denn sonst erhalten Sie unterschiedliche Roots für dieselben Daten.

Weiterführende Möglichkeiten

Sobald Sie mit Merkle-Proofs arbeiten, eröffnen sich weitere interessante Möglichkeiten.

Kombination mit digitalen Signaturen: Wenn Sie Einträge zusätzlich mit Ed25519 oder einem anderen Signaturverfahren signieren, erhalten Sie zwei Garantien: Signaturen beweisen, dass der Eintrag von Ihrem System stammt und nicht manipuliert wurde. Merkle-Proofs beweisen, dass der Eintrag zum fraglichen Zeitpunkt Teil Ihres Datensatzes war. Zusammen bieten sie End-to-End kryptografische Integrität: Authentizität plus Zugehörigkeit.

Veröffentlichung auf öffentlichen Ledgern: Die Veröffentlichung auf Ihrer Website ist ein guter Anfang, aber Sie könnten den Root auch nachträglich ändern. Für maximale Beweiskraft veröffentlichen Sie Ihre Merkle-Roots auf einem öffentlichen Ledger: Eine Blockchain-Transaktion oder ein Certificate-Transparency-Log schafft einen Zeitstempel, den Sie nicht manipulieren können. Das ist aufwendiger, aber in regulierten Branchen oder bei hohen Streitwerten kann sich der Mehraufwand lohnen.

Selective Disclosure Workflows: Merkle-Proofs ermöglichen auch anspruchsvolle Szenarien mit selektiver Offenlegung. Stellen Sie sich vor: Sie sammeln Daten aus mehreren Quellen, und verschiedene Parteien dürfen unterschiedliche Teilmengen sehen. Mit Merkle-Trees geben Sie jeder Partei nur die Proofs für die Einträge, die sie sehen darf. Die Partei kann verifizieren, dass diese Einträge Teil des Gesamtdatensatzes sind, erfährt aber nichts über die restlichen Daten. Das ist besonders relevant für Multi-Mandanten-Systeme oder Datenmarktplätze.

Fazit

Merkle-Trees lösen ein konkretes Problem: Sie ermöglichen den Nachweis, dass bestimmte Daten zu einem gegebenen Zeitpunkt existierten, ohne den gesamten Datenbestand offenzulegen. Die Mathematik dahinter ist seit Jahrzehnten erprobt und bildet das Fundament von Systemen wie Git und Bitcoin.

Für Entwicklerinnen und Entwickler, die mit Audits, Compliance oder Datenintegrität zu tun haben, lohnt sich ein Blick auf diese Datenstruktur. Die Implementierung ist überschaubar, die Vorteile sind handfest: Sie können Behauptungen über Ihre Daten nicht nur aufstellen, sondern kryptografisch belegen. Und Ihre Gegenüber können diese Belege unabhängig verifizieren, ohne Ihnen vertrauen zu müssen.

(mai)