Hash tree

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 5. srpna 2021; kontroly vyžadují 2 úpravy .

Hašovací strom , Merkle strom , se nazývá úplný binární strom , v jehož listových vrcholech jsou umístěny hashe z datových bloků a vnitřní vrcholy obsahují hashe z přidávání hodnot v podřízených vrcholech. Kořenový uzel stromu obsahuje hash celé datové sady, tj. hashovací strom je jednosměrná hashovací funkce. Strom Merkle se používá pro efektivní ukládání transakcí v blockchainu kryptoměn (například v bitcoinech , ethereu ). Umožňuje získat „otisk“ všech transakcí v bloku a také efektivně ověřovat transakce [1] .

Konstrukce

Vyplnění hodnot v uzlech stromu jde zdola nahoru. Nejprve se na každý blok dat použije hašování a tak dále. Výsledné hodnoty se zapisují do listů stromu. Bloky o jednu úroveň výše jsou vyplněny jako hash součtu jejich potomků , kde obvykle znamená zřetězení . Tato operace se opakuje, dokud není získána nejvyšší hodnota - nebo [1] . $Hash_{00}=hash(L_{1})$ $Hash_{01}=hash(L_{2})$ $Hash_{0}=hash(Hash_{00}+Hash_{01})$ $+$ $TopHash$ merkle_root

Bitcoin používá jako svou hashovací funkci double SHA-256 , tedy [1] . Hašovací funkcí však může být cokoliv, například Tiger Tree Hash (TTH), používaný v sítích pro sdílení souborů p2p , je Merkle strom s tigerovou hašovací funkcí [2] . $hash(x)=\operatorname {SHA256} (\operatorname {SHA256} (x))$

Pokud se ukáže, že počet bloků na některé úrovni stromu je lichý, pak je jeden blok duplikován [1] nebo přenesen beze změny na další úroveň, jako se to stává při výpočtu hash Tiger Tree [2] .

Účinnost

Hašovací stromy mají výhodu oproti hašovacím řetězcům nebo hašovacím funkcím. Při použití hash stromů je mnohem méně nákladné prokázat, že určitý datový blok patří do sady. Vzhledem k tomu, že různé bloky jsou často nezávislá data, jako jsou transakce nebo části souborů, zajímá nás možnost kontrolovat pouze jeden blok bez přepočítávání hashů pro ostatní uzly stromu. Nechť je blok, který nás zajímá, tento (viz obr.). Pak důkazem jeho existence a platnosti bude root hash, stejně jako top hashe dalších větví ( a ) [1] [3] . V tomto případě se kontrola nezdaří, pokud . $L_{3}$ ${auth_{L}}_{4}=Hash_{11}$ ${auth_{L}}_{2}=Hash_{0}$ $TopHash\neq hash(Hash_{0}+hash(hash(L_{3})+Hash_{11}))$

Obecně se dá psát

$signature(L)=(L\ |\ {auth_{L}}_{1},\tečky ,{auth_{L}}_{K-1})$ ,

a zkontrolovat jak , kde $TopHash==Hash_{K}$

$Hash_{k}={\begin{cases}hash(L),&{\mbox{if }}k=1,\\hash(Hash_{k-1}+{auth_{L}}_{ k-1}),&{\mbox{if }}2\leq k\leq K\end{cases}}$ .

Sada bloků se nazývá autentizační cesta nebo Merkleova cesta [1] . $\{{auth_{L}}_{1},\tečky ,{auth_{L}}_{K-1}\}$

Je vidět, že výše uvedenou kontrolu lze provádět v krocích, kde je výška stromu nebo délka autentizační cesty a počet datových bloků. Stejná kontrola v případě hash řetězce by byla složitá [1] [4] . $O(K)=O(\log _{2}N)$ $K$ $N$ $NA)$

Níže uvedená tabulka ukazuje, že i při značném počtu transakcí v bloku se nemusíte obávat složitosti výpočtů [1] .

Počet transakcí	Přibližná velikost bloku	Velikost cesty (v hash)	Velikost cesty (v bajtech)
16 transakcí	4 kilobajty	4 hashe	128 bajtů
512 transakcí	128 kilobajtů	9 hashů	288 bajtů
2048 transakcí	512 kilobajtů	11 hashů	352 bajtů
65535 transakcí	16 megabajtů	16 hashů	512 bajtů

Zjednodušené ověření platby

Bitcoinový blok ukládá pouze hodnotu merkle_rootsvých transakcí. To vám umožní získat určité výhody a snížit zatížení sítě.

Po nashromáždění dostatečného počtu bloků lze staré transakce smazat, aby se ušetřilo místo. Samotný blok přitom zůstává nezměněn, protože ukládá pouze merkle_root. Blok bez transakcí zabere 80 B, tedy 4,2 MB za rok (při generování bloku každých 10 minut) [5] .

