Ce este un arbore Merkle? Ghid pentru începători pentru această componentă Blockchain

Merkle Trees sunt o componentă fundamentală a blockchain-urilor care susțin funcționalitatea acestora. Acestea permit verificarea eficientă și sigură a structurilor mari de date și, în cazul blockchain-urilor, seturi de date potențial nelimitate.

Implementarea arborilor Merkle în blockchains are efecte multiple. Le permite să se scaleze, oferind în același timp arhitectura bazată pe hash pentru a menține integritatea datelor și o modalitate trivială de a verifica integritatea datelor.

Funcțiile hash criptografice sunt tehnologia de bază care permite ca arborii Merkle să funcționeze, așa că, mai întâi, este important să înțelegem ce sunt funcțiile hash criptografice.

Verdictul rapid: Arborii Merkle sunt structuri de date compuse din hashuri criptografice care permit verificarea eficientă a integrității și maparea seturilor mari de date, făcându-le o componentă integrală a sistemelor precum blockchain-urile și controlul distribuit al versiunilor.

Fapte rapide

Funcții hash criptografice

Mai simplu spus, o funcție hash este orice funcție care este utilizată pentru a mapa date de o dimensiune arbitrară (intrare) la o ieșire de dimensiune fixă. La intrarea datelor este aplicat un algoritm de hashing, iar rezultatul rezultat de lungime fixă ​​este denumit hash.

Mulți algoritmi de hashing sunt disponibili public pe scară largă și pot fi selectați în funcție de nevoile dvs.

Hash-ul rezultat din intrarea arbitrară nu este doar fix în lungime, ci este, de asemenea, complet unic pentru intrare, iar funcția în sine este deterministă. Adică, indiferent de câte ori rulați funcția pe aceeași intrare, ieșirea va fi întotdeauna aceeași.

De exemplu, dacă aveți următoarele seturi de date de mai jos ca intrare, ieșirile rezultate sunt unice pentru fiecare intrare. Observați cum în al doilea și al treilea exemple, chiar dacă diferența de intrări este doar un cuvânt, ieșirile rezultate sunt complet diferite.

Acest lucru este foarte important, deoarece permite „amprentarea” datelor.

O funcție hash criptografică, imagine de pe Wikipedia

Deoarece lungimea de ieșire (suma hash din exemplu) este întotdeauna aceeași cu cea determinată de algoritmul de hashing utilizat, cantități uriașe de date pot fi identificate numai prin hashul rezultat.

Cu sistemele care conțin cantități masive de date, beneficiile de a putea stoca și identifica date cu o lungime fixă ​​pot crea economii mari de stocare și pot ajuta la creșterea eficienței.

În cadrul blockchain-urilor, algoritmii de hashing sunt utilizați pentru a determina starea blockchain-ului.

Blockchain-urile sunt liste legate care conțin date și un indicator hash care indică către blocul anterior, creând un lanț de blocuri conectate, de unde și numele „blockchain”.

Fiecare bloc este conectat unul la altul printr-un pointer hash, care este hash-ul datelor din interiorul blocului anterior împreună cu adresa blocului anterior. Prin legarea blocurilor de date în acest format, fiecare hash rezultat al blocului anterior reprezintă întreaga stare a blockchain-ului, deoarece toate datele hash ale blocurilor anterioare sunt hash într-un singur hash.

Aceasta este reprezentată (în cazul algoritmului SHA-256) printr-o ieșire (hash) ca aceasta:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Hash-ul de mai sus este amprenta întregii stări a blockchain-ului înaintea acestuia. Starea blockchain-ului înainte de noul bloc (ca date hashed) este intrarea, iar hashul rezultat este rezultatul.

Deși este posibil să se utilizeze hashuri criptografice fără arbori Merkle, este extrem de ineficient și nu este scalabil. Utilizarea hashurilor pentru a stoca date într-un bloc într-un format de serie este consumatoare de timp și greoaie.

După cum veți vedea, arborii Merkle permit rezoluția trivială a integrității datelor, precum și maparea acestor date prin întregul arbore folosind dovezile Merkle.

Merkle Trees și Merkle Proofs

Numiți după Ralph Merkle, care a brevetat conceptul în 1979, arborii Merkle sunt în principiu arbori cu structură de date în care fiecare nod care nu este frunză este un hash al nodurilor sale secundare respective.

Nodurile frunzelor sunt cel mai jos nivel de noduri din arbore. La început, poate părea dificil de înțeles, dar dacă te uiți la figura folosită în mod obișnuit de mai jos, va deveni mult mai ușor de înțeles.

Un exemplu de arbore hash binar, Imagine de pe Wikipedia

Important, observați cum nodurile sau „ramurile” non-frunze (reprezentate prin Hash 0-0 și Hash 0-1) din partea stângă sunt hash-uri ale copiilor lor L1 și L2. Mai mult, observați cum ramura Hash 0 este hash-ul copiilor săi concatenați, ramurile Hash 0-0 și Hash 0-1.

Exemplul de mai sus este cea mai comună și simplă formă a arborelui Merkle cunoscut sub numele de arbore Merkle binar. După cum puteți vedea, există un hash de sus, care este hash-ul întregului copac, cunoscut sub numele de hash rădăcină. În esență, arborii Merkle sunt o structură de date care poate lua „n” număr de hash și îl poate reprezenta cu un singur hash.

Structura arborelui permite cartografierea eficientă a unor cantități arbitrar de mari de date și permite identificarea cu ușurință a locului în care apar modificări ale datelor respective. Acest concept permite dovezile Merkle, cu ajutorul cărora cineva poate verifica dacă hashing-ul datelor este consecvent pe tot parcursul arborelui și în poziția corectă, fără a fi nevoie să se uite efectiv la întregul set de hashuri.

