Hva er et Merkle-tre? Nybegynnerveiledning til denne Blockchain-komponenten

Merkle Trees er en grunnleggende komponent i blokkjeder som underbygger funksjonaliteten deres. De gir mulighet for effektiv og sikker verifisering av store datastrukturer, og i tilfelle blokkjeder, potensielt grenseløse datasett.

Implementeringen av Merkle-trær i blokkjeder har flere effekter. Den lar dem skalere, samtidig som den gir den hash-baserte arkitekturen for å opprettholde dataintegriteten og en triviell måte å verifisere dataintegriteten på.

Kryptografiske hashfunksjoner er den underliggende teknologien som gjør at Merkle-trær kan fungere, så først er det viktig å forstå hva kryptografiske hashfunksjoner er.

Hurtig dom: Merkle-trær er datastrukturer sammensatt av kryptografiske hasjer som tillater effektiv integritetsverifisering og kartlegging av store datasett, noe som gjør dem til en integrert komponent av systemer som blokkjeder og distribuert versjonskontroll.

Kjappe fakta

Kryptografiske Hash-funksjoner

Enkelt sagt er en hash-funksjon en hvilken som helst funksjon som brukes til å kartlegge data av en vilkårlig størrelse (input) til en utdata med fast størrelse. En hashing-algoritme brukes på datainngangen, og den resulterende utgangen med fast lengde blir referert til som hashen.

Mange hashing-algoritmer er allment tilgjengelige og kan velges basert på dine behov.

Den resulterende hashen fra den vilkårlige inngangen er ikke bare fast i lengden, den er også helt unik for inngangen og selve funksjonen er deterministisk. Det vil si at uansett hvor mange ganger du kjører funksjonen på samme inngang, vil utgangen alltid være den samme.

For eksempel, hvis du har følgende datasett nedenfor som inngang, er de resulterende utgangene unike for hver inngang. Legg merke til hvordan i det andre og tredje eksemplet, selv om forskjellen mellom inngangene bare er ett ord, er de resulterende utgangene helt forskjellige.

Dette er veldig viktig siden det tillater "fingeravtrykk" av data.

En kryptografisk hash-funksjon, bilde fra Wikipedia

Siden utdatalengden (hash sum i eksempelet) alltid er den samme som bestemmes av hashing-algoritmen som brukes, kan enorme mengder data identifiseres utelukkende gjennom deres resulterende hash.

Med systemer som inneholder enorme mengder data, kan fordelene ved å kunne lagre og identifisere data med utdata med fast lengde skape enorme lagringsbesparelser og bidra til å øke effektiviteten.

Innen blokkjeder brukes hashing-algoritmer for å bestemme tilstanden til blokkjeden.

Blokkjeder er koblede lister som inneholder data og en hash-peker som peker til forrige blokk, og skaper en kjede med tilkoblede blokker, derav navnet "blokkjede".

Hver blokk er koblet til hverandre gjennom en hash-peker, som er hashen til dataene inne i den forrige blokken sammen med adressen til den forrige blokken. Ved å koble sammen blokker med data i dette formatet, representerer hver resulterende hash av forrige blokk hele tilstanden til blokkjeden siden alle hashdataene til de tidligere blokkene hash til én hash.

Dette er representert (i tilfellet med SHA-256-algoritmen) av en utgang (hash) som dette:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Hash-en ovenfor er fingeravtrykket av hele blokkjedens tilstand før den. Tilstanden til blokkjeden før den nye blokken (som hash-data) er inngangen, og den resulterende hashen er utdata.

Selv om det er mulig å bruke kryptografiske hasjer uten Merkle-trær, er det ekstremt ineffektivt og ikke skalerbart. Å bruke hashes til å lagre data i en blokk i serieformat er tidkrevende og tungvint.

Som du vil se, tillater Merkle-trær triviell oppløsning av dataintegritet samt kartlegging av disse dataene gjennom hele treet ved å bruke Merkle-bevis.

Merkle Trees og Merkle Proofs

Oppkalt etter Ralph Merkle, som patenterte konseptet i 1979, er Merkle-trær i utgangspunktet datastrukturtrær der hver ikke-bladnode er en hash av sine respektive barnenoder.

Bladnodene er det laveste nivået av noder i treet. Til å begynne med kan det høres vanskelig ut å forstå, men hvis du ser på den ofte brukte figuren nedenfor, vil den bli mye lettere å forstå.

Et eksempel på et binært hasj-tre, Bilde fra Wikipedia

Viktigere, legg merke til hvordan ikke-bladknutene eller "grenene" (representert av Hash 0-0 og Hash 0-1) på venstre side, er hashes til deres respektive barn L1 og L2. Legg også merke til hvordan gren Hash 0 er hasjen til de sammenkoblede barna, grenene Hash 0-0 og Hash 0-1.

Eksemplet ovenfor er den vanligste og enkleste formen av et Merkle-tre kjent som et binært Merkle-tre. Som du kan se, er det en topphash som er hasjen til hele treet, kjent som rothasjen. I hovedsak er Merkle-trær en datastruktur som kan ta "n" antall hash og representere den med en enkelt hash.