Je možné zjednodušené ověření platby . Uzel SPV nestahuje celý blok, ale pouze hlavičku bloku. Pro transakci, která ho zajímá, si také vyžádá její autentizační cestu. Stáhne tedy pouze několik kilobajtů, přičemž celková velikost bloku může být více než 10 megabajtů (viz tabulka) [1] . Použití této metody však vyžaduje, aby uživatel důvěřoval hostiteli, ze kterého se bude dotazovat na hlavičky bloků. Jedním ze způsobů, jak se vyhnout útoku, tedy nahrazení uzlu bezohlednou stranou, je posílat výstrahy po celé síti, když je detekována chyba v bloku, což uživatele donutí stáhnout celý blok [5] .

Provoz tzv. „tenkých“ bitcoinových klientů [6] [7] je založen na zjednodušeném ověřování plateb .

Extra

Merkle tree traversal problem

Strom Merkle má i nevýhody, které se projevují rostoucím počtem listů. Jak bylo uvedeno výše, pro výpočet podpisu libovolného bloku potřebujete znát všechny hodnoty ze sady . To není problém, pokud je možné uložit všechny vnitřní uzly stromu do paměti, ale pro velké stromy (počet listů se může zvýšit až na ) to není vhodné. Je také možné pokaždé přepočítat vnitřní bloky, což ale výrazně zpomalí výkon takového systému. Proto vyvstává problém efektivního procházení stromů a generování signatur ( Merkle tree traversal problem ) [4] . K dnešnímu dni existují řešení, která využívají čas a paměť, kde je počet listů. Bylo také prokázáno, že neexistuje žádný algoritmus procházení, který by byl lepší v čase i paměti [8] . $L$ $\{{auth_{L}}_{i}\}$ $2^{40}$ $2\log _{2}(N)$ $3\log _{2}(N)$ $N$ $O(\log _{2}(N))$

Poznámky

↑ 1 2 3 4 5 6 7 8 9 Antonopoulos, Andreas M.,. Mastering bitcoin: odemykání digitálních kryptoměn . - První vydání. — Sebastopol, Kalifornie. — xxi, 272 stran s. — ISBN 9781449374044 . Archivováno 19. ledna 2018 na Wayback Machine
↑ 1 2 J. Chapweske , G. Mohr . Formát Tree Hash EXchange (THEX ) . Společnost Onion Networks Inc. (4. března 2003). - Standard pro výměnu hash stromů přes soubory. Získáno 8. prosince 2017. Archivováno z originálu dne 4. března 2018.
↑ Einar Mykletun , Maithili Narasimha , Gene Tsudik . Poskytování autentizace a integrity v outsourcovaných databázích pomocí Merkle Hash Tree // ACM Transactions on Storage: Journal. - 2006. - Květen ( vol. 2 , č. 2 ). - str. 107-138 . Archivováno z originálu 19. února 2020.
↑ 1 2 Georg Becker, Ruhr-universität Bochum. Podpisová schémata Merkle, stromy Merkle a jejich kryptoanalýza . Archivováno 14. prosince 2017 na Wayback Machine
↑ 1 2 Satoshi Nakamoto. Bitcoin: systém digitálních peer-to-peer hotovosti // bitcoin.org. Archivováno z originálu 5. dubna 2018. (Ruština)
↑ Israa Alqassem, Davor Svetinovic. Směrem k referenční architektuře pro kryptoměny: Bitcoinová architektonická analýza // Mezinárodní konference IEEE o internetu věcí ( iThings) a IEEE Green Computing and Communications (GreenCom) a IEEE Cyber, Physical and Social Computing (CPSCom) : Journal. - 2014. - září. — ISBN 978-1-4799-5967-9 . - doi : 10.1109/iThings.2014.78 . Archivováno z originálu 2. dubna 2018.
↑ Zjednodušené ověření platby . Slovníček bitcoinů . Datum přístupu: 7. prosince 2017. Archivováno z originálu 7. prosince 2017.
↑ Michael Szydlo. Merkle Tree Traversal in Log Space and Time (anglicky) // Advances in Cryptology - EUROCRYPT 2004. - Springer, Berlin, Heidelberg, 2004-05-02. — S. 541–554 . — ISBN 9783540219354 , 9783540246763 . - doi : 10.1007/978-3-540-24676-3_32 . Archivováno z originálu 15. prosince 2017.

Viz také

Odkazy

Merkle Patricia Tree je vylepšená implementace stromu Merkle používaného v Ethereu.
Tiger Tree Torrent je návrh nahradit SHA-1 Tiger Tree Hash v souborech .torrent .

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree