La propiedad clave: la raíz resume el grafo entero

La lección anterior estableció la regla y sus consecuencias inmediatas, pero dejó sin explotar la que convierte al Merkle DAG en una herramienta de sistemas distribuidos y no en una curiosidad de teoría de estructuras. La regla dice que el nombre de un nodo depende de los nombres de sus hijos; aplicada hacia arriba y de forma reiterada, dice que el nombre de la raíz depende de absolutamente todo lo alcanzable desde ella. Eso convierte un identificador de tamaño fijo en un resumen fiel de una estructura de tamaño arbitrario, y transforma la pregunta más cara de cualquier sistema replicado —tenemos los dos lo mismo— en una comparación de treinta y dos bytes que puede hacerse por una red lenta, en un mensaje diminuto y sin leer un solo byte de los datos. Y cuando la respuesta es que no, la misma estructura ofrece un procedimiento de descenso que localiza la diferencia pagando en proporción a la diferencia y no en proporción al tamaño. Esta lección demuestra la propiedad, la explota y luego mide con precisión hasta dónde llega.

De la regla local a la propiedad global

El enunciado que interesa es una implicación en un solo sentido y conviene decirlo así de crudo: si el identificador de dos nodos coincide, entonces los subgrafos completos que cuelgan de ambos son idénticos nodo a nodo. La dirección contraria es trivial, porque el identificador es una función determinista del contenido, y por eso suele darse por supuesta y no aporta nada. Lo valioso es la primera dirección, porque permite concluir algo sobre una estructura enorme a partir de un dato minúsculo.

La demostración es una inducción sobre la profundidad y cabe en un párrafo. En el caso base, un nodo sin hijos: si los hashes coinciden, o los contenidos coinciden o alguien ha encontrado una colisión en la función. En el paso inductivo, un nodo con hijos: si los hashes coinciden, coinciden los cuerpos serializados salvo colisión, y el cuerpo contiene tanto los datos propios como la lista de identificadores de los hijos; por hipótesis de inducción, identificadores iguales en los hijos implican subgrafos iguales en los hijos. La conclusión se propaga hacia abajo hasta las hojas.

Conviene subrayar la cláusula que aparece dos veces en ese razonamiento, porque define la naturaleza exacta de la garantía. La igualdad no es una certeza lógica sino una certeza computacional: es cierta salvo que exista una colisión, y la resistencia a colisiones de la función es lo único que impide construirla. Es la misma clase de garantía sobre la que se apoyan las firmas digitales y el control de versiones, y sostiene sistemas enteros sin dramatismo, pero tiene fecha de caducidad ligada a la vida útil de la función elegida.

Que cuesta responder a la pregunta tenemos los dos lo mismo

  comparar campo a campo ....... proporcional al tamano de los datos
  comparar marcas de tiempo .... barato y poco fiable, depende de relojes
  comparar numeros de version .. barato y solo vale con un contador central
  comparar raices de Merkle .... constante, y fiable como comparar byte a byte

Merece la pena detenerse en la tercera línea de esa tabla, porque es la alternativa que más se usa y la que peor envejece. Un número de versión funciona mientras alguien lo asigne de forma centralizada; en cuanto dos réplicas pueden avanzar por su cuenta, el contador deja de ordenar nada y hay que sustituirlo por un vector, con el coste de metadatos que el track ya estudió. La raíz de Merkle no es un contador y no pretende ordenar: se limita a decir si dos estados son el mismo, que es una pregunta más débil y, precisamente por eso, contestable sin coordinación de ningún tipo.

Comparar dos estructuras enormes con un solo intercambio

La aplicación directa es el saludo de sincronización. Dos réplicas que quieren saber si divergen se envían mutuamente el identificador de su raíz. Si coinciden, han terminado: el protocolo concluye con la certeza de que sus estados son idénticos hasta el último byte, habiendo transferido unas pocas decenas de bytes. Este caso, que parece anecdótico, es en realidad el caso mayoritario en producción, porque la inmensa mayoría de las comprobaciones periódicas de un sistema replicado devuelven que no hay nada que hacer.

// El saludo completo cuando no hay divergencia
async function estamosAlDia(remoto) {
  const mia = await raizLocal();
  const suya = await remoto.pedirRaiz();
  return mia === suya;   // dos identificadores, ninguna lectura de datos
}

Hay un detalle de ese saludo que conviene no perder de vista, porque explica por qué la técnica funciona bien en redes hostiles. El resultado no depende de que ambos extremos sean honestos ni de que el canal sea fiable: si el remoto miente sobre su raíz, lo único que consigue es que el descenso posterior no cuadre y falle la verificación de algún bloque; si el mensaje llega corrupto, la comparación da distinto y se repite. Ningún fallo del canal ni del interlocutor puede producir un falso positivo de igualdad, que es la respuesta peligrosa, porque para fabricarla haría falta una colisión.

El contraste con las alternativas convencionales es lo que da la medida del ahorro. Comparar por marcas de tiempo obliga a recorrer la estructura entera y además es poco fiable, porque los relojes mienten y una copia puede tener fecha nueva con contenido idéntico. Comparar por tamaños es más barato y más frágil todavía. Comparar campo a campo es fiable y cuesta proporcional al tamaño de los datos, además de exigir que ambos lados estén dispuestos a transmitirlos. La raíz de un Merkle DAG da la fiabilidad de la última opción al precio de la primera.

El descenso: localizar la diferencia pagando por la diferencia

Cuando las raíces no coinciden, la estructura ofrece algo mejor que un simple no. Basta descender un nivel: se piden los dos bloques raíz, se comparan sus listas de identificadores de hijos y se anotan las posiciones donde difieren. Los subgrafos cuyos identificadores coinciden se descartan enteros, sin mirarlos, con la garantía de la propiedad anterior. Solo se recurre sobre las ramas discrepantes, y así hasta llegar a las hojas que efectivamente cambiaron.

