Čo je to strom Merkle? Príručka pre začiatočníkov k tomuto komponentu blockchainu

Merkle Trees sú základnou súčasťou blockchainov, ktoré podporujú ich funkčnosť. Umožňujú efektívne a bezpečné overovanie veľkých dátových štruktúr a v prípade blockchainov aj potenciálne neobmedzené dátové súbory.

Implementácia stromov Merkle v blockchainoch má viacero účinkov. Umožňuje im to škálovať a zároveň im poskytuje architektúru založenú na hash na zachovanie integrity údajov a triviálny spôsob overenia integrity údajov.

Kryptografické hašovacie funkcie sú základnou technológiou, ktorá umožňuje Merkleovým stromom fungovať, takže najprv je dôležité pochopiť, čo sú to kryptografické hašovacie funkcie.

Rýchla verdikt: Stromy Merkle sú dátové štruktúry zložené z kryptografických hashov, ktoré umožňujú efektívne overovanie integrity a mapovanie veľkých súborov údajov, vďaka čomu sú integrálnou súčasťou systémov, ako sú blockchainy a distribuovaná kontrola verzií.

Rýchle fakty

Kryptografické hashovacie funkcie

Jednoducho povedané, hašovacia funkcia je akákoľvek funkcia, ktorá sa používa na mapovanie údajov ľubovoľnej veľkosti (vstupu) na výstup s pevnou veľkosťou. Na vstup údajov sa použije hašovací algoritmus a výsledný výstup s pevnou dĺžkou sa označuje ako hash.

Mnoho hashovacích algoritmov je verejne dostupných a možno ich vybrať podľa vašich potrieb.

Výsledný hash z ľubovoľného vstupu má nielen pevnú dĺžku, ale je tiež úplne jedinečný pre vstup a samotná funkcia je deterministická. To znamená, že bez ohľadu na to, koľkokrát spustíte funkciu na rovnakom vstupe, výstup bude vždy rovnaký.

Napríklad, ak máte ako vstup nižšie uvedené súbory údajov, výsledné výstupy sú jedinečné pre každý vstup. Všimnite si, že v druhom a treťom príklade, aj keď je rozdiel vstupov len jedno slovo, výsledné výstupy sú úplne odlišné.

Je to veľmi dôležité, pretože umožňuje „odtlačok“ údajov.

Kryptografická hašovacia funkcia, obrázok z Wikipédie

Keďže dĺžka výstupu (v príklade súčet hash) je vždy rovnaká, ako je určená použitým hashovacím algoritmom, veľké množstvo údajov možno identifikovať iba prostredníctvom ich výsledného hashovania.

Pri systémoch, ktoré obsahujú obrovské množstvo údajov, môžu výhody možnosti ukladať a identifikovať údaje s výstupom s pevnou dĺžkou vytvárať obrovské úspory úložného priestoru a pomôcť zvýšiť efektivitu.

V rámci blockchainov sa na určenie stavu blockchainu používajú hašovacie algoritmy.

Blockchainy sú prepojené zoznamy, ktoré obsahujú údaje a hash pointer, ktorý ukazuje na predchádzajúci blok, čím sa vytvára reťaz prepojených blokov, odtiaľ názov „blockchain“.

Každý blok je navzájom prepojený pomocou hash pointeru, čo je hash dát vo vnútri predchádzajúceho bloku spolu s adresou predchádzajúceho bloku. Prepojením blokov údajov v tomto formáte každý výsledný hash predchádzajúceho bloku predstavuje celý stav blockchainu, pretože všetky hašované údaje predchádzajúcich blokov sú hašované do jedného hashu.

Toto je reprezentované (v prípade algoritmu SHA-256) výstupom (hash), ako je tento:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Vyššie uvedený hash predstavuje odtlačok prsta celého stavu blockchainu pred ním. Stav blockchainu pred novým blokom (ako hashované dáta) je vstup a výsledný hash je výstup.

