Hash træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 5. august 2021; checks kræver 2 redigeringer .

Et hash-træ , et Merkle -træ kaldes et komplet binært træ , i hvis bladspidser er placeret hashes fra datablokke, og de interne knudepunkter indeholder hashes fra tilføjelse af værdier i underordnede knudepunkter. Træets rodknude indeholder hashen af hele datasættet, dvs. hash-træet er en envejs hashfunktion. Merkle-træet bruges til effektiv opbevaring af transaktioner i blockchain af kryptovalutaer (for eksempel i Bitcoin , Ethereum ). Det giver dig mulighed for at få et "fingeraftryk" af alle transaktioner i blokken, samt effektivt verificere transaktioner [1] .

Bygning

Påfyldningen af værdier i træets noder går fra bund til top. Først anvendes hashing på hver datablok , og så videre. De resulterende værdier skrives til træets blade. Blokke et niveau op er udfyldt som hashes af summen af deres børn , hvor det normalt betyder sammenkædning . Denne operation gentages, indtil topværdien er opnået - eller [1] . $Hash_{00}=hash(L_{1})$ $Hash_{01}=hash(L_{2})$ $Hash_{0}=hash(Hash_{00}+Hash_{01})$ $+$ $TopHash$ merkle_root

Bitcoin bruger dobbelt SHA-256 som sin hash-funktion , dvs. [1] . Imidlertid kan hash-funktionen være hvad som helst, for eksempel er Tiger Tree Hash (TTH), der bruges i p2p-fildelingsnetværk , et Merkle-træ med en Tiger - hash-funktion [2] . $hash(x)=\operatørnavn {SHA256} (\operatørnavn {SHA256} (x))$

Hvis antallet af blokke på et eller andet niveau af træet viser sig at være ulige, så duplikeres en blok [1] eller overføres uændret til det næste niveau, som det sker, når man beregner Tiger Tree Hash [2] .

Effektivitet

Hash-træer har en fordel i forhold til hashkæder eller hashfunktioner. Når du bruger hash-træer, er det meget billigere at bevise, at en bestemt datablok tilhører sættet. Da forskellige blokke ofte er uafhængige data, såsom transaktioner eller dele af filer, er vi interesserede i muligheden for kun at kontrollere én blok uden at genberegne hashes for andre træknuder. Lad den blok, vi er interesseret i, være denne (se fig.). Så vil beviset for dets eksistens og gyldighed være root-hashen, såvel som de øverste hashes af andre grene ( og ) [1] [3] . I dette tilfælde mislykkes kontrollen, hvis . $L_{3}$ ${auth_{L}}_{4}=Hash_{11}$ ${auth_{L}}_{2}=Hash_{0}$ $TopHash\neq hash(Hash_{0}+hash(hash(L_{3})+Hash_{11}))$

Generelt kan man skrive

$signatur(L)=(L\ |\ {auth_{L}}_{1},\dots ,{auth_{L}}_{K-1})$ ,

og tjek hvordan , hvor $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}}$ .

Sættet af blokke kaldes autentificeringsstien eller Merkle-stien [1] . $\{{auth_{L}}_{1},\dots ,{auth_{L}}_{K-1}\}$

Det kan ses, at kontrollen ovenfor kan udføres i trin, hvor er højden af træet eller længden af autentificeringsstien, og er antallet af datablokke. Den samme kontrol i tilfælde af en hashkæde ville have kompleksitet [1] [4] . $O(K)=O(\log _{2}N)$ $K$ $N$ $PÅ)$

Tabellen nedenfor viser, at selv med et betydeligt antal transaktioner i en blok, behøver du ikke bekymre dig om kompleksiteten af beregninger [1] .

Antal transaktioner	Omtrentlig blokstørrelse	Stistørrelse (i hash)	Stistørrelse (i bytes)
16 transaktioner	4 kilobyte	4 hash	128 bytes
512 transaktioner	128 kilobyte	9 hashes	288 bytes
2048 transaktioner	512 kilobyte	11 hashes	352 bytes
65535 transaktioner	16 megabyte	16 hashes	512 bytes

Forenklet betalingsverifikation

En Bitcoin-blok gemmer kun værdien af merkle_rootsine transaktioner. Dette giver dig mulighed for at få visse fordele og reducere belastningen på netværket.

Efter at have akkumuleret et tilstrækkeligt antal blokke, kan gamle transaktioner slettes for at spare plads. Samtidig forbliver selve blokken uændret, da den kun gemmer merkle_root. En blok uden transaktioner fylder 80 B, eller 4,2 MB om året (når en blok genereres hvert 10. minut) [5] .

Forenklet betalingsverifikation bliver mulig . SPV-noden downloader ikke hele blokken, men kun blokhovedet. For transaktionen, der er af interesse for ham, anmoder han også om dens autentificeringssti. Den downloader således kun få kilobyte, mens den samlede blokstørrelse kan være mere end 10 megabyte (se tabel) [1] . Brug af denne metode kræver dog, at brugeren har tillid til værten, hvorfra der kan forespørges efter blokoverskrifter. En måde at undgå et angreb på, det vil sige udskiftning af en node af en skruppelløs part, er at sende advarsler gennem netværket, når der opdages en fejl i en blok, hvilket tvinger brugeren til at downloade hele blokken [5] .

