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.

Stell dir vor, du suchst in einer riesigen Bibliothek nach einem bestimmten Buch, das am besten zu deiner Frage passt. Normalerweise gibt dir der Bibliothekar (der Server) einfach eine Liste mit den Top 5 Ergebnissen. Aber wie kannst du sicher sein, dass er wirklich die besten Bücher ausgewählt hat und nicht einfach ein paar alte oder unpassende Bücher herausgesucht hat, nur um Zeit zu sparen oder weil er dich beeinflussen will?

Das ist das Problem, das V3DB löst. Es ist wie ein magischer, unbestechlicher Bibliothekar, der dir nicht nur die Bücher gibt, sondern dir auch einen unsichtbaren, aber überprüfbaren Nachweis liefert, dass er die Regeln genau befolgt hat – ohne dir dabei zu verraten, welche anderen Bücher in der Bibliothek stehen.

Hier ist die Erklärung in einfachen Schritten:

1. Das Problem: Der "Vertrauens-Loch"

In der digitalen Welt nutzen viele Apps und KI-Systeme "Vektorsuche". Das ist wie eine Bibliothek, in der Bücher nicht nach Titel, sondern nach ihrer "Bedeutung" (ihrem Inhalt) sortiert sind.

Das Dilemma: Du fragst den Server: "Zeig mir die 10 besten Ergebnisse!" Der Server antwortet. Aber du hast keine Ahnung, ob er wirklich die wirklich besten 10 genommen hat oder ob er einfach die ersten 10 aus einem alten Stapel genommen hat, um schneller zu sein.
Das Risiko: Der Server könnte Ergebnisse manipulieren (z. B. nur positive Nachrichten über einen Sponsor zeigen) oder veraltete Daten nutzen.

2. Die Lösung: V3DB (Der "Audit-on-Demand"-Bibliothekar)

V3DB ist ein System, das dem Server erlaubt, zu beweisen: "Ich habe genau das getan, was du wolltest, basierend auf dem genauen Stand der Bibliothek, den wir vereinbart haben."

Es funktioniert in drei Hauptteilen:

A. Die Bibliothek neu ordnen (Index Shaping)

Stell dir vor, die Bücher in der Bibliothek sind in Regalen ungleichmäßig verteilt. Manche Regale sind vollgestopft, andere fast leer. Für einen Computer ist das schwer zu überprüfen.

Was V3DB macht: Es ordnet die Bibliothek vorher so um, dass jedes Regal exakt gleich viele Plätze hat. Wenn ein Regal zu voll ist, werden Bücher in leere Regale umgeschoben. Wenn ein Regal zu leer ist, werden leere Platzhalter (wie leere Kartons) eingefügt.
Warum? Damit der Computer (der "Beweis-Generator") immer das gleiche, vorhersehbare Muster durchlaufen kann, ohne sich in chaotischen Wegen zu verirren. Das macht den Beweis viel schneller.

B. Der Siegel-Vertrag (Versioned Snapshot)

Bevor der Server auch nur eine Frage beantwortet, drückt er einen "digitalen Stempel" auf den aktuellen Zustand der Bibliothek.

Die Analogie: Stell dir vor, der Bibliothekar macht ein Foto von allen Regalen und versiegelt es in einem Glas. Er gibt dir nur den Fingerabdruck (den Hash) dieses Fotos.
Wenn du später eine Frage stellst, verspricht er dir: "Ich habe meine Antwort basierend auf diesem versiegelten Foto erstellt." Er muss dir nicht das ganze Foto zeigen (das wäre zu teuer und würde Geheimnisse verraten), aber er kann beweisen, dass er sich daran gehalten hat.

C. Der magische Beweis (Zero-Knowledge Proof)

Jetzt kommt das Magische. Wenn du skeptisch bist und sagst: "Beweise mir, dass du die besten 10 Bücher gewählt hast!", erstellt der Server einen mathematischen Beweis.

Das "Zero-Knowledge"-Wunder: Dieser Beweis ist wie ein Zaubertrick. Der Server sagt: "Ich habe die Regeln befolgt." Du kannst den Beweis prüfen und sofort sehen: "Okay, die Mathematik stimmt." Aber dabei erfährst du nichts darüber, welche anderen Bücher in den Regalen lagen oder wie genau der Server gerechnet hat. Es bleibt alles privat.
Der Trick: Normalerweise wäre es extrem schwer, zu beweisen, dass man die besten 10 aus 1 Million Büchern gewählt hat, ohne alles aufzulisten. V3DB nutzt einen cleveren Trick: Statt alles zu sortieren (was sehr langsam ist), prüft es, ob die gewählten Bücher eine korrekte Teilmenge sind und ob die Randbedingungen stimmen. Das ist wie wenn ein Lehrer nicht jede einzelne Matheaufgabe eines Schülers nachrechnet, sondern prüft, ob die Formeln stimmen und das Endergebnis logisch ist.

