【论文笔记18】使用智能合约的可验证计算

Sepideh Avizheh, Mahmudun Nabi, Reihaneh Safavi-Naini, Muni Venkateswarlu K.. 2019.Verifiable Computation using Smart Contracts. In 2019 Cloud Computing Security Workshop(CCSW’19), November 11, 2019, London, United Kingdom. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3338466.3358925

0x00 摘要

外包计算已被广泛用于允许弱客户端访问云的计算资源。客户端的安全要求是能够有效地验证接收到的计算结果。验证通用计算的一种有吸引力的方法是将计算发送到多个云，并使用精心设计的协议来比较结果并实现可验证性。然而，这需要受信任的第三方 (TTP) 来管理客户端和云的交互。我们的目标是使用智能合约作为 TTP。这也使客户端免于直接与云交互，并可能参与复杂的有状态协议。我们专注于 Canetti、Riva 和 Rothbulm (CRR) 的可验证计算协议，该协议具有可证明的针对恶意云的安全性，并表明直接使用该协议与智能合约将导致攻击，从而破坏系统的安全性。我们描述和分析了攻击，并扩展了 CRR 协议以防止这种攻击，从而产生了一个使用智能合约的安全可验证计算系统。我们还给出了智能合约的伪代码和可用于实现协议的所需函数，用 Solidity 语言编写，并解释其工作原理。

关键词 ：外包计算；可验证计算；区块链；智能合约

0x01 INTRODUCTION

云计算正在迅速超越传统的本地计算，用于数字世界中的应用程序和服务交付。公司和组织转向云计算以降低基础设施成本、加快软件部署并提高运营灵活性。对于（计算上）较弱的客户，云计算通过允许客户将其计算外包给云，并从云可用的大量计算资源中受益，开辟了大量新的可能性。

外包计算的基本安全要求（对于客户端）是有效验证云提供的计算结果的能力。由于各种原因，计算结果可能不正确，这些原因可以分为意外和故意。本文的重点是云对结果的有意 *** 纵。为了让客户端验证计算结果，云必须提供一个可以被客户端有效验证的证明。效率很重要，否则客户端可以自己进行计算。已经有大量工作考虑了不同设置下一般计算的计算可验证性问题。在 [4, 10, 13] 中，客户端将由布尔电路表示的计算外包给单个云，并使用完全同态加密来允许云证明计算的正确性。然而，这些协议需要对许多输入进行初始处理和多次计算，以便可以摊销所需的初始离线计算成本。还有大量关于概率证明系统的理论工作，包括交互式证明 [5, 14] 和概率可检查证明 (PCP) [17, 18] 的工作，虽然是相关的 2，但需要多轮交互，因此在实践中用途有限。第三种直观吸引人的方法是将计算外包给多个云，并设计一个协议来使用从云接收的多个独立计算来验证结果的正确性。这种方法很有吸引力，因为它具有通用性（适用于一般计算），并且客户端所需的工作量相对较小。在多个云上重复计算是实现结果的可靠性和信心的代价。使用这种方法的简单可验证计算系统是选择由大多数云生成的解决方案作为正确的解决方案。如果至少有三个云，该协议将给出正确的结果，并且可以假设大多数云是诚实的。

Canetti、Riva 和 Rothblum [9] 考虑了只有两个云的可验证外包，并提出了一个协议，我们称之为 CRR，它建立在 Feige 和 Kilian [12] 的裁判博弈框架之上，并为任何高效可计算函数。如果可验证性基于多个独立执行，则这是所需的最少云数。如果两个云中至少有一个是诚实的，CRR 协议保证正确的输出，并且在两个不同结果的情况下，使用两个云之间的裁判游戏来识别恶意云。这确保诚实的云会得到奖励，从而激励正确的行为。他们还提供了系统的实现，其中计算表示为 C 程序，并编译并打包成 X86 可执行文件（适用于 Windows 环境），可以发送到云端。

CRR 协议。在高级 CRR 协议的工作原理如下：客户端将计算（程序和输入）发送到两个云。一旦客户端从云端接收到结果，它会进行如下处理： (i) 如果两个结果相同，它认为结果是正确的并终止（在支付云端之后）； (ii) 如果结果不匹配，客户端与两朵云进行多轮裁判游戏，在每一轮中，客户端向两朵云提出一个问题，并根据收到的结果提出后续问题问题。一系列问题以识别恶意云结束。我们将此协议称为 MCId，Malicious Cloud Identification，协议。假设至少有一个云是诚实的，MCId 始终正确（且有效地）识别恶意云。因此，一旦发现恶意云，另一个必须诚实，他们的解决方案将是正确的。

CRR 协议（也称为 [11, 15]）假定客户端是受信任的并正确执行协议。然而，在实践中，云还需要信任客户履行其承诺的计算付款。为了消除这些假设，可以使用受信任的第三方 (TTP) 来管理所需的交互和付款。

智能合约作为外包的 TTP。在本文中，我们的目标是将智能合约用于基于 CRR 的可验证计算系统。基于区块链的智能合约 [8] 是驻留在区块链上的一段公共代码，它指定了在底层共识计算机上运行的协议（参见第 2.3 节），以保证可信执行（假设大多数共识节点是诚实的） ，并处理所需的资金转移。智能合约为在协议中使用 TTP 提供了一种有吸引力的数字替代方案，并且被广泛认为会彻底改变当今的许多计算服务。它们通过在共识计算机上运行智能合约代码来提供 TTP 所期望的正确性、透明度和不变性。使用智能合约根据 CRR 验证计算特别有吸引力，因为 CRR 的可证明保证（可验证性只会使计算成本翻倍）及其用于一般计算而无需过多的预处理、交互或加密 *** 作。

使用带有智能合约的 CRR 协议。智能合约将消除 CRR 中客户端信任假设的需要，确保正确遵循协议，并且云将按照合约中的规定获得奖励。此外，它将最大限度地减少客户端的计算、通信和交互，这对于计算能力较弱的客户端来说可能变得不可接受。

然而，我们将证明，由于多种因素的综合作用，这个有吸引力的提议将完全失败。我们展示了一种攻击，我们称之为复制攻击，当与智能合约一起使用时，它完全破坏了 CRR 协议的安全保证。我们描述和分析了这种攻击，提出了可以有效防御攻击的 CRR 协议的扩展，并将我们的解决方案的伪代码作为以太坊区块链上的智能合约给出。

1.1 Our work

我们考虑通过在加密货币区块链上使用智能合约来进行可验证外包，并使用 CRR 协议使用两个云进行可验证计算。智能合约将充当 TTP 来管理各方之间的交互以及他们之间所需的资金转移。具体而言，我们将自始至终使用以太坊区块链，但我们的工作是通用的，适用于其他常用的去中心化和分布式公共分类账加密货币，这些加密货币支持比特币 (RSK [2]) 等智能合约。以太坊由一个松散同步的计算节点网络组成，这些节点共同工作以实现账户持有人之间的资金转移，以及模拟共识计算机，其中计算步骤由共识算法（使用工作量证明达成协议）批准在活跃的以太坊节点（矿工）之间。第 2.3 节概述了以太坊、其区块链和计算模型。以太坊节点存储智能合约，每个合约都指定一组功能，可以由用户或其他合约调用。每个节点处理的交易包括对合约中函数的调用，以及发布到网络的加密货币交易。

复制攻击：CRR 协议是使用公共通信（从服务器到客户端的消息经过数字签名但未加密）的全信息（公共币）协议。以太坊网络中的消息传输不是即时的，不同节点（例如云）生成的消息需要不同的时间在网络中传播。这为恶意云提供了查看其他（诚实）云生成的计算结果的机会，并将结果复制到其自己的（签名）消息（交易）中，然后发送给合约。也就是说，在不进行实际计算的情况下，恶意云能够产生正确的结果（假设发布的结果来自诚实的云）。这是多方计算中的一个快速对手，在每一轮计算中，在看到诚实方的消息后选择它的消息。复制攻击导致智能合约收到两个相同的解决方案，它将接受为正确的，并奖励两个云。请注意，这不会破坏 CRR 的安全性，因为要求至少有一个云是诚实的，并且将确保复制的解决方案是正确的解决方案。这种复制攻击的效果是恶意云无需进行任何计算即可获得奖励。换句话说，恶意云总是可以搭便车，并从诚实云的计算中受益。

复制攻击的一个更严重的负面影响是 CRR 认为 MCId 协议将激励云的诚实行为，这些行为被认为是理性的：“我们将服务器视为理性的自利方（例如云计算服务提供商）。 ” 知道复制结果的可用性以及在不进行计算的情况下获得奖励的可能性，将极大地抑制诚实行为。一个云总是可以等待另一个云提交解决方案并复制它。如果两个云都使用这个等待策略，会出现死锁，无法提供解决方案。理性的云可以避免通过随机化提交解决方案的时间来实现死锁。知道它的解决方案将被另一个云复制（因为两者都是合理的），云可能会发现生成一个随机解决方案并在考虑到云对网络延迟的估计的（随机）时间提交它就足够了，以及智能合约超时（提交解决方案的指定截止日期）等因素。如果解决方案在发布自己的解决方案之前被第二个云看到，那么复制攻击将很有可能成功。请注意，智能合约超时将大大大于消息在网络中的传播时间，因此复制攻击很可能会成功。两个云也有可能生成两个单独的解决方案（随机或恶意构建的结果），这将导致不匹配。原 CRR 对这种情况没有任何安全保证。

总而言之，复制攻击会抑制诚实行为，并且协议确实有可能接受随机值作为正确结果。

在第 3.1 节中，我们使用类似动作树的游戏展示了云的可能动作序列，并描述了每种情况下的结果。分析清楚地显示了可以接受随机甚至恶意构建的解决方案的案例（案例5），并且系统中没有针对此案例的检测/预防机制。我们注意到，复制攻击将吸引理性云，其效用由奖励定义，这将为恶意云提供机会在网络中发布和传播其恶意构建的解决方案，以期被复制和公认。

保护机制：上面的讨论表明，上述设置中结果的正确性不能基于两个相同的独立解，即使两个云不合作，复制也有效地去除了独立性假设。

我们建议对 CRR 协议进行修改，以在智能合约使用时保持其安全保证。我们修改了提交解决方案的格式以包括执行磁带的长度，3 和执行跟踪的 Merkle 证明（参见第 2.1 节），并在 CRR 中引入新的结果确认 (RC) 协议，该协议将在两个结果确实匹配。 RC 协议可以有效地检测解决方案提供商是否使用提交的执行证明实际执行了计算。 RC 协议包括向每个云发送一个随机生成的单独查询，使智能合约能够有效地识别尚未执行计算的云。 RC 和 MCId 协议的组合确保理性云将 (i) 被激励以正确执行计算，而不是懒惰并依赖其他云的工作，或者简单地产生随机结果并希望被复制，并且（ii）相信他们的工作会得到回报（与原始 CRR 相同）。即 RC 激励一个诚实的云来避免复制攻击并正确执行计算，而 MCId 将确保 CRR 的原始激励得以保持。

生成随机查询。查询是由云的执行声明确定的范围内的随机整数。由于智能合约无法保密，因此需要使用其他来源智能合约可用的随机性。我们使用类似于 [7] 的方法，通过将抗碰撞哈希函数应用于过去块的序列来生成随机查询。在 3.3.2 节中，我们将描述我们的随机查询生成算法，并在 3.3.1 节中，证明假设查询是随机的，智能合约 CRR（简称 scCRR）（修改消息并包含 RC 协议）将恢复CRR原有的正确性保证。

执行。在第 4 节中，我们给出了使用 scCRR 进行可验证计算的智能合约的伪代码。 scCRR 合约由一组功能组成，如图 3 所示，可以使用智能合约（通过公共地址）调用。客户端在以太坊区块链上发布合约并调用 Initialize() 函数来初始化合约。合同中的其他功能和控制流程在第 4.1 节中描述。

如 [9] 中所述，CRR 适应现实世界的执行非常微妙，比较两个执行需要执行中的确定性（不受 *** 作系统影响），以及从给定状态集的任何中间状态执行程序等能力变量。它们的实现使用 C 程序，它们的可执行代码将保持计算状态。

我们使用 EVM 来实现智能合约。智能合约的计算（在共识计算机上）包括（i）比较两个云的结果，（ii）生成发送到云的查询，并根据提交的证明验证响应（当存在匹配时）结果），以及 (iii) 执行 MCId（当结果不匹配时）。可以使用与 [9] 相同的方法来准备每个云的计算。但是，这将要求 RC 和 MCId 协议使用的中间计算结果能够被以太坊虚拟机（EVM）“理解”。为简单起见，我们假设每个云的计算包将采用 EVM 字节码并在云中的 EVM 上运行。我们注意到，EVM 上的计算不会发送到以太坊网络（不会由共识计算机执行）。所需的计算（功能和输入描述以及指向 EVM 字节码和输入数据的链接，以及费用和奖励）将发布在网络上，并通过相关网站和社交平台进行宣传。云的成功注册将导致将记录在区块链上的合同状态更改。使用智能合约作为 TTP 将引入交互延迟（云与智能合约的交互）。我们将通过执行 CRR 所需的以太坊交易数量来量化这种延迟。

1.2 Related work

验证通用计算已经在理论和面向应用的研究中进行了研究 [4, 5, 10, 13, 14, 17, 18]。这些工作的动机是将计算外包给云，特别是当客户端是资源受限设备时。尽管这些结果具有普遍性和重要性，但它们的实际应用有限。 [9] 的工作受到 Feige 和 Kilian [12] 在裁判游戏中的优雅工作的启发，其中计算有界的诚实裁判必须决定两名球员之一的诚实。费格等人。的计算假设很好地匹配了我们工作中考虑的智能合约设置：云有无限计算和智能合约在其计算中是有界的（智能合约的每条指令都将在共识计算机上运行，​​并且必须通过加密货币支付）。卡内蒂等人。遵循此模型并引入计算的裁判委托（RDoC）并提出我们在使用智能合约的可验证计算系统中使用的裁判游戏（交互式协议，CRR）。在[6]中正式研究了独立计算代理使用多个解决方案来提供可验证性，并假设许多理性代理参与计算并因其工作而获得奖励。作者考虑了一种设置，其中一个称为老板的中央机构将计算外包给承包商，如果他们正确执行计算，承包商将获得奖励，如果发现产生了不正确的结果将被罚款。作者假设老板是诚实的，计算代理是理性的，并且系统的正确性保证是经过多轮协议执行和承包商参与。该系统的保证是针对理性节点[6]。该模型已在 [16, 20] 中使用，其目标包括优化奖励和罚款，以及最小化外包商成本的审计率。

我们的工作遵循 Canetti 等人的模型。并且它的安全性不假设定义良好的效用函数。我们协议的安全保证是针对云的任意恶意行为，并适用于损坏的云使用的任何恶意策略。假设其中一个云是诚实的，我们的案例中的正确性保证适用于协议的任何运行。 Canetti 等人的理性概念。只能说，保证诚实的云会因其工作而获得奖励，而恶意的云会被抓获4，这将激励诚实的行为。

[6, 9, 16, 20] 中使用的一个重要假设是节点不合作（共谋）。当计算节点是云时，这是很合理的。然而，这个假设在 [15, 21] 中没有使用，其中计算节点可能会串通，从而导致更复杂的安全分析。将大型计算分配给志愿者计算节点可以追溯到 BOINC [3] 等项目，该项目为志愿者提供了一个外包计算平台。

Paper organization.第 2 节为预备课。第 3 节展示了如何使用智能合约实现 CRR。在 3.1 节中，我们讨论了复制攻击和我们提出的保护机制。第 4 节给出了我们提出的系统的伪代码以及对使用智能合约引入的延迟的估计。第 5 节是结束语。

0x02  PRELIMINARIES

我们首先简要概述 Merkle 哈希树和 CRR 协议 [9]，然后介绍以太坊区块链和以太坊智能合约的基础知识。

2.1 默克尔哈希树（MHT）

Merkle 哈希树是使用抗碰撞哈希函数构造的二叉树，叶子是单个数据块的哈希，每个父节点是它的两个孩子的串联。哈希树的构建从叶子开始，一直移动到根。

图 1 是 8 个数据块上的 MHT 示例。数据块 分别被散列为 。对于第二层，节点 H12 = H(H1||H2) 和 H34、H56 和 H78 的定义类似。在第三层中，H1234 = H(H12||H34) 和 H5678 = H(H56||H78)。最后，树的根是 MHroot (str) = H(H1234||H5678)。 

给定根 MHroot (str)，Merkle proof pi = MHproof (str, i) 一个字符串位于 str 的第 i 个位置，由来自第 i 个叶子的路径上的所有兄弟节点的哈希值组成值（即 Hi ）到根。例如，索引 i = 3 处的叶节点 H3 的 Merkle 证明是 p3 = MHpr oof (str, 3) = (H3, H4, H12, H5678)。在 CRR [9] 中，该证明称为一致性证明。

给定一个 Merkle 根，root = MHr oot (str)，对于一个字符串 str，一个证明 pi，使用 Veri f yMHProo f (root, i, str,pi) 进行验证。如果 pi 中的哈希值序列（从 str 的第 i 个元素开始）与根匹配，则该函数将返回 T rue，否则返回 False。

---

---

2.2 CRR 协议

[9] 的模型被作者称为计算的裁判委托 (RDoC)，包括一个具有输入 x 的客户端和两个被雇用来计算 y = f (x) 的云。计算由图灵机 (TM) 表示，其状态由简化的图灵机 (TM) 配置表示，对于索引 j，其由 rcj = (sj,hj,vj, rj ) 给出，其中 sj 和 hj分别表示 TM 的当前状态和磁头位置，vj 表示磁带上 TM 磁头位置的值，tape[head]，rj = MHr oot (tj ) 是磁带 tj 上 Merkle 树的根。简化配置 rcj 捕获计算状态 sj 。

CRR 协议的工作原理如下：

i) 客户端请求两个云对输入 x 执行函数 f。 Cloud i, i ∈ {1, 2}，将其结果 yi = f (x) 返回给客户端。

ii) 如果两个结果匹配，则结果被接受。

iii) 否则，客户端启动恶意云识别（MCId）协议来检测恶意云的。伪代码MCId 协议在附录 A 中的算法 3 中给出。该协议有两个功能：（i）二分搜索和（ii）验证减少步骤。

二分搜索函数将 （其中一个云计算 f (x) 所采取的最小步数）作为输入，并返回与两个云匹配的最后一个简化配置的索引 ；即 ,verify-reduced-step 函数采用两个连续的缩减配置， 其中 ，一致性证明 用于来自其中一个云（例如 C1）的树索引 ，其中 是计算步骤处的磁带。

然后它调用 重新计算配置 的 Merkle 根，并执行从 到 的计算，并验证 的 Merkle 根(调用 )。如果两个结果（）匹配，则云（C1）被认为是诚实的并且其结果被接受。否则，另一个云 (C2) 是诚实的，并且其结果被接受。

---

---

2.3 以太坊和智能合约

以太坊是一个开源、去中心化和分布式计算平台，使用户能够开发智能合约和去中心化应用程序，即 DApps。智能合约是一种计算机协议，无需 TTP 即可促进、验证和执行各方之间的协议。以太坊智能合约平台的主要构建块是，（i）点对点网络，其中用户的计算机形成一个网络，用于在没有中央服务器的情况下进行数据交换； (ii) 一种共识算法，区块链用户使用该算法就区块链的当前状态达成共识。以太坊使用使用工作量证明的共识算法。 (iii) 以太坊虚拟机 (EVM)，一种图灵完备的虚拟机，是一种可以在底层硬件之上的抽象层上运行的软件，以及 (iv) 加密令牌和地址，可实现区块链上资产的安全转移.在以太坊中用于交换的加密货币称为以太币。

有大量的以太坊节点通过共识协议验证和执行计算任务并达成一致。在 [19] 中，这种可编写脚本的加密货币框架被称为共识计算机，强调网络中所有节点对执行指令的一致性。共识过程引入了从发出交易到出现在链上的延迟。在这台共识计算机上执行程序需要承担成本。在以太坊上运行 *** 作的成本以气体单位衡量，与合同相关的总气体可以转换为 ETH。智能合约带有一个用户界面，通常以网页、移动应用程序或应用程序的形式实现。

为了部署智能合约，程序代码被编译成 EVM 字节码，并在交易中发送到以太坊网络。当交易出现在区块链上时，以太坊计算节点会生成一个不同的地址，然后用于与智能合约进行交互。与合约的交互是通过交易调用合约中的函数。已发布的交易在以太坊网络中传播，直到它被添加到一个块中。网络延迟是交易提出后出现在区块链上的经过时间。

0x03  部署 CRR

使用由智能合约管理的 CRR 协议实现可验证计算可以采用不同的形式。例如，它可以实现为一个服务，它从问题提供者那里获取一个元组 [(x, f ()), α]，指定所需的计算 (x, f ()) 和奖励 α，管理整个过程，并将结果返回给问题提供者5。智能合约代码是公开的，因此所需的计算 (x, f ()) 可以发布在公共仪表板或网页上。为了专注于新的攻击，我们考虑一个基本设置，其中客户端（问题提供者）启动一个智能合约，其中包含一个有信誉的 Web 托管站点的 URL，其中包括计算任务 f() 和输入 x，CRR 算法和 EVM 字节码，以及描述加密货币流的过程。智能合约执行（在共识计算机上运行）（i）招募两个云来执行计算，（ii）执行 CRR，以及（iii）支付所需的款项。系统中的实体是 (i) 在以太坊区块链上编写和启动合约的问题提供者 (PG)，(ii) 假定独立且不合作的两个云 C1 和 C2，以及 (iii)由以太坊共识计算机实现的“可信计算机”。我们假设在不执行计算的情况下生成正确结果的概率可以忽略不计。 To attract volunteer clouds for the computation the fees and rewards must be appropriately chosen. CRR 协议确保诚实的云将始终因其工作而获得回报。每个云支付押金 δ 以参与计算。为了抑制恶意行为，已识别的恶意云的存款将用于执行 MCId 协议。确定费用和奖励可能需要许多因素。一个典型的例子是：PG通过估计计算成本α'c（即执行计算所需的资源）来估计它应该为计算提供给云的奖励α'，并包括一个额外的激励，α' r ，鼓励云的参与。 PG 在智能合约中存入 α = 2α′ 作为费用，它将支付给云计算（即，接收正确的结果）。此外，PG 将支付 epg 作为合约部署交易费用。因此，每个云支付 δ，如果它们正确执行计算，则接收 α′，如果发现恶意，则支付 MCId 协议的执行费用。恶意云没有明确定义的实用程序，并且可能会计划其策略而不管奖励如何。

3.1 复制攻击与防护

在下文中，我们使用使用 CRR 的智能合约可验证计算系统，并表明智能合约直接使用 CRR 将使系统容易受到我们称为复制攻击的攻击。

模型。我们的计算模型由以下实体组成：(i) PG，(ii) 智能合约，和 (iii) 两个云，都通过被建模为同步网络的以太坊网络进行通信有界的延迟。两朵云独立行动。我们考虑一个可以破坏其中一个云的匆忙对手，在这种情况下，云将采取恶意行为。恶意云将复制作为其策略之一，但可能会使用其他策略来构建其解决方案。未损坏的云是理性的，其效用由计算奖励定义。一个理性的云将使用可用的策略来确保它获得奖励，同时最小化其执行计算的资源成本。它将避免所有会否认奖励的策略，甚至更糟地惩罚它。

