¿Te resulta más fácil leer con fondo crema, un tono de color, más contraste o un texto más grande? Elige tus colores y tu texto una sola vez, para todas las páginas.

Lección gratuita

Árboles de Merkle y pruebas de pertenencia

Después de esta lección: Puedo verificar una prueba de pertenencia de Merkle frente a una raíz.

Lección de 65 min2 comandosLaboratorio de pruebas de conocimiento cero: compromisos, Schnorr, Fiat-Shamir y Merkle en Python

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

PalabraQué significa
Hojael hash de un elemento de la lista
Nodoel hash de dos hashes unidos
Raízel único hash de arriba del árbol
Hermanoel otro hash de una pareja
Prueba de pertenencialos 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

Código: python
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

Comando
docker exec jupyter python3 steps/membership.py

Se 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 listaNiveles sobre las hojasHashes en una prueba
422
833
10241010
10485762020

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

Comando
docker exec jupyter grep -n def merkle.py

Se muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.

Sobre este laboratorio y su código: Laboratorio de pruebas de conocimiento cero: compromisos, Schnorr, Fiat-Shamir y Merkle en Python

¿Enseñas a una clase? Asigna este módulo a tus alumnos con guía del profesor, tareas con corrección automática y un laboratorio para cada alumno.