În schimb, ei pot verifica dacă o bucată de date este în concordanță cu hash-ul rădăcină verificând doar un mic subset de hash-uri, mai degrabă decât întregul set de date.

Atâta timp cât hash-ul rădăcină este cunoscut public și de încredere, oricine dorește să facă o căutare cheie-valoare într-o bază de date este posibil să utilizeze o dovadă Merkle pentru a verifica poziția și integritatea unei date dintr-o bază de date care are o anumită rădăcină.

Când hash-ul rădăcină este disponibil, arborele hash poate fi primit de la orice sursă nede încredere și o ramură a arborelui poate fi descărcată la un moment dat, cu verificarea imediată a integrității datelor, chiar dacă întregul arbore nu este încă disponibil.

Unul dintre cele mai importante beneficii ale structurii arborelui Merkle este capacitatea de a autentifica seturi arbitrar de mari de date printr-un mecanism de hashing similar care este utilizat pentru a verifica cantități mult mai mici de date.

Arborele este avantajos pentru distribuirea de seturi mari de date în părți mai mici gestionabile, unde bariera pentru verificarea integrității este redusă substanțial în ciuda dimensiunii generale mai mari a datelor.

Hash-ul rădăcină poate fi folosit ca amprentă pentru un întreg set de date, inclusiv o întreagă bază de date sau reprezentând întreaga stare a unui blockchain. În secțiunile următoare, vom discuta despre modul în care Bitcoin și alte sisteme implementează arborii Merkle.

Merkle Trees în Bitcoin

Funcția hash criptografică folosită de Bitcoin este algoritmul SHA-256. Aceasta înseamnă „Secure Hashing Algorithm”, a cărui ieșire are o lungime fixă ​​de 256 de biți. Funcția de bază a arborilor Merkle din Bitcoin este de a stoca și, eventual, de a tăia tranzacțiile în fiecare bloc.

După cum am menționat mai devreme, blocurile dintr-un blockchain sunt conectate prin hash-uri ale blocului anterior. În Bitcoin, fiecare bloc conține toate tranzacțiile din acel bloc, precum și antetul blocului care constă din:

• Blocare numărul versiunii
• Anterior Block Hash
• Marcaj de timp
• Ținta de dificultate în minerit
• nonce
• Merkle Root Hash

Imaginea de mai jos este din cartea albă Bitcoin și ilustrează modul în care arborele Merkle se potrivește în fiecare bloc.

Tranzacțiile sunt incluse în blocuri de către mineri și sunt indexate ca parte a unui arbore Merkle, conducând la rădăcina Merkle care este stocată în antetul blocului. Acest design are o serie de beneficii distincte.

În special, așa cum se subliniază în cartea albă, acest lucru permite existența nodurilor de verificare simplă a plăților (SPV), cunoscute și sub denumirea de „clienți ușori”. Aceste noduri nu trebuie să descarce întregul blockchain Bitcoin, ci doar anteturile de bloc ale celui mai lung lanț.

Nodurile SPV pot realiza acest lucru interogând nodurile lor egale până când sunt convinși că anteturile de bloc stocate pe care operează fac parte din cel mai lung lanț. Un nod SPV este capabil să determine apoi starea unei tranzacții utilizând dovezile Merkle pentru a mapa tranzacția la un arbore Merkle specific cu hash-ul rădăcină al arborelui Merkle respectiv într-un antet de bloc care face parte din cel mai lung lanț.

În plus, implementarea de către Bitcoin a arborilor Merkle permite tăierea blockchain-ului pentru a economisi spațiu. Acesta este rezultatul stocării numai a hash-ului rădăcină în antetul blocului, prin urmare, blocurile vechi pot fi tăiate prin eliminarea ramurilor inutile ale arborelui Merkle, păstrând în același timp doar cele necesare pentru proba Merkle.

Implementarea arborilor Merkle în alte blockchain și sisteme

Deși Bitcoin a fost primul blockchain care a implementat arbori Merkle, multe alte blockchain implementează structuri de arbore Merkle similare sau chiar versiuni mai complexe.

În plus, implementarea arborelui Merkle nu se limitează doar la blockchain-uri și este aplicată la o varietate de alte sisteme.

Ethereum, fiind cealaltă criptomonedă cea mai recunoscută, este, de asemenea, un exemplu excelent de implementare diferită a arborelui Merkle. Deoarece Ethereum este o platformă completă pentru construirea de aplicații mult mai complexe, folosește o versiune mai complexă a arborelui Merkle numită arbore Merkle Patricia, care este de fapt 3 arbori Merkle separati, utilizați pentru trei tipuri de obiecte. Puteți afla mai multe despre acești copaci aici.

În cele din urmă, arborii Merkle sunt o componentă importantă a sistemelor distribuite de control al versiunilor, cum ar fi Git și IPFS. Capacitatea lor de a asigura și verifica cu ușurință integritatea datelor partajate între computere într-un format P2P le face de neprețuit pentru aceste sisteme.

Concluzie

Arborii Merkle sunt o componentă integrantă a blockchain-urilor și le permit în mod eficient să funcționeze cu imuabilitate și integritate a tranzacțiilor dovedibile.

Înțelegerea rolului pe care îl joacă ele în rețelele distribuite și tehnologia lor de bază a funcțiilor hash criptografice este crucială pentru a înțelege conceptele de bază din criptomonede, pe măsură ce acestea continuă să se dezvolte în sisteme mai mari și mai complexe.