Hašový strom
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.) |