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

Ну, и заключительный перевод статьи о ZKVM.

Разве не неэффективно иметь ограничения для каждого опкода, если мы используем только один?

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

Мы можем повысить эффективность, используя Quin selector (или два) для определения того, какие элементы стека будут входом для опкода, но это все равно означает, что каждая итерация стека нуждается в ограничениях для хэша, даже если он их не использует.

Эта низкая эффективность ненужного повторения неиспользуемых ограничений является серьезным недостатком ванильного R1CS, который не позволяет условно использовать ограничения.

Решения для повышения эффективности

Два современных подхода, позволяющих значительно повысить эффективность, - это ограничения, основанные на таблицах поиска, и рекурсивные доказательства.

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

2. Рекурсивное доказательство создает отдельное ZK-доказательство для каждой инструкции, а затем объединяет его с другим ZK-доказательством, которое проверяет правильность входных доказательств. Учтите, что алгоритм верификации в ZK сам по себе может быть смоделирован с помощью арифметической схемы.

#zkvm