Obsah

• Co je strom Merkle?

• Jak stromy Merkle fungují?

• Proč se v bitcoinu používají kořeny Merkle?

  • Hornictví

  • Ověření

• Závěrečné myšlenky

Co je strom Merkle?

Myšlenka Merkleho stromu přišla na počátku 80. let 20. století Ralphem Merklem – počítačovým vědcem, který se nejlépe proslavil svou prací v oblasti kryptografie veřejného klíče.

Merkle strom je struktura používaná k efektivnímu ověření integrity dat v daném datovém souboru a je zvláště důležitá v kontextu sítí peer-to-peer, kde účastníci potřebují sdílet a ověřovat informace nezávisle.

Hashovací funkce jsou nezbytnou součástí stromových struktur Merkle, proto doporučujeme přečíst si článek s názvem Co je hash? Než budete pokračovat ve čtení tohoto článku.

Jak stromy Merkle fungují?

Řekněme, že chcete stáhnout velký soubor. V případě softwaru s otevřeným zdrojovým kódem budete obvykle chtít zkontrolovat, zda hodnota hash staženého souboru odpovídá hodnotě, kterou vývojáři zveřejnili. Pokud ano, pak víte, že soubor, který máte v počítači, odpovídá jejich.

Pokud se hodnoty hash neshodují, máte problém. Buď jste stáhli soubor malwaru vydávajícího se za program, nebo stahování bylo neúspěšné, takže to nefunguje. Pokud se stahování nepodaří, pravděpodobně vás nepotěší, když budete muset chvíli čekat, než se soubor stáhne. Poté budete muset proces začít znovu a doufat, že tentokrát to dopadne dobře.

Možná si v tomto případě říkáte, kdyby existoval jednodušší způsob, jak to udělat. Naštěstí zde přichází na řadu strom Merkle. Pomocí tohoto stromu je soubor rozdělen na části. Pokud je velikost souboru 50 GB, můžete jej rozdělit na 100 částí, každý o velikosti 0,5 GB, a stáhnout jej po částech. To je v podstatě to, co děláte, když používáte torrent soubory.

V tomto případě vám zdroj souboru poskytne hodnotu hash známou jako kořen Merkle. Tato jediná hodnota je reprezentací každého kusu dat, který tvoří váš soubor, ale Merkle root umožňuje mnohem snazší ověření dat.

Aby to nebylo jednoduché, podíváme se na tento příklad, kde používáme 8GB soubor, který je rozdělen na 8 částí, a tyto různé části označíme písmeny A až H. Každá část pak projde hashovací funkcí, výsledkem je 8 různých hodnot hash.

Každou z osmi částí projdeme hašovací funkcí, abychom získali jejich hašovací hodnoty.

No, teď tu máme něco, co dává trochu větší smysl. Máme hodnoty hash všech částí, takže pokud je jedna z nich špatná, poznáte to porovnáním se zdrojovou hodnotou hash, že? Možná, ale je to také velmi neefektivní, pokud má soubor tisíce částí, opravdu je všechny rozdělíte a výsledky pak tak pečlivě porovnáte?

Ne, místo toho vezmeme každou dvojici hodnot hash, sečteme je a pak je zahašujeme dohromady. Hašujeme tedy hA + hB,  hC + hD,  hE + hF a  hG + hH, abychom skončili se 4 hašovacími hodnotami, a poté pro tyto hodnoty provedeme další kolo hašování, až nakonec dosáhneme 2 hašovacích hodnot. Nakonec zahašujeme zbývající dvě hodnoty, abychom získali hlavní hodnotu hash – kořen Merkle (nebo hodnotu root hash).

Struktura vypadá jako převrácený strom, kde v poslední řadě máme listy, které se spojí a vytvoří uzly a nakonec kořen.

Nyní máme kořen Merkle, který představuje soubor, který jsme stáhli. Tuto hodnotu root hash lze porovnat s hodnotou poskytnutou zdrojem, a pokud se shodují, skvělé! Ale pokud jsou hodnoty hash různé, máme jistotu, že data byla upravena, to znamená, že jedna nebo více částí vytvořilo jinou hodnotu hash, takže jakákoli jednoduchá úprava dat nám dá úplně jiný kořen Merkle. .

Naštěstí pro nás všechny existuje snadný způsob, jak zkontrolovat, která část je špatně. V tomto případě řekněme, že tato část je hE. Nejprve se zeptejte partnera na dvě hodnoty hash, které vytvořily kořen Merkle (hABCD a hEFGH). Vaše hodnota hABCD by měla odpovídat jeho, protože v tomto podstromu není žádná chyba. To však neplatí pro hodnotu  hEFGH, proto byste měli tuto hodnotu zkontrolovat. Poté si vyžádáte hodnoty hEF a hGH a porovnáte je se svými vlastními hodnotami. Zjistíte, že hodnota hGH je v pořádku, a pak si uvědomíte, že hodnota hEF je důvodem problému. Nakonec porovnáte hašovací hodnoty hE a hF a nyní víte, že hE je nesprávné, takže si můžete tento fragment znovu stáhnout.

