在 ZK 中建模栈数据结构 - 如何在 Circom 中创建一个堆栈

RareSkills
发布于 5小时前
阅读 27

本文详细介绍了如何在 Circom 中创建一个栈数据结构，以及如何使用零知识证明（ZK proofs）来验证栈的操作，包括 push、pop 和 no change。通过定义栈的最大高度和使用栈指针（stack pointer）来跟踪栈的使用情况，并详细描述了在不同操作下栈状态的转换和约束。

本教程展示了如何在 Circom 中创建一个堆栈。

请注意——本章内容较长。

然而，关于堆栈创建 ZK 证明的策略，在我们下一章创建一个简单的 ZK 虚拟机 (ZKVM) 时至关重要。理解 ZKVM 工作原理的大部分工作已提前在本章完成。

堆栈能够将数字 **push** 到堆栈顶部，**pop** 堆栈顶部，或者 **不做任何更改**。

堆栈本质上是可变的，但在 Circom 中，我们只允许使用不可变数组。因此，堆栈必须用不可变数组建模。每次堆栈更改（通过 pop 或 push）时，我们都会创建一个新数组来表示新的堆栈状态。

这可能看起来效率不高，但这是没有办法的，因为 ZK 中的信号是不可变的（更高级的 ZK 技术有优化此问题的方法，但该讨论超出了本文的范围）。

第一个要求是堆栈具有固定的“最大高度”——也就是不可变数组的长度。为了跟踪堆栈有多少被“使用”，我们使用一个单独的变量，称为“栈指针”，它是一个从零开始的索引，告诉我们下一个项目应该 **push** 到哪里。`sp` 指向数组中一个未使用的位置，应该在此处 **push** 一个新值，该位置比堆栈顶部高一个索引。下图展示了一个包含三个项目 10、16 和 20 的堆栈：

$$
\begin{align*}\texttt{sp}=3\\
\begin{array}{|c|c|c|c|c|c|c|}
\hline
\text{array}&10 & 16 & 20 & \circ &  \space &  \space \\ \hline
\text{index}&0 & 1 &2 &3 &4 &5\\
\hline
\end{array}
\end{align*}
$$

栈指针 `sp` 指向索引 3，该索引为空，用 $\circ$ 表示。堆栈忽略索引 3（当前的 `sp`）或更大的任何值。它们可能具有非零值，但电路不会考虑它们。

假设我们将项目 `21` **push** 到堆栈上。这意味着我们递增栈指针并复制所有先前的值。更新后的堆栈现在有 `sp` = 4。

$$
\begin{align*}\texttt{sp}=4\\
\begin{array}{|c|c|c|c|c|c|}
\hline
10& 16 & 20 &  \circ &  \space \\ \hline
10 & 16 & 20 & 21&  \circ &  \space \\ \hline
\end{array}
\end{align*}
$$

如果我们从堆栈中 **pop**，则 `sp` 会递减，我们不会将值 `21` 复制到下一个堆栈中：

$$ 
\begin{align*}\texttt{sp}=3\\
\begin{array}{|c|c|c|c|c|c|}
\hline
10 & 16 & 20 &  \circ &  \space \\ \hline
10 & 16 & 20 & 21&  \circ &  \space \\ \hline
10 & 16 & 20 & \circ&  \space &  \space \\ \hline
\end{array}
\end{align*}
$$

如果堆栈没有发生任何变化，我们仍然会经历某种计算步骤，我们只是将所有先前的值复制到下一个堆栈。

由于 `sp` 每次迭代都会变化，我们需要每次都将新值存储在一个新的信号中，因为一旦赋值，信号的值就无法更新。因此，我们使用一个数组来跟踪每次迭代时 `sp` 的值：

$$
\begin{array}{|c||c|c|c|c|c|c|}
\hline
\texttt{sp}\downarrow & \\
\hline
3 & 10 & 16 & 20 &  \circ &  \space \\ \hline
4 & 10 & 16 & 20 & 21&  \circ &  \space \\ \hline
3 &10 & 16 & 20 & \circ&  \space &  \space \\ \hline
3 &10 & 16 & 20 & \circ&  \space &  \space \\ \hline
\end{array}
$$

正如堆栈有一个最大高度一样，我们也可以更新它的最大次数，因为模拟堆栈的表（底层是一个 2D Circom 数组）必须是固定大小的。

最大大小取决于我们的应用。在区块链环境中，不太可能执行 100 万条指令，但在为更密集的应用创建电路时，我们可能需要分配一个更大的电路来容纳潜在的堆栈大小。

### 堆栈的约束

无论我们 **push**、**pop** 还是什么都不做，从 0 到 `sp - 2`（包括）的项目都需要复制（并约束为相等）到下一个堆栈。在下面的示例中，栈指针在 4，然后我们执行了一个 **pop** 操作，栈指针变为 3。栈指针索引 0、1、2（橙色部分）中的项目被复制。

$$ 
\begin{array}{|c||c|c|c|c|c|c|}
\hline
\texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\\
\hline
4 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & 21&  \circ &  \space \\ \hline
3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ&  \space &  \space \space \\ \hline
\end{array}
$$

如果指令是 **pop**，那么我们还需要新的栈指针比前一个少 1。

### Push 的约束

在 **push** 期间，所有直到 `sp - 1` 的值都必须复制到新的堆栈中（注意，栈指针指向一个空区域，因此不需要复制它）。`sp - 1` 处的值必须约束为 **push** 的值。

$$
\begin{array}{|c||c|c|c|c|c|c|}
\hline
\texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\\
\hline
3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ&  \space &  \space
\space \\ \hline
4 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & 24&  \circ &  \space \\ \hline
\end{array}
$$

在上面的示例中，栈指针为 3，我们复制了 0、1、2 中的项目。我们还约束栈指针递增 1。我们还必须约束栈指针比之前的栈指针大 1。

### Pop 的约束

在 **pop** 期间，所有直到 `sp - 2` 的值都必须复制到新的堆栈中。我们约束栈指针递减 1。

$$
\begin{array}{|c||c|c|c|c|c|c|}
\hline
\texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\\
\hline
3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ&  \space &  \space
\space \\ \hline
2 & \color{orange}{10} & \color{orange}{16} & \circ & &  &  \space \\ \hline
\end{array}

### Nop（不执行任何操作）的约束

所有直到 `sp - 1` 的值必须约束为相同。`sp` 必须约束为等于前一次迭代的值。

$$ 
\begin{array}{|c||c|c|c|c|c|c|}
\hline
\texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\\
\hline
3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ&  \space &  \space
\space \\ \hline
3 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& &  \space \\ \hline
\end{array}
$$

## 根据一组指令更新堆栈

在指令的每次迭代中，我们需要知道我们是 **push** 一个数字，**pop** 顶部，还是什么都不做，我们将用“操作码”或“指令”PUSH、POP 或 NOP 表示。

例如，假设我们得到指令 `PUSH 10 POP PUSH 16 PUSH 15 PUSH 4 NOP POP`。我们可以将这组指令表示为一个数组：

[PUSH, 10, POP, 0, PUSH, 16, PUSH, 15, PUSH, 4, NOP, 0, POP, 0]

不失一般性，我们可以将 PUSH 称为数字 1，POP 称为 2，NOP 称为 0，因此指令可以编码如下。

$$
\begin{matrix}
1 & 10 & 2 & 0 & 1 & 16 & 1 & 15 & 1 & 4 & 0 & 0 & 2&  0\\
\texttt{PUSH}&&\texttt{POP}&&\texttt{PUSH}&&\texttt{PUSH}&&\texttt{PUSH}&&\texttt{NOP}&&\texttt{POP}
\end{matrix}
$$

请注意，每条指令后都有一个常数。对于 PUSH，这是要 **push** 的值，但对于 POP 和 NOP，之后的常数将被忽略。将指令放在索引 0,2,4,… 等等处，允许我们以步长 2 迭代指令。换句话说，如果指令可以有参数也可以没有参数，那么我们将需要根据是否有参数来更改步长。这个有条件的步长增加了我们例子的复杂性，因此我们将操作码放在均匀的间隔上，以便我们始终可以进行步长为 2 的操作。

现在，让我们生成一个“metaTable”，它告诉我们每次执行的哪一行会发生哪个操作。如果我们添加列 `is_push`、`is_pop` 或 `is_nop`，指示哪个指令处于活动状态，那么我们将得到下表。

https://img.learnblockchain.cn/2025/04/16/stack.mp4

最终结果如下所示，但我们将在接下来的部分中逐步重建此表：

$$ 
\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 10 & – & – & – \\\hline0 & \color{orange}{1} & 0 & – & 1 & – & – & – & – \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 16 & – & – & – \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & 16 & 15 & – & – \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & 16 & 15 & 4 & – \\\hline0 & 0 & \color{orange}{1} & – & 3 & 16 & 15 & 4 & – \\\hline0 & \color{orange}{1} & 0 & – & 3 & 16 & 15 & – & – \\\hline\end{array}
$$

`sp` 的解释是，如果当前指令是 **push**，则下一个值应该写入的位置。如果指令是 `pop`，则 `sp - 1` 是不应该复制的项目。

## 填充表格

要从 `is_push` 到 `arg` 填充表格，我们可以简单地在一个循环中复制指令，如果当前指令是 PUSH，则将 `is_push` 设置为 1，对于其他指令也是如此。我们将得到以下结果：

$$
\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & & & & & \\\hline0 & \color{orange}{1} & 0 & – & & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\\hline0 & 0 & \color{orange}{1} & – & & & & & \\\hline0 & \color{orange}{1} & 0 & – & & & & & \\\hline\end{array}
$$

栈指针必须始终从零开始，所以我们可以简单地硬编码：

$$
\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_apop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & \boxed{0}& & & & \\\hline0 & \color{orange}{1} & 0 & – & & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\\hline0 & 0 & \color{orange}{1} & – & & & & & \\\hline0 & \color{orange}{1} & 0 & – & & & & & \\\hline\end{array}

如果指令是 PUSH，则递增它，对于 POP 则递减它，对于 NOP 则保持不变，我们可以填充剩余的栈指针列。请注意，我们根据当前行更新 **next** `sp`。因此，在迭代 0 时，我们按如下方式更新第 1 行：

$$
\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_apop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & \boxed{0}& & & & \\\hline0 & \color{orange}{1} & 0 & – & \boxed{1}& & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\\hline0 & 0 & \color{orange}{1} & – & & & & & \\\hline0 & \color{orange}{1} & 0 & – & & & & & \\\hline\end{array}
$$

也就是说，因为当前的 `is_push` 是 1，并且当前的 `sp` 是 0，我们将 0 + 1 写入下一个单元格。然后我们按如下方式填充 `sp` 列的其余部分：

$$
\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & & & & \\\hline0 & \color{orange}{1} & 0 & – & 1 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & & \\\hline0 & 0 & \color{orange}{1} & – & 3 & & & & \\\hline0 & \color{orange}{1} & 0 & – & 3 & & & & \\\hline\end{array}
$$

然后我们通过使用 `sp` 和 `arg` 列（如果 `is_push` 是 1）将 **push** 值写入适当的单元格。请注意，只有 `is_push == 1` 的行才会在这一步中填充：

$$ 
\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & – & 1 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & 4 & \\\hline0 & 0 & \color{orange}{1} & – & 3 & & & & \\\hline0 & \color{orange}{1} & 0 & – & 3 & & & & \\\hline\end{array}
$$

请注意，先前的值没有复制过来——我们将在后面的部分中修复它。

### 处理第零行

第零行是唯一的，因为它不复制上一行的值。为了避免不得不根据我们是否在第零行进行分支，我们将表做得比它需要的行数多一行，然后我们开始在第 1 行构建我们的约束。这样，每一行总是复制它上面的行。

在即将到来的代码演示中，我们硬连接了第 0 行中的约束，因为稍后，将第 0 行视为我们是否复制上一行值的极端情况是不方便的。

## 复制上一行

现在，我们需要确保从一行到下一行的值被正确复制。一个单元格复制它上面的值，直到下一行的栈指针减 1。请记住，`sp` 指向上方堆栈的空闲空间，因此 `sp - 1` 指向堆栈的顶部。

### 列和堆栈术语

因为我们将堆栈“横向”存储在一个表中，我们将把堆栈的底部称为第 0 列，该列顶部的项目（如果存在）称为第 1 列，依此类推。当我们说“列”时，我们的意思是堆栈的“索引”（如果底部为零）。

### 复制的约束

1. 如果 `is_push = 1`，则必须复制堆栈 `0..sp - 1`（包括）的所有项目。`sp` 处的单元格将包含新的递增值。这将复制整个堆栈。
  2. 如果 `is_nop = 1`，则必须复制堆栈 `0..sp - 1`（包括）的所有项目。没有任何内容写入到 `sp` 处的单元格。这将复制整个堆栈。
  3. 如果 `is_pop = 1`，则必须复制堆栈 `0..sp - 2`（包括）的所有项目。请记住，`sp` 指向堆栈上方的空单元格，因此 `sp - 1` 是将被 **pop** 的值。必须复制 `sp - 2` 和下面的所有内容。这将复制除了堆栈顶部之外的所有内容。

如果栈指针分别是 0 或 1，则条件 2 和 3 存在极端情况，因为会发生下溢。因此，我们需要特殊的列来指示 `sp` 是否小于 2 或 1，我们需要以不同的方式处理复制。具体来说：

* 如果 `sp = 0`，则不会复制任何内容
  * 如果 `sp = 1`，只有当指令是 NOP 或 PUSH 时，我们才会复制第 0 列的单元格

我们创建额外的列（`copy0`、`copy1`、`copy2`、`copy3`）作为标志，分别指示 (`column0`、`column1`、`column2`、`column3`) 的值是否将被复制到下一行。

$$ 
\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & & & & & 10 & & & \\\hline0 & \color{orange}{1} & 0 & – & 1 & & & & & & &...

本教程展示了如何在 Circom 中创建一个堆栈。

请注意——本章内容较长。

然而，关于堆栈创建 ZK 证明的策略，在我们下一章创建一个简单的 ZK 虚拟机 (ZKVM) 时至关重要。理解 ZKVM 工作原理的大部分工作已提前在本章完成。

堆栈能够将数字 push 到堆栈顶部，pop 堆栈顶部，或者 不做任何更改。

这可能看起来效率不高，但这是没有办法的，因为 ZK 中的信号是不可变的（更高级的 ZK 技术有优化此问题的方法，但该讨论超出了本文的范围）。

第一个要求是堆栈具有固定的“最大高度”——也就是不可变数组的长度。为了跟踪堆栈有多少被“使用”，我们使用一个单独的变量，称为“栈指针”，它是一个从零开始的索引，告诉我们下一个项目应该 push 到哪里。sp 指向数组中一个未使用的位置，应该在此处 push 一个新值，该位置比堆栈顶部高一个索引。下图展示了一个包含三个项目 10、16 和 20 的堆栈：

$$ \begin{align}\texttt{sp}=3\ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{array}&10 & 16 & 20 & \circ & \space & \space \ \hline \text{index}&0 & 1 &2 &3 &4 &5\ \hline \end{array} \end{align} $$

栈指针 sp 指向索引 3，该索引为空，用 $\circ$ 表示。堆栈忽略索引 3（当前的 sp）或更大的任何值。它们可能具有非零值，但电路不会考虑它们。

假设我们将项目 21 push 到堆栈上。这意味着我们递增栈指针并复制所有先前的值。更新后的堆栈现在有 sp = 4。

$$ \begin{align}\texttt{sp}=4\ \begin{array}{|c|c|c|c|c|c|} \hline 10& 16 & 20 & \circ & \space \ \hline 10 & 16 & 20 & 21& \circ & \space \ \hline \end{array} \end{align} $$

如果我们从堆栈中 pop，则 sp 会递减，我们不会将值 21 复制到下一个堆栈中：

$$ \begin{align}\texttt{sp}=3\ \begin{array}{|c|c|c|c|c|c|} \hline 10 & 16 & 20 & \circ & \space \ \hline 10 & 16 & 20 & 21& \circ & \space \ \hline 10 & 16 & 20 & \circ& \space & \space \ \hline \end{array} \end{align} $$

如果堆栈没有发生任何变化，我们仍然会经历某种计算步骤，我们只是将所有先前的值复制到下一个堆栈。

由于 sp 每次迭代都会变化，我们需要每次都将新值存储在一个新的信号中，因为一旦赋值，信号的值就无法更新。因此，我们使用一个数组来跟踪每次迭代时 sp 的值：

$$ \begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp}\downarrow & \ \hline 3 & 10 & 16 & 20 & \circ & \space \ \hline 4 & 10 & 16 & 20 & 21& \circ & \space \ \hline 3 &10 & 16 & 20 & \circ& \space & \space \ \hline 3 &10 & 16 & 20 & \circ& \space & \space \ \hline \end{array} $$

正如堆栈有一个最大高度一样，我们也可以更新它的最大次数，因为模拟堆栈的表（底层是一个 2D Circom 数组）必须是固定大小的。

堆栈的约束

无论我们 push、pop 还是什么都不做，从 0 到 sp - 2（包括）的项目都需要复制（并约束为相等）到下一个堆栈。在下面的示例中，栈指针在 4，然后我们执行了一个 pop 操作，栈指针变为 3。栈指针索引 0、1、2（橙色部分）中的项目被复制。

$$ \begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\ \hline 4 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & 21& \circ & \space \ \hline 3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& \space & \space \space \ \hline \end{array} $$

如果指令是 pop，那么我们还需要新的栈指针比前一个少 1。

Push 的约束

在 push 期间，所有直到 sp - 1 的值都必须复制到新的堆栈中（注意，栈指针指向一个空区域，因此不需要复制它）。sp - 1 处的值必须约束为 push 的值。

$$ \begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\ \hline 3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& \space & \space \space \ \hline 4 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & 24& \circ & \space \ \hline \end{array} $$

在上面的示例中，栈指针为 3，我们复制了 0、1、2 中的项目。我们还约束栈指针递增 1。我们还必须约束栈指针比之前的栈指针大 1。

Pop 的约束

在 pop 期间，所有直到 sp - 2 的值都必须复制到新的堆栈中。我们约束栈指针递减 1。

$$ \begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\ \hline 3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& \space & \space \space \ \hline 2 & \color{orange}{10} & \color{orange}{16} & \circ & & & \space \ \hline \end{array}

Nop（不执行任何操作）的约束

所有直到 sp - 1 的值必须约束为相同。sp 必须约束为等于前一次迭代的值。

$$ \begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\ \hline 3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& \space & \space \space \ \hline 3 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& & \space \ \hline \end{array} $$

根据一组指令更新堆栈

在指令的每次迭代中，我们需要知道我们是 push 一个数字，pop 顶部，还是什么都不做，我们将用“操作码”或“指令”PUSH、POP 或 NOP 表示。

例如，假设我们得到指令 PUSH 10 POP PUSH 16 PUSH 15 PUSH 4 NOP POP。我们可以将这组指令表示为一个数组：

