Merkle Patricia Tree

Introducción: Radix Tree

Un Radix Tree que utiliza una dirección a modo de clave tendrá las siguientes características:

  • Las direcciones se representan mediante caracteres hexadecimales.
  • Cada nodo del árbol es una matriz de 16 elementos (0123...def).
  • Nodos leaf: su valor puede ser cualquier dato binario.
  • non-leaf node: su valor es un hash calculado en base a los datos de sus nodos _children.

Para una dirección de 160-bits, la altura máxima del árbol es 40.

../../_images/radix_tree.png

Problemas: mucho espacio para una entrada sencilla; 40 pasos para cada lookup

Avanzado: Merkle Patricia Tree

Para reducir el espacio de almacenamiento de Radix Tree, los nodos en Merkle Patricia Tree se dividen en tres tipos:

  • nodo de extensión: comprime los nodos utilizando prefijos comunes.
  • nodo hoja: comprime los nodos utilizando prefijos únicos
  • nodo rama: ídem a los nodos en el Radix Tree.

../../_images/merkle_tree.png

Cómo almacenar Merkle Patricia Tree

Almacenamiento de los pares clave/valor

hash(value) = sha3(serialize(value))

key = hash(value)

Cómo actualizar Merkle Patricia Tree

Consulta

DFS de arriba hacia abajo

Actualizar, Eliminar o Añadir

  1. Realizar consultas en el nodo, desde arriba hacia abajo.
  2. Actualizar el hash y el path desde abajo hacia arriba.

../../_images/merkle_tree_update.png

Performance Cada operación cuesta O (log (n)).

Cómo realizar verificaciones usando Merkle Patricia Tree

Teoremas

  1. Los Merkle Trees iguales deben tener el mismo root hash.
  2. Los Merkle Trees distintos deben tener distintos root hash.

Usando los teoremas se puede verificar el resultado de la ejecución de las transacciones.

Verificación rápida

Un cliente lightweight, sin necesidad de sincronizar enormes bloques de transacciones, puede determinar inmediatamente el estado y el balance exacto de cualquier cuenta simplemente consultando la red para buscar una ruta desde la raíz hasta la cuenta nodo.