从智能合约到半智能审判法庭

张亚宁   |     |   1827 次阅读

原文:https://blog.ethereum.org/2016/02/17/smart-contracts-courts-not-smart-/
翻译:@rubyu2

Ethereum经常被描述为一个自动执行智能合约的平台。尽管这是事实,本文认为,尤其是当更加复杂的系统参与进来时,它在某种程度上是有着智能律师的法庭,但是法官并不是那么智能,或者更正式地讲,依靠有限计算机资源的法官。我们在后面将会看到这个观点将会用于编写非常有效的智能合约系统,可以实现跨链交易或者工作量证明计算被几乎零成本的实施。

法院的类比

首先,你可能知道在Ethereum上的智能合约本身不能从外部世界获取信息。它只能求助于外部参与者代为输入信息。即使如此,它要么必须相信外部参与者,要么验证信息的诚实性。在法庭上,审判官通常会询问专家的观点(通常他们被信任),或者证人的证词来进行交叉验证。
我想这很明显,在Ethereum上的法官计算资源是被限制的,因为gas限制,相对来自外部世界的律师的计算能力,它非常低。但是,这样有限资源的法官仍然可以在非常复杂的法律案件上进行仲裁:它的力量来源于,它可以让辩护者和法官进行多轮验证。

复杂理论

一个非常好的类比,是由Feige, Shamir 和 Tennenholtz发表的一篇文章The Noisy Oracle Problem。他们的主要结论的简单版本是:假设我们有一个合约(法官),可以使用N步来进行计算(可能覆盖多个交易)。这里有多个外部参与者(律师),他们可以帮助法官,他们中至少有一个是诚实的(也就是说至少有一个参与者是遵守给定协议的,其它的可能是恶意的攻击者,会发送任意信息),但是法官不知道哪个是诚实的参与者。这样的一个合约,可以依赖N个记忆组件和任意数量的步骤,在不需要外部帮助的情况下,进行任意计算。(正式版本指出,一个多项式时间验证者在这个模型里可以接受所有的PSPACE)。

这或许听起来有点笨重,但是他们的证明是非常有启发性的,使用PSPACE类比这类问题,可以通过“游戏”被解决。例如,让我们来看下Ethereum合约如何来玩象棋游戏,在几乎不消耗gas的情况下(专家们请原谅我使用国际象棋,这样的NEXPTIME complete模型,但是这里我们使用经典的8x8,所以它实际上是PSPACE...):在这种情况下下棋意味着,一些外部参与者提议下棋位置,然后合约来决定是否这个位置是白方的获胜位置,也就是说白方总是可以赢,假设白方和黑方有无限的聪明。这假设诚实的链外参与者有着足够的计算能力来完美地玩象棋。但是,问题并不是和外部参与者玩象棋,而是确定给定的位置是对于白方是否是胜利的位置,求助于外部参与者(除了其中之一,其他人可能会给出错误的答案来误导)的帮助。我希望你能同意,在没有外界帮助的情况下,做这件事极其困难。简单来讲,我们只看有两个参与者A和B的情况。合约的做法如下:
1. 问A和B,某个位置对于白方是否是胜利的位置。如果两个人都同意,这就是答案(至少有一个是诚实的)。
2. 如果他们不同意,问那个回答“是”(现在我们称呼W,另外一个为B)白方的胜利位置。
3. 如果这步无效(比如没有位置可行),黑方胜利。
4. 否则,执行这步操作,问B黑方的胜利位置(因为B断言黑方可以赢)。
5. 如果这步无效(比如没有没有可行),白方胜。
6. 否则,执行这步操作,问A白方的胜利步骤,然后继续方法3.

这个合约不需要真的了解象棋的战略。它只需要能够确认是否每一步是否有效,所以合约的消耗大概为N*(V+U),N表示移动的步数,V表示验证一步的消耗,U表示更新棋盘的消耗。

这个结果实际上可以改进为差不多N*U+V,因为我们不需要验证每一步。我们只需要更新棋盘(假设每一步都在坐标系内),当我们要问下一步时,我们同时也问前一步是否是无效的。如果回答“是”,我们检查这一步。根据每一步是否有效,就可以判断其中一个选手是否存在欺骗,我们就可以知道谁赢了。

家庭作业:改进合约这样我们只需要存下来每一步的序列,更新棋盘只需要一小部分步骤,执行步骤验证只需要一步,这样的话,总的消耗N*M + tiny(N)*U + V,M是存储一步,tiny是适当的函数,返回极小于N的数字。