// Descenso comparativo: solo se abre lo que difiere
async function diferencias(idA, idB, ruta = []) {
  if (idA === idB) return [];                     // rama identica, se poda entera
  const [a, b] = await Promise.all([leer(idA), leer(idB)]);
  if (esHoja(a) || esHoja(b)) return [{ ruta, idA, idB }];
  const salida = [];
  for (const clave of union(a.enlaces, b.enlaces)) {
    salida.push(...await diferencias(a.enlaces[clave], b.enlaces[clave], [...ruta, clave]));
  }
  return salida;
}

flowchart TB
RA[raiz local] --> A1[rama uno identidad igual]
RA --> A2[rama dos identidad distinta]
RB[raiz remota] --> A1
RB --> B2[rama dos version remota]
A2 --> H1[hoja cambiada]
B2 --> H2[hoja cambiada remota]
style A1 fill:#a6e3a1,color:#11111b
style H1 fill:#f38ba8,color:#11111b
style H2 fill:#f38ba8,color:#11111b

La cuenta del coste de ese descenso es la razón por la que esta técnica sostiene protocolos de antientropía en sistemas reales. Si en un grafo equilibrado de un millón de hojas ha cambiado una sola, el descenso abre un bloque por nivel a cada lado, alrededor de veinte bloques en total, y descarta el resto sin leerlo. El número de rondas es la profundidad y el número de bytes transferidos es proporcional al número de nodos en el camino, no al tamaño de la estructura. Cuando lo que ha cambiado son mil hojas dispersas, el coste sube a los caminos de esas mil hojas, que comparten los niveles altos y por tanto no se suman de forma independiente.

Descenso sobre un grafo de un millon de hojas y aridad treinta y dos

  hojas cambiadas ....... 1        bloques abiertos ....... unos 8 por lado
  hojas cambiadas ....... 100      bloques abiertos ....... unos 300 por lado
  hojas cambiadas ....... 100 000  bloques abiertos ....... casi todo el grafo

  el metodo gana cuando la divergencia es pequena y se degrada suavemente

La última fila del cuadro dice algo que conviene aceptar sin resistencia: cuando la divergencia es masiva, el descenso no ahorra nada y además paga muchas rondas de red para descubrirlo. Un protocolo maduro detecta ese caso pronto —por ejemplo, si en los dos primeros niveles difieren casi todos los enlaces— y cambia de estrategia, transfiriendo el subárbol entero de una vez en lugar de seguir preguntando. El descenso es una optimización para el caso frecuente, no un algoritmo universal, y tratarlo como lo segundo produce sincronizaciones iniciales lentísimas.

La segunda tarjeta merece una precisión, porque la palabra poda se usa a menudo para heurísticas que pueden equivocarse. Aquí no hay heurística ni margen de error tolerado: descartar una rama porque su identificador coincide es una deducción, con la misma fuerza que la demostración por inducción del principio de la lección. Esa exactitud es la que permite construir sincronizadores que no necesitan una fase de verificación posterior, y la que diferencia este mecanismo de los filtros probabilísticos que también se usan para comparar conjuntos y que sí admiten falsos positivos.

La cuarta tarjeta apunta a un beneficio que se aprovecha poco. El descenso produce, además del conjunto de bloques que faltan, la ruta lógica hasta cada uno: qué directorio, qué campo, qué índice. Eso convierte un mecanismo de sincronización en un mecanismo de diagnóstico, capaz de explicar en términos del dominio qué es lo que ha divergido, y no solo de arreglarlo en silencio.

Los límites exactos de la garantía

La propiedad es fuerte y por eso conviene acotar con precisión qué no dice, porque los errores de diseño más caros vienen de extenderla más allá de su alcance. Lo primero: la igualdad de raíces es igualdad de bytes serializados, no equivalencia semántica. Dos réplicas que contienen la misma información lógica pero la serializan con las claves en distinto orden, o con un entero codificado de dos maneras válidas, producirán raíces distintas y el protocolo concluirá que divergen. La canonicidad de la codificación es, por tanto, precondición de todo lo anterior.

Lo segundo, y más importante: la raíz no dice nada sobre el tiempo. Un identificador antiguo es tan válido y tan verificable como uno reciente, y no hay nada dentro del grafo que permita saber cuál de dos raíces distintas es posterior. Cuando el descenso encuentra una discrepancia, la estructura te dice dónde difieren, jamás cuál tiene razón. Esa pregunta pertenece a los relojes lógicos y a los CRDT de los niveles anteriores, o a una firma que ordene las raíces por fuera, y ninguna cantidad de hashing la responderá.

Lo tercero es una asimetría que se olvida a menudo: descubrir qué falta no es lo mismo que obtenerlo. El descenso identifica los bloques ausentes por su nombre y termina ahí. Que alguien tenga esos bytes y esté dispuesto a servirlos es un problema de la capa de red, y la lección final del nivel volverá sobre esa frontera. Un protocolo que confunda ambas cosas acabará con un conjunto perfecto de identificadores irresolubles.

Y lo cuarto es una fuga de información que conviene tener presente en escenarios adversarios. Participar en un descenso revela al otro extremo la forma de tu grafo: qué ramas coinciden con las suyas y cuáles no, con la granularidad que permita la estructura. Si los identificadores se derivan de contenido que el otro puede adivinar, el protocolo se convierte en un oráculo que confirma o desmiente hipótesis sobre lo que guardas. En despliegues donde eso importa, la respuesta habitual es cifrar antes de trocear, con el coste en deduplicación que eso conlleva y que la tercera lección ya adelantó.