原文：https://blog.ethereum.org/2016/02/17/smart-contracts-courts-not-smart-/
翻译：@rubyu2
Ethereum is often described as a platform for self-enforcing smart contracts. While this is certainly true, this article argues that, especially when more complex systems are involved, it is rather a court with smart lawyers and a judge that is not so smart, or more formally, a judge with restricted computational resources. We will see later how this view can be leveraged to write very efficient smart contract systems, to the extent that cross-chain token transfers or computations like checking proof of work can be implemented at almost no cost.
Ethereum经常被描述为一个自动执行智能合约的平台。尽管这是事实，本文认为，尤其是当更加复杂的系统参与进来时，它在某种程度上是有着智能律师的法庭，但是法官并不是那么智能，或者更正式地讲，依靠有限计算机资源的法官。我们在后面将会看到这个观点将会用于编写非常有效的智能合约系统，可以实现跨链交易或者工作量证明计算被几乎零成本的实施。
法院的类比
首先，你可能知道在Ethereum上的智能合约本身不能从外部世界获取信息。它只能求助于外部参与者代为输入信息。即使如此，它要么必须相信外部参与者，要么验证信息的诚实性。在法庭上，审判官通常会询问专家的观点（通常他们被信任），或者证人的证词来进行交叉验证。
我想这很明显，在Ethereum上的法官计算资源是被限制的，因为gas限制，相对来自外部世界的律师的计算能力，它非常低。但是，这样有限资源的法官仍然可以在非常复杂的法律案件上进行仲裁：它的力量来源于，它可以让辩护者和法官进行多轮验证。
The Court Analogy
First of all, you probably know that a smart contract on Ethereum cannot in itself retrieve information from the outside world. It can only ask outside actors to deliver information on its behalf. And even then, it either has to trust the outside actors or verify the integrity of the information itself. In court, the judge usually asks experts about their opinion (who they usually trust) or witnesses for a testimony that is often verified by cross-checking.
I guess it is obvious that the computational resources of the judge in Ethereum are restricted due to the gas limit, which is rather low when compared to the computational powers of the lawyers coming from the outside world. Yet, a judge restricted in such a way can still decide on very complicated legal cases: Her powers come from the fact that she can play off the defender against the prosecutor.
复杂理论
一个非常好的类比，是由Feige, Shamir 和 Tennenholtz发表的一篇文章The Noisy Oracle Problem。他们的主要结论的简单版本是：假设我们有一个合约（法官），可以使用N步来进行计算（可能覆盖多个交易）。这里有多个外部参与者（律师），他们可以帮助法官，他们中至少有一个是诚实的（也就是说至少有一个参与者是遵守给定协议的，其它的可能是恶意的攻击者，会发送任意信息），但是法官不知道哪个是诚实的参与者。这样的一个合约，可以依赖N个记忆组件和任意数量的步骤，在不需要外部帮助的情况下，进行任意计算。（正式版本指出，一个多项式时间验证者在这个模型里可以接受所有的PSPACE）。
Complexity Theory
This exact analogy was formalised in an article by Feige, Shamir and Tennenholtz, The Noisy Oracle Problem. A very simplified version of their main result is the following: Assume we have a contract (judge) who can use N steps to perform a computation (potentially spread over multiple transactions). There are several outside actors (lawyers) who can help the judge and at least one of them is honest (i.e. at least one actor follows a given protocol, the others may be malicious and send arbitrary messages), but the judge does not know who the honest actor is. Such a contract can perform any computation that can be carried out using N memory cells and an arbitrary number of steps without outside help. (The formal version states that a polynomial-time verifier can accept all of PSPACE in this model)
这或许听起来有点笨重，但是他们的证明是非常有启发性的，使用PSPACE类比这类问题，可以通过“游戏”被解决。例如，让我们来看下Ethereum合约如何来玩象棋游戏，在几乎不消耗gas的情况下（专家们请原谅我使用国际象棋，这样的NEXPTIME complete模型，但是这里我们使用经典的8x8，所以它实际上是PSPACE...）：在这种情况下下棋意味着，一些外部参与者提议下棋位置，然后合约来决定是否这个位置是白方的获胜位置，也就是说白方总是可以赢，假设白方和黑方有无限的聪明。这假设诚实的链外参与者有着足够的计算能力来完美地玩象棋。但是，问题并不是和外部参与者玩象棋，而是确定给定的位置是对于白方是否是胜利的位置，求助于外部参与者（除了其中之一，其他人可能会给出错误的答案来误导）的帮助。我希望你能同意，在没有外界帮助的情况下，做这件事极其困难。简单来讲，我们只看有两个参与者A和B的情况。合约的做法如下：
- 问A和B，某个位置对于白方是否是胜利的位置。如果两个人都同意，这就是答案（至少有一个是诚实的）。
- 如果他们不同意，问那个回答“是”（现在我们称呼W，另外一个为B）白方的胜利位置。
- 如果这步无效（比如没有位置可行），黑方胜利。
- 否则，执行这步操作，问B黑方的胜利位置（因为B断言黑方可以赢）。
- 如果这步无效（比如没有没有可行），白方胜。
- 否则，执行这步操作，问A白方的胜利步骤，然后继续方法3.
This might sound a bit clunky, but their proof is actually quite instructive and uses the analogy of PSPACE being the class of problems that can be solved by “games”. As an example, let me show you how an Ethereum contract can play chess with almost no gas costs (experts may forgive me to use chess which is NEXPTIME complete, but we will use the classic 8×8 variant here, so it actually is in PSPACE…): Playing chess in this context means that some outside actor proposes a chess position and the contract has to determine whether the position is a winning position for white, i.e. white always wins, assuming white and black are infinitely clever. This assumes that the honest off-chain actor has enough computing power to play chess perfectly, but well… So the task is not to play chess against the outside actors, but to determine whether the given position is a winning position for white and asking the outside actors (all except one of which might be misleading by giving wrong answers) for help. I hope you agree that doing this without outside help is extremely complicated. For simplicity, we only look at the case where we have two outside actors A and B. Here is what the contract would do:
Ask A and B whether this is a winning position for white. If both agree, this is the answer (at least one is honest).
If they disagree, ask the one who answered “yes” (we will call that actor W from now on, and the other one B) for a winning move for white.
If the move is invalid (for example because no move is possible), black wins
Otherwise, apply the move to the board and ask B for a winning move for black (because B claimed that black can win)
If the move is invalid (for example because no move is possible), white wins
Otherwise, apply the move to the board, ask A for a winning move for white and continue with 3.
这个合约不需要真的了解象棋的战略。它只需要能够确认是否每一步是否有效，所以合约的消耗大概为N*(V+U)，N表示移动的步数，V表示验证一步的消耗，U表示更新棋盘的消耗。
The contract does not really need to have a clue about chess strategies. It just has to be able to verify whether a single move was valid or not. So the costs for the contract are roughly N*(V+U)
, where N is the number of moves (ply, actually), V is the cost for verifying a move and U is the cost for updating the board.
这个结果实际上可以改进为差不多N*U+V，因为我们不需要验证每一步。我们只需要更新棋盘（假设每一步都在坐标系内），当我们要问下一步时，我们同时也问前一步是否是无效的。如果回答“是”，我们检查这一步。根据每一步是否有效，就可以判断其中一个选手是否存在欺骗，我们就可以知道谁赢了。
This result can actually be improved to something like N*U + V
, because we do not have to verify every single move. We can just update the board (assuming moves are given by coordinates) and while we ask for the next move, we also ask whether the previous move was invalid. If that is answered as “yes”, we check the move. Depending on whether the move was valid or not, one of the players cheated and we know who wins.
家庭作业：改进合约这样我们只需要存下来每一步的序列，更新棋盘只需要一小部分步骤，执行步骤验证只需要一步，这样的话，总的消耗N*M + tiny(N)*U + V，M是存储一步，tiny是适当的函数，返回极小于N的数字。
Homework: Improve the contract so that we only have to store the sequence of moves and update the board only for a tiny fraction of the moves and perform a move verification only for a single move, i.e. bring the costs to something like NM + tiny(N)U + V
, where M is the cost for storing a move and tiny is an appropriate function which returns a “tiny fraction” of N.
在旁注中，Babai, Fortnow and Lund展示了一个模型，律师可以合作但是不能互相通讯，法官被允许掷骰子（这两种变化都很重要）来捕获一个更大的被称为NEXPTIME的类，不确定的指数增长时间。
On a side note, Babai, Fortnow and Lund showed that a model where the lawyers are cooperating but cannot communicate with each other and the judge is allowed to roll dice (both changes are important) captures an allegedly much larger class called NEXPTIME, nondeterministic exponential time.
在游戏中增加密码学
记住之前部分的一个设定，假设交易不会被审查，合约总是会找到谁是诚实的，谁是不诚实的。这会导致一个非常有趣的观察结果，我们现在可以用非常低的交互协议成本去解决复杂的问题，但是我们可以增加密码学经济机制，来确保协议几乎不会被执行：这个机制允许任何人提交计算结果并交一部分保证金。任何人可以挑战这个结果，但是也必须提交保证金。如果至少有一个挑战者，那么交互协议（或多方验证的变体）就会被执行。假设至少有一个诚实的参与者，在提交者和挑战者里，不诚实的参与者总是会被找出，诚实的参与者获得押金（减去一定的百分比，这会抑制不诚实的提交者挑战他们自己）作为奖励。所以最后的结果是，只要至少有一个诚实的人正在观察谁没有被审查，恶意参与者是没有办法成功的，甚至恶意参与者进行尝试的成本都很高。
Adding Cryptoeconomics to the Game
One thing to remember from the previous section is that, assuming transactions do not get censored, the contract will always find out who the honest and who the dis-honest actor was. This leads to the interesting observation that we now have a rather cheap interactive protocol to solve hard problems, but we can add a crypto economic mechanism that ensures that this protocol almost never has to be carried out: The mechanism allows anyone to submit the result of a computation together with a security deposit. Anyone can challenge the result, but also has to provide a deposit. If there is at least one challenger, the interactive protocol (or its multi-prover variant) is carried out. Assuming there is at least one honest actor among the set of proposers and challengers, the dishonest actors will be revealed and the honest actor will receive the deposits (minus a percentage, which will disincentivise a dishonest proposer from challenging themselves) as a reward. So the end result is that as long as at least one honest person is watching who does not get censored, there is no way for a malicious actor to succeed, and even trying will be costly for the malicious actor.
想要使用计算结果的应用，可以使用押金作为计算信任度的指标：如果提议者有一个巨大的押金，并且相当一段时间内没有人挑战，这个结果可能是正确的。只要有人挑战，应用应该等待协议去解决。我们甚至可以创建计算结果保险来保证链外的检查计算，如果一个错误的结果没有被及早的挑战，可以返回保险金。
Applications that want to use the computation result can take the deposits as an indicator for the trustworthiness of the computation: If there is a large deposit from the solution proposer and no challenge for a certain amount of time, the result is probably correct. As soon as there are challenges, applications should wait for the protocol to be resolved. We could even create a computation result insurance that promises to check computations off-chain and refunds users in case an invalid result was not challenged early enough.
二分查找的魔力
在后面的两节中，我们给出两个特定的例子。一个是关于交互验证数据在外链的存在性，第二个是验证常规（决定性的）计算。在这两个里，我们会经常有这样一种情况，提议者有一个非常长的值列表（不能直接被使用到合约中，因为它的长度），以正确的值开头，错误的值结尾（因为提议者想要作弊）。合约可以简单的计算从ith到(1+1)st的值，但是检查整个列表就非常昂贵。挑战者知道正确的列表，然后可以问提议者提供列表中的几个值，如果第一个值正确，而后面的值不正确，那肯定至少有一个点i在这个列表中，这个ith的值是正确的，但是(i+1)st是错误的，挑战者的任务就是找到这个位置（让我们称这个点为“转折点”），因为合约可以验证它。
The Power of Binary Search
In the next two sections, I will give two specific examples. One is about interactively verifying the presence of data in a foreign blockchain, the second is about verifying general (deterministic) computation. In both of them, we will often have the situation where the proposer has a very long list of values (which is not directly available to the contract because of its length) that starts with the correct value but ends with an incorrect value (because the proposer wants to cheat). The contract can easily compute the (i+1)st value from the ith, but checking the full list would be too expensive. The challenger knows the correct list and can ask the proposer to provide several values from this list. Since the first value is correct and the last is incorrect, there must be at least one point i in this list where the ith value is correct and the (i+1)st value is incorrect, and it is the challenger’s task to find this position (let us call this point the “transition point”), because then the contract can check it.
让我们假设列表长度是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步。
Let us assume the list has a length of 1.000.000, so we have a search range from 1 to 1.000.000. The challenger asks for the value at position 500.000. If it is correct, there is at least one transition point between 500.000 and 1.000.000. If it is incorrect, there is a transition point between 1 and 500.000. In both cases, the length of the search range was reduced by one half. We now repeat this process until we reach a search range of size 2, which must be the transition point. The logarithm to the basis two can be used to compute the number of steps such an “iterated bisection” takes. In the case of 1.000.000, these are log 1.000.000 ≈ 20 steps.
便宜的跨链交易
作为第一个真实世界的例子，我想展示如何去设计一个非常便宜的跨链状态和支付验证。基于这样的事实，区块链不是确定的，可以分叉的，这有点复杂，但是整个思路是一样的。
Cheap Cross-Chain Transfers
As a first real-world example, I would like to show how to design an extremely cheap cross-chain state or payment verification. Due to the fact that blockchains are not deterministic but can fork, this is a bit more complicated, but the general idea is the same.
一个提议者提交了一个数据，她想要应用到目标合约中（例如，比特币或者狗币交易，状态值在另外一个Ethereum链，或者任何Merkle-DAG，它的根哈希值在区块链的第一个块中，而且被公开确认的（这很重要）），并且提交了块数字，块头和押金。
The proposer submits the data she wants to be available in the target contract (e.g. a bitcoin or dogecoin transaction, a state value in another Ethereum chain, or anything in a Merkle-DAG whose root hash is included in the block header of a blockchain and is publicly known (this is very important)) together with the block number, the hash of that block header and a deposit.
注意我们只提交了一个块数字和哈希值。在第一个版本的BTCRelay中，当前所有的比特币块头都需要被提交，他们的工作量证明都被验证过。这个协议只有在攻击时才需要这些信息。
Note that we only submit a single block number and hash. In the first version of BTCRelay, currently all bitcoin block headers need to be submitted and the proof of work is verified for all of them. This protocol will only need that information in case of an attack.
如果一切正常，也就是说，外部的验证者检查块的哈希值符合标准链（和选择性的其他确认），确认交易和数据包含在块中，提议者可以请求返回保证金，跨链交易结束。这是没有攻击者的情况。每笔交易大约花费200000 gas。
If everything is fine, i.e. external verifiers check that the hash of the block number matches the canonical chain (and optionally has some confirmations) and see the transaction / data included in that block, the proposer can request a return of the deposit and the cross-chain transfer is finished. That’s all there is in the non-attack case. This should cost about 200000 gas per transfer.
如果有任何错误，也就是说有一个恶意的提交者或者恶意的挑战者，挑战者可以有两种可能：
- 声明这个块无效（因为它不存在或者属于一个废弃的分叉）或者
- 声明Merkle-hashed数据无效（但是块哈希和数字有效）
If something is wrong, i.e. we either have a malicious proposer / submitter or a malicious challenger, the challenger now has two possibilities:
declare the block hash invalid (because it does not exist or is part of an abandoned fork) or
declare the Merkle-hashed data invalid (but the block hash and number valid)
记住区块链是一个Merkle-DAG ，包含两个“胳膊”：一个是由块头的链构成，一个是由状态或者交易的Merkle-DAG的构成。一旦我们接受了根（当前的块头哈希）是合法的，验证两个胳膊就是简单的Merkle-DAG-proofs.
Note that a blockchain is a Merkle-DAG consisting of two “arms”: One that forms the chain of block headers and one that forms the Merkle-DAG of state or transactions. Once we accept the root (the current block header hash) to be valid, verifications in both arms are simple Merkle-DAG-proofs.
（2）因此让我们先考虑第二种情况，因为它相对简单些：因为我们想要尽可能的高效，我们不向提议者请求全部的Merkle-DAG证明。而是，我们只请求DAG从根到数据的路径（也就是子索引的串）。
(2) So let us consider the second case first, because it is simpler: As we want to be as efficient as possible, we do not request a full Merkle-DAG proof from the proposer. Instead we just request a path through the DAG from the root to the data (i.e. a sequence of child indices).
如果路径太长或者有无效的索引，挑战者可以要求提交者给出在超出范围点的父和子的值，提交者不能提供合法的数据使哈希值符合父节点。否则，我们有这样的情况，根哈希正确，但是某个点的哈希是不同的。使用二分查找我们可以在路径中找到这样的点，我们有正确的哈希在一个不正确的上。提交者如果不能提供子哈希符合父哈希，那么通过合约诈骗就可以被检查出来。
If the path is too long or has invalid indices, the challenger asks the proposer for the parent and child values at the point that goes out of range and the proposer cannot supply valid data that hashes to the parent. Otherwise, we have the situation that the root hash is correct but the hash at some point is different. Using binary search we find a point in the path where we have a correct hash directly above an incorrect one. The proposer will be unable to provide child values that hash to the correct hash and thus the fraud is detectable by the contract.
（1）让我们现在来考虑提交者使用一个错误的块或者一个废弃的分叉的块的情况。让我们假设我们有这样一个机制来关联其他区块链块数和Etheruem区块链的时间，那么合约有一个方法告诉块数无效，因为它在未来。提议者现在能提供所有的块头（对于比特币只有80 bytes，如果他们很大，就只提供哈希值）到一个合约已经知道的特定检查点（或者挑战者请求这些块）。挑战者必须做同样的事情，提供一个更高的块的块数和难度值。他们两个现在可以交叉验证他们的块。如果某人发现一个错误，他们可以提交块数到合约，合约可以验证它或者在另外的交互阶段验证。
(1) Let us now consider the situation where the proposer used an invalid block or a block that was part of an abandoned fork. Let us assume that we have a mechanism to correlate the block numbers of the other blockchain to the time on the Ethereum blockchain, so the contract has a way to tell a block number invalid because it must lie in the future. The proposer now has to provide all block headers (only 80 bytes for bitcoin, if they are too large, start with hashes only) up to a certain checkpoint the contract already knows (or the challenger requests them in chunks). The challenger has to do the same and will hopefully supply a block with a higher block number / total difficulty. Both can now cross-check their blocks. If someone finds an error, they can submit the block number to the contract which can check it or let it be verified by another interactive stage.
针对一般计算的特定交互证明
假定我们有一个计算模型，遵循locality，也就是说每一步它只能对内存做局部更改。图灵机遵循locality，但是随机存取机（普通计算机）也是如此如果他们每一步只是修改在内存中固定数量的点。进一步讲，假设我们有一个安全的散列函数，有H bits的输出。如果一个在这个机器的计算需要 t步，并且需要使用最多s bytes 内存／状态，然后我们就可以对这个计算在以太坊上进行交互验证（在提议者和挑战者模型），需要差不多log(t) + 2 * log(log(s)) + 2轮，在一轮中信息不会超过max(log(t), H + k + log(s))，k表示“程序计数器”的大小，暂存器，磁带头位置或者其他内部状态。除了在storage里存储信息外，合约需要进行最多机器运算的一步或者一个散列函数的运行。
Specific Interactive Proofs for General Computations
Assume we have a computing model that respects locality, i.e. it can only make local modifications to the memory in a single step. Turing machines respect locality, but random-access-machines (usual computers) are also fine if they only modify a constant number of points in memory in each step. Furthermore, assume that we have a secure hash function with H bits of output. If a computation on such a machine needs t steps and uses at most s bytes of memory / state, then we can perform interactive verification (in the proposer/challenger model) of this computation in Ethereum in about log(t) + 2 * log(log(s)) + 2 rounds, where messages in each round are not longer than max(log(t), H + k + log(s)), where k is the size of the “program counter”, registers, tape head position or similar internal state. Apart from storing messages in storage, the contract needs to perform at most one step of the machine or one evaluation of the hash function.
证明：
计算所有内存的Merkle-tree的想法可以被用于计算每一步。每一步对内存的影响容易被合约验证，因为只有固定数量的点在内存中会被访问，内存的连贯性可以通过Merkle-proofs来验证。
Proof:
The idea is to compute (at least on request) a Merkle-tree of all the memory that is used by the computation at each single step. The effects of a single step on memory is easy to verify by the contract and since only a constant number of points in memory will be accessed, the consistency of memory can be verified using Merkle-proofs.
为了方便概括，我们假设每一步只能访问内存中的一个点。协议开始于，提交者提交输入和输出。挑战者开始请求，对于不同时间的步骤i，Merkle-tree的根内存，内部状态或程序的计数器，和内存的位置可以被访问。挑战者可以通过执行二分查找来找到步骤i返回正确的信息，但是i+1步返回错误的信息。这需要最多log(t)轮，信息大小为log(t) resp. H + k + log(s)。
Without loss of generality, we assume that only a single point in memory is accessed at each step. The protocol starts by the proposer submitting input and output. The challenger can now request, for various time steps i, the Merkle-tree root of the memory, the internal state / program counter and the positions where memory is accessed. The challenger uses that to perform a binary search that leads to a step i where the returned information is correct but it is incorrect in step i + 1. This needs at most log(t) rounds and messages of size log(t) resp. H + k + log(s).
挑战者现在请求内存中访问到的值（在步骤前和后）以及兄弟节点的路径到根节点（也就是说一个Merkle proof）。记住在步骤前后兄弟节点是相同的，只是数据本身变化。使用这样的信息，合约可以验证步骤是否正确执行，根哈希是否正确更新。如果合约验证Merkle proof有效，输入内存的数据肯定正确（因为散列函数是安全的，两个提议者和挑战者有相同的pre-root哈希）。如果步骤执行被验证正确，他们的输出内存数据是相同的。因为Merkle tree兄弟节点是相同的，找到不同的post-root哈希的唯一方法，是计算或者Merkel proof有误。
The challenger now requests the value in memory that is accessed (before and after the step) together with all siblings along the path to the root (i.e. a Merkle proof). Note that the siblings are identical before and after the step, only the data itself changed. Using this information, the contract can check whether the step is executed correctly and the root hash is updated correctly. If the contract verified the Merkle proof as valid, the input memory data must be correct (because the hash function is secure and both proposer and challenger have the same pre-root hash). If also the step execution was verified correct, their output memory data is equal. As the Merkle tree siblings are the same, the only way to find a different post-root hash is for the computation or the Merkle proof to have an error.
注意，在前面段落提到的步骤需要一轮，消息大小为(H+1)log(s)。因此我们有log(t)+1轮，消息大小max(log(t),k + (H+2)log(s))。进一步讲，合约需要计算哈希函数2*log(s)次。如果它很大，或者哈希函数很复杂，我们可以减少消息的大小，只需要单独应用哈希函数，消耗更多的交互。在Merkle proof执行二分查找方法如下：
我们不向提交者请求全部的Merkle proof，而是只要前和后的值在内存中。合约可以验证执行，所以我们假设状态变化是正确的（包括内部处态次态和内存访问索引在步骤i+1）。情况有两种：
- 提交者提交了错误的pre-data
- pre- 和 post-data是正确的，但是Merkle root在post memory中是错的。
Note that the step described in the previous paragraph took one round and a message size of (H+1) log(s). So we have log(t) + 1 rounds and message sizes of max(log(t), k + (H+2) log(s)) in total. Furthermore, the contract needed to compute the hash function 2*log(s) times. If s is large or the hash function is complicated, we can decrease the size of the messages a little and reach only a single application of the hash function at the cost of more interactions. The idea is to perform a binary search on the Merkle proof as follows:
We do not ask the proposer to send the full Merkle proof, but only the pre- and post values in memory. The contract can check the execution of the stop, so let us assume that the transition is correct (including the internal post state and the memory access index in step i + 1). The cases that are left are:
the proposer provided the wrong pre-data
pre- and post-data are correct but the Merkle root of the post memory is wrong
在第一种情况下，挑战者进行交互二分查找，从Merkle tree 包含内存数据的叶子到根，找到一个位置，是正确的父节点，但是错误的子节点。这需要最多log(log(s))轮，信息大小为log(log(s)) resp. H bits.最后，因为散列函数是安全的，提交者不能为错误的子节点提供兄弟节点到父节点。这可以通过合约的一个简单散列函数的计算来确认。
In the first case, the challenger performs an interactive binary search on the path from the Merkle tree leaf containing the memory data to the root and finds a position with correct parent but wrong child. This takes at most log(log(s)) rounds and messages of size log(log(s)) resp. H bits. Finally, since the hash function is secure, the proposer cannot supply a sibling for the wrong child that hashes to the parent. This can be checked by the contract with a single evaluation of the hash function.
在第二种情况下，我们是相反的情况：根节点是错误的，但是叶子节点是正确的。挑战者再次这行一个交互二分查找用最多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去验证。
In the second case, we are in an inverted situation: The root is wrong but the leaf is correct. The challenger again performs an interactive binary search in at most log(log(s(n))) rounds with message sizes of log(log(s)) resp. H bits and finds a position in the tree where the parent P is wrong but the child C is correct. The challenger asks the proposer for the sibling S such that (C, S) hash to P, which the contract can check. Since we know that only the given position in memory could have changed with the execution of the step, S must also be present at the same position in the Merkle-tree of the memory before the step. Furthermore, the value the proposer provided for S cannot be correct, since then, (C, S) would not hash to P (we know that P is wrong but C and S are correct). So we reduced this to the situation where the proposer supplied an incorrect node in the pre-Merkle-tree but a correct root hash. As seen in the first case, this takes at most log(log(s)) rounds and messages of size log(log(s)) resp. H bits to verify.
总的来讲，我们需要进行至少log(t) + 1 + 2 * log(log(s)) + 1轮，消息大小最多max(log(t), H + k + log(s)).
Overall, we had at most log(t) + 1 + 2 * log(log(s)) + 1 rounds with message sizes at most max(log(t), H + k + log(s)).
家庭作业：将证明转换为合约，可以使用EVM或者TinyRAM（C）程序和集成到Piper Merriam’s Ethereum computation market.
Homework: Convert this proof to a working contract that can be used for EVM or TinyRAM (and thus C) programs and integrate it into Piper Merriam’s Ethereum computation market.
谢谢Vitalik的建议Merkle-hash内存，允许任意数量的内部步数的内存大小。顺便说下，这可能不是一个新的结果。
Thanks to Vitalik for suggesting to Merkle-hash the memory to allow arbitrary intra-step memory sizes! This is by the way most likely not a new result.
实际应用
这些对数非常好，但是在实际中它意味着什么呢？让我们假设我们有一个计算，它需要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（只有最后一个消息这么大）。
In Practice
These logarithms are nice, but what does that mean in practice? Let us assume we have a computation that takes 5 seconds on a 4 GHz computer using 5 GB of RAM. Simplifying the relation between real-world clock rate and steps on an artificial architecture, we roughly have t = 20000000000 ≈ 243
and s = 5000000000 ≈ 232
. Interactively verifying such a computation should take 43 + 2 + 2 * 5 = 55 rounds, i.e. 2 * 55 = 110 blocks and use messages of around 128 bytes (mostly depending on k, i.e. the architecture). If we do not verify the Merkle proof interactively, we get 44 rounds (88 blocks) and messages of size 1200 bytes (only the last message is that large).
如果你认为110个块（在以太坊差不多30分钟，3个确认在比特币上）听起来很多，别忘了我们之前提到过：在4GH的机器上使用全部的5GB RAM运行5秒钟。如果你通常运行程序需要那么多资源，他们搜索特定的“输入”值来满足特定条件（优化的路径，密码破解，工作证明求解...）。因为我么只需要验证计算，查找值不需要这样运行，我么可以提供一种解决方案，只是从头开始来检查这些条件。
If you say that 110 blocks (roughly 30 minutes on Ethereum, 3 confirmations on bitcoin) sounds like a lot, don’t forget what we are talking about here: 5 seconds on a 4 GHz machine actually using full 5 GB of RAM. If you usually run programs that take so much power, they search for specific input values that satisfy a certain condition (optimizing routines, password cracker, proof of work solver, …). Since we only want to verify a computation, searching for the values does not need to be performed in that way, we can supply the solution right from the beginning and only check the condition.
现在，计算和更新Merkle tree为每一步计算，是非常昂贵的，但是这个例子只是展示了这个协议可以广泛应用于区块链。更进一步讲，多数的计算，尤其是函数语言，可以被分割成不同level，我么可以调用一个昂贵的函数使用大量的内存，但是只是输出一个小的数字。我么可以在主协议中把这些当作一个单独的步骤，开始一个新的交互协议，如果有在这个函数被检测出来。最后，正如之前所说：在多数的例子里，我么只是验证输出而不需要去挑战它（只有当我么需要时才计算Merkle tree），因此提议者也几乎会一定失去它的押金。
Ok, right, it should be quite expensive to compute and update the Merkle tree for each computation step, but this example should only show how well this protocol scales on chain. Furthermore, most computations, especially in functional languages, can be subdivided into levels where we call an expensive function that use a lot of memory but outputs a small number. We could treat this function as a single step in the main protocol and start a new interactive protocol if an error is detected in that function. Finally, as already said: In most cases, we simply verify the output and never challenge it (only then do we need to compute the Merkle tree), as the proposer will almost certainly lose their deposit.
开放问题
在这篇文章的几个地方，我们假设我么只有两个外部参与者，他们中至少一个是诚实的。我们可以接近这个猜想，通过需要提交者和挑战者都需要押金。一个问题是他们中的一个或许拒绝继续协议，所以我们需要超时。如果我们增加超时，另外一方面讲，一个恶意的参与人可以拖延区块链，使用不相关的交易，以使正确的答案不能及时的被加入到块中。如果有一个可能的合约来检测这种情况，防止拉长超时？更近一步讲，诚实的提议者可以被阻塞在网络外。因为如此（因为诚实的参与者比恶意的参与者多更好），我们或许允许另外的人介入（双方），在经过押金之后。如果我们允许这么做，恶意的攻击者也能介入诚实的一边，然后假装是诚实的。这些听起来有些复杂，但是我有信心它最终会解决的。
Open Problems
In several places in this article, we assumed that we only have two external actors and at least one of them is honest. We can get close to this assumption by requiring a deposit from both the proposer and the challenger. One problem is that one of them might just refuse to continue with the protocol, so we need to have timeouts. If we add timeouts, on the other hand, a malicious actor could saturate the blockchain with unrelated transactions in the hope that the answer does not make it into a block in time. Is there a possibility for the contract to detect this situation and prolong the timeout? Furthermore, the honest proposer could be blocked out from the network. Because of that (and because it is better to have more honest than malicious actors), we might allow the possibility for anyone to step in (on both sides) after having made a deposit. Again, if we allow this, malicious actors could step in for the “honest” side and just pretend to be honest. This all sounds a bit complicated, but I am pretty confident it will work out in the end.
