Entrevista general: Verificar una prueba de inclusión de Merkle

Prompt y alcance

Este es un problema de implementación de protocolos y estructuras de datos criptográficas. Una prueba de inclusión de Merkle envía solo los nodos hermanos necesarios para conectar una hoja de destino con una raíz, en lugar de todo el árbol. RFC 9162 separa por dominios los hashes de hojas y de nodos interiores y requiere que el verificador use leaf_index y tree_size al decidir izquierda y derecha en cada nivel. Asume que el cliente obtuvo root_hash a través de un canal seguro; el verificador no establece esa confianza.

Qué evalúa el entrevistador

Distinguir hashes de hojas, hashes interiores e información de dirección de la ruta.
Usar leaf_index y tree_size para validación de límites y rutas.
Comprender la separación de dominios para que los bytes de una hoja no se confundan con la entrada de un nodo interior.
Explicar el tamaño de prueba O(log n) y el tiempo de verificación, además del límite de la raíz de confianza.

Aclaraciones a plantear primero

Confirma la especificación del árbol: el árbol de tamaño variable de RFC 9162 o un árbol binario completo fijo; canonicalización de hojas; algoritmo de hash y constantes de prefijo; y si la ruta está ordenada de hoja a raíz. Aclara también si se requieren pruebas de consistencia append-only o firmas, o solo una prueba de inclusión. Sin estas convenciones, una lista de hashes no define de forma única una raíz.

Respuesta de 30 segundos

Verifica 0 <= leaf_index < tree_size y limita la longitud de la ruta. Canonicaliza la hoja como HASH(0x00 || leaf_bytes), luego mantén fn = leaf_index, sn = tree_size - 1 y el hash actual r. En cada nivel, usa el bit bajo de fn o la condición fn == sn para decidir si el hermano está a la izquierda o a la derecha, calcula el hash con el prefijo interior 0x01 y desplaza ambos índices. Ten éxito solo cuando sn == 0 y r == root_hash.

Solución paso a paso

1. Fijar el contrato de entrada y la separación de dominios

El verificador necesita un algoritmo de hash versionado, codificación de hojas, orden de ruta y semántica de tamaño del árbol. El Merkle Tree Hash de RFC 9162 usa 0x00 para hojas y 0x01 para nodos interiores, evitando que la misma cadena de bytes se interprete en dos roles. No calcules el hash de leaf || sibling sin separación de dominios ni permitas que quien llama reemplace los prefijos arbitrariamente.

2. Realizar primero las comprobaciones de límites y recursos

leaf_index >= tree_size debe fallar; un árbol vacío no tiene una hoja válida. Limita la ruta, por ejemplo en ceil(log2(tree_size)) + 1, y exige una longitud de bytes fija para cada hash. Rechaza desbordamientos de enteros, codificaciones negativas, análisis duplicados y rutas sobredimensionadas para que pruebas hostiles no puedan consumir recursos ilimitados. Una ruta corta no es válida automáticamente; el estado final debe converger a una sola raíz.

3. Reconstruir la raíz nivel por nivel

Para el árbol de tamaño variable de RFC 9162, la paridad por sí sola es insuficiente: la condición de límite fn == sn cambia la dirección de concatenación. Desplaza tanto fn como sn después de cada nivel para mapear el nodo actual a su padre. Pseudocódigo:

text

verify(leaf, leafIndex, treeSize, path, expectedRoot):
  if treeSize <= 0 or leafIndex < 0 or leafIndex >= treeSize: return false
  r = HASH(0x00 || leaf)
  fn = leafIndex
  sn = treeSize - 1
  for sibling in path:
    if sn == 0: return false
    if (fn & 1) == 1 or fn == sn:
      r = HASH(0x01 || sibling || r)
    else:
      r = HASH(0x01 || r || sibling)
    fn = fn >> 1
    sn = sn >> 1
  return sn == 0 and r == expectedRoot

4. Verificar la concordancia entre la ruta y el tamaño del árbol

El tree_size de la prueba participa en el cálculo de la dirección; no es metadato decorativo de registro. Cuando la ruta se consume, sn debe ser cero. Si permanece positivo, la prueba no alcanzó la raíz; si sn ya es cero y quedan más hermanos, rechaza la prueba. Una implementación de árbol fijo puede usar reglas diferentes, pero su generador y verificador deben compartir esa convención de árbol en lugar de mezclarla con rutas de RFC 9162.

