Obsah
Koncept hashového (Merkleova) stromu předložil začátkem 80. let Ralph Merkle – informatik, který proslul svou prací na
asymetrické kryptografii (kryptografii s veřejným klíčem).
Hashový strom je struktura, kterou je možné efektivně ověřit integritu nějaké sady dat. To je obzvlášť zajímavé v kontextu
peer-to-peer sítí, kde účastníci potřebují sdílet informace a nezávisle je ověřovat.
V jádru struktur hashovacího stromu jsou hashovací funkce, takže než budete pokračovat, doporučujeme vám přečíst si článek o tom,
Co je hashování.
Předpokládejme, že chcete stáhnout velký soubor. U
softwaru s otevřeným zdrojovým kódem budete chtít pravděpodobně ověřit, že hash staženého souboru odpovídá hashi, který zveřejnili vývojáři. Pokud tomu tak je, můžete si být jistí, že soubor ve vašem počítači je naprosto stejný jako ten jejich.
Pokud hashe shodné nejsou, máte problém. Buď jste si stáhli soubor se škodlivým kódem, který se za váš software jen vydává, nebo se soubor nestáhl správně a nebude fungovat. Ten druhý případ vás pravděpodobně moc nepotěší, protože jste museli nějakou dobu čekat, než se soubor stáhne. Teď ho budete muset stáhnout znovu a doufat, že nebude opět poškozený.
Asi si říkáte: „Kdyby tak existoval jednodušší způsob, jak to udělat“. A od toho tu jsou naštěstí hashovací stromy. Jedním takovým stromem můžete soubor rozdělit na bloky dat. Kdybyste měli 50GB soubor, mohli byste ho rozdělit na 100 bloků, takže každý z nich by měl 0,5 GB. Pak byste ho blok po bloku stáhli. Tak v podstatě funguje stahování přes torrenty.
V tomto případě by vám zdroj poskytl hash známý jako Merkleový kořenový hash. Tento jediný hash představuje všechny bloky dat, ze kterých se skládá váš soubor. Kořenový hash ale ověření těchto dat výrazně usnadňuje.
Vysvětlíme si to zjednodušeně na příkladu 8GB souboru, který je rozdělený na osm částí. Jednotlivé fragmenty nazveme od A po H. Každý fragment pak projde hashovací funkcí, ze které získáme osm různých hashů.
Všech osm fragmentů protáhneme hashovací funkcí, aby získaly svoje hashe.
Dobře, teď máme něco, co dává trochu větší smysl. Máme hashe všech fragmentů, takže kdyby byl jeden vadný, poznáme to při porovnání s těmi zdrojovými, ne? To je možné, ale zároveň ohromně neefektivní. Pokud má váš soubor tisíce fragmentů, vážně u všech z nich provedete hashování a budete pečlivě srovnávat výsledky?
Ne. Místo toho vezmeme jednotlivé páry hashů, zkombinujeme je a zahashujeme je dohromady. Zahashujeme tedy hA + hB, hC + hD, hE + hF a hG + hH. Získáme tak čtyři hashe. Pak uděláme další kolo a skončíme se dvěma. Nakonec zahashujeme zbývající dva hashe a získáme hlavní hash – kořenový hash (neboli Merkleový kořen).
Tato struktura vypadá jako obrácený strom. Dolní řadu tvoří listy, z jejichž kombinací vznikají uzly a nakonec vznikne kořen.
Teď máme Merkleový kořenový hash, který zastupuje stažený soubor. Tento kořenový hash můžeme srovnat s kořenovým hashem zdroje. Pokud se shodují, super! Pokud se ale hashe liší, je jisté, že data byla pozměněna. Jinými slovy, jeden nebo více fragmentů vyprodukovalo jiný hash, takže jakákoli drobná modifikace dat povede k úplně jinému kořenovému hashi.
Naštěstí existuje praktický způsob, jak zjistit, který fragment je chybný. Řekněme, že je to v našem případě fragment hE. Začali byste tím, že byste si ověřili shodu dvou hashů, ze kterých vznikl kořenový hash (hABCD a hEFGH). Vaše hodnota hABCD by měla odpovídat jejich hodnotě, protože v tomto podstromu není žádná chyba. Hodnota hEFGH se ale shodovat nebude, takže víte, že se musíte podívat tam. Pak si vyžádáte zdrojové hodnoty hEF a hGH a srovnáte je s těmi vašimi. Hodnota hGH vypadá v pořádku, takže víte, že za to může hEF. Nakonec srovnáte hashe hE a hF. Teď už víte, že chyba byla u fragmentu hE, a tak ho můžete stáhnout znovu.
Když si to shrneme, hashový strom vznikne rozdělením dat do mnoha bloků, které se pak opakovaně hashují, dokud nevznikne kořenový hash. Pak dokážete efektivně ověřit, jestli se s některým fragmentem dat něco stalo. Jak uvidíme v další části, tato technologie má i další zajímavá využití.
Chcete začít s kryptoměnami? Kupte si Bitcoin na platformě Binance!
Hashové stromy mají několik různých možností použití, ale my se tady zaměříme na jejich význam pro
blockchainy. Hashové stromy jsou pro
Bitcoin a mnoho dalších kryptoměn naprosto nezbytné. Jsou nedílnou součástí každého
bloku a najdete je vždy v
hlavičce bloku. Listy našeho stromu získáme z hashe transakce (
TXID) od každé transakce v bloku.
Kořenový hash má v tomto případě několik funkcí. Pojďme se podívat na jeho různé možnosti využití při těžbě kryptoměn a ověřování transakcí.
Těžba
Bitcoinový blok se skládá ze dvou částí. První částí je hlavička bloku – segment s pevnou velikostí obsahující
metadata bloku. Druhou částí je seznam transakcí, jehož velikost není pevná a obvykle bývá mnohem větší než velikost hlavičky.
Aby těžaři vytěžili platný blok, musí opakovaně hashovat data a vytvořit výstup, který odpovídá určitým podmínkám. Mohou to vyzkoušet až bilionkrát, než jeden z nich najdou. Aby vyprodukovali jiný výstup, mění s každým pokusem náhodné číslo v hlavičce bloku (hodnotu
nonce). Většina bloku ale zůstává stejná. V bloku mohou být tisíce transakcí a stejně je musíte pokaždé znovu hashovat.
Kořenový hash celý tento proces značně zjednodušuje. Když začnete těžit, připravíte si všechny transakce, které chcete zahrnout, a vytvoříte hashový strom. Výsledný kořenový hash (32 bajtů) vložíte do hlavičky bloku. Při těžbě pak místo celého bloku budete muset hashovat jen jeho hlavičku.
Funguje to, protože to není možné zmanipulovat. Všechny transakce bloku efektivně shromáždíte do kompaktního formátu. Nemůžete najít platnou hlavičku bloku a pak změnit seznam transakcí, protože byste tím změnili kořenový hash. Když je blok odeslán jiným uzlům, vypočítají kořen z každého seznamu transakcí. Pokud se neshoduje s kořenem v hlavičce, blok odmítnou.
Ověření
Kořenové hashe mají další zajímavou vlastnost, kterou můžeme využít. Ta se týká lehkých klientů (uzlů, které nemají celou kopii blockchainu). Pokud provozujete uzel na zařízení s omezenými prostředky, nechcete stahovat a hashovat všechny transakce bloku. Místo toho si můžete prostě zažádat o Merkleův důkaz – doklad vystavený plným uzlem, který dokazuje, že se vaše transakce nachází v konkrétním bloku. Tento důkaz se častěji označuje jako zjednodušené ověření platby (SPV – Simplified Payment Verification), které je
Satoshim Nakamotem popsané v bílé knize Bitcoinu.
Když chceme ověřit hD, stačí nám ověřit jen červeně zbarvené hashe.
Představte si situaci, ve které chceme znát informace o transakci, jejíž TXID je hD. Pokud získáme hC, můžeme dopočítat hCD. Pak potřebujeme hAB, abychom spočítali hABCD. A nakonec pomocí hEFGH můžeme ověřit, jestli výsledný kořenový hash odpovídá hashi v hlavičce bloku. Pokud jsou stejné, je to důkaz, že transakce byla zařazena do bloku – je téměř nemožné vytvořit stejný hash z jiných dat.
Ve výše uvedeném příkladu nám stačilo provést jen tři hashování. Bez Merkleova důkazu bychom museli hashovat sedmkrát. Vzhledem k tomu, že v dnešní době bloky obsahují tisíce transakcí, použití Merkleových důkazů nám ušetří spoustu času a výpočetních zdrojů.
Hashové stromy se osvědčily v řadě použití v informatice – jak jsme viděli, pro blockchain jsou nesmírně cenné. V distribuovaných systémech umožňují hashové stromy snadné ověření informací, aniž by zahltily síť zbytečnými daty.
Bez hashových stromů (a kořenových hashů) by
bitcoinové bloky a bloky dalších
kryptoměn nebyly zdaleka tak kompaktní, jako jsou dnes. A i když lehcí klienti nejsou tak soukromí a zabezpečení, Merkleovy důkazy uživatelům umožňují s minimálním úsilím zkontrolovat, jestli jejich transakce byly zahrnuty do bloku.
