Zum Inhalt springen
ecdsa.com

Merkle-Baum

Ein binärer Hash-Baum, in dem jeder innere Knoten den Hash seiner beiden Kindknoten bildet, sodass ein einziger Root-Hash alle Blätter festschreibt und sich die Zugehörigkeit eines Eintrags oder ein Wachstum nur durch Anhängen mit Beweisen logarithmischer Größe nachweisen lässt.
Auch geschrieben alshash treeMerkle rootinclusion proofconsistency proof

Certificate Transparency (RFC 6962 §2.1, RFC 9162 §2.1) legt das Hashing fest, das die meisten Transparenzlogs verwenden: Blätter sind SHA-256(0x00 ‖ data) und Knoten SHA-256(0x01 ‖ left ‖ right); die Präfixe verhindern, dass ein Blatt als innerer Knoten ausgegeben wird. Ein Inclusion-Proof für einen Eintrag unter einer Million braucht etwa 20 Hashes; ein Consistency-Proof zeigt, dass ein neuerer Baum einen älteren erweitert, ohne die Historie umzuschreiben.

Auf dieser Struktur beruhen CT-Logs, Rekor von Sigstore, die Prüfsummendatenbank von Go (sum.golang.org), die Transaktionswurzel von Bitcoin (mit einer anderen Konstruktion aus doppeltem SHA-256 und einer bekannten Eigenheit bei duplizierten Blättern), Git und die meisten inhaltsadressierten Speicher sowie die hashbasierten Signaturen XMSS, LMS und SLH-DSA.

Transparenzlogs veröffentlichen signierte Tree Heads (Checkpoints), die Zeugen (Witnesses) mitsignieren; so fällt ein Log auf, das verschiedenen Clients unterschiedliche Historien zeigt.

Standards und Quellen

Alle Begriffe