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.

Stromové datové struktury
Vyhledávací stromy
(dynamické množiny/ asociativní pole)
2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • Bx • (Optimální) Binární vyhledávací • Dancing • HTree • Intervalový • Stromy s pořadím (Order statistic) • (Doleva převážený) Červeno-černý • Scapegoat • Splay • T • Treap • UB • Váhově vyvážený (tj. BB[α])
Haldy
Binární • Binomiální • Brodal • Fibonacciho • Leftist • Pairing • Skew • Van Emde Boasův strom • Slabá
Trie
Ctrie • C-trie • Hašovací • Komprimovaná trie (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast
Prostorové indexační stromy
Ball • BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • PH • Prioritní R • Čtyřstrom (Quadtree) • R • R+ • R* • Segmentový • VP (vantage-point) • X
Jiné stromy
Strom pokrytí • Obousměrně provázaný (Doubly chained tree) • Exponenciální • Fenwickův • (Binární) Strom s prstem • Fraktálový indexový • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný spojovací • Hašový Merkleův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom)
Kategorie:Stromy (dat. strukt.)