Мысли Sin7Y об устранении ограничений памяти в ZKEVM

Мысли Sin7Y об устранении ограничений памяти в ZKEVM

17 ноября 2022 г.

ZKEVM — это программируемая виртуальная машина, основанная на технологии ZK. Он может генерировать доказательство ZK для всех операций, выполняемых виртуальной машиной, чтобы доказать правильность операций, выполняемых виртуальной машиной. Для ознакомления с несколькими схемами реализации ЗКЭВМ и сравнения преимуществ и недостатков можно обратиться к статье Виталика Бутерина: Различные типы ZK-EVM. Если вам нужны дополнительные сведения о дизайне, вы также можете прочитать:

Схема PSE ZKEVM (собственный уровень): privacy-scaling-explorations/zkevm-specs< /сильный>

Проект Polygon ZKEVM (на уровне байт-кода): Документация Polygon zkEVM.

Дизайн ZKEVM от Sin7y (на уровне языка): OlaVM: ZKVM, совместимый с Ethereum.

Независимо от схемы, zk требуется для ограничения всех действий ВМ, в том числе:

  • Выполнение вычислительной логики контракта
  • Выполнение доступа к памяти
  • Выполнение вычисления хэша
  • Выполнение обновлений состояния мира

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

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

В схеме ZK(E)VM мы должны применять zk в основном для доказательства самого вычисления. Для других вариантов поведения EVM (таких как доступ к памяти) мы можем оптимизировать их на уровне виртуальной машины (например, использование памяти с однократной записью), чтобы уменьшить масштаб ограничений ZK (избегая ограничения проверки согласованности доступа к памяти).

Дизайн памяти

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

Источник изображения: ethereum_evm_illustrated, стр. 51

В EVM инструкции, связанные с памятью:

  • MLOAD(x): загрузить 32 байта данных с адреса x в стек вызовов (стек)
  • MSTORE(x,y): начиная с адреса x, записать 32 байта y
  • MSTORE8(x,y): начиная с адреса x, запишите 8 байтов y (начиная с младшего разряда)

Заинтересованные читатели могут ознакомиться с изменениями памяти и стека с помощью упомянутых операций с памятью на игровой площадке EVM.

Ограничение памяти

В OlaVM все операции с оперативной памятью формируют единую таблицу, а содержимое таблицы состоит из двух типов: память и хранилище. Здесь мы сосредоточимся только на ограничениях памяти. n Типы операций с памятью можно разделить на три категории:

  • Начать операцию
  • Операция записи
  • Операция чтения

Есть три сценария, которые могут инициировать Init, а именно преобразование ctx, изменение типа и изменение адреса. При запуске любого сценария требуются ограничения: тип операции — w(запись), а v(значение) — 0. Когда три вышеуказанных сценария не запускаются, необходимо ограничить его на основе текущего типа операции. * Если это операция w(запись), ограничения clk должны быть увеличены (вызов модуля проверки диапазона), а записанное значение v является правильным (вызов ограничений копирования, в OlaVM все значения команд памяти поступают из регистров) * Если это операция r(чтение), ограничения clk должны быть увеличены (вызов модуля проверки диапазона), считанное значение совпадает со значением, записанным в последний раз

Потенциальные улучшения в «Дружественности к ZK»

  • Необходимо ли для операции Init ограничить инициализированное значение адреса памяти равным 0? п

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

* Для операции чтения можно ли избежать соответствующего ограничения, то есть избежать проверки «прочитанное значение соответствует последнему записанному значению». п

Поскольку тип памяти, определяемый самой виртуальной машиной, является памятью для чтения/записи, нет гарантии, что значение этого адреса памяти не будет изменено до того, как виртуальная машина прочитает значение этого адреса памяти. Поэтому требуется проверка на равенство, как показано ниже:

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

Обратите внимание: это может усложнить реализацию виртуальной машины, поскольку это не часто используемая модель памяти. Кроме того, мы не должны определять высокоуровневый DSL на виртуальной машине в первую очередь, потому что язык будет несколько недружественным для разработчиков dApp, и его необходимо будет удалить на уровне компилятора, что сделает их недружественными и невидимыми для разработчиков.< /p>

Таким образом, используя приведенную выше модель памяти, единственным ограничением на модуль памяти является ограничение для операций записи, то есть «использовать ограничения копирования, чтобы гарантировать правильность записанного значения». Без ограничений:

  • Значение для чтения равно значению для записи, так как память может быть записана только один раз.
  • Clk чтения больше, чем clk записи, потому что вы можете только писать, а затем читать.
  • Значение инициализации памяти равно 0 (память не требуется)

:::информация Также опубликовано здесь.

:::


Оригинал