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

Le papier présente V3DB, un service de recherche vectorielle vérifiable qui permet aux clients de demander des preuves à connaissance nulle garantissant l'exactitude des résultats de recherche sur des instantanés de données engagés, sans révéler le corpus ni l'index privé, tout en assurant des temps de preuve et de vérification efficaces grâce à une optimisation de la pipeline IVF-PQ.

L'essentiel

Imaginez que vous demandez à un libraire très puissant de vous trouver les 10 livres les plus pertinents sur un sujet précis dans une bibliothèque de plusieurs millions d'ouvrages. Vous recevez une liste, mais vous n'avez aucun moyen de savoir si le libraire a vraiment cherché dans toute la bibliothèque, s'il a triché pour mettre en avant ses amis auteurs, ou s'il vous a donné une liste vieille de dix ans.

C'est exactement le problème que résout V3DB.

Voici une explication simple de ce système, imagée pour tout le monde.

1. Le Problème : Le Libraire Mystérieux

Dans le monde numérique actuel, les moteurs de recherche utilisent des "vecteurs" (des empreintes digitales mathématiques des textes) pour trouver des informations. Souvent, ce travail est fait par un serveur distant (le "libraire").

• Le souci : Vous ne voyez que le résultat final. Si le libraire triche (en sautant des étapes, en utilisant une vieille liste, ou en favorisant certains résultats), vous ne pouvez pas le prouver sans tout vérifier vous-même, ce qui prendrait des siècles.
• Le dilemme : Pour prouver qu'il n'a pas triché, le libraire devrait vous montrer toute sa bibliothèque et ses classements secrets. Mais cette bibliothèque est souvent un secret commercial ou contient des données privées.

2. La Solution V3DB : Le "Certificat Magique"

V3DB est un système qui permet au libraire de vous donner un certificat mathématique (une preuve à divulgation nulle de connaissance, ou Zero-Knowledge Proof).

Imaginez que le libraire vous remet un petit ticket scellé. Ce ticket vous dit : "Je vous jure sur mon âme que cette liste de 10 livres est exactement le résultat d'une recherche précise dans cette bibliothèque spécifique, sans que vous ayez besoin de voir les livres ni de refaire la recherche."

Ce qui est génial avec ce ticket :

• Il est court et rapide à vérifier (quelques millisecondes).
• Il ne révèle aucun secret (vous ne voyez pas les autres livres, ni comment il a trié).
• Il est impossible à falsifier.

