La definición: el nombre de un nodo contiene el de sus hijos

El nivel anterior dejó resuelto el caso más simple del direccionamiento por contenido: un bloque de bytes se nombra con el hash de esos bytes, y ese nombre trae de regalo la integridad y la deduplicación. El problema es que casi nada de lo que nos importa es un bloque suelto. Un directorio contiene ficheros, un fichero contiene bloques, un documento contiene versiones y una base de datos contiene tablas que contienen filas. Extender el direccionamiento por contenido a las estructuras admite dos respuestas evidentes y ambas son malas: serializar el conjunto entero y hashearlo produce un nombre monolítico que cambia por completo ante el retoque más pequeño, y hashear cada parte por separado deja la lista de partes fuera del esquema, sin nombre y sin verificación. La construcción de Merkle es la tercera respuesta, y consiste en un movimiento tan discreto que cuesta ver su alcance: meter los nombres de los hijos dentro de aquello que se hashea para nombrar al padre. Todo lo que hace interesante a este nivel se deduce de ese único gesto.

De nombrar un bloque a nombrar una estructura

Conviene enunciar la regla antes de discutirla, porque es corta y no admite matices. Un nodo tiene dos cosas: unos datos propios y una lista ordenada de enlaces a otros nodos. Su identificador es el hash criptográfico de la serialización conjunta de ambas cosas, y para poder serializar los enlaces hay que conocer antes los identificadores de los hijos. De ahí sale una definición recursiva en la que el nombre de un nodo no depende solo de lo que ese nodo contiene, sino de todo lo que alcanza por debajo.

// La regla que define el grafo entero, y no hay mas regla que esta
function idDe(nodo) {
  const enlaces = nodo.hijos.map(idDe);        // primero los hijos
  const cuerpo = serializar(nodo.datos, enlaces);
  return hash(cuerpo);                          // el nombre incluye a los hijos
}

Merece la pena mirar el orden de las dos primeras líneas, porque contiene la asimetría que gobierna todo lo demás. Un padre no puede existir hasta que sus hijos tienen nombre; un hijo, en cambio, ignora por completo quién lo apunta y cuántos lo apuntan. El grafo se construye siempre de abajo hacia arriba y se recorre siempre de arriba hacia abajo, y esa dirección única no es una convención de implementación sino una consecuencia aritmética de que el hash del padre dependa del identificador del hijo.

La segunda pieza que conviene fijar es qué se hashea exactamente. No se hashean los hijos: se hashean sus identificadores. Un nodo intermedio suele ocupar unos pocos cientos de bytes aunque el subgrafo que cuelga de él pese gigabytes, porque lo único que guarda de cada hijo es un identificador de tamaño fijo, más el nombre lógico del enlace y, en la mayoría de los formatos, el tamaño acumulado de lo que hay debajo. Esa compresión brutal de una estructura arbitraria en una lista de nombres cortos es lo que permite manipular grafos enormes leyendo bloques pequeños.

Anatomia de un nodo antes y despues de hashearse

  datos propios ......... lo que el nodo dice de si mismo
  enlace 0 .............. nombre logico, identificador del hijo, tamano debajo
  enlace 1 .............. nombre logico, identificador del hijo, tamano debajo
  enlace k .............. ...

  se serializa todo lo anterior de forma canonica
  se hashea la serializacion completa
  el resultado es el identificador del nodo

Fíjate en que los datos propios y los enlaces entran juntos en la misma serialización. Si entraran por separado y se hashearan de forma independiente, dos nodos podrían intercambiar contenido y estructura sin que el nombre lo delatara; al hashear el cuerpo entero, cualquier alteración de cualquier campo —incluido el nombre lógico de un enlace o el orden en que aparecen— produce un identificador distinto. La integridad no cubre solo lo que hay, sino también cómo estaba dispuesto.

Por qué es acíclico por construcción

La palabra acíclico aparece en el nombre y es fácil leerla como una restricción que el diseñador impone para que los algoritmos terminen. No lo es. Es un teorema, y su demostración cabe en dos frases. Para calcular el identificador de un nodo hace falta conocer antes el identificador de todos sus hijos. Un ciclo exigiría conocer el nombre de A para calcular el de B y el de B para calcular el de A, es decir, exigiría resolver un punto fijo del hash, que es precisamente el problema que la función criptográfica está diseñada para hacer intratable.

Por que no se puede escribir un ciclo

  quiero que A apunte a B y que B apunte a A

  para nombrar A necesito el nombre de B
  para nombrar B necesito el nombre de A
  para nombrar A necesito el nombre de B
  ...

  no hay orden en el que empezar, y forzarlo equivale a hallar un punto fijo del hash

Esta diferencia entre prohibido y computacionalmente inalcanzable importa más de lo que parece. En un grafo de punteros convencional, la ausencia de ciclos es una invariante que alguien debe mantener y que cualquier código descuidado puede romper; aquí no hay nada que mantener, porque el ciclo no se puede escribir aunque se quiera. De ahí se sigue, gratis, que existe un orden topológico, que la recursión de recorrido termina siempre, que el recuento de referencias basta como recolector de basura sin detector de ciclos, y que la profundidad del grafo está acotada por el trabajo que se hizo al construirlo.

flowchart TB
R[raiz con id derivado de a y b] --> A[nodo a]
R --> B[nodo b]
A --> H[hoja compartida con id identico]
B --> H
A --> X[hoja propia de a]
B --> Y[hoja propia de b]
style H fill:#a6e3a1,color:#11111b
style R fill:#89b4fa,color:#11111b

