Herramientas criptográficas 101: funciones hash y árboles de Merkle

¿De qué trata este artículo?

Las blockchains permiten que las personas lleguen a acuerdos sin intermediarios. En lugar de depender de la confianza, dependen de pruebas criptográficas. Para generar estas pruebas se utilizan primitivas criptográficas. Pero ¿qué son?

En este artículo analizamos dos primitivas criptográficas esenciales para las pruebas criptográficas en las blockchains: las funciones hash y los árboles de Merkle. Exploraremos los mecanismos principales de las funciones hash, veremos por qué son importantes para las blockchains y aprenderemos sobre los punteros hash. Después examinaremos los árboles de Merkle tradicionales y concurrentes, y explicaremos su importancia para Solana.

¿Qué es una primitiva criptográfica?

Una primitiva criptográfica es una operación o un algoritmo fundamental para crear protocolos y sistemas criptográficos. Las primitivas son para los protocolos criptográficos lo que los átomos son para las moléculas: los componentes básicos de soluciones más complejas. Los generadores de números aleatorios, los esquemas de compromiso y la criptografía de clave pública son ejemplos de primitivas criptográficas.

Por sí solas, las primitivas criptográficas son bastante limitadas. Cuando se combinan, proporcionan funciones básicas de seguridad como autenticación, confidencialidad e integridad. Combinar primitivas criptográficas es un proceso lleno de matices que exige una planificación cuidadosa y un conocimiento profundo de cómo interactúan entre sí. Durante este proceso, debes considerar los aspectos de seguridad según los objetivos que quieras alcanzar. Los métodos para combinar primitivas criptográficas pueden clasificarse, en términos generales, así:

• Composición secuencial: aplicar una primitiva después de otra (por ejemplo, encadenamiento de hashes)
• Composición paralela: usar primitivas de forma simultánea e independiente (por ejemplo, cifrar y aplicar hashing a los datos al mismo tiempo)
• Composición jerárquica: usar una primitiva criptográfica dentro de otra (por ejemplo, árboles de Merkle)

Entender qué es una primitiva criptográfica, cómo funciona y qué sutilezas implica combinarlas te ayuda a comprender y diseñar sistemas seguros y eficientes. Una de las primitivas criptográficas más utilizadas y combinadas es la función hash.

¿Qué es una función hash?

Una función hash es una función criptográfica que recibe datos de cualquier tamaño y devuelve un valor de tamaño fijo. El valor que devuelve se conoce como resumen o hash. Algunos algoritmos de hashing populares son SHA-1, SHA-2, SHA-3, MD5 y Argon2. Las funciones hash se utilizan en todas las blockchains, por lo que es fundamental entender qué son y cómo funcionan.

Una analogía sencilla

Imagina que horneas un extravagante pastel de chocolate. Tiene varias capas, cada una preparada con sus propios ingredientes. Mientras lo horneas, un amigo te envía un mensaje para preguntarte qué haces. Darle una explicación detallada de cómo preparaste el pastel y de todos los ingredientes que utilizaste sería bastante tedioso. En su lugar, decides enviarle una foto del pastel de chocolate.

En este caso, la foto del pastel funciona como un hash: es una representación sencilla y compacta de algo mucho más complejo. Tu amigo no sabrá hasta el último ingrediente que utilizaste, pero tendrá una buena idea de lo que acabas de hornear. Supongamos que tu pastel de chocolate tenía frambuesas encima. Si las quitaras o las cambiaras por fresas, la foto sería completamente distinta del producto final. De forma similar, cualquier cambio en los datos procesados generaría un nuevo valor hash.

Propiedades de una buena función hash criptográfica

Hay que admitir que la definición anterior de una función hash es engañosa. Una función hash podría devolver un hash de tamaño variable. También podría devolver el mismo hash para dos entradas diferentes. Incluso podría ser muy fácil aplicar ingeniería inversa al hash y encontrar la entrada original. La definición anterior correspondía a una buena función hash criptográfica. Pero ¿qué hace que una función hash criptográfica sea buena?

