halo2 vectordb
1.0.0
可驗證的向量相似性查詢在授權的矢量數據庫上查詢。
該項目旨在使用零知識證明獲得可驗證的向量數據庫的概念驗證。我們大量使用了Awesome ZkFixedPointChip，該ChippointChip可以使用Halo2-Lib進行固定點算術。
您需要安裝生鏽：
curl --proto ' =https ' --tlsv1.2 -sSf https://sh.rustup.rs | sh然後，您可以克隆此存儲庫並使用其中的芯片：
git clone https://github.com/erhant/halo2-vectordb.git
cd halo2-vectordb我們實施兩個芯片，一個用於HALO2中的距離指標，另一個用於基本矢量數據庫操作。
DistanceChip DistanceChip提供的距離指標可以在兩個相等長度的向量上運行。預計將使用FixedPointChip策略對矢量元素進行量化。實施以下距離指標：
euclidean_distance計算兩個向量之間的歐幾里得距離。manhattan_distance計算兩個向量之間的曼哈頓距離。hamming_distance計算兩個向量之間的一個減錘相似性。cosine_distance計算兩個向量之間的一個減去餘弦相似性。VectorDBChip VectorDBChip在一組向量上實現了基本矢量數據庫功能。與DistanceChip類似，它需要一個FixedPointChip才能超過量化值。它揭示了以下功能：
nearest_vector採用一組向量和查詢向量，並找到與給定距離函數最相似的向量。它還返回一個指標（即指示結果向量索引的一列編碼向量），該指標可以在以後的步驟中使用。merkle_commitment採用了一組向量，並使用帶有Poseidon Hashes的Merkle樹致力於它們。如果給定的集合不包含兩個元素的功率，則它將在其餘的葉子上添加零。在我們的情況下，我們只需要整個向量或根本不需要，因此我們不關心致力於向量內的要素。因此，我們首先將整個矢量放置，然後將其視為葉子節點。kmeans採用一組向量，一個K常數來確定質心數量和I常數以確定迭代次數。 K-均值通常是一種迭代算法，當質心不再更新時終止；但是，在ZK電路中不可能進行這種控制流。因此， I參數確定固定數量的迭代。我們還具有特徵FixedPointVectorInstructions及其對FixedPointChip策略的實現，這是簡單的實用程序函數，以量化和去除向量。
可以在demo_test上找到一個示範性的測試套件：
K質心和集群。K centroids＆clusters以及K+2 Merkle根。f64 Rust實現準確。通過以下一個來運行示例：
# 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您可以通過--input <input-name>選項提供特定的輸入。
進行測試：
cargo test一些測試利用Jégou等人的ANN_SIFT_10K數據集。可以在colpus-texmex下載。該數據集128維向量。在我們的測試文件夾中， common模塊公開了兩個函數以讀取這些向量：
read_vectors_from_disk採用路徑和維度（在這種情況下為128），並從數據集中讀取.fvec文件，並返回一個f32值的單個向量。該單個矢量由所有矢量元素組成，組成。select_from_vectors獲取該向量和索引列表，僅返回所選向量。 
