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.

Imagine que você está em uma biblioteca gigante e muito moderna, onde os livros não são organizados por título ou autor, mas pelo sentimento ou significado que eles transmitem. Você pede ao bibliotecário: "Me traga os 10 livros que mais parecem com a história de um herói que perdeu a memória".

O bibliotecário (o servidor) volta com uma lista de 10 livros. Mas aqui está o problema: como você sabe que ele realmente procurou nos livros certos?

Ele poderia ter:

Pego os livros que ele mais gosta, ignorando o que você pediu.
Usado uma lista antiga de livros que não existem mais na biblioteca.
Pulado etapas da busca para ser mais rápido, entregando resultados ruins.
Escondido que ele está usando um "livro secreto" patrocinado por uma empresa para aparecer no topo.

Normalmente, você só vê a lista final. Você não tem como auditar o processo. É como pedir um prato no restaurante e receber o prato, mas sem poder ver a cozinha ou a receita usada.

O que é o V3DB?

O V3DB é como um selo de garantia mágico e invisível para esse bibliotecário. Ele permite que você peça: "Prove que você realmente seguiu as regras exatas para encontrar esses 10 livros, sem me mostrar os livros secretos da biblioteca ou como você organizou as prateleiras".

Aqui está como funciona, usando analogias simples:

1. A "Foto Oficial" (Snapshot Commitment)

Antes de começar a buscar, o bibliotecário tira uma foto digital perfeita de toda a organização da biblioteca naquele momento. Ele coloca essa foto dentro de um cofre indestrutível e entrega a você apenas a chave do cofre (um código único).

Analogia: É como se ele selasse a prateleira com fita adesiva e um lacre oficial. Se ele tentar mudar um livro depois, o lacre quebra e a prova não funciona.

2. A "Receita Padronizada" (Fixed-Shape Semantics)

Para provar que fez o trabalho direito, o bibliotecário não pode inventar um método novo a cada vez. Ele deve seguir uma receita de bolo de 5 passos que todos conhecem e que é sempre a mesma, não importa quantos livros existam.

O Problema: Provar que você seguiu a receita é difícil se a cozinha for bagunçada e cheia de passos aleatórios.
A Solução do V3DB: Eles organizaram a biblioteca de uma forma especial (chamada de "Index Shaping") para que a receita seja sempre a mesma, com o mesmo número de passos, facilitando a prova.

3. O "Detetive Mágico" (Zero-Knowledge Proofs)

Aqui entra a mágica. Quando você questiona o resultado, o bibliotecário não precisa abrir o cofre nem mostrar os livros. Em vez disso, ele gera um certificado matemático curto (uma prova de conhecimento zero).

A Analogia: Imagine que o bibliotecário coloca a receita e os livros em uma máquina de fax mágica. A máquina não mostra o conteúdo, mas emite um bilhete que diz: "Eu garanto, com 100% de certeza matemática, que se você seguisse a receita oficial com os livros que estão no cofre, você chegaria exatamente a essa lista de 10 livros que eu te entreguei."
Você verifica o bilhete em milissegundos. Se estiver correto, você sabe que ele não trapaceou. Se ele tentou pular etapas, o bilhete não sai.

4. O Truque da "Caixa de Ferramentas" (Multiset Checks)

Fazer essa prova matemática é muito difícil e lento se o bibliotecário tiver que provar cada comparação de livro um por um (como ordenar uma pilha gigante de cartas na frente de você). Isso seria como tentar provar que você ordenou 1 milhão de cartas sem nunca mostrar a ordem, apenas fazendo contas complexas.

O V3DB usa um truque inteligente:

Em vez de provar a ordem exata passo a passo, ele prova que o conjunto de livros usados é o mesmo que deveria ter sido usado.
Analogia: Imagine que você tem uma caixa com 100 peças de Lego. Em vez de provar que você montou o castelo peça por peça, você prova que a caixa de peças que você usou é exatamente a mesma que a caixa original, e que as peças sobrando estão no lugar certo. Isso é muito mais rápido e fácil de verificar.