Aj keď je možné použiť kryptografické hash bez Merkle stromov, je to extrémne neefektívne a neškálovateľné. Používanie hashov na ukladanie údajov do bloku vo formáte série je časovo náročné a ťažkopádne.

Ako uvidíte, stromy Merkle umožňujú triviálne rozlíšenie integrity údajov, ako aj mapovanie týchto údajov cez celý strom pomocou dôkazov Merkle.

Merkle stromy a Merkle dôkazy

Stromy Merkle, pomenované po Ralphovi Merkleovi, ktorý si tento koncept patentoval v roku 1979, sú v podstate stromami dátovej štruktúry, kde každý nelistový uzol je hash svojich príslušných podriadených uzlov.

Listové uzly sú najnižšou vrstvou uzlov v strome. Spočiatku to môže znieť ťažko pochopiteľné, ale ak sa pozriete na bežne používaný obrázok nižšie, bude oveľa ľahšie porozumieť.

Príklad binárneho hash stromu, obrázok z Wikipédie

Dôležité je, že si všimnite, že nelistové uzly alebo „vetvy“ (reprezentované hashom 0-0 a hashom 0-1) na ľavej strane sú hashmi ich príslušných potomkov L1 a L2. Ďalej si všimnite, že vetva Hash 0 je hash jej zreťazených potomkov, vetvy Hash 0-0 a Hash 0-1.

Vyššie uvedený príklad je najbežnejšou a najjednoduchšou formou stromu Merkle známy ako binárny strom Merkle. Ako vidíte, existuje horný hash, ktorý je hashom celého stromu, známy ako koreňový hash. Merkle stromy sú v podstate dátová štruktúra, ktorá môže mať „n“ počet hashov a reprezentovať ho jedným hashom.

Štruktúra stromu umožňuje efektívne mapovanie ľubovoľne veľkého množstva údajov a umožňuje jednoduchú identifikáciu toho, kde v týchto údajoch dochádza k zmenám. Tento koncept umožňuje Merkle dôkazy, pomocou ktorých môže niekto overiť, že hašovanie údajov je konzistentné po celej dĺžke stromu a na správnej pozícii bez toho, aby sa musel skutočne pozerať na celú sadu hashov.

Namiesto toho môžu overiť, či je dátový blok konzistentný s koreňovým hashom, a to tak, že skontrolujú iba malú podmnožinu hashov, a nie celý súbor údajov.

Pokiaľ je koreňový hash verejne známy a dôveryhodný, každý, kto chce v databáze vyhľadať kľúčovú hodnotu, môže použiť dôkaz Merkle na overenie pozície a integrity časti údajov v databáze, ktorá má konkrétny koreň.

Keď je k dispozícii koreňový hash, hašovací strom môže byť prijatý z akéhokoľvek nedôveryhodného zdroja a môže sa sťahovať jedna vetva stromu naraz s okamžitým overením integrity údajov, aj keď celý strom ešte nie je dostupný.

Jednou z najdôležitejších výhod stromovej štruktúry Merkle je schopnosť autentifikovať ľubovoľne veľké súbory údajov pomocou podobného hashovacieho mechanizmu, ktorý sa používa na overenie oveľa menšieho množstva údajov.

Strom je výhodný pre distribúciu veľkých množín údajov do spravovateľných menších častí, kde je bariéra pre overenie integrity podstatne znížená napriek celkovo väčšej veľkosti údajov.

Koreňový hash možno použiť ako odtlačok prsta pre celý súbor údajov, vrátane celej databázy alebo predstavujúci celý stav blockchainu. V nasledujúcich častiach budeme diskutovať o tom, ako Bitcoin a ďalšie systémy implementujú stromy Merkle.

Merkle stromy v bitcoinech

Kryptografická hašovacia funkcia, ktorú používa Bitcoin, je algoritmus SHA-256. Toto je skratka pre „Secure Hash Algorithm“, ktorého výstup má pevnú dĺžku 256 bitov. Základnou funkciou stromov Merkle v Bitcoine je ukladať a prípadne orezávať transakcie v každom bloku.