Una buena función hash es determinista: la misma entrada siempre genera la misma salida. Si aplico hashing a la entrada “baseball”, esa función producirá siempre el mismo hash, sin importar el sistema. Esto también significa, en parte, que el hash tendrá el mismo tamaño sin importar el tamaño de la entrada. Esto es importante para la eficiencia del procesamiento y el almacenamiento de datos. Saber que una entrada única siempre generará una salida única y que estas salidas siempre tendrán un tamaño fijo es un claro indicador de una buena función hash criptográfica.

Una buena función hash es resistente a la preimagen. Esto significa que resulta inviable, desde el punto de vista computacional, aplicar ingeniería inversa para obtener el valor de entrada a partir de su hash. Por lo tanto, si alguien te da un hash, no deberías poder averiguar qué datos lo generan. Esto también se relaciona con la idea de que dos conjuntos distintos de datos no deben producir el mismo hash. Se dice que una buena función hash es resistente a colisiones cuando dos entradas cualesquiera nunca producen el mismo hash.

Una buena función hash cumple el efecto avalancha: un pequeño cambio en la entrada debe producir un hash radicalmente diferente. Cambiar incluso un solo carácter debe generar un hash completamente distinto. Por lo tanto, la salida hash no debe revelar información sobre la entrada ni presentar patrones reconocibles. Observa la diferencia entre los hashes de la figura anterior. El zorro rojo que “corre” genera un hash muy diferente al del zorro rojo que “camina”. Tampoco hay indicios de que estos dos hashes contengan información casi idéntica.

Una buena función hash debe ser rápida de calcular. Las funciones hash lentas no son prácticas para cálculos en tiempo real o casi en tiempo real, como la verificación de transacciones. Una función hash lenta podría convertirse en un cuello de botella grave y limitar tanto el rendimiento como el desempeño de la red. Una función hash rápida es necesaria para que la blockchain funcione de forma eficiente y segura.

¿Por qué es importante para las blockchains?

Una blockchain es un libro mayor descentralizado y distribuido que registra transacciones en toda su red. Estas transacciones se agrupan en bloques, vinculados de forma segura mediante una función hash buena. Cada bloque contiene datos de transacciones, una marca de tiempo y el hash del bloque anterior. Como el hash de cada bloque depende del hash del bloque anterior, cualquier cambio en el contenido de un bloque modificaría su hash e invalidaría todos los bloques posteriores. Este proceso de usar hashes anteriores para generar uno nuevo se conoce como encadenamiento de hashes.

Agregar un nuevo bloque a una blockchain se conoce como confirmación. Una confirmación verifica y protege todas las transacciones del nuevo bloque y de todos los bloques anteriores. Esto se debe a que cada nueva confirmación dificulta más la modificación de los bloques anteriores. Para modificar un bloque anterior, un atacante tendría que volver a calcular todos los hashes posteriores. Por lo tanto, el encadenamiento de hashes garantiza que modificar la blockchain sea inviable una vez que un bloque acumula una cantidad considerable de confirmaciones.

En pocas palabras, una blockchain es una cadena de bloques protegida mediante funciones hash. Pero ¿cómo apuntamos exactamente de un bloque a otro? Sí, se utiliza una función hash criptográfica para encadenar los bloques, pero ¿cómo podemos consultar los datos de bloques anteriores? Se supone que una función hash criptográfica buena es resistente a la preimagen.

¿Qué es un puntero hash?

Un puntero es una variable que contiene la ubicación donde se almacenan determinados datos en la memoria. Es fácil acceder a los datos de esta dirección de memoria porque el puntero “apunta” a su ubicación. Un puntero hash es una estructura de datos similar a un puntero, pero también contiene un hash criptográfico de los datos referenciados. Por lo tanto, un puntero hash te indica dónde acceder a un dato específico y te permite comprobar la integridad de los datos consultados.

La estructura de una blockchain puede describirse con mayor precisión como una lista enlazada que utiliza punteros hash. El hash del bloque anterior es un puntero hash que apunta a un conjunto de transacciones y a un hash de todas ellas. Los punteros hash permiten vincular bloques, preservar la integridad de cada bloque y verificar que los bloques recién agregados sigan correctamente a los anteriores.

