V3DB: Audit-on-Demand Zero-Knowledge Proofs for Verifiable Vector Search over Committed Snapshots

V3DB es un servicio de búsqueda vectorial verificado que permite a los clientes auditar la corrección de los resultados de búsqueda aproximada sobre instantáneas comprometidas mediante pruebas de conocimiento cero, garantizando la integridad del proceso sin revelar los datos privados del índice.

Lo esencial

Imagina que tienes un bibliotecario muy inteligente (llamémosle "El Servicio") que tiene acceso a una biblioteca secreta y gigantesca llena de millones de libros. Tú le haces una pregunta, y él te devuelve una lista de los 10 libros que cree que más te van a gustar.

El problema es que no confías plenamente en el bibliotecario. Podría estar:

1. Ignorando libros nuevos para mostrarte solo los viejos.
2. Dándote libros que le pagan por recomendarte (sesgo).
3. Simplemente inventando la lista sin buscar realmente.

Normalmente, para verificar que hizo bien su trabajo, tendrías que descargar toda la biblioteca (imposible) o dejar que él te muestre sus notas privadas (lo cual es peligroso si la biblioteca es secreta o sensible).

V3DB es la solución mágica que proponen los autores. Es como un sistema de "Auditoría bajo demanda" que permite al bibliotecario probar que hizo el trabajo correctamente, sin revelar ni un solo libro de la biblioteca ni sus notas privadas.

Aquí te explico cómo funciona con analogías sencillas:

1. El Truco de la "Caja Sellada" (Compromiso de la Instantánea)

Antes de empezar, el bibliotecario toma una "foto" de su biblioteca en un momento específico y la mete en una caja de seguridad digital (una snapshot). Sella la caja y te da una huella digital única (un commitment).

• La promesa: "Te juro que voy a buscar en esta caja sellada. Si intento cambiar los libros dentro de la caja, la huella digital cambiará y todos se darán cuenta".

2. La Búsqueda Estandarizada (El Camino Fijo)

Para que la auditoría sea posible, el bibliotecario no puede buscar a su libre albedrío. Debe seguir un camino de 5 pasos predefinido y rígido (como una receta de cocina exacta).

• En lugar de buscar "lo que parezca más cercano", sigue reglas estrictas: "Mira los grupos A, B y C, calcula distancias, y elige los 10 mejores".
• Esto es como si el bibliotecario tuviera que seguir un mapa de tesoro que tú le diste, en lugar de caminar por el bosque a su antojo.

3. El "Prueba Mágica" (Zero-Knowledge Proofs)

Aquí viene la parte más genial. Cuando tú le pides: "¡Muéstrame que realmente buscaste en la caja y no inventaste la lista!", el bibliotecario no te muestra los libros ni la caja.

En su lugar, te entrega un papel sellado con un código matemático (una prueba de conocimiento cero).

• La analogía: Imagina que tienes un laberinto gigante. El bibliotecario te dice: "Te voy a demostrar que encontré la salida sin mostrarte el mapa ni los muros".
• Para hacerlo, usa un truco matemático llamado comprobación de multiconjuntos. En lugar de ordenar y comparar cada libro uno por uno (lo cual es lento y costoso de probar), agrupa los libros en "bolsas" y demuestra matemáticamente que:
  1. La bolsa de libros que usó para buscar es exactamente la misma que la que estaba en la caja sellada (aunque no veas los libros).
  2. La lista final que te dio es exactamente la misma que saldría si siguieras la receta de 5 pasos con esos libros.

4. ¿Por qué es tan rápido? (El problema de la "Ordenación")

El mayor desafío era que ordenar millones de libros es muy lento para las matemáticas de la prueba.

• El problema: Imagina tener que ordenar 1 millón de cartas en una mesa para demostrar que las elegiste bien. Eso tardaría horas.
• La solución de V3DB: En lugar de ordenarlas una por una frente a ti, el bibliotecario las pone en una pila desordenada y te demuestra con un truco de magia matemática que, si las ordenaras, serían las correctas. Esto reduce el tiempo de prueba de horas a milisegundos.

En Resumen: ¿Qué gana cada uno?

