Truebit：为可验证计算开辟市场

去中心化应用程序向我们描绘了美好的未来图景。它们透明度高且具有防篡改性，永不停歇地运行着，在全球范围内释放激励并解决协调性问题。

但发展的道路上也有阻碍。

去中心化的计算十分昂贵，受区块 Gas 上限的限制，致使许多去中心化应用变得十分昂贵和不切实际。

难题：去中心化的计算

使用 Solidity 编写的代码会在 EVM（以太坊虚拟机）中编译为字节码，然后打包到区块链中。自此之后，每一笔向存储着字节码的合约地址发送的交易都会触发代码的运行。由此可以看出，区块链共识机制在设计上存在冗余：所有的矿工进行一样的计算，然后对结果达成共识。

计算被量化，相应地费用也是视代码执行的复杂程度决定的。区块链虚拟机指令集中的每个操作都被标好价格（称之为“Gas”），交易的发送者每执行一个指令，都会根据计算量来支付费用。

但凡复杂的业务逻辑，总会带来高昂的成本。

不止如此，在网络上进行的计算总量会受 Gas 上限的影响。Gas 上限是指在一个区块中所有交易能消耗的 Gas 总量。不幸的是，由于存在验证者困境的问题，我们不能单纯地增加 Gas 上限；矿工一旦接收到一个刚刚形成的区块，就需要先验证这个区块是否有效，才能开始寻找下一个区块，但是这样的验证是免费的劳动。受利益驱动的矿工处在了一个两难的境地：验证这个区块还是直接跳过它。而当区块的 Gas 上限增加时，这种困境的影响也随之变大了。

所以说计算是昂贵且受限制的。

Turebit 旨在解决这一问题。

它通过将计算移到链下来解决这一问题，并通过一种交互式的加密经济协议来验证计算的正确性。

解决方案：链下的可验证计算

当一个 dApp（去中心化应用程序）想要运行昂贵或是超过 Gas 上限的计算时，与其直接在以太坊上运行计算，不如交给 Truebit 协议。

Truebit 合约

和 Truebit 协议进行交互的 API 十分简单：它仅仅是 Truebit 智能合约上的一个叫做 createTask 的函数。

dApp 调用 createTask 函数的过程需发送以下内容：

程序：程序代码。Turebit 使用的是 WebAssembly 虚拟机技术，所以 dApp 能直接将程序代码的字节码发送给 WebAssembly 虚拟机，或者发送该程序代码在 IPFS 或其他基于内容寻址的系统上的哈希值。

输入值：针对程序的输入值。dApp 能直接发送这些输入值，或是发送这些输入值在基于内容寻址的系统上的哈希值。

奖励：奖励金额，提供给任何运行这个程序的人。

一个 dApp 创建了一个 Truebit 任务

为了进一步说明这个流程，下面我们来看两个例子。

Livepeer 是一个去中心化计算平台，它需要检查转码器是否正常工作。于是它调用了 createTask函数，将 FFmpeg 作为程序、一段视频作为输入值发送给了该函数。

Aragon 是一个匿名组织的平台，它想进行计票的工作。在链上循环进行大批量的投票工作是十分昂贵的，而且如果计票的数量太多，Gas 上限就会阻碍这项工作的进行。于是 Aragon 调用了 Truebit 的 createTask 函数，将计票函数作为程序、票数数组作为输入值发送给了该函数。

这个函数会在 Truebit 合约中生成一个新的任务。

Truebit 网络

Truebit 是一个计算任务市场。

任何人都能安装 Truebit 客户端，加入无门槛的网络中，然后通过运行计算任务来获取报酬。

Truebit 矿工所安装的客户端会监听 Truebit 合约所发出的事件。

Truebit 矿工监听计算任务

一旦生成新的任务，Truebit 矿工能下载其代码，然后使用任务发布者提供的输入在本地 Truebit WebAssembly 虚拟机中运行程序，接着将自己的结果发送给智能合约。

承接计算任务的同样要交纳押金，用于保证任务处理人对自己的计算结果负责。

任务处理人提交结果

计时器启动。在挑战限时之内，任何 Truebit 验证者都能在交纳押金的前提下挑战已提交的计算结果。

第一种情况：没有挑战者

这是符合预期的情况。任务处理人正确地运行了程序。如果在整个挑战时限内，没人对已有计算结果提出异议的话，即认定为正确结果。Truebit 合约会使用该计算结果去回调发起任务的 dApp。

任务发起人收到问题的答案

第二种情况：有挑战者

一个验证者交纳了押金，对当前的计算结果发起了挑战。现在对计算结果产生了分歧。对合约而言，它不但保管着任务发起人所提供的原始任务奖励，还保管着任务处理人的押金，以及挑战者的押金。

一个验证者发起了挑战

由此在任务处理人和挑战者之间展开了一场交互式验证游戏。

验证游戏

要注意的是 Truebit 任务是一个 WebAssembly 程序，会按顺序执行一系列指令。

一个简单的 C 程序（图左）及其编译后的 WebAssembly 文本形式（图右）

挑战者发起了验证游戏。

任务处理人和挑战者的初始状态都是 0 ，他们各自启动了一个空的虚拟机，用同样的程序运行同样的输入（如区块链上的任务描述中所规定的那样）。在状态为 0 的时候，他们是一致的。

在程序运行的终点，我们假设是在运行了 14 个指令之后，他们计算出了不同的结果。也就是说，在状态为 14 时，任务处理人和挑战者出现了分歧。

任务处理人和挑战者在状态为 0 时计算结果一致并在状态为14 时发生了分歧

挑战者根据这一信息来查询任务处理人在程序运行到一半，即运行完第 7 个指令之时的状态。

挑战者查询任务处理人的状态

任务处理人可以利用 Truebit 的 WebAssembly 虚拟机来计算己方状态的哈希值。它是由任务处理人的 WebAssembly 虚拟机的堆栈、内存和完整状态导出一个默克尔树根。任务处理人会通过一个 Respond（答复）消息将这个根提交至智能合约。

任务处理人和挑战者进行验证游戏

现在轮到挑战者在本地计算己方状态的默克尔树根，并且将结果和任务处理人的结果进行比较。

如果两根相等，就能判断他们出现分歧的位置是在计算指令集合的后半部分。如果两根不等，那么他们的分歧在集合的前半部分就发生了。

为了便于说明，我们现在假设状态为 7 时这两个根是相等的。

挑战者和任务处理人在状态为 7 时状态根相等

挑战者于是发送一个 Query（查询）消息，询问任务处理人在计算指令集合后半部分的中点，即运行完第 10 个指令后，的状态根。

挑战者询问集合内第二个中点的状态根

任务处理人据此做出相同的回应。

挑战者发现在状态为 10 之时两方的状态根相同，于是接着查询下一个中点，即状态为12之时，的状态根。

挑战者查询第三个中点的状态根

交互式验证游戏继续进行。

挑战者使用二叉搜索的方法迫使任务处理人找到出现分歧的状态的位置。整个游戏的时间复杂度为 O(log(n)) ，其中 n 是程序中指令的总数。根据任务处理人提交的指令发生前后的状态根，最终将分歧发生的位置锁定在某一个指令处。

争论：从 状态12 转变为 状态13 时的那个指令

现在的计算量已经小到足以让 Trubit 智能合约根据指令执行前的状态来初始化一个虚拟机，然后在区块链上运行那个产生争议的指令。

链上 WebAssembly 解释器运行有争议的指令

如果该状态的默克尔根计算出来和任务处理人提供的状态根不同，后者的押金就会被没收。
 

整个过程就是这样！

我们把所有的计算都移到链下进行，仅使用以太坊来计算那个单步指令，以防出现争议。

通过上述方式，我们对最终结果达成了共识，不过这种共识比中本聪的要求大多数人要诚实，BFT 的要求三分之二的人诚实更强。我们得到了一种“没有争议的共识：只要有一个诚实的验证人，就能保证系统的安全。

加密经济学

Truebit 的激励包括任务奖励、押金、任务处理人和挑战者之间的挑战机制以及计算市场的经济设计。

最近我们公布了 Truebit 代币的升级计划，以下是目前考虑使用的两种解决方案：

激励层一：强制出错 & 累积奖池

仔细地研究这个协议，一些敏锐的读者可能会发现一个问题。

任务处理人明白自己的计算结果会受到检查，而且如果出错，会被没收押金，因此不会作弊。长此以往，验证者极难发现错误，无法获得收入，最终在计算市场中消失。在验证者消失之后，任务处理人就会开始作弊了。然后，验证者会再度出现，把错误揪出来。

这个系统并不处在一种稳定的平衡之中，而是经常上下翻转的。

为了解决这个问题，Truebit 在白皮书中提出了一种强制出错（forced error）和累积奖池（jackpot）的概念。Truebit 协议会在一定概率下强制任务处理人提供错误的计算结果。凡是发现这类错误并挑战成功的验证者都将自动收到一份累积奖金。这笔意外之财的奖额是从所有任务的奖励中抽取的，因此十分巨大，为验证者提供了可观的预期收益。即使任务处理人总是提供正确的计算结果，验证任务也是有利可图的。

激励层二：多个任务处理人和结对验证挑战

另一个替代方案来源于具体实施过程。任务处理人和验证者总是做着一样的工作：他们下载相同的程序，在本地运行，然后得到计算结果。那么与其按照时序规则来规定一个任务处理人和多个挑战者，为什么不改变协议，允许每个人在同一时刻提交自己的计算结果呢？

智能合约会检查所有的计算结果是否一致。如果一致，就认为结果是正确的。如果不一致，且产生了几类计算结果的话，智能合约会组织不同类的任务处理人进行结对验证。

这种改进的协议能更好地保证时效性，因为验证挑战是并行的。这种改进也能替代强制出错和累积奖池。但不足之处在于增加了任务发起人应支付多少奖励以及多个任务处理人之间如何分配奖励等问题的复杂度。

我们正在努力研究如何改进协议（欢迎向 Zack Lawrence 和 Ali Yahya 的推特提出一些有建设性的建议！）

模块化架构

Truebit 是一个模块化系统，可分为以下三个层次：

Trubit 的模块化架构

计算层：即 WebAssembly 虚拟机（或者说是一个有限状态机，就像我们在使用交互式 scrypt 设计 Doge-Ethereum 转换桥中所用到的那样）它需要链上和链下双重的建设。

Truebit 的 WebAssembly 解释器具有确定性和可计量性，能够生成内部状态的默克尔树。

争议解决层： 这是一个两方间的交互式验证游戏，包括任务处理人和验证者之间多次的交互式问答。

激励层：这一层包括奖励、押金、任务处理人和挑战者之间的挑战机制，以及代币机制。

各层之间会通过定义好的接口进行交流。

结语

我们的工程方向目前聚焦于计算和争议解决层。我们的调研主要针对激励层和代币机制。

最近我们公布了针对 Scrypt 验证的 Truebit 解决方案，它在 Doge-Ethereum 转换桥中得到了应用。

可以点击这里观看我们的 demo 视频，或者在 Github 上查阅我们的代码。

我们的下一版视线中就会支持 WebAssembly VM。

敬请期待！

原文链接: https://medium.com/truebit/truebit-the-marketplace-for-verifiable-computation-f51d1726798f
作者: Sina Habibian
翻译&校对: 安仔 Clint & 闵敏