Ethereum is frequently characterized as a foundation for self-executing smart contracts. While this is unquestionably accurate, this article contends that, especially when intricate systems are involved, it resembles a courtroom with astute lawyers and a judge who is not particularly bright, or more formally, a judge with limited computational capabilities. We will explore later how this perspective can be utilized to craft highly efficient smart contract frameworks, enabling cross-chain token transfers or computations like validating proof of work to be executed at minimal expense.
The Court Analogy
To begin with, you are likely aware that a smart contract on Ethereum cannot inherently gather information from the external environment. It can only request outside participants to provide information on its behalf. Moreover, it must either trust the external participants or validate the reliability of the information itself. In a courtroom, the judge typically seeks opinions from experts (whom they generally trust) or testimonies from witnesses that are often confirmed through cross-verification.
It should be clear that the computational abilities of the Ethereum judge are constrained due to the gas limit, which is relatively low when contrasted with the computational prowess of the external lawyers. Nevertheless, a judge with such limitations can still adjudicate very complicated legal matters: Her authority stems from the fact that she can pit the defense against the prosecution.
Complexity Theory
This exact parallel was formalized in a publication by Feige, Shamir, and Tennenholtz, The Noisy Oracle Problem. A greatly simplified version of their principal finding is as follows: Suppose we have a contract (judge) capable of using N steps to execute a computation (potentially distributed over several transactions). There are multiple external participants (lawyers) who can assist the judge, and at least one of them is sincere (i.e., at least one participant adheres to a specific protocol, while the others may act maliciously and send random messages), but the judge is unaware of which participant is trustworthy. Such a contract can execute any computation that can be conducted using N memory cells and an unlimited number of steps without external assistance. (The formal version indicates that a polynomial-time verifier can accept all of PSPACE in this framework)
This may come across as somewhat cumbersome, but their proof is, in fact, quite enlightening and employs the analogy of PSPACE being the category of issues that can be resolved by “games”. For instance, let me illustrate how an Ethereum contract can engage in chess with nearly no gas expenses (experts may excuse me for using chess, which is NEXPTIME complete, but we will consider the traditional 8×8 variation here, so it indeed falls within PSPACE…): Engaging in chess within this context means that some external participant proposes a chess position, and the contract must assess whether the position constitutes a winning scenario for white, meaning white always prevails, assuming both white and black are infinitely clever. This presupposes that the honest off-chain participant possesses sufficient computational power to play chess flawlessly, but well… Thus, the objective is not to compete in chess against the external participants, but to determine if the specified position is a winning scenario for white while seeking assistance from the external participants (all except one of whom might provide misleading answers). I trust you agree that accomplishing this without external aid is extraordinarily complex. For simplicity, we will only consider the scenario in which there are two external participants, A and B. Here is what the contract would execute:
- Inquire of A and B whether this is a winning position for white. If both concur, this is the resolution (at least one is trustworthy).
- If they disagree, question the one who replied “yes” (we will refer to that participant as W from this point forward, and the other one as B) for a winning move for white.
- If the move is invalid (for instance, because no move is feasible), black prevails
- Conversely, 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, due to no possible moves), white prevails
- Otherwise, apply the move to the board, request A for a winning move for white, and continue with step 3.
The contract does not genuinely need to understand chess strategies. It merely needs to verify whether a solitary move is valid or otherwise. Consequently, the expenses for the contract are approximately
N*(V+U), where N signifies the number of moves (ply, specifically), V represents the cost of move verification, and U signifies the expense of updating the board.
This finding can indeed be enhanced to something akin to N*U + V, since we do not need to validate each move individually. We can simply refresh the board (assuming moves are indicated by coordinates) and concurrently ask for the subsequent move while also inquiring if the previous move was invalid. If the response is “yes”, we examine the move. Depending on whether the move was valid or not, one of the players has cheated, revealing who the victor is.
Assignment: Refine the contract so that we only need to retain the sequence of moves and update the board only for a small fraction of the moves, performing move verification only for one single move, thus reducing the costs to around N*M + tiny(N)*U + V, where M denotes the cost for retaining a move, and tiny is an appropriate function that returns a “tiny fraction” of N.
Additionally, Babai, Fortnow and Lund demonstrated that a framework in which the lawyers collaborate but are unable to communicate with one another, and in which the judge is permitted to roll dice (both modifications are crucial), encapsulates an allegedly much broader class known as NEXPTIME, nondeterministic exponential time.
Incorporating Cryptoeconomics into the Game
A crucial aspect to keep in mind from the preceding section is that, provided transactions remain uncensored, the contract will consistently identify the honest and disingenuous actors. This observation leads to the fascinating conclusion that we have an affordable interactive protocol to address complex issues, but we can introduce a cryptoeconomic mechanism that guarantees this protocol is seldom required: The mechanism permits anyone to present the outcome of a computation along with a security deposit. Anyone is allowed to contest the outcome, but they must also provide a deposit. If at least one challenger exists, the interactive protocol (or its multi-prover variant) is executed. Assuming there is at least one truthful participant among the group of proposers and challengers, the malicious participants will be unmasked and the honest participant will secure the deposits (after deducting a percentage, which will deter a fraudulent proposer from contesting themselves) as a reward. Therefore, the ultimate outcome is that as long as at least one honest individual is monitoring who remains uncensored, no malicious participant can prevail, and even attempting to do so will incur costs for the malicious actor.
Entities that aim to utilize the computation result can regard the deposits as an indicator of the reliability of the computation: If there is a significant deposit from the solution proposer and no challenges arise for a specific duration, the outcome is likely accurate. As soon as challenges emerge, entities should await the resolution of the protocol. We could even establish a computation result insurance that guarantees to verify computations off-chain and reimburses users if an invalid result was not contested promptly enough.
The Efficacy of Binary Search
In the next two subsections, I will provide two particular illustrations. One concerns interactively confirming the existence of data in an external blockchain, while the other pertains to validating general (deterministic) computations. In both instances, we will frequently encounter a scenario where the proposer possesses a lengthy list of values (which is not directly accessible to the contract due to its length) beginning with the correct value but concluding with an inaccurate one (as the proposer intends to deceive). The contract can effortlessly compute the (i+1)th value from the ith, yet verifying the entire list would be prohibitively expensive. The challenger has knowledge of the accurate list and can request the proposer to supply several values from this list. Since the first value is accurate and the last is incorrect, there must exist at least one index i in this list where the ith value is correct and the (i+1)th value is incorrect, and it is the challenger’s responsibility to locate this position (referred to as the “transition point”), as this enables the contract to verify it.
Let us assume the list consists of 1,000,000 elements, establishing a search range from 1 to 1,000,000. The challenger inquires about the value at position 500,000. If it is correct, there is at least one transition point between 500,000 and 1,000,000. Conversely, if it is incorrect, there is a transition point between 1 and 500,000. In both scenarios, the search range’s length has been halved. We now continue this process until the search range is reduced to a size of 2, which must indicate the transition point. The logarithm base two can be employed to determine the number of steps such an “iterated bisection” process necessitates. For 1,000,000, this amounts to log 1,000,000 ≈ 20 steps.
Affordable Cross-Chain Transfers
As an initial real-world illustration, I wish to demonstrate how to construct an exceptionally economical cross-chain state or payment verification. Given that blockchains are not deterministic and can fork, this becomes somewhat more complex, yet the fundamental concept remains consistent.
The proposer submits the information she wishes to be accessible in the target contract (for instance, a Bitcoin or Dogecoin transaction, a state value in a different Ethereum chain, or any data within a Merkle-DAG whose root hash is incorporated in the block header of a blockchain and is publicly available (this is crucial)) along with the block number, the hash of that block header, and a deposit.
It is important to note that we only submit a single block number and hash. In the initial version of BTCRelay, all Bitcoin block headers must be submitted and the proof of work verified for each one. This protocol will only require that information in the event of an attack.
If all is well, meaning external verifiers confirm that the block number’s hash corresponds to the canonical chain (and optionally possesses some confirmations) and observe the transaction / data contained within that block, the proposer can request the return of the deposit, thereby concluding the cross-chain transfer. That is all that occurs in a non-attack scenario. This should cost approximately 200,000 gas per transfer.
If something is amiss, meaning we either have a malicious proposer / submitter or a malevolent challenger, the challenger now has two options:
- declare the block hash invalid (because it does not exist or belongs to a forsaken fork) or
- declare the Merkle-hashed data invalid (but the block hash and number valid)
It is noteworthy that a blockchain is a Merkle-DAG composed of two “arms”: one forming the chain of block headers and the other constituting the Merkle-DAG of states or transactions. Once we accept the root (the current block header hash) to be valid, verifications in both arms are straightforward Merkle-DAG proofs.
(2) Let us explore the second case first, as it is simpler: In our pursuit of efficiency, we do not request a complete Merkle-DAG proof from the proposer. Instead, we merely request a path through the DAG from the root to the data (i.e., a series of child indices).
If the path is excessively lengthy or contains invalid indices, the challenger requests the proposer for the parent and child values at the point that extends out of range, and the proposer cannot provide valid data that hashes to the parent. Conversely, we find ourselves in a situation where the root hash is accurate but the hash at some point differs. By employing binary search, we identify a point in the path where we have a correct hash directly above an incorrect one. The proposer will be unable to furnish child values that hash to the correct hash, rendering the fraud detectable by the contract.
(1) Now let us examine the scenario where the proposer utilized an invalid block or a block that formed part of a forsaken fork. Assume we have a mechanism to correlate the block numbers of the other blockchain to the time on the Ethereum blockchain, enabling the contract to identify a block number as invalid if it must occur in the future. The proposer is then required to supply all block headers (only 80 bytes for Bitcoin; if they are overly large, start with hashes only) up to a specific checkpoint already known to the contract (or the challenger may request them in segments). The challenger must also do the same, ideally providing a block with a higher block number / total difficulty. Both parties can now cross-verify their blocks. If a discrepancy is discovered, they can submit the block number to the contract, which can verify it or allow it to be confirmed through another interactive phase.
Particular Interactive Proofs for General Computations
Let us presume we possess a computational model that adheres to locality, meaning it can exclusively make local adjustments to the memory in a singular step. Turing machines conform to locality, yet random-access machines (common computers) are also viable if they only alter a fixed number of points in memory during each step. Additionally, we assume that there exists a secure hash function producing H bits of output. If a computation on such a machine requires t steps and utilizes no more than s bytes of memory/state, then we can execute interactive verification (in the proposer/challenger framework) of this computation on Ethereum in approximately log(t) + 2 * log(log(s)) + 2 rounds, where messages in each round do not exceed max(log(t), H + k + log(s)), with k representing the size of the “program counter”, registers, tape head position, or similar internal state. Besides retaining messages in storage, the contract must execute at most one step of the machine or perform one evaluation of the hash function.
Demonstration:
The concept is to generate (at least upon request) a Merkle-tree of all the memory utilized by the computation at each discrete step. The outcomes of a single step on memory are easily verifiable by the contract, and given that only a fixed number of points in memory will be accessed, the coherence of memory can be confirmed using Merkle-proofs.
Without loss of generality, we assume that only one point in memory is accessed during each step. The protocol initiates with the proposer presenting input and output. The challenger can now ask, for various time steps i, the Merkle-tree root of the memory, the internal state/program counter, and the positions at which memory is accessed. The challenger employs this information to undertake a binary search that leads to a step i where the provided data is accurate, but it is erroneous in step i + 1. This requires no more than log(t) rounds and messages of size log(t) or H + k + log(s).
The challenger now solicits the value in memory that is accessed (before and after the step) alongside all siblings along the path to the root (i.e. a Merkle proof). It is important to note that the siblings remain identical before and after the step, with only the data itself undergoing change. Utilizing this information, the contract can verify whether the step is executed accurately and whether the root hash is modified correctly. If the contract validates the Merkle proof as legitimate, the input memory data must be accurate (due to the security of the hash function and because both proposer and challenger possess the same pre-root hash). If the step execution is also confirmed as correct, then their output memory data is equivalent. Since the Merkle tree siblings are identical, the sole means of finding a different post-root hash is for either the computation or the Merkle proof to contain an error.
It should be noted that the step described in the preceding paragraph utilized one round and a message size of (H+1) log(s). Therefore, we have log(t) + 1 rounds and message sizes of max(log(t), k + (H+2) log(s)) in total. Moreover, the contract needed to evaluate the hash function 2*log(s) times. If s is extensive or the hash function is complex, we can slightly reduce message sizes and achieve merely a singular application of the hash function, albeit at the expense of more interactions. The strategy is to conduct a binary search on the Merkle proof as follows:
We do not require the proposer to send the complete Merkle proof, but rather just the pre- and post-values in memory. The contract can verify the execution of the step, so let us assume that the transition is accurate (including the internal post state and the memory access index at step i + 1). The scenarios that remain are:
- the proposer delivered incorrect pre-data
- pre- and post-data are correct but the Merkle root of the post memory is incorrect
In the former scenario, the challenger conducts an interactive binary search along the path from the Merkle tree leaf encompassing the memory data to the root and identifies a position with a correct parent but an incorrect child. This requires at most log(log(s)) rounds and messages of size log(log(s)) or H bits. Ultimately, since the hash function is secure, the proposer cannot provide a sibling for the incorrect child that hashes to the parent. This can be validated by the contract with a single evaluation of the hash function.
In the latter scenario, we are presented with an opposite situation: The root is incorrect, but the leaf is accurate. The challenger again performs an interactive binary search in no more than log(log(s(n))) rounds with message sizes of log(log(s)) or H bits and discovers a position in the tree where the parent P is incorrect, yet the child C is accurate. The challenger requests the proposer for the sibling S such that (C, S) hash to P, which the contract can then check. Since we know that only the provided position in memory could have been altered during the execution of the step, S must also appear at the identical position in the Merkle tree of memory prior to the step. Furthermore, the value offered by the proposer for S cannot be accurate; otherwise, (C, S) would not hash to P (we understand that P is incorrect while C and S are correct). Consequently, we have reduced this to the circumstance where the proposer presented an incorrect node in the pre-Merkle tree but a correct root hash. As noted in the earlier scenario, this takes a maximum of log(log(s)) rounds and message sizes of log(log(s)) or H bits to verify.
In total, we encountered no more than log(t) + 1 + 2 * log(log(s)) + 1 rounds with message sizes at most max(log(t), H + k + log(s)).
Assignment: Transform this proof into a functioning contract that can be utilized for EVM or TinyRAM (and therefore C) programs and incorporate it into Piper Merriam’s Ethereum computation market.
Appreciation to Vitalik for proposing to Merkle-hash the memory to facilitate arbitrary intra-step memory sizes! This is, by the way, most likely not a groundbreaking result.
In Practice
These logarithmic expressions are appealing, but what does it signify in practice? Let us assume we are executing a computation that takes 5 seconds on a 4 GHz computer utilizing 5 GB of RAM. Simplifying the association between real-world clock speed and steps on a synthetic architecture, we roughly estimate t = 20000000000 ≈ 243 and s = 5000000000 ≈ 232. Interactively validating such a computation should take 43 + 2 + 2 * 5 = 55 rounds, meaning 2 * 55 = 110 blocks and utilizing messages of roughly 128 bytes (primarily depending on k, i.e. the architecture). If we bypass the interactive verification of the Merkle proof, we obtain 44 rounds (88 blocks) and messages of size 1200 bytes (only the final message is so large).
If you claim that 110 blocks (approximately 30 minutes on Ethereum, 3 confirmations on bitcoin) appears to be excessive, remember what we are considering here: 5 seconds on a 4 GHz machine actually consuming a full 5 GB of RAM. If you usually operate programs that require such substantial resources, they seek specific input values that fulfill particular conditions (optimization routines, password cracking, proof of work solving, etc.). Since we solely wish to validate a computation, the search for the values need not be performed in that fashion; we can provide the solution from the start and merely check the condition.
Indeed, it should be relatively costly to compute and update the Merkle tree for each step of computation, but this example is intended to showcase how effectively this protocol scales on-chain. Moreover, most computations, especially in functional languages, can often be divided into levels where we invoke an expensive function that consumes considerable memory but produces a minimal output. We could treat this function as a single step in the main protocol and initiate a new interactive protocol if an error arises within that function. Lastly, as previously mentioned, in most scenarios, we simply authenticate the output and seldom dispute it (it is only then that we need to compute the Merkle tree), as the proposer would almost certainly forfeit their deposit.
Open Issues
In various parts of this article, we assumed that only two external participants are involved and at least one is honest. We can come close to this assumption by mandating a deposit from both the proposer and the challenger. One complication is that one of them might simply decline to continue with the protocol, necessitating timeouts. Conversely, if we implement timeouts, a malicious participant might inundate the blockchain with unrelated transactions, hoping that the response does not get included in a block in time. Is there a mechanism for the contract to identify this situation and extend the timeout? Furthermore, the honest proposer could become excluded from the network. Thus (and due to the preference for more honest rather than malicious participants), we might allow anyone to intervene (on both sides) after making a deposit. However, if we permit this, malicious actors could impersonate the “honest” side and merely feign honesty. All this sounds somewhat complex, yet I am fairly optimistic that it will ultimately be resolved.