[PUSH, 10, POP, 0, PUSH, 16, PUSH, 15, PUSH, 4, NOP, 0, POP, 0]

不失一般性，我们可以将 PUSH 称为数字 1，POP 称为 2，NOP 称为 0，因此指令可以编码如下。

$$ \begin{matrix} 1 & 10 & 2 & 0 & 1 & 16 & 1 & 15 & 1 & 4 & 0 & 0 & 2& 0\ \texttt{PUSH}&&\texttt{POP}&&\texttt{PUSH}&&\texttt{PUSH}&&\texttt{PUSH}&&\texttt{NOP}&&\texttt{POP} \end{matrix} $$

请注意，每条指令后都有一个常数。对于 PUSH，这是要 push 的值，但对于 POP 和 NOP，之后的常数将被忽略。将指令放在索引 0,2,4,… 等等处，允许我们以步长 2 迭代指令。换句话说，如果指令可以有参数也可以没有参数，那么我们将需要根据是否有参数来更改步长。这个有条件的步长增加了我们例子的复杂性，因此我们将操作码放在均匀的间隔上，以便我们始终可以进行步长为 2 的操作。

现在，让我们生成一个“metaTable”，它告诉我们每次执行的哪一行会发生哪个操作。如果我们添加列 is_push、is_pop 或 is_nop，指示哪个指令处于活动状态，那么我们将得到下表。

https://img.learnblockchain.cn/2025/04/16/stack.mp4

最终结果如下所示，但我们将在接下来的部分中逐步重建此表：

$$ \begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is_push} & \texttt{is_pop} & \texttt{is_nop} & \texttt{arg} & \texttt{sp} \\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 10 & – & – & – \\hline0 & \color{orange}{1} & 0 & – & 1 & – & – & – & – \\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 16 & – & – & – \\hline\color{orange}{1} & 0 & 0 & 15 & 1 & 16 & 15 & – & – \\hline\color{orange}{1} & 0 & 0 & 4 & 2 & 16 & 15 & 4 & – \\hline0 & 0 & \color{orange}{1} & – & 3 & 16 & 15 & 4 & – \\hline0 & \color{orange}{1} & 0 & – & 3 & 16 & 15 & – & – \\hline\end{array} $$

sp 的解释是，如果当前指令是 push，则下一个值应该写入的位置。如果指令是 pop，则 sp - 1 是不应该复制的项目。

填充表格

要从 is_push 到 arg 填充表格，我们可以简单地在一个循环中复制指令，如果当前指令是 PUSH，则将 is_push 设置为 1，对于其他指令也是如此。我们将得到以下结果：

$$ \begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is_push} & \texttt{is_pop} & \texttt{is_nop} & \texttt{arg} & \texttt{sp} \\hline\color{orange}{1} & 0 & 0 & 10 & & & & & \\hline0 & \color{orange}{1} & 0 & – & & & & & \\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\hline0 & 0 & \color{orange}{1} & – & & & & & \\hline0 & \color{orange}{1} & 0 & – & & & & & \\hline\end{array} $$

栈指针必须始终从零开始，所以我们可以简单地硬编码：

$$ \begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is_push} & \texttt{is_apop} & \texttt{is_nop} & \texttt{arg} & \texttt{sp} \\hline\color{orange}{1} & 0 & 0 & 10 & \boxed{0}& & & & \\hline0 & \color{orange}{1} & 0 & – & & & & & \\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\hline0 & 0 & \color{orange}{1} & – & & & & & \\hline0 & \color{orange}{1} & 0 & – & & & & & \\hline\end{array}

如果指令是 PUSH，则递增它，对于 POP 则递减它，对于 NOP 则保持不变，我们可以填充剩余的栈指针列。请注意，我们根据当前行更新 next sp。因此，在迭代 0 时，我们按如下方式更新第 1 行：

