halo2 vectordb

Halo2 vectordb

Kueri kesamaan vektor yang dapat diverifikasi atas database vektor yang berkomitmen.

Proyek ini bertujuan untuk mendapatkan bukti konsep untuk database vektor yang dapat diverifikasi menggunakan bukti nol-pengetahuan. Kami memanfaatkan berat ZkFixedPointChip yang luar biasa yang memungkinkan aritmatika titik tetap dengan halo2-lib.

Instalasi

Anda perlu dipasang karat:

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

Kemudian, Anda dapat mengkloning repositori ini dan menggunakan chip di dalamnya:

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

Penggunaan

Kami menerapkan dua chip, satu untuk metrik jarak di halo2, dan yang lainnya untuk operasi basis data vektor dasar.

DistanceChip

DistanceChip menyediakan metrik jarak yang beroperasi pada dua vektor dengan panjang yang sama. Elemen vektor diharapkan dikuantisasi dengan FixedPointChip . Metrik jarak berikut diimplementasikan:

• euclidean_distance menghitung jarak Euclidean antara dua vektor.
• manhattan_distance menghitung jarak Manhattan antara dua vektor.
• hamming_distance menghitung satu minus hamming kesamaan antara dua vektor.
• cosine_distance menghitung satu minus kemiripan cosinus antara dua vektor.

VectorDBChip

VectorDBChip mengimplementasikan fungsionalitas database vektor dasar atas satu set vektor. Mirip dengan DistanceChip , membutuhkan FixedPointChip untuk beroperasi melalui nilai -nilai terkuantisasi. Itu memperlihatkan fungsi -fungsi berikut:

• nearest_vector mengambil satu set vektor dan vektor kueri, dan menemukan vektor yang paling mirip dengan kueri WRT fungsi jarak yang diberikan. Ini juga mengembalikan indikator (yaitu vektor yang dikodekan satu-panas yang menunjukkan indeks vektor hasil) yang dapat digunakan pada langkah-langkah selanjutnya.
• merkle_commitment mengambil satu set vektor, dan berkomitmen untuk mereka menggunakan pohon merkle dengan hash poseidon. Jika set yang diberikan tidak termasuk kekuatan dua elemen, itu akan memadukan nol ke daun yang tersisa. Dalam skenario kami, kami hanya membutuhkan seluruh vektor atau tidak sama sekali, dan untuk alasan itu kami tidak peduli berkomitmen pada elemen -elemen di dalam vektor. Dengan demikian, pertama -tama kita hash seluruh vektor, dan kemudian memperlakukan hash itu sebagai simpul daun.
• kmeans mengambil satu set vektor, konstanta K untuk menentukan jumlah centroid dan konstanta I untuk menentukan jumlah iterasi. K-means biasanya merupakan algoritma berulang yang berakhir ketika centroid tidak lagi diperbarui; Namun, aliran kontrol seperti itu tidak dimungkinkan dalam sirkuit ZK. Oleh karena itu, parameter I menentukan jumlah iterasi yang tetap.

Kami juga memiliki sifat FixedPointVectorInstructions dan implementasinya untuk FixedPointChip , yang merupakan fungsi utilitas sederhana untuk mengukur dan menghilangkan vektor.

Demonstrasi

Suite tes demonstratif dapat ditemukan di demo_test :

• Pertama, kami melatih database tanpa sirkuit ZK yang terlibat, menghasilkan K Centroids & Clusters.
• Kemudian, kami melatih database lain dengan sirkuit halo2, menghasilkan K centroid & cluster bersama dengan root K+2 Merkle.
• Vektor kueri acak diberikan untuk kedua basis data, dan hasilnya dibandingkan dengan elemen dengan kesalahan relatif. Perhatikan bahwa presisi titik tetap tidak seakurat implementasi karat f64 .
• Akar Merkle dibandingkan antara fase pengindeksan dan kueri, dan diharapkan cocok.

Contoh

Jalankan contoh melalui salah satu dari yang berikut:

 # 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

Anda dapat memberikan input spesifik melalui opsi --input <input-name> .

Pengujian

Untuk menjalankan tes:

cargo test

Beberapa tes memanfaatkan dataset ANN_SIFT_10K oleh Jégou et al. yang dapat diunduh di Corpus-TexMex. Dataset ini 128 vektor dimensi. Dalam folder Tes kami, modul common memperlihatkan dua fungsi untuk membaca vektor -vektor ini:

• read_vectors_from_disk mengambil jalur dan dimensi (128 dalam hal ini) dan membaca file .fvec dari dataset, mengembalikan vektor tunggal nilai f32 . Vektor tunggal ini terdiri dari semua elemen vektor, disusun bersama.
• select_from_vectors mengambil vektor tunggal dan daftar indeks, dan mengembalikan vektor yang dipilih saja.

Ucapan Terima Kasih

• Proyek ini dikembangkan sebagai bagian dari program V2 Open Source Axiom.
• Proyek ini tidak akan mungkin terjadi tanpa ZkFixedPointchip.