halo2 vectordb

Halo2 Vectordb

Проверяемые векторные сходства запросы по убедительной векторной базе данных.

Этот проект направлен на получение проверки концепции для проверенной векторной базы данных с использованием доказательств нулевого знания. Мы широко используем потрясающий ZKFixedPointChip, который позволяет арифметике с фиксированной точкой с 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 берет набор векторов и вектор запросов и находит вектор, который наиболее похож на запрос WRT данной функции расстояния. Он также возвращает индикатор (т.е. кодированный вектор с одним горячим, который указывает индекс вектора результата), который может использоваться на более поздних шагах.
• merkle_commitment берет набор векторов и занимается им, используя дерево Меркл с хэшами Посейдона. Если заданный набор не включает в себя мощность двух элементов, он будет наносить нули к оставшимся листьям. В нашем сценарии нам нужен только весь вектор или ни один вообще, и по этой причине мы не заботимся о том, чтобы посвятить себя элементам в векторе. Таким образом, мы сначала охватываем весь вектор, а затем рассматриваем этот хэш как листовой узел.
• kmeans принимает набор векторов, K постоянную, чтобы определить количество центроидов и константа I , чтобы определить количество итераций. K-средние обычно являются итерационным алгоритмом, который заканчивается, когда центроиды больше не обновляются; Тем не менее, такой контрольный поток невозможна в ZK-цирке. Поэтому параметр I определяет фиксированное количество итераций.

У нас также есть черта FixedPointVectorInstructions и ее реализация для FixedPointChip , которые являются простыми полезными функциями для квантования и отрыва векторов.

Демонстрация

Демонстративный набор тестирования можно найти на demo_test :

• Во -первых, мы обучаем базу данных без каких -либо цепей ZK, что приводит к K Centroid & Clusters.
• Затем мы тренируем другую базу данных с цепями Halo2, в результате чего K Centroid & Clusters и K+2 Merkle Cools.
• Случайный вектор запросов дается обеим базам данных, и результаты сравниваются в виде элемента с относительной ошибкой. Обратите внимание, что точность с фиксированной точкой не так точна, как реализация ржавчины f64 .
• Корни Меркле сравниваются между фазами индексации и запросов и, как ожидается, будут соответствовать.

Примеры

Запустите примеры по одному из следующих действий:

 # 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 измерных векторов. В нашей папке Tests common модуль выявляет две функции для чтения этих векторов:

• read_vectors_from_disk берет путь и размер (128 в данном случае) и считывает файлы .fvec из набора данных, возвращая один вектор значений f32 . Этот единственный вектор состоит из всех векторных элементов, составленных вместе.
• select_from_vectors принимает один вектор и список индексов и возвращает только выбранные векторы.

Благодарности

• Этот проект разработан в рамках программы Axiom Open Source V2.
• Этот проект был бы невозможным без zkfixedpointchip.