halo2 vectordb

Halo2 vectordb

Consultas de similaridade vetorial verificável em um banco de dados vetorial comprometido.

Esses projetos têm como objetivo obter uma prova de conceito para um banco de dados vetorial verificável usando provas de sabor zero. Fazemos uso pesado do incrível ZKFIXEDPOintChip, que permite a aritmética de ponto fixo com o halo2-Lib.

Instalação

Você precisa de ferrugem instalada:

curl --proto ' =https ' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Em seguida, você pode clonar este repositório e usar as fichas dentro dele:

git clone https://github.com/erhant/halo2-vectordb.git
cd halo2-vectordb

Uso

Implementamos dois chips, um para métricas de distância em Halo2 e o outro para operações básicas de banco de dados vetorial.

DistanceChip

DistanceChip fornece métricas de distância que operam em dois vetores de igual comprimento. Espera -se que os elementos vetoriais sejam quantizados com o FixedPointChip . As seguintes métricas de distância são implementadas:

• euclidean_distance calcula a distância euclidiana entre dois vetores.
• manhattan_distance calcula a distância de Manhattan entre dois vetores.
• hamming_distance calcula uma similaridade de hamming menos entre dois vetores.
• cosine_distance calcula uma similaridade de cosseno menos entre dois vetores.

VectorDBChip

VectorDBChip implementa a funcionalidade básica do banco de dados vetorial sobre um conjunto de vetores. Semelhante ao DistanceChip , requer um FixedPointChip para operar sobre valores quantizados. Ele expõe as seguintes funções:

• nearest_vector pega um conjunto de vetores e um vetor de consulta e encontra o vetor mais semelhante à consulta WRT uma determinada função de distância. Ele também retorna um indicador (ou seja, um vetor codificado de um hot que indica o índice do vetor de resultado) que pode ser usado nas etapas posteriores.
• merkle_commitment pega um conjunto de vetores e se compromete com eles usando uma árvore Merkle com Hashes Poseidon. Se o conjunto fornecido não incluir muitos elementos de potência de dois elementos, ele prenderá os zeros nas folhas restantes. Em nosso cenário, precisamos apenas de todo o vetor ou nenhum, e por esse motivo, não nos importamos em nos comprometer com elementos dentro do vetor. Como tal, primeiro o vetor inteiro e depois tratamos esse hash como o nó foliar.
• kmeans pega um conjunto de vetores, uma constante K para determinar o número de centróides e I constante para determinar o número de iterações. O K-Means geralmente é um algoritmo iterativo que termina quando os centróides não são mais atualizados; No entanto, esse fluxo de controle não é possível em um circuito ZK. Portanto, o parâmetro I determina um número fixo de iterações.

Também temos uma característica FixedPointVectorInstructions e sua implementação para o FixedPointChip , que são funções de utilidade simples para quantizar e desquantizar os vetores.

Demonstração

Um conjunto de testes demonstrativo pode ser encontrado no demo_test :

• Primeiro, treinamos um banco de dados sem os circuitos ZK envolvidos, resultando em K Centroids & Clusters.
• Em seguida, treinamos outro banco de dados com circuitos HALO2, resultando em K Centroids & Clusters, juntamente com as raízes de Merkle K+2 .
• Um vetor de consulta aleatório é fornecido a ambos os bancos de dados e os resultados são comparados em termos de elemento com erro relativo. Observe que a precisão do ponto fixo não é tão preciso quanto a implementação da ferrugem f64 .
• As raízes de Merkle são comparadas entre fases de indexação e consulta e devem corresponder.

Exemplos

Execute os exemplos por meio de um dos seguintes:

 # demonstrate distance computations
LOOKUP_BITS=12 cargo run --example distances -- 
  --name distances -k 13 mock

# example merkle commitment to vectors
LOOKUP_BITS=12 cargo run --example merkle -- 
  --name merkle -k 13 mock

# exhaustively find the similar vector & commit to the database
LOOKUP_BITS=12 cargo run --example query -- 
  --name query -k 13 mock

# compute centroids
LOOKUP_BITS=15 cargo run --example kmeans -- 
  --name kmeans -k 16 mock

Você pode fornecer uma entrada específica através da opção --input <input-name> .

Teste

Para executar testes:

cargo test

Alguns dos testes usam o conjunto de dados ANN_SIFT_10K por Jégou et al. que pode ser baixado no corpus-texmex. Este conjunto de dados de vetores 128-dimensionais. Dentro da nossa pasta de testes, o módulo common expõe duas funções para ler estes vetores:

• read_vectors_from_disk segue um caminho e uma dimensão (128 neste caso) e lê os arquivos .fvec do conjunto de dados, retornando um único vetor de valores f32 . Este vetor único é composto por todos os elementos vetoriais, compostos juntos.
• select_from_vectors pega esse vetor único e uma lista de índices e retorna apenas os vetores selecionados.

Agradecimentos

• Este projeto é desenvolvido como parte do programa Axiom Open Source V2.
• Este projeto não seria possível sem o zkfixedpointchip.