在旁注中,Babai, Fortnow and Lund展示了一个模型,律师可以合作但是不能互相通讯,法官被允许掷骰子(这两种变化都很重要)来捕获一个更大的被称为NEXPTIME的类,不确定的指数增长时间。

在游戏中增加密码学

记住之前部分的一个设定,假设交易不会被审查,合约总是会找到谁是诚实的,谁是不诚实的。这会导致一个非常有趣的观察结果,我们现在可以用非常低的交互协议成本去解决复杂的问题,但是我们可以增加密码学经济机制,来确保协议几乎不会被执行:这个机制允许任何人提交计算结果并交一部分保证金。任何人可以挑战这个结果,但是也必须提交保证金。如果至少有一个挑战者,那么交互协议(或多方验证的变体)就会被执行。假设至少有一个诚实的参与者,在提交者和挑战者里,不诚实的参与者总是会被找出,诚实的参与者获得押金(减去一定的百分比,这会抑制不诚实的提交者挑战他们自己)作为奖励。所以最后的结果是,只要至少有一个诚实的人正在观察谁没有被审查,恶意参与者是没有办法成功的,甚至恶意参与者进行尝试的成本都很高。

想要使用计算结果的应用,可以使用押金作为计算信任度的指标:如果提议者有一个巨大的押金,并且相当一段时间内没有人挑战,这个结果可能是正确的。只要有人挑战,应用应该等待协议去解决。我们甚至可以创建计算结果保险来保证链外的检查计算,如果一个错误的结果没有被及早的挑战,可以返回保险金。

二分查找的魔力

在后面的两节中,我们给出两个特定的例子。一个是关于交互验证数据在外链的存在性,第二个是验证常规(决定性的)计算。在这两个里,我们会经常有这样一种情况,提议者有一个非常长的值列表(不能直接被使用到合约中,因为它的长度),以正确的值开头,错误的值结尾(因为提议者想要作弊)。合约可以简单的计算从ith(1+1)st的值,但是检查整个列表就非常昂贵。挑战者知道正确的列表,然后可以问提议者提供列表中的几个值,如果第一个值正确,而后面的值不正确,那肯定至少有一个点i在这个列表中,这个ith的值是正确的,但是(i+1)st是错误的,挑战者的任务就是找到这个位置(让我们称这个点为“转折点”),因为合约可以验证它。

让我们假设列表长度是1.000.000,所以我们搜索范围是1到1.000.000。挑战者可以请求在500.000位置的值。如果正确,至少有一个转折点在500.000到1.000.000之间。如果不正确,至少有一个转折点在1到500.000之间。在这两种情况下,搜索范围都减少了一半。我们现在可以重复这个过程,至到我们到达搜索范围是2,这里肯定是转折点。以2为底的对数可以被用于计算步数,像这样的“二分遍历”任务。在1.000.000的情况下是log1.000.000 ≈ 20步。

便宜的跨链交易

作为第一个真实世界的例子,我想展示如何去设计一个非常便宜的跨链状态和支付验证。基于这样的事实,区块链不是确定的,可以分叉的,这有点复杂,但是整个思路是一样的。

一个提议者提交了一个数据,她想要应用到目标合约中(例如,比特币或者狗币交易,状态值在另外一个Ethereum链,或者任何Merkle-DAG,它的根哈希值在区块链的第一个块中,而且被公开确认的(这很重要)),并且提交了块数字,块头和押金。

注意我们只提交了一个块数字和哈希值。在第一个版本的BTCRelay中,当前所有的比特币块头都需要被提交,他们的工作量证明都被验证过。这个协议只有在攻击时才需要这些信息。

如果一切正常,也就是说,外部的验证者检查块的哈希值符合标准链(和选择性的其他确认),确认交易和数据包含在块中,提议者可以请求返回保证金,跨链交易结束。这是没有攻击者的情况。每笔交易大约花费200000 gas。

如果有任何错误,也就是说有一个恶意的提交者或者恶意的挑战者,挑战者可以有两种可能:
1. 声明这个块无效(因为它不存在或者属于一个废弃的分叉)或者
2. 声明Merkle-hashed数据无效(但是块哈希和数字有效)

