TON 虚拟机 - 第一章：概述

1. 概述

本章概述了 TVM 的主要功能和设计原则，后续章节将详细讨论每个主题。

1.0 比特串的符号表示

在本文中，我们将使用以下符号表示比特串（bitstrings），即由二进制数字（比特）0 和 1 组成的有限字符串。

1.0.1 十六进制表示法：当比特串的长度是 4 的倍数时，我们将其划分为四比特一组，并以 0-9 和 A-F 的十六进制数字表示每组，如：

• 0₁₆ ↔ 0000₂
• 1₁₆ ↔ 0001₂
• F₁₆ ↔ 1111₂
  得到的十六进制字符串就是比特串的等效表示。

1.0.2 长度非四的倍数的比特串：如果比特串的长度不是 4 的倍数，我们在其末尾添加一个 1 和若干（可能是 0 个） 0，使其长度变为 4 的倍数，然后按上述方式转换为十六进制字符串。为了表明此类转换，我们在十六进制字符串末尾加上特殊符号“”作为补全标记。
例如，8A 对应的二进制串是 10001010，而 8A 和 8A0 均对应二进制串 100010。空比特串可以表示为‘’、‘8’、‘0’、‘’或‘00_’。

1.0.3 强调字符串是比特串的十六进制表示：有时我们需要强调某个十六进制字符串是比特串的表示。此时，我们可以在字符串前加上 x（如 x8A）或使用 x{和}将其括起来（如 x{2D9_} 表示 00101101100）。

1.0.4 比特串的序列化为八位字节序列：当需要将比特串表示为由 8 位字节（取值为 0 到 255 的整数）组成的序列时，可以类似处理：将比特串划分为 8 位一组，并将每组作为无符号整数解释。如果比特串的长度不是 8 的倍数，则在末尾添加一个二进制 1 和最多 7 个二进制 0。处理后的字节序列即为比特串的等效表示。

1.1 TVM 是栈机

首先，TVM 是一种栈机。这意味着与将值存储在“变量”或“通用寄存器”中不同，TVM 将值保存在一个栈中（后进先出，LIFO），至少从“低级别”（TVM）的角度看是这样。

大多数操作和用户定义的函数从栈顶获取参数，并将结果替换这些参数。例如，整数加法原语（内置操作）ADD 不需要任何参数来描述哪些寄存器或立即数应相加，或者结果应存储在哪里。相反，它从栈顶取出两个值，将它们相加，并将它们的和放入栈顶。

高层的智能合约编程语言可能会为编程方便而创建变量的“可见性”；然而，这些操作在编译为 TVM 机器代码时，所有变量的值仍会保存在 TVM 的栈中。

1.1.1 TVM 值

可以存储在 TVM 栈中的实体称为 TVM 值，或者为简便起见称为“值”。它们属于预定义值类型中的一种，每个值都属于某个具体的值类型。值在栈中始终与唯一确定其类型的标签一起保存，所有内置的 TVM 操作（即原语）只接受特定类型的值。

例如，整数加法原语 ADD 只接受两个整数值，并返回一个整数结果。不能用两个字符串代替两个整数来传递给 ADD，期望它们会被拼接，或被隐式转换为它们的十进制整数值。任何这样的操作都将导致运行时的类型检查异常。

1.1.2 静态类型、动态类型和运行时类型检查

从某些方面来看，TVM 执行了一种动态类型检查，即运行时的类型检查。然而，这并不意味着 TVM 代码是像 PHP 或 JavaScript 那样的“动态类型”语言，因为所有的原语只接受并返回预定义类型的值，每个值严格属于一种类型，且值从不被隐式转换为另一种类型。

与传统的微处理器机器代码相比，TVM 的值标记机制防止了使用字符串的地址作为数字，或错误地使用数字作为字符串的地址，避免了由无效内存访问引发的内存损坏或段错误。这一特性对于执行智能合约的虚拟机来说非常重要。因此，TVM 对所有值类型进行标签检查，而不是根据操作的需要重新解释寄存器中的位序列，提供了一种额外的运行时类型安全机制。

