# Árboles de Merkle
Un árbol de Merkle es una estructura de datos que se puede utilizar para verificar la integridad de un conjunto de datos. Esta compuesto por nodos que son llamados hojas, los cuales son el hash de la concatenación de hojas anteriores del árbol o el hash directo de bloques de datos. Veamos un ejemplo para ilustrar mejor la idea en que consiste y luego lo definamos de una manera más rigurosa.

Si tenemos el vector $\vec V =(a,b,c,d)$ su árbol correspondiente dada la función de hash $H$ sería:


Es decir como primer paso se calcula el hash de cada elemento del vector $\vec V$. Definimos $H_i=H(i)$ donde $i \in \{a,b,c,d\}$, Luego en la siguiente fila del arbol se calcula el hash de concatenar dos hojas contiguas, es decir $H_{ab}=H(H_a||H_b)$ y $H_{cd}=H(H_c||H_d)$. Asi se realiza lo mismo en nuestro ejemplo calculado $H_{abcd}=H(H(H_{ab}||H_{cd})$. Cada uno de los $H_i$ los llamamos hojas del arbol y El ultimo valor que se calcula es llamado nodo raiz del árbol.

## Algoritmo de Árbol de Merkle.

Partiendo de un conjunto de elementos en el vector $\vec{V} = (v_1, \dots, v_n)$ de longitud $2^k$, (en caso de no ser asi se completa a una potencia de $2$ con un valor a acordar). Dada una funcion de hash $H:X\to Y$. El algoritmo produce una raíz de Merkle, que es un único hash representativo de todo el vector.

**Entrada:**

- Un vector $V=(v_1,…,v_n)$, donde cada $v_i \in X$ y $n$ es una potencia de $2$.

**Salida:**

- Un único valor $y \in Y$, que corresponde al hash de la raíz del árbol de Merkle.

**Procedimiento:**

1. **Calcular los hashes iniciales de las hojas**:
- Para cada $i=1,…,n.$

$$
yi \leftarrow H(vi)
$$

Esto genera un conjunto inicial de hashes $(y_1, \dots, y_n)$ correspondientes a los elementos de $\vec V$

2. **Construir el árbol de Merkle**:

Para cada nivel superior del árbol, combinar pares de hashes consecutivos y calcular sus hashes hasta llegar a la raíz:

- Para $i=1,\dots,n−1$.

$$
y_{i+n}\leftarrow H(y_{2i−1}∣∣y_{2i})
$$

Aquí, cada $y_{i+n}$ es el hash de la concatenación de dos hashes hijos $y_{2i-1} \text{ y }y_{2i}$, generando las hojas del siguiente nivel del árbol $y_{n+1}, \dots, y_{2n-1}.$

3. **Obtener la raíz de Merkle**:
- La raíz del árbol de Merkle es $y_{2n-1}$, que representa el hash final del árbol.

Observemos que si el vector $\vec V$ se actualiza agregando información, podemos agregar nuevas hojas al árbol calculando los hashes correspondientes completando con ceros si es necesario para llegar a una potencia de $2.$ Volviendo al ejemplo anterior, nuestro vector se expande con nuevos bloques de información $e$ y $f$. Calculando la rama nueva coloreada expandiendo el árbol.


Con esta ultima propiedad podemos realizar con la ayuda de los árboles de Merkle un esquema de compromiso vectorial.

## Arboles de Merkle como Compromisos Vectoriales.

Con los siguientes algoritmos podemos utilizar a los árboles de merkle como un compromiso vectorial. Dada la construcción del árbol de Merkle $T$ de el vector de información $\vec V$, se quiere saber si el bloque de información $s$ se encuentra en $\vec V$.

- $(H) \leftarrow \mathsf{Setup}(1^{\lambda}):$ Donde en la entrada tenemos parámetros del sistema y la salida es la función de hash a utilizar.
- $\mathsf{C} \leftarrow \mathsf{Commit}(T):$ Se tiene como salida el compromiso $\mathsf{C}$ es decir la raíz del árbol de Merkle.
- $(i,\pi) \leftarrow\mathsf{Open}(T,s)$: $i$ es el lugar en donde se encuentra $s$ y $\pi=(y_{(1)},\dots, y_{(m)})$ son los hashes necesarios para que el agente verificador reconstruya la raíz y donde $m=\operatorname{log}2(n)$.
- $*\mathsf{1/0}\leftarrow\mathsf{Verify}(H,C,\pi)$:*El verificador tiene que reconstruir la raíz de la siguiente forma:

$$
\mathsf{C} = H(\ldots H(H( s || y{(1)})||y_{(2)}) \ldots || y_{(m)})
$$

Así el verificador calcula $\operatorname{log}_2(n)$ veces la función hash de un cierto valor.

## Conclusión

Un árbol de Merkle proporciona una estructura de datos eficiente. Gracias a su construcción jerárquica de hashes, permite generar un compromiso único sobre el contenido de los datos, encapsulado en la raíz del árbol. Además, su estructura admite actualizaciones incrementales y permite pruebas eficientes de pertenencia actualizables, lo que hace de los árboles de Merkle una herramienta robusta para aplicaciones de integridad de datos y compromisos criptográficos. En particular, al emplearlos como compromisos vectoriales, facilitan pruebas de inclusión sin necesidad de revelar toda la información almacenada.

### Referencias

https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_6.pdf

https://hackmd.io/@kullervo/commitmentVector

https://eprint.iacr.org/2011/495.pdf