Co je Merkle Tree?
Merkle Tree je datová struktura, která zkomprimuje velký soubor záznamů do jednoho krátkého otisku. Umožňuje dokázat, že položka je v obrovském seznamu tím, že ověříte jen pár malých částí, ne celý obsah. Představte si rodokmen, kde každý rodič je souhrnem svých potomků, vše směřuje k jednomu konečnému předkovi.
Merkle Tree "ukládá" všechny transakce samotný. Ne tak docela. Ukládá jen kompaktní otisky těchto záznamů a strom lze z původních záznamů kdykoli znovu sestavit.
Jak Merkle Tree funguje
Představte si blok plateb, který potřebuje rychlý, ověřitelný souhrn. Zde je princip Merkle Tree v prostých slovech:
- Krok 1: Začněte s seznamem položek, například transakcí, z nichž každá je listem stromu.
- Krok 2: Převeďte každou položku na krátký otisk pomocí hashovací funkce.
- Krok 3: Spojujte sousední otisky po dvojicích, smáčejte každou dvojici dohromady a znovu zahashujte, abyste vytvořili jejich rodiče.
- Krok 4: Opakujte párování a hashování až do doby, kdy zůstane jediný vrchní otisk. To je Merkle root této množiny.
- Krok 5: Chcete‑li dokázat, že položka patří do množiny, potřebujete jen tu položku a krátkou cestu sousedních otisků. Rychlé a malé.
Tím je myšlena myšlenka: malé důkazy, vysoká důvěra.
Proč je Merkle Tree důležitý
Shrnutím obrovského množství transakčních dat do jednoho kompaktního otisku Merkle Tree zrychluje a zlevňuje ověřování.
- Výhoda: Zkontrolujete zařazení bez stahování celého bloku, čímž šetříte čas a přenos dat.
- Poznámka: Hodí se k dnešnímu postoji na internetu: důvěřuj, ale ověřuj; Rolex potká Reddit.
- Kde se s tím setkáte: Narazíte na něj v blocích Bitcoinu, v potvrzeních Ethereum, v allowlistech NFT, při airdropech a v rollupech.
Pokud je počet listů lichý, mnohé návrhy duplikují poslední před tím, než se hashy postupně spojují směrem k vrcholu. Také si ověřte přesný hashovací proces, který vaše síť nebo knihovna používá, protože drobné odlišnosti v pravidlech mohou změnit důkazy.
Hlavní vlastnosti Merkle Tree
Tady je, co ho dělá užitečným:
- Efektivita: Důkazy zůstávají malé i při velmi velkém množství dat, takže lehké klienty nezatíží.
- Integrita: Změníte jeden byte v listu a změna se projeví až v kořeni, takže manipulace jsou snadno odhalitelné.
- Kořen: Vše se sbalí do jediného Merkle root, který lze uložit nebo podepsat pro pozdější ověření.
Varianty
Merkle Tree má několik běžných podob, na které narazíte:
- Binární: Klasický strom založený na párech, používaný v blocích Bitcoinu.
- Merkle Patricia: Trie pro data ve formě klíč‑hodnota, používaná pro stav a potvrzení v Ethereu.
- Řídký: Obrovský indexovaný strom, kde většina listů je prázdná, vhodný pro stručné důkazy o členství i nečlenství.
- Verkle: Novější příbuzný s kratšími důkazy při velmi vysokém větvení, zkoumaný pro možné budoucí upgrady.
Merkle Tree důkazy jsou důvěryhodné jen do míry, v jaké důvěřujete hlavičce nebo kontrolnímu bodu, který přijmete. Pokud důvěřujete špatnému Merkle rootu, i ten nejpřesnější důkaz nic neznamená.
Příklad
Lehká peněženka ve stylu Bitcoinu může ověřit vaši platbu kontrolou krátké cesty hashů od vaší transakce až po záhlaví bloku, aniž by stáhla celou historii transakcí.
Zajímavost
Ralph Merkle načrtl tuto myšlenku koncem sedmdesátých let jako studentský projekt a několik let se držela v akademických kruzích, než ji Satoshi použil v Bitcoinu. Důkaz, že dobré nápady stárnou dobře.
Shrnutí
V kostce? Merkle Tree poskytuje rychlé, malé důkazy, že něco patří do velkého souboru, bez zbytečného dramatického ověřování a bez stahování velkého množství dat.