El diagrama muestra el otro rasgo que separa el grafo del árbol: la hoja compartida tiene dos padres y existe una sola vez. Nadie programó esa fusión. Si dos ramas contienen exactamente el mismo subgrafo, sus raíces reciben el mismo hash, y dos nodos con el mismo nombre son el mismo nodo por definición del esquema. La deduplicación estructural, que en un sistema convencional sería una optimización que hay que buscar activamente, aquí es un efecto secundario del que resulta imposible librarse.

Lo que cambia la recursión

Con la regla y su corolario sobre la mesa se pueden derivar las consecuencias, y conviene hacerlo despacio porque las tres se usarán constantemente en las lecciones siguientes. La primera es la verificación transitiva. Quien tiene el identificador de la raíz y recibe el bloque de la raíz puede comprobarlo hasheándolo; ese bloque contiene los identificadores de los hijos, de modo que ahora puede comprobar los hijos cuando lleguen; y así hacia abajo. Un solo dato de confianza inicial —un identificador de treinta y dos bytes— basta para autenticar un grafo de cualquier tamaño, y además lo hace de forma incremental, bloque a bloque, sin necesidad de tenerlo entero.

La segunda es la compartición estructural. Si dos versiones de una estructura comparten un subgrafo, comparten literalmente los mismos nodos, porque el nombre de ese subgrafo no ha cambiado. Publicar la versión nueva no consiste en copiar nada, sino en escribir únicamente los nodos que sí cambiaron. Es exactamente el comportamiento de una estructura de datos persistente, pero obtenido sin escribir código de compartición y funcionando además entre procesos, entre máquinas y entre organizaciones que no se conocen.

La tercera es la localidad del cambio, que es la cara complementaria de la anterior. Modificar una hoja obliga a renombrar a su padre, que obliga a renombrar al abuelo, hasta la raíz. Nada más. El coste de una modificación no es proporcional al tamaño de la estructura sino a la profundidad del camino desde la hoja tocada hasta la raíz, que en un grafo bien equilibrado crece de forma logarítmica.

Conviene notar que esa propagación hacia arriba es obligatoria y no un efecto que se pueda evitar con ingenio. Como el nombre del padre depende del nombre del hijo, no existe forma de cambiar un hijo conservando el nombre del padre; si existiera, sería una colisión. Por eso el único parámetro que el diseñador controla es la forma del grafo: aridad alta y profundidad baja abaratan la propagación y encarecen cada nodo interno, y la elección entre ambas cosas volverá a aparecer en las tres lecciones siguientes con distinto disfraz.

Editar una hoja en un grafo de un millon de nodos

  hoja modificada .................. 1 nodo nuevo
  padres en el camino a la raiz .... unos 20 nodos nuevos
  resto del grafo .................. 0 nodos nuevos, se reutilizan tal cual

  la version anterior sigue siendo valida y accesible por su raiz antigua

La cuarta tarjeta merece un comentario porque suele malinterpretarse. Que las versiones antiguas sigan siendo direccionables no significa que alguien las conserve: el nombre sigue siendo válido, pero los bytes solo existen mientras alguien los almacene. Esa separación entre nombrar y tener recorre todo el nivel y volverá con fuerza en la última lección, porque es la frontera exacta entre lo que el direccionamiento por contenido resuelve y lo que deja intacto.

El coste, y lo que este grafo no resuelve

Conviene añadir que la ausencia de ciclos no impide expresar relaciones que en un modelo mutable serían circulares; solo impide expresarlas dentro del grafo. Si un nodo necesita referirse a algo que a su vez lo referencia, la salida habitual es introducir una indirección: uno de los dos extremos apunta a un nombre mutable en lugar de a un identificador de contenido, y ese nombre se resuelve fuera del esquema. La circularidad se recupera, pero pasa a vivir en una capa que ya no ofrece las garantías de esta, y reconocer ese traslado es parte de diseñar bien sobre estas estructuras.

Toda la elegancia anterior se paga en un sitio muy concreto: la mutabilidad desaparece. Un nodo no se puede modificar, porque modificarlo lo convierte en otro nodo con otro nombre. Un nodo tampoco sabe quién lo apunta, así que no se puede navegar hacia arriba sin un índice construido aparte. Y ninguna referencia se puede reparar: si un enlace apunta a un identificador cuyos bytes nadie tiene, el enlace no está roto en el sentido habitual —sigue siendo correcto y verificable— sino simplemente irresoluble, que es un fallo distinto y con remedios distintos.

Hay además una consecuencia práctica que sorprende a quien viene de sistemas de ficheros. Como la identidad depende de los bytes serializados, dos representaciones distintas de la misma información lógica producen nombres distintos. El orden de las claves de un mapa, la codificación de un entero, la presencia de un campo con valor por defecto: cualquiera de esas decisiones, si no está canonicalizada, rompe la deduplicación y hace que dos réplicas que contienen lo mismo no se reconozcan. La canonicidad de la serialización no es un detalle de formato, es un requisito de corrección.

Y conviene ser explícito sobre lo que el grafo deliberadamente no contiene, porque el error más común al construir sobre él consiste en esperar que lo aporte. No hay orden temporal: dos raíces distintas no se pueden ordenar mirándolas. No hay autoría: nada dice quién escribió un nodo. No hay actualidad: un identificador antiguo es tan válido como uno recién calculado. Y no hay disponibilidad: un enlace correcto puede apuntar a bytes que ya no tiene nadie. Las cuatro cosas se pueden añadir encima —con firmas, con relojes lógicos, con punteros mutables, con una capa de red— y las cuatro son responsabilidad de otras capas del track.