Ano ang isang Merkle Tree? Gabay ng Baguhan sa Blockchain Component na ito

Ang Merkle Trees ay isang pangunahing bahagi ng mga blockchain na nagpapatibay sa kanilang paggana. Nagbibigay-daan ang mga ito para sa mahusay at secure na pag-verify ng malalaking istruktura ng data, at sa kaso ng mga blockchain, potensyal na walang hangganang set ng data.

Ang pagpapatupad ng mga puno ng Merkle sa mga blockchain ay may maraming epekto. Nagbibigay-daan ito sa kanila na mag-scale habang nagbibigay din ng hash-based na arkitektura para mapanatili nila ang integridad ng data at isang maliit na paraan upang ma-verify ang integridad ng data.

Ang mga cryptographic hash function ay ang pinagbabatayan na teknolohiya na nagbibigay-daan sa mga Merkle tree na gumana, kaya una, mahalagang maunawaan kung ano ang cryptographic hash function.

Mabilis na Pagsusulit: Ang mga puno ng Merkle ay mga istruktura ng data na binubuo ng mga cryptographic na hash na nagbibigay-daan sa mahusay na pag-verify ng integridad at pagmamapa ng malalaking set ng data, na ginagawa itong mahalagang bahagi ng mga system tulad ng mga blockchain at distributed na kontrol sa bersyon.

Mabilis na Katotohanan

Mga Pag-andar ng Cryptographic Hash

Sa madaling salita, ang hash function ay anumang function na ginagamit upang i-map ang data ng isang arbitrary na laki (input) sa isang nakapirming laki ng output. Ang isang hashing algorithm ay inilapat sa input ng data at ang nagreresultang nakapirming haba na output ay tinutukoy bilang ang hash.

Maraming hashing algorithm ang malawak na magagamit sa publiko at maaaring mapili batay sa iyong mga pangangailangan.

Ang resultang hash mula sa arbitrary input ay hindi lamang naayos sa haba, ito rin ay ganap na natatangi sa input at ang function mismo ay deterministic. Iyon ay, kahit gaano karaming beses mong patakbuhin ang function sa parehong input, ang output ay palaging magiging pareho.

Halimbawa, kung mayroon kang sumusunod na data set sa ibaba bilang isang input, ang mga resultang output ay natatangi para sa bawat input. Pansinin kung paano sa pangalawa at pangatlong halimbawa, kahit na ang pagkakaiba ng mga input ay isang salita lamang, ang mga resultang output ay ganap na naiiba.

Napakahalaga nito dahil pinapayagan nito ang "fingerprinting" ng data.

Isang cryptographic hash function, Larawan mula sa Wikipedia

Dahil ang haba ng output (hash sum sa halimbawa) ay palaging pareho sa tinutukoy ng hashing algorithm na ginamit, malaking halaga ng data ang maaaring matukoy lamang sa pamamagitan ng kanilang resultang hash.

Sa mga system na naglalaman ng napakaraming data, ang mga benepisyo ng kakayahang mag-imbak at matukoy ang data na may nakapirming haba na output ay maaaring lumikha ng malawak na pagtitipid sa storage at makakatulong upang mapataas ang kahusayan.

Sa loob ng mga blockchain, ang mga algorithm ng hashing ay ginagamit upang matukoy ang estado ng blockchain.

Ang mga blockchain ay mga naka-link na listahan na naglalaman ng data at isang hash pointer na tumuturo sa nakaraang block, na lumilikha ng isang chain ng mga konektadong block, kaya tinawag na "blockchain".

Ang bawat bloke ay konektado sa isa't isa sa pamamagitan ng hash pointer, na siyang hash ng data sa loob ng nakaraang bloke kasama ang address ng nakaraang block. Sa pamamagitan ng pag-link ng mga bloke ng data sa format na ito, ang bawat resultang hash ng nakaraang bloke ay kumakatawan sa buong estado ng blockchain dahil ang lahat ng na-hash na data ng mga nakaraang bloke ay na-hash sa isang hash.

Ito ay kinakatawan (sa kaso ng SHA-256 algorithm) ng isang output (hash) tulad nito:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Ang hash sa itaas ay ang fingerprint ng buong estado ng blockchain bago ito. Ang estado ng blockchain bago ang bagong block (bilang hashed data) ay ang input, at ang resultang hash ay ang output.

Bagama't posibleng gumamit ng mga cryptographic na hash nang walang mga puno ng Merkle, ito ay lubhang hindi mabisa at hindi nasusukat. Ang paggamit ng mga hash upang mag-imbak ng data sa isang bloke sa isang format ng serye ay nakakaubos ng oras at mahirap.