Stručně řečeno, strom Merkle je vytvořen rozdělením dat do několika částí, které se pak iterativně hašují, aby vytvořily kořen Merkle. Poté můžete efektivně zkontrolovat, zda nedošlo k chybě u určitého údaje. Jak uvidíme v další části, existují i ​​další zajímavé aplikace.

Chcete začít obchodovat v digitálních měnách? Kupte si bitcoiny (BTC) na Binance nyní!

Proč se v bitcoinu používají kořeny Merkle?

Pro stromy Merkle existuje několik případů použití, ale zde se zaměříme na jejich význam v blockchainech. Stromy Merkle jsou pro bitcoin a další kryptoměny velmi důležité. Představuje hlavní součást každého bloku, protože je umístěn v oddílech úložiště bloku. Pro přístup k listům stromu používáme hodnotu hash transakce (ID transakce) každé transakce v bloku.

V tomto případě kořen Merkle slouží několika účelům a níže si projdeme jeho aplikace v těžbě kryptoměn a ověřování transakcí.

Hornictví

Blok bitcoinů se skládá ze dvou částí, první částí je oddíl úložiště bloku, což je část s pevnou velikostí, která obsahuje metadata pro blok. Druhá část je seznam transakcí s proměnnou velikostí, ale obvykle má mnohem větší velikost než oddíl blokového úložiště.

Těžaři potřebují opakovaně hašovat data, aby vytvořili výstup, který odpovídá specifickým podmínkám pro těžbu platného bloku. Než najdou správný blok, mohou provést biliony pokusů. Při každém pokusu změní náhodné číslo v sekci úložiště bloku (soukromý kód), aby vytvořili jiný výstup. Velká část hmoty však zůstává stejná. Počet transakcí může být tisíce transakcí a budete je muset pokaždé hashovat.

Kořen Merkle tento proces mnohem usnadňuje, protože když začnete těžit, vložíte do řady všechny transakce, které chcete zahrnout, a vytvoříte strom Merkle. Výslednou hodnotu hash root (32 bajtů) pak umístíte do oddílu úložiště bloku. Poté, když těžíte, vše, co musíte udělat, je hashovat oddíl úložiště bloku místo celého bloku.

Tato metoda funguje, protože s ní nelze manipulovat a efektivně shrnuje všechny blokové transakce do kompaktního formátu. A nemůžete najít platný oddíl úložiště bloků 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čítá kořen ze seznamu transakcí, a pokud se neshoduje s tím, co je uvedeno v sekci ukládání bloku, blok je odmítnut.

Ověření

Existuje ještě jedna zajímavá vlastnost kořenů Merkle, kterou můžeme využít. Tato funkce je důležitá pro jednoduchý software uzlů (uzly, které nenesou úplnou kopii blockchainového řetězce). Pokud provozujete uzel na stroji s omezenými zdroji, nechcete stahovat a hashovat všechny transakce bloku. Místo toho si můžete vyžádat důkaz Merkle – důkaz poskytnutý celým uzlem, který dokazuje, že jde o transakci existuje v konkrétním bloku. To se často označuje jako zjednodušené ověření platby (SPV) a podrobně to vysvětlil Satoshi Nakamoto v technické zprávě o bitcoinech.

K ověření hD potřebujeme pouze hodnoty hash zobrazené červeně.

Uvažujme například scénář, kdy chceme znát informace o transakci s ID transakce hD. Pokud máme k dispozici hodnotu hC, můžeme hCD najít. Potom potřebujeme  hAB k výpočtu hABCD. Nakonec v případě  hEFGH můžeme zkontrolovat, zda se výsledný kořen Merkle shoduje s kořenem v oddílu úložiště bloku. Pokud se shoduje, je to důkaz, že transakce v bloku existovala – protože by bylo téměř nemožné vygenerovat stejnou hash hodnotu s různými daty.

V předchozím příkladu jsme museli provést hash pouze třikrát a bez Merkleova důkazu bychom ho museli provést 7krát. Vzhledem k tomu, že bloky dnes obsahují tisíce transakcí, použití Merkleho důkazu šetří spoustu času a výpočetních zdrojů.

Závěrečné myšlenky

Stromy Merkle se ukázaly jako extrémně užitečné v řadě aplikací počítačové vědy – a jak jsme viděli, pro blockchainy mají obrovský význam. V distribuovaných systémech Merkle stromy usnadňují ověřování informací, aniž by zahlcovaly síť přívalem zbytečných dat.

Bez stromů Merkle (a kořenů Merkle) by bloky bitcoinu a dalších kryptoměn nebyly tak malé jako dnes. Zatímco jednoduchý smluvní software postrádá soukromí a zabezpečení, Merkleův důkaz umožňuje uživatelům ověřit, zda se jejich transakce připojily k bloku s minimálními náklady.