Por que isso é importante?

Confiança sem Espionagem: Você pode confiar que o resultado é honesto sem precisar baixar a biblioteca inteira (que pode ser privada, cara ou sensível).
Segurança para Negócios: Empresas que usam inteligência artificial para buscar patentes, dados financeiros ou históricos médicos podem provar que não estão manipulando os resultados para favorecer clientes ou esconder informações.
Velocidade: O sistema foi otimizado para ser rápido. O "bilhete" (a prova) é gerado em segundos e verificado em milissegundos, tornando o processo prático para o dia a dia.

Resumo em uma frase

O V3DB é um sistema que permite que um servidor prove que encontrou os melhores resultados para você, seguindo regras estritas e usando uma versão específica dos dados, sem nunca precisar mostrar os dados secretos ou como ele fez a busca, garantindo transparência total sem perda de privacidade.

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

Resumo Técnico: V3DB

1. O Problema

Os serviços de recuperação densa (dense retrieval), fundamentais para busca semântica, sistemas de recomendação e Geração Aumentada por Recuperação (RAG), operam frequentemente em ambientes onde o provedor de serviço é potencialmente não confiável.

Falta de Auditabilidade: Os clientes recebem apenas uma lista top-k de resultados sem evidências verificáveis de como essa lista foi gerada.
Riscos de Integridade: Um provedor malicioso pode reduzir o orçamento de busca, pular etapas caras, reutilizar snapshots desatualizados ou introduzir viés de classificação (ex: suprimir itens desfavoráveis) sem que o cliente perceba apenas olhando para o resultado final.
Dilema Privacidade vs. Verificação: Para provar a integridade, o provedor não pode simplesmente revelar o corpus de embeddings ou o índice, pois esses dados são frequentemente proprietários, licenciados ou sensíveis (ex: perfis de usuários, dados biométricos).
Limitações das Soluções Atuais: Abordagens baseadas em Ambientes de Execução Confiáveis (TEEs) transferem a confiança para o hardware e exigem execução protegida contínua. Abordagens criptográficas existentes (como Objetos de Verificação - VOs) muitas vezes revelam metadados dependentes do acesso, o que é indesejável.

2. Metodologia e Arquitetura

O V3DB propõe um serviço de busca vetorial versionado e verificável que utiliza Provas de Conhecimento Zero (ZK) para permitir verificações de correção sob demanda ("audit-on-demand") sem revelar os dados privados.

Componentes Principais:

Index Shaping (Moldagem do Índice):
- O sistema transforma um banco de dados vetorial bruto em um snapshot de forma fixa usando o índice IVF-PQ (Inverted File with Product Quantization).
- Para evitar loops dependentes de dados e acesso aleatório irregular (que são caros em circuitos ZK), o sistema aplica um processo de rebalanceamento e preenchimento (padding). Isso garante que cada lista invertida tenha exatamente $n$ slots, com flags de validade, criando uma estrutura de dados uniforme.
Camada de Snapshot Versionado:
- O provedor compromete cada versão do snapshot publicamente através de um identificador com (composto por raízes de Merkle para os índices e hashes para os codebooks de PQ). Isso permite vincular a prova a uma versão específica do índice sem revelar seu conteúdo.
Backend de Prova (Proving Backend):
- Dada uma consulta $q$ e um compromisso com, o serviço retorna a lista top-k.
- Se desafiado, o provedor gera uma prova ZK sucinta ( $\pi$ ) atestando que a lista retornada é exatamente o resultado da execução de uma semântica de consulta padronizada de cinco etapas sobre o snapshot comprometido.

Otimização Crítica: Design Baseado em Multiconjuntos
O maior desafio é que operações de ordenação (para seleção de listas e top-k) e acesso aleatório a tabelas (para pontuação PQ) são extremamente custosas em circuitos ZK.

Baseline (Circuito Único): Codificaria diretamente a ordenação e o acesso aleatório no circuito, resultando em um custo computacional proibitivo.
Abordagem V3DB (Multiset-Based): O provador executa o pipeline IVF-PQ fora do circuito para obter as sequências ordenadas e os valores selecionados. O circuito ZK, em vez de reordenar, verifica a consistência usando:
- Igualdade de Multiconjuntos (Multiset Equality): Para provar que a sequência ordenada contém os mesmos elementos que a original.
- Inclusão de Multiconjuntos (Multiset Inclusion): Para provar que os valores selecionados das tabelas de busca (LUT) pertencem às tabelas completas.
- Verificações de Fronteira Leves: Para garantir que as condições de ordenação parcial (ex: os $k$ primeiros são menores que os restantes) sejam atendidas.

Isso elimina a necessidade de redes de comparação complexas e acesso aleatório dentro do circuito, reduzindo drasticamente o número de portas lógicas (gates).

3. Contribuições Chave

Sistema V3DB e Instanciação IVF-PQ: Apresentação de um banco de dados vetorial verificável que padroniza a semântica de busca IVF-PQ em um formato de forma fixa, viabilizando a geração de provas em escala.
Backend de Prova Eficiente: Substituição de operações caras no circuito (ordenamento e acesso aleatório) por verificações de multiconjuntos e condições de fronteira, reduzindo a complexidade assintótica do circuito.
Implementação e Avaliação: Implementação em Plonky2 demonstrando que a geração de provas é prática sob orçamentos realistas, com tempos de verificação em milissegundos.
Seleção de Configuração Orientada a Custos: Proposição de um procedimento para selecionar parâmetros de configuração (como número de listas e tamanho do codebook) que minimizam o custo de prova (tamanho do domínio de avaliação) sem sacrificar excessivamente a utilidade da recuperação.

4. Resultados Experimentais

Os experimentos foram conduzidos em servidores AMD EPYC utilizando os conjuntos de dados SIFT1M, GIST1M e MS MARCO.

Desempenho de Prova:
- A abordagem baseada em multiconjuntos foi até 22 vezes mais rápida na geração de provas em comparação com a baseline de circuito único.
- Redução de até 40% no consumo de pico de memória.
- O tempo de verificação permaneceu na faixa de milissegundos (ex: ~10ms).
Utilidade de Recuperação:
- O pré-processamento "amigável a ZK" (codificação de ponto fixo e rebalanceamento) preservou a utilidade da recuperação. Métricas como Recall@1, Recall@100, Hit@10 e NDCG permaneceram muito próximas da baseline de ponto flutuante (diferenças na ordem de $10^{-3} $a$ 10^{-2}$).
Escalabilidade:
- O custo de prova escala quase linearmente com o número de listas invertidas ( $n_{list}$ ) sob um orçamento de varredura fixo.
- O tempo de prova exibe um comportamento de "degrau" (step behavior) governado pelo tamanho do domínio de avaliação (potências de 2), validando o modelo de custo proposto.

5. Significado e Impacto

O V3DB preenche uma lacuna crítica entre a privacidade dos dados e a integridade dos serviços de IA.

Confiança sem Exposição: Permite que clientes e auditores terceiros verifiquem a correção de buscas em corpora proprietários ou sensíveis sem precisar baixar os dados ou confiar no provedor.
Viabilidade Prática: Demonstra que provas ZK para buscas vetoriais complexas (ANN) são viáveis em produção, superando as barreiras de custo computacional através de otimizações de arquitetura de circuito.
Aplicações: É particularmente relevante para cenários de alto valor como busca de patentes, finanças e sistemas jurídicos, onde a transparência do processo de decisão é crucial, mas os dados subjacentes são confidenciais.

Em resumo, o V3DB transforma a busca vetorial em um processo auditável e verificável criptograficamente, garantindo que os resultados entregues sejam o reflexo exato de uma execução honesta sobre uma versão específica e comprometida dos dados, mantendo a privacidade do índice e dos embeddings.