Hash fa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. augusztus 5-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A hash-fát , a Merkle - fát teljes bináris fának nevezzük , amelynek levélcsúcsaiban az adatblokkokból származó hash -ek, a belső csúcsok pedig a gyermekcsúcsokban hozzáadott értékekből származó hash-eket tartalmaznak. A fa gyökércsomópontja a teljes adathalmaz hash-ét tartalmazza, azaz a hash fa egy egyirányú hash függvény. A Merkle-fát a tranzakciók hatékony tárolására használják a kriptovaluták blokkláncában (például Bitcoinban , Ethereumban ). Lehetővé teszi, hogy "ujjlenyomatot" kapjon a blokkban lévő összes tranzakcióról, valamint hatékonyan ellenőrizze a tranzakciókat [1] .

Épület

Az értékek kitöltése a fa csomópontjaiban alulról felfelé halad. Először is a rendszer minden adatblokkra kivonatolást alkalmaz , és így tovább. A kapott értékeket a fa leveleire írják. Az egy szinttel feljebb lévő blokkok a gyermekeik összegének hash-jeként vannak kitöltve , ahol általában összefűzést jelent . Ezt a műveletet addig ismételjük, amíg el nem érjük a felső értéket - vagy [1] . $Hash_{00}=hash(L_{1})$ $Hash_{01}=hash(L_{2})$ $Hash_{0}=hash(Hash_{00}+Hash_{01})$ $+$ $TopHash$ merkle_root

A Bitcoin kettős SHA-256- ot használ hash függvényként , azaz [1] . A hash függvény azonban bármi lehet, például a p2p fájlmegosztó hálózatokban használt Tiger Tree Hash (TTH) egy Merkle-fa Tiger hash funkcióval [2] . $hash(x)=\operátornév {SHA256} (\operátornév {SHA256} (x))$

Ha a blokkok száma a fa valamely szintjén páratlannak bizonyul, akkor az egyik blokk megkettőződik [1] , vagy változatlanul átkerül a következő szintre, ahogy az a Tiger Tree Hash [2] kiszámításakor történik .

Hatékonyság

A hash fák előnyt élveznek a hash láncokkal vagy a hash függvényekkel szemben. Hash-fák használatakor sokkal olcsóbb annak bizonyítása, hogy egy adott adatblokk a halmazhoz tartozik. Mivel a különböző blokkok gyakran független adatok, például tranzakciók vagy fájlok részei, érdekel bennünket, hogy csak egy blokkot ellenőrizzünk anélkül, hogy a többi fa csomópontjához újra kellene számítani a hash-eket. Legyen ez a minket érdeklő blokk (lásd ábra). Ekkor létezésének és érvényességének bizonyítéka a gyökérkivonat, valamint más ágak felső hash-ei ( és ) [1] [3] . Ebben az esetben az ellenőrzés sikertelen, ha . $L_{3}$ ${auth_{L}}_{4}=Hash_{11}$ ${auth_{L}}_{2}=Hash_{0}$ $TopHash\neq hash(Hash_{0}+hash(hash(L_{3})+Hash_{11}))$

Általában lehet írni

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

és ellenőrizze, hogyan , hol $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}}$ .

A blokkok halmazát hitelesítési útvonalnak vagy Merkle útvonalnak [1] nevezzük . $\{{auth_{L}}_{1},\dots ,{auth_{L}}_{K-1}\}$

Látható, hogy a fenti ellenőrzés lépésenként hajtható végre, ahol a fa magassága vagy a hitelesítési út hossza, illetve az adatblokkok száma. Ugyanez az ellenőrzés egy hash lánc esetén bonyolult lenne [1] [4] . $O(K)=O(\log _{2}N)$ $K$ $N$ $TOVÁBB)$

Az alábbi táblázat bemutatja, hogy még jelentős számú tranzakció esetén sem kell aggódnia a számítások bonyolultsága miatt [1] .