Tulad ng makikita mo, ang mga Merkle tree ay nagbibigay-daan para sa maliit na resolusyon ng integridad ng data pati na rin ang pagmamapa ng data na iyon sa buong puno gamit ang mga Merkle proof.

Mga Puno ng Merkle at Mga Katibayan ng Merkle

Pinangalanan pagkatapos ng Ralph Merkle, na nag-patent ng konsepto noong 1979, ang mga puno ng Merkle sa panimula ay mga puno ng istruktura ng data kung saan ang bawat node na hindi dahon ay isang hash ng kani-kanilang mga child node.

Ang mga leaf node ay ang pinakamababang tier ng mga node sa puno. Sa una, maaaring mukhang mahirap unawain, ngunit kung titingnan mo ang karaniwang ginagamit na figure sa ibaba, magiging mas madali itong maunawaan.

Isang halimbawa ng binary hash tree, Larawan mula sa Wikipedia

Mahalaga, pansinin kung paanong ang mga non-leaf node o "mga sanga" (kinakatawan ng Hash 0-0 at Hash 0-1) sa kaliwang bahagi, ay mga hash ng kani-kanilang mga anak na L1 at L2. Dagdag pa, pansinin kung paano ang branch Hash 0 ay ang hash ng mga pinagdugtong na bata nito, ang mga branch na Hash 0-0 at Hash 0-1.

Ang halimbawa sa itaas ay ang pinakakaraniwan at simpleng anyo ng isang Merkle tree na kilala bilang isang Binary Merkle Tree. Tulad ng nakikita mo, mayroong isang tuktok na hash na ang hash ng buong puno, na kilala bilang root hash. Sa pangkalahatan, ang mga Merkle tree ay isang istraktura ng data na maaaring tumagal ng "n" na bilang ng mga hash at kinakatawan ito ng isang hash.

Ang istraktura ng puno ay nagbibigay-daan para sa mahusay na pagmamapa ng arbitraryong malalaking halaga ng data at nagbibigay-daan sa madaling pagtukoy kung saan nangyayari ang mga pagbabago sa data na iyon. Ang konseptong ito ay nagbibigay-daan sa mga patunay ng Merkle, kung saan, maaaring ma-verify ng isang tao na ang pag-hash ng data ay pare-pareho hanggang sa puno at nasa tamang posisyon nang hindi na kailangang aktwal na tumingin sa buong hanay ng mga hash.

Sa halip, maaari nilang i-verify na ang isang data chunk ay naaayon sa root hash sa pamamagitan lamang ng pagsuri sa isang maliit na subset ng mga hash sa halip na sa buong set ng data.

Hangga't ang root hash ay kilala at pinagkakatiwalaan ng publiko, posible para sa sinumang gustong gumawa ng key-value lookup sa isang database na gumamit ng Merkle proof upang i-verify ang posisyon at integridad ng isang piraso ng data sa loob ng isang database na mayroong isang partikular na ugat.

Kapag available na ang root hash, maaaring matanggap ang hash tree mula sa anumang hindi pinagkakatiwalaang source at maaaring ma-download ang isang sangay ng tree nang sabay-sabay na may agarang pag-verify ng integridad ng data, kahit na hindi pa available ang buong tree.

Ang isa sa pinakamahalagang benepisyo ng istruktura ng Merkle tree ay ang kakayahang patotohanan ang mga arbitraryong malalaking hanay ng data sa pamamagitan ng katulad na mekanismo ng pag-hash na ginagamit upang i-verify ang mas maliit na dami ng data.

Ang puno ay kapaki-pakinabang para sa pamamahagi ng malalaking set ng data sa mga napapamahalaang mas maliliit na bahagi kung saan ang hadlang para sa pag-verify ng integridad ay nababawasan nang malaki sa kabila ng pangkalahatang mas malaking laki ng data.

Ang root hash ay maaaring gamitin bilang fingerprint para sa isang buong set ng data, kabilang ang isang buong database o kumakatawan sa buong estado ng isang blockchain. Sa mga sumusunod na seksyon, tatalakayin natin kung paano ipinapatupad ng Bitcoin at iba pang mga sistema ang mga puno ng Merkle.

Mga Puno ng Merkle sa Bitcoin

Ang cryptographic hash function na ginagamit ng Bitcoin ay ang SHA-256 algorithm. Ito ay kumakatawan sa "Secure Hashing Algorithm", na ang output ay isang nakapirming 256 bits ang haba. Ang pangunahing pag-andar ng mga puno ng Merkle sa Bitcoin ay mag-imbak, at kalaunan ay putulin ang mga transaksyon sa bawat bloke.

