halo2 vectordb

Halo2 vectordb

Consultas de similitud vectorial verificable sobre una base de datos vectorial comprometida.

Estos proyectos tienen como objetivo obtener una prueba de concepto para una base de datos vectorial verificable que utiliza pruebas de conocimiento cero. Hacemos un gran uso del impresionante ZkFixedPointChip que permite la aritmética de punto fijo con halo2-lib.

Instalación

Necesitas el óxido instalado:

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

Luego, puede clonar este repositorio y usar los chips dentro de él:

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

Uso

Implementamos dos chips, uno para métricas de distancia en Halo2 y el otro para operaciones básicas de la base de datos vectorial.

DistanceChip

DistanceChip proporciona métricas de distancia que operan en dos vectores de igual longitud. Se espera que los elementos de vectores se cuanten con FixedPointChip . Se implementan las siguientes métricas de distancia:

• euclidean_distance calcula la distancia euclidiana entre dos vectores.
• manhattan_distance calcula la distancia de Manhattan entre dos vectores.
• hamming_distance calcula una similitud menos hamming entre dos vectores.
• cosine_distance calcula una similitud de coseno menos entre dos vectores.

VectorDBChip

VectorDBChip implementa la funcionalidad básica de la base de datos vectorial en un conjunto de vectores. Similar a DistanceChip , requiere un FixedPointChip para operar sobre valores cuantificados. Expone las siguientes funciones:

• nearest_vector toma un conjunto de vectores y un vector de consulta, y encuentra el vector que es más similar a la consulta WRT una función de distancia dada. También devuelve un indicador (es decir, un vector codificado unido que indica el índice del vector de resultados) que puede usarse en pasos posteriores.
• merkle_commitment toma un conjunto de vectores y se compromete con ellos usando un árbol de Merkle con Hashes Poseidon. Si el conjunto dado no incluye la potencia de los dos elementos, se enfrentará a los ceros a las hojas restantes. En nuestro escenario, solo necesitamos todo el vector o ninguno en absoluto, y por esa razón no nos importa comprometernos con elementos dentro del vector. Como tal, primero hash todo el vector, y luego tratamos ese hash como el nodo de la hoja.
• kmeans toma un conjunto de vectores, una constante K para determinar el número de centroides y una constante I para determinar el número de iteraciones. K-means generalmente es un algoritmo iterativo que termina cuando los centroides ya no están actualizados; Sin embargo, tal flujo de control no es posible en un circuito ZK. Por lo tanto, el parámetro I determina un número fijo de iteraciones.

También tenemos un rasgo FixedPointVectorInstructions y su implementación para FixedPointChip , que son funciones de utilidad simples para cuantificar y desquantizar vectores.

Demostración

Se puede encontrar un suite de prueba demostrativo en demo_test :

• Primero, capacitamos una base de datos sin ningún circuito ZK involucrado, lo que resulta en K centroides y clústeres.
• Luego, entrenamos otra base de datos con circuitos de Halo2, lo que resulta en K centroides y clústeres junto con K+2 Merkle Roots.
• Se da un vector de consulta aleatorio a ambas bases de datos, y los resultados se comparan en cuanto a elementos con error relativo. Tenga en cuenta que la precisión de punto fijo no es tan precisa como la implementación de óxido f64 .
• Las raíces de Merkle se comparan entre las fases de indexación y consulta, y se espera que coincidan.

Ejemplos

Ejecute los ejemplos a través de uno de los siguientes:

 # 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

Puede proporcionar una entrada específica a través de la opción --input <input-name> .

Pruebas

Para ejecutar pruebas:

cargo test

Algunas de las pruebas utilizan el conjunto de datos ANN_SIFT_10K por Jégou et al. que se puede descargar en Corpus-TexMex. Este conjunto de datos 128 vectores dimensionales. Dentro de nuestra carpeta de pruebas, el módulo common expone dos funciones para leer estos vectores:

• read_vectors_from_disk toma una ruta y una dimensión (128 en este caso) y lee los archivos .fvec del conjunto de datos, devolviendo un solo vector de valores f32 . Este vector único está compuesto por todos los elementos vectoriales, compuestos juntos.
• select_from_vectors toma ese vector único y una lista de índices, y solo devuelve los vectores seleccionados.

Expresiones de gratitud

• Este proyecto se desarrolla como parte del programa Axiom Open Source V2.
• Este proyecto no sería posible sin el ZKFixedPointChip.