• Tú (El Cliente): Obtienes una garantía matemática de que el bibliotecario no te mintió ni manipuló los resultados, sin tener que descargar terabytes de datos ni revelar tus secretos.
• El Bibliotecario (El Proveedor): Puede seguir manteniendo su biblioteca secreta y sus algoritmos privados, pero gana tu confianza demostrando su honestidad de forma eficiente.
• El Auditor: Puede verificar la lista en menos de un segundo.

V3DB es, en esencia, un sistema que permite decir: "Confía en mí, pero no tienes que confiar en mí; puedes verificarlo tú mismo con una prueba matemática que no revela mis secretos". Es como tener un testigo invisible que asegura que el juego es limpio, sin necesidad de que nadie mire las cartas de los otros jugadores.

Resumen técnico

Resumen Técnico: V3DB

1. El Problema

Los servicios de recuperación densa (búsqueda semántica, recomendaciones, RAG) dependen cada vez más de la búsqueda de vecinos más cercanos aproximados (ANN) sobre grandes corpora de vectores. Sin embargo, existe una brecha fundamental de responsabilidad:

• Los clientes reciben solo una lista de resultados top-k sin evidencia auditable de cómo se generó.
• Un proveedor de servicios no confiable podría reducir el presupuesto de búsqueda, saltar pasos costosos, usar una instantánea (snapshot) desactualizada o introducir sesgos en la clasificación sin que el cliente lo detecte.
• Las soluciones existentes basadas en índices autenticados a menudo revelan metadatos dependientes del acceso (patrones de consulta), lo cual es indeseable cuando los índices o los datos son propietarios o sensibles.
• Las pruebas de conocimiento cero (ZK) tradicionales son demasiado costosas para la búsqueda de vectores debido a la necesidad de realizar operaciones de ordenamiento (sorting) y acceso aleatorio dentro del circuito, lo que genera circuitos inmanejablemente grandes.

La pregunta clave: ¿Puede un servicio de recuperación demostrar, mediante un certificado corto y verificable, que sus resultados son el resultado exacto de una semántica de consulta pública sobre una instantánea comprometida, sin revelar el corpus de vectores ni el contenido del índice privado?

2. Metodología

El sistema V3DB aborda este problema combinando una arquitectura de base de datos versionada con pruebas de conocimiento cero (ZK) optimizadas.

A. Semántica de Consulta Estandarizada (IVF-PQ de Forma Fija)
Para hacer viable la generación de pruebas, V3DB estandariza el pipeline de búsqueda IVF-PQ (Inverted File Index con Cuantización de Producto) en una semántica de cinco pasos de forma fija:

1. Distancias a centroides: Calcular distancias entre la consulta y todos los centroides.
2. Selección de sondas: Seleccionar las listas invertidas más cercanas.
3. Tablas de búsqueda ADC: Construir tablas de distancia asimétrica.
4. Distancias de candidatos: Calcular distancias aproximadas usando códigos PQ.
5. Selección final Top-k: Extraer los mejores resultados.

B. Moldeado del Índice (Index Shaping)
Para evitar el flujo de control dependiente de datos (que es costoso en ZK), V3DB transforma la base de datos original en una instantánea de forma fija:

• Reequilibrio: Se redistribuyen los vectores para que cada lista invertida tenga un número máximo de registros ($n$).
• Relleno (Padding): Se rellenan las listas hasta la capacidad exacta $n$ con un indicador de validez. Esto elimina la necesidad de bucles dinámicos en el circuito.

C. Capa de Compromiso de Instantánea (Snapshot Commitment)
El proveedor publica un identificador público ($com$) que compromete la versión del índice. Este compromiso incluye:

• Una raíz de Merkle ($root_{mk}$) que cubre la disposición IVF (centroides y listas invertidas rellenas).
• Un hash ($root_{cb}$) de los libros de códigos de cuantización (PQ).

D. Backend de Pruebas Optimizado (Multiset-Based Design)
En lugar de codificar el ordenamiento y el acceso aleatorio directamente en el circuito (lo cual es ineficiente), V3DB utiliza un enfoque híbrido:

• Fuera del circuito: El proveedor ejecuta el pipeline completo y genera las secuencias ordenadas y las entradas seleccionadas de las tablas.
• Dentro del circuito: El circuito verifica la consistencia de estos datos mediante:
  • Igualdad de Multiconjuntos (Multiset Equality): Para probar que la lista ordenada es una permutación válida de los datos originales.
  • Inclusión de Multiconjuntos (Multiset Inclusion): Para verificar que las entradas de las tablas de búsqueda provienen de los libros de códigos correctos.
  • Condiciones de Límite: Comprobaciones ligeras para asegurar que los elementos seleccionados son realmente los mejores (top-k) o las sondas correctas.

Esto evita el costoso ordenamiento "in-circuit" y el acceso aleatorio, reduciendo drásticamente el tamaño del circuito.

3. Contribuciones Clave

1. Sistema V3DB y Estandarización IVF-PQ: Presentación de un servicio de recuperación vectorial versionado y verificable que normaliza el pipeline IVF-PQ en una semántica de cinco pasos de forma fija, habilitando la ejecución en circuitos a gran escala.
2. Backend de Pruebas Eficiente: Diseño que evita el ordenamiento y el acceso aleatorio dentro del circuito mediante el uso de verificaciones de igualdad/inclusión de multiconjuntos y condiciones de límite. Esto reduce la complejidad del circuito significativamente.
3. Implementación y Evaluación: Desarrollo de un prototipo en Plonky2 que demuestra la viabilidad práctica de las pruebas de auditoría bajo demanda. Se compara una línea base de "solo circuito" con el diseño optimizado basado en multiconjuntos.
4. Selección de Configuración Guiada por Costos: Propuesta de un procedimiento para seleccionar parámetros de IVF-PQ ($n_{list}$, $K$, etc.) que minimizan el costo de prueba (número de puertas) manteniendo la utilidad de la recuperación.

4. Resultados Experimentales

Los experimentos se realizaron en un servidor AMD EPYC utilizando el framework Plonky2.

• Rendimiento de Prueba (Proving Time):
  • El diseño basado en multiconjuntos es hasta 22 veces más rápido que la línea base de solo circuito en configuraciones grandes.
  • En configuraciones de tamaño medio, la mejora es de aproximadamente 3.6x.
• Consumo de Memoria:
  • Se reduce el consumo de memoria pico en hasta un 40%.
• Tiempo de Verificación:
  • La verificación de las pruebas se mantiene en el rango de milisegundos (menos de 15 ms incluso en configuraciones grandes).
• Utilidad de Recuperación:
  • El preprocesamiento "amigable con ZK" (codificación de punto fijo, reequilibrio y relleno) preserva la utilidad de la recuperación. Las métricas (Recall@1, Recall@100, NDCG) son casi idénticas a las de un pipeline IVF-PQ estándar en punto flotante, con diferencias del orden de $10^{-3}$a$10^{-2}$.
• Escalabilidad:
  • El tamaño del circuito escala casi linealmente con el número de listas invertidas ($n_{list}$) bajo un presupuesto de escaneo fijo.
  • El tiempo de prueba sigue un comportamiento de "escalones" de potencia de dos, determinado por el tamaño del dominio de evaluación relleno ($G_B$).

5. Significado e Impacto

V3DB cierra la brecha entre la privacidad/propiedad de los datos y la necesidad de auditoría en sistemas de recuperación de información modernos.

• Confianza sin Revelación: Permite a los clientes y terceros auditar la integridad de los resultados de búsqueda sin obligar al proveedor a revelar su corpus de datos, sus índices privados o sus patrones de acceso.
• Viabilidad Práctica: Demuestra que las pruebas ZK para tareas complejas como la búsqueda de vectores (ANN) son factibles en la práctica, superando los cuellos de botella tradicionales de ordenamiento y acceso aleatorio.
• Aplicaciones Críticas: Es especialmente relevante para dominios de alto valor como patentes, finanzas y legales, donde la manipulación de resultados o el uso de datos desactualizados puede tener consecuencias graves, y donde los datos subyacentes suelen ser sensibles o propietarios.
• Modelo de Amenaza: Ofrece una garantía criptográfica contra un operador malicioso que podría desviar el flujo de trabajo o equivocar versiones, algo que las soluciones basadas en TEE (Entornos de Ejecución de Confianza) no garantizan sin depender de la confianza en el hardware.

En resumen, V3DB establece un nuevo estándar para la recuperación vectorial verificable, permitiendo auditorías bajo demanda eficientes y privadas sobre bases de datos vectoriales comprometidas.