Hash puu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 5. elokuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Hajapuuta eli Merkle - puuta kutsutaan täydelliseksi binääripuuksi , jonka lehtipisteisiin sijoitetaan tietolohkojen tiivisteet ja sisäiset kärjet sisältävät hajautusarvoja alipisteissä olevien arvojen lisäämisestä . Puun juurisolmu sisältää koko tietojoukon tiivisteen, eli tiivistepuu on yksisuuntainen hajautusfunktio. Merkle-puuta käytetään transaktioiden tehokkaaseen tallentamiseen kryptovaluuttojen lohkoketjussa (esimerkiksi Bitcoinissa , Ethereumissa ). Sen avulla voit saada "sormenjäljen" kaikista lohkon tapahtumista sekä tarkistaa tapahtumat tehokkaasti [1] .

Rakennus

Puun solmujen arvojen täyttö tapahtuu alhaalta ylös. Ensinnäkin jokaiseen tietolohkoon sovelletaan tiivistystä ja niin edelleen. Tuloksena saadut arvot kirjoitetaan puun lehtiin. Yhden tason ylemmät lohkot täytetään tiivisteinä niiden lasten summasta, mikä tarkoittaa yleensä ketjuttamista . Tätä toimenpidettä toistetaan, kunnes saavutetaan suurin arvo - tai [1] . $Hash_{00}=hash(L_{1})$ $Hash_{01}=hash(L_{2})$ $Hash_{0}=hash(Hash_{00}+Hash_{01})$ $+$ $TopHash$ merkle_root

Bitcoin käyttää kaksois -SHA-256 :ta hash-funktionaan , eli [1] . Hash-funktio voi kuitenkin olla mikä tahansa, esimerkiksi p2p-tiedostonjakoverkoissa käytetty Tiger Tree Hash (TTH) on Merkle-puu, jossa on Tiger hash -funktio [2] . $hash(x)=\operaattorin nimi {SHA256} (\operaattorin nimi {SHA256} (x))$

Jos lohkojen määrä jollain puun tasolla osoittautuu parittomaksi, niin yksi lohko monistetaan [1] tai siirretään muuttumattomana seuraavalle tasolle, kuten tapahtuu Tiger Tree Hash -arvoa laskettaessa [2] .

Tehokkuus

Hash-puilla on etu hash-ketjuihin tai hash-funktioihin verrattuna. Hash-puita käytettäessä on paljon halvempaa todistaa, että tietty tietolohko kuuluu joukkoon. Koska eri lohkot ovat usein itsenäisiä tietoja, kuten tapahtumia tai tiedostojen osia, olemme kiinnostuneita mahdollisuudesta tarkistaa vain yksi lohko laskematta uudelleen hajautusarvoja muille puusolmuille. Olkoon meitä kiinnostava lohko tämä (katso kuva). Silloin todiste sen olemassaolosta ja pätevyydestä on juurihaja, samoin kuin muiden haarojen ylimmät tiivisteet ( ja ) [1] [3] . Tässä tapauksessa tarkistus epäonnistuu, jos . $L_{3}$ ${auth_{L}}_{4}=Hash_{11}$ ${auth_{L}}_{2}=Hash_{0}$ $TopHash\neq hash(Hash_{0}+hash(hash(L_{3})+Hash_{11}))$

Yleensä voi kirjoittaa

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

ja tarkista miten , missä $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}}$ .

Lohkojen joukkoa kutsutaan autentikointipoluksi tai Merkle-poluksi [1] . $\{{auth_{L}}_{1},\dots ,{auth_{L}}_{K-1}\}$

Voidaan nähdä, että yllä oleva tarkistus voidaan suorittaa vaiheittain, missä on puun korkeus tai todennuspolun pituus ja tietolohkojen lukumäärä. Sama tarkistus hash-ketjun tapauksessa olisi monimutkainen [1] [4] . $O(K)=O(\log _{2}N)$ $K$ $N$ $PÄÄLLÄ)$

Alla oleva taulukko osoittaa, että vaikka lohkossa olisi huomattava määrä tapahtumia, sinun ei tarvitse huolehtia laskelmien monimutkaisuudesta [1] .

Tapahtumien määrä	Arvioitu lohkon koko	Polun koko (tiivisteinä)	Polun koko (tavuina)
16 tapahtumaa	4 kilotavua	4 tiivistettä	128 tavua
512 tapahtumaa	128 kilotavua	9 tiivistettä	288 tavua
2048 tapahtumaa	512 kilotavua	11 tiivistettä	352 tavua
65535 tapahtumaa	16 megatavua	16 tiivistettä	512 tavua

Yksinkertaistettu maksun vahvistus

Bitcoin-lohko tallentaa vain merkle_roottapahtumiensa arvon. Näin voit saada tiettyjä etuja ja vähentää verkon kuormitusta.

Kun riittävä määrä lohkoja on kertynyt, vanhat tapahtumat voidaan poistaa tilan säästämiseksi. Samanaikaisesti itse lohko pysyy muuttumattomana, koska se tallentaa vain merkle_root. Lohko ilman tapahtumia vie 80 B tai 4,2 Mt vuodessa (kun lohko luodaan 10 minuutin välein) [5] .

Yksinkertainen maksun vahvistus tulee mahdolliseksi . SPV-solmu ei lataa koko lohkoa, vaan vain lohkootsikon. Häntä kiinnostavaa tapahtumaa varten hän pyytää myös sen todennuspolkua. Siten se lataa vain muutaman kilotavun, kun taas lohkon kokonaiskoko voi olla yli 10 megatavua (katso taulukko) [1] . Tämän menetelmän käyttäminen edellyttää kuitenkin, että käyttäjä luottaa isäntään, josta hän pyytää lohkootsikoita. Eräs tapa välttää hyökkäys eli solmun korvaaminen häikäilemättömän osapuolen toimesta on lähettää hälytyksiä koko verkkoon, kun lohkossa havaitaan virhe, jolloin käyttäjän on ladattava koko lohko [5] .

Niin kutsuttujen "ohuiden" bitcoin-asiakkaiden [6] [7] toiminta perustuu yksinkertaistettuun maksun varmentamiseen .

Ekstrat

Merkle-puun läpikulkuongelma

Merkle-puulla on myös haittoja, jotka ilmenevät kasvavalla lehtimäärällä. Kuten aiemmin näytettiin, mielivaltaisen lohkon allekirjoituksen laskemiseksi sinun on tiedettävä kaikki joukon arvot . Tämä ei ole ongelma, jos on mahdollista tallentaa kaikki puun sisäiset solmut muistiin, mutta suurille puille (lehtien lukumäärä voi kasvaa jopa ) tämä ei sovellu. On myös mahdollista laskea sisäiset lohkot uudelleen joka kerta, mutta tämä hidastaa merkittävästi tällaisen järjestelmän suorituskykyä. Tästä syystä puun tehokkaan läpikäynnin ja allekirjoituksen luomisen ongelma syntyy ( Merkle tree traversal problem ) [4] . Tähän mennessä on olemassa aikaa ja muistia käyttäviä ratkaisuja, missä on lehtien määrä. On myös todistettu, ettei ole olemassa ajallisesti ja muistissa parempaa läpikulkualgoritmia [8] . $L$ $\{{auth_{L}}_{i}\}$ $2^{40}$ $2\log _{2}(N)$ $3\log _{2}(N)$ $N$ $O(\log _{2}(N))$

Muistiinpanot

↑ 1 2 3 4 5 6 7 8 9 Antonopoulos, Andreas M.,. Bitcoinin hallitseminen: digitaalisten kryptovaluuttojen lukituksen avaaminen . - Ensimmäinen painos. - Sebastopol, CA — xxi, 272 sivua s. — ISBN 9781449374044 . Arkistoitu 19. tammikuuta 2018 Wayback Machinessa
↑ 1 2 J. Chapweske , G. Mohr . Tree Hash Exchange -muoto (THEX ) . Onion Networks Inc. (4. maaliskuuta 2003). - Standardi hash-puiden vaihtamiseen tiedostojen välillä. Haettu 8. joulukuuta 2017. Arkistoitu alkuperäisestä 4. maaliskuuta 2018.
↑ Einar Mykletun , Maithili Narasimha , Gene Tsudik . Todennuksen ja eheyden tarjoaminen ulkoistetuissa tietokantoissa Merkle Hash Treen avulla // ACM Transactions on Storage : Journal. - 2006. - Toukokuu ( osa 2 , nro 2 ). - s. 107-138 . Arkistoitu alkuperäisestä 19. helmikuuta 2020.
↑ 1 2 Georg Becker, Ruhr-universität Bochum. Merklen allekirjoitusjärjestelmät, Merkle-puut ja niiden krypta-analyysi . Arkistoitu 14. joulukuuta 2017 Wayback Machineen
↑ 1 2 Satoshi Nakamoto. Bitcoin: digitaalisen peer-to-peer käteisen järjestelmä // bitcoin.org. Arkistoitu alkuperäisestä 5. huhtikuuta 2018. (Venäjän kieli)
↑ Israa Alqassem, Davor Svetinovic. Kohti kryptovaluuttojen vertailuarkkitehtuuria: Bitcoin Architectural Analysis // IEEE International Conference on Internet of Things ( iThings) ja IEEE Green Computing and Communications (GreenCom) ja IEEE Cyber, Physical and Social Computing (CPSCom): Journal. - 2014 - syyskuu. — ISBN 978-1-4799-5967-9 . - doi : 10.1109/iThings.2014.78 . Arkistoitu alkuperäisestä 2. huhtikuuta 2018.
↑ Yksinkertaistettu maksun vahvistus . Bitcoinin sanasto . Käyttöpäivä: 7. joulukuuta 2017. Arkistoitu alkuperäisestä 7. joulukuuta 2017.
↑ Michael Szydlo. Merkle Tree Traversal in Log Space and Time (englanniksi) // Advances in Cryptology - EUROCRYPT 2004. - Springer, Berliini, Heidelberg, 2004-05-02. — s. 541–554 . — ISBN 9783540219354 , 9783540246763 . - doi : 10.1007/978-3-540-24676-3_32 . Arkistoitu alkuperäisestä 15. joulukuuta 2017.

Katso myös

Linkit

Merkle Patricia Tree on Ethereumissa käytetyn Merkle-puun parannettu toteutus.
Tiger Tree Torrent on ehdotus SHA-1 :n korvaamiseksi Tiger Tree Hashilla .torrent - tiedostoissa.

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga 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 Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla