Verificación por trozos: comprobar sin tener el fichero entero

Hasta aquí el árbol se ha vendido como una técnica de rendimiento, y esa es la mitad menos interesante de la historia. Su consecuencia estructural es otra y no tiene equivalente en un diseño encadenado: si el resumen de un fichero se construye combinando resúmenes de partes, entonces cualquiera que tenga la raíz puede autenticar una parte concreta sin tener las demás, aportando únicamente los pocos valores intermedios que conectan esa parte con la raíz. Un resumen secuencial no admite nada parecido a ningún precio, porque su valor final depende de haber recorrido todos los bytes en orden y no queda ningún objeto intermedio que citar. La diferencia parece técnica y es de producto: decide si tu sistema puede reanudar una descarga interrumpida, reproducir un vídeo mientras lo comprueba, pedir trozos a varios pares a la vez o abrir el minuto cuarenta sin traerse los treinta y nueve anteriores. Esta lección desarrolla la propiedad con precisión, incluyendo lo que hay que aportar además de la raíz, que es la parte que casi todas las explicaciones se saltan.

La prueba de camino

Supón que tienes la raíz de un fichero y quieres comprobar que unos bytes concretos que te acaban de entregar pertenecen de verdad a ese fichero y están en esa posición. Con un resumen secuencial la respuesta es que no puedes: tendrías que recorrer el fichero entero para llegar al valor que sabes comparar. Con un árbol la respuesta es que sí, y lo que necesitas es el fragmento más los valores encadenados de los hermanos que hay a lo largo del camino desde ese fragmento hasta la raíz.

El procedimiento es mecánico. Se calcula el valor encadenado del trozo recibido. Se combina con el valor del hermano para obtener el del padre. Se combina el del padre con el de su hermano para obtener el del abuelo. Se sube así hasta obtener un candidato a raíz y se compara con la raíz que ya se tenía. Si coinciden, el fragmento es auténtico, está en la posición que dice y pertenece a ese fichero, y todo eso se ha establecido sin haber visto un solo byte del resto.

flowchart BT
T[trozo recibido] --> P1[padre]
H1[hermano del trozo] --> P1
P1 --> P2[abuelo]
H2[hermano del padre] --> P2
P2 --> R[raiz conocida]
style T fill:#a6e3a1,color:#11111b
style H1 fill:#f9e2af,color:#11111b
style H2 fill:#f9e2af,color:#11111b
style R fill:#cba6f7,color:#11111b

Los números concretos son la parte que convence. En BLAKE3 las hojas son trozos de mil veinticuatro bytes y cada nodo padre son sesenta y cuatro bytes: los valores encadenados de sus dos hijos concatenados. Un fichero de un gigabyte tiene alrededor de un millón de trozos, lo que da un árbol de unos veinte niveles. Autenticar un trozo cualquiera de ese fichero exige por tanto unos veinte nodos padre, es decir del orden de mil trescientos bytes de prueba para certificar mil veinticuatro bytes de datos. Y lo importante es cómo crece: la prueba es logarítmica en el tamaño del fichero, de modo que pasar a un terabyte añade diez niveles y unos seiscientos cuarenta bytes más.

// Verificar un fragmento subiendo por el camino hasta la raiz
function verificaFragmento(trozo, indice, hermanos, raizConocida) {
  let actual = cvDeTrozo(trozo, indice);
  let pos = indice;
  for (const hermano of hermanos) {          // de la hoja hacia arriba
    actual = pos % 2 === 0
      ? cvDePadre(actual, hermano)           // yo soy el izquierdo
      : cvDePadre(hermano, actual);          // yo soy el derecho
    pos = Math.floor(pos / 2);
  }
  return iguales(salidaRaiz(actual), raizConocida);
}

Los tres formatos

La especificación de referencia para esto es Bao, el proyecto del que salió el modo en árbol que después se publicó como BLAKE3 y que hoy se centra en la transmisión verificada. Define tres formatos y cada uno resuelve un problema distinto de despliegue.

El formato combinado es el contenido de los trozos y de los nodos padre concatenados en orden previo —primero el padre, después su subárbol izquierdo y después el derecho— con la longitud de la entrada añadida al principio en ocho bytes en orden de byte menos significativo primero. Ese orden hace que la secuencia en disco coincida con el orden de un recorrido en profundidad, de modo que un descodificador que lea de principio a fin no necesita saltar nunca. Su sobrecoste es acotado y pequeño: un árbol binario sobre n hojas tiene n menos uno nodos internos de sesenta y cuatro bytes cada uno, lo que sobre trozos de mil veinticuatro bytes queda por debajo del seis coma veinticinco por ciento.

El formato externo es el mismo pero omitiendo los trozos, de manera que la codificación es diminuta y el descodificador lee los datos del fichero original. Es la opción natural cuando ya tienes el fichero en disco y solo quieres poder verificarlo por partes sin duplicarlo: el árbol se guarda aparte y ocupa la fracción de metadatos que acabamos de calcular.

