miden 证明系统架构

miden是一个基于strark技术的zkvm实现方案。它的底层是基于winterfell这个zkp库来生成stark证明和对证明进行验证。下图1中虚线部分是Miden实现的主要功能。可以看出,主要有三个组件构成。

1. 一套词法语法编译器,下图1中的lexical analyzer和syntax parser。它们可以将miden定义的汇编指令编程成codeblock和block中包含的opcode和op value。

2. 一套指令的执行器,下图1中的executor。它负责按照定义的规则执行codeblock和block中包含的opcode及op value。执行结果为用于生成证明的execution trace。

3. 一套符合stark证明要求的AIR(代数中间表示),下图1中的AIR。用来对miden的虚拟机执行过程进行约束。

Miden的stark证明系统

AIR结构设计图

AIR的约束分为stack和decoder两部分:

图2为stack的约束,初始化时分配了最上边深度为8的stack。在执行时根据程序需要,可能会超出初始化分配的深度,那么max_depth会根据需要递增。但是不能超过最大深度16。否则报错。

 

Miden的stark证明系统

图3为decoder的约束。其中的op_counter,op_sponge,cf_op_bits, ld_op_bits,hd_op_bits是固定列长度的。其中的op_sponge用于执行指令的顺序和正确性的约束。cf_op_bits约束3bit的flow_ops。ld_op_bits,hd_op_bits分别约束了user_ops的低5bits和高2bits。ld_op_bits和hd_op_bits组合构成一条执行的user_op,还用来作为stack每step状态约束的selector。

Miden的stark证明系统

Miden VM执行过程实例

本节将展示一个简单的miden逻辑来说明vm的执行过程和stark的execution trace的生成。

下边代码段1是要执行的代码段:

它执行的逻辑是将3和5压栈。之后从tape读取flag。判断flag是1还是0。如果是1则运行if.true分支将压栈的两个数3和5取出,相加得到8并重新压入栈。如果是0则运行else分支将压栈的两个数3和5取出相乘得到15,再将15重新压入栈。

Miden的stark证明系统

代码段通过miden的词法和语法分析器解析后的最终指令代码如下代码段2:

Miden的stark证明系统

下边图4是vm运行代码段2的过程,中间是executor执行opcode的流程图,左边虚线指向的是代码执行产生的decoder trace,右边点划线指向的是代码执行产生的stack trace。

其中executor是按照code block来一块一块执行。在本例子里,首先执行了一个span block。之后在第32步时执行if-else-end结构进入了swtich block块,并将之前的span block的最后一步执行生成的sponge hash压入ctx_stack,并在swtich block块执行完之后,在第49步弹出到sponge里。

Miden的stark证明系统

Note:本文档描述针对miden工程的main分支最新版本。目前miden的next分支对于指令进行了大量重新设计,AIR也只实现了很少一部分的约束。

stack约束条件

本节将展示主要的User操作指令的约束条件。其中的old_stack_x指的是指令执行前的stack的x位置存储的value。new_stack_x指的是指令执行后的stack的x位置存储的value。-->是将栈左边位置的value拷贝到右边位置。==是等式约束。stack的约束相对比较简单,就不多做解释了。

条件指令

Choose

Constrain:

Miden的stark证明系统

如果condition为1, x在堆栈顶部,condition为0, y在堆栈顶部

算术指令

add

Constrain:

Miden的stark证明系统

mul

Constrain:

Miden的stark证明系统

inv

Constrain:

Miden的stark证明系统

neg

Constrain:

Miden的stark证明系统

bool 指令

not

Constrain:

Miden的stark证明系统

and

Constrain:

Miden的stark证明系统

or

Constrain:

Miden的stark证明系统

hash 指令

RESCR

满足 hash函数协议的限制函数hash

占用 6 registers

Constrain:

Miden的stark证明系统

比较指令

eq

Constrain:

Miden的stark证明系统

cmp

根据比较的两个数的bit长度循环比较。比如

A: [0,1,0,1]

B: [0,0,1,1]

需要比较4次

Constrain:

Miden的stark证明系统

堆栈操作指令

dup.n

Constrain:

Miden的stark证明系统

swap

Constrain:

Miden的stark证明系统

ROLL4

Constrain:

Miden的stark证明系统

decoder的约束条件

本节将展示主要的Flow操作指令的约束条件。

用户代码执行

op_bits

对于cf_op_bits,ld_op_bits,hd_op_bits的约束。

约束1: 每bit只能为0或者1。

约束2: 当op_counter不为0时,ld_ops 和 hd_ops不能同时为0。

约束3: 当cf_op_bits为hacc时。 op_counter状态会加1。

约束4: BEGIN, LOOP, BREAK, and WRAP指令需要16对齐。

约束5: TEND and FEND指令需要16对齐。

约束6:PUSH指令需要8对齐。

Miden的stark证明系统

hacc

hacc作为flowOps,每次执行该指令都会引起sponge的状态改变,需要进行约束

Miden的stark证明系统

条件判断

t_end

作为if的true分支结束的约束,分为两部分:

约束1: sponge状态的约束,弹出栈顶的值等于new_sponge_0。if的true分支的最后一步执行后的sponge等于new_sponge_1。new_sponge_3等于0。

约束2: ctx_stack的约束。弹出栈顶的值等于new_sponge_0。栈内其他元素都往栈顶移动一个位置。

约束3: loop_stack的约束。loop_stack的状态不变。

Miden的stark证明系统

f_end

作为if的false分支结束的约束,分为两部分:

约束1: sponge状态的约束,弹出栈顶的值等于new_sponge_0。if的true分支的最后一步执行后的sponge等于new_sponge_2。new_sponge_3等于0。

约束2: ctx_stack的约束。弹出栈顶的值等于new_sponge_0。栈内其他元素都往栈顶移动一个位置。

约束3: loop_stack的约束。loop_stack的状态不变。

Miden的stark证明系统

关于我们

Sin7Y成立于2021年,由顶尖的区块链开发者和密码学工程师组成。我们既是项目孵化器也是区块链技术研究团队,探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。

微信公众号:Sin7Y

GitHub:Sin7Y

Twitter:@Sin7Y_Labs

Medium:Sin7Y

Mirror:Sin7Y

HackMD:Sin7Y

HackerNoon:Sin7Y

Email:contact@sin7y.org