$$ \begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is_push} & \texttt{is_apop} & \texttt{is_nop} & \texttt{arg} & \texttt{sp} \\hline\color{orange}{1} & 0 & 0 & 10 & \boxed{0}& & & & \\hline0 & \color{orange}{1} & 0 & – & \boxed{1}& & & & \\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\hline0 & 0 & \color{orange}{1} & – & & & & & \\hline0 & \color{orange}{1} & 0 & – & & & & & \\hline\end{array} $$

也就是说，因为当前的 is_push 是 1，并且当前的 sp 是 0，我们将 0 + 1 写入下一个单元格。然后我们按如下方式填充 sp 列的其余部分：

$$ \begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is_push} & \texttt{is_pop} & \texttt{is_nop} & \texttt{arg} & \texttt{sp} \\hline\color{orange}{1} & 0 & 0 & 10 & 0 & & & & \\hline0 & \color{orange}{1} & 0 & – & 1 & & & & \\hline\color{orange}{1} & 0 & 0 & 16 & 0 & & & & \\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & & & \\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & & \\hline0 & 0 & \color{orange}{1} & – & 3 & & & & \\hline0 & \color{orange}{1} & 0 & – & 3 & & & & \\hline\end{array} $$

然后我们通过使用 sp 和 arg 列（如果 is_push 是 1）将 push 值写入适当的单元格。请注意，只有 is_push == 1 的行才会在这一步中填充：

$$ \begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is_push} & \texttt{is_pop} & \texttt{is_nop} & \texttt{arg} & \texttt{sp} \\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 10 & & & \\hline0 & \color{orange}{1} & 0 & – & 1 & & & & \\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 16 & & & \\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & 15 & & \\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & 4 & \\hline0 & 0 & \color{orange}{1} & – & 3 & & & & \\hline0 & \color{orange}{1} & 0 & – & 3 & & & & \\hline\end{array} $$

请注意，先前的值没有复制过来——我们将在后面的部分中修复它。

处理第零行

在即将到来的代码演示中，我们硬连接了第 0 行中的约束，因为稍后，将第 0 行视为我们是否复制上一行值的极端情况是不方便的。

复制上一行

现在，我们需要确保从一行到下一行的值被正确复制。一个单元格复制它上面的值，直到下一行的栈指针减 1。请记住，sp 指向上方堆栈的空闲空间，因此 sp - 1 指向堆栈的顶部。

列和堆栈术语

复制的约束

如果 is_push = 1，则必须复制堆栈 0..sp - 1（包括）的所有项目。sp 处的单元格将包含新的递增值。这将复制整个堆栈。
如果 is_nop = 1，则必须复制堆栈 0..sp - 1（包括）的所有项目。没有任何内容写入到 sp 处的单元格。这将复制整个堆栈。
如果 is_pop = 1，则必须复制堆栈 0..sp - 2（包括）的所有项目。请记住，sp 指向堆栈上方的空单元格，因此 sp - 1 是将被 pop 的值。必须复制 sp - 2 和下面的所有内容。这将复制除了堆栈顶部之外的所有内容。

如果栈指针分别是 0 或 1，则条件 2 和 3 存在极端情况，因为会发生下溢。因此，我们需要特殊的列来指示 sp 是否小于 2 或 1，我们需要以不同的方式处理复制。具体来说：

如果 sp = 0，则不会复制任何内容
如果 sp = 1，只有当指令是 NOP 或 PUSH 时，我们才会复制第 0 列的单元格

我们创建额外的列（copy0、copy1、copy2、copy3）作为标志，分别指示 (column0、column1、column2、column3) 的值是否将被复制到下一行。

$$ \begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is_push} & \texttt{is_pop} & \texttt{is_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\hline\color{orange}{1} & 0 & 0 & 10 & 0 & & & & & 10 & & & \\hline0 & \color{orange}{1} & 0 & – & 1 & & & & & & &...