记住区块链是一个Merkle-DAG ,包含两个“胳膊”:一个是由块头的链构成,一个是由状态或者交易的Merkle-DAG的构成。一旦我们接受了根(当前的块头哈希)是合法的,验证两个胳膊就是简单的Merkle-DAG-proofs.

(2)因此让我们先考虑第二种情况,因为它相对简单些:因为我们想要尽可能的高效,我们不向提议者请求全部的Merkle-DAG证明。而是,我们只请求DAG从根到数据的路径(也就是子索引的串)。

如果路径太长或者有无效的索引,挑战者可以要求提交者给出在超出范围点的父和子的值,提交者不能提供合法的数据使哈希值符合父节点。否则,我们有这样的情况,根哈希正确,但是某个点的哈希是不同的。使用二分查找我们可以在路径中找到这样的点,我们有正确的哈希在一个不正确的上。提交者如果不能提供子哈希符合父哈希,那么通过合约诈骗就可以被检查出来。

(1)让我们现在来考虑提交者使用一个错误的块或者一个废弃的分叉的块的情况。让我们假设我们有这样一个机制来关联其他区块链块数和Etheruem区块链的时间,那么合约有一个方法告诉块数无效,因为它在未来。提议者现在能提供所有的块头(对于比特币只有80 bytes,如果他们很大,就只提供哈希值)到一个合约已经知道的特定检查点(或者挑战者请求这些块)。挑战者必须做同样的事情,提供一个更高的块的块数和难度值。他们两个现在可以交叉验证他们的块。如果某人发现一个错误,他们可以提交块数到合约,合约可以验证它或者在另外的交互阶段验证。

针对一般计算的特定交互证明

假定我们有一个计算模型,遵循locality,也就是说每一步它只能对内存做局部更改。图灵机遵循locality,但是随机存取机(普通计算机)也是如此如果他们每一步只是修改在内存中固定数量的点。进一步讲,假设我们有一个安全的散列函数,有H bits的输出。如果一个在这个机器的计算需要 t步,并且需要使用最多s bytes 内存/状态,然后我们就可以对这个计算在以太坊上进行交互验证(在提议者和挑战者模型),需要差不多log(t) + 2 * log(log(s)) + 2轮,在一轮中信息不会超过max(log(t), H + k + log(s))k表示“程序计数器”的大小,暂存器,磁带头位置或者其他内部状态。除了在storage里存储信息外,合约需要进行最多机器运算的一步或者一个散列函数的运行。

证明:
计算所有内存的Merkle-tree的想法可以被用于计算每一步。每一步对内存的影响容易被合约验证,因为只有固定数量的点在内存中会被访问,内存的连贯性可以通过Merkle-proofs来验证。

为了方便概括,我们假设每一步只能访问内存中的一个点。协议开始于,提交者提交输入和输出。挑战者开始请求,对于不同时间的步骤i,Merkle-tree的根内存,内部状态或程序的计数器,和内存的位置可以被访问。挑战者可以通过执行二分查找来找到步骤i返回正确的信息,但是i+1步返回错误的信息。这需要最多log(t)轮,信息大小为log(t) resp. H + k + log(s)

挑战者现在请求内存中访问到的值(在步骤前和后)以及兄弟节点的路径到根节点(也就是说一个Merkle proof)。记住在步骤前后兄弟节点是相同的,只是数据本身变化。使用这样的信息,合约可以验证步骤是否正确执行,根哈希是否正确更新。如果合约验证Merkle proof有效,输入内存的数据肯定正确(因为散列函数是安全的,两个提议者和挑战者有相同的pre-root哈希)。如果步骤执行被验证正确,他们的输出内存数据是相同的。因为Merkle tree兄弟节点是相同的,找到不同的post-root哈希的唯一方法,是计算或者Merkel proof有误。

注意,在前面段落提到的步骤需要一轮,消息大小为(H+1)log(s)。因此我们有log(t)+1轮,消息大小max(log(t),k + (H+2)log(s))。进一步讲,合约需要计算哈希函数2*log(s)次。如果它很大,或者哈希函数很复杂,我们可以减少消息的大小,只需要单独应用哈希函数,消耗更多的交互。在Merkle proof执行二分查找方法如下:
我们不向提交者请求全部的Merkle proof,而是只要前和后的值在内存中。合约可以验证执行,所以我们假设状态变化是正确的(包括内部处态次态和内存访问索引在步骤i+1)。情况有两种:
1. 提交者提交了错误的pre-data
2. pre- 和 post-data是正确的,但是Merkle root在post memory中是错的。

