Merkle stabla su temeljna komponenta blockchaina koja podupire njihovu funkcionalnost. Omogućuju učinkovitu i sigurnu provjeru velikih struktura podataka, au slučaju blockchaina, potencijalno neograničene skupove podataka.
Implementacija Merkleovih stabala u blockchain ima višestruke učinke. Omogućuje im skaliranje dok im također pruža arhitekturu temeljenu na hash-u za održavanje integriteta podataka i trivijalan način provjere integriteta podataka.
Kriptografske hash funkcije temeljna su tehnologija koja omogućuje rad Merkleovih stabala, pa je prvo važno razumjeti što su kriptografske hash funkcije.
Brza presuda: Merkleova stabla podatkovne su strukture sastavljene od kriptografskih hashova koji omogućuju učinkovitu provjeru integriteta i mapiranje velikih skupova podataka, čineći ih sastavnom komponentom sustava poput blockchaina i distribuirane kontrole verzija.
Brze činjenice
| Ključne točke | Opis |
|---|---|
| Kriptografske hash funkcije | Funkcije raspršivanja koje uzimaju unos bilo koje veličine i izlaze hash vrijednost fiksne duljine. Koristi se u Merkleovim stablima. |
| struktura stabla Merkle | Struktura podataka stabla gdje je svaki čvor koji nije list hash svojih čvorova djeteta. Omogućuje učinkovito mapiranje i provjeru velikih skupova podataka. |
| Root hash | Hash na vrhu Merkleovog stabla koji predstavlja hash cijelog stabla. Djeluje kao otisak prsta za cijeli skup podataka. |
| Merkleovi dokazi | Omogućuje provjeru integriteta podataka i položaja u stablu bez potrebe za punim skupom podataka, samo korijenski hash. |
| Implementacija u Bitcoinu | Merkle stabla pohranjuju transakcije u blokovima. Root hash pohranjen u zaglavlju bloka omogućuje SPV čvorovima provjeru transakcija. |
| Druge implementacije blockchaina | Koristi se u mnogim lancima blokova poput Ethereuma koji koristi složenije Merkle Patricia Trees. |
| Distribuirani sustavi | Omogućite sustavima za kontrolu verzija kao što su Git & IPFS da jednostavno provjeravaju podatke koji se dijele između ravnopravnih korisnika. |
Kriptografske hash funkcije
Jednostavno rečeno, hash funkcija je svaka funkcija koja se koristi za mapiranje podataka proizvoljne veličine (ulaz) u izlaz fiksne veličine. Algoritam raspršivanja primjenjuje se na ulaz podataka, a rezultirajući izlaz fiksne duljine naziva se raspršivanje.
Mnogi algoritmi raspršivanja široko su dostupni i mogu se odabrati na temelju vaših potreba.
Rezultirajući hash iz proizvoljnog unosa nije samo fiksne duljine, već je i potpuno jedinstven za ulaz, a sama funkcija je deterministička. To jest, bez obzira koliko puta pokrenete funkciju na istom ulazu, izlaz će uvijek biti isti.
Na primjer, ako kao ulaz imate sljedeće skupove podataka u nastavku, rezultirajući izlazi jedinstveni su za svaki ulaz. Primijetite 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 vrlo važno jer omogućuje "uzimanje otisaka" podataka.
Kriptografska hash funkcija, slika s Wikipedije
Budući da je duljina izlaza (zbroj hashiranja u primjeru) uvijek ista kao što je određeno upotrijebljenim algoritmom hashiranja, goleme količine podataka mogu se identificirati isključivo kroz njihov rezultirajući hash.
Sa sustavima koji sadrže ogromne količine podataka, prednosti mogućnosti pohranjivanja i identificiranja podataka s izlazom fiksne duljine mogu stvoriti velike uštede u pohrani i pomoći u povećanju učinkovitosti.
Unutar blockchaina, algoritmi raspršivanja koriste se za određivanje stanja blockchaina.
Blockchaini su povezani popisi koji sadrže podatke i hash pointer koji pokazuje na prethodni blok, stvarajući lanac povezanih blokova, otuda i naziv "blockchain".
Svaki blok povezan je jedan s drugim putem hash pokazivača, koji je hash podataka unutar prethodnog bloka zajedno s adresom prethodnog bloka. Povezivanjem blokova podataka u ovom formatu, svaki rezultirajući raspršivanje prethodnog bloka predstavlja cjelokupno stanje lanca blokova budući da su svi raspršeni podaci prethodnih blokova raspršeni u jedan raspršivač.
To je predstavljeno (u slučaju algoritma SHA-256) izlazom (hash) kao što je ovaj:
b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7
Gornji hash je otisak cijelog stanja blockchaina prije njega. Stanje blockchaina prije novog bloka (kao hashirani podaci) je ulaz, a rezultirajući hash je izlaz.
Iako je moguće koristiti kriptografske hashove bez Merkleovih stabala, to je izuzetno neučinkovito i nije skalabilno. Korištenje hashova za pohranjivanje podataka u bloku u formatu serije dugotrajno je i glomazno.
Kao što ćete vidjeti, Merkleova stabla omogućuju trivijalno rješavanje integriteta podataka kao i mapiranje tih podataka kroz cijelo stablo pomoću Merkleovih dokaza.
Merkleova stabla i Merkleovi dokazi
Nazvana po Ralphu Merkleu, koji je patentirao koncept 1979., Merkleova stabla u osnovi su stabla podatkovne strukture gdje je svaki čvor koji nije list hash svojih odgovarajućih čvorova djeteta.
Listni čvorovi su najniži sloj čvorova u stablu. U početku može zvučati teško za razumjeti, ali ako pogledate često korištenu sliku u nastavku, bit će vam mnogo lakše razumjeti.
Primjer binarnog hash stabla, slika s Wikipedije
Važno je primijetiti kako su čvorovi koji nisu listovi ili "grane" (predstavljeni Hash 0-0 i Hash 0-1) na lijevoj strani, hashovi svojih odgovarajućih potomaka L1 i L2. Nadalje, primijetite kako je grana Hash 0 hash svojih spojenih potomaka, grana Hash 0-0 i Hash 0-1.
Gornji primjer najčešći je i jednostavan oblik Merkleovog stabla poznatog kao binarno Merkleovo stablo. Kao što vidite, postoji glavni hash koji je hash cijelog stabla, poznat kao korijenski hash. U osnovi, Merkle stabla su podatkovna struktura koja može uzeti "n" broj hashova i predstaviti ih jednim hashom.
Struktura stabla omogućuje učinkovito mapiranje proizvoljno velikih količina podataka i omogućuje jednostavno prepoznavanje mjesta promjena u tim podacima. Ovaj koncept omogućuje Merkleove dokaze, pomoću kojih netko može potvrditi da je raspršivanje podataka dosljedno sve do stabla i na ispravnom položaju, a da ne mora zapravo pogledati cijeli skup raspršivanja.
Umjesto toga, mogu provjeriti je li dio podataka u skladu s korijenskim hashom provjeravajući samo mali podskup hashova, a ne cijeli skup podataka.
Sve dok je korijenski hash javno poznat i pouzdan, moguće je za svakoga tko želi izvršiti pretraživanje ključa i vrijednosti u bazi podataka da koristi Merkleov dokaz za provjeru položaja i integriteta dijela podataka unutar baze podataka koja ima određeni korijen.
Kada je korijenski hash dostupan, hash stablo se može primiti iz bilo kojeg nepouzdanog izvora, a jedna po jedna grana stabla može se preuzeti uz trenutačnu provjeru integriteta podataka, čak i ako cijelo stablo još nije dostupno.
Jedna od najvažnijih prednosti strukture stabla Merkle je mogućnost provjere autentičnosti proizvoljno velikih skupova podataka putem sličnog mehanizma raspršivanja koji se koristi za provjeru puno manjih količina podataka.
Stablo je korisno za distribuciju velikih skupova podataka u manje dijelove kojima se može upravljati, gdje je prepreka za provjeru integriteta značajno smanjena unatoč sveukupnoj većoj veličini podataka.
Korijenski hash može se koristiti kao otisak prsta za cijeli skup podataka, uključujući cijelu bazu podataka ili predstavljanje cjelokupnog stanja blockchaina. U sljedećim odjeljcima raspravljat ćemo o tome kako Bitcoin i drugi sustavi implementiraju Merkle stabla.
Merkle stabla u Bitcoinu
Kriptografska hash funkcija koju koristi Bitcoin je algoritam SHA-256. Ovo je skraćenica za "sigurni algoritam raspršivanja", čiji je izlaz duljine fiksnih 256 bita. Osnovna funkcija Merkleovih stabala u Bitcoinu je pohranjivanje i eventualno smanjenje transakcija u svakom bloku.
Kao što je ranije spomenuto, blokovi u lancu blokova povezani su kroz hashove 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 hash
- Timestamp
- Mining Difficulty Target
- nPo
- Merkle Root Hash
Slika ispod je iz Bitcoin whitepapera i ilustrira kako se Merkleovo stablo uklapa u svaki blok.
Transakcije rudari uključuju u blokove i raspršuju se kao dio Merkleovog stabla, što vodi do Merkleovog korijena koji je pohranjen u zaglavlju bloka. Ovaj dizajn ima niz jasnih prednosti.
Najznačajnije, kao što je navedeno u bijeloj knjizi, to omogućuje postojanje čvorova za jednostavnu provjeru plaćanja (SPV), također poznatih kao "laki klijenti". Ovi čvorovi ne moraju preuzeti cijeli Bitcoin blockchain, samo zaglavlja blokova najdužeg lanca.
SPV čvorovi to mogu postići postavljanjem upita svojim ravnopravnim čvorovima dok se ne uvjere da su pohranjena zaglavlja blokova na kojima rade dio najdužeg lanca. SPV čvor tada može odrediti status transakcije korištenjem Merkleovog dokaza za mapiranje transakcije na određeno Merkleovo stablo s tim odgovarajućim korijenskim hashom Merkleovog stabla u zaglavlju bloka koji je dio najdužeg lanca.
Osim toga, Bitcoinova implementacija Merkleovih stabala omogućuje obrezivanje blockchaina kako bi se uštedio prostor. To je rezultat pohranjivanja samo korijenskog hash-a u zaglavlju bloka, stoga se stari blokovi mogu orezati uklanjanjem nepotrebnih grana Merkleovog stabla, a istovremeno sačuvati samo one potrebne za Merkleov dokaz.
Implementacija Merkleovih stabala u drugim lancima blokova i sustavima
Iako je Bitcoin bio prvi blockchain koji je implementirao Merkle stabla, mnogi drugi blockchaini 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 sustava.
Ethereum, kao druga najprepoznatljivija kriptovaluta, također je izvrstan primjer implementacije drugačijeg Merkleovog stabla. Budući da je Ethereum turing-kompletan kao platforma za izgradnju mnogo složenijih aplikacija, koristi složeniju verziju Merkleovog stabla nazvanu Merkle Patricia Tree koje su zapravo 3 odvojena Merkleova 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 sustava kontrole verzija kao što su Git i IPFS. Njihova sposobnost da jednostavno osiguraju i provjere integritet podataka koji se dijele između računala u P2P formatu čini ih neprocjenjivim za ove sustave.
Zaključak
Merkleova stabla sastavna su komponenta lanaca blokova i učinkovito im omogućuju da funkcioniraju s dokazivom nepromjenjivošću i integritetom transakcije.
Razumijevanje uloge koju igraju u distribuiranim mrežama i njihove temeljne tehnologije kriptografskih hash funkcija ključno je za shvaćanje osnovnih koncepata unutar kriptovaluta dok se one nastavljaju razvijati u veće i složenije sustave.
Izvor: https://blockonomi.com/merkle-tree/