1. 计算类型

Programs程序有2种类型：

  • 1）Circuit电路：即，程序即电路。将程序转换为电路。
  • 2）Virtual machine虚拟机：即，程序为电路的输入。【Miden VM属于此类型】

2. 何为ZK virtual machine？

常规虚拟机为：

  • 输入有：
    • 初始状态
    • 待执行程序
  • 输出有：
    • 基于初始状态，执行完该程序后的最终状态。

Zero-Knowledge（ZK）虚拟机为：

  • 输入有：
    • 初始状态
    • 待执行程序：可为公开输入，也可为隐私输入。
    • witness（可选项，用作private input）
  • 输出有：
    • 基于初始状态，执行完该程序后的最终状态。
    • 相应的proof

使用ZK虚拟机的好处在于：

  • 1）易于使用：无需学习密码学知识和ZKP系统知识。
  • 2）通用性：图灵完备的ZK虚拟机，可为任意计算生成proofs。
  • 3）简单性：单个（相对）简单约束集合，可描述整个虚拟机。
  • 4）递归性：proof验证流程，可看成是执行在虚拟机上的另一程序。

ZK虚拟机的缺点在于：

  • 1）特殊的计算结构：并非所有的ZKP证明系统都可用于构建ZK虚拟机。如具有很多重复的结构，对于R1CS证明系统来说并不容易死。
    • 但对STARKs（AIR算术化➕FRI）证明系统来说，这不是问题。
  • 2）性能：专门定制的特殊电路可能会更快，特别是对于简单计算。【虚拟机模式有很多额外的开销，如对程序解码、对内存的随机访问等。对于简单计算来说，这些额外开销可能会超过实际电路。】
    • 不过，可在ZK虚拟机内部使用这种专门定制的特殊电路。

3. Polygon Miden VM架构

Polygon Miden VM设计时，做了如下选择：

  • 1）ZKP系统：为 STARKs ➕ multiset checks：快速且完美匹配机器计算。
  • 2）Prover：为 Winterfell：为以Rust编写的通用STARK prover。
  • 3）Field：为 Goldilocks域 2 64− 2 32+12^{64}-2^{32}+1 264−232+1：快速且完美匹配32位整数运算。
  • 4）Instruction Set指令集：为 定制指令集架构：基于Stack的、针对ZK优化的指令集架构，基于MAST的programs。

3.1 Polygon Miden VM组件

Polygon Miden VM 关键组件有：

  • Stack
  • Memory
  • Bus
  • Chiplets：专门定制的特殊电路。
  • Advice provider

Chiplets为专门定制的特殊电路，当前有如下类型的chiplets：

  • 1）Range checks：
    • 16-bit range checks：Miden VM的内存会大量使用16-bit range checks，用于做32位运算，如将某域元素分解为2个32位value等。
  • 2）Rescue hash：
    • 2-to-1 hashes
    • Linear hashes
    • Merkle paths
  • 3）Bitwise operations：
    • 基于32位值的bitwise AND、XOR。

3.2 Polygon Miden VM Execution Trace

Miden VM execution trace结构为：

以stack execution trace为例：

其中还引入了overflow table：【实际实现时使用multi-set checks】

  • 1）当items无法放入stack的top 16 slots时，会将这些items推入到overflow table中。
  • 2）当有items从stack中移除时，会将overflow table中的items移回到stack中。

以hash chiplets为例：【通过bus，区分了stack trace和hasher trace。仍然需使用multi-set checks。】

4. Polygon Miden VM程序执行

Polygon Miden VM中：

  • 输入的程序采用Miden Assembly汇编语言编写。
  • 然后将用Miden Assembly汇编语言程序，编译为Program MAST。
  • 最终，在Miden VM中实际执行的是Program MAST。

准确来说，Miden VM程序为VM指令的Merklized abstract syntax trees（MAST）。其具有如下关键属性：

  • 1）所有程序可被reduce为单个哈希（其MAST的root）。
  • 2）每个内部节点自身为某更小程序的MAST。
  • 3）program MAST的叶子节点，为（无control flow的）linear programs。

具体示例为：【join表示依次执行其左右子节点；split表示要么执行其左子节点，要么执行其右子节点。】

4.1 选择MAST的原因

选择MAST的原因在于：

  • 1）效率：在VM中仅需对所执行的代码进行哈希。
  • 2）安全性：所有已执行代码是静态已知的（无自修改代码 或 动态跳转）
  • 3）隐私：可支持隐私程序输入，该隐私程序具有公开的前置条件或后置条件。

参考资料

[1] 2022年9月Bobbin Threadbare分享视频 09 Miden VM architecture overview

Miden系列博客

  • zk、zkVM、zkEVM及其未来
  • Polygon L2扩容方案揭秘
  • STARKs and STARK VM: Proofs of Computational Integrity
  • Feeding Program Source Code to ZK VMs
  • 混合Rollup：探秘 Metis、Fraxchain、Aztec、Miden和Ola
  • Polygon Miden：扩展以太坊功能集的ZK-optimized rollup
  • Polygon Miden zkRollup中的UTXO+账户混合状态模型
  • Polygon Miden交易模型：Actor模式 + ZKP =＞ 并行 + 隐私
  • Polygon Miden状态模型：解决状态膨胀，而不牺牲隐私和去中心化
  • Polygon Miden中的nullifier sets设计
  • Polygon Miden VM中的哈希函数对比
  • Polygon MidenVM中的recursive STARK verification优化