5. Complejidad, comunicación y confianza

Un árbol balanceado suele tener O(log n) hashes hermanos. La verificación toma O(log n) operaciones de hash y O(1) de estado más allá de la ruta; la comunicación es O(log n * hashSize). La prueba solo vincula una hoja a la raíz proporcionada. Si la raíz provino de una respuesta no confiable, un atacante puede reemplazar tanto la raíz como la prueba. Los protocolos de producción protegen la raíz y el tamaño del árbol con firmas, una cabecera de registro de confianza o transporte autenticado.

Respuesta modelo

Vincularía el verificador a una especificación de árbol versionada. Primero compruebo tree_size > 0, 0 <= leaf_index < tree_size, las longitudes de hash y el presupuesto de ruta, luego calculo r = HASH(0x00 || leaf). Mantengo fn = leaf_index y sn = tree_size - 1; en cada nivel coloco el hermano a la izquierda cuando fn es impar o fn == sn, de lo contrario a la derecha, y actualizo con HASH(0x01 || left || right). Desplazo ambos índices. Al final, solo sn == 0 y la igualdad con la raíz de confianza tienen éxito. El tamaño de la prueba y el costo de verificación son O(log n), mientras que el protocolo debe autenticar la raíz, el tamaño del árbol y el orden de la ruta.

Errores comunes

Elegir la dirección solo a partir de la paridad del índice e ignorar el límite del árbol variable fn == sn.
Usar un solo prefijo de hash para hojas y nodos interiores, perdiendo la separación de dominios.
Comparar solo la raíz reconstruida sin verificar los límites de las hojas, la longitud de la ruta o la convergencia de sn.
Tratar la raíz de una respuesta no confiable como un ancla de autenticación.
Construir con una convención de árbol y verificar con una regla de árbol binario completo diferente.
Omitir el orden de la ruta, el orden de bytes del hash o la canonicalización de hojas del contrato versionado.

Preguntas de seguimiento

¿Cómo verificarías una prueba de consistencia append-only?

Una prueba de inclusión responde si una hoja pertenece a una raíz. Una prueba de consistencia reconstruye tanto una raíz antigua como una nueva y demuestra que el árbol antiguo es un prefijo del nuevo. Las entradas incluyen tamaños antiguo y nuevo, una ruta y ambas raíces de confianza. Sus transiciones de estado difieren, por lo que no debe ocultarse dentro de una función de inclusión únicamente booleana.

¿Por qué transmitir tree_size en lugar de solo la ruta?

En un árbol de tamaño variable, el último nodo puede no tener hermano derecho en su nivel. La dirección depende del límite del subárbol actual. tree_size le dice al verificador qué nodos existen y evita que se introduzcan hashes adicionales en una ruta de raíz falsa.

¿Cómo evitas el downgrade del algoritmo de hash?

Versiona el identificador del algoritmo, la longitud de salida, los prefijos de hoja/interior y la canonicalización. Acepta solo una lista de permitidos y rechaza algoritmos desconocidos o débiles. Una migración crea un nuevo espacio de nombres de raíz; los resúmenes de diferentes algoritmos no deben compartir un mismo árbol.

¿Cómo afectan las hojas duplicadas a la prueba?

Una prueba de inclusión vincula bytes a una posición; no prueba que el valor aparezca solo una vez. La unicidad requiere un índice de claves separado o una prueba de conjunto. Una única raíz de Merkle no puede probar la no existencia de otro valor igual.

¿Cómo puede un generador ser incremental sin almacenar todo el árbol?

Mantén el resumen de subárbol derecho más reciente en cada nivel como acumulador de prefijo y fusiona una nueva hoja como la propagación de acarreo binario. Probar una hoja antigua todavía requiere retener los hermanos necesarios o un almacén externo; la raíz por sí sola no puede recrear una ruta.

¿Cómo debe manejar el verificador una ruta sobredimensionada?

Calcula un límite a partir del tamaño del árbol y la longitud del hash antes de analizar, rechaza rutas más largas y verifica la longitud fija de cada elemento para evitar desbordamiento por multiplicación. Agota el presupuesto de recursos antes de calcular hashes para que una prueba malformada no pueda desencadenar un bucle infinito o una asignación de memoria grande.