Driften af de såkaldte "tynde" bitcoin-klienter [6] [7] er baseret på forenklet betalingsverifikation .

Ekstra

Merkle træ traversal problem

Merkle-træet har også ulemper, som viser sig med et voksende antal blade. Som vist tidligere, for at beregne signaturen af en vilkårlig blok , skal du kende alle værdierne fra sættet . Dette er ikke et problem, hvis det er muligt at gemme alle træets interne noder i hukommelsen, men for store træer (antallet af blade kan stige op til ) er dette ikke egnet. Det er også muligt at genberegne de interne blokke hver gang, men dette vil sænke ydeevnen af et sådant system betydeligt. Derfor opstår problemet med effektiv trægennemgang og signaturgenerering ( Merkle trægennemløbsproblem ) [4] . Til dato er der løsninger, der bruger tid og hukommelse, hvor er antallet af blade. Det er også blevet bevist, at der ikke findes en traversal-algoritme, der både er bedre i tid og hukommelse [8] . $L$ $\{{auth_{L}}_{i}\}$ $2^{40}$ $2\log _{2}(N)$ $3\log _{2}(N)$ $N$ $O(\log _{2}(N))$

Noter

↑ 1 2 3 4 5 6 7 8 9 Antonopoulos, Andreas M.,. Mestring af bitcoin: oplåsning af digitale kryptovalutaer . — Første udgave. — Sebastopol, CA. — xxi, 272 sider s. — ISBN 9781449374044 . Arkiveret 19. januar 2018 på Wayback Machine
↑ 1 2 J. Chapweske , G. Mohr . Træ Hash EXchange-format (THEX ) . Onion Networks Inc. (4. marts 2003). - Standarden for udveksling af hash-træer over filer. Hentet 8. december 2017. Arkiveret fra originalen 4. marts 2018.
↑ Einar Mykletun , Maithili Narasimha , Gene Tsudik . Levering af autentificering og integritet i outsourcede databaser ved hjælp af Merkle Hash Tree's // ACM Transactions on Storage: Journal. - 2006. - Maj ( bind 2 , nr. 2 ). - S. 107-138 . Arkiveret fra originalen den 19. februar 2020.
↑ 1 2 Georg Becker, Ruhr-universität Bochum. Merkle signaturskemaer, Merkle-træer og deres krypteringsanalyse . Arkiveret 14. december 2017 på Wayback Machine
↑ 1 2 Satoshi Nakamoto. Bitcoin: et system med digitale peer-to-peer kontanter // bitcoin.org. Arkiveret fra originalen den 5. april 2018. (Russisk)
↑ Israa Alqassem, Davor Svetinovic. Towards Reference Architecture for Cryptocurrencies: Bitcoin Architectural Analysis // IEEE International Conference on Internet of Things ( iThings), og IEEE Green Computing and Communications (GreenCom) og IEEE Cyber, Physical and Social Computing (CPSCom) : Journal. - 2014. - September. — ISBN 978-1-4799-5967-9 . - doi : 10.1109/iThings.2014.78 . Arkiveret fra originalen den 2. april 2018.
↑ Forenklet betalingsbekræftelse . Ordliste over Bitcoin . Dato for adgang: 7. december 2017. Arkiveret fra originalen 7. december 2017.
↑ Michael Szydlo. Merkle Tree Traversal in Log Space and Time (engelsk) // 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 . Arkiveret fra originalen den 15. december 2017.

Se også

Links

Merkle Patricia Tree er en forbedret implementering af Merkle-træet, der bruges i Ethereum.
Tiger Tree Torrent er et forslag om at erstatte SHA-1 med Tiger Tree Hash i .torrent - filer.

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge 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 Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE

Træ (datastruktur)
Binært søgetræ Træ (grafteori) træstruktur
Binære træer	binært træ T-træ
Selvbalancerende binære træer	AA træ AVL træ Rød-sort træ Splay træ træ med bøder kartesisk træ Fibonacci træ B-træ T-træ
B-træer	2-3-træ B⁺-træ B*-træ B x -træ UB træ 2-3-4 træ (a,b)-træ dansende træ
præfiks træer	suffiks træ Komprimeret præfikstræ Ternært søgetræ
Binær opdeling af rummet	k-dimensionelt træ VP træ
Ikke-binære træer	Quadtree oktre Sparsom Voxel Octree eksponentielt træ PQ træ
At bryde rummet op	R-træ Hilbert R-træ R+-træ R*-træ X-træ M-træ Fenwick træ Segmenttræ
Andre træer	dynge hash træ fingertræ metrisk træ Belægning træ BK-træ Dobbeltkædet træ iDistance Linkskåret træ LSM træ
Algoritmer	Bredde først søgning Dybde første søgning DSW algoritme spanning tree protokol