halo2 vectordb

Halo2 Vectordb

Überprüfbare Vektor -Ähnlichkeitsabfragen über eine engagierte Vektordatenbank.

Diese Projekte zielen darauf ab, einen Nachweis des Konzepts für eine überprüfbare Vektordatenbank mit Null-Wissen-Beweisen zu erhalten. Wir nutzen das fantastische zkfixedPointChip, das die Festpoint-Arithmetik mit Halo2-Lib ermöglicht.

Installation

Sie brauchen Rost installiert:

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

Anschließend können Sie dieses Repository klonen und die darin enthaltenen Chips verwenden:

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

Verwendung

Wir implementieren zwei Chips, eine für Distanzmetriken in Halo2 und die andere für grundlegende Vektor -Datenbankoperationen.

DistanceChip

DistanceChip bietet Abstandsmetriken, die auf zwei Vektoren gleicher Länge arbeiten. Es wird erwartet, dass die Vektorelemente mit dem FixedPointChip quantisiert werden. Die folgenden Entfernungsmetriken werden implementiert:

• euclidean_distance berechnet den euklidischen Abstand zwischen zwei Vektoren.
• manhattan_distance berechnet die Distanz von Manhattan zwischen zwei Vektoren.
• hamming_distance berechnet eine minus Hamming -Ähnlichkeit zwischen zwei Vektoren.
• cosine_distance berechnet eine minus Cosinus -Ähnlichkeit zwischen zwei Vektoren.

VectorDBChip

VectorDBChip implementiert grundlegende Funktionen der Vektordatenbank über eine Reihe von Vektoren. Ähnlich wie bei DistanceChip benötigt es einen FixedPointChip , um über quantisierte Werte über quantisierte Werte zu arbeiten. Es enthüllt die folgenden Funktionen:

• nearest_vector nimmt eine Reihe von Vektoren und einen Abfragebericht und findet den Vektor, der der Abfrage einer bestimmten Entfernungsfunktion am ähnlichsten ist. Es gibt auch einen Indikator zurück (dh in einem HOT-codierten Vektor, der den Index des Ergebnisvektors angibt), der in späteren Schritten verwendet werden kann.
• merkle_commitment nimmt eine Reihe von Vektoren und verpflichtet sich mit einem Merkle -Baum mit Poseidon -Hashes. Wenn der angegebene Satz nicht viele Elemente mit Kraft von zwei Jahren enthält, werden Nullen in die verbleibenden Blätter gepadelt. In unserem Szenario brauchen wir nur den gesamten Vektor oder gar keine, und aus diesem Grund kümmern wir uns nicht darum, Elemente innerhalb des Vektors zu verpflichten. Als solches hasht wir zuerst den gesamten Vektor und behandeln diesen Hash als Blattknoten.
• kmeans nimmt eine Reihe von Vektoren, eine K -Konstante, um die Anzahl der Zentroide und eine I -Konstante zu bestimmen, um die Anzahl der Iterationen zu bestimmen. K-Means ist normalerweise ein iterativer Algorithmus, der endet, wenn die Schwerpunkte nicht mehr aktualisiert sind. Ein solcher Kontrollfluss ist jedoch in einem ZK-Kreislauf nicht möglich. Daher bestimmt der I -Parameter eine feste Anzahl von Iterationen.

Wir haben außerdem ein Merkmal FixedPointVectorInstructions und seine Implementierung für den FixedPointChip , die einfache Nutzfunktionen sind, um Vektoren zu quantisieren und zu dequantisieren.

Demonstration

Eine demo_test finden Sie eine Demonstrativtestsuite:

• Zunächst schulen wir eine Datenbank ohne beteiligte ZK -Schaltungen, was zu K Centroids & Clustern führt.
• Dann trainieren wir eine weitere Datenbank mit Halo2 -Schaltungen, was zu K -Zentroiden und -Clustern zusammen mit K+2 Merkle Roots führt.
• In beiden Datenbanken wird ein zufälliger Abfragebektor verabreicht, und die Ergebnisse werden mit dem relativen Fehler verglichen. Beachten Sie, dass die Fixpunktpräzision in nicht so genau wie die f64 Rust-Implementierung.
• Die Merkle -Wurzeln werden zwischen Indexierung und Abfragephasen verglichen und werden voraussichtlich übereinstimmen.

Beispiele

Führen Sie die Beispiele über eine der folgenden Aussagen aus:

 # 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

Sie können eine bestimmte Eingabe über die Option --input <input-name> angeben.

Testen

Tests ausführen:

cargo test

Einige der Tests verwenden den Datensatz von ANN_SIFT_10K von Jégou et al. die bei Corpus-Texmex heruntergeladen werden können. Dieser Datensatz 128-dimensionaler Vektoren. In unserem Testordner wird das common Modul zwei Funktionen zum Lesen dieser Vektoren enthüllt:

• read_vectors_from_disk nimmt einen Pfad und eine Dimension (128 in diesem Fall) und liest die .fvec -Dateien aus dem Datensatz, wobei ein einzelner Vektor von f32 -Werten zurückgegeben wird. Dieser einzelne Vektor besteht aus allen Vektorelementen, die zusammen zusammengesetzt sind.
• select_from_vectors nimmt diesen einzelnen Vektor und eine Liste von Indizes an und gibt nur die ausgewählten Vektoren zurück.

Anerkennung

• Dieses Projekt wird im Rahmen des Axiom Open Source V2 -Programms entwickelt.
• Dieses Projekt wäre ohne den ZKFixedPointChip nicht möglich.