zkevm 中用于创建执行轨迹的 plookup
简介
字节码很难迁移到 snark。一个原因是跳转，因为每个操作码都可以跳转到任何其他操作码，所以需要一种方法在电路中追踪这些跳转。一种方法需要添加操作码来证明一个操作码在一个累加器中。这会花费大量的约束，每步需要数千个约束。
为了克服这个问题，我们使用 plookup 允许证明者选择他们想要的任何操作码顺序。然后，我们在 evm 证明中针对程序计数器检查每个操作码，以确保所选顺序正确。
plookup 允许你证明 f 的元素也包含在 t 中。例如，如果 `t = [1,2,3,4]` 并且 `f = [1,2,3]`，这将通过 plookup 检查，但是
`t = [1,2,3,4]` 并且 `f = [1,2,5]` 将无法通过，因为 5 不在 t 中。
这可以被认为是一种执行以下操作的方式
``` python
for element in f:
assert(element in t)
```
允许重复，并且一旦你执行了足够的检查来克服恒定成本，每次检查的成本约为 1 个约束。
部署时间
在部署时，用户提供
```
opcodes = [add, mul, jump, add , mul, jumpdest, term]
```
我们获取这些操作码，为每个操作码添加一个索引，这就是我们的表 t，我们称之为 `t_opcodes`。
```
t_opcodes = [0add, 1mul, 2jump, 3add, 4mul, 5jumpdest, 6term]
```
状态证明
在我们的状态证明阶段，我们允许证明者从我们的 t_opcodes 中选择任何操作码。我们不在此处检查有效性，但稍后会检查。
所以我们选择了操作码
execution_opcodes = [0add, 1mul, 2jump, 5jumpdest, 6term]
执行证明
在我们的执行证明中，我们要求第一个操作码的索引为 0。这是为了确保我们不会跳入字节码的中间，跳过一些检查。
然后，每次我们递增程序计数器时，我们都会检查下一个操作码的索引是否与其匹配。这样我们就可以向前或向后跳跃并重复操作码。
```python=
def execution_proof(execution_opcodes):
program_counter = 0
for i, opcode in execution_opcodes:
assert(program_counter == i)
执行当前操作码并获取下一个要执行的操作码
next_opcode = execute(opcode)
program_counter = next_opcode
```
为什么这是安全的
这是安全的，因为即使证明者可以选择任何操作码，他们也只能为任何索引选择一个操作码。这意味着他们不能跳过一个操作码，因为索引与程序计数器不匹配。此外，他们不能添加不属于那里的操作码，因为那样程序计数器将小于该操作码的索引。
重复操作码
假设我们在字节码中定义了一个 while 循环
t_opcodes = [0add, 1mul, 2jump, 3jumpdest, 4mul, 5jumpi, 6term, 7jumpdest, 8add, 9jump]
我们执行 0add, 1mul, 2jump (到索引 7), add, jump 到索引 3 ,如果 stack[0] == 1 则 mul 跳到索引 6，否则 term。
这是一种 while 循环，我们继续将前两个堆栈元素相乘，直到 stack[0] == 0，然后退出。
那么这如何与 plookup 一起工作。我们的证明者计算出我们的 while 循环需要执行多少次，并基于此构造我们的执行跟踪。这可以是可变的，具体取决于需要多少次迭代。例如，假设我们进行 4 次迭代
execution_opcodes = [0add, 1mul, 2jump, 7jumpdest, 8add, 9jump, 3jumpdest, 4mul , 5jumpi, 3jumpdest, 4mul , 5jumpi, 3jumpdest, 4mul , 5jumpi, 3jumpdest, 4mul , 5jumpi, term ]
这在我们的 evm 证明中效果很好。我们的执行证明的操作码被启用，我们只需要担心那些被启用的操作码。我们的证明者通过按顺序提供这些操作码来提供帮助。但他们不能作弊，因为我们在 evm 证明中检查每个索引和操作码。
我们可以在操作码级别上这样做吗？
有些操作码实际上是多个操作码。例如，add 实际上是 4 个操作码
1. 从堆栈中弹出第一个元素
2. 从堆栈中弹出第二个元素
3. 将这些元素加在一起
4. 将结果压入堆栈。
t_opcodes= [0add,1term]
然后，我们向我们的约束选择器多项式添加一个 opcode_counter 的概念（类似于 program_counter）。
execution_opcodes = [0add, 0add, 0add, 0add]
```python=
def execution_proof(execution_opcodes):
program_counter = 0
opcode_counter = 0
for i, opcode in execution_opcodes:
assert(program_counter == i)
执行当前操作码并获取下一个要执行的操作码
next_opcode, opcode_counter = execute(opcode, opcode_counter)
program_counter = next_opcode
```
然后在我们的 execute add 期间，我们更新 opcode_counter 3 次，然后在我们执行加法的最后一步时最终更新 program_counter。
另一个例子：returndatacopy
returndatacopy 是一个难以支持的操作码，因为迭代次数取决于返回数据的大小，而返回数据的大小是可变的。为了支持这一点，我们使用了与 add 类似的技巧，但有一个可变检查而不是恒定的 4 次重复。
```python=
def execution_proof(execution_opcodes):
program_counter = 0
opcode_counter = 0
for i, opcode in execution_opcodes:
assert(program_counter == i)
执行当前操作码并获取下一个要执行的操作码
next_opcode, opcode_counter = execute(opcode, opcode_counter)
if (opcode_counter == returndatasize):
program_counter += 1
```
现在我们可以重复 returndatacopy，直到所有数据都已复制到堆栈上。我们让证明者提供我们需要重复的次数，而 evm 证明只验证这是否足以复制所有数据。
另一个例子：哈希函数
关于哈希函数的一个非常令人讨厌的事情是，与我们的任何其他操作码相比，它们在 zkp 中需要更多的约束。因此，如果我们要包含它们，我们将不得不为每个其他操作码添加恒定的开销。我们可以通过使用与 add 类似的技巧来避免这种情况。只需重复哈希函数的轮次，直到所有内容都已执行完毕。
