Ce este un copac Merkle?
Conceptul de arbore Merkle a fost propus la începutul anilor ’80 de Ralph Merkle – un informatician renumit pentru munca sa asupra criptografiei cu cheie publică.
Un arbore Merkle este o structură utilizată pentru a verifica eficient integritatea datelor dintr-un set. Sunt deosebit de interesante în contextul rețelelor peer-to-peer, unde participanții trebuie să partajeze și să valideze în mod independent informațiile.
Funcțiile hash sunt la baza structurilor arborelui Merkle, așa că vă recomandăm să verificați Ce este Hashing? înainte de a începe.
Cum funcționează arborii Merkle?
Să presupunem că doriți să descărcați un fișier mare. Cu software-ul open-source, de obicei, ați dori să verificați dacă hash-ul fișierului pe care l-ați descărcat se potrivește cu cel făcut public de dezvoltatori. Dacă da, știți că fișierul pe care îl aveți pe computer este exact același cu al lor.
Dacă hashe-urile nu se potrivesc, aveți o problemă. Fie ați descărcat un fișier rău intenționat mascalat ca software, fie nu s-a descărcat corect și, prin urmare, nu va funcționa. Dacă acesta din urmă este cazul, probabil că nu veți fi prea fericit dacă ați trebuit să așteptați ceva timp pentru descărcarea fișierului. Acum, trebuie să reporniți procesul și să sperați că nu se va mai corupt.
Dacă ar fi o modalitate mai ușoară de a face asta, crezi. Din fericire, aici intervin copacii Merkle. Cu unul dintre aceștia, ți-ar fi rupt dosarul în bucăți. Dacă a fost un fișier de 50 GB, l-ați putea împărți în o sută de bucăți, astfel încât fiecare să aibă o dimensiune de 0,5 GB. Apoi, ar fi descărcat bucată cu bucată. Acest lucru este, în esență, ceea ce faci când faci fișiere torrent.
În acest caz, sursa dumneavoastră vă va fi furnizat un hash cunoscut sub numele de rădăcină Merkle. Acest hash unic este o reprezentare a fiecărei bucăți de date care formează fișierul dvs. Dar rădăcina Merkle face mult mai ușoară verificarea datelor.
Pentru a rămâne simplu, să luăm un exemplu în care folosim un fișier de 8 GB împărțit în opt bucăți. Apelați diferitele fragmente de la A la H. Fiecare fragment este apoi trecut printr-o funcție hash, dându-ne opt hash-uri diferite.
Trecem fiecare dintre cele opt fragmente ale noastre printr-o funcție hash pentru a obține hashurile lor.
Bine, deci avem ceva care are un pic mai logic. Avem hash-ul tuturor fragmentelor, așa că dacă unul este defect, îl vom ști comparându-l cu cel al sursei, nu? Posibil, dar asta este și incredibil de ineficient. Dacă fișierul tău are mii de fragmente, chiar le vei hash pe toate și vei compara meticulos rezultatele?
Nu. În schimb, vom lua fiecare pereche de hașuri, le vom combina, apoi le vom combina. Deci hașăm hA + hB, hC + hD, hE + hF și hG + hH. Sfârșim cu patru hașuri. Apoi facem o altă rundă de hashing cu acestea pentru a ajunge cu două. În cele din urmă, le facem hash pe celelalte două pentru a ajunge la hash-ul nostru principal - rădăcina Merkle (sau hash-ul rădăcină).
Structura arată ca un copac cu susul în jos. Pe rândul de jos, avem frunzele, care sunt combinate pentru a produce nodurile și, în final, rădăcina.
Acum avem rădăcina Merkle care reprezintă fișierul pe care l-am descărcat. Putem compara acest hash rădăcină cu cel furnizat de sursă. Daca se potriveste, perfect! Dar dacă hashurile sunt diferite, putem fi siguri că datele au fost modificate. Cu alte cuvinte, unul sau mai multe fragmente au produs un hash diferit. Deci, orice modificare ușoară a datelor ne va oferi o rădăcină Merkle total diferită.
Din fericire, există o modalitate utilă de a verifica ce fragment este defect. În cazul nostru, să presupunem că este el. Veți începe prin a cere unui egal pentru cele două hashuri care au produs rădăcina Merkle (hABCD și hEFGH). Valoarea ta hABCD ar trebui să se potrivească cu a lor, deoarece nu există nicio greșeală în acel subarbore. Dar hEFGH nu o va face, așa că știi să te înregistrezi acolo. Apoi solicitați hEF și hGH și le comparați cu ale dvs. hGH va arăta bine, așa că știți că hEF este vinovatul nostru. În cele din urmă, comparați hashurile lui hE și hF. Acum știți că el este incorect, așa că puteți descărca din nou acea bucată.
Rezumând totul, un arbore Merkle este creat prin împărțirea datelor în mai multe bucăți, care sunt apoi hashing în mod repetat pentru a forma rădăcina Merkle. Apoi puteți verifica eficient dacă ceva a mers prost cu o bucată de date. După cum vom vedea în secțiunea următoare, există și alte aplicații interesante.
Vrei să începi cu criptomoneda? Cumpărați Bitcoin pe Binance!
De ce sunt folosite rădăcinile Merkle în Bitcoin?
Există o mână de cazuri de utilizare pentru arborii Merkle, dar aici ne vom concentra asupra importanței acestora în blockchains. Arborii Merkle sunt esențiali în Bitcoin și în multe alte criptomonede. Sunt o componentă integrală a fiecărui bloc, unde pot fi găsite în anteturile blocurilor. Pentru a obține frunzele pentru arborele nostru, folosim hash-ul tranzacției (TXID-ul) al fiecărei tranzacții incluse în bloc.
Rădăcina Merkle servește la câteva scopuri în acest caz. Să aruncăm o privire la aplicațiile lor în minarea criptomonedelor și verificarea tranzacțiilor.
Minerit
Un bloc Bitcoin este format din două bucăți. Prima parte este antetul blocului, un segment de dimensiune fixă care conține metadate pentru bloc. A doua parte este o listă de tranzacții a căror dimensiune este variabilă, dar tinde să fie mult mai mare decât antetul.
Minerii trebuie să trimită în mod repetat datele pentru a produce o ieșire care să îndeplinească anumite condiții pentru a extrage un bloc valid. Ei pot face trilioane de încercări înainte de a găsi una. Cu fiecare încercare, ei schimbă un număr aleatoriu în antetul blocului (nonce) pentru a produce o ieșire diferită. Dar o mare parte din bloc rămâne același. Pot exista mii de tranzacții și ar trebui să le faci hash de fiecare dată.
O rădăcină Merkle simplifică procesul considerabil. Când începeți mineritul, aliniați toate tranzacțiile pe care doriți să le includeți și construiți un arbore Merkle. Puneți hash-ul rădăcină rezultat (32 de octeți) în antetul blocului. Apoi, când exploatezi, trebuie doar să faci hash header-ul blocului, în loc de întregul bloc.
Acest lucru funcționează pentru că este inviolabil. Rezumați efectiv toate tranzacțiile blocului într-un format compact. Nu puteți găsi un antet de bloc valid și ulterior modifica lista de tranzacții, deoarece asta ar schimba rădăcina Merkle. Când blocul este trimis către alte noduri, acestea calculează rădăcina din lista de tranzacții. Dacă nu se potrivește cu cel din antet, ei resping blocul.
Verificare
Există o altă proprietate interesantă a rădăcinilor Merkle pe care o putem valorifica. Acesta se referă la clienții light (noduri care nu dețin o copie completă a blockchain-ului). Dacă rulați un nod pe un dispozitiv cu resurse limitate, nu doriți să descărcați și să folosiți hash toate tranzacțiile unui bloc. Ceea ce puteți face în schimb este să solicitați pur și simplu o dovadă Merkle - dovezi furnizate de nodul complet care dovedește că tranzacția dvs. este într-un anumit bloc. Acest lucru este denumit mai frecvent verificarea plăților simplificate sau SPV și a fost detaliat de Satoshi Nakamoto în cartea albă Bitcoin.
Pentru a verifica hD, avem nevoie doar de hashurile afișate în roșu.
Luați în considerare scenariul în care dorim să cunoaștem informații despre tranzacția al cărei TXID este hD. Dacă ne este furnizat hC, putem stabili hCD. Apoi, avem nevoie de hAB pentru a calcula hABCD. În cele din urmă, cu hEFGH, putem verifica dacă rădăcina Merkle rezultată se potrivește cu cea din antetul blocului. Dacă se întâmplă, este o dovadă că tranzacția a fost inclusă în bloc - ar fi aproape imposibil să se creeze același hash cu date diferite.
În exemplul de mai sus, a trebuit să facem hash doar de trei ori. Fără o dovadă Merkle, ar fi trebuit să o facem de șapte ori. Deoarece blocurile conțin în zilele noastre mii de tranzacții, folosirea probelor Merkle ne economisește mult timp și resurse de calcul.
Gânduri de închidere
Arborii Merkle s-au dovedit extrem de utili într-o serie de aplicații informatice – după cum am văzut, sunt incredibil de valoroși în blockchain-uri. În sistemele distribuite, arborii Merkle permit verificarea ușoară a informațiilor fără a inunda rețeaua cu date inutile.
Fără arborii Merkle (și rădăcinile Merkle), blocurile Bitcoin și ale altor criptomonede nu ar fi nici pe departe la fel de compacte precum sunt astăzi. Și în timp ce clienții ușoare lipsesc în ceea ce privește confidențialitatea și securitatea, dovezile Merkle le permit utilizatorilor să verifice dacă tranzacțiile lor au fost incluse într-un bloc cu cheltuieli minime.
