Obsah
Co je strom Merkle?
Jak se staví stromy Merkle?
Proč se v bitcoinu používají kořeny Merkle?
Hornictví
Ověření
souhrn
Co je strom Merkle?
Koncept stromu Merkle navrhl počátkem 80. let Ralph Merkle, počítačový vědec známý svou prací v oblasti šifrování veřejného klíče.
Merkle strom je struktura pro ověřování dat v množině. Je široce používán v oblasti sítí peer-to-peer, kde si účastníci potřebují vyměňovat informace a podrobovat je nezávislému ověření.
Stromová struktura Merkle je založena na hashovacích funkcích, proto doporučujeme, abyste si nejprve přečetli článek „Co je to hash“ a poté se k tomuto tématu vrátili.
Jak se staví stromy Merkle?
Řekněme, že stahujete velký soubor. Při použití programu s otevřeným zdrojovým kódem je třeba zkontrolovat, zda hash staženého souboru odpovídá publikovanému hash vývojářů. Pokud se shoduje, pak je soubor ve vašem počítači přesně stejný jako jejich soubor.
Pokud se hodnoty hash liší, pak jste buď stáhli škodlivý soubor vydávající se za program, nebo byl stažen nesprávně a nebude fungovat. Problémy s načítáním mohou být také potíže, zvláště pokud to trvá dlouho. V takovém případě budete muset soubor stáhnout znovu a doufat, že tentokrát vše proběhne v pořádku.
Pravděpodobně si říkáte: "Je to opravdu tak složité?" Naštěstí se zde hodí stromy Merkle, které nám umožňují rozdělit soubor na části. Například soubor o velikosti 50 GB lze rozdělit na 100 částí o velikosti 0,5 GB. V tomto případě se bude stahovat po částech, podobně jako se soubory stahují přes torrent.
Hlavním cílem procesu je získat jediný hash zvaný Merkle root, který reprezentuje každý kus dat v souboru. Použitím kořene Merkle můžeme značně zjednodušit ověřování dat.
Jako příklad si vezměme 8 GB soubor rozdělený na 8 částí. Každý fragment je pojmenován od A do H a poté prochází hashovací funkcí, aby se vytvořilo 8 různých hashů.
Každý z osmi fragmentů prochází hashovací funkcí, aby se vytvořil jeho hash.
Tak jsme to dostali z cesty. Obdrželi jsme hash všech fragmentů, což znamená, že jej můžeme porovnat s původním a zjistit, který je vadný, že? Je to možné, ale bylo by to extrémně neúčinné. V našem souboru je pouze osm fragmentů, ale pokud jich jsou tisíce, hashovali byste je všechny a porovnali výsledky?
Stěží. Místo toho musíte vzít každý pár hashů, zřetězit je a hašovat je dohromady. Hašujeme tedy hA + hB, hC + hD, hE + hF a hG + hH a získáme čtyři haše. Poté provedeme další kolo hašování tak, aby byly haše dva. Nakonec zbylý pár zahašujeme a získáme hlavní hash – Merkle root (neboli root hash).
Struktura připomíná strom vzhůru nohama. Ve spodním řádku jsou „listy“, které jdou do uzlů, které jdou do kořene.
Máme tedy kořen Merkle představující stažený soubor. Nyní můžeme porovnat kořenový hash s původním hashem tvůrce. Pokud se shodují, pak je vše skvělé! Pokud se hash liší, znamená to, že data byla změněna, to znamená, že jeden nebo více fragmentů vytvořilo jiný hash. Jakákoli úprava dat tedy vytvoří zcela jiný Merkle kořen.
Naštěstí můžeme snadno najít nesprávný fragment. Řekněme, že tohle je on. Nejprve se dotazujte na poslední dva hash, které vytvořily kořen Merkle (hABCD a hEFGH). Váš hABCD bude stejný jako originál, protože v tomto segmentu nejsou žádné chyby, ale váš hEFGH bude jiný a měl by být zkontrolován. Dále požadujeme hEF a hGH a porovnáme je s našimi. Protože hGH bude odpovídat, potřebujeme hEF. Nakonec porovnáme hashe hE a hF. Takže jsme zjistili, že nesprávný fragment je hE, což znamená, že jej musíme znovu stáhnout.
Abychom to shrnuli, Merkle strom je vytvořen rozdělením dat do mnoha částí, které jsou pak opakovaně hašovány, aby vytvořily Merkleův kořen. Tento systém usnadňuje kontrolu, zda jsou všechny údaje v pořádku. V další části se podíváme na další možná použití.
Zajímá vás, jak začít s kryptoměnami? Kupte si bitcoiny na Binance!
Proč se v bitcoinu používají kořeny Merkle?
Stromy Merkle mají mnoho využití, ale zatím nás zajímá jejich aplikace v blockchainu. Merkle stromy jsou nezbytné při práci s bitcoiny a mnoha dalšími kryptoměnami, jsou nedílnou součástí každého bloku a jsou umístěny v hlavičkách bloků. K získání listů stromu používáme hash každé transakce (TXID) obsažené v bloku.
V tomto případě plní kořen Merkle několik úkolů. Dále se podíváme na jejich využití při těžbě kryptoměn a ověřování transakcí.
Hornictví
Bitcoinový blok se skládá ze dvou částí. První částí je záhlaví bloku, segment pevné velikosti obsahující metadata bloku. Druhou částí je seznam transakcí, jejichž velikost je obvykle mnohem větší než hlavička, ale může se lišit.
Těžaři potřebují hašovat data vícekrát, aby získali výsledek, který splňuje určité podmínky a vytěží platný blok. Jeho nalezení může trvat biliony pokusů, protože těžaři potřebují změnit náhodné číslo v hlavičce bloku (nikoli), aby získali nový výsledek, ale většina bloku zůstane stejná. V bloku mohou být tisíce transakcí a všechny budou muset být pokaždé hašovány.
Kořen Merkle tento proces značně zjednodušuje. Během těžby jsou všechny potřebné transakce seřazeny do stromu Merkle. Kořenový hash (32 bajtů) je umístěn v hlavičce bloku, poté se hašuje pouze hlavička bloku, nikoli celý blok.
Tato metoda je odolná proti neoprávněné manipulaci a efektivně shrnuje všechny transakce do bloku v kompaktním formátu. Je však nemožné najít platnou hlavičku bloku a poté změnit seznam transakcí, protože to změní kořen Merkle. Když je blok odeslán do jiných uzlů, vypočítají kořen ze seznamu transakcí. Pokud se neshoduje s kořenem v hlavičce, blok je odmítnut.
Ověření
Podívejme se na další užitečnou vlastnost kořenů Merkle, která se týká zjednodušených uzlů (které neobsahují kompletní kopii blockchainu). Pokud provozujete uzel na zařízení s omezenými prostředky, nemusíte nutně stahovat a hashovat všechny transakce bloku. Místo toho můžete jednoduše požádat celý uzel o důkaz Merkle – důkaz, že vaše transakce je v konkrétním bloku. Tuto metodu podrobně popsal Satoshi Nakamoto v bílé knize o bitcoinech a často se nazývá zjednodušené ověření platby (SPV).
Pro kontrolu hD jsou potřeba pouze červené hash.
Řekněme, že potřebujeme informace o transakci, jejíž TXID je hD. Vzhledem k hC můžeme vypočítat hCD. K výpočtu hABCD pak potřebujeme hAB. Nakonec lze hEFGH použít ke kontrole, zda se výsledný kořen Merkle shoduje s kořenem v hlavičce bloku. Pokud ano, pak to dokazuje, že transakce byla zahrnuta do bloku, protože je téměř nemožné vytvořit stejný hash s různými daty.
Ve výše uvedeném příkladu jsme hašovali pouze třikrát, zatímco bez Merkleho důkazu by to muselo být provedeno sedmkrát. Vzhledem k tomu, že bloky mohou obsahovat tisíce transakcí, může používání důkazů Merkle ušetřit spoustu času a výpočetních zdrojů.
souhrn
Stromy Merkle prokázaly svou účinnost ve výpočetní technice. Jsou neuvěřitelně užitečné v blockchainech a umožňují snadné ověření informací napříč distribuovanými systémy, aniž by došlo k přetížení sítě zbytečnými daty.
Bez stromů Merkle (a kořenů Merkle) by bloky bitcoinu a dalších kryptoměn byly velmi objemné. Zatímco lehké uzly mohou mít obavy o soukromí a bezpečnost, důkazy Merkle mohou nákladově efektivně zjistit, zda byly transakce zahrnuty do bloku.