Ako už bolo spomenuté, bloky v blockchaine sú prepojené pomocou hash predchádzajúceho bloku. V bitcoinoch každý blok obsahuje všetky transakcie v rámci tohto bloku, ako aj hlavičku bloku, ktorá pozostáva z:

• Číslo verzie bloku
• Predchádzajúci blokový hash
• Timestamp
• Cieľ obtiažnosti ťažby
• nonce
• Merkle Root Hash

Obrázok nižšie je z whitepaperu o bitcoinoch a ilustruje, ako strom Merkle zapadá do každého bloku.

Transakcie sú zahrnuté do blokov baníkmi a sú hašované ako súčasť stromu Merkle, čo vedie ku koreňu Merkle, ktorý je uložený v hlavičke bloku. Tento dizajn má množstvo zreteľných výhod.

Predovšetkým, ako sa uvádza v bielej knihe, to umožňuje existenciu uzlov na overenie jednoduchých platieb (SPV), ktoré sú tiež známe ako „ľahkí klienti“. Tieto uzly nemusia sťahovať celý bitcoinový blockchain, iba hlavičky blokov najdlhšieho reťazca.

Uzly SPV to môžu dosiahnuť dotazovaním svojich uzlov rovnocenných partnerov, kým nie sú presvedčené, že uložené hlavičky blokov, s ktorými pracujú, sú súčasťou najdlhšieho reťazca. Uzol SPV je potom schopný určiť stav transakcie pomocou dôkazu Merkle na mapovanie transakcie ku konkrétnemu stromu Merkle s koreňovým hashom príslušného stromu Merkle v hlavičke bloku, ktorá je súčasťou najdlhšieho reťazca.

Implementácia stromov Merkle v bitcoinoch navyše umožňuje orezanie blockchainu, aby sa ušetrilo miesto. Je to dôsledok toho, že v hlavičke bloku je uložený iba koreňový hash, preto je možné staré bloky orezať odstránením nepotrebných vetiev stromu Merkle, pričom sa zachovajú iba tie, ktoré sú potrebné na dôkaz Merkle.

Implementácia Merkle Trees do iných blockchainov a systémov

Hoci bitcoin bol prvým blockchainom, ktorý implementoval stromy Merkle, mnohé ďalšie blockchainy implementujú podobné štruktúry stromu Merkle alebo ešte zložitejšie verzie.

Implementácia stromu Merkle sa ďalej neobmedzuje len na blockchainy a aplikuje sa na množstvo iných systémov.

Ethereum, ako ďalšia najznámejšia kryptomena, je tiež skvelým príkladom inej implementácie stromu Merkle. Pretože Ethereum je turing-complete ako platforma na vytváranie oveľa komplexnejších aplikácií, používa zložitejšiu verziu stromu Merkle nazývanú Merkle Patricia Tree, čo sú v skutočnosti 3 samostatné stromy Merkle používané pre tri druhy objektov. Viac o týchto stromoch sa dozviete tu.

Nakoniec, stromy Merkle sú dôležitou súčasťou distribuovaných systémov na správu verzií, ako sú Git a IPFS. Ich schopnosť jednoducho zabezpečiť a overiť integritu údajov zdieľaných medzi počítačmi vo formáte P2P ich robí pre tieto systémy neoceniteľnými.

záver

Merkle stromy sú neoddeliteľnou súčasťou blockchainov a efektívne im umožňujú fungovať s preukázateľnou nemennosťou a integritou transakcií.

Pochopenie úlohy, ktorú zohrávajú v distribuovaných sieťach a ich základnej technológie kryptografických hašovacích funkcií, je rozhodujúce pre pochopenie základných konceptov v rámci kryptomien, keďže sa naďalej vyvíjajú do väčších a komplexnejších systémov.