Arbre Merkle

Els arbres de Merkle són un component fonamental de les cadenes de blocs que fonamenten la seva funcionalitat. Permeten una verificació eficient i segura d’estructures de dades grans i, en el cas de cadenes de blocs, conjunts de dades potencialment il·limitats.

La implementació dels arbres de Merkle a les cadenes de blocs té múltiples efectes. Els permet escalar alhora que proporciona l’arquitectura basada en hash perquè mantinguin la integritat de les dades i una forma trivial de verificar la integritat de les dades.

Les funcions de hash criptogràfic són la tecnologia subjacent que permet treballar els arbres de Merkle, per tant, primer és important entendre quines són les funcions de hash criptogràfic.

Funcions Hash criptogràfiques

En poques paraules, una funció hash és qualsevol funció que s’utilitza per assignar dades d’una mida arbitrària (entrada) a una sortida de mida fixa. S’aplica un algoritme de hash a l’entrada de dades i la sortida de longitud fixa resultant es coneix com a hash.

Molts algoritmes de hash estan disponibles públicament i es poden seleccionar en funció de les vostres necessitats.

El hash resultant de l’entrada arbitrària no només es fixa en longitud, sinó que també és completament exclusiu de l’entrada i la funció en si és determinista. És a dir, no importa quantes vegades executeu la funció a la mateixa entrada, la sortida sempre serà la mateixa.

Per exemple, si teniu els següents conjunts de dades a continuació com a entrada, les sortides resultants són úniques per a cada entrada. Fixeu-vos com en el segon i tercer exemples, tot i que la diferència de les entrades és només una paraula, les sortides resultants són completament diferents.

Això és molt important, ja que permet “empremtes digitals” de dades.

Una funció hash criptogràfica, Imatge de Viquipèdia

Com que la longitud de sortida (suma de hash a l’exemple) sempre és la mateixa que determina l’algoritme de hash utilitzat, es poden identificar grans quantitats de dades únicament a través del seu hash resultant.

Amb els sistemes que contenen grans quantitats de dades, els avantatges de poder emmagatzemar i identificar dades amb una sortida de longitud fixa poden generar grans estalvis d’emmagatzematge i ajudar a augmentar l’eficiència.

Dins de les cadenes de blocs, s’utilitzen algoritmes de resum per determinar l’estat de la cadena de blocs.

Les cadenes de blocs són llistes enllaçades que contenen dades i un punter de hash que apunta al bloc anterior, creant una cadena de blocs connectats, d’aquí el nom de “cadena de blocs”.

Cada bloc està connectat entre si mitjançant un punter de hash, que és el hash de les dades dins del bloc anterior juntament amb l’adreça del bloc anterior. En enllaçar blocs de dades en aquest format, cada hash resultant del bloc anterior representa l’estat complet de la cadena de blocs, ja que totes les dades hash dels blocs anteriors es comparteixen en un hash..

Això està representat (en el cas de l’algorisme SHA-256) per una sortida (hash) com aquesta.

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

El hash anterior és l’empremta digital de tot l’estat de la cadena de blocs anterior. L’entrada de l’estat de la cadena de blocs anterior al nou bloc (com a dades resumides) i la sortida resultant és la sortida.

Tot i que és possible utilitzar hash criptogràfics sense arbres de Merkle, és extremadament ineficient i no és escalable. Utilitzar hash per emmagatzemar dades en un bloc en un format de sèrie requereix molt de temps i és feixuc.

Com veureu, els arbres de Merkle permeten la resolució trivial de la integritat de les dades, així com el mapatge d’aquestes dades a tot l’arbre mitjançant proves de Merkle..

Arbres Merkle i proves Merkle

Amb el nom de Ralph Merkle, que va patentar el concepte el 1979, els arbres de Merkle són fonamentalment arbres d’estructures de dades on cada node que no és de fulla és un hash dels seus respectius nodes fills..

Els nodes de fulla són el nivell més baix de nodes de l’arbre. Al principi, pot semblar difícil de comprendre, però si observeu la figura més utilitzada a continuació, serà molt més fàcil d’entendre.

Arbre Hash

Un exemple d’un arbre de hash binari, Image from Viquipèdia

És important tenir en compte que els nodes o fulles que no són fulles (representades per Hash 0-0 i Hash 0-1) al costat esquerre, són hash dels seus fills respectius L1 i L2. A més, observeu com la branca Hash 0 és el hash dels seus fills concatenats, les branques Hash 0-0 i Hash 0-1.

L’exemple anterior és la forma més comuna i senzilla d’un arbre de Merkle conegut com a arbre de Merkle binari. Com podeu veure, hi ha un hash superior que és el hash de tot l’arbre, conegut com a hash d’arrel. Essencialment, els arbres de Merkle són una estructura de dades que pot agafar “n” nombre de hash i representar-lo amb un sol hash.

L’estructura de l’arbre permet un mapatge eficient de quantitats de dades arbitràriament grans i permet identificar fàcilment on es produeixen els canvis en aquestes dades. Aquest concepte permet proves de Merkle, amb les quals algú pot verificar que el resum de dades és coherent fins a l’arbre i en la posició correcta sense haver de mirar realment tot el conjunt de hash..

