Как работает ZKVM. Часть 1

В начале хотел бы сказать, что закрыл чат канал от комментариев, так как в последнее время заходит очень много ботов и спамеров. Ставить бота-модератора не хочу из-за наличия реклам и такой же необходимости чистить чат после них. Поэтому некоторое время будем без комментов.

А сейчас, перед праздниками, посмотрим на одну необычную тему о ZKVM.

Виртуальная машина с нулевыми знаниями (Zero-Knowledge Virtual Machine, ZKVM) - это виртуальная машина, которая может создать ZK-доказательство, подтверждающее, что она правильно выполнила набор машинных инструкций.

Это позволяет нам взять программу (набор операционных кодов), спецификацию виртуальной машины и доказать, что полученный результат является правильным. Верификатору не нужно повторно запускать программу, а только проверить сгенерированное ZK-доказательство - это позволяет сделать верификацию лаконичной.

Вопреки названию, ZKVM редко являются «нулевыми знаниями» в том смысле, что они хранят вычисления в тайне. Скорее, они используют алгоритмы ZK для получения краткого доказательства того, что программа выполнилась правильно на определенном входе, чтобы проверяющий мог перепроверить вычисления с экспоненциально меньшими затратами. Несмотря на то, что раскрытие входных данных программы необязательно, предотвращение случайных утечек данных и согласование приватного состояния несколькими сторонами - очень сложные инженерные задачи, которые до сих пор не решены и имеют ограничения по масштабированию.

ZKVM «вычисляет» каждый шаг в опкоде, а затем ограничивает правильность выполнения опкода. Ограничения должны быть разработаны таким образом, чтобы мы могли работать с произвольной, но корректной последовательностью опкодов.

Мы можем представить ZKVM как серию переходов из одного «состояния» в другое. Функция перехода в "состояние" принимает предыдущее состояние и текущий опкод, который должен быть выполнен, и генерирует новое состояние.

ZKVM реализует «функцию перехода состояния» и ограничения схемы, которые моделируют ее поведение. Обратите внимание, что «состояние» может включать в себя такие вещи, как «program counter» или другие учетные записи, необходимые для правильной работы VM.

В этой серии постов мы построим очень простую ZKVM, которая поддерживает только базовую арифметику, но может быть расширена для других операционных кодов. Представленная здесь VM имеет только стек и не имеет памяти или хранилища. В конце постов будут рекомендации по дальнейшему изучению ZKVM.

Простой ZKVM основанный на стеке

Мы построим простой стековый ZKVM с одним сигналом специального назначения, содержащим результат вычислений. VM получает серию опкодов и чисел, а затем выводит конечный результат на специальный сигнал, который мы вызываем.

Наш ZKVM имеет только следующие опкоды:

- PUSH (переносит первый аргумент в стек);
- ADD (извлекает два верхних элемента из стека и вставляет их сумму);
- MUL (выводит два верхних элемента из стека и выводит их произведение);
- NOP (нет операции, ничего не делать);

Для простоты все опкоды принимают один аргумент, но только PUSH использует этот аргумент. Остальные инструкции игнорируют аргумент.
Причина, по которой мы снабжаем аргументами опкоды, которые их не используют, заключается в том, что нам не нужно условно проверять наличие или отсутствие аргумента, основываясь на опкоде.

Здесь нет опкода STOP или RETURN (его замена будет объяснена в ближайшее время). VM принимает аргумент steps и возвращает значение, находящееся в нижней части стека после выполнения множества инструкций step.

P.S. В анимации выше приведен простой пример сложения двух чисел в этой архитектуре.

В Circom циклы не могут быть переменной длины, они всегда должны выполняться за фиксированное число итераций, так как сама базовая система ограничений ранга 1 (R1CS) должна иметь фиксированный размер. Аналогично, программы не могут быть переменного размера. Однако они должны иметь одинаковое количество опкодов, независимо от того, какая программа выполняется.