halo2 vectordb
1.0.0
검증 가능한 벡터 유사성이 커밋 된 벡터 데이터베이스를 통해 쿼리합니다.
이 프로젝트는 제로 지식 증명을 사용하여 검증 가능한 벡터 데이터베이스에 대한 개념 증명을 얻는 것을 목표로합니다. 우리는 Halo2-lib와 고정 점 산술을 가능하게하는 멋진 zkfixedpointchip을 많이 사용합니다.
녹 설치가 필요합니다.
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 벡터 세트와 쿼리 벡터를 가져 와서 주어진 거리 함수와 쿼리 WRT와 가장 유사한 벡터를 찾습니다. 또한 이후 단계에서 사용될 수있는 표시기 (예 : 결과 벡터의 인덱스를 나타내는 1 인용 인코딩 된 벡터)를 반환합니다.merkle_commitment 벡터 세트를 가져 와서 포세이돈 해시가있는 머클 트리를 사용하여 그들에게 커밋합니다. 주어진 세트에 여러 요소가 포함되어 있지 않으면 나머지 잎에 0을 배치합니다. 시나리오에서는 전체 벡터 만 있거나 전혀 필요하지 않으며, 따라서 벡터 내의 요소에 커밋하는 것을 신경 쓰지 않습니다. 따라서 먼저 전체 벡터를 해시 한 다음 해시를 잎 노드로 취급합니다.kmeans 벡터 세트, K 상수를 취하여 중심의 수를 결정하고 반복 수를 결정하기 위해 I 상수를 결정합니다. K- 평균은 일반적으로 중심이 더 이상 업데이트되지 않을 때 종료되는 반복 알고리즘입니다. 그러나 이러한 제어 흐름은 ZK 회로에서 불가능합니다. 따라서 I 매개 변수는 고정 된 수의 반복을 결정합니다. 우리는 또한 고정 점 FixedPointVectorInstructions FixedPointChip 대한 구현을 보유하고 있으며, 이는 벡터를 정량화하고 정문하기위한 간단한 유틸리티 함수입니다.
실증 테스트 스위트는 demo_test 에서 찾을 수 있습니다.
K Centroids & Clusters를 초래합니다.K+2 Merkle Root와 함께 K Centroid 및 클러스터를 만듭니다.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 일부 테스트 ANN_SIFT_10K Jégou et al. Corpus-Texmex에서 다운로드 할 수 있습니다. 이 데이터 세트 128 차원 벡터. 테스트 폴더 내에서 common 모듈은이 벡터를 읽기 위해 두 가지 기능을 노출시킵니다.
read_vectors_from_disk 경로와 치수 (이 경우 128)를 취하고 데이터 세트에서 .fvec 파일을 읽고 f32 값의 단일 벡터를 반환합니다. 이 단일 벡터는 함께 구성된 모든 벡터 요소로 구성됩니다.select_from_vectors 해당 단일 벡터와 인덱스 목록을 가져 와서 선택한 벡터 만 반환합니다. 