En lloc d’això, poden verificar que un fragment de dades sigui coherent amb el hash arrel només comprovant un petit subconjunt de hash en lloc de tot el conjunt de dades.

Mentre el hash arrel sigui conegut i confiat públicament, és possible que qualsevol persona que vulgui fer una cerca de valor clau en una base de dades utilitzi una prova de Merkle per verificar la posició i la integritat d’una peça de dades dins d’una base de dades que tingui una arrel particular.

Quan hi ha disponible el hash arrel, es pot rebre l’arbre de hash des de qualsevol font no fiable i es pot descarregar una branca de l’arbre alhora amb verificació immediata de la integritat de les dades, fins i tot si tot l’arbre encara no està disponible.

Un dels avantatges més importants de l’estructura de l’arbre de Merkle és la capacitat d’autenticar conjunts de dades arbitràriament grans mitjançant un mecanisme de resum similar que s’utilitza per verificar quantitats de dades molt més petites..

L’arbre és avantatjós per distribuir grans conjunts de dades en parts més petites manejables on la barrera per a la verificació de la integritat es redueix substancialment malgrat la mida de dades generalment més gran.

El hash arrel es pot utilitzar com a empremta digital per a un conjunt de dades sencer, inclosa tota una base de dades o que representa tot l’estat d’una cadena de blocs. A les seccions següents, parlarem de com Bitcoin i altres sistemes implementen els arbres de Merkle.

Arbres Merkle a Bitcoin

La funció de criptografia hash emprada per Bitcoin és l’algorisme SHA-256. Això significa “Algoritme de protecció segura”, la sortida del qual té una longitud fixa de 256 bits. La funció bàsica dels arbres de Merkle a Bitcoin és emmagatzemar i, finalment, podar transaccions a tots els blocs.

Com s’ha esmentat anteriorment, els blocs d’una cadena de blocs es connecten mitjançant hash del bloc anterior. A Bitcoin, cada bloc conté totes les transaccions dins d’aquest bloc, així com la capçalera del bloc que consisteix en:

  • Bloqueja el número de versió
  • Anterior Block Hash
  • Marca de temps
  • Objectiu de dificultat minera
  • Nonce
  • Merkle Root Hash

La imatge següent és del Bitcoin paper blanc i il·lustra com l’arbre de Merkle s’adapta a cada bloc.

Arbre Merkle

Les transaccions s’inclouen en blocs pels miners i es comparteixen com a part d’un arbre de Merkle, que condueix a l’arrel de Merkle que s’emmagatzema a la capçalera del bloc. Aquest disseny té diversos avantatges.

El més destacat, tal com es recull al llibre blanc, permet l’existència de nodes de verificació de pagaments senzills (SPV), també coneguts com a “clients lleugers”. Aquests nodes no han de descarregar tota la cadena de blocs de Bitcoin, només les capçaleres de blocs de la cadena més llarga.

Els nodes SPV ho poden aconseguir consultant els seus nodes parells fins que estiguin convençuts que les capçaleres de bloc emmagatzemades en què operen formen part de la cadena més llarga. Un node SPV pot determinar l’estat d’una transacció mitjançant la prova de Merkle per assignar la transacció a un arbre de Merkle específic amb el hash de l’arrel de l’arbre de Merkle respectiu en una capçalera de bloc que forma part de la cadena més llarga..

A més, la implementació d’arbres Merkle de Bitcoin permet la poda de la cadena de blocs per tal d’estalviar espai. Això és el resultat de que només s’emmagatzema el hash de l’arrel a la capçalera del bloc, per tant, es poden podar blocs antics eliminant branques innecessàries de l’arbre de Merkle tot conservant les necessàries per a la prova de Merkle.

Implementació d’arbres de Merkle en altres sistemes i cadenes de blocs

Tot i que Bitcoin va ser la primera cadena de blocs a implementar arbres de Merkle, moltes altres cadenes de blocs implementen estructures d’arbres de Merkle similars o fins i tot versions més complexes.

A més, la implementació de l’arbre de Merkle no només es limita a cadenes de blocs i s’aplica a una gran varietat d’altres sistemes.

Ethereum, sent l’altra criptomoneda més reconeguda, també és un gran exemple d’una implementació diferent de l’arbre de Merkle. Com que Ethereum és completament complet com a plataforma per construir aplicacions molt més complexes, utilitza una versió més complexa de l’arbre de Merkle anomenada Merkle Patricia Tree que en realitat són 3 arbres de Merkle separats que s’utilitzen per a tres tipus d’objectes. Podeu obtenir més informació sobre aquests arbres aquí.

Finalment, els arbres de Merkle són un component important dels sistemes de control de versions distribuïdes com Git i IPFS. La seva capacitat per assegurar i verificar fàcilment la integritat de les dades compartides entre ordinadors en format P2P els fa inestimables per a aquests sistemes.

Conclusió

Els arbres de Merkle són un component integral de les cadenes de blocs i els permeten eficaçment funcionar amb una immutabilitat i integritat de les transaccions demostrables.

Comprendre el paper que juguen a les xarxes distribuïdes i la seva tecnologia subjacent de funcions de hash criptogràfic és crucial per copsar els conceptes bàsics de les criptomonedes, ja que continuen desenvolupant-se en sistemes més grans i complexos..

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me