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}+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优化