Los Merkle Trees son un componente fundamental de las cadenas de bloques que sustentan su funcionalidad. Permiten una verificación eficiente y segura de grandes estructuras de datos y, en el caso de las cadenas de bloques, conjuntos de datos potencialmente ilimitados.
La implementación de árboles Merkle en blockchains tiene múltiples efectos. Les permite escalar y al mismo tiempo les proporciona la arquitectura basada en hash para mantener la integridad de los datos y una forma trivial de verificar la integridad de los datos.
Las funciones hash criptográficas son la tecnología subyacente que permite que los árboles Merkle funcionen, por lo que primero es importante comprender qué son las funciones hash criptográficas.
Veredicto rápido: Los árboles Merkle son estructuras de datos compuestas de hashes criptográficos que permiten una verificación eficiente de la integridad y el mapeo de grandes conjuntos de datos, lo que los convierte en un componente integral de sistemas como blockchains y control de versiones distribuidas.
Datos generales
| Lista de verificación | Descripción |
|---|---|
| Funciones hash criptográficas | Funciones hash que toman una entrada de cualquier tamaño y generan un valor hash de longitud fija. Utilizado en árboles Merkle. |
| estructura de árbol merkle | Estructura de datos de árbol donde cada nodo que no es hoja es un hash de sus nodos secundarios. Permite mapear y verificar eficientemente grandes conjuntos de datos. |
| Hachís de raíz | Hash en la parte superior del árbol Merkle que representa el hash de todo el árbol. Actúa como huella digital para todo el conjunto de datos. |
| pruebas de merkle | Permita la verificación de la integridad de los datos y su posición en el árbol sin necesidad del conjunto de datos completo, solo el hash raíz. |
| Implementación en Bitcoin | Los árboles Merkle almacenan transacciones en bloques. El hash raíz almacenado en el encabezado del bloque permite a los nodos SPV verificar las transacciones. |
| Otras implementaciones de blockchain | Se utiliza en muchas cadenas de bloques como Ethereum, que utiliza Merkle Patricia Trees más complejos. |
| Sistemas distribuidos | Permita que los sistemas de control de versiones como Git e IPFS verifiquen fácilmente los datos compartidos entre pares. |
Funciones criptográficas de hash
En pocas palabras, una función hash es cualquier función que se utiliza para asignar datos de un tamaño arbitrario (entrada) a una salida de tamaño fijo. Se aplica un algoritmo hash a la entrada de datos y la salida de longitud fija resultante se denomina hash.
Muchos algoritmos hash están ampliamente disponibles públicamente y pueden seleccionarse según sus necesidades.
El hash resultante de la entrada arbitraria no solo tiene una longitud fija, sino que también es completamente exclusivo de la entrada y la función en sí es determinista. Es decir, no importa cuántas veces ejecutes la función en la misma entrada, la salida siempre será la misma.
Por ejemplo, si tiene los siguientes conjuntos de datos a continuación como entrada, las salidas resultantes son únicas para cada entrada. Observe cómo en el segundo y tercer ejemplo, aunque la diferencia de las entradas es solo una palabra, las salidas resultantes son completamente diferentes.
Esto es muy importante ya que permite tomar "huellas dactilares" de los datos.
Una función hash criptográfica, imagen de Wikipedia
Dado que la longitud de salida (suma hash en el ejemplo) es siempre la misma que la determinada por el algoritmo hash utilizado, se pueden identificar grandes cantidades de datos únicamente a través de su hash resultante.
Con sistemas que contienen cantidades masivas de datos, los beneficios de poder almacenar e identificar datos con una salida de longitud fija pueden generar grandes ahorros de almacenamiento y ayudar a aumentar la eficiencia.
Dentro de las cadenas de bloques, se utilizan algoritmos hash para determinar el estado de la cadena de bloques.
Las blockchains son listas enlazadas que contienen datos y un puntero hash que apunta al bloque anterior, creando una cadena de bloques conectados, de ahí el nombre “blockchain”.
Cada bloque está conectado entre sí a través de un puntero hash, que es el hash de los datos dentro del bloque anterior junto con la dirección del bloque anterior. Al vincular bloques de datos en este formato, cada hash resultante del bloque anterior representa el estado completo de la cadena de bloques, ya que todos los datos hash de los bloques anteriores se convierten en un solo hash.
Esto se representa (en el caso del algoritmo SHA-256) mediante una salida (hash) como esta:
b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7
El hash de arriba es la huella digital de todo el estado de la cadena de bloques anterior. El estado de la cadena de bloques antes del nuevo bloque (como datos hash) es la entrada y el hash resultante es la salida.
Aunque es posible utilizar hashes criptográficos sin árboles Merkle, es extremadamente ineficiente y no escalable. El uso de hashes para almacenar datos en un bloque en formato de serie requiere mucho tiempo y es engorroso.
Como verá, los árboles de Merkle permiten una resolución trivial de la integridad de los datos, así como el mapeo de esos datos a través de todo el árbol utilizando pruebas de Merkle.
Árboles Merkle y pruebas Merkle
Los árboles de Merkle, que llevan el nombre de Ralph Merkle, quien patentó el concepto en 1979, son fundamentalmente árboles de estructura de datos donde cada nodo que no es hoja es un hash de sus respectivos nodos secundarios.
Los nodos de hoja son el nivel más bajo de nodos del árbol. Al principio, puede parecer difícil de comprender, pero si observa la figura más utilizada a continuación, será mucho más fácil de entender.
Un ejemplo de árbol hash binario, Imagen de Wikipedia
Es importante destacar que los nodos que no son hoja o “ramas” (representados por Hash 0-0 y Hash 0-1) en el lado izquierdo son hashes de sus respectivos hijos L1 y L2. Además, observe cómo la rama Hash 0 es el hash de sus hijos concatenados, las ramas Hash 0-0 y Hash 0-1.
El ejemplo anterior es la forma más común y simple de un árbol Merkle conocido como árbol binario Merkle. Como puedes ver, hay un hash superior que es el hash de todo el árbol, conocido como hash raíz. Esencialmente, los árboles Merkle son una estructura de datos que puede tomar "n" número de hashes y representarlos con un solo hash.
La estructura del árbol permite un mapeo eficiente de cantidades arbitrariamente grandes de datos y permite una fácil identificación de dónde ocurren los cambios en esos datos. Este concepto permite pruebas de Merkle, con las cuales alguien puede verificar que el hash de datos es consistente en todo el árbol y está en la posición correcta sin tener que mirar todo el conjunto de hashes.
En cambio, pueden verificar que un fragmento de datos sea consistente con el hash raíz verificando solo un pequeño subconjunto de los hashes en lugar de todo el conjunto de datos.
Siempre que el hash raíz sea públicamente conocido y confiable, es posible que cualquiera que desee realizar una búsqueda de valores clave en una base de datos utilice una prueba de Merkle para verificar la posición y la integridad de un dato dentro de una base de datos que tiene una raíz determinada.
Cuando el hash raíz está disponible, el árbol hash se puede recibir de cualquier fuente que no sea confiable y se puede descargar una rama del árbol a la vez con verificación inmediata de la integridad de los datos, incluso si el árbol completo aún no está disponible.
Uno de los beneficios más importantes de la estructura de árbol de Merkle es la capacidad de autenticar conjuntos de datos arbitrariamente grandes a través de un mecanismo hash similar que se utiliza para verificar cantidades de datos mucho más pequeñas.
El árbol es ventajoso para distribuir grandes conjuntos de datos en partes más pequeñas manejables donde la barrera para la verificación de la integridad se reduce sustancialmente a pesar del mayor tamaño general de los datos.
El hash raíz se puede utilizar como huella digital para un conjunto de datos completo, incluida una base de datos completa o que representa el estado completo de una cadena de bloques. En las siguientes secciones, discutiremos cómo Bitcoin y otros sistemas implementan árboles Merkle.
Árboles Merkle en Bitcoin
La función hash criptográfica empleada por Bitcoin es el algoritmo SHA-256. Esto significa "Algoritmo de hash seguro", cuya salida tiene una longitud fija de 256 bits. La función básica de los árboles Merkle en Bitcoin es almacenar y, eventualmente, podar las transacciones en cada bloque.
Como se mencionó anteriormente, los bloques en una cadena de bloques están conectados mediante hashes del bloque anterior. En Bitcoin, cada bloque contiene todas las transacciones dentro de ese bloque, así como el encabezado del bloque que consta de:
- Número de versión del bloque
- Hash de bloque anterior
- Timestamp
- Objetivo de dificultad minera
- nuncio apostólico
- Hash de raíz de Merkle
La siguiente imagen es del documento técnico de Bitcoin e ilustra cómo encaja el árbol Merkle en cada bloque.
Los mineros incluyen las transacciones en bloques y se procesan como parte de un árbol Merkle, lo que conduce a la raíz de Merkle que se almacena en el encabezado del bloque. Este diseño tiene una serie de beneficios distintos.
En particular, como se describe en el documento técnico, esto permite la existencia de nodos de Verificación de Pago Simple (SPV), también conocidos como "clientes ligeros". Estos nodos no tienen que descargar toda la cadena de bloques de Bitcoin, solo los encabezados de bloque de la cadena más larga.
Los nodos SPV pueden lograr esto consultando a sus nodos pares hasta que estén convencidos de que los encabezados de bloque almacenados en los que están operando son parte de la cadena más larga. Luego, un nodo SPV puede determinar el estado de una transacción utilizando la prueba Merkle para asignar la transacción a un árbol Merkle específico con el hash raíz de ese árbol Merkle respectivo en un encabezado de bloque que forma parte de la cadena más larga.
Además, la implementación de árboles Merkle en Bitcoin permite podar la cadena de bloques para ahorrar espacio. Esto es el resultado de que solo se almacena el hash raíz en el encabezado del bloque; por lo tanto, los bloques antiguos se pueden podar eliminando ramas innecesarias del árbol Merkle y preservando solo las necesarias para la prueba de Merkle.
Implementación de árboles Merkle en otras cadenas de bloques y sistemas
Aunque Bitcoin fue la primera cadena de bloques en implementar árboles Merkle, muchas otras cadenas de bloques implementan estructuras de árboles Merkle similares o incluso versiones más complejas.
Además, la implementación del árbol Merkle no solo se limita a blockchains sino que se aplica a una variedad de otros sistemas.
Ethereum, al ser la otra criptomoneda más reconocible, también es un gran ejemplo de una implementación diferente del árbol Merkle. Debido a que Ethereum es una plataforma completa para crear aplicaciones mucho más complejas, utiliza una versión más compleja del árbol Merkle llamada árbol Merkle Patricia que en realidad consta de 3 árboles Merkle separados que se utilizan para tres tipos de objetos. Puedes aprender más sobre estos árboles aquí.
Finalmente, los árboles Merkle son un componente importante de los sistemas de control de versiones distribuidos como Git e IPFS. Su capacidad para garantizar y verificar fácilmente la integridad de los datos compartidos entre computadoras en formato P2P los hace invaluables para estos sistemas.
Conclusión
Los árboles Merkle son un componente integral de las cadenas de bloques y les permiten funcionar de manera efectiva con inmutabilidad e integridad de transacciones demostrables.
Comprender el papel que desempeñan en las redes distribuidas y su tecnología subyacente de funciones hash criptográficas es crucial para comprender los conceptos básicos dentro de las criptomonedas a medida que continúan desarrollándose hacia sistemas más grandes y complejos.
Fuente: https://blockonomi.com/merkle-tree/