Kas ir Merkles koks?
Merkles koka koncepciju 80. gadu sākumā ierosināja Ralfs Merks – datorzinātnieks, kurš bija slavens ar savu darbu pie publiskās atslēgas kriptogrāfijas.
Merkles koks ir struktūra, ko izmanto, lai efektīvi pārbaudītu kopas datu integritāti. Tie ir īpaši interesanti vienādranga tīklu kontekstā, kur dalībniekiem ir jādalās un neatkarīgi jāapstiprina informācija.
Jaucējfunkcijas ir Merkle koka struktūru pamatā, tāpēc iesakām pārbaudīt Kas ir jaukšana? pirms turpināt.
Kā darbojas Merkles koki?
Pieņemsim, ka vēlaties lejupielādēt lielu failu. Izmantojot atvērtā pirmkoda programmatūru, jūs parasti vēlaties pārbaudīt, vai lejupielādētā faila jaucējkods atbilst izstrādātāju publiskotajam failam. Ja tā ir, jūs zināt, ka jūsu datorā esošais fails ir tieši tāds pats kā viņu fails.
Ja jaucējvērtības nesakrīt, jums ir problēma. Jūs vai nu esat lejupielādējis ļaunprātīgu failu, kas tiek maskēts kā programmatūra, vai arī tas nav lejupielādēts pareizi un tāpēc nedarbosies. Ja tas tā ir, jūs, iespējams, nebūsit pārāk priecīgs, ja kādu laiku būs jāgaida, līdz fails tiks lejupielādēts. Tagad jums ir jāsāk process un jācer, ka tas vairs netiks sabojāts.
Ja vien būtu vieglāks veids, kā to izdarīt, jūs domājat. Par laimi, tieši šeit parādās Merkles koki. Izmantojot vienu no tiem, jūsu fails tiks sadalīts gabalos. Ja tas bija 50 GB fails, varat to sadalīt simtos gabalos, lai katrs būtu 0,5 GB liels. Pēc tam tas tiks lejupielādēts pa gabalam. Tas būtībā ir tas, ko jūs darāt, kad torrentat failus.
Šajā gadījumā jūsu avots būs nodrošinājis jūs ar jaucējkodu, kas pazīstams kā Merkles sakne. Šis viens jauktais ir katra datu gabala attēlojums, kas veido jūsu failu. Bet Merkles sakne ļauj daudz vieglāk pārbaudīt datus.
Lai tas būtu vienkārši, ņemsim piemēru, kur mēs izmantojam 8 GB failu, kas sadalīts astoņās daļās. Izsauciet dažādus fragmentus no A līdz H. Pēc tam katrs fragments tiek nodots caur jaukšanas funkciju, dodot mums astoņas dažādas jaucējfunkcijas.
Mēs izlaižam katru no astoņiem fragmentiem caur jaucējfunkciju, lai iegūtu to jaucējus.
Labi, tāpēc mums ir kaut kas jēgpilnāks. Mums ir visu fragmentu jaucējkods, tāpēc, ja kāds ir bojāts, mēs to uzzināsim, salīdzinot to ar avota fragmentu, vai ne? Iespējams, bet tas ir arī neticami neefektīvi. Ja failā ir tūkstošiem fragmentu, vai tiešām tos visus jauksiet un rūpīgi salīdzināsiet rezultātus?
Nē. Tā vietā mēs paņemsim katru jaukšanas pāri, apvienosim tos un pēc tam jauksim kopā. Tātad mēs sajaukām hA + hB, hC + hD, hE + hF un hG + hH. Mēs galu galā iegūstam četras jaucējzīmes. Pēc tam veicam vēl vienu jaukšanas kārtu ar šiem, lai beigtos ar diviem. Visbeidzot, mēs sajaucam atlikušos divus, lai nokļūtu mūsu galvenajā jaucējkodā — Merkles saknē (vai saknes jaucējkodā).
Struktūra izskatās kā apgriezts koks. Apakšējā rindā mums ir lapas, kuras tiek apvienotas, lai iegūtu mezglus un, visbeidzot, sakni.
Tagad mums ir Merkles sakne, kas apzīmē lejupielādēto failu. Mēs varam salīdzināt šo saknes hash ar to, ko nodrošina avots. Ja sakrīt, ideāli! Bet, ja jaucējvērtības atšķiras, mēs varam būt pārliecināti, ka dati ir mainīti. Citiem vārdiem sakot, viens vai vairāki fragmenti ir radījuši atšķirīgu hash. Tātad jebkura neliela datu pārveidošana dos mums pilnīgi atšķirīgu Merkles sakni.
Par laimi, mums ir ērts veids, kā pārbaudīt, kurš fragments ir bojāts. Mūsu gadījumā pieņemsim, ka tas ir viņš. Jūs sāktu, pajautājot vienaudžiem diviem hashiem, kas radīja Merkles sakni (hABCD un hEFGH). Jūsu vērtībai hABCD ir jāatbilst viņu vērtībai, jo šajā apakškokā nav kļūdu. Bet hEFGH nedarīs, tāpēc jūs zināt, lai reģistrētos tur. Pēc tam jūs pieprasāt hEF un hGH un salīdzināt tos ar savējiem. hGH izskatīsies labi, tāpēc jūs zināt, ka hEF ir mūsu vaininieks. Visbeidzot, jūs salīdzināt hE un hF jaucējvērtības. Tagad jūs zināt, ka viņš ir nepareizs, tāpēc varat atkārtoti lejupielādēt šo daļu.
Apkopojot visu, Merkles koks tiek izveidots, sadalot datus daudzos gabalos, kas pēc tam tiek atkārtoti sajaukti, veidojot Merkles sakni. Pēc tam varat efektīvi pārbaudīt, vai ar kādu datu daļu kaut kas nav noticis. Kā redzēsim nākamajā sadaļā, ir arī citas interesantas lietojumprogrammas.
Vai vēlaties sākt darbu ar kriptovalūtu? Pērciet Bitcoin vietnē Binance!
Kāpēc Merkles saknes tiek izmantotas Bitcoin?
Merkle kokiem ir daži lietošanas gadījumi, taču šeit mēs koncentrēsimies uz to nozīmi blokķēdēs. Merkles koki ir būtiski Bitcoin un daudzās citās kriptovalūtās. Tie ir katra bloka neatņemama sastāvdaļa, kur tos var atrast bloku galvenēs. Lai iegūtu lapas mūsu kokam, mēs izmantojam katra blokā iekļautā darījuma transakcijas jaucējkodu (TXID).
Merkles sakne šajā gadījumā kalpo vairākiem mērķiem. Apskatīsim viņu lietojumprogrammas kriptovalūtas ieguvē un darījumu pārbaudē.
Kalnrūpniecība
Bitcoin bloks sastāv no diviem gabaliem. Pirmā daļa ir bloka galvene, fiksēta izmēra segments, kas satur bloka metadatus. Otrā daļa ir to darījumu saraksts, kuru lielums ir mainīgs, bet mēdz būt daudz lielāks par galveni.
Kalnračiem ir atkārtoti jājauc dati, lai iegūtu izvadi, kas atbilst noteiktiem nosacījumiem, lai iegūtu derīgu bloku. Viņi var veikt triljoniem mēģinājumu, pirms to atrod. Ar katru mēģinājumu viņi maina nejaušu skaitli bloka galvenē (nonce), lai iegūtu citu izvadi. Bet liela daļa bloka paliek nemainīga. Var būt tūkstošiem darījumu, un jums tie joprojām ir jājauc katru reizi.
Merkles sakne ievērojami racionalizē procesu. Kad sākat ieguvi, jūs sarindojat visus darījumus, kurus vēlaties iekļaut, un izveidojat Merkle koku. Iegūto saknes hash (32 baiti) ievietojat bloka galvenē. Pēc tam, veicot ieguvi, jums ir jājauc tikai bloka galvene, nevis viss bloks.
Tas darbojas, jo ir drošs pret viltojumiem. Jūs efektīvi apkopojat visus bloka darījumus kompaktā formātā. Jūs nevarat atrast derīgu bloka galveni un vēlāk mainīt darījumu sarakstu, jo tas mainītu Merkles sakni. Kad bloks tiek nosūtīts uz citiem mezgliem, tie aprēķina sakni no darījumu saraksta. Ja tas neatbilst galvenē esošajam, viņi noraida bloķēšanu.
Pārbaude
Ir vēl viena interesanta Merkles sakņu īpašība, ko mēs varam izmantot. Tas attiecas uz vieglajiem klientiem (mezgliem, kuriem nav pilna blokķēdes kopija). Ja izmantojat mezglu ierīcē ar ierobežotiem resursiem, jūs nevēlaties lejupielādēt un jaukt visus bloka darījumus. Tā vietā jūs varat vienkārši pieprasīt Merkle pierādījumu — pierādījumu, ko nodrošina pilns mezgls, kas pierāda, ka jūsu darījums notiek noteiktā blokā. To biežāk dēvē par vienkāršotu maksājumu verifikāciju vai SPV, un Satoshi Nakamoto to detalizēti aprakstīja Bitcoin tehniskajā dokumentā.
Lai pārbaudītu hD, mums ir vajadzīgas tikai sarkanā krāsā parādītās jaucējzīmes.
Apsveriet scenāriju, kurā mēs vēlamies uzzināt informāciju par darījumu, kura TXID ir hD. Ja mums tiek nodrošināts hC, mēs varam izstrādāt hCD. Pēc tam mums ir nepieciešams hAB, lai aprēķinātu hABCD. Visbeidzot, izmantojot hEFGH, mēs varam pārbaudīt, vai iegūtā Merkle sakne atbilst saknei no bloka galvenes. Ja tas tā ir, tas ir pierādījums tam, ka darījums tika iekļauts blokā — būtu gandrīz neiespējami izveidot vienu un to pašu jaucējfunkciju ar dažādiem datiem.
Iepriekš minētajā piemērā mums bija jājauc tikai trīs reizes. Bez Merkles pierādījuma mums tas būtu jādara septiņas reizes. Tā kā mūsdienās bloki satur tūkstošiem transakciju, Merkle proofs izmantošana ietaupa mums daudz laika un skaitļošanas resursu.
Noslēguma domas
Merkles koki ir izrādījušies ļoti noderīgi dažādās datorzinātnēs — kā mēs redzējām, tie ir neticami vērtīgi blokķēdēs. Sadalītās sistēmās Merkle koki ļauj viegli pārbaudīt informāciju, nepārpludinot tīklu ar nevajadzīgiem datiem.
Bez Merkles kokiem (un Merkles saknēm) Bitcoin un citu kriptovalūtu bloki nebūtu ne tuvu tik kompakti kā šodien. Un, lai gan privātuma un drošības jomā trūkst vieglo klientu, Merkle pierādījumi ļauj lietotājiem pārbaudīt, vai viņu darījumi ir iekļauti blokā ar minimālām pieskaitāmajām izmaksām.