Tranzakciók száma	Hozzávetőleges blokkméret	Útvonal mérete (kivonatokban)	Útvonal mérete (bájtban)
16 tranzakció	4 kilobájt	4 hash	128 bájt
512 tranzakció	128 kilobájt	9 hash	288 bájt
2048 tranzakció	512 kilobájt	11 hash	352 bájt
65535 tranzakció	16 megabájt	16 hash	512 bájt

Egyszerűsített fizetési ellenőrzés

merkle_rootA Bitcoin blokk csak a tranzakcióinak értékét tárolja . Ez lehetővé teszi bizonyos előnyök megszerzését és a hálózat terhelésének csökkentését.

Elegendő számú blokk felhalmozása után a régi tranzakciók helytakarékosság céljából törölhetők. Ugyanakkor maga a blokk változatlan marad, mivel csak a merkle_root. Egy tranzakció nélküli blokk 80 B-t, vagyis 4,2 MB-ot foglal el évente (amikor 10 percenként generálódik egy blokk) [5] .

Lehetővé válik az egyszerűsített fizetési ellenőrzés . Az SPV csomópont nem tölti le a teljes blokkot, hanem csak a blokkfejlécet. Az őt érdeklő tranzakcióhoz annak hitelesítési útvonalát is kéri. Így csak néhány kilobájtot tölt le, miközben a teljes blokkméret több mint 10 megabájt lehet (lásd a táblázatot) [1] . Ennek a módszernek a használata azonban megköveteli, hogy a felhasználó megbízzon abban a gazdagépben, amelyről a blokkfejléceket lekérdezheti. A támadások elkerülésének, vagyis a csomópont gátlástalan fél általi helyettesítésének egyik módja az, hogy riasztásokat küldenek a hálózaton, ha hibát észlel egy blokkban, és arra kényszeríti a felhasználót, hogy töltse le a teljes blokkot [5] .

Az úgynevezett "vékony" bitcoin kliensek [6] [7] működése az egyszerűsített fizetés-ellenőrzésen alapul .

Extrák

Merkle fa bejárási probléma

A Merkle-fának vannak hátrányai is, amelyek a levelek növekedésével nyilvánulnak meg. Mint korábban bemutattuk, egy tetszőleges blokk aláírásának kiszámításához ismernie kell a halmaz összes értékét . Ez nem probléma, ha a fa összes belső csomópontját el lehet tárolni a memóriában, de nagy fáknál (a levelek száma akár ig is növekedhet ) ez nem megfelelő. Lehetőség van arra is, hogy minden alkalommal újraszámolják a belső blokkokat, de ez jelentősen lelassítja egy ilyen rendszer teljesítményét. Ezért felmerül a hatékony fa bejárás és aláírás generálás problémája ( Merkle tree traversal problem ) [4] . A mai napig vannak időt és memóriát használó megoldások, hol van a levelek száma. Az is bebizonyosodott, hogy nincs olyan bejárási algoritmus, amely mind időben, mind memóriában jobb lenne [8] . $L$ $\{{auth_{L}}_{i}\}$ $2^{40}$ $2\log _{2}(N)$ $3\log _{2}(N)$ $N$ $O(\log _{2}(N))$

Jegyzetek