复制攻击。智能合约不能保存任何秘密，因此使用智能合约作为 TTP 意味着与 TTP 的通信渠道将是公开的和经过身份验证的。以太坊网络中的网络延迟提供了一个时间窗口，攻击者可以利用该时间窗口来执行复制攻击。一个匆忙的对手将延迟损坏云的消息，直到它在本轮中收到另一个云的消息；这意味着损坏云的第 i + 1 轮消息可以依赖于其他云的第 i + 1 轮消息。如果云使用复制攻击，无论是恶意的还是理性的，都会导致匹配，无论第一个云的解决方案是否正确，都会破坏CRR的安全基础，即存在两个独立的解决方案.也就是说，虽然两个云不合作，但解决方案将变得依赖。该攻击促使诚实（和理性）的云转移正确计算函数的诚实行为，并尝试在不执行计算的情况下接收奖励。

3.2 分析

受博弈论分析中的动作树的启发，我们使用可能场景的树表示来展示复制攻击对 CRR 系统的影响。该树显示了首先发送其计算结果的云以及稍后发送其结果的云的可能事件序列。我们将复制攻击视为合理（未损坏）云的一种有吸引力的策略。我们不考虑理性云随机生成解决方案并希望它被可能是恶意的其他云复制的非常冒险的策略。

第一个云，比如 C1，(1) 可能是诚实的，计算函数并发送正确的结果。这是一个诚实的云，没有看到其他云的解决方案。 (2) 可能是恶意的；它会生成一个不正确的解决方案并将其发送到智能合约。第二个云，比如说 C2，如果诚实的话，除了计算结果之外，（3）可以复制第一个云的解决方案并将其发送到智能合约。图 2 显示了事件的序列，考虑到如果 C1 损坏，则 C2 将是诚实的，它的两个可用策略是计算或复制。

事件的顺序和相应的结果如下:

案例 1：（两朵云都是诚实的，并且正确地计算了函数。）结果匹配。 PG 将收到正确的结果。每个云收到奖励 α '，以及它的存款 δ。每个云都花费了 α′c 进行计算。

案例 2：（C1 是诚实的，C2 是恶意的。）结果不匹配。智能合约会发起[9]的MCId协议，识别恶意云。 C1 的结果将被认为是正确的结果，并将传递给PG.C1 将获得奖励 α′，将 α′c 用于计算成本，并取回其押金 δ。 C2 将收取 ξ 执行 MCId 协议的费用并取回其押金（即 δ - ξ ）。

案例 3：（C1 诚实，C2 使用复制策略。）结果匹配。 PG 会收到正确的结果。每个云都会收到奖励 α ' 和它的存款 δ。然而，C1 将承担计算成本，而 C2 将成为搭便车者。请注意，复制是诚实（理性）和恶意云都可以使用的策略。

案例 4：（C1 是恶意的，C2 是诚实的并计算函数。）结果与案例 2 相同，云的角色和它们之间的资金分配相反。

案例 5：（C1 是恶意的，C2 是诚实的（和理性的），使用复制策略。）结果匹配。 PG 将收到错误的结果。每个云收到奖励 α ' 并取回押金 δ。然而，C1 将有计算成本（< α 'c ），而 C2 是搭便车者。

上述案例表明，使用智能合约直接实现 CRR 并不能防止第二云的搭便车，并且在案例 5 中导致错误的结果被接受。

 3.3 防止复制攻击

当在智能合约管理的可验证计算中运行时，我们修改 CRR 协议以防止复制攻击。我们将修改后的协议称为 scCRR（使用 CRR 的智能合约）。

scCRR 包括一个附加的检查协议，即结果确认 (RC)，当结果匹配时使用该协议。 RC 由智能合约和每个云之间的单轮交互组成。下面我们给出协议的细节并证明它的安全保证。

3.3.1 Result confirmation (RC). 在 scCRR 中，云发送其形式为 的结果，其中，Res 是计算结果，是在数组简化配置 C，N 是数组 C 的长度。MHT 的每个叶节点存储值，其中 H 是抗碰撞哈希函数。当两个云的计算结果匹配时，RC 协议执行如下：

 (1) 智能合约生成一对不同的随机查询 qi，i = 1, 2，每个云一个，并将其发送给它们。查询的形式为 (i, xi )，其中 i 是云标签，xi 是 [1, N - 1] 范围内的随机整数，使得|x2 -x1| > 1（即 x2 和 x1 不连续）（有关随机查询生成的详细信息，请参见第 3.3.2 节）。

(2) 每个云 i ∈ {1, 2}，以第 xi 个配置 关于根 的一致性证明来响应。

(3) 一旦收到结果，智能合约对每个云 i 执行以下 *** 作。

        (a) 它根据根验证证明 。如果验证成功，则证明证明有效。

         (b) 如果上述检查失败，云的计算被拒绝。

步骤 3a，将以压倒性的概率检测搭便车。

讨论： RC 协议可以有效地识别使用复制策略的云，并且无法对其执行跟踪的查询提供所需的响应。在下文中，我们评估了在第 3.2 节中考虑的五种情况下使用 RC 协议的效果。

复制攻击发生在两种情况下，案例 3 和案例 5。RC 协议始终可以识别复制云（因为复制者未能对智能合约的查询提供正确的响应，见定理 3.1）。这对诚实（理性）云的影响是它将从其可用策略中删除复制（因为它知道它将被捕获），因此将始终正确计算。然而，损坏的云仍可能将复制视为有效策略。 RC将再次检测到这种情况。这意味着 RC 有效地去除了 Case 3 和 Case 5。剩下的 Case 1 会生成正确的结果，Case 2 和 4 会有两个不匹配的结果，MCId 将用于识别诚实的云。定理 3.1 给出了 RC 协议的安全性。

 定理 3.1：考虑第 3 节中的复制攻击和第 3.3.1 节中的 RC 协议，让 H 是一个抗冲突哈希函数，用于在缩减配置数组 C 上构造 Merkle 哈希树。然后 RC 协议提供防止复制的保护诚实云的攻击。

