Merkle Tree
Un árbol de Merkle coloca los hashes de datos en las hojas y los hashes de los hijos en los nodos internos, permitiendo una verificación de integridad eficiente de grandes datos; se usa en Git y en blockchains.
Propósito
Hacer eficiente la verificación de integridad de datos a gran escala y localizable en bloques de datos específicos.
Mecanismo
Las hojas contienen los hashes de los bloques de datos H(d_i). Los nodos internos hashean la concatenación de sus hijos, H(left||right). El hash raíz representa el todo. Verificar un bloque solo requiere los O(log n) hashes hermanos del camino raíz-hoja (una prueba de Merkle). Cualquier cambio en un bloque altera el hash raíz.
Casos de uso
- Verificación del árbol de objetos de Git
- Verificación de transacciones en blockchain
- Direccionamiento de contenidos en IPFS
- Consistencia de almacenamiento distribuido
Ejemplos
- entrada
4 data blocks → a 2-level Merkle treeOutputThe root hash represents all of themO(log n) verification
Errores comunes
- Weak hashes enable collision forgery
- Use a secure hash such as SHA-256
Términos relacionados
Bloom Filter
Un filtro de Bloom aproxima la pertenencia a un conjunto con k funciones hash y un array de bits, ofreciendo eficiencia espacial a cambio de una tasa de falsos positivos. GLOSARIO
Consistent Hashing
El hash consistente remapea solo 1/n de las claves al añadir o eliminar nodos, minimizando la redistribución; se usa en caché distribuida y sharding. GLOSARIO
SHA-256
SHA-256 es el miembro de la familia SHA-2 con salida de 256 bits, muy usado en TLS, blockchains y aplicaciones criptográficas, sin ataques prácticos conocidos. GLOSARIO