Los punteros hash se utilizan para encadenar bloques de forma eficiente. Pero ¿qué ocurre con las transacciones del bloque? Si un bloque contuviera mil transacciones, ¿no sería costoso verificarlas una por una?

¿Qué es un árbol de Merkle?

Un árbol de Merkle es una estructura de datos que se utiliza para organizar y verificar grandes conjuntos de datos. Los datos se organizan en una estructura de árbol donde cada hoja o nodo se etiqueta con el hash de un conjunto de datos. Cada nodo que no es una hoja contiene el hash de sus nodos hijos. Los árboles de Merkle se utilizan para verificar las transacciones incluidas en bloques específicos que se propagan a la blockchain. Entonces, ¿cómo funcionan?

Las transacciones se agrupan en una lista para formar un bloque. A cada transacción de la lista se le aplica hashing mediante una función hash buena. Estos hashes funcionan como nodos hoja. Los nodos hoja se agrupan en pares y se les aplica hashing para crear una nueva capa de hashes. Este proceso continúa de forma iterativa hasta que solo queda un hash, conocido como raíz de Merkle. La raíz de Merkle se almacena en el encabezado del bloque y funciona como una huella digital de todas las transacciones incluidas en él. También podemos referirnos a la raíz de Merkle como el hash del bloque. Por eso, cuando decimos que un bloque nuevo se vincula con uno anterior mediante el blockhash del bloque anterior, queremos decir que el nuevo bloque utiliza la raíz de Merkle del bloque anterior como parte de su hash.

Los árboles de Merkle permiten verificar con eficiencia transacciones individuales dentro de un bloque. Tradicionalmente, tendrías que verificar cada transacción para validar una específica, lo que resulta costoso y lleva mucho tiempo. Los árboles de Merkle proporcionan un “atajo” criptográfico para facilitar este proceso, conocido como prueba de Merkle. Una prueba de Merkle es una ruta que va desde el nodo hoja de la transacción hasta la raíz de Merkle. En la figura anterior, puedes imaginarla como una ruta desde Datos A hasta la raíz de Merkle. Esta ruta también incluye sus nodos hermanos: las hojas adyacentes a cada nodo de la ruta que no forman parte de ella. Un verificador puede calcular un hash mediante la ruta de prueba y comprobar si coincide con la raíz de Merkle. Si el hash resultante coincide, el verificador puede confiar en que la transacción es legítima y no ha sido manipulada.

Una hoja puede modificarse aplicando hashing a sus nuevos datos y volviendo a calcular la raíz de Merkle. Esta nueva raíz se utiliza para verificar los cambios e invalida la prueba anterior. En una red de alto rendimiento como Solana, los validadores pueden recibir solicitudes de cambio para árboles de Merkle on-chain en rápida sucesión (por ejemplo, dentro del mismo slot). Cada cambio de datos tendría que volver a calcularse de forma secuencial. De lo contrario, cada solicitud posterior quedaría invalidada por la solicitud anterior realizada dentro del slot. Modificar los datos de una hoja y calcular una nueva raíz de Merkle es muy común en las blockchains. Entonces, ¿cómo gestionamos los cambios rápidos?

¿Qué es un árbol de Merkle concurrente?

Un árbol de Merkle concurrente es un árbol de Merkle optimizado para lecturas y escrituras simultáneas. Almacena un registro seguro de los cambios más recientes, su hash raíz y la prueba necesaria para derivarlo. Este registro de cambios se almacena on-chain en una cuenta específica del árbol e incluye una cantidad máxima de cambios que pueden realizarse mientras la raíz de Merkle siga siendo válida. Esta cantidad máxima se conoce como maxBufferSize. Por lo tanto, cuando un validador recibe solicitudes de cambio para un árbol de Merkle on-chain en rápida sucesión, puede usar este registro como fuente de verdad y permitir hasta maxBufferSize cambios en el árbol dentro del mismo slot.

