Co je to strom Merkle? Průvodce pro začátečníky k této blockchainové komponentě

Merkle Trees jsou základní součástí blockchainů, které podporují jejich funkčnost. Umožňují efektivní a bezpečné ověřování velkých datových struktur a v případě blockchainů potenciálně neomezené datové sady.

Implementace stromů Merkle v blockchainech má více efektů. Umožňuje jim to škálovat a zároveň jim poskytuje architekturu založenou na hash pro zachování integrity dat a triviální způsob ověření integrity dat.

Kryptografické hašovací funkce jsou základní technologií, která umožňuje Merkleovým stromům fungovat, takže nejprve je důležité pochopit, co jsou to kryptografické hašovací funkce.

Rychlý výrok: Stromy Merkle jsou datové struktury složené z kryptografických hashů, které umožňují efektivní ověřování integrity a mapování velkých souborů dat, díky čemuž jsou nedílnou součástí systémů, jako jsou blockchainy a distribuovaná kontrola verzí.

Stručná fakta

Kryptografické hashovací funkce

Jednoduše řečeno, hashovací funkce je jakákoli funkce, která se používá k mapování dat libovolné velikosti (vstupu) na výstup s pevnou velikostí. Na vstup dat je aplikován hashovací algoritmus a výsledný výstup s pevnou délkou se nazývá hash.

Mnoho hashovacích algoritmů je široce veřejně dostupných a lze je vybrat podle vašich potřeb.

Výsledný hash z libovolného vstupu má nejen pevnou délku, ale je také zcela jedinečný pro vstup a samotná funkce je deterministická. To znamená, že bez ohledu na to, kolikrát spustíte funkci na stejném vstupu, výstup bude vždy stejný.

Pokud například máte jako vstup níže uvedené datové sady, výsledné výstupy jsou pro každý vstup jedinečné. Všimněte si, jak ve druhém a třetím příkladu, i když je rozdíl vstupů pouze jedno slovo, výsledné výstupy jsou zcela odlišné.

To je velmi důležité, protože umožňuje „otisky prstů“ dat.

Kryptografická hašovací funkce, obrázek z Wikipedie

Vzhledem k tomu, že délka výstupu (v příkladu součet hash) je vždy stejná, jako je určena použitým algoritmem hash, lze obrovské množství dat identifikovat pouze pomocí jejich výsledného hash.

U systémů, které obsahují obrovské množství dat, mohou výhody možnosti ukládat a identifikovat data s výstupem s pevnou délkou vytvořit obrovské úspory úložiště a pomoci zvýšit efektivitu.

V rámci blockchainů se k určení stavu blockchainu používají hashovací algoritmy.

Blockchainy jsou propojené seznamy, které obsahují data a hash ukazatel, který ukazuje na předchozí blok, čímž vytváří řetězec spojených bloků, odtud název „blockchain“.

Každý blok je vzájemně propojen přes hash pointer, což je hash dat uvnitř předchozího bloku spolu s adresou předchozího bloku. Propojením bloků dat v tomto formátu představuje každý výsledný hash předchozího bloku celý stav blockchainu, protože všechna hašovaná data předchozích bloků jsou hašována do jednoho hashe.

To je reprezentováno (v případě algoritmu SHA-256) výstupem (hash), jako je tento:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Výše uvedený hash je otisk celého stavu blockchainu před ním. Stav blockchainu před novým blokem (jako hashovaná data) je vstup a výsledný hash je výstup.

I když je možné používat kryptografické hashe bez Merkle stromů, je to extrémně neefektivní a neškálovatelné. Použití hashů k ukládání dat v bloku ve formátu série je časově náročné a těžkopádné.

Jak uvidíte, stromy Merkle umožňují triviální rozlišení integrity dat a také mapování těchto dat přes celý strom pomocí důkazů Merkle.

Merkle Trees a Merkle Proofs

Stromy Merkle, pojmenované po Ralphu Merkleovi, který si tento koncept patentoval v roce 1979, jsou v zásadě stromy datové struktury, kde každý nelistový uzel je hash svých příslušných podřízených uzlů.

Listové uzly jsou nejnižší vrstvou uzlů ve stromu. Zpočátku to může znít těžko pochopitelné, ale když se podíváte na běžně používaný obrázek níže, bude to mnohem snazší pochopit.

Příklad binárního hash stromu, Obrázek z Wikipedie

Důležité je, že si všimněte, že nelistové uzly nebo „větve“ (reprezentované hash 0-0 a hash 0-1) na levé straně jsou hashe jejich příslušných potomků L1 a L2. Dále si všimněte, že větev Hash 0 je hash svých zřetězených potomků, větví Hash 0-0 a Hash 0-1.

Výše uvedený příklad je nejběžnější a nejjednodušší formou stromu Merkle známého jako binární strom Merkle. Jak vidíte, existuje horní hash, který je hashem celého stromu, známý jako kořenový hash. Stromy Merkle jsou v podstatě datovou strukturou, která může mít „n“ počet hashů a reprezentovat je jedním hashem.

