ハッシュ木
ハッシュ木は、単独または複数のコンピュータで保存・処理・転送される任意のデータの検証処理に利用できる。現在の主な用途としては、Peer to Peerネットワークにおいて他のピアから受信したデータブロックが破損したり改竄されたりしていないか、あるいは他のピアが偽のデータブロックを送信していないかといった検証処理が挙げられる。また、ハッシュ木をTrusted Computingで使用するという提案もなされている。具体的な利用例としては、サン・マイクロシステムズがZFSにハッシュ木を使用している。他にも、ハッシュ木はApache Waveプロトコル、分散バージョン管理システムGit、バックアップシステムTahoe-LAFS、BitcoinのPeer to Peerネットワーク、Apache CassandraおよびRiakのようなNoSQLシステムで使用されている。
ハッシュ木は1979年にラルフ・マークルによって発明された。元々の目的は大量のランポート署名を効率的に処理することであった。ランポート署名は量子コンピュータが実現してもなお安全性を保つことができると言われているが、ひとつの鍵は一つのメッセージの署名にしか使用できないという制約がある。ここで、ランポート署名をハッシュ木と組み合わせると、ひとつの鍵を複数のメッセージに対して使用できるようになり、効率的なデジタル署名スキームを構築することができる。