Strukturen til treet gir mulighet for effektiv kartlegging av vilkårlig store datamengder og muliggjør enkel identifikasjon av hvor endringer i disse dataene skjer. Dette konseptet muliggjør Merkle-bevis, som noen kan verifisere at hashing av data er konsistent hele veien opp i treet og i riktig posisjon uten å faktisk se på hele settet med hashes.

I stedet kan de verifisere at en databit stemmer overens med rothashen ved bare å sjekke en liten delmengde av hashen i stedet for hele datasettet.

Så lenge rothashen er offentlig kjent og klarert, er det mulig for alle som ønsker å gjøre et nøkkelverdi-oppslag på en database å bruke et Merkle-bevis for å verifisere posisjonen og integriteten til et datastykke i en database som har en bestemt rot.

Når rothashen er tilgjengelig, kan hashtreet mottas fra en hvilken som helst ikke-klarert kilde, og én gren av treet kan lastes ned om gangen med umiddelbar verifisering av dataintegriteten, selv om hele treet ennå ikke er tilgjengelig.

En av de viktigste fordelene med Merkle-trestrukturen er muligheten til å autentisere vilkårlig store sett med data gjennom en lignende hashing-mekanisme som brukes til å verifisere mye mindre datamengder.

Treet er fordelaktig for å distribuere store sett med data til håndterbare mindre deler der barrieren for verifisering av integritet er betydelig redusert til tross for den totale større datastørrelsen.

Rothashen kan brukes som fingeravtrykk for et helt datasett, inkludert en hel database eller som representerer hele tilstanden til en blokkjede. I de følgende avsnittene vil vi diskutere hvordan Bitcoin og andre systemer implementerer Merkle-trær.

Merkle Trees i Bitcoin

Den kryptografiske hash-funksjonen som brukes av Bitcoin er SHA-256-algoritmen. Dette står for "Secure Hashing Algorithm", hvis utgang er en fast 256 bits lengde. Den grunnleggende funksjonen til Merkle-trær i Bitcoin er å lagre, og til slutt beskjære transaksjoner i hver blokk.

Som nevnt tidligere, er blokker i en blokkjede koblet sammen gjennom hasher fra forrige blokk. I Bitcoin inneholder hver blokk alle transaksjonene innenfor den blokken samt blokkoverskriften som består av:

• Blokker versjonsnummer
• Forrige Block Hash
• Tidsstempel
• Gruvevanskelighetsmål
• nuncio
• Merkle Root Hash

Bildet nedenfor er fra Bitcoin Whitepaper og illustrerer hvordan Merkle-treet passer inn i hver blokk.

Transaksjonene er inkludert i blokker av gruvearbeidere og hashes som en del av et Merkle-tre, som fører til Merkle-roten som er lagret i blokkhodet. Denne designen har en rekke distinkte fordeler.

Mest bemerkelsesverdig, som skissert i hvitboken, tillater dette eksistensen av Simple Payment Verification (SPV) noder, også kjent som "lette klienter". Disse nodene trenger ikke å laste ned hele Bitcoin-blokkkjeden, bare blokkhodene til den lengste kjeden.

SPV-noder kan oppnå dette ved å spørre på peer-nodene deres til de er overbevist om at de lagrede blokkhodene de opererer på er en del av den lengste kjeden. En SPV-node er i stand til å bestemme statusen til en transaksjon ved å bruke Merkle-beviset for å kartlegge transaksjonen til et spesifikt Merkle-tre med det respektive Merkle-treets rothash i en blokkhode som er en del av den lengste kjeden.

I tillegg tillater Bitcoins implementering av Merkle-trær beskjæring av blokkjeden for å spare plass. Dette er et resultat av at bare root-hashen er lagret i blokkoverskriften, derfor kan gamle blokker beskjæres ved å fjerne unødvendige grener av Merkle-treet mens bare de som trengs for Merkle-beviset bevares.

Implementering av Merkle-trær i andre blokkkjeder og systemer

Selv om Bitcoin var den første blokkjeden som implementerte Merkle-trær, implementerer mange andre blokkjeder lignende Merkle-trestrukturer eller enda mer komplekse versjoner.

Videre er Merkle-treimplementering ikke bare begrenset til blokkjeder og brukes på en rekke andre systemer.

Ethereum, som er den andre mest gjenkjennelige kryptovalutaen, er også et godt eksempel på en annen Merkle-treimplementering. Fordi Ethereum er komplett som en plattform for å bygge mye mer komplekse applikasjoner, bruker den en mer kompleks versjon av Merkle-treet kalt et Merkle Patricia-tre som faktisk er 3 separate Merkle-trær som brukes til tre typer objekter. Du kan lære mer om disse trærne her.

Til slutt er Merkle-trær en viktig komponent i distribuerte versjonskontrollsystemer som Git og IPFS. Deres evne til enkelt å sikre og verifisere integriteten til data som deles mellom datamaskiner i et P2P-format, gjør dem uvurderlige for disse systemene.

konklusjonen

Merkle-trær er en integrert komponent av blokkjeder og lar dem effektivt fungere med påviselig uforanderlighet og transaksjonsintegritet.

Å forstå rollen de spiller i distribuerte nettverk og deres underliggende teknologi for kryptografiske hashfunksjoner er avgjørende for å forstå de grunnleggende konseptene innen kryptovalutaer når de fortsetter å utvikle seg til større og mer komplekse systemer.