Hvad er et Merkle-træ? Begynderguide til denne Blockchain-komponent

Merkle Trees er en grundlæggende komponent i blockchains, der understøtter deres funktionalitet. De giver mulighed for effektiv og sikker verifikation af store datastrukturer, og i tilfælde af blockchains, potentielt grænseløse datasæt.

Implementeringen af ​​Merkle-træer i blockchains har flere effekter. Det giver dem mulighed for at skalere, samtidig med at de giver den hash-baserede arkitektur til at bevare dataintegriteten og en triviel måde at verificere dataintegriteten på.

Kryptografiske hash-funktioner er den underliggende teknologi, der gør det muligt for Merkle-træer at fungere, så først er det vigtigt at forstå, hvad kryptografiske hash-funktioner er.

Hurtig dom: Merkle-træer er datastrukturer sammensat af kryptografiske hashes, der tillader effektiv integritetsverifikation og kortlægning af store datasæt, hvilket gør dem til en integreret komponent af systemer som blockchains og distribueret versionskontrol.

hurtige fakta

Kryptografiske hash-funktioner

Kort sagt er en hash-funktion enhver funktion, der bruges til at kortlægge data af en vilkårlig størrelse (input) til et output med fast størrelse. En hashing-algoritme anvendes på datainputtet, og det resulterende output med fast længde omtales som hashen.

Mange hashing-algoritmer er bredt offentligt tilgængelige og kan vælges baseret på dine behov.

Den resulterende hash fra det vilkårlige input er ikke kun fast i længden, det er også helt unikt for inputtet, og selve funktionen er deterministisk. Det vil sige, at uanset hvor mange gange du kører funktionen på samme input, vil output altid være det samme.

For eksempel, hvis du har følgende datasæt nedenfor som input, er de resulterende output unikke for hver input. Bemærk, hvordan i det andet og tredje eksempel, selvom forskellen mellem inputs kun er ét ord, er de resulterende output helt forskellige.

Dette er meget vigtigt, da det giver mulighed for "fingeraftryk" af data.

En kryptografisk hash-funktion, Billede fra Wikipedia

Da output-længden (hash-sum i eksemplet) altid er den samme som bestemt af den anvendte hashing-algoritme, kan enorme mængder data identificeres udelukkende gennem deres resulterende hash.

Med systemer, der indeholder enorme mængder data, kan fordelene ved at være i stand til at lagre og identificere data med en output med fast længde skabe enorme lagerbesparelser og hjælpe med at øge effektiviteten.

Inden for blockchains bruges hashing-algoritmer til at bestemme tilstanden af ​​blockchain.

Blockchains er sammenkædede lister, der indeholder data og en hash-pointer, der peger på den forrige blok, hvilket skaber en kæde af forbundne blokke, deraf navnet "blockchain".

Hver blok er forbundet med hinanden gennem en hash-pointer, som er hashen af ​​dataene i den forrige blok sammen med adressen på den forrige blok. Ved at sammenkæde datablokke i dette format repræsenterer hver resulterende hash i den foregående blok hele tilstanden af ​​blokkæden, da alle de hash-data fra de tidligere blokke er hashed til én hash.

Dette er repræsenteret (i tilfælde af SHA-256-algoritmen) af et output (hash) som dette:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Hash ovenfor er fingeraftrykket af hele tilstanden af ​​blockchain før den. Tilstanden af ​​blockchain før den nye blok (som hash-data) er input, og den resulterende hash er output.

Selvom det er muligt at bruge kryptografiske hashes uden Merkle-træer, er det ekstremt ineffektivt og ikke skalerbart. Det er tidskrævende og besværligt at bruge hash til at gemme data i en blok i et serieformat.

Som du vil se, tillader Merkle-træer triviel opløsning af dataintegritet samt kortlægning af disse data gennem hele træet ved hjælp af Merkle-beviser.

Merkle Trees og Merkle Proofs

Opkaldt efter Ralph Merkle, som patenterede konceptet i 1979, er Merkle-træer grundlæggende datastrukturtræer, hvor hver ikke-bladknude er en hash af dens respektive underknudepunkter.

Bladknuderne er det laveste niveau af noder i træet. Umiddelbart lyder det måske svært at forstå, men hvis du ser på den almindeligt brugte figur nedenfor, bliver den meget lettere at forstå.

Et eksempel på et binært hash-træ, Billede fra Wikipedia

Vigtigt er det, at læg mærke til, hvordan ikke-bladknuderne eller "grenene" (repræsenteret ved Hash 0-0 og Hash 0-1) på venstre side, er hash for deres respektive børn L1 og L2. Læg desuden mærke til, hvordan gren Hash 0 er hash for dens sammenkædede børn, grener Hash 0-0 og Hash 0-1.

Eksemplet ovenfor er den mest almindelige og enkle form for et Merkle-træ kendt som et binært Merkle-træ. Som du kan se, er der en tophash, der er hash af hele træet, kendt som rodhash. I det væsentlige er Merkle-træer en datastruktur, der kan tage "n" antal hash og repræsentere det med en enkelt hash.

