Ang konsepto ng isang Merkle tree ay iminungkahi noong unang bahagi ng ‘80s ni Ralph Merkle – isang siyentista sa kompyuter na kilala sa kanyang gawain sa
public-key cryptography.
Ang Merkle tree ay isang istrakturang ginamit upang mahusay na mapatunayan ang integridad ng data sa isang hanay. Partikular silang kawili-wili sa konteksto ng mga
peer-to-peer network, kung saan kailangang ibahagi ng mga kalahok at malayang patunayan ang impormasyon.
Ang mga function ng Hash ay nasa core ng mga istraktura ng Merkle tree, kaya inirerekumenda naming suriin mo ang
Ano ang Hashing? bago magpatuloy.
Ipagpalagay na nais mong mag-download ng isang malaking file. Sa pamamagitan ng
open-source software, karaniwang nais mong suriin kung ang hash ng file na iyong na-download ay tumutugma sa isang ginawang pampubliko ng mga developer. Kung gagawin ito, malalaman mo na ang file na mayroon ka sa iyong kompyuter ay eksaktong kapareho ng sa kanila.
Kung ang mga hash ay hindi tumutugma, mayroon kang problema. Na-download mo man ang isang nakakahamak na file na nagpapakunwari bilang software, o hindi ito na-download nang tama at, samakatuwid, ay hindi gagana. Kung ang huli ay ang kaso, marahil ay hindi ka masyadong nasisiyahan kung kailangan mong maghintay para sa ilang oras para ma-download ang file. Ngayon, kailangan mong simulan ulit ang proseso at inaasahan na hindi na ito muli masira.
Kung mayroon lang isang mas madaling paraan upang magawa ito, sa palagay mo. Sa kasamaang palad, doon pumapasok ang mga Merkle tree. Sa isa sa mga ito, naisasira ang iyong file sa mga chunk. Kung ito ay 50GB file, puwede mo itong hatiin sa isang daang piraso, tulad ng bawat isa ay 0.5GB ang laki. Pagkatapos, mai-download nang paunti-unti. Ito ang mahalagang ginagawa mo kapag nag-torrent ng mga file.
Sa kasong ito, bibigyan ka ng iyong mapagkukunan ng isang hash na kilala bilang Merkle root. Ang solong hash na ito ay isang representasyon ng bawat tipak ng data na bumubuo sa iyong file. Ngunit ang Merkle root ay ginagawang mas madali upang ma-verify ang data.
Upang mapanatili itong simple, kumuha tayo ng isang halimbawa kung saan gumagamit kami ng 8GB file na pinaghiwa-hiwalay sa walong piraso. Tawagin ang iba't ibang mga fragment A hanggang H. Ang bawat fragment ay pagkatapos ay dumaan sa isang hash function, na nagbibigay sa amin ng walong magkakaibang mga hash.
Pinapasa namin ang bawat isa sa aming walong mga fragment sa pamamagitan ng isang hash function upang makuha ang kanilang mga hash.
Okay, kaya't mayroon kaming isang bagay na medyo may katuturan. Mayroon kaming hash ng lahat ng mga fragment, kaya kung ang isa ay may sira, malalaman natin sa pamamagitan ng paghahambing nito sa isa sa pinagmulan, tama? Posible, ngunit hindi rin kanais-nais na hindi mabisa. Kung ang iyong file ay may libu-libong mga fragment, maha-hash mo ba ang lahat ng mga ito at masusing pinaghahambing ang mga resulta?
Hindi. Sa halip ay kukuha kami ng bawat pares ng mga hash, pagsamahin ito, at pagkatapos ay i-hash ang mga ito nang magkasama. Kaya't mayroon kaming hA hB, hC hD, hE hF, at hG hH. Napunta kami sa apat na mga hash. Pagkatapos ay gumawa kami ng isa pang pag-ikot ng pag-hash sa mga ito upang magtapos sa dalawa. Pangwakas, maha-hash namin ang natitirang dalawa upang makapunta sa aming master hash – ang Merkle root (o root hash).
Ang istraktura ay mukhang isang baligtad na puno. Sa ibabang hilera, mayroon kaming mga dahon, na pinagsama upang makabuo ng mga node at, sa wakas, ang ugat.
Mayroon na kaming Merkle root na kumakatawan sa file na aming na-download. Puwede naming ihambing ang root hash na ito sa ibinigay ng mapagkukunan. Kung tumutugma ito, perpekto! Ngunit kung ang mga hash ay magkakaiba, makakasiguro kaming nabago ang data. Sa madaling salita, ang isa o higit pang mga fragment ay nakagawa ng iba't ibang hash. Kaya't ang anumang bahagyang pagbabago ng data ay magbibigay sa amin ng ganap na magkakaibang Merkle root.
Sa kasamaang palad, may isang madaling gamiting paraan para masuri namin kung aling fragment ang may sira. Sa aming kaso, sabihin nating ito ay ang hE. Magsisimula ka sa pamamagitan ng pagtatanong sa isang kapantay para sa dalawang hashes na gumawa ng Merkle root (hABCD at hEFGH). Ang iyong halagang hABCD ay dapat na tumugma sa kanila dahil walang pagkakamali sa subtree na iyon. Ngunit ang hEFGH ay hindi, kaya alam mong mag-check in doon. Humiling ka pagkatapos ng hEF at hGH, at ihambing ang mga ito sa iyo. Ang hGH ay magiging maayos, kaya alam mo na ang hEF ang aming salarin. Panghuli, ihinahambing mo ang mga hashe ng hE at hF. Alam mo na ngayon na ang hE ay hindi tama, kaya puwede mong ma-download ulit ang tipak na iyon.
Sa kabuuan, ang isang Merkle tree ay nilikha sa pamamagitan ng paghahati ng data sa maraming mga piraso, na pagkatapos ay paulit-ulit na na-hash upang mabuo ang Merkle root. Mahusay mong ma-e-verify kung may mali sa isang piraso ng data. Tulad ng makikita natin sa susunod na seksyon, may iba pang mga kagiliw-giliw na application.
Nagbabalak na makapagsimula sa cryptocurrency? Bumili ng Bitcoin sa Binance!
Mayroong isang maliit na mga kaso ng paggamit para sa mga Merkle tree, ngunit dito ay magtutuon kami sa kanilang kahalagahan sa
mga blockchain. Mahalaga ang mga merkle tree sa
Bitcoin at maraming iba pang mga cryptocurrency. Ang mga ito ay isang mahalagang bahagi ng bawat
block, kung saan sila matatagpuan sa
mga header ng block. Upang makuha ang mga dahon para sa aming puno, ginagamit namin ang hash ng transaksyon (ang
TXID) ng bawat transaksyon na kasama sa block.
Naghahain ang Merkle root ng ilang mga layunin sa kasong ito. Tingnan natin ang kanilang mga aplikasyon sa pagmimina ng cryptocurrency at pag-verify sa transaksyon.
Pagmimina
Ang Bitcoin block ay binubuo ng dalawang piraso. Ang unang bahagi ay ang header ng block, isang nakapirming sukat na naglalaman ng
metadata para sa block. Ang pangalawang bahagi ay isang listahan ng mga transaksyon na ang laki ay variable, ngunit may kaugaliang mas malaki kaysa sa header.
Kailangang paulit-ulit na ma-hash ng mga minero ang data upang makagawa ng isang output na tumutugma sa ilang mga kundisyon upang mamina ng ang wastong block. Puwede silang gumawa ng trilyon na mga pagtatangka bago maghanap ng isa. Sa bawat pagtatangka, binago nila ang isang random na numero sa block header (ang
nonce) upang makagawa ng ibang output. Ngunit marami sa harangan ay nananatiling pareho. Puwedeng maging libu-libong mga transaksyon, at kakailanganin mo pa ring ma-hash ang mga ito sa bawat oras.
Ang Merkle root ay na-streamline ang proseso nang malaki. Kapag sinimulan mo ang pagmimina, nililinya mo ang lahat ng mga transaksyon na nais mong isama at bumuo ng isang Merkle tree. Inilagay mo ang nagresultang root hash (32 bytes) sa block header. Pagkatapos, kapag nagmimina ka, kailangan mo lang ma-hash ang block header, sa halip na ang buong block.
Gumagana ito dahil ito ay tamper-proof. Epektibo mong ibubuod ang lahat ng mga transaksyon ng block sa isang compact format. Hindi ka makakahanap ng wastong header ng block at sa paglaon ay mababago ang listahan ng transaksyon, dahil mababago nito ang Merkle root. Kapag ang block ay ipinadala sa iba pang mga node, kinakalkula nila ang ugat mula sa listahan ng transaksyon. Kung hindi ito tumutugma sa isa sa header, tinanggihan nila ang block.
Pag-verify
May isa pang kagiliw-giliw na pag-aari ng mga Merkle root na puwede nating magamit. Ang isang ito ay patungkol sa mga magaan na kliyente (mga node na hindi nagtataglay ng isang buong kopya ng blockchain). Kung nagpapatakbo ka ng isang node sa isang device na may limitadong mapagkukunan, hindi mo nais na ma-download at ma-hash ang lahat ng mga transaksyon ng isang block. Ang puwede mong gawin sa halip ay humiling lang ng isang patunay ng Merkle – katibayan na ibinigay ng buong node na nagpapatunay na ang iyong transaksyon ay nasa isang partikular na block. Ito ay mas karaniwang tinutukoy bilang Pinasimple na Pag-verify sa Pagbabayad, o SPV, at detalyado ni
Satoshi Nakamoto sa whitepaper ng Bitcoin.
Upang suriin ang hD, kailangan lang namin ang mga hash na ipinapakita sa pula.
Isaalang-alang ang senaryo kung saan nais naming malaman ang impormasyon tungkol sa transaksyon na ang TXID ay hD. Kung ang hC ay ibinigay sa amin, puwede naming maisagawa ang hCD. Pagkatapos, kailangan namin ng hAB upang makalkula ang hABCD. Panghuli, sa hEFGH, puwede nating suriin na ang nagresulta ng Merkle root ay tumutugma sa isa mula sa block header. Kung gagawin ito, pruweba ito na ang transaksyon ay kasama sa block – malapit nang imposibleng lumikha ng parehong hash na may iba't ibang data.
Sa halimbawa sa itaas, kinailangan lang naming mag-hash ng tatlong beses. Nang walang isang patunay ng Merkle, kakailanganin naming gawin ito ng pitong beses. Dahil ang mga block sa ngayon ay naglalaman ng libu-libong mga transaksyon, ang paggamit ng mga patunay ng Merkle ay nakakatipid sa atin ng maraming oras at mga mapagkukunan sa computing.
Pinatunayan ng mga merkle tree ang kanilang sarili na lubos na kapaki-pakinabang sa isang hanay ng mga aplikasyon sa computer science – tulad ng nakita natin, napakahalaga nila sa mga blockchain. Sa mga ipinamamahaging system, pinapayagan ng mga Merkle tree ang madaling pag-verify ng impormasyon nang hindi binabaha ang network ng hindi kinakailangang data.
Kung walang mga Merkle tree (at mga Merkle root), ang mga block ng
Bitcoin at iba pang
mga cryptocurrency ay hindi magiging kasing compact tulad ng ngayon. At habang ang mga magaan na kliyente ay kulang sa mga harap ng privacy at seguridad, pinahihintulutan ng Merkle na mga user na suriin kung ang kanilang mga transaksyon ay isinama sa isang block na may kaunting overhead.
