Ralph C. Merkle je kryptograf, jehož práce patří k základům moderní kryptografie. Merkleovy hádanky řeší vytvoření společného tajemství přes odposlouchávané spojení; Merkle Tree umožňuje ověřit, že údaj patří do určitého seznamu, aniž musíme stáhnout celý seznam. Jsou to různé úlohy a ani jedna sama nerozhoduje o platnosti bitcoinových transakcí.
Chcete poslat zašifrovanou zprávu. Příjemce k jejímu přečtení potřebuje tajný klíč, ale jak mu ho předat, když někdo sleduje celou komunikaci? Ralph Merkle v článku z roku 1978 popsal překvapivý postup: odesílatel připraví mnoho zašifrovaných hádanek, příjemce náhodně vybere a vyřeší jednu a veřejně vrátí její identifikátor, ukrytý uvnitř. Oba tím zjistí společný klíč. Posluchač identifikátor také vidí, ale neví, ve které hádance byl. V popsaném modelu proto potřebuje výrazně více práce: jeho náklady rostou kvadraticky vůči velikosti úlohy, zatímco práce účastníků roste lineárně. Jde o kvadratický, nikoli exponenciální rozdíl; historický průlom není dnešní doporučení, jak šifrovat zprávy. [1]
Pro pochopení článku z roku 1978 je podstatné, co protivník smí. Může poslouchat, ale zachovává se předpoklad zjistitelné změny či padělání zpráv. Představte si někoho, kdo čte dopisy, a někoho, kdo je navíc přepisuje a podepisuje vaším jménem. Druhý případ potřebuje další ochranu: ověřit, s kým vlastně mluvíte. Samotný rozdíl ve výpočetní práci tuto otázku neřeší. Proto nelze z hádanek vyvozovat, že libovolná komunikace přes aktivního prostředníka je bezpečná. Jejich přínosem je ukázat možnost dohody bez předem sdíleného tajného klíče za uvedených předpokladů. [1]
Jinou otázku řeší Merkle Tree, autentizační strom popsaný v Merkleově disertaci z roku 1979. Představte si archiv smluv: chcete ověřit konkrétní smlouvu, ale nestahovat celý archiv. Z každé položky se vypočte hash, krátký digitální otisk. Otisky se po dvojicích spojují a znovu hashují, až zbude společný kořen stromu. Hashování obsah nešifruje; umožňuje ověřovat shodu. Aby kontrola měla smysl, potřebujete předem autentizovaný kořen, tedy ověřený otisk správného archivu. Kdyby vám podvodník mohl dodat vlastní dokument i libovolný kořen, jejich vzájemná shoda by nic neprokazovala o původním archivu. [2]
Vezměme vyvážený binární strom s 8 položkami. K ověření vybraného listu potřebujete 3 sousední hashe: na každé úrovni jeden otisk vedlejší větve. Z vlastního listu a těchto otisků postupně dopočítáte kořen a porovnáte ho s ověřeným kořenem. Samotný list ani kořen se do těchto pomocných hashů nepočítají. Musíte také znát strukturu stromu a pořadí spojování, tedy zda soused patří vlevo, nebo vpravo. Úspora není trik se skrytými daty: vzdálené části archivu zastupují jejich otisky. Celé cizí dokumenty proto pro tuto konkrétní kontrolu nepotřebujete. [2]
Merkle Tree dokládá vztah mezi položkou a daným souborem dat. Chybný údaj tím ale nezíská pravdivost. Do našeho archivu lze uložit i smlouvu s nesprávným jménem; důkaz může správně potvrdit její zařazení, aniž odhalí chybu ve jméně. Podobně otisk neověřuje oprávnění člověka, který dokument vytvořil. Je proto dobré oddělit otázky: odpovídá položka tomuto kořeni, odkud znám kořen a podle jakých pravidel přijímám obsah? Právě toto rozlišení pomáhá porozumět tomu, co stejná technika umí v Bitcoinu a co za ni musí udělat jiné části systému. [2]
Bitcoin používá Merkle Tree k propojení transakcí s hlavičkou bloku, jeho stručným záznamem. Kořen je součástí hlavičky; změna zahrnutých transakcí se promítne do jejich společného otisku. Satoshi Nakamoto tuto konstrukci popisuje v části 7 whitepaperu a Merkleovu práci uvádí mezi zdroji. To dokládá technický vliv, nikoli autorství Bitcoinu. Merkleho strom nevybírá platnou historii a neověřuje podpisy transakcí za uzly. Bitcoin jej spojuje s dalšími pravidly, včetně ověřování transakcí a Proof of Work, tedy důkazu výpočetní práce. Pochopení jedné součásti je užitečnější než připsat jí schopnosti celého systému. [3]
Část 8 whitepaperu popisuje SPV, zjednodušené ověřování plateb. Lehký klient pracuje s hlavičkami bloků a větví stromu, která propojí transakci s vybraným blokem. Ušetří tím data, ale přebírá předpoklady o řetězci s největší kumulovanou prací a chování těžařů. Samotný důkaz zařazení nekontroluje všechna pravidla transakcí jako Full Node, plně ověřující uzel. Nepotvrzuje ani, že konkrétní výstup později nebyl utracen: k tomu by bylo potřeba znát následné dění. Pro začátečníka je klíčové nepovažovat větu „tato platba je v tomto bloku“ za úplné ověření peněz, které jsou právě k dispozici. [3]
Disertace z roku 1979 používá autentizační strom také pro sadu jednorázových digitálních podpisů. Digitální podpis umožňuje ověřit, že zprávu schválil držitel příslušného tajného klíče; není to obrázek podpisu na papíře. Strom může propojit mnoho ověřovacích hodnot s jediným známým kořenem. V popsané konstrukci je však zásoba podpisů konečná a kořen se musí časem obnovit. Nelze z toho odvodit neomezené opakování stejného jednorázového klíče. Tato pokročilejší větev Merkleovy práce ukazuje společný motiv: ověřit potřebnou část pomocí malého důkazu, přitom přesně vědět, na čem ověření stojí. [2]
Pro nejúplnější obraz čtěte toto heslo společně s David Chaum, Timothy May, Merkle Tree, Block Header. Opačným směrem na něj odkazují také David Chaum, Timothy May.