证明：（草图）考虑一个复制攻击，其中云 C1 产生并发布了结果，云 C2 复制了结果。 C1 将接收查询 x1，C2 将接收查询 x2，其中 |x2 -x1| > 1. 每个云必须为对应的查询 rcx1 和 rcx2 提供关于根 MHr oot 的一致性证明。让 C1 生成一个证明

首先考虑 C1 是诚实云的情况，然后验证 。 C2 可以复制此证明的任何部分。然而它需要生成一个证明，。 MHT 树的每个叶子都会有一条到根的路径长度为 log N，并且由于两个叶子不连续，它们不会有一个共同的父节点，因此它们到根的路径将至少包含一个哈希值：无法从发布的路径计算。例如，在图 1 中，查询 x1 = 1 对应于散列到 H1 并具有路径 (H2、H34、H5678) 的叶子。另一方面，叶子 x2 = 3 的路径是 (H4, H12, H5678)。因此，至少有一个 j 对应于。为了成功，C2 必须找到满足的 ，因此它的成功概率受限于哈希族的冲突概率。

 接下来考虑 C1 是恶意的情况，因此验证。复制云 C2 的成功概率会更低，因为 C1 的发布路径没有提供有用的信息。

 在 [9] 中，计算的裁判委托 (RDoC) 协议定义如下：

 定义 3.2。 (P1, P2 · · · PN , R) 是一个 ϵ-RDoC，对于函数 f，如果满足以下条件：

         — 对于任何输入 x 和任何 i ∈ [1, N ]，如果 Pi 是诚实的，那么对于任何，R 的输出是 f (x)，概率至少为 1 - ϵ。

        —客户端的复杂性在 |x | 中至多是准线性的并且（诚实的）服务器的复杂度在评估 f() 的复杂度中是多项式的。

使用 [9] 中的定理 3.1 和定理 1，我们有以下内容。

推论 3.3：假设散列函数是抗冲突的，那么 scCRR 协议是一个计算上可靠的、完整的信息 RDoC，它有两个服务器，并且对于任何可在多项式时间内计算的函数的稳健性 ε 可以忽略不计。

3.3.2 随机查询生成。让区块链中的每个区块都有一个索引，显示它在链中的位置；例如，第一个块（创世块）的索引为 0，之后的下一个块为 1，依此类推。智能合约必须生成两个不可预测的查询索引 x1 和 x2（除非随机猜测的机会可以忽略不计）并且满足 |x2 − x1| > 1. 我们使用 [7] 中的一种方法，该方法使用区块链上的块子集来提取随机字符串。我们生成一个索引 x1 是随机的，然后选择 x2 作为 x1 的移位。对于 C1 的查询，我们在区块链上的连续发布块集合上使用抗碰撞哈希函数，范围为 [idx - 2κ, idx - κ]，其中 idx 是发布云结果的块索引（如果有两个这样的块，我们考虑较小的索引）。查询索引 x1 计算为。第二个查询是简单的 x2 = x1 + d (mod N - 1)，其中 d 是 PG 在 [2, N - 3] 范围内选择的随机值。这里 κ 是区块链的安全参数（见下文）。这两个查询将是 (i) 不同的，并且由于选择 d 不会是连续的，(ii) 每个都是随机的，并且被相应的云不可预测，并且 (iii) 通过使用足够大的 κ，它们不会受到恶意方的偏见。算法 2 显示了生成随机查询的步骤。除其他外，κ 的值将与底层共识算法相关，并且将被选择为（i）在每个 κ 连续块中，至少有一个保证是诚实生成的块，以及（ii）通过删除最后的 κ 块，区块链将在大多数计算节点之间保持一致。条件 (i) 确保至少一个哈希不受恶意云的影响。条件（ii）保证随机性是从区块链的稳定部分中提取的，因此大多数节点都会看到用于随机性生成的块，并且可以生成和验证查询（详见第 1.1 节） [7]）。

 

 3.4 修改 CRR 以用于智能合约

 在智能合约中使用 CRR 需要进行以下修改。我们将生成的协议称为 scCRR。

scCRR 协议：

        (i) scCRR 中的第一条消息是 ，如第 3.3.1 节所述。（CRR 中对应的消息是 Res = f (x)。） 

         (ii) 如果结果匹配，则使用 RC 协议。该协议选择两个不同的随机查询，向每个云发送一个，并接收响应。如果响应与一致，则接受该响应，否则拒绝该响应。生成随机查询的算法在 3.3.2 节中给出。

        (iii) 如果结果不匹配，将使用 CRR 中的 MCId 协议及其相关决策。

0x04 实施

图 3 中的智能合约由 PG 编写，由一组可用于与合约交互的函数及其相应的输入和输出组成。 PG 部署并初始化智能合约，但在收到最终结果之前无法更新或与之交互。该合约将在该阶段被终止，并在需要时重新部署。在智能合约初始化后限制 PG 与智能合约的交互，保证 PG 无法破坏合约。

 函数的伪代码如图 4 至图 8 所示。下面我们对每个函数进行简要说明。

(1) Constructor()-构造函数: 一旦执行其构造函数（使用关键字构造函数声明），就会在以太坊区块链上部署智能合约代码。该函数分配智能合约的变量（如果有），并将问题提供者设置为智能合约的创建者（PG = msg.sender）。这里，msg.sender 指的是 PG 的地址。

(2) Initialize()-初始化函数。 PG首先调用initialize函数来启动智能合约的执行。为此，PG 向指定以下内容的智能合约地址发送交易。

        (i) 提供计算信息的 url，以及计算 EVM 字节码 和输入 x 的链接；

        (ii) 网页的哈希值 和 hw（由 url 指向）。 hw 和 hc 分别被云用于检查网页的完整性和计算。

        (iii) 合约执行所需的价值，包括奖励α和注册最低存款δ，将存储在合约存储中。 Initialize()用关键字onlyOwner注解，保证只有PG可以调用该函数。

        初始化成功后，会向区块链发送一个事件 taskInitialized。该事件将允许云观察所需的计算，并能够通过注册来表达他们的兴趣。

 

