Co je strom Merkle?
Koncept Merkleho stromu navrhl na počátku 80. let Ralph Merkle – počítačový vědec proslulý svou prací na kryptografii s veřejným klíčem.
Merkle strom je struktura používaná k efektivnímu ověření integrity dat v sadě. Jsou obzvláště zajímavé v kontextu sítí peer-to-peer, kde účastníci potřebují sdílet a nezávisle ověřovat informace.
Hašovací funkce jsou jádrem stromových struktur Merkle, takže vám doporučujeme podívat se na Co je hašování? před pokračováním.
Jak stromy Merkle fungují?
Předpokládejme, že chcete stáhnout velký soubor. U softwaru s otevřeným zdrojovým kódem byste obvykle chtěli zkontrolovat, zda hash souboru, který jste si stáhli, odpovídá tomu, který zveřejnili vývojáři. Pokud ano, víte, že soubor, který máte v počítači, je úplně stejný jako ten jejich.
Pokud se hash neshoduje, máte problém. Buď jste si stáhli škodlivý soubor vydávající se za software, nebo se nestáhl správně, a proto nebude fungovat. Pokud je tomu tak v druhém případě, pravděpodobně nebudete příliš šťastní, pokud jste museli nějakou dobu čekat na stažení souboru. Nyní musíte proces restartovat a doufat, že se znovu nepoškodí.
Kdyby existoval jednodušší způsob, jak toho dosáhnout, myslíte si. Naštěstí tam přicházejí stromy Merkle. S jedním z nich byste měli svůj soubor rozdělený na kousky. Pokud by se jednalo o soubor o velikosti 50 GB, můžete jej rozdělit na sto kusů, takže každý má velikost 0,5 GB. Pak by se to stahovalo kus po kuse. To je v podstatě to, co děláte, když torrentujete soubory.
V tomto případě vám váš zdroj poskytl hash známý jako Merkle root. Tento jediný hash představuje každou část dat, která tvoří váš soubor. Kořen Merkle však mnohem snadněji ověřuje data.
Aby to bylo jednoduché, ukažme si příklad, kdy použijeme 8GB soubor rozdělený na osm částí. Volejte různé fragmenty A až H. Každý fragment pak prochází hashovací funkcí, což nám dává osm různých hashů.
Každý z našich osmi fragmentů procházíme hashovací funkcí, abychom získali jejich hash.
Dobře, takže máme něco, co dává trochu větší smysl. Máme hash všech fragmentů, takže pokud je jeden vadný, poznáme to porovnáním s fragmentem zdroje, že? Možná, ale je to také neuvěřitelně neefektivní. Pokud má váš soubor tisíce fragmentů, opravdu je všechny zahašujete a výsledky pečlivě porovnáte?
Ne. Namísto toho vezmeme každý pár hashů, zkombinujeme je a pak je hašujeme dohromady. Takže hašujeme hA + hB, hC + hD, hE + hF a hG + hH. Skončíme se čtyřmi hashemi. Potom s nimi provedeme další kolo hašování, abychom skončili se dvěma. Nakonec zbylé dva hašujeme, abychom se dostali k našemu hlavnímu haši – Merkle root (neboli root hash).
Struktura vypadá jako převrácený strom. Ve spodní řadě máme listy, které se spojí, aby vznikly uzly a nakonec kořen.
Nyní máme kořen Merkle, který představuje soubor, který jsme stáhli. Tento root hash můžeme porovnat s tím, který poskytuje zdroj. Pokud to odpovídá, perfektní! Pokud se ale hash liší, můžeme si být jisti, že data byla upravena. Jinými slovy, jeden nebo více fragmentů vytvořilo jiný hash. Takže jakákoli drobná úprava dat nám dá úplně jiný Merkle kořen.
Naštěstí pro nás existuje šikovný způsob, jak zkontrolovat, který fragment je vadný. V našem případě řekněme, že je to on. Začnete tím, že se zeptáte partnera na dva hashe, který vytvořil Merkleho kořen (hABCD a hEFGH). Vaše hodnota hABCD by se měla shodovat s jejich, protože v tomto podstromu není žádná chyba. Ale hEFGH nebude, takže víte, že se tam máte přihlásit. Poté požádáte o hEF a hGH a porovnáte je se svými. hGH bude vypadat dobře, takže víte, že hEF je náš viník. Nakonec porovnáte hashe hE a hF. Nyní víte, že hE je nesprávné, takže si můžete tento kus znovu stáhnout.
Když to všechno shrneme, Merkle strom je vytvořen rozdělením dat na mnoho částí, které jsou pak opakovaně hašovány, aby vytvořily Merkleův kořen. Poté můžete efektivně ověřit, zda se s některým údajem něco pokazilo. Jak uvidíme v další části, existují i další zajímavé aplikace.
Chcete začít s kryptoměnou? Kupte si bitcoiny na Binance!
Proč se v bitcoinu používají kořeny Merkle?
Existuje několik případů použití pro stromy Merkle, ale zde se zaměříme na jejich význam v blockchainech. Merkle stromy jsou nezbytné v bitcoinu a mnoha dalších kryptoměnách. Jsou nedílnou součástí každého bloku, kde je lze nalézt v záhlaví bloků. K získání listů pro náš strom používáme transakční hash (TXID) každé transakce zahrnuté v bloku.
Kořen Merkle v tomto případě slouží k několika účelům. Pojďme se podívat na jejich aplikace v těžbě kryptoměn a ověřování transakcí.
Hornictví
Bitcoinový blok se skládá ze dvou kusů. První částí je záhlaví bloku, segment pevné velikosti obsahující metadata pro blok. Druhá část je seznam transakcí, jejichž velikost je proměnná, ale bývá mnohem větší než hlavička.
Těžaři potřebují opakovaně hašovat data, aby vytvořili výstup, který odpovídá určitým podmínkám pro těžbu platného bloku. Než nějaký najdou, mohou udělat biliony pokusů. Při každém pokusu změní náhodné číslo v hlavičce bloku (nonce), aby vytvořili jiný výstup. Ale velká část bloku zůstává stejná. Transakcí mohou být tisíce a i tak je budete muset pokaždé hashovat.
Kořen Merkle tento proces značně zjednodušuje. Když začnete těžit, seřadíte všechny transakce, které chcete zahrnout, a vytvoříte strom Merkle. Výsledný kořenový hash (32 bajtů) vložíte do hlavičky bloku. Když pak těžíte, stačí zahašovat pouze hlavičku bloku místo celého bloku.
Funguje to, protože je odolný proti neoprávněné manipulaci. Efektivně shrnete všechny transakce bloku v kompaktním formátu. Nemůžete najít platnou hlavičku bloku a později změnit seznam transakcí, protože by to změnilo kořen Merkle. Když je blok odeslán do jiných uzlů, vypočítají kořen ze seznamu transakcí. Pokud se neshoduje s tím v záhlaví, blok odmítnou.
Ověření
Existuje další zajímavá vlastnost kořenů Merkle, kterou můžeme využít. Toto se týká lehkých klientů (uzlů, které nedrží úplnou kopii blockchainu). Pokud provozujete uzel na zařízení s omezenými prostředky, nechcete stahovat a hashovat všechny transakce bloku. Místo toho můžete jednoduše požádat o důkaz Merkle – důkaz poskytnutý celým uzlem, který dokazuje, že vaše transakce je v konkrétním bloku. Toto se častěji označuje jako zjednodušené ověření plateb nebo SPV a bylo podrobně popsáno Satoshi Nakamotem v bitcoinové bílé knize.
Ke kontrole hD potřebujeme pouze červeně zobrazené hashe.
Zvažte scénář, kdy chceme znát informace o transakci, jejíž TXID je hD. Pokud nám bude poskytnut hC, můžeme hCD vypracovat. Potom potřebujeme hAB k výpočtu hABCD. Nakonec pomocí hEFGH můžeme zkontrolovat, zda se výsledný kořen Merkle shoduje s kořenem z hlavičky bloku. Pokud ano, je to důkaz, že transakce byla zahrnuta do bloku – bylo by téměř nemožné vytvořit stejný hash s různými daty.
Ve výše uvedeném příkladu jsme museli hashovat pouze třikrát. Bez Merkleho důkazu bychom to museli udělat sedmkrát. Protože bloky v dnešní době obsahují tisíce transakcí, používání Merkle proofs nám šetří spoustu času a výpočetních zdrojů.
Závěrečné myšlenky
Stromy Merkle se ukázaly jako velmi užitečné v řadě aplikací počítačové vědy – jak jsme viděli, v blockchainech jsou neuvěřitelně cenné. V distribuovaných systémech Merkle stromy umožňují snadné ověření informací bez zahlcení sítě zbytečnými daty.
Bez stromů Merkle (a kořenů Merkle) by bloky bitcoinu a dalších kryptoměn nebyly zdaleka tak kompaktní jako dnes. A zatímco lehkí klienti postrádají ochranu soukromí a zabezpečení, důkazy Merkle umožňují uživatelům zkontrolovat, zda byly jejich transakce zahrnuty do bloku s minimální režií.