在第一种情况下,挑战者进行交互二分查找,从Merkle tree 包含内存数据的叶子到根,找到一个位置,是正确的父节点,但是错误的子节点。这需要最多log(log(s))轮,信息大小为log(log(s)) resp. H bits.最后,因为散列函数是安全的,提交者不能为错误的子节点提供兄弟节点到父节点。这可以通过合约的一个简单散列函数的计算来确认。

在第二种情况下,我们是相反的情况:根节点是错误的,但是叶子节点是正确的。挑战者再次这行一个交互二分查找用最多log(log(s(n))轮,信息大小最多为log(log(s)) resp. H bits,然后找到这个位置,父节点P是错误的,但是子节点C是正确的。挑战者要求提交者提交兄弟节点S,这样(C,S)hash为P,合约可以进行验证。因为我们知道只有给定位置的内存可以被修改,通过这步,S必须在这步之前存在同样的位置在内存的Merkle-tree。更近一步讲,提交者提交的S不可能是正确的,因为(C,S)不能hash为P(我们知道P是错误的,但是C和S是正确的)。所以我们reduced到这种情况,提交者提供错误的节点在pre-Merkle-tree,但是正确的根节点。正如在第一个种情况那样,它需要最多log(log(s))轮,信息大小为log(log(s))resp. H bits去验证。

总的来讲,我们需要进行至少log(t) + 1 + 2 * log(log(s)) + 1轮,消息大小最多max(log(t), H + k + log(s)).

家庭作业:将证明转换为合约,可以使用EVM或者TinyRAM(C)程序和集成到Piper Merriam’s Ethereum computation market.

谢谢Vitalik的建议Merkle-hash内存,允许任意数量的内部步数的内存大小。顺便说下,这可能不是一个新的结果。

实际应用

这些对数非常好,但是在实际中它意味着什么呢?让我们假设我们有一个计算,它需要5秒钟在一个4GHz的计算机使用5G的RAM。简单真实世界时钟频率和人工体系结构步数之间的关系。我们大概需要t = 20000000000约等于2的43次方,和s = 5000000000约等于2的32次方。交互验证这样的计算,应该需要43 + 2 + 2 * 5 = 55轮,也就是说2*55 = 100个块,使用消息差不多128 bytes(基本上取决于k,也就是说架构)。如果我们不交互验证Merkle proof,我们需要44轮(88个块),消息大小为1200 bytes(只有最后一个消息这么大)。

如果你认为110个块(在以太坊差不多30分钟,3个确认在比特币上)听起来很多,别忘了我们之前提到过:在4GH的机器上使用全部的5GB RAM运行5秒钟。如果你通常运行程序需要那么多资源,他们搜索特定的“输入”值来满足特定条件(优化的路径,密码破解,工作证明求解...)。因为我么只需要验证计算,查找值不需要这样运行,我么可以提供一种解决方案,只是从头开始来检查这些条件。

现在,计算和更新Merkle tree为每一步计算,是非常昂贵的,但是这个例子只是展示了这个协议可以广泛应用于区块链。更进一步讲,多数的计算,尤其是函数语言,可以被分割成不同level,我么可以调用一个昂贵的函数使用大量的内存,但是只是输出一个小的数字。我么可以在主协议中把这些当作一个单独的步骤,开始一个新的交互协议,如果有在这个函数被检测出来。最后,正如之前所说:在多数的例子里,我么只是验证输出而不需要去挑战它(只有当我么需要时才计算Merkle tree),因此提议者也几乎会一定失去它的押金。

开放问题

在这篇文章的几个地方,我们假设我么只有两个外部参与者,他们中至少一个是诚实的。我们可以接近这个猜想,通过需要提交者和挑战者都需要押金。一个问题是他们中的一个或许拒绝继续协议,所以我们需要超时。如果我们增加超时,另外一方面讲,一个恶意的参与人可以拖延区块链,使用不相关的交易,以使正确的答案不能及时的被加入到块中。如果有一个可能的合约来检测这种情况,防止拉长超时?更近一步讲,诚实的提议者可以被阻塞在网络外。因为如此(因为诚实的参与者比恶意的参与者多更好),我们或许允许另外的人介入(双方),在经过押金之后。如果我们允许这么做,恶意的攻击者也能介入诚实的一边,然后假装是诚实的。这些听起来有些复杂,但是我有信心它最终会解决的。

 
1 人喜欢