3. Comment ça marche ? (L'Analogie du "Moule à Gâteau")

Pour que ce certificat fonctionne, le système doit être très rigide. C'est là que V3DB innove avec deux idées clés :

A. Le Moule à Gâteau (Index Shaping)

Normalement, les bibliothèques sont désordonnées. Certaines étagères sont pleines, d'autres vides. Pour faire un certificat mathématique, il faut que tout soit parfaitement carré.

• L'astuce : V3DB prend la bibliothèque et la "reformate" dans un moule rigide. Il force chaque étagère à avoir exactement le même nombre de places, même si certaines sont vides (remplies de "paille" ou de faux livres marqués comme invalides).
• Pourquoi ? Cela permet de faire le calcul de la recherche de la même façon à chaque fois, comme suivre une recette de cuisine étape par étape, sans jamais devoir dire "si l'étagère est pleine, fais ceci, sinon fais cela". Cela rend la vérification mathématique beaucoup plus rapide.

B. La Preuve par "Sacs de Perles" (Multiset Equality)

C'est la partie la plus intelligente pour éviter les calculs lents.

• L'ancien problème : Pour prouver qu'il a bien choisi les 10 meilleurs livres, le libraire devrait, en théorie, comparer chaque livre à chaque autre livre dans la liste. C'est comme essayer de trouver la perle la plus brillante dans un sac en comparant chaque perle à toutes les autres une par une. C'est trop long.
• La solution V3DB : Au lieu de comparer tout, le libraire vous donne deux sacs de perles.
  1. Le premier sac contient les perles (les livres) dans l'ordre où il les a trouvées.
  2. Le deuxième sac contient les mêmes perles, mais triées par brillance.
• Le tour de magie : Le système vérifie simplement que les deux sacs contiennent exactement les mêmes perles (même si l'ordre est différent) et que les perles du haut du sac trié sont bien les plus brillantes.
• Le résultat : Au lieu de faire des milliers de comparaisons complexes, le système fait une vérification rapide de "cohérence". C'est comme vérifier qu'un jeu de cartes est complet sans avoir à trier les cartes une par une.

4. Les Résultats Concrets

Grâce à cette méthode, V3DB a réussi à :

• Rendre la preuve 22 fois plus rapide que les méthodes précédentes (qui essayaient de tout calculer à la main).
• Réduire la mémoire nécessaire de 40 %.
• Garantir la confidentialité : Le libraire prouve qu'il a bien travaillé sans jamais vous montrer ses données sensibles.

En Résumé

V3DB est comme un notaire numérique pour les recherches intelligentes. Il permet à un service de vous prouver qu'il a fait son travail correctement, en utilisant une bibliothèque secrète, sans jamais vous obliger à voir cette bibliothèque ou à refaire le travail vous-même. C'est la garantie que le résultat que vous obtenez est honnête, à l'heure actuelle, et basé sur les règles convenues, le tout en quelques millisecondes.

Résumé technique

Voici un résumé technique détaillé du papier V3DB en français, structuré selon les sections demandées.

1. Problème et Contexte

Les services de recherche par vecteurs denses (dense retrieval) sont devenus la pierre angulaire de nombreuses applications modernes telles que la recherche sémantique, les systèmes de recommandation et la génération augmentée par récupération (RAG). Cependant, dans la plupart des déploiements actuels, le client ne reçoit qu'une liste des $k$ meilleurs résultats ($top-k$) sans aucune preuve auditable de la manière dont ces résultats ont été générés.

Cela crée un fossé de responsabilité :

• Un fournisseur de service non fiable pourrait réduire le budget de recherche, sauter des étapes coûteuses, réutiliser des snapshots obsolètes ou introduire des biais de classement pour des raisons commerciales.
• Le client ne peut pas vérifier si le service a exécuté l'algorithme promis sur la version de données (snapshot) déclarée.
• Les solutions existantes basées sur des environnements d'exécution de confiance (TEE) transfèrent la confiance vers le matériel et les fournisseurs, tandis que les méthodes cryptographiques traditionnelles (objets de vérification) révèlent souvent des métadonnées sensibles sur l'accès aux données.

Le défi principal est de permettre à un client de demander une vérification à la demande (audit-on-demand) d'un résultat de recherche, en obtenant une preuve succincte que le résultat est correct par rapport à un index et un corpus spécifiques, sans révéler le contenu du corpus, les embeddings ou la structure de l'index (qui sont souvent propriétaires ou sensibles).

2. Méthodologie : V3DB

V3DB est un service de recherche vectorielle versionné et vérifiable qui utilise des Preuves à Connaissance Nulle Succinctes (ZK-SNARKs) pour garantir l'intégrité des requêtes Approximate Nearest Neighbour (ANN).

A. Standardisation de la Pipeline IVF-PQ

Pour rendre la preuve réalisable dans un circuit arithmétique (qui nécessite une forme fixe et un contrôle de flux statique), V3DB standardise l'indexation IVF-PQ (Inverted File with Product Quantization) en une procédure de requête fixe en cinq étapes :

1. Calcul des distances aux centroïdes.
2. Sélection des listes à sonder (probe selection).
3. Construction des tables de recherche ADC (Asymmetric Distance Computation).
4. Calcul des distances des candidats via les tables ADC.
5. Sélection finale du top-k.

B. Façonnage de l'Index (Index Shaping)

Les index IVF-PQ classiques ont des listes inversées de longueurs variables, ce qui est inefficace pour les circuits ZK. V3DB introduit une étape de rééquilibrage et de remplissage (padding) :

• L'opérateur impose une capacité maximale fixe $n$ par liste.
• Les points sont rééquilibrés pour respecter cette limite.
• Les listes sont remplis jusqu'à $n$ slots avec des drapeaux de validité.
• Cela transforme l'index en une structure de forme fixe, éliminant les accès mémoire dynamiques et les boucles dépendantes des données.

C. Engagement de Snapshot Versionné

Le fournisseur publie un engagement public (commitment) com pour chaque version de l'index. Cet engagement est composé de :

• La racine d'un arbre de Merkle (rootmk) couvrant la structure IVF (centroïdes et listes inversées remplis).
• Un hachage (rootcb) couvrant les codebooks de quantification produit (PQ).
• Cela permet de lier la preuve à une version spécifique de l'index sans révéler son contenu.

D. Backend de Preuve Optimisé (Multiset-based)

C'est l'innovation clé de V3DB. Au lieu d'encoder directement les opérations coûteuses (tri, sélection, accès aléatoire) dans le circuit, V3DB utilise une approche hybride :

• Hors-circuit : Le prouveur exécute la pipeline IVF-PQ standard pour générer les séquences triées et les valeurs intermédiaires.
• Dans-circuit : Le circuit vérifie la cohérence de ces données fournies par le prouveur en utilisant des relations d'égalité et d'inclusion de multisets (multiset equality/inclusion) combinées à des vérifications de bornes légères.
  • Cela évite les réseaux de comparaison coûteux (comme les algorithmes de tri complets dans le circuit) et les accès aléatoires directs aux tables.
  • Le circuit prouve que les données fournies sont bien un sous-ensemble ou une permutation des données calculées, sans révéler l'ordre exact ou les valeurs privées.

3. Contributions Clés

1. Système V3DB et Instantiation IVF-PQ : Présentation d'un système complet pour la recherche dense vérifiable sur des snapshots engagés. Standardisation d'une sémantique de requête IVF-PQ à forme fixe en cinq étapes, rendue possible par un pipeline de façonnage d'index compatible ZK.
2. Backend de Preuve Efficace : Remplacement des encodages de circuits "bruts" (coûteux) par des vérifications de multisets et des conditions aux limites. Cela réduit considérablement la complexité du circuit en évitant le tri et l'accès aléatoire en circuit.
3. Implémentation et Évaluation : Mise en œuvre d'un prototype basé sur Plonky2 démontrant la faisabilité pratique. Le système propose une procédure de sélection de configuration basée sur le coût (gate count) pour optimiser les paramètres (nombre de listes, taille du codebook) en fonction des contraintes de preuve.

4. Résultats Expérimentaux

Les expériences ont été menées sur des jeux de données réels (SIFT1M, GIST1M, MS MARCO) avec des configurations variées.

• Utilité de la Recherche (RQ1) : Le prétraitement compatible ZK (encodage fixe, rééquilibrage) préserve presque totalement l'utilité de la recherche. Les métriques de rappel (Recall@1, Recall@100) et de classement (NDCG, MRR) sont très proches de la pipeline IVF-PQ flottante standard (différences de l'ordre de $10^{-3}$à$10^{-2}$).
• Coût de Preuve (RQ2) : L'approche basée sur les multisets surpasse massivement la baseline "circuit-only" :
  • Vitesse de preuve : Jusqu'à 22 fois plus rapide pour les grandes configurations.
  • Mémoire : Réduction de 40 % de la consommation mémoire de pointe (peak memory).
  • Vérification : Le temps de vérification reste de l'ordre de la milliseconde.
  • Note : Pour les configurations très petites, la baseline peut être plus rapide, mais pour des cas d'usage réalistes, l'optimisation est cruciale.
• Échelle et Configuration (RQ3) :
  • La taille du circuit croît de manière quasi-linéaire avec le nombre de listes ($n_{list}$) sous un budget de scan fixe.
  • Le temps de preuve suit le comportement "en escalier" typique des preuves ZK, dicté par la taille du domaine d'évaluation (puissance de 2).
  • L'algorithme de sélection de configuration (Algorithm 2) permet de trouver des configurations optimales (zk-opt) qui minimisent le coût de preuve tout en préservant l'efficacité de la recherche.

5. Signification et Impact

V3DB comble un fossé critique entre la nécessité de confidentialité/propriété des données et la demande croissante de transparence et d'auditabilité dans les services de recherche IA.

• Confiance sans confiance : Il permet aux clients de vérifier l'intégrité des résultats sans avoir à faire confiance au fournisseur ni à télécharger l'ensemble des données.
• Protection de la propriété intellectuelle : Contrairement aux méthodes précédentes qui pourraient révéler des métadonnées d'accès, V3DB cache le contenu de l'index et les embeddings, protégeant ainsi les bases de données propriétaires (ex: archives payantes, profils utilisateurs).
• Faisabilité pratique : En réduisant drastiquement le coût de génération de preuves (de plusieurs minutes/heures à quelques secondes pour de grands ensembles de données), V3DB rend l'audit "à la demande" économiquement viable pour des applications réelles, ouvrant la voie à des marchés de données vérifiables et à des systèmes RAG plus fiables.

En résumé, V3DB démontre que la vérification cryptographique de la recherche vectorielle à grande échelle est non seulement théoriquement possible, mais aussi pratiquement réalisable avec des performances acceptables.