↑ 1 2 3 4 5 6 7 8 9 Antonopoulos, Andreas M.,. A bitcoin elsajátítása: digitális kriptovaluták feloldása . - Első kiadás. – Sebastopol, CA. — xxi, 272 oldal p. — ISBN 9781449374044 . Archivált : 2018. január 19. a Wayback Machine -nél
↑ 1 2 J. Chapweske , G. Mohr . Fa hash csereformátum (THEX ) . Onion Networks Inc. (2003. március 4.). - A szabvány a hash-fák fájlok közötti cseréjéhez. Letöltve: 2017. december 8. Az eredetiből archiválva : 2018. március 4..
↑ Einar Mykletun , Maithili Narasimha , Gene Tsudik . Hitelesítés és integritás biztosítása kiszervezett adatbázisokban a Merkle Hash Tree segítségével // ACM Transactions on Storage : Journal. - 2006. - május ( 2. köt. , 2. sz. ). - 107-138 . o . Archiválva az eredetiből: 2020. február 19.
↑ 1 2 Georg Becker, Ruhr-universität Bochum. Merkle aláírási sémák, Merkle fák és kriptoanalízisük . Archiválva : 2017. december 14. a Wayback Machine -nál
↑ 1 2 Satoshi Nakamoto. Bitcoin: a digitális peer-to-peer készpénz rendszere // bitcoin.org. Archiválva az eredetiből 2018. április 5-én. (Orosz)
↑ Israa Alqassem, Davor Svetinovic. Towards Reference Architecture for Cryptocurrencies: Bitcoin Architectural Analysis // IEEE International Conference on Internet of Things ( iThings), valamint IEEE Green Computing and Communications (GreenCom) és IEEE Cyber, Physical and Social Computing (CPSCom): Journal. - 2014. - szeptember. — ISBN 978-1-4799-5967-9 . - doi : 10.1109/iThings.2014.78 . Archiválva az eredetiből 2018. április 2-án.
↑ Egyszerűsített fizetés -ellenőrzés . A Bitcoin szószedete . Hozzáférés dátuma: 2017. december 7. Az eredetiből archiválva : 2017. december 7.
↑ Michael Szydlo. Merkle Tree Traversal in Log Space and Time (angol) // Advances in Cryptology - EUROCRYPT 2004. - Springer, Berlin, Heidelberg, 2004-05-02. — P. 541–554 . — ISBN 9783540219354 , 9783540246763 . - doi : 10.1007/978-3-540-24676-3_32 . Az eredetiből archiválva: 2017. december 15.

Lásd még

Linkek

A Merkle Patricia Tree az Ethereumban használt Merkle fa továbbfejlesztett megvalósítása.
A Tiger Tree Torrent egy olyan javaslat, amely az SHA-1- et Tiger Tree Hash -re cseréli a .torrent fájlokban.

Hash függvények
Általános rendeltetésű	Adler-32 CRC Fletcher ellenőrző összeg FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH – Hash Tree jenkins hash hash összeg
Kriptográfia	Stribog GOST R 34.11-94 Öv BLAKE BMW CubeHash VISSZHANG edonkey2k FSB Fúga 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 Bőr Snefru Tigris Örvény
Kulcsgenerálási funkciók	bcrypt PBKDF2 scrypt Argon2 Lyra2
Csekkszám ( összehasonlítás )	Ellenőrző összeg Verhouff algoritmusa Hold algoritmus Damm algoritmus Vonalkód bankszámlák bankkártyák VAN SNILS OKPO ÓN OKATO ISBN OGRN és OGRNIP VIN
Hashes	A csekkszámok összehasonlítása Hitelesítési protokollok Vonalkód összehasonlítás Kriptográfia Mágneses kapcsolat Merkle aláírása ed2k URNA

Fa (adatstruktúra)
Bináris keresőfa Fa (gráfelmélet) fa szerkezet
Bináris fák	bináris fa T-fa
Önkiegyensúlyozó bináris fák	AA fa AVL fa Vörös-fekete fa Splay fa fa bírságokkal karteziánus fa Fibonacci fa B-fa T-fa
B-fák	2-3-fa B⁺-fa B*-fa B x -fa UB fa 2-3-4 fa (a,b)-fa táncoló fa
előtag fák	utótag fa Tömörített előtag fa hármas keresőfa
A tér bináris particionálása	k-dimenziós fa VP fa
Nem bináris fák	Quadtree oktfa Ritka Voxel Octree exponenciális fa PQ fa
A tér felosztása	R-fa Hilbert R-fa R+-fa R*-fa X-fa M-fa Fenwick fa Szegmens fa
Más fák	halom hash fa ujjfa metrikus fa Bevonat fa BK-fa Kétláncú fa iDistance Link-vágott fa LSM fa
Algoritmusok	Szélesség első keresés Mélységi első keresés DSW algoritmus átívelő fa protokoll