halo2 vectordb
1.0.0
Requêtes de similitude vectorielle vérifiables sur une base de données vectorielle engagée.
Ces projets visent à obtenir une preuve de concept pour une base de données vectorielle vérifiable à l'aide de preuves de connaissances zéro. Nous utilisons lourds le génial ZKFixedPointchip qui permet l'arithmétique à virgule fixe avec Halo2-lib.
Vous avez besoin de rouille installée:
curl --proto ' =https ' --tlsv1.2 -sSf https://sh.rustup.rs | shEnsuite, vous pouvez cloner ce référentiel et utiliser les puces à l'intérieur:
git clone https://github.com/erhant/halo2-vectordb.git
cd halo2-vectordbNous implémentons deux puces, l'une pour les mesures de distance dans HALO2 et l'autre pour les opérations de base de données vectorielles de base.
DistanceChip DistanceChip fournit des mesures de distance qui fonctionnent sur deux vecteurs de longueur égale. Les éléments vectoriels devraient être quantifiés avec le FixedPointChip . Les mesures de distance suivantes sont mises en œuvre:
euclidean_distance calcule la distance euclidienne entre deux vecteurs.manhattan_distance calcule la distance de Manhattan entre deux vecteurs.hamming_distance COMMUSE UN MINUS HAMMING COMMILITÉ ENTRE deux vecteurs.cosine_distance Calcule une similitude sans cosinus entre deux vecteurs.VectorDBChip VectorDBChip implémente la fonctionnalité de base de données vectorielle de base sur un ensemble de vecteurs. Semblable à DistanceChip , il nécessite qu'un FixedPointChip fonctionne sur des valeurs quantifiées. Il expose les fonctions suivantes:
nearest_vector prend un ensemble de vecteurs et un vecteur de requête, et trouve le vecteur qui est le plus similaire à la requête WRT une fonction de distance donnée. Il renvoie également un indicateur (c'est-à-dire un vecteur codé à un hot qui indique l'indice du vecteur de résultat) qui peut être utilisé à des étapes ultérieures.merkle_commitment prend un ensemble de vecteurs et leur engage à l'aide d'un arbre Merkle avec des hachages Poseidon. Si l'ensemble donné n'inclut pas la puissance de deux éléments, il remplira les zéros aux feuilles restantes. Dans notre scénario, nous n'avons besoin que du vecteur entier ou pas du tout, et pour cette raison, nous ne nous soucions pas de nous engager dans les éléments du vecteur. En tant que tel, nous hachons d'abord tout le vecteur, puis traitons ce hachage comme le nœud feuille.kmeans prend un ensemble de vecteurs, une constante K pour déterminer le nombre de centroïdes et une constante I pour déterminer le nombre d'itérations. K-Means est généralement un algorithme itératif qui se termine lorsque les centroïdes ne sont plus mis à jour; Cependant, un tel flux de contrôle n'est pas possible dans un circuit ZK. Par conséquent, le paramètre I détermine un nombre fixe d'itérations. Nous avons également un trait FixedPointVectorInstructions et son implémentation pour le FixedPointChip , qui sont des fonctions d'utilité simples pour quantifier et déshabiller les vecteurs.
Une suite de tests démonstrative se trouve sur demo_test :
K Centroïdes et clusters.K Centroïdes et des grappes ainsi que des racines K+2 Merkle.f64 .Exécutez les exemples via l'un des éléments suivants:
# 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 Vous pouvez fournir une entrée spécifique via l'option --input <input-name> .
Pour exécuter des tests:
cargo test Certains tests utilisent l'ensemble de données ANN_SIFT_10K par Jégou et al. qui peut être téléchargé sur Corpus-Texmex. Cet ensemble de données vecteurs 128 dimensions. Dans notre dossier Tests, le module common expose deux fonctions pour lire ces vecteurs:
read_vectors_from_disk prend un chemin et une dimension (128 dans ce cas) et lit les fichiers .fvec à partir de l'ensemble de données, renvoyant un seul vecteur de valeurs f32 . Ce vecteur unique est composé de tous les éléments vectoriels, composés ensemble.select_from_vectors prend ce vecteur unique et une liste d'indices, et renvoie uniquement les vecteurs sélectionnés. 
