Hašový strom

Příklad hašového stromu

Hašový strom neboli Merkleův strom je datová struktura používaná v kryptografii a informatice. Jedná se o strom, který má v listech data a ve všech ostatních vrcholech má hodnotu odpovídající výsledku kryptografické hašovací funkce, která na vstup dostane hodnotu dat v dětech. Na rozdíl od jednodušších lineárních seznamů hašů nebo hašových řetězců je u hašového stromu možné ověřit integritu listu v logaritmickém čase vzhledem k počtu datových uzlů.

Hašové stromy vymyslel v roce 1979 Ralph Merkle původně proto, aby jimi rozšířil Lamportovo podpisové schéma, čímž vytvořil Merkleovo podpisové schéma.

Použití hašovavých stromů pro zajištění integrity je poměrné pestré, používají je například souborové systémy Btrfs, ZFS a IPFS, verzovací systém Git a kryptoměny Bitcoin a Ethereum.

Reference

V tomto článku byly použity překlady textů z článků Hash-baum na německé Wikipedii a Merkle tree na anglické Wikipedii.