Tulad ng nabanggit kanina, ang mga bloke sa isang blockchain ay konektado sa pamamagitan ng mga hash ng nakaraang bloke. Sa Bitcoin, ang bawat bloke ay naglalaman ng lahat ng mga transaksyon sa loob ng bloke na iyon pati na rin ang block header na binubuo ng:

• I-block ang Numero ng Bersyon
• Nakaraang Block Hash
• Timestamp
• Target ng Hirap sa Pagmimina
• Nonce
• Merkle Root Hash

Ang larawan sa ibaba ay mula sa Bitcoin whitepaper at inilalarawan kung paano umaangkop ang Merkle tree sa bawat bloke.

Ang mga transaksyon ay kasama sa mga bloke ng mga minero at na-hash bilang bahagi ng isang Merkle tree, na humahantong sa Merkle root na naka-imbak sa block header. Ang disenyo na ito ay may isang bilang ng mga natatanging benepisyo.

Kapansin-pansin, gaya ng nakabalangkas sa whitepaper, nagbibigay-daan ito sa pagkakaroon ng Simple Payment Verification (SPV) node, na kilala rin bilang "mga magaan na kliyente." Ang mga node na ito ay hindi kailangang i-download ang buong Bitcoin blockchain, tanging ang mga block header ng pinakamahabang chain.

Magagawa ito ng mga SPV node sa pamamagitan ng pagtatanong sa kanilang mga peer node hanggang sa kumbinsido sila na ang mga nakaimbak na block header na kanilang pinapatakbo ay bahagi ng pinakamahabang chain. Magagawang matukoy ng isang SPV node ang status ng isang transaksyon sa pamamagitan ng paggamit ng Merkle proof upang imapa ang transaksyon sa isang partikular na Merkle tree na may root hash ng kaukulang Merkle tree na iyon sa isang block header na bahagi ng pinakamahabang chain.

Bukod pa rito, ang pagpapatupad ng Bitcoin ng mga puno ng Merkle ay nagbibigay-daan para sa pruning ng blockchain upang makatipid ng espasyo. Ito ay resulta ng root hash lamang ang nakaimbak sa block header, samakatuwid, ang mga lumang bloke ay maaaring putulin sa pamamagitan ng pag-alis ng mga hindi kinakailangang sanga ng Merkle tree habang pinapanatili lamang ang mga kailangan para sa Merkle proof.

Pagpapatupad ng Mga Puno ng Merkle sa Iba pang mga Blockchain at Sistema

Bagama't ang Bitcoin ang unang blockchain na nagpatupad ng mga puno ng Merkle, maraming iba pang mga blockchain ang nagpapatupad ng mga katulad na istruktura ng puno ng Merkle o kahit na mas kumplikadong mga bersyon.

Dagdag pa, ang pagpapatupad ng Merkle tree ay hindi lamang limitado sa mga blockchain at inilalapat sa iba't ibang mga sistema.

Ang Ethereum, bilang isa pang pinakakilalang cryptocurrency, ay isa ring magandang halimbawa ng ibang pagpapatupad ng Merkle tree. Dahil ang Ethereum ay kumpleto na bilang isang platform para sa pagbuo ng mas kumplikadong mga application, gumagamit ito ng mas kumplikadong bersyon ng Merkle tree na tinatawag na Merkle Patricia Tree na talagang 3 magkahiwalay na Merkle tree na ginagamit para sa tatlong uri ng mga bagay. Maaari kang matuto nang higit pa tungkol sa mga punong ito dito.

Sa wakas, ang mga Merkle tree ay mahalagang bahagi ng mga distributed version control system gaya ng Git at IPFS. Ang kanilang kakayahang madaling matiyak at ma-verify ang integridad ng data na ibinabahagi sa pagitan ng mga computer sa isang P2P na format ay ginagawa silang napakahalaga sa mga system na ito.

Konklusyon

Ang mga puno ng Merkle ay isang mahalagang bahagi ng mga blockchain at epektibong nagbibigay-daan sa kanila na gumana nang may napapatunayang immutability at integridad ng transaksyon.

Ang pag-unawa sa papel na ginagampanan nila sa mga distributed network at ang kanilang pinagbabatayan na teknolohiya ng cryptographic hash functions ay napakahalaga sa pag-unawa sa mga pangunahing konsepto sa loob ng cryptocurrencies habang patuloy silang nagiging mas malaki at mas kumplikadong mga system.