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

Each language version is independently generated for its own context, not a direct translation.

Immagina di andare in una biblioteca enorme e privata, gestita da un bibliotecario di cui non ti fidi ciecamente. Chiedi: "Dammi i 10 libri più simili a questo argomento". Il bibliotecario ti passa una lista di 10 libri. Ma come fai a sapere che:

Ha davvero cercato in tutti i libri giusti?
Non ha scelto quelli solo perché gli piacevano o perché erano sponsorizzati?
Non sta usando una lista di libri vecchia di dieci anni invece di quella aggiornata di oggi?

Di solito, non puoi saperlo. Devi fidarti. V3DB è la soluzione a questo problema. È un sistema che permette di verificare la correttezza della ricerca senza dover guardare dentro la biblioteca (che potrebbe contenere segreti o dati sensibili).

Ecco come funziona, spiegato con delle metafore semplici:

1. Il Problema: La "Scatola Nera"

Oggi, quando usi motori di ricerca intelligenti o sistemi di raccomandazione (come quelli che usano l'intelligenza artificiale), il server fa un lavoro complesso: scansiona milioni di documenti, calcola distanze matematiche e sceglie i migliori.
Il problema è che il server è come una scatola nera. Tu vedi solo l'uscita (la lista di risultati), ma non sai cosa è successo dentro. Il server potrebbe essere pigro, truccare i risultati o usare dati vecchi. Se lo contesti, non ha modo di provare che ha lavorato onestamente senza rivelare i suoi segreti (i suoi dati interni).

2. La Soluzione: V3DB (Il "Fotografo Magico")

V3DB è come un sistema che prende una fotografia istantanea e sigillata di tutta la biblioteca in un dato momento.

L'Impronta Digitale (Commitment): Prima di iniziare, il bibliotecario crea un "sigillo digitale" (una sorta di impronta digitale matematica) di tutti i libri e dell'ordine in cui sono sistemati. Questo sigillo è pubblico. Chiunque può vederlo, ma non può vedere i libri dentro.
La Ricerca: Quando chiedi i tuoi 10 libri, il bibliotecario esegue la ricerca.
La Sfida (Audit-on-Demand): Se hai un dubbio, puoi dire: "Dimmi che hai fatto davvero il lavoro!". Il bibliotecario non ti mostra i libri, ma ti consegna un biglietto magico (una prova crittografica).

3. Il "Biglietto Magico" (Le Prove a Conoscenza Zero)

Questo biglietto è una prova a conoscenza zero. È come se il bibliotecario ti dicesse:

"Guarda questo biglietto. Contiene una serie di numeri magici che dimostrano matematicamente che ho seguito esattamente le regole che abbiamo stabilito, ho usato la fotografia del momento giusto e ho scelto i 10 libri migliori. Non ti mostro i libri, ma la matematica del biglietto è inconfutabile: se i libri scelti fossero sbagliati, il biglietto non esisterebbe."

Tu controlli il biglietto in un millisecondo e sei sicuro al 100% che il lavoro è stato fatto bene, senza che il bibliotecario ti abbia mai mostrato i suoi dati privati.

4. Il Trucco: Come è possibile farlo velocemente?

Fare queste prove matematiche è solitamente lentissimo e costoso, come cercare di ricostruire un puzzle di un milione di pezzi mentre qualcuno ti guarda.
Gli autori di V3DB hanno trovato un trucco geniale: hanno semplificato il puzzle prima di iniziare.

Il Ristrutturatore (Index Shaping): Immagina che i libri nella biblioteca siano disposti in modo disordinato: alcuni scaffali sono pieni zeppi, altri vuoti. Questo rende difficile fare i calcoli. V3DB prende la biblioteca e la riorganizza in modo perfetto: ogni scaffale ha esattamente lo stesso numero di spazi (anche se alcuni sono vuoti e contrassegnati come "finti").
Il Controllo di Gruppo (Multiset Checks): Invece di controllare libro per libro (che richiederebbe un tempo infinito), il sistema usa un trucco statistico. Chiede al bibliotecario di dimostrare che "il gruppo di libri che hai scelto esiste davvero nella biblioteca" e che "non hai inventato nessun libro". È come se il bibliotecario ti dicesse: "Ecco i 10 libri. Se li metti in una scatola e li mescoli con quelli della biblioteca, combaciano perfettamente". Non serve guardare ogni singolo libro, basta verificare che il "gruppo" sia corretto.

5. I Risultati nella Vita Reale

Grazie a questo trucco, V3DB è diventato incredibilmente veloce:

È 22 volte più veloce nel creare la prova rispetto ai metodi precedenti.
Usa meno memoria (come se il computer non si surriscaldasse).
La verifica è istantanea (pochi millisecondi).

In Sintesi

V3DB è come un notaio digitale per la ricerca su internet.
Permette a un servizio di dire: "Credo che questi siano i migliori risultati per te", e a te di rispondere: "Fammi vedere la prova". Il servizio ti dà una prova matematica che dice: "Sì, ho fatto esattamente quello che dovevo fare, usando i dati giusti, e non ho barato". E tutto questo succede senza che tu debba scaricare l'intero database o che il servizio debba rivelare i suoi segreti commerciali.

È la garanzia che, anche in un mondo digitale dove non ci fidiamo ciecamente degli altri, possiamo comunque ottenere risposte oneste e verificabili.

Each language version is independently generated for its own context, not a direct translation.

Titolo

V3DB: Prove a Conoscenza Zero (ZK) su Richiesta per la Ricerca Vettoriale Verificabile su Snapshot Impegnati

1. Il Problema

I servizi di recupero denso (dense retrieval), fondamentali per la ricerca semantica, i sistemi di raccomandazione e la generazione aumentata dal recupero (RAG), operano spesso tramite fornitori di servizi remoti non fidati. In questi scenari:

Mancanza di Accountability: I client ricevono solo una lista dei primi k risultati (top-k) senza alcuna prova verificabile di come tale lista sia stata generata.
Rischi di Manipolazione: Un provider potrebbe ridurre il budget di ricerca, saltare passaggi costosi, riutilizzare snapshot obsoleti o introdurre bias di ranking per scopi commerciali, senza che il client possa rilevarlo dalla sola lista finale.
Dilemma Privacy vs. Verifica: Per "provare la propria innocenza", un provider non può rivelare il corpus dei dati, gli embedding o la struttura dell'indice, poiché questi sono spesso proprietari, sensibili o soggetti a licenza.
Limiti delle Soluzioni Esistenti: Gli approcci basati su ambienti di esecuzione fidati (TEE) spostano la fiducia sull'hardware e richiedono esecuzione protetta continua. Le soluzioni crittografiche basate su oggetti di verifica (VO) tradizionali tendono a rivelare metadati dipendenti dall'accesso, violando la privacy.

L'obiettivo è fornire un meccanismo di audit "su richiesta" (audit-on-demand) che garantisca l'integrità del risultato di ricerca su uno snapshot specifico e impegnato, senza rivelare i dati sottostanti.

2. Metodologia: V3DB

V3DB è un servizio di ricerca vettoriale versionato e verificabile che utilizza Prove a Conoscenza Zero Succinte (ZK-SNARKs). Il sistema si basa su tre pilastri principali:

A. Formattazione dell'Indice (Index Shaping)

Per rendere la ricerca compatibile con i circuiti ZK (che richiedono esecuzioni a forma fissa), V3DB trasforma l'indice IVF-PQ (Inverted File with Product Quantization) standard in una struttura a forma fissa:

Rebilanciamento e Padding: L'indice viene ridistribuito per garantire che ogni lista invertita abbia esattamente lo stesso numero di slot ( $n$ ). Gli slot vuoti vengono riempiti con flag di validità.
Semantica a 5 Passi: La query viene standardizzata in una sequenza fissa di cinque passaggi:
1. Calcolo delle distanze dai centroidi.
2. Selezione delle $n_{probe}$ liste più vicine.
3. Costruzione delle tabelle di ricerca (ADC Lookup Tables).
4. Calcolo delle distanze dei candidati tramite tabelle PQ.
5. Selezione finale dei top-k.

B. Livello di Commitment Versionato

Il provider pubblica un identificatore pubblico (com) che impegna (commits) una specifica versione dell'indice:

Un albero di Merkle radice (rootmk) che impegna la struttura IVF (centroidi e liste invertite).
Un hash (rootcb) che impegna i codebook di quantizzazione (PQ).
Questo permette di verificare che la prova sia stata generata su una specifica versione dei dati senza rivelarne il contenuto.

C. Backend di Prova Ottimizzato (Multiset-Based)

La sfida principale è l'efficienza dei circuiti ZK. Un'implementazione "circuit-only" diretta richiederebbe operazioni di ordinamento (sorting) e accesso casuale (random access) all'interno del circuito, risultando proibitivo.
V3DB introduce un'ottimizzazione chiave:

Evitare l'ordinamento in-circuit: Invece di ordinare i dati dentro il circuito, il prover esegue l'ordinamento fuori dal circuito e fornisce le sequenze ordinate come "witness" (testimonianza).
Verifica tramite Relazioni di Multiset: Il circuito verifica la correttezza di queste sequenze fornite utilizzando:
- Uguaglianza di Multiset (SetEq): Per provare che la lista ordinata contiene esattamente gli stessi elementi della lista originale (usando compressione polinomiale).
- Inclusione di Multiset (Incl): Per verificare che i valori selezionati dalle tabelle PQ provengano effettivamente dalle tabelle calcolate.
- Condizioni di Bordo: Controlli leggeri per garantire che i primi $k$ elementi siano effettivamente i migliori (es. $D_0 \le D_1 \le \dots$ ).

3. Contributi Chiave

Sistema V3DB: Prima implementazione di un database vettoriale verificabile su larga scala che supporta audit su richiesta per retrieval denso, proteggendo la privacy degli embedding e dell'indice.
Semantica IVF-PQ a Forma Fissa: Progettazione di un pipeline di query standardizzato in 5 passi, reso compatibile con i circuiti ZK tramite tecniche di rebilanciamento e padding.
Backend di Prova Efficiente: Sostituzione di costose operazioni di ordinamento e accesso casuale in-circuit con controlli di uguaglianza/inclusione di multiset, riducendo drasticamente la complessità del circuito.
Implementazione e Valutazione: Un prototipo basato su Plonky2 che dimostra la fattibilità pratica del sistema.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su dataset reali (SIFT1M, GIST1M, MS MARCO) confrontando il baseline "circuit-only" con l'approccio ottimizzato basato su multiset.

Velocità di Generazione della Prova: L'approccio ottimizzato è fino a 22 volte più veloce rispetto al baseline circuit-only (es. da ~527 secondi a ~24 secondi per configurazioni grandi).
Consumo di Memoria: Riduzione del picco di memoria fino al 40%.
Tempo di Verifica: La verifica rimane estremamente rapida, nell'ordine dei millisecondi.
Utilità del Recupero: Le tecniche di pre-processing (fixed-point encoding e rebilanciamento) hanno un impatto minimo sulle metriche di recupero (Recall@k, Hit@10), mantenendo prestazioni quasi identiche rispetto a un pipeline IVF-PQ standard in floating-point.
Scalabilità: La dimensione del circuito cresce quasi linearmente con il numero di liste invertite ( $n_{list}$ ) sotto un budget di scansione fisso, e il tempo di prova segue il comportamento "a gradini" tipico delle dimensioni di dominio raddrizzate (power-of-two).

5. Significato e Impatto

V3DB risolve il fondamentale compromesso tra privacy, integrità e efficienza nei servizi di ricerca vettoriale esterni:

Trustless Verification: Permette a clienti e auditor di terze parti di verificare che un risultato di ricerca sia corretto e derivi da uno snapshot specifico, senza dover scaricare i dati o fidarsi del fornitore.
Applicabilità Reale: Rende praticabile l'audit di sistemi critici in settori come finanza, legale e brevetti, dove la manipolazione dei risultati di ricerca può avere conseguenze gravi.
Ottimizzazione Crittografica: Dimostra come l'adattamento degli algoritmi di ricerca (IVF-PQ) alle restrizioni dei circuiti ZK (evitando branching e accesso casuale) possa portare a guadagni di prestazioni enormi, rendendo le prove ZK fattibili per carichi di lavoro complessi e su larga scala.

In sintesi, V3DB trasforma la ricerca vettoriale da un "black box" in un processo trasparente e verificabile, abilitando nuovi modelli di fiducia per l'IA generativa e i sistemi di raccomandazione.