Saturs
Merkles koks ir struktūra, kuru izmanto, lai efektīvi verificētu datu integritāti datu kopā. Tas ir jo īpaši interesanti
vienādranga tīklu kontekstā, kad tīkla dalībniekiem ir nepieciešams kopīgot un neatkarīgi validēt informāciju.
Merkles koka struktūru pamatā ir jaukšanas funkcijas, tāpēc vispirms aicinām izlasīt sadaļu
Kas ir jaukšana? .
Pieņemsim, ka tu vēlies lejupielādēt apjomīgu failu. Ar
atvērtā pirmkoda programmatūru tu, visticamāk, vēlēsies pārbaudīt, vai lejupielādētā faila jaucējkods atbilst izstrādātāju publiskotajam. Ja tas atbilst, tu vari būt drošs, ka fails tavā datorā precīzi atbilst izstrādātāja failam.
Ja jaucējkodi atšķiras, tev ir problēma. Tu vai nu esi lejupielādējis ļaunprātīgu failu, kas tiek slēpts programmatūras veidolā, vai arī lejupielāde nav notikusi pareizi un fails tāpēc nedarbojas. Otrajā gadījumā tu, visticamāk, nebūsi apmierināts pēc tam, kad būsi gaidījis, līdz apjomīgais fails beidzot tiks lejupielādēts. Tagad tev būs jāsāk viss no gala un jācer, ka nākamreiz fails darbosies.
Tu, iespējams, nodomāsi: "Ja vien būtu vienkāršāks veids, kā to atrisināt...". Par laimi, šajā situācijā var noderēt Merkles koks. Tas ļautu sadalīt failu mazākās daļiņās. 50 GB failu varētu sadalīt simt daļās – katru 0,5 GB lielumā. Pēc tam varētu katru no šīm daļām lejupielādēt atsevišķi. Tieši tā notiek torenta failu lejupielāde.
Šajā gadījumā avots tev būtu piešķīris jaucējkodu jeb Merkles sakni. Šis jaucējkods ietver katru datu daļiņu, kas visas kopā veido attiecīgo failu. Tomēr ar Merkles sakni ir daudz vieglāk pārbaudīt datus.
Labākai izpratnei apskatīsim piemēru, kurā izmantosim 8 GB failu, sadalot to astoņās daļās. Apzīmēsim šos fragmentus ar burtiem no A līdz H. Pēc tam katram no šiem fragmentiem tiks izmantota jaukšanas funkcija, kā rezultātā iegūsim astoņus atšķirīgus jaucējkodus.
Katram no šiem astoņiem fragmentiem tiks izpildīta jaukšanas funkcija, lai iegūtu fragmentu jaucējkodus.
Labi, tagad viss kļūst jau nedaudz skaidrāks. Mums ir visu fragmentu jaucējkodi, kas nozīmē, ka, ja kāds no fragmentiem ir bojāts, mēs to varēsim noskaidrot, salīdzinot ar avota datiem, vai ne? Iespējams, taču tas ir arī ārkārtīgi neefektīvi. Ja failā ir tūkstošiem fragmentu, vai tu veiksi jaukšanu tiem visiem un rūpīgi salīdzināsi rezultātus?
Nē. Tā vietā mēs ņemsim katru jaucējkodu pāri, salīdzināsim tos un pēc tam jauksim tos kopā. Tātad mēs jauksimhA + hB, hC + hD, hE + hF un hG + hH. Rezultātā iegūsim četrus jaucējkodus. Pēc tam mēs atkal veiksim jaukšanu šiem četriem jaucējkodiem un rezultātā iegūsim divus. Visbeidzot, izpildīsim jaukšanas funkciju atlikušajiem diviem un iegūsim galveno jaucējkodu – t. s. Merkles sakni (jeb saknes jaucējkodu).
Struktūra atgādina otrādi apgrieztu koku. Apakšējā rindā atrodas lapas, kas kopā veido mezglus un, visbeidzot, sakni.
Tagad esam ieguvuši Merkles sakni, kas atbilst lejupielādētajam failam. Varam šo saknes jaucējkodu salīdzināt ar avota sniegto. Ja tie ir vienādi – lieliski! Tomēr, ja jaucējkodi atšķiras, varam būt droši, ka dati ir mainīti. Citiem vārdiem sakot, viens vai vairāki fragmenti radīja atšķirīgus jaucējkodus. Tātad pat niecīgākās izmaiņas datos radīs pilnīgi atšķirīgu Merkles sakni.
Par laimi, pastāv parocīgs veids, kā identificēt problemātisko fragmentu. Mūsu gadījumā pieņemsim, ka tas ir hE. Vispirms mēs pavaicāsim lietotājam abus jaucējkodus, kas veidoja Merkles sakni (hABCD un hEFGH). Iegūtajai vērtībai hABCD vajadzētu atbilst otra lietotāja iegūtajai vērtībai, jo šajā apakškokā nav kļūdu. Tomēr hEFGH gadījumā vērtības nesakritīs, tāpēc zināsim, ka jāpārbauda ir šī daļa. Tad pieprasīsim hEF un hGH datus un salīdzināsim tos ar savējiem. hGH izskatīsies labi, un tas nozīmēs, ka "vainīgais" posms ir hEF. Visbeidzot, salīdzinināsim hE un hF jaucējkodus. Tagad zinām, ka hE ir kļūdains, tāpēc varam no jauna lejupielādēt tieši šo fragmentu.
Rezumējot – Merkles koku iegūst, sadalot datus daudzās daļās, kuras pēc tam tiek atkārtoti jauktas, veidojot Merkles sakni. Pēc tam var efektīvi pārbaudīt, vai ar kādu datu daļu ir radušās kādas problēmas. Kā redzēsim nākamajā sadaļā, šo koncepciju var izmantot arī citos interesantos veidos.
Vēlies sākt izmantot kriptovalūtas? Pērc Bitcoin platformā Binance!
Merkles kokus var izmantot dažādiem mērķiem, taču mēs pievērsīsimies tiem, kas ir nozīmīgi
blokķēžu kontekstā. Merkles kokiem ir būtiska loma
Bitcoin un daudzu citu kriptovalūtu darbībā. Tie ir katra
bloka neatņemama sastāvdaļa, kas atrodama
bloka galvenē. Lai iegūtu koka lapas, mēs izmantojam katra blokā ietvertā darījuma jaucējkodu (
TXID).
Šajā gadījumā Merkles sakne kalpo vairākiem mērķiem. Apskatīsim tās izmantošanas iespējas kriptovalūtu ieguvē un darījumu verificēšanā.
Ieguve
Bitcoin bloku veido divas daļas. Pirmā daļa ir bloka galvene – nemainīga izmēra segments, kas ietver attiecīgā bloka
metadatus. Otrā daļa ir darījumu saraksts, kura lielums ir mainīgs, bet parasti daudz lielāks par galveni.
Lai iegūtu derīgu bloku, ieguvējiem ir atkārtoti jājauc dati, līdz tiek iegūts rezultāts, kas atbilst noteiktiem nosacījumiem. Var veikt triljoniem mēģinājumu, līdz tiek atrasts īstais risinājums. Ar katru mēģinājumu viņi maina nejaušu skaitli bloka galvenē (
vienreizējo kodu), lai iegūtu atšķirīgu rezultātu. Tomēr lielākā daļa bloka nemainās. Var būt tūkstošiem darījumu, un vienalga katru reizi būs jāveic jaukšana.
Merkles sakne ievērojami vienkāršo šo procesu. Sākot ieguves procesu, tiek sarindoti visi darījumi, kuri ir jāiekļauj Merkles kokā. Bloka galvenē tiek ievietots iegūtais saknes jaucējkods (32 baiti). Pēc tam ieguves laikā ir jājauc tikai bloka galvene, nevis viss bloks.
Šis risinājums darbojas, jo tas ir drošs. Tā ir iespēja efektīvi apkopot visus bloka darījumus kompaktā formātā. Nav iespējams atrast derīgu bloka galveni un pēc tam mainīt darījumu sarakstu, jo tas mainītu Merkles sakni. Kad bloks ir nosūtīts uz citiem mezgliem, tie aprēķina sakni no darījumu saraksta. Ja rezultāts neatbilst galvenē norādītajam, bloks tiek noraidīts.
Verifikācija
Pastāv vēl viena interesanta Merkles sakņu īpašība, kuru varam izmantot. Tā ir saistīta ar plānajiem klientiem (mezgliem, kas neietver blokķēdes pilnu kopiju). Ja mezgls tiek darbināts ierīcē ar ierobežotiem resursiem, tu nevēlēsies lejupielādēt un jaukt visus bloka darījumus. Tā vietā pastāv iespēja vienkārši pieprasīt Merkles apliecinājumu – pierādījumu no pilnā mezgla tam, ka darījums ietilpst attiecīgajā blokā. To biežāk sauc par vienkāršoto maksājumu verifikāciju (SPV), kas detalizēti izklāstīta
Satoshi Nakamoto izstrādātajā Bitcoin tehniskajā dokumentā.
Lai pārbaudītu hD, ir nepieciešami tikai sarkanā krāsā atzīmētie jaucējkodi.
Iedomājies situāciju, kad ir jāiegūst informācija par darījumu, kura TXID ir hD. Ja mums ir zināms hC, varam iegūt hCD. Pēc tam mums ir jānoskaidro hAB, lai varētu aprēķināt hABCD. Visbeidzot, zinot hEFGH, varam pārbaudīt, vai rezultātā iegūtā Merkles sakne atbilst bloka galvenē norādītajai. Ja tās ir vienādas, tas pierāda, ka attiecīgais darījums bija iekļauts blokā, jo būtu teju neiespējami izveidot tādu pašu jaucējkodu ar atšķirīgiem datiem.
Apskatītajā piemērā jaukšanu veicām vien trīs reizes. Bez Merkles apliecinājuma tas būtu jādara septiņas reizes. Tā kā bloki mūsdienās ietver tūkstošiem darījumu, Merkles apliecinājums ļauj ievērojami ietaupīt laiku un skaitļošanas resursus.
Merkles koki ir apliecinājuši savu lietderību dažādos datorzinātnes aspektos – kā jau redzējām, tie ir ārkārtīgi noderīgi blokķēdēs. Decentralizētās sistēmās Merkles koki ļauj vienkāršā veidā verificē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ādi tie ir šobrīd. Un, lai gan plānajiem klientiem ir nepilnības privātuma un drošības jomās, Merkles apliecinājumi ļauj lietotājiem ar minimālām izmaksām pārbaudīt, vai viņu darījumi ir iekļauti blokā.
