跳到主要内容

图灵完备性

Utxo合约图灵完备性论述。

加密生态一直存在一个误解，UTXO模型无法实现图灵完备的智能合约，最主要的论据就是UTXO模型不存在死循环，本文将针对图灵完备的问题进行解释。

什么是图灵完备​

图灵完备是指一种计算机或编程语言的能力，能够模拟图灵机的所有功能。图灵机是一种理论计算机，由英国数学家图灵提出，它是一种理想化的计算模型，能够模拟任何计算机程序。图灵完备的编程语言能够实现任何计算机程序，包括递归函数、条件判断、循环等。

图灵机是一种理论计算机，由一个无限长的纸带和一个读写头组成。纸带上分布着一系列的符号，读写头可以读取和写入符号，并根据一系列的规则进行操作。图灵机的操作包括移动读写头、读取和写入符号、改变状态等。图灵机的操作规则是一种有限状态机，它可以根据当前的状态和读取的符号来决定下一步的操作。

那么根据图灵完备的定义，能够完整实现图灵机功能的就是图灵完备。注意这里存在一个前提，那就是无限长的纸带，它的实现前提是无限的内存或者执行时间。但是真实世界受限于物理规则，资源始终有限，真正意义上的解决所有可计算问题的计算机是不存在的。我们通常认可的图灵完备编程语言和程序，比如高级编程语言，ETH合约等，都不能实现无限的循环，也只能算是近似意义上的图灵完备。

以ETH合约为例，如果合约逻辑过于复杂或者循环次数过多，超过GAS limit，那么合约程序就会发生中断，导致无法继续执行出结果。ETH设置“GAS limit”的原因正是在于此，实际也不可能让合约无限制执行下去。

那么基于以上的论述，考虑实际计算资源和时间受限的情况下，我们其实真正讨论的是一种近似意义上的图灵完备，而不是真正意义上的图灵完备。在这种意义上，UTXO模型是可以实现近似意义上的图灵完备的，账户模型可以实现的计算，UTXO模型都可以等价实现。

图灵完备

执行范式的区别​

BVM和EVM在合约执行范式上有所不同，用编程中的概念可以将EVM类比为（命令式编程），而BVM类比为（函数式编程）。

EVM命令式编程，就是通过一系列的命令来描述程序的执行过程，比如C语言，Java等。命令式编程的特点是程序的执行过程是由一系列的命令来描述的，程序的执行过程是可变的，在编译期也很难预期最终结果。EVM在触发合约的时候，会根据合约的代码逐步执行合约状态转换，直到代码执行完毕或者GAS消耗完毕，合约结束，整个过程可以完全由EVM自行完成。同时由于无法预期合约执行的步数，在发起合约交易的时候必须指定好GAS limit。其特点如下：

  1. 合约的状态是全局的，合约的执行过程中需要维护全局状态，因此对同一状态的修改必须串行执行。
  2. 发起合约只需要一笔交易，合约内部的状态转移可以是多次的并且由EVM自动进行状态转移。
  3. 多笔合约的触发必须有严格的顺序依赖关系，不同顺序执行的合约可能会导致不同的结果。
  4. 发起合约的交易必须指定GAS limit，GAS limit设置的不同可能会导致运行结果不同。
  5. 合约执行失败也会花费GAS费，因为合约执行的过程已经由全网进行验证，GAS费已经消耗。

对比而言，BVM的函数式编程，就是通过一系列的函数来描述程序的执行过程，比如Haskell，Lisp等。函数式编程的特点是程序的执行过程是由一系列的函数来描述的，程序的执行过程是不可变的，函数的执行结果只与输入有关，不会受到外部环境的影响。同样，为了防止资源被耗尽，BVM在设置和触发合约的时候，必须指定循环次数的上限，在合约执行的时候，合约执行所需要的步数和结果都已经确定下来并不会发生改变。其特点如下：

  1. 合约的状态是局部的，状态存储在函数（UTXO）中，不同的状态之间是相互独立的，可以并行执行。
  2. 状态随着每一次的交易而转移，每一次交易只会触发一次状态转移，无论合约内部的逻辑多复杂，状态转移多少次，BVM只会将最终的状态转移结果记录在链上。如果需要实现多个步骤的状态转移或者递归等特性需要多个交易，也就是多个函数调用链共同完成。BVM不会自动触发后续的状态转移。需要合约调用方（任何人都可以调用函数，但不是任何人都能成功解锁）构建链式并执行。
  3. 合约编写的时候，需要很多编译期常量，比如循环次数等，此常量规定了合约可以接受的最大循环次数，也就定义了此函数的边界，不会无限膨胀耗尽资源。
  4. 合约的执行结果只与输入有关，不会受到任何外部状态的影响，合约执行结果可以被拿到链下验证，每次的执行结果必然完全相同（可复现性）。
  5. 发起合约的时候所消耗的最大GAS或者手续费就已经确定了下来，在运行期不再发生任何改变。
  6. 失败的调用无法上链改变状态，可以认为BVM修改状态，要么不成功什么都不发生，要么成功修改状态。因此失败的调用不会消耗GAS费，也不会记录上链。

正由于BVM或者UTXO模型和函数式编程范式的特点，BVM的模型也就能够充分利用函数式编程的优势，保证合约的安全性和可预测性，同时也能够实现图灵完备的智能合约。函数式编程模式现在在很多关键领域，尤其是对性能和安全有双重要求的领域，都有着广泛的应用，比如金融，AI等，都凸显了越来越多的优势。很多现代编程语言也开始引入函数式编程的特性，比如Java，Rust，以提高程序的安全性，可预测性，还有健壮性。

综上，我们可以认为BVM可以实现等同于EVM的图灵完备性，任何在EVM上可以实现的计算，BVM都可以等价实现。同时，BVM的函数式编程模式也为合约的安全性和可预测性提供了更好的保障，也为合约的分析和调试提供了更多的便利。