3. Warum ist das so schnell? (Der "Multiset"-Trick)

Frühere Systeme versuchten, den ganzen Sortierprozess im Beweis nachzubauen. Das war wie der Versuch, einen ganzen Marathon im Zeitraffer zu laufen – extrem langsam und energieaufwendig.

V3DB nutzt eine Methode namens Multiset-Prüfung:

Statt: "Sortiere alle 1 Million Bücher und zeige mir die Top 10."
Macht V3DB: "Hier ist die Liste der Top 10. Hier ist die Liste aller Bücher, die ich in Betracht gezogen habe. Prüfe nur, ob die Top 10 wirklich aus der großen Liste kommen und ob sie die kleinsten Entfernungen haben."
Das Ergebnis: Der Server ist bis zu 22-mal schneller beim Erstellen des Beweises als frühere Methoden, und der Beweis ist so klein, dass er in Millisekunden geprüft werden kann.

Zusammenfassung in einem Satz

V3DB ist wie ein unbestechlicher, magischer Bibliothekar, der dir garantiert, dass er die besten Ergebnisse für dich gefunden hat, indem er dir einen unsichtbaren, aber mathematisch wasserdichten Nachweis liefert, ohne dir dabei zu verraten, was in den anderen Regalen der Bibliothek steht.

Das ist besonders wichtig für sensible Bereiche wie Finanzen, Patente oder medizinische Daten, wo man wissen muss, dass die KI nicht manipuliert wurde, aber die Daten trotzdem geheim bleiben müssen.

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

Hier ist eine detaillierte technische Zusammenfassung des Papers „V3DB: Audit-on-Demand Zero-Knowledge Proofs for Verifiable Vector Search over Committed Snapshots" auf Deutsch:

1. Problemstellung

Dichte Retrieval-Dienste (Dense Retrieval) bilden die Grundlage für semantische Suche, Empfehlungssysteme und Retrieval-Augmented Generation (RAG). In der Praxis werden diese Dienste oft von externen Anbietern betrieben, die die Vektordatenbank und den Suchindex verwalten. Kunden erhalten lediglich eine Top-k-Liste mit Ergebnissen, ohne Beweise dafür, wie diese generiert wurden.

Dies führt zu einem fundamentalen Vertrauens- und Verantwortlichkeitsdefizit:

Ein Anbieter könnte den Suchbudget reduzieren, teure Schritte überspringen, veraltete Snapshots wiederverwenden oder Ranking-Voreingenommenheit einführen.
Bei einer Streitigkeit kann der Anbieter nicht effizient nachweisen, dass er die vereinbarte Suchlogik auf dem versprochenen Datensatz angewendet hat.
Eine Offenlegung des gesamten Korpus oder des Index zur Verifizierung ist oft aufgrund von Datenschutz, geistigem Eigentum oder Sensibilität der Daten (z. B. biometrische Daten, interne RAG-Daten) nicht akzeptabel.

Das Ziel ist es, eine Lösung zu finden, die Integrität (die Ergebnisse entsprechen der spezifizierten Logik) und Privatsphäre (Daten und Index bleiben verborgen) gleichzeitig gewährleistet, ohne dass der Client den gesamten Datensatz herunterladen muss.

2. Methodik: V3DB

V3DB ist ein verifizierbarer, versionierter Vektordienst, der Zero-Knowledge Proofs (ZK) nutzt, um die Korrektheit von Approximate Nearest Neighbor (ANN)-Suchen nachzuweisen.

Kernkomponenten:

Index-Shaping (Festlegung der Struktur):
- Herkömmliche IVF-PQ-Indizes (Inverted File Index mit Product Quantization) haben variable Listenlängen und Datenabhängigkeiten, die in ZK-Schaltkreisen (Circuits) extrem teuer sind.
- V3DB transformiert den Rohdatensatz in einen förmlich festgelegten (fixed-shape) IVF-PQ-Snapshot. Dies geschieht durch ein Rebalancing-Verfahren, das sicherstellt, dass jede invertierte Liste eine maximale Kapazität $n$ hat, gefolgt von Padding, um alle Listen auf genau $n$ Slots zu bringen. Jeder Slot erhält eine Gültigkeitsflagge.
Versionierte Snapshot-Commitment:
- Der Anbieter erstellt einen öffentlichen Commitment-Wert com für jeden Snapshot. Dieser besteht aus:
  - Einer Merkle-Root (rootmk), die die zentroidenbasierte IVF-Struktur und die gepaddeten Listen bindet.
  - Einem Hash-Digest (rootcb) der PQ-Codebooks.