一种替代方式是，在允许智能合约代码在虚拟机中执行之前，甚至在将其上传到区块链中作为智能合约的代码之前，分析其类型正确性和类型安全性。然而，对于图灵完备的机器来说，对代码进行静态类型检查是一个耗时且复杂的问题，可能与图灵机的停机问题等价，因此我们希望在区块链智能合约的背景下避免这种复杂性。

需要注意的是，用户始终可以将静态类型的高级智能合约语言编译为 TVM 代码（我们也确实预期大部分 TON 智能合约会以这样的语言编写），就像可以将静态类型语言编译为常规机器代码（例如 x86 架构）一样。如果编译器工作正常，生成的机器代码将永远不会引发运行时类型检查异常。所有在 TVM 中处理的值的类型标签都将是预期的，除了 TVM 的运行时生成和验证这些类型标签会略微降低代码执行速度外，这些标签在分析 TVM 代码时可以被安全地忽略。

1.1.3 值类型的初步列表

TVM 支持的值类型的初步列表如下：

• 整数：带符号的 257 位整数，表示 -2^256 到 2^256 - 1 范围内的整数值，以及特殊的“非数字”值 NaN。
• 单元：TVM 单元最多包含 1023 位数据，以及最多 4 个对其他单元的引用。TON 区块链中的所有持久数据（包括 TVM 代码）都表示为 TVM 单元的集合。
• 元组：最多包含 255 个元素的有序集合，每个元素可能具有不同的值类型。可用于表示任意代数数据类型的非持久值。
• 空值：仅包含一个值 ⊥，用于表示空列表、二叉树的空分支、某些情况下的返回值缺失等。
• 切片：TVM 单元的切片，即现有单元的一个连续的“子单元”，包含其部分数据位和部分引用。切片用于解包先前存储（或序列化）的单元或单元树中的数据。
• 生成器：TVM 单元生成器，即一个“未完成”的单元，支持快速在其末尾附加比特串和单元引用的操作。生成器用于将栈顶的数据打包（或序列化）为新单元（例如，在将数据转移到持久存储之前）。
• 延续：表示 TVM 的一个“执行令牌”，可以稍后调用（执行）。它是函数地址（即函数指针和引用）、子程序返回地址、指令指针地址、异常处理器地址、闭包、部分应用、匿名函数等的泛化。

此列表并不完整，未来可能会在不破坏旧 TVM 代码的前提下进行扩展。进一步的值类型扩展和向后兼容性机制将在后续章节中讨论。

1.2 TVM 指令的类别

TVM 指令，也称为原语，有时也被称为（内置）操作，它们是 TVM 中可以存在的、最小的原子操作。这些指令根据它们处理的值类型（参见 1.1.3）分为几类。最重要的类别包括：

• 栈（操作）原语 — 用于在 TVM 栈中重新排列数据，使得其他原语和用户定义的函数可以以正确的参数顺序被调用。与大多数其他原语不同，栈原语是多态的，也就是说它们可以操作任意类型的值。

• 元组（操作）原语 — 用于构建、修改和解构元组。与栈原语类似，它们也是多态的。

• 常量或字面量原语 — 将“常量”或“字面量”值推入栈中，这些值嵌入在 TVM 代码中，为其他原语提供参数。它们与栈原语类似，但它们的通用性较低，因为它们仅适用于特定类型的值。

• 算术原语 — 执行整数类型的值的常规整数算术运算。

• 单元（操作）原语 — 用于创建新单元并向其存储数据（单元创建原语），或从先前创建的单元读取数据（单元解析原语）。由于 TVM 的所有内存和持久存储都由单元组成，这些单元操作原语实际上相当于其他架构中的“内存访问指令”。单元创建原语通常与生成器类型的值一起使用，而单元解析原语则与切片类型的值一起使用。

• 延续与控制流原语 — 用于创建和修改延续，以及以不同方式执行现有的延续，包括条件和重复执行。

• 自定义或应用特定原语 — 用于高效地执行应用程序（在我们的案例中是 TON 区块链）所需的特定高级操作，如计算哈希函数、执行椭圆曲线加密、发送新的区块链消息、创建新的智能合约等。这些原语类似于标准库函数，而不是微处理器指令。

1.3 控制寄存器

尽管 TVM 是一种栈机，有些不经常更改、但几乎所有函数都需要的值，最好存储在某些特殊寄存器中，而不是栈顶。否则，管理这些值将需要过多的栈重排操作。

为此，TVM 模型除了栈外，还包括最多 16 个特殊控制寄存器，标记为 c0 到 c15，或 c(0) 到 c(15)。原始版本的 TVM 仅使用其中的一部分寄存器，其余寄存器可能会在将来支持。

1.3.1 存储在控制寄存器中的值
存储在控制寄存器中的值与存储在栈中的值类型相同。然而，某些控制寄存器只接受特定类型的值，尝试加载其他类型的值将会导致异常。

1.3.2 控制寄存器列表
TVM 的原始版本定义并使用以下控制寄存器：

• c0 — 包含下一个延续或返回延续（类似于传统设计中的子程序返回地址）。此值必须是延续类型。
• c1 — 包含备用（返回）延续；此值也必须是延续类型。它用于某些（实验性）控制流原语，允许 TVM 定义并调用“带有两个退出点的子程序”。
• c2 — 包含异常处理器。此值为延续类型，当触发异常时将被调用。
• c3 — 包含当前字典，本质上是一个包含程序中所有函数代码的哈希映射。此值也是延续类型，而不是预期的单元类型，后续章节将对此进行解释。
• c4 — 包含持久数据的根节点，或者简称为数据。此值为单元类型。当智能合约代码被调用时，c4 指向其持久数据的根单元（该数据存储在区块链状态中）。如果智能合约需要修改这些数据，它在返回之前会修改 c4。
• c5 — 包含输出操作。它也是一个初始化为空单元的单元，但其最终值被视为智能合约的输出之一。例如，TON 区块链特定的 SENDMSG 原语会将消息插入存储在输出操作中的列表中。
• c7 — 包含临时数据的根节点。此值为元组类型，在调用智能合约前被初始化为空元组引用，并在合约终止后被丢弃。

更多的控制寄存器可能会在未来根据特定的 TON 区块链或高级编程语言的需求定义。

1.4 TVM 的整体状态（SCCCG）

TVM 的整体状态由以下几个部分组成：

• 栈（参见 1.1）：包含零个或多个值（参见 1.1.1），每个值属于 1.1.3 中列出的值类型之一。
• 控制寄存器 c0–c15：包含一些特定的值，如 1.3.2 中所述（当前版本只使用了 7 个控制寄存器）。
• 当前延续（cc）：包含当前的延续，即当前原语执行完毕后正常执行的代码。这个组件类似于其他架构中的指令指针寄存器（ip）。
• 当前代码页（cp）：一个特殊的带符号 16 位整数值，用来选择下一个 TVM 操作码的解码方式。例如，未来版本的 TVM 可能会使用不同的代码页来添加新操作码，同时保持向后兼容性。
• Gas 限制（gas）：包含四个带符号的 64 位整数：当前的 gas 限制（gl）、最大 gas 限制（gm）、剩余 gas（gr）和 gas 贷记（gc）。始终满足 0 ≤ gl ≤ gm，gc ≥ 0，且 gr ≤ gl + gc；gc 通常初始化为 0，gr 初始化为 gl + gc，并随着 TVM 的运行逐渐减少。当 gr 变为负值或最终值小于 gc 时，将触发“gas 用尽”异常。

注意，这里没有“返回栈”来保存所有先前调用但未完成的函数的返回地址。取而代之的是使用控制寄存器 c0，原因将在 4.1.9 中解释。

此外，TVM 没有通用寄存器，因为 TVM 是一个栈机（参见 1.1）。因此，上述列表可以概括为“栈、控制、延续、代码页和 gas”（SCCCG），类似于经典的 SECD 机器状态（“栈、环境、控制、转储”），这确实构成了 TVM 的整体状态。

1.5 整数运算

TVM 的所有算术原语都对栈顶的整数值进行操作，并将结果（同为整数类型）放回栈中。回顾一下，整数代表的是 -2²⁵⁶ ≤ x < 2²⁵⁶ 范围内的整数值，此外还包含一个特殊的 NaN（非数字）值。

如果结果超出了支持的整数范围，或者参数之一是 NaN，那么结果将被替换为 NaN，且默认情况下会生成整数溢出异常。然而，某些特殊的“安静”版本的算术操作只会产生 NaN 并继续执行。如果这些 NaN 被用于非“安静”的算术操作或非算术操作，将触发整数溢出异常。

1.5.1 无自动整数转换
注意，TVM 中的整数是“数学”意义上的整数，而不是像其他机器代码设计中那样，使用不同的原语时将 257 位的字符串重新解释。例如，TVM 只有一个乘法原语 MUL，而不像流行的 x86 架构那样有两个乘法原语（MUL 用于无符号乘法，IMUL 用于有符号乘法）。

1.5.2 自动溢出检查
TVM 的所有算术原语都会执行结果的溢出检查。如果结果不适合整数类型，它将被替换为 NaN，通常还会引发异常。特别是，结果不会像大多数硬件机器代码架构那样自动进行模 2²⁵⁶ 或模 2²⁵⁷ 的运算。

1.5.3 自定义溢出检查
除了自动溢出检查，TVM 还提供了自定义溢出检查原语 FITS n 和 UFITS n（其中 1 ≤ n ≤ 256）。这些原语用于检查栈顶的值是否在 -2^n-1 ≤ x < 2^n-1 或 0 ≤ x < 2ⁿ 范围内，如果不在此范围内，则将值替换为 NaN，并（可选）生成整数溢出异常。这极大简化了任意 n 位整数类型的实现，无论是有符号还是无符号类型：程序员或编译器必须在每次算术操作之后插入适当的 FITS 或 UFITS 原语（这更合理，但需要更多检查），或者在存储计算值并返回函数之前插入这些原语。这对于智能合约尤其重要，因为意外的整数溢出往往是错误的最常见原因之一。

1.5.4 模 2ⁿ 还原
TVM 还提供了一个原语 MODPOW2 n，它将栈顶的整数按 2ⁿ 取模，结果在 0 到 2ⁿ-1 之间。

1.5.5 整数是 257 位而非 256 位
现在可以理解为什么 TVM 中的整数是带符号的 257 位而不是 256 位。原因在于它是包含 256 位有符号整数和 256 位无符号整数的最小整数类型，不需要根据所使用的操作自动重新解释相同的 256 位字符串。

1.5.6 除法与取整
TVM 最重要的除法原语是 DIV、MOD 和 DIVMOD。它们从栈中取出两个整数参数 x 和 y（y 在栈顶，x 在 y 之下），计算商 q 和余数 r（即两个整数，使得 x = yq + r 且 |r| < |y|），然后返回 q、r 或两者。如果 y 为 0，所有期望的结果将被替换为 NaN，且通常会触发整数溢出异常。

TVM 的除法实现与大多数其他实现不同，尤其是在取整方面。默认情况下，这些原语向负无穷大取整，即 q = ⌊x/y⌋，且 r 与 y 同号（大多数常规实现使用“向零取整”，即 r 与 x 同号）。除了这种“向下取整”，还提供了其他两种取整模式，分别是“向上取整”（q = ⌈x/y⌉，r 和 y 异号）和“最近取整”（q = ⌊x/y + 1/2⌋ 且 |r| ≤ |y|/2）。这些取整模式由带有 C 和 R 后缀的其他除法原语选择。例如，DIVMODR 使用最近取整模式来计算商和余数。

1.5.7 组合乘除、乘移和移除操作
为了简化定点算术的实现，TVM 支持具有双长度（即 514 位）中间乘积的组合乘除、乘移和移除操作。例如，MULDIVMODR 从栈中取出三个整数参数 a、b 和 c，首先使用 514 位的中间结果计算 ab，然后将 ab 除以 c，结果四舍五入为最接近的整数。如果 c 为 0 或商不适合整数类型，则返回两个 NaN，或生成整数溢出异常，具体取决于使用的是安静版还是非安静版的操作。否则，商和余数都将被推入栈中。