(3) Register()-寄存器函数。有兴趣参与计算的云向调用 Register() 的智能合约地址发送交易，并提供其地址和最低存款金额。此功能使用关键字payable进行注释，以便能够从云端接收存款。合约将存款添加到其余额中，并将云地址保存在数组 Cloud[] 中。当注册两个云时，设置状态变量进行计算，并发出事件 registerComplete 以反映状态并指示云已注册成功。在这个阶段，每个云都会使用 task_url 下载计算的 EVM 字节码和输入数据，通过将相应的哈希值与 comp_hash 进行比较来验证它们的完整性，并启动执行。

 (4)  receiveResults()-接收结果函数。每个云在其本地机器上执行计算，并使用 receiveResults() 传递结果（通过发送事务）。事务包括第 3.3.1 节中指定的参数。合约将结果和根值分别保存在数组 Result[] 和 MRoot[] 中。收到结果后，智能合约调用内部函数 Compare() 来检查结果。

 

 (5) Compare()-比较函数。如果两个云的结果都匹配根，比较函数启动 RC 协议（算法 1）。否则，它启动 MCId 协议（算法 3）。

当两个结果匹配时，Compare() 调用 resultConfirmation()，它返回一对布尔值 (true, true)、(true, f alse) 和 (false, false)，表示案例 1、3 和 5 3.2 节分别将其赋给变量case。

如果结果不匹配，则调用 binary-search() 来查找最后匹配的配置索引。然后，要求两个云之一提供两个连续的配置，从匹配的索引开始，以及一致性证明。这将使用内部函数 verify-reduced-step 进行验证。此验证步骤导致 (true, false) 或 (false, true)，分别代表第 3.2 节中给出的情况 2 和 4。这将分配给变量 case。执行 RC（或 MCId）协议后，内部调用 Pay() 函数以获取案例值，以正确分配和/或惩罚云。

(6) QueryGen-查询生成。该函数采用四个整数，即安全参数 κ、由 N 表示的 C 的长度、随机值 d ∈ [2, N -3] 以及包含第一个发布结果的块的索引 idx。 idx 值通过block.number 获得。最后，QueryGen() 返回 qi = (i, xi ), i = 1, 2 形式的两个随机查询。（有关更多详细信息，请参阅第 3.3.2 节，有关 Solidity 代码，请参阅附录 B。）

(7) Pay()-支付函数。该函数根据 3.2 节中描述的情况将奖励分配到云端，返回（剩余的）存款，并将（正确的）结果发送给 PG。

(8) shutDown()-关闭函数。在计算结束时，shutDown() 函数被调用。一旦调用此函数，合约将不再可执行。如果计算不成功，PG 可能会重复上述过程，重新部署智能合约并重新外包计算。

 这是一个基本合约，它可以扩展为包括超时以指定执行时间。

4.2 部署和执行

部署——智能合约是用 Solidity 编写的，这是一种高级语言。代码将被编译成低级机器指令，即 *** 作码，供 EVM 使用。然后 *** 作码被编码为字节码，将使用称为合约创建交易的特定交易（由 PG）部署在以太坊网络上，其结构如下：

 一旦合约创建交易在区块链上发布，交易中的 To 字段将填写网络创建的合约地址。合约地址是确定性的根据 PG 的地址和交易中的 nonce 值计算得出。这样就完成了智能合约的部署。与已部署的智能合约交互。在 scCRR 中，关键字 public 的函数只能被 PG 或注册的云调用，关键字 internal 的函数只能被合约调用。要调用公共函数，调用方将交易发送到合约地址，并在数据字段中指定函数 ID 和输入参数。函数签名的哈希值的前 4 个字节被视为函数 id。调用智能合约函数的交易结构如图 10 所示。

 执行——每个参与的云都将安装一个连接到以太坊网络的以太坊客户端（例如 Geth）。这个客户允许云作为拥有自己的 EVM 的以太坊节点工作，这是一个运行汇编指令（ *** 作码）的有状态机器。

合约代码存储在 EVM [22] 的虚拟 ROM 中。在执行期间，每个 EVM 维护 (i) 一个堆栈来存储 *** 作码间歇执行的输出，(ii) 一个易失性存储器来存储临时数据，例如函数参数、局部变量和返回值，以及 (iii)程序计数器指向当前指令（即 *** 作码）。在执行开始时，堆栈和内存为空，EVM 将程序计数器设置为零。每次执行指令时，堆栈和内存都会相应更新，程序计数器也会递增。

状态和精简配置——我们将 EVM 中程序的执行状态设置为元组（堆栈内容、内存内容、程序计数器），并假设每个云都有一个数据库来存储所有中间执行状态。特定状态的简化配置被定义为建立在该状态之上的 Merkle 树的根哈希。简化后的配置被编码为 EVM 字节码，并在结果不匹配时发送以进行二进制搜索。

在二分搜索阶段之后，其中一个云将两个连续的完整状态，即堆栈、内存内容和程序计数器发送到以太坊网络进行验证。由于以太坊中的智能合约执行是完全确定的，因此它会为任何从相同状态开始的一致实现产生相同的状态转换 [22]。这样，以太坊网络就可以验证计算的正确性。

4.3 延迟分析

使用智能合约会导致 scCRR 的执行延迟，因为与智能合约之间的通信使用以太坊网络。每条消息都以交易的形式发送到智能合约，这需要时间才能被包含在一个区块中；该块必须广播到网络，挖掘并在达成共识后附加到区块链。这些步骤所需的时间取决于区块链，并且可以从发布的网络统计数据中估算出来。在以太坊中，发送交易和将其包含在区块中之间的延迟取决于该交易的 gas 价格 [1]，并且可以由 PG 在创建智能合约时确定。

在下文中，我们将讨论在给定计算中在云和智能合约之间发送和接收的交易数量；请注意，我们不区分智能合约发送的交易和云交易。为了实现方便，我们假设每个云都有部署在区块链上用于发送和接收消息的智能合约。这是必需的，因为在以太坊中，智能合约只能向另一个智能合约发送消息。 –注册时，每个云都会发送一笔交易来支付押金。智能合约发出一个事件，即 registerComplete，以确认注册完成。这总共需要两个事务。

– 执行任务后，每个云将其结果作为交易发送到智能合约（即总共两个交易）。

– 如果结果相同，智能合约调用结果确认函数，依次向云端发出两个查询。作为回应，云提供了关于 作为事务的一致性证明。因此，此阶段涉及四笔交易。 

– 如果结果不匹配，云将参与 MCId 协议执行。首先，他们将运行可能需要多达 个事务的二分搜索。在每一步，scCRR 都会发送云应该响应的下一步的索引。这需要两个事务，因此总共需要多达 个事务。其次，他们将从事验证降步功能；其中一个云提供了两个连续的配置以及一致性证明，总共需要三个事务。

 表 1 显示了智能合约执行的不同阶段所需的交易数量。

 

0x05 结论

智能合约可以用作 TTP 来重构当今使用的许多信息通信系统。使用智能合约构建基于 CRR 的可验证计算系统为可验证外包（通用）计算问题提供了一个有吸引力的解决方案。如果从云到 TTP 的通道可以保密，例如通过使用公钥加密算法，则由受信任的第三方运行 CRR 不会影响 CRR 的安全性。然而，使用智能合约作为 TTP 消除了这种可能性，并使系统面临我们在这里研究的新攻击。

我们的工作提出了许多有趣的研究问题，包括在其他可验证的计算系统中使用智能合约作为 TTP，以及放宽云必须在 EVM 中运行计算的要求。这些是我们未来工作的方向。

0x06  参考文献

[1] 2019. ETH gas station. https://ethgasstation.info/ Accessed on August 19, 2019.

 [2] 2019. RSK. https://www.rsk.co/solutions/ Accessed on August 19, 2019.
[3] David P Anderson. 2004. Boinc: A system for public-resource computing and
storage. In proceedings of the 5th IEEE/ACM International Workshop on Grid
Computing. IEEE Computer Society, 4–10.
[4] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2010. From secrecy to sound-
ness: Efficient verification via secure computation. In International Colloquium
on Automata, Languages, and Programming. Springer, 152–163.
[5] László Babai. 1985. Trading group theory for randomness. In Proceedings of the
seventeenth annual ACM symposium on Theory of computing. ACM, 421–429.
[6] Mira Belenkiy, Melissa Chase, C Chris Erway, John Jannotti, Alptekin Küpçü, and
Anna Lysyanskaya. 2008. Incentivizing outsourced computation. In Proceedings
of the 3rd international workshop on Economics of networked systems. ACM, 85–90.
[7] Iddo Bentov, Rafael Pass, and Elaine Shi. 2016. Snow White: Provably Secure
Proofs of Stake. IACR Cryptology ePrint Archive 2016 (2016), 919.
[8] Vitalik Buterin et al. 2014. A next-generation smart contract and decentralized
application platform. white paper (2014).
[9] Ran Canetti, Ben Riva, and Guy N Rothblum. 2011. Practical delegation of
computation using multiple servers. In Proceedings of the 18th ACM conference
on Computer and communications security. ACM, 445–454.
[10] Kai-Min Chung, Yael Kalai, and Salil Vadhan. 2010. Improved delegation of com-
putation using fully homomorphic encryption. In Annual Cryptology Conference.
Springer, 483–501.
[11] Changyu Dong, Yilei Wang, Amjad Aldweesh, Patrick McCorry, and Aad van
Moorsel. 2017. Betrayal, distrust, and rationality. In Proceedings of the 2017 ACM
SIGSAC Conference on Computer and Communications Security. ACM, 211–227.
[12] Uriel Feige and Joe Kilian. 1997. Making games short. In STOC, Vol. 97. 506–516.
[13] Rosario Gennaro, Craig Gentry, and Bryan Parno. 2010. Non-interactive verifiable
computing: Outsourcing computation to untrusted workers. In Annual Cryptology
Conference. Springer, 465–482.
[14] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1989. The knowledge
complexity of interactive proof systems. SIAM Journal on computing 18, 1 (1989),
186–208.
[15] Dominik Harz and Magnus Boman. 2018. The Scalability of Trustless Trust. In
International Conference on Financial Cryptography and Data Security. Springer,
279–293.
[16] MHR Khouzani, Viet Pham, and Carlos Cid. 2014. Incentive engineering for
outsourced computation in the face of collusion. In Proceedings of WEIS.
[17] Joe Kilian. 1992. A note on efficient zero-knowledge proofs and arguments. In
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing.
ACM, 723–732.
[18] Joe Kilian. 1995. Improved efficient arguments. In Annual International Cryptology
Conference. Springer, 311–324.
[19] Loi Luu, Jason Teutsch, Raghav Kulkarni, and Prateek Saxena. 2015. Demystifying
incentives in the consensus computer. In Proceedings of the 22nd ACM SIGSAC
Conference on Computer and Communications Security. ACM, 706–719.
[20] Viet Pham, MHR Khouzani, and Carlos Cid. 2014. Optimal contracts for out-
sourced computation. In International Conference on Decision and Game Theory
for Security. Springer, 79–98.
[21] Jason Teutsch and Christian Reitwießner. 2017. A scalable verification solution
for blockchains. url: https://people. cs. uchicago. edu/teutsch/papers/truebit pdf
(2017).
[22] Gavin Wood et al. 2014. Ethereum: A secure decentralised generalised transaction
ledger. Ethereum project yellow paper 151, 2014 (2014), 1–32.