- Dies ermöglicht die Bindung eines Beweises an eine spezifische Version des Index, ohne den Inhalt preiszugeben.
Standardisierte 5-Schritt-Semantik:
Die Suche wird in eine feste, fünfstufige Abfolge zerlegt, die sich für ZK-Beweise eignet:
1. Berechnung der Distanzen zu den Centroiden.
2. Auswahl der $n_{probe}$ nächsten Listen (Probe Selection).
3. Erstellen von ADC-Lookup-Tabellen (Asymmetric Distance Computation).
4. Berechnung der Kandidatendistanzen via PQ-Code-Lookups.
5. Extraktion der finalen Top-k-Ergebnisse.
Effizientes Proving-Backend (Der entscheidende Innovationsschritt):
Anstatt die gesamte Sortierung und den zufälligen Zugriff (Random Access) direkt im ZK-Schaltkreis zu kodieren (was zu riesigen Schaltkreisen führen würde), nutzt V3DB einen multiset-basierten Ansatz:
- Der Prover führt die Sortierung und Auswahl außerhalb des Schaltkreises durch.
- Im Schaltkreis werden nur Multiset-Gleichheits- und Inklusionsprüfungen (mittels Polynom-Identitäten) sowie leichte Randbedingungen (Boundary Checks) verifiziert.
- Dies beweist, dass die vom Prover gelieferte sortierte Liste und die ausgewählten Lookups konsistent mit den im Schaltkreis neu berechneten Basisdaten sind, ohne die Daten selbst offenzulegen.

3. Wichtige Beiträge

Systemarchitektur V3DB: Einführung eines verifizierbaren, versionierten Vektordatenbanksystems für dichte Retrieval-Aufgaben mit öffentlichen Commitments.
Standardisierung der IVF-PQ-Semantik: Entwicklung eines festen, fünfstufigen Suchprozesses, der durch Rebalancing und Padding für ZK-Schaltkreise optimiert ist.
Optimierter Proving-Backend: Ersetzung teurer in-circuit Sortier- und Selektionsoperationen durch effiziente Multiset-Relationen. Dies vermeidet die Notwendigkeit, komplexe Datenabhängigkeiten direkt im Circuit zu kodieren.
Implementierung und Evaluation: Vollständige Implementierung in Plonky2 mit detaillierten End-to-End-Evaluierungen, die zeigen, dass Audit-on-Demand unter realistischen Budgets praktikabel ist.

4. Ergebnisse

Die Autoren haben V3DB auf einer dedizierten Server-Hardware (AMD EPYC) evaluiert und folgende Ergebnisse erzielt:

Performance-Gewinn: Im Vergleich zu einem reinen „Circuit-Only"-Baseline-Ansatz (der Sortierung direkt im Circuit kodiert) erreicht die multiset-basierte V3DB-Implementierung:
- Bis zu 22-fach schnellere Beweisgenerierung (Proving Time).
- Bis zu 40 % geringeren Spitzen-Speicherbedarf (Peak Memory).
- Verifizierungszeiten im Millisekundenbereich.
Retrieval-Qualität: Die ZK-freundliche Vorverarbeitung (Fixed-Point-Encoding, Rebalancing) führt zu einem vernachlässigbaren Verlust bei der Suchqualität (Recall@k, NDCG). Die Metriken liegen nahe an denen von Standard-Float-Pipelines.
Konfigurationsoptimierung: Es wurde gezeigt, dass die Beweiszeit stark von der Größe des „padded evaluation domain" ( $G_B$ ) abhängt. Ein vorgeschlagener Tuning-Algorithmus (basierend auf Scan- und Code-Budgets) kann Konfigurationen finden, die die Beweiszeit minimieren, ohne die Suchgenauigkeit übermäßig zu beeinträchtigen.
Skalierbarkeit: Die Analyse zeigt eine nahezu lineare Skalierung der Schaltkreisgröße mit der Anzahl der invertierten Listen ( $n_{list}$ ) unter einem festen Scan-Budget.

5. Bedeutung und Ausblick

V3DB schließt eine kritische Lücke zwischen der Notwendigkeit von vertrauenswürdigen KI-Diensten und dem Schutz proprietärer Daten.

Vertrauenswürdigkeit: Es ermöglicht Kunden und Dritten, die Korrektheit von Suchergebnissen zu überprüfen, ohne den Anbieter zu vertrauen oder sensible Daten zu enthüllen.
Praktikabilität: Durch die drastische Reduzierung der Beweisgenerierungskosten macht V3DB Zero-Knowledge-Verifizierung für hochskalierte Vektorsuchdienste (wie sie in RAG-Systemen oder Patentdatenbanken verwendet werden) erstmals wirtschaftlich und technisch machbar.
Privatsphäre: Im Gegensatz zu Trusted Execution Environments (TEEs), die Hardware-Vertrauen erfordern, bietet V3DB eine rein kryptografische Lösung, die von jedem Verifizierer überprüft werden kann.

Zusammenfassend demonstriert V3DB, dass durch geschickte Systemdesigns (Index-Shaping) und kryptografische Optimierungen (Multiset-Checks) komplexe ANN-Suchvorgänge effizient und privat verifiziert werden können.