El formato de rodaja es el que cierra el caso de la transferencia parcial. Quien pide indica un punto de inicio y un número de bytes, y el extractor omite todos los trozos y nodos padre que no se encontrarían al buscar ese punto y leer esa cantidad. El ejemplo de la especificación es transparente: sobre una entrada de dos mil cuarenta y nueve bytes, pedir una rodaja que empieza en el byte mil veinticuatro produce la cabecera de longitud, el nodo padre raíz, el nodo padre izquierdo y el segundo trozo, y nada más. Descodificar una rodaja funciona igual que descodificar el formato combinado, con la única diferencia de que donde el descodificador saltaría hacia delante simplemente sigue leyendo, porque el salto ya lo hizo el extractor.

La cuarta tarjeta merece un comentario porque es una decisión de diseño deliberada y con historia. Una versión anterior de Bao mezclaba la longitud en el nodo raíz como dato asociado, y se retiró; el resultado es que el resumen que produce la herramienta de transmisión verificada coincide exactamente con el resumen BLAKE3 normal del mismo fichero. Eso significa que un sistema puede adoptar la verificación por trozos sin cambiar ni uno de sus identificadores, lo cual convierte la adopción en incremental en lugar de en una migración.

Por qué cambia las transferencias y el streaming

Con un resumen secuencial la verificación es un veredicto que llega al final y no admite matices. Descargas cuatro gigabytes, calculas, comparas, y si no cuadra sabes exactamente una cosa: que algo está mal en alguna parte. No sabes dónde, no puedes conservar la parte buena y no puedes reanudar; solo puedes tirarlo todo y volver a empezar, con la misma probabilidad de que vuelva a fallar. Ese modo de fallo tiene un nombre útil: el radio de daño de una corrupción es el objeto entero.

Con verificación por trozos el radio de daño baja al trozo. Cada fragmento se comprueba al llegar y el que falla se vuelve a pedir sin tocar los demás. De ahí salen cuatro capacidades que en local-first no son adornos.

La primera es la reanudación honesta. Una descarga interrumpida al setenta por ciento conserva ese setenta por ciento con garantía, no por confianza, y continúa desde ahí. La segunda es la descarga desde varias fuentes: distintos rangos se piden a distintos pares y cada respuesta se valida por separado contra la misma raíz, de modo que un par malicioso solo puede hacer fallar sus propios trozos y queda identificado en el acto. La tercera es la reproducción en flujo: el descodificador puede entregar el contenido de cada trozo válido a quien lo pidió inmediatamente después de comprobarlo, lo que permite empezar a reproducir sin renunciar a la verificación. La cuarta es el acceso aleatorio: pedir el minuto cuarenta cuesta el trozo más su camino, y no los treinta y nueve minutos anteriores.

# Reanudar sin verificacion es reanudar sin garantia
curl -C - -O https://ejemplo.org/paquete.bin   # continua donde iba
sha256sum paquete.bin                          # veredicto al final, sin diagnostico

# Con arbol, cada rango se pide y se comprueba por separado contra la misma raiz

Las trampas del descodificador

Un descodificador verificador es fácil de escribir mal de maneras que pasan todas las pruebas y comprometen la garantía, y la especificación de Bao documenta las trampas concretas. La principal es el requisito del trozo final: la longitud de la entrada solo se considera validada cuando se valida el último trozo, y el descodificador no debe exponer la longitud al llamante de ninguna forma antes de eso. Las formas de exponerla son más numerosas de lo que parece: un método explícito que la devuelva, buscar más allá del final, buscar relativo al final, y sobre todo el caso de la codificación vacía, donde un descodificador que asuma que ha terminado al llegar a la posición cero sin comprobar el trozo vacío estaría aceptando cualquier raíz como válida.

La segunda trampa son las lecturas cortas. Las interfaces de entrada y salida de casi todos los lenguajes permiten que una lectura devuelva menos bytes de los pedidos por cualquier motivo, y una implementación que no llame en bucle hasta completar funcionará en las pruebas y fallará de forma esporádica al leer de una tubería o de un conector de red. Además abre un ataque: un adversario que declare una longitud mayor que los bytes disponibles puede lograr que un descodificador descuidado valide lo que hay y quede en un estado inconsistente que el atacante controla.

La tercera es esperar de la codificación una unicidad que no ofrece. El formato es maleable: como el descodificador nunca lee hasta el final del fichero codificado sino exactamente lo que la cabecera de longitud indica, unos bytes de basura añadidos al final no afectan a la descodificación y producen ficheros codificados distintos que descodifican al mismo contenido. Comparar dos ficheros codificados byte a byte para predecir si darán el mismo resultado es por tanto incorrecto. Lo que sí se garantiza, y es lo que importa, es que los bytes de salida coinciden con los de la entrada original, que cualquier final de fichero comunicado coincide con la longitud real, y que no existen colisiones de descodificación: una salida completa no descodifica bajo dos raíces distintas.