Demostrar que un nombre está en la lista
Un árbol de Merkle convierte una lista entera en un solo hash corto, la raíz. Una prueba de pertenencia muestra después que un elemento está en la lista con unos pocos hashes, no con la lista entera.
Los sistemas de conocimiento cero lo usan para demostrar que perteneces a un grupo. Las blockchains lo usan para demostrar que un pago está en un bloque.
Al terminar esta lección
Nota
Puedo verificar una prueba de pertenencia de Merkle frente a una raíz.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Hoja | el hash de un elemento de la lista |
| Nodo | el hash de dos hashes unidos |
| Raíz | el único hash de arriba del árbol |
| Hermano | el otro hash de una pareja |
| Prueba de pertenencia | los hermanos del camino de una hoja a la raíz |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un árbol son hashes de hashes
Haz el hash de cada elemento para obtener las hojas. Une las hojas por parejas y haz el hash de cada pareja para el nivel siguiente. Repite hasta que quede un hash: la raíz.
Cambia cualquier elemento y cambia su hoja, luego su padre, y así hasta la raíz. Por eso la raíz representa la lista entera. El módulo 37 (Blockchain y registros distribuidos) enlazaba bloques con hashes en fila; un árbol los enlaza por parejas.
Pruébalo: un árbol de cuatro salas
import hashlib
def leaf(item):
return hashlib.sha256(("leaf:" + item).encode()).hexdigest()
def node(left, right):
return hashlib.sha256(("node:" + left + right).encode()).hexdigest()
# Cuatro salas reservadas en un edificio compartido.
a = leaf("sala-1")
b = leaf("sala-2")
c = leaf("sala-3")
d = leaf("sala-4")
left = node(a, b)
right = node(c, d)
root = node(left, right)
print("raíz:", root[:16])
# Una prueba de que sala-3 está reservada: d, y luego left.
check = node(left, node(leaf("sala-3"), d))
print("la prueba de sala-3 da la raíz:", check == root)
# Cambia de orden left y el nodo interior en la llamada de fuera y ejecuta otra vez.
Una prueba son los hermanos al subir
Para mostrar que un elemento está en la lista, da sus hermanos. Primero el hash que tiene al lado, luego el que tiene al lado su padre, y así hasta arriba. Quien comprueba hace el hash del elemento, une cada hermano por el lado correcto y compara el resultado con la raíz.
Una lista de 8 necesita 3 hermanos, y una de alrededor de un millón solo 20.
Comprueba que dev está en la lista
docker exec jupyter python3 steps/membership.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.
Lee lo que imprimió el laboratorio
El script imprime en inglés: proof es la prueba y list la lista. Ocho nombres dieron una raíz que empieza por fb53457810bd44ae. La prueba de dev, el cuarto nombre, tiene 3 hashes, cada uno marcado L o R según el lado en que va. Al subir el camino desde dev salió la raíz, así que la respuesta fue True.
El nombre dan con la misma prueba dio False. Nadie puede construir un camino que convierta otro nombre en esta raíz.
Ejemplo: cuánto mide una prueba
| Elementos en la lista | Niveles sobre las hojas | Hashes en una prueba |
|---|---|---|
| 4 | 2 | 2 |
| 8 | 3 | 3 |
| 1024 | 10 | 10 |
| 1048576 | 20 | 20 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un error frecuente
Advertencia
Mucha gente cree que los hermanos se pueden unir en cualquier orden. No se puede: node(a, b) y node(b, a) son hashes distintos. La posición del elemento te dice el lado. Una posición par en un nivel significa que el hermano va a la derecha.
Lista las funciones de merkle.py
docker exec jupyter grep -n def merkle.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.