Drevesa Merkle so temeljna komponenta verig blokov, ki podpirajo njihovo funkcionalnost. Omogočajo učinkovito in varno preverjanje velikih podatkovnih struktur, v primeru blokovnih verig pa potencialno neomejene nize podatkov.
Implementacija dreves Merkle v verigah blokov ima več učinkov. Omogoča jim skaliranje, hkrati pa jim zagotavlja arhitekturo, ki temelji na zgoščevanju, da ohranijo celovitost podatkov in trivialen način za preverjanje celovitosti podatkov.
Kriptografske zgoščevalne funkcije so osnovna tehnologija, ki omogoča delovanje Merklovih dreves, zato je najprej pomembno razumeti, kaj so kriptografske zgoščevalne funkcije.
Hitra razsodba: Drevesa Merkle so podatkovne strukture, sestavljene iz kriptografskih zgoščenih vrednosti, ki omogočajo učinkovito preverjanje celovitosti in preslikavo velikih nizov podatkov, zaradi česar so sestavni del sistemov, kot so verige blokov in porazdeljeni nadzor različic.
Redna cena:
| Ključne točke | Opis |
|---|---|
| Kriptografske zgoščevalne funkcije | Zgoščevalne funkcije, ki sprejmejo vnos poljubne velikosti in izpišejo zgoščeno vrednost fiksne dolžine. Uporablja se pri drevesih Merkle. |
| Struktura drevesa Merkle | Drevesna podatkovna struktura, kjer je vsako nelistno vozlišče zgoščena vrednost svojih podrejenih vozlišč. Omogoča učinkovito preslikavo in preverjanje velikih nizov podatkov. |
| Root hash | Hash na vrhu Merklovega drevesa, ki predstavlja zgoščeno vrednost celotnega drevesa. Deluje kot prstni odtis za celoten nabor podatkov. |
| Merklovi dokazi | Omogočite preverjanje celovitosti podatkov in položaja v drevesu, ne da bi potrebovali celoten nabor podatkov, samo korensko zgoščevanje. |
| Implementacija v Bitcoinu | Merklejeva drevesa shranjujejo transakcije v blokih. Korenski hash, shranjen v glavi bloka, omogoča vozliščem SPV preverjanje transakcij. |
| Druge izvedbe blockchaina | Uporablja se v številnih verigah blokov, kot je Ethereum, ki uporablja bolj zapletena drevesa Merkle Patricia. |
| Porazdeljeni sistemi | Omogočite sistemom za nadzor različic, kot sta Git & IPFS, enostavno preverjanje podatkov, ki so v skupni rabi med vrstniki. |
Kriptografske Hash funkcije
Preprosto povedano, zgoščevalna funkcija je katera koli funkcija, ki se uporablja za preslikavo podatkov poljubne velikosti (vnos) v izhod fiksne velikosti. Za vnesene podatke se uporabi algoritem zgoščevanja, rezultat s fiksno dolžino pa se imenuje zgoščevanje.
Številni algoritmi zgoščevanja so splošno dostopni in jih je mogoče izbrati glede na vaše potrebe.
Zgoščena vrednost, ki izhaja iz poljubnega vnosa, ni le fiksna v dolžini, je tudi popolnoma edinstvena za vnos in sama funkcija je deterministična. Se pravi, ne glede na to, kolikokrat zaženete funkcijo na istem vhodu, bo izhod vedno enak.
Če imate na primer kot vhod naslednje nize podatkov, so dobljeni izhodi edinstveni za vsak vnos. Opazite, kako so v drugem in tretjem primeru, čeprav je razlika med vhodi samo ena beseda, posledični izhodi popolnoma različni.
To je zelo pomembno, saj omogoča "prstni odtis" podatkov.
Kriptografska zgoščevalna funkcija, slika iz Wikipedije
Ker je dolžina izhoda (zgoščene vsote v primeru) vedno enaka, kot jo določa uporabljeni algoritem zgoščevanja, je mogoče ogromne količine podatkov identificirati samo prek njihovega nastalega zgoščevanja.
Pri sistemih, ki vsebujejo ogromne količine podatkov, lahko prednosti shranjevanja in prepoznavanja podatkov z izhodom fiksne dolžine ustvarijo velike prihranke pri shranjevanju in pomagajo povečati učinkovitost.
Znotraj verig blokov se za določanje stanja verige blokov uporabljajo algoritmi zgoščevanja.
Blockchaini so povezani seznami, ki vsebujejo podatke in hash kazalec, ki kaže na prejšnji blok, kar ustvarja verigo povezanih blokov, od tod tudi ime "blockchain".
Vsak blok je med seboj povezan prek zgoščenega kazalca, ki je zgoščena vrednost podatkov v prejšnjem bloku skupaj z naslovom prejšnjega bloka. S povezovanjem blokov podatkov v tej obliki vsaka nastala zgoščena vrednost prejšnjega bloka predstavlja celotno stanje verige blokov, saj so vsi zgoščeni podatki prejšnjih blokov zgoščeni v eno zgoščeno vrednost.
To je (v primeru algoritma SHA-256) predstavljeno z izhodom (hash), kot je ta:
b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7
Zgornja zgoščena vrednost je prstni odtis celotnega stanja verige blokov pred njim. Stanje verige blokov pred novim blokom (kot zgoščeni podatki) je vhod, nastala zgoščena vrednost pa izhod.
Čeprav je mogoče uporabiti kriptografske zgoščene vrednosti brez Merklovih dreves, je to izjemno neučinkovito in ni razširljivo. Uporaba zgoščenih vrednosti za shranjevanje podatkov v bloku v serijski obliki je dolgotrajna in okorna.
Kot boste videli, drevesa Merkle omogočajo trivialno razrešitev celovitosti podatkov kot tudi preslikavo teh podatkov skozi celotno drevo z uporabo dokazov Merkle.
Merklova drevesa in Merklova dokazila
Poimenovana po Ralphu Merklu, ki je koncept patentiral leta 1979, so Merklova drevesa v bistvu drevesa s podatkovno strukturo, kjer je vsako nelistno vozlišče zgoščena vrednost ustreznih podrejenih vozlišč.
Listna vozlišča so najnižja raven vozlišč v drevesu. Sprva se morda sliši težko razumljivo, a če pogledate spodnjo pogosto uporabljeno sliko, bo veliko lažje razumeti.
Primer binarnega zgoščenega drevesa, slika iz Wikipedije
Pomembno je opaziti, da so nelistna vozlišča ali "veje" (predstavljena z Hash 0-0 in Hash 0-1) na levi strani zgoščene vrednosti svojih otrok L1 in L2. Nadalje opazite, kako je razpršitev veje 0 razpršitev svojih povezanih otrok, veje razpršitev 0-0 in razpršitev 0-1.
Zgornji primer je najpogostejša in preprosta oblika Merklovega drevesa, znanega kot binarno Merklovo drevo. Kot lahko vidite, obstaja zgornja zgoščena vrednost, ki je zgoščena vrednost celotnega drevesa, znana kot korenska zgoščena vrednost. V bistvu so drevesa Merkle podatkovna struktura, ki lahko sprejme "n" število zgoščenih vrednosti in jih predstavi z eno samo zgoščeno vrednostjo.
Struktura drevesa omogoča učinkovito preslikavo poljubno velikih količin podatkov in omogoča enostavno prepoznavanje, kje v teh podatkih prihaja do sprememb. Ta koncept omogoča dokaze Merkle, s katerimi lahko nekdo preveri, ali je zgoščevanje podatkov dosledno vse do drevesa in v pravilnem položaju, ne da bi moral dejansko pogledati celoten niz zgoščenih vrednosti.
Namesto tega lahko preverijo, ali je del podatkov skladen s korensko zgoščeno vrednostjo, tako da preverijo samo majhno podmnožico zgoščenih vrednosti in ne celotnega nabora podatkov.
Dokler je korenski hash javno znan in zaupanja vreden, lahko vsakdo, ki želi opraviti iskanje po ključu in vrednosti v zbirki podatkov, uporabi Merkleov dokaz za preverjanje položaja in celovitosti dela podatkov v zbirki podatkov, ki ima določen koren.
Ko je korenski razpršilec na voljo, lahko razpršilno drevo prejmete iz katerega koli vira, ki ni zaupanja vreden, in eno vejo drevesa lahko prenesete hkrati s takojšnjim preverjanjem celovitosti podatkov, tudi če celotno drevo še ni na voljo.
Ena najpomembnejših prednosti drevesne strukture Merkle je zmožnost avtentikacije poljubno velikih nizov podatkov prek podobnega mehanizma zgoščevanja, ki se uporablja za preverjanje veliko manjših količin podatkov.
Drevo je ugodno za distribucijo velikih nizov podatkov v manjše dele, ki jih je mogoče upravljati, kjer je ovira za preverjanje celovitosti bistveno zmanjšana kljub skupni večji velikosti podatkov.
Korensko zgoščeno vrednost lahko uporabite kot prstni odtis za celoten nabor podatkov, vključno s celotno bazo podatkov ali predstavlja celotno stanje verige blokov. V naslednjih razdelkih bomo razpravljali o tem, kako Bitcoin in drugi sistemi implementirajo drevesa Merkle.
Merkle Trees v Bitcoinu
Kriptografska zgoščevalna funkcija, ki jo uporablja Bitcoin, je algoritem SHA-256. To pomeni "varni algoritem zgoščevanja", katerega izhod je fiksne dolžine 256 bitov. Osnovna funkcija dreves Merkle v Bitcoinu je shranjevanje in sčasoma obrezovanje transakcij v vsakem bloku.
Kot smo že omenili, so bloki v verigi blokov povezani prek zgoščenih vrednosti prejšnjega bloka. V Bitcoinu vsak blok vsebuje vse transakcije v tem bloku in glavo bloka, ki je sestavljena iz:
- Številka različice bloka
- Prejšnji blok Hash
- Timestamp
- Cilj težavnosti rudarjenja
- Neskončno
- Merkle Root Hash
Spodnja slika je iz bele knjige Bitcoin in prikazuje, kako se drevo Merkle prilega vsakemu bloku.
Transakcije rudarji vključijo v bloke in so zgoščene kot del drevesa Merkle, kar vodi do korena Merkle, ki je shranjen v glavi bloka. Ta zasnova ima številne posebne prednosti.
Predvsem, kot je opisano v beli knjigi, to omogoča obstoj vozlišč za preprosto preverjanje plačil (SPV), znanih tudi kot "lahki odjemalci". Tem vozliščem ni treba prenesti celotne verige blokov Bitcoin, temveč samo glave blokov najdaljše verige.
Vozlišča SPV lahko to dosežejo s poizvedovanjem po enakovrednih vozliščih, dokler niso prepričana, da so shranjene glave blokov, s katerimi delujejo, del najdaljše verige. Vozlišče SPV lahko nato določi status transakcije z uporabo dokazila Merkle za preslikavo transakcije v določeno drevo Merkle s korensko zgoščenostjo zadevnega drevesa Merkle v glavi bloka, ki je del najdaljše verige.
Poleg tega Bitcoinova izvedba dreves Merkle omogoča obrezovanje verige blokov, da se prihrani prostor. To je posledica tega, da je v glavi bloka shranjen samo korenski hash, zato lahko stare bloke obrežemo tako, da odstranimo nepotrebne veje drevesa Merkle, medtem ko ohranimo samo tiste, ki so potrebne za dokaz Merkle.
Implementacija dreves Merkle v drugih verigah blokov in sistemih
Čeprav je bil Bitcoin prva veriga blokov, ki je implementirala drevesa Merkle, številne druge verige blokov izvajajo podobne drevesne strukture Merkle ali celo bolj zapletene različice.
Poleg tega implementacija drevesa Merkle ni omejena samo na verige blokov in se uporablja za številne druge sisteme.
Ethereum, ki je druga najbolj prepoznavna kriptovaluta, je tudi odličen primer drugačne implementacije drevesa Merkle. Ker je Ethereum turing-complete kot platforma za gradnjo veliko bolj zapletenih aplikacij, uporablja bolj zapleteno različico drevesa Merkle, imenovano drevo Merkle Patricia, ki je pravzaprav 3 ločena drevesa Merkle, ki se uporabljajo za tri vrste objektov. Več o teh drevesih lahko izveste tukaj.
Nazadnje so drevesa Merkle pomemben sestavni del porazdeljenih sistemov za nadzor različic, kot sta Git in IPFS. Zaradi njihove zmožnosti, da enostavno zagotovijo in preverijo celovitost podatkov, ki se delijo med računalniki v formatu P2P, so neprecenljivi za te sisteme.
zaključek
Merkleova drevesa so sestavni del verig blokov in jim učinkovito omogočajo delovanje z dokazljivo nespremenljivostjo in celovitostjo transakcij.
Razumevanje vloge, ki jo imajo v porazdeljenih omrežjih, in njihove osnovne tehnologije kriptografskih zgoščevalnih funkcij je ključnega pomena za razumevanje osnovnih konceptov znotraj kriptovalut, ko se te še naprej razvijajo v večje in kompleksnejše sisteme.
Vir: https://blockonomi.com/merkle-tree/