Træets struktur giver mulighed for effektiv kortlægning af vilkårligt store mængder data og muliggør nem identifikation af, hvor ændringer i disse data sker. Dette koncept muliggør Merkle-beviser, hvormed nogen kan verificere, at hashing af data er konsistent hele vejen op i træet og i den korrekte position uden faktisk at skulle se på hele sættet af hashes.

I stedet kan de verificere, at en datachunk er i overensstemmelse med root-hashen ved kun at kontrollere en lille delmængde af hashen i stedet for hele datasættet.

Så længe root-hashen er offentligt kendt og har tillid til, er det muligt for alle, der ønsker at foretage et nøgleværdiopslag på en database, at bruge et Merkle-bevis til at verificere positionen og integriteten af ​​et stykke data i en database, der har en bestemt rod.

Når rodhashen er tilgængelig, kan hashtræet modtages fra enhver ikke-pålidelig kilde, og en gren af ​​træet kan downloades ad gangen med øjeblikkelig verifikation af dataintegriteten, selvom hele træet endnu ikke er tilgængeligt.

En af de vigtigste fordele ved Merkle-træstrukturen er evnen til at autentificere vilkårligt store datasæt gennem en lignende hashing-mekanisme, der bruges til at verificere meget mindre mængder data.

Træet er fordelagtigt til at distribuere store sæt data i håndterbare mindre dele, hvor barrieren for verifikation af integritet er væsentligt reduceret på trods af den samlede større datastørrelse.

Root-hashen kan bruges som fingeraftryk for et helt datasæt, inklusive en hel database eller repræsenterer hele tilstanden af ​​en blockchain. I de følgende afsnit vil vi diskutere, hvordan Bitcoin og andre systemer implementerer Merkle-træer.

Merkle træer i Bitcoin

Den kryptografiske hash-funktion, der anvendes af Bitcoin, er SHA-256-algoritmen. Dette står for "Secure Hashing Algorithm", hvis output er en fast 256 bit i længden. Den grundlæggende funktion af Merkle træer i Bitcoin er at gemme og til sidst beskære transaktioner i hver blok.

Som nævnt tidligere er blokke i en blockchain forbundet gennem hashes fra den forrige blok. I Bitcoin indeholder hver blok alle transaktionerne inden for den blok samt blokoverskriften, som består af:

• Bloker versionsnummer
• Forrige Block Hash
• Timestamp
• Mine Sværhedsgrad Mål
• nonce
• Merkle Root Hash

Billedet nedenfor er fra Bitcoin-hvidbogen og illustrerer, hvordan Merkle-træet passer ind i hver blok.

Transaktionerne er inkluderet i blokke af minearbejdere og hashes som en del af et Merkle-træ, hvilket fører til Merkle-roden, der er gemt i blokoverskriften. Dette design har en række forskellige fordele.

Mest bemærkelsesværdigt, som skitseret i hvidbogen, tillader dette eksistensen af ​​Simple Payment Verification (SPV) noder, også kendt som "lette klienter". Disse noder behøver ikke at downloade hele Bitcoin blockchain, kun blokoverskrifterne i den længste kæde.

SPV-noder kan opnå dette ved at forespørge deres peer-knudepunkter, indtil de er overbevist om, at de lagrede blokoverskrifter, de opererer på, er en del af den længste kæde. En SPV-node er derefter i stand til at bestemme status for en transaktion ved at bruge Merkle-beviset til at kortlægge transaktionen til et specifikt Merkle-træ med det respektive Merkle-træs rodhash i en blokoverskrift, der er en del af den længste kæde.

Derudover giver Bitcoins implementering af Merkle-træer mulighed for beskæring af blockchain for at spare plads. Dette er et resultat af, at kun rodhashen er gemt i blokhovedet, derfor kan gamle blokke beskæres ved at fjerne unødvendige grene af Merkle-træet, mens du kun bevarer dem, der er nødvendige for Merkle-beviset.

Implementering af Merkle-træer i andre blockchains og systemer

Selvom Bitcoin var den første blockchain til at implementere Merkle-træer, implementerer mange andre blockchains lignende Merkle-træstrukturer eller endnu mere komplekse versioner.

Ydermere er Merkle-træimplementering ikke kun begrænset til blockchains og anvendes til en række andre systemer.

Ethereum, som er den anden mest genkendelige kryptovaluta, er også et godt eksempel på en anderledes Merkle-træimplementering. Fordi Ethereum er komplet som en platform til at bygge meget mere komplekse applikationer, bruger den en mere kompleks version af Merkle-træet kaldet et Merkle Patricia-træ, der faktisk er 3 separate Merkle-træer, der bruges til tre slags objekter. Du kan lære mere om disse træer her.

Endelig er Merkle-træer en vigtig komponent i distribuerede versionskontrolsystemer som Git og IPFS. Deres evne til nemt at sikre og verificere integriteten af ​​data, der deles mellem computere i et P2P-format, gør dem uvurderlige for disse systemer.

Konklusion

Merkle træer er en integreret komponent af blockchains og giver dem effektivt mulighed for at fungere med beviselig uforanderlighed og transaktionsintegritet.

At forstå den rolle, de spiller i distribuerede netværk og deres underliggende teknologi af kryptografiske hash-funktioner, er afgørende for at forstå de grundlæggende begreber inden for kryptovalutaer, efterhånden som de fortsætter med at udvikle sig til større og mere komplekse systemer.