Merkles Baum: 100 Bit statt 2,5 GB – so spart die Baum-Authentifizierung Speicher

From One Seed to a Thousand Leaves – Merkle's Authentication Tree

Ralph Merkle verbesserte 1979 die Lamport-Diffie-Einmalsignatur, die zu viel Speicher für öffentliche Schlüssel benötigt. Seine Baum-Authentifizierung reduziert den Speicherbedarf drastisch: Statt aller Schlüssel muss nur die Wurzel eines Hash-Baums gespeichert werden – bei 1000 Nachrichten und 1000 Nutzern sind das 100 Bit statt 2,5 GB. Der Artikel erklärt anschaulich, wie der Baum aufgebaut ist, wie Signaturen damit funktionieren und warum das Zählen von Nullen die Sicherheit erhöht.