Merkle stabla su osnovna komponenta blockchaina koji podupiru njihovu funkcionalnost. Oni omogućavaju efikasnu i sigurnu verifikaciju velikih struktura podataka, au slučaju blockchaina, potencijalno neograničenih skupova podataka.
Implementacija Merkle stabala u blockchainima ima višestruke efekte. Omogućava im skaliranje, a istovremeno im pruža arhitekturu zasnovanu na hash-u za održavanje integriteta podataka i trivijalan način za provjeru integriteta podataka.
Kriptografske hash funkcije su osnovna tehnologija koja omogućava da Merkle stabla rade, pa je prvo važno razumjeti što su kriptografske hash funkcije.
Brza presuda: Merkle stabla su strukture podataka sastavljene od kriptografskih heševa koje omogućavaju efikasnu verifikaciju integriteta i mapiranje velikih skupova podataka, čineći ih integralnom komponentom sistema kao što su blockchains i distribuirana kontrola verzija.
Brze činjenice
| Ključne točke | Opis |
|---|---|
| Kriptografske hash funkcije | Haš funkcije koje uzimaju ulaz bilo koje veličine i izlaze heš vrijednost fiksne dužine. Koristi se u drveću Merkle. |
| Struktura drveta Merkle | Struktura podataka stabla u kojoj je svaki čvor bez lista heš njegovih podređenih čvorova. Omogućava efikasno mapiranje i verifikaciju velikih skupova podataka. |
| Root hash | Hash na vrhu Merkle stabla koji predstavlja hash cijelog stabla. Djeluje kao otisak prsta za cijeli skup podataka. |
| Merkle dokazi | Dozvolite provjeru integriteta podataka i pozicije u stablu bez potrebe za cijelim skupom podataka, samo root hash. |
| Implementacija u Bitcoin | Merkle stabla pohranjuju transakcije u blokove. Root hash pohranjen u zaglavlju bloka omogućava SPV čvorovima da verifikuju transakcije. |
| Ostale implementacije blockchaina | Koristi se u mnogim blockchainima kao što je Ethereum koji koristi složenije Merkle Patricia Trees. |
| Distribuirani sistemi | Dozvolite sistemima za kontrolu verzija kao što su Git i IPFS da lako provjere podatke koji se dijele između kolega. |
Kriptografske hash funkcije
Jednostavno rečeno, hash funkcija je svaka funkcija koja se koristi za mapiranje podataka proizvoljne veličine (ulaza) u izlaz fiksne veličine. Algoritam heširanja se primjenjuje na ulaz podataka i rezultirajući izlaz fiksne dužine naziva se hash.
Mnogi algoritmi heširanja su javno dostupni i mogu se odabrati na osnovu vaših potreba.
Rezultirajući hash iz proizvoljnog ulaza nije samo fiksne dužine, on je također potpuno jedinstven za ulaz i sama funkcija je deterministička. To jest, bez obzira koliko puta pokrenete funkciju na istom ulazu, izlaz će uvijek biti isti.
Na primjer, ako imate sljedeće skupove podataka ispod kao ulaz, rezultirajući izlazi su jedinstveni za svaki ulaz. Zapazite kako su u drugom i trećem primjeru, iako je razlika između ulaza samo jedna riječ, rezultirajući izlazi potpuno različiti.
Ovo je veoma važno jer omogućava „otisak prsta“ podataka.
Kriptografska hash funkcija, slika sa Wikipedije
Budući da je izlazna (heš suma u primjeru) dužina uvijek ista kao što je određena korišćenim algoritmom heširanja, ogromne količine podataka mogu se identifikovati isključivo kroz njihov rezultujući heš.
Sa sistemima koji sadrže ogromne količine podataka, prednosti mogućnosti pohranjivanja i identifikacije podataka sa izlazom fiksne dužine mogu stvoriti velike uštede u skladištu i pomoći u povećanju efikasnosti.
Unutar blockchaina, algoritmi heširanja se koriste za određivanje stanja blockchaina.
Blockchains su povezane liste koje sadrže podatke i hash pokazivač koji ukazuje na prethodni blok, stvarajući lanac povezanih blokova, otuda i naziv "blockchain".
Svaki blok je povezan jedan s drugim preko hash pokazivača, koji je hash podataka unutar prethodnog bloka zajedno sa adresom prethodnog bloka. Povezivanjem blokova podataka u ovom formatu, svaki rezultirajući heš prethodnog bloka predstavlja cjelokupno stanje lanca blokova budući da se svi heširani podaci prethodnih blokova heširaju u jedan hash.
Ovo je predstavljeno (u slučaju SHA-256 algoritma) izlazom (hash) kao što je ovaj:
b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7
Heš iznad je otisak prsta cjelokupnog stanja blockchaina prije njega. Stanje blockchaina prije novog bloka (kao heširani podaci) je ulaz, a rezultirajući hash je izlaz.
Iako je moguće koristiti kriptografske hešove bez Merkle stabala, to je izuzetno neefikasno i nije skalabilno. Korištenje hashova za pohranjivanje podataka u bloku u formatu serije je dugotrajno i glomazno.
Kao što ćete vidjeti, Merkle stabla omogućavaju trivijalno rješavanje integriteta podataka, kao i mapiranje tih podataka kroz cijelo stablo koristeći Merkle dokaze.
Merkle drveće i Merkle dokazi
Nazvano po Ralphu Merkleu, koji je patentirao koncept 1979. godine, Merkle stabla su u osnovi stabla strukture podataka gdje je svaki nelisni čvor heš svojih odgovarajućih podređenih čvorova.
Čvorovi lista su najniži nivo čvorova u stablu. U početku može zvučati teško za razumjeti, ali ako pogledate često korištenu sliku ispod, bit će vam mnogo lakše razumjeti.
Primjer binarnog hash stabla, slika sa Wikipedije
Važno je primijetiti kako su nelisni čvorovi ili „grane“ (predstavljeni s Hash 0-0 i Hash 0-1) na lijevoj strani, heševi njihovih odgovarajućih djece L1 i L2. Nadalje, primijetite kako je grana Hash 0 heš njegovih spojenih djece, grana Hash 0-0 i Hash 0-1.
Gornji primjer je najčešći i jednostavan oblik Merkleovog stabla poznatog kao Binarno Merkle drvo. Kao što možete vidjeti, postoji gornji hash koji je heš cijelog stabla, poznat kao korijenski hash. U suštini, Merkle stabla su struktura podataka koja može uzeti "n" broj heša i predstaviti ga jednim hešom.
Struktura stabla omogućava efikasno mapiranje proizvoljno velikih količina podataka i omogućava laku identifikaciju gde se promene u tim podacima dešavaju. Ovaj koncept omogućava Merkle dokaze, pomoću kojih neko može potvrditi da je heširanje podataka konzistentno sve do stabla iu ispravnom položaju, a da ne mora zapravo gledati cijeli skup hashova.
Umjesto toga, oni mogu provjeriti da li je komad podataka konzistentan s korijenskim hešom provjeravanjem samo malog podskupa hashova, a ne cijelog skupa podataka.
Sve dok je root hash javno poznat i pouzdan, moguće je da svako ko želi da izvrši pretragu ključ-vrijednost u bazi podataka koristi Merkle dokaz za provjeru položaja i integriteta podatka u bazi podataka koja ima određeni korijen.
Kada je root hash dostupan, heš stablo se može primiti iz bilo kojeg nepouzdanog izvora i jedna grana stabla se može preuzeti istovremeno uz trenutnu provjeru integriteta podataka, čak i ako cijelo stablo još nije dostupno.
Jedna od najvažnijih prednosti strukture Merkle stabla je mogućnost provjere autentičnosti proizvoljno velikih skupova podataka putem sličnog mehanizma raspršivanja koji se koristi za verifikaciju mnogo manjih količina podataka.
Stablo je korisno za distribuciju velikih skupova podataka u manje dijelove kojima se može upravljati gdje je barijera za verifikaciju integriteta značajno smanjena uprkos ukupnoj većoj veličini podataka.
Root hash se može koristiti kao otisak prsta za cijeli skup podataka, uključujući cijelu bazu podataka ili predstavlja cjelokupno stanje blockchaina. U narednim odeljcima ćemo razgovarati o tome kako Bitcoin i drugi sistemi implementiraju Merkle stabla.
Merkle drveće u Bitcoinu
Kriptografska heš funkcija koju koristi Bitcoin je SHA-256 algoritam. Ovo je skraćenica za “Algoritam sigurnog heširanja”, čiji je izlaz fiksne dužine 256 bita. Osnovna funkcija Merkle stabala u Bitcoin-u je pohranjivanje i eventualno smanjenje transakcija u svakom bloku.
Kao što je ranije spomenuto, blokovi u blockchainu su povezani preko hashova prethodnog bloka. U Bitcoinu, svaki blok sadrži sve transakcije unutar tog bloka, kao i zaglavlje bloka koje se sastoji od:
- Broj verzije bloka
- Prethodni blok heš
- Vremenska oznaka
- Cilj težine rudarenja
- Nonce
- Merkle Root Hash
Slika ispod je iz Bitcoin whitepaper-a i ilustruje kako se drvo Merkle uklapa u svaki blok.
Rudari uključuju transakcije u blokove i heširaju se kao dio Merkle stabla, što vodi do Merkle korijena koji je pohranjen u zaglavlju bloka. Ovaj dizajn ima niz izrazitih prednosti.
Najvažnije, kao što je navedeno u bijeloj knjizi, ovo omogućava postojanje čvorova za jednostavnu verifikaciju plaćanja (SPV), također poznatih kao „laki klijenti“. Ovi čvorovi ne moraju preuzimati cijeli Bitcoin blockchain, već samo zaglavlja blokova najdužeg lanca.
SPV čvorovi to mogu postići ispitivanjem svojih ravnopravnih čvorova dok se ne uvjere da su pohranjena zaglavlja bloka na kojima rade dio najdužeg lanca. SPV čvor može zatim odrediti status transakcije koristeći Merkle dokaz za mapiranje transakcije na određeno Merkle stablo sa korijenskim hashom tog odgovarajućeg Merkle stabla u zaglavlju bloka koje je dio najdužeg lanca.
Osim toga, implementacija Merkle stabala u Bitcoin-u omogućava orezivanje blockchaina kako bi se uštedio prostor. Ovo je rezultat toga što se samo korijenski hash pohranjuje u zaglavlju bloka, stoga se stari blokovi mogu orezati uklanjanjem nepotrebnih grana Merkle stabla dok se čuvaju samo one potrebne za Merkle dokaz.
Implementacija Merkle drveća u drugim blokčejnovima i sistemima
Iako je Bitcoin bio prvi blockchain koji je implementirao Merkle stabla, mnogi drugi blockchain implementiraju slične strukture Merkle stabla ili čak složenije verzije.
Nadalje, implementacija Merkle stabla nije ograničena samo na blockchaine i primjenjuje se na niz drugih sistema.
Ethereum, kao druga najprepoznatljivija kriptovaluta, također je odličan primjer drugačije implementacije Merkle stabla. Budući da je Ethereum kompletan kao platforma za izgradnju mnogo složenijih aplikacija, koristi složeniju verziju Merkle stabla pod nazivom Merkle Patricia Tree koje je zapravo 3 odvojena Merkle stabla koja se koriste za tri vrste objekata. Više o ovim stablima možete saznati ovdje.
Konačno, Merkle stabla su važna komponenta distribuiranih sistema kontrole verzija kao što su Git i IPFS. Njihova sposobnost da lako obezbede i provere integritet podataka koji se dele između računara u P2P formatu čini ih neprocenjivim za ove sisteme.
zaključak
Merkle stabla su sastavna komponenta blockchaina i efektivno im omogućavaju da funkcionišu uz nepromjenjivost i integritet transakcija koji se mogu dokazati.
Razumijevanje uloge koju oni igraju u distribuiranim mrežama i njihove osnovne tehnologije kriptografskih hash funkcija ključno je za razumijevanje osnovnih koncepata unutar kriptovaluta dok se one nastavljaju razvijati u veće i složenije sisteme.
Izvor: https://blokonomi.com/merkle-tree/