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.
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.
Cómo almacenar Merkle Patricia Tree¶
Cómo actualizar Merkle Patricia Tree¶
Cómo realizar verificaciones usando Merkle Patricia Tree¶
Teoremas¶
- Los Merkle Trees iguales deben tener el mismo root hash.
- 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.