Struktura stromu umožňuje efektivní mapování libovolně velkého množství dat a umožňuje snadnou identifikaci, kde dochází ke změnám v těchto datech. Tento koncept umožňuje Merkle důkazy, pomocí kterých může někdo ověřit, že hašování dat je konzistentní po celé délce stromu a ve správné pozici, aniž by se musel skutečně dívat na celou sadu hashů.

Místo toho mohou ověřit, zda je datový blok konzistentní s kořenovým hashem, a to tak, že zkontrolují pouze malou podmnožinu hodnot hash, nikoli celou sadu dat.

Dokud je kořenový hash veřejně známý a důvěryhodný, je možné, aby každý, kdo chce v databázi vyhledat klíč-hodnota, použít důkaz Merkle k ověření pozice a integrity části dat v databázi, která má konkrétní kořen.

Když je k dispozici kořenový hash, může být hashovací strom přijat z jakéhokoli nedůvěryhodného zdroje a může být stažena jedna větev stromu najednou s okamžitým ověřením integrity dat, i když celý strom ještě není k dispozici.

Jednou z nejdůležitějších výhod stromové struktury Merkle je možnost autentizovat libovolně velké sady dat pomocí podobného hashovacího mechanismu, který se používá k ověření mnohem menšího množství dat.

Strom je výhodný pro distribuci velkých sad dat do spravovatelných menších částí, kde je bariéra pro ověření integrity podstatně snížena i přes celkově větší objem dat.

Kořenový hash lze použít jako otisk pro celou sadu dat, včetně celé databáze nebo představující celý stav blockchainu. V následujících částech probereme, jak Bitcoin a další systémy implementují stromy Merkle.

Merkle stromy v bitcoinu

Kryptografická hašovací funkce, kterou Bitcoin používá, je algoritmus SHA-256. To je zkratka pro „Secure Hash Algorithm“, jehož výstup má pevnou délku 256 bitů. Základní funkcí stromů Merkle v bitcoinu je ukládat a případně ořezávat transakce v každém bloku.

Jak již bylo zmíněno dříve, bloky v blockchainu jsou propojeny pomocí hashů předchozího bloku. V bitcoinu každý blok obsahuje všechny transakce v tomto bloku a také hlavičku bloku, která se skládá z:

• Číslo verze bloku
• Předchozí blokový hash
• Timestamp
• Cíl obtížnosti těžby
• Nuncius
• Merkle Root Hash

Obrázek níže je z whitepaperu o bitcoinech a ilustruje, jak strom Merkle zapadá do každého bloku.

Transakce jsou těžaři zahrnuty do bloků a jsou hashovány jako součást Merkleho stromu, což vede ke kořenu Merkle, který je uložen v hlavičce bloku. Tento design má řadu zřetelných výhod.

Především, jak je uvedeno v dokumentu whitepaper, to umožňuje existenci uzlů Simple Payment Verification (SPV), také známých jako „lehcí klienti“. Tyto uzly nemusí stahovat celý bitcoinový blockchain, pouze hlavičky bloků nejdelšího řetězce.

SPV uzly toho mohou dosáhnout dotazováním svých uzlů, dokud se nepřesvědčí, že uložené hlavičky bloků, se kterými pracují, jsou součástí nejdelšího řetězce. Uzel SPV je pak schopen určit stav transakce pomocí důkazu Merkle k mapování transakce na konkrétní strom Merkle s kořenovým hashem příslušného stromu Merkle v hlavičce bloku, která je součástí nejdelšího řetězce.

Implementace stromů Merkle v bitcoinu navíc umožňuje prořezávání blockchainu za účelem úspory místa. To je důsledkem toho, že v hlavičce bloku je uložen pouze kořenový hash, takže staré bloky lze ořezat odstraněním nepotřebných větví stromu Merkle a zachovat pouze ty, které jsou potřebné pro důkaz Merkle.

Implementace Merkle Trees do jiných blockchainů a systémů

Ačkoli Bitcoin byl prvním blockchainem, který implementoval stromy Merkle, mnoho dalších blockchainů implementuje podobné stromové struktury Merkle nebo ještě složitější verze.

Dále, implementace stromu Merkle není omezena pouze na blockchainy, ale je aplikována na řadu dalších systémů.

Ethereum, další nejznámější kryptoměna, je také skvělým příkladem jiné implementace stromu Merkle. Protože Ethereum je turing-complete jako platforma pro vytváření mnohem složitějších aplikací, používá složitější verzi stromu Merkle nazývanou Merkle Patricia Tree, což jsou ve skutečnosti 3 samostatné stromy Merkle používané pro tři druhy objektů. Více o těchto stromech se můžete dozvědět zde.

A konečně, stromy Merkle jsou důležitou součástí distribuovaných systémů pro správu verzí, jako jsou Git a IPFS. Jejich schopnost snadno zajistit a ověřit integritu dat sdílených mezi počítači ve formátu P2P je činí pro tyto systémy neocenitelnými.

Proč investovat do čističky vzduchu?

Merkle stromy jsou nedílnou součástí blockchainů a efektivně jim umožňují fungovat s prokazatelnou neměnností a integritou transakcí.

Pochopení role, kterou hrají v distribuovaných sítích, a jejich základní technologie kryptografických hašovacích funkcí je zásadní pro pochopení základních konceptů v rámci kryptoměn, protože se neustále vyvíjejí do větších a složitějších systémů.