Los árboles de Merkle concurrentes mejoran los árboles tradicionales y los vuelven adecuados para entornos de alto rendimiento como Solana. Para crear un árbol de Merkle concurrente on-chain en Solana, hay tres propiedades que afectan el tamaño y el costo de creación del árbol, además de la cantidad de cambios concurrentes que admite:

• Profundidad máxima
• Tamaño máximo del búfer
• Profundidad del dosel

La profundidad máxima se refiere al número máximo de saltos necesarios para ir desde cualquier hoja hasta la raíz de Merkle. maxDepth se utiliza para determinar la cantidad máxima de nodos que se almacenarán en el árbol. Se puede calcular con la fórmula: numberOfNodes = 2 ^ maxDepth. La profundidad de un árbol debe establecerse al crearlo. Por eso, es importante usar esta fórmula para determinar cuántos datos quieres almacenar en él.

Como se explicó antes, el tamaño máximo del búfer se refiere a la cantidad máxima de cambios que pueden realizarse en un árbol mientras su raíz de Merkle sigue siendo válida.

La profundidad del dosel se refiere a un subconjunto del árbol de Merkle que se almacena on-chain. Estas pruebas almacenadas en caché se utilizan para comparar un hash con la raíz de Merkle on-chain. Debes usar la ruta de prueba completa para verificar la propiedad original de una hoja cuando escribas en ella. Por ejemplo, escribirías en el árbol al transferir un NFT. El dosel te permite reducir el tamaño de la prueba y evita que tengas que usar un tamaño de prueba de maxDepth para verificar el árbol. Un árbol con un maxDepth de 20 requeriría una prueba de tamaño 20. Con un dosel de 15, solo es necesario enviar una prueba de tamaño 5 por cada transacción de escritura. Por lo tanto, una mayor profundidad del dosel implica pagar un costo inicial más alto para poder enviar pruebas más pequeñas después.

La profundidad del dosel es uno de los principales factores que determinan el costo de crear un árbol. Esto se debe a que una mayor profundidad exige una cuenta más grande. Los desarrolladores pueden usar el paquete @solana/spl-account-compression para calcular el espacio necesario según el tamaño del árbol y el costo de asignar ese espacio on-chain. Pueden usar la función getConcurrentMerkleTreeAccountSize para calcular el espacio que necesita una cuenta según sus parámetros y utilizar getMinimumBalanceForRentExemption con el espacio requerido para obtener el costo final en Lamports.

Solana utiliza árboles de Merkle concurrentes para comprimir el estado. La compresión de estado consiste en crear un hash de datos off-chain y almacenarlo on-chain para verificarlos de forma segura. El caso de uso más popular es el de los NFT comprimidos, porque reduce drásticamente el costo de acuñación. Por ejemplo, acuñar mil millones de NFT en Solana costaría 507 $SOL, frente a 12 000 000 $SOL con NFT “normales”. Ahora que entiendes bien el hashing y los árboles de Merkle, exploraremos los NFT comprimidos en un próximo artículo.

Conclusión

¡Felicitaciones! En este artículo analizamos las funciones hash y los árboles de Merkle, dos primitivas criptográficas esenciales para las blockchains. Entender las blockchains no es una tarea sencilla: son sistemas distribuidos complejos que exigen amplios conocimientos técnicos. A menudo, se asume que el desarrollador, usuario o inversionista promedio ya posee estos conocimientos. Este artículo no presupone conocimientos de primitivas criptográficas. Comenzamos con los conceptos básicos y después avanzamos hacia temas más complejos, como los árboles de Merkle tradicionales y concurrentes. Es fundamental contar con estas bases antes de explorar temas más complejos, como los NFT comprimidos. Con estos nuevos conocimientos, estás mejor preparado para navegar bases de código o participar en conversaciones sobre primitivas criptográficas y soluciones criptográficas más complejas.

Si llegaste hasta aquí, anon, ¡gracias!

Recursos adicionales y lecturas recomendadas

• Capítulo detallado de un libro sobre primitivas criptográficas
• Artículo que compara algoritmos seguros de hashing
• Algoritmos de hashing y seguridad: video de Computerphile en YouTube
• Video breve de YouTube sobre árboles de Merkle
• Análisis de la compresión de NFT en Solana