Haschträd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 5 augusti 2021; kontroller kräver 2 redigeringar .

Ett hash-träd , ett Merkle- träd kallas ett komplett binärt träd , i vars bladhörn placeras hash från datablock, och de interna hörnen innehåller hash från att lägga till värden i underordnade hörn. Trädets rotnod innehåller hash för hela datamängden, dvs hashträdet är en enkelriktad hashfunktion. Merkle-trädet används för effektiv lagring av transaktioner i blockkedjan av kryptovalutor (till exempel i Bitcoin , Ethereum ). Det låter dig få ett "fingeravtryck" av alla transaktioner i blocket, samt effektivt verifiera transaktioner [1] .

Byggnad

Fyllningen av värden i trädets noder går från botten till toppen. Först tillämpas hashing på varje datablock , och så vidare. De resulterande värdena skrivs till trädets löv. Block en nivå upp fylls i som hash av summan av deras barn , där vanligtvis betyder sammanlänkning . Denna operation upprepas tills toppvärdet erhålls - eller [1] . $Hash_{00}=hash(L_{1})$ $Hash_{01}=hash(L_{2})$ $Hash_{0}=hash(Hash_{00}+Hash_{01})$ $+$ $TopHash$ merkle_root

Bitcoin använder dubbel SHA-256 som sin hashfunktion , dvs [1] . Hashfunktionen kan dock vara vad som helst, till exempel är Tiger Tree Hash (TTH), som används i p2p fildelningsnätverk, ett Merkle- träd med en Tiger - hashfunktion [2] . $hash(x)=\operatörsnamn {SHA256} (\operatörsnamn {SHA256} (x))$

Om antalet block på någon nivå av trädet visar sig vara udda, så dupliceras ett block [1] eller förs över oförändrat till nästa nivå, vilket händer när man beräknar Tiger Tree Hash [2] .

Effektivitet

Hashträd har en fördel framför haschkedjor eller hashfunktioner. När du använder hashträd är det mycket billigare att bevisa att ett visst datablock tillhör uppsättningen. Eftersom olika block ofta är oberoende data, såsom transaktioner eller delar av filer, är vi intresserade av möjligheten att kontrollera endast ett block utan att räkna om hash för andra trädnoder. Låt blocket vi är intresserade av vara detta (se fig.). Då kommer beviset på dess existens och giltighet att vara rothashen, såväl som topphascharna för andra grenar ( och ) [1] [3] . I det här fallet misslyckas kontrollen om . $L_{3}$ ${auth_{L}}_{4}=Hash_{11}$ ${auth_{L}}_{2}=Hash_{0}$ $TopHash\neq hash(Hash_{0}+hash(hash(L_{3})+Hash_{11}))$

I allmänhet kan man skriva

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

och kolla hur , var $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}}$ .

Uppsättningen av block kallas autentiseringsvägen eller Merkle-vägen [1] . $\{{auth_{L}}_{1},\dots ,{auth_{L}}_{K-1}\}$

Det kan ses att kontrollen ovan kan utföras i steg, där är höjden på trädet eller längden på autentiseringsvägen, och är antalet datablock. Samma kontroll i fallet med en hashkedja skulle ha komplexitet [1] [4] . $O(K)=O(\log _{2}N)$ $K$ $N$ $PÅ)$

Tabellen nedan visar att även med ett betydande antal transaktioner i ett block behöver du inte oroa dig för komplexiteten i beräkningarna [1] .

Antal transaktioner	Ungefärlig blockstorlek	Sökvägsstorlek (i hash)	Sökvägsstorlek (i byte)
16 transaktioner	4 kilobyte	4 hash	128 byte
512 transaktioner	128 kilobyte	9 hash	288 byte
2048 transaktioner	512 kilobyte	11 hash	352 byte
65535 transaktioner	16 megabyte	16 hash	512 byte

Förenklad betalningsverifiering

Ett Bitcoin-block lagrar bara värdet av merkle_rootsina transaktioner. Detta gör att du kan få vissa fördelar och minska belastningen på nätverket.

Efter att ha samlat ett tillräckligt antal block kan gamla transaktioner raderas för att spara utrymme. Samtidigt förblir själva blocket oförändrat, eftersom det endast lagrar merkle_root. Ett block utan transaktioner tar upp 80 B, eller 4,2 MB per år (när ett block genereras var 10:e minut) [5] .

Förenklad betalningsverifiering blir möjlig . SPV-noden laddar inte ner hela blocket, utan bara blockhuvudet. För transaktionen av intresse för honom begär han också dess autentiseringsväg. Således laddar den bara ned några få kilobyte, medan den totala blockstorleken kan vara mer än 10 megabyte (se tabell) [1] . Att använda den här metoden kräver dock att användaren litar på den värd från vilken man kan fråga efter blockrubriker. Ett sätt att undvika en attack, d.v.s. ersättning av en nod av en skrupelfri part, är att skicka varningar i hela nätverket när ett fel upptäcks i ett block, vilket tvingar användaren att ladda ner hela blocket [5] .

Driften av de så kallade "tunna" bitcoinklienterna [6] [7] är baserad på förenklad betalningsverifiering .

Extra

Merkle tree traversal problem

Merkleträdet har också nackdelar, som visar sig med ett växande antal löv. Som visats tidigare, för att beräkna signaturen för ett godtyckligt block , måste du känna till alla värden från uppsättningen . Detta är inget problem om det är möjligt att lagra alla interna noder i trädet i minnet, men för stora träd (antalet löv kan öka upp till ) är detta inte lämpligt. Det är också möjligt att räkna om de interna blocken varje gång, men detta kommer avsevärt att bromsa prestandan för ett sådant system. Därför uppstår problemet med effektiv trädgenomgång och signaturgenerering ( Merkle tree traversal problem ) [4] . Hittills finns det lösningar som använder tid och minne, där är antalet löv. Det har också bevisats att det inte finns någon traversalalgoritm som är både bättre i tid och minne [8] . $L$ $\{{auth_{L}}_{i}\}$ $2^{40}$ $2\log _{2}(N)$ $3\log _{2}(N)$ $N$ $O(\log _{2}(N))$

Anteckningar

↑ 1 2 3 4 5 6 7 8 9 Antonopoulos, Andreas M.,. Att bemästra bitcoin: låsa upp digitala kryptovalutor . - Första upplagan. — Sebastopol, CA. — xxi, 272 sidor sid. — ISBN 9781449374044 . Arkiverad 19 januari 2018 på Wayback Machine
↑ 1 2 J. Chapweske , G. Mohr . Tree Hash EXchange-format (THEX ) . Onion Networks Inc. (4 mars 2003). - Standarden för att utbyta hashträd över filer. Hämtad 8 december 2017. Arkiverad från originalet 4 mars 2018.
↑ Einar Mykletun , Maithili Narasimha , Gene Tsudik . Tillhandahålla autentisering och integritet i outsourcade databaser med Merkle Hash Tree's // ACM Transactions on Storage : Journal. - 2006. - Maj ( vol. 2 , nr 2 ). - S. 107-138 . Arkiverad från originalet den 19 februari 2020.
↑ 1 2 Georg Becker, Ruhr-universität Bochum. Merkle signaturscheman, Merkle-träd och deras krypteringsanalys . Arkiverad 14 december 2017 på Wayback Machine
↑ 1 2 Satoshi Nakamoto. Bitcoin: ett system med digitala peer-to-peer kontanter // bitcoin.org. Arkiverad från originalet den 5 april 2018. (ryska)
↑ Israa Alqassem, Davor Svetinovic. Mot referensarkitektur för kryptovalutor: Bitcoin Architectural Analysis // IEEE International Conference on Internet of Things ( iThings), och IEEE Green Computing and Communications (GreenCom) och IEEE Cyber, Physical and Social Computing (CPSCom) : Journal. - 2014. - September. — ISBN 978-1-4799-5967-9 . - doi : 10.1109/iThings.2014.78 . Arkiverad från originalet den 2 april 2018.
↑ Förenklad betalningsverifiering . Ordlista för Bitcoin . Datum för åtkomst: 7 december 2017. Arkiverad från originalet 7 december 2017.
↑ Michael Szydlo. Merkle Tree Traversal in Log Space and Time (engelska) // 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 . Arkiverad från originalet den 15 december 2017.

Se även

Länkar

Merkle Patricia Tree är en förbättrad implementering av Merkle-trädet som används i Ethereum.
Tiger Tree Torrent är ett förslag att ersätta SHA-1 med Tiger Tree Hash i .torrent - filer.

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H 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 Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA

Träd (datastruktur)
Binärt sökträd Träd (grafteori) trädstruktur
Binära träd	binärt träd T-träd
Självbalanserande binära träd	AA-träd AVL-träd Röd-svart träd Splay träd träd med böter kartesiskt träd Fibonacci träd B-träd T-träd
B-träd	2-3-träd B⁺-träd B*-träd B x -träd UB-träd 2-3-4 träd (a,b)-träd dansande träd
prefix träd	suffixträd Komprimerat prefixträd Ternärt sökträd
Binär uppdelning av utrymme	k-dimensionellt träd VP-träd
Icke-binära träd	Quadtree octree Gles Voxel Octree exponentiellt träd PQ-träd
Bryter upp utrymmet	R-träd Hilbert R-träd R+-träd R*-träd X-träd M-träd Fenwick träd Segment träd
Andra träd	högen haschträd fingerträd metriskt träd Beläggning träd BK-träd Dubbelkedjat träd iDistance Länkklippt träd LSM-träd
Algoritmer	Utöka första sökningen Djup första sökning DSW-algoritm spaning tree-protokoll