Reconstructing Smart Contracts Part I. The Ghost of Undeterminism Erik Zhang, Da Hongfei
The Reconstructing Smart Contracts series is the brainchild of the founders of Antshares, and presents an excerpt of the insights gathered by them while designing Antshares smart contracts. The series, set out to propose a new smart contract design, comprises of three parts and reviews existing smart contract systems through three angles respectively: determinism and resource control; scalability and decoupling; and universality and ecosystem compatibility.
Smart-Contracts and the Blockchain
Since the birth of Bitcoin, Ethereum, and bourgeoning blockchain technology as a whole, the term Smart Contract has frequented financial and tech media. The term Smart Contract was first proposed by cryptography scientist Nick Szabo in 1994, a concept as old as our contemporary Internet. According to Szabo, A smart contract is a computerized transaction protocol that executes the terms of a contract.
Traditionally the lifecycle of a contract comprises 3 stages: negotiation, signing and execution, so it is with smart contracts. However, prior to the advent of Blockchain technology, a single computer could not provide secure and accountable signing and execution services, hence smart contracts have remained a theoretical concept. Bitcoin introduced the world to Blockchain Technology, providing assets like multi-party recording, multi-party computation, transparency of rule sets, and immutability. With this, a secure and accountable record vehicle and runtime environment have been created which allow for the practical implementation of smart contracts.
Unlike traditional computer programs, blockchain-based smart contracts must be deterministic and terminable.
Blockchain systems realize data immutability and computation trust through multi-party storage and computation. Smart contracts run on multiple nodes within a blockchain network, so, should a smart contract be un-deterministic, the consistency of multiple nodes (and hence consensus among them) could not be achieved, driving the network towards stagnation. Furthermore, if a smart contract was to be never-ending, the blockchain nodes processing it would have to consume an infinite amount of time and resources to run the contract, which, as well, would lead to network stagnancy. Below we will discuss these two subjects, determinism and terminality, and elaborate on the different strategies to manage their implications.
Smart Contract Determinism
If a program always produces the same output on the basis of a given input on different computers, or on different runs on the same computer, the program is considered to be deterministic, otherwise it is un-deterministic. A program can be un-deterministic for a number of reasons as listed below:
1. Call on un-deterministic system functions
Developers tend to call system functions to reduce workload when coding. These system functions may contain un-deterministic elements, such as nonce generating and system-time acquiring functions. Once a program has called an un-deterministic function and has used its output, the program itself is rendered un-deterministic.
2. Un-deterministic data sources
If a program does acquire data when running, and the data source is un-deterministic, the program as well becomes un-deterministic. Requesting the top 10 search results for a given search-engine query is a good example. Search engines may return different result-rankings to IP addresses from different countries, and hence produce different outputs for the same input in dissimilar environments.
3. Dynamic Calls
Dynamic Calls refer to a situation in which a program calls a second program, which can only be determined when running. Since the call target of a dynamic call is only decided when running, its actions are rendered un-deterministic.
Since un-deterministic contracts may return differing results on the different nodes comprising a multi-party computational system, they pose the danger of undermining the consistency of blockchain networks, hence blockchain-based smart contracts are obliged to be deterministic. Blockchain developers should be aware of this, and when designing a smart contract system, eliminate all un-deterministic factors. Below we will examine how different blockchain systems address this issue.
Bitcoin has a built-in scripting engine to execute identification scripts. This scripting engine is the predecessor of all blockchain-based smart contract engines. Bitcoin developers may write simple applications on this system, these applications however are rather simple and non-Turing-Complete, providing very limited functionalities. Bitcoin provides no systemic functions or capabilities to call data, let alone dynamic calls. Thus, we can conclude that Bitcoin-based smart contracts are inherently deterministic.
Ethereum-based smart contracts provide no un-deterministic systemic functions, and accessible data is confined to on-chain information only, while external data can only be sent to contracts via transactions. However, target addresses of Ethereum’s Call and CALLCODE orders are conveyed by stacks, enabling contracts to call the code of other contracts when running dynamic calls. This could potentially render the call route of a contract un-deterministic. Fortunately, the data that is accessible to contracts is deterministic by nature, ensuring that all nodes acquire the same target address when running a dynamic call. Thus we can conclude that system consistency is ensured. However, the possible un-deterministic call routes might cause a significant performance loss on scalability. We will elaborate on this in our next article: Reconstructing Smart Contracts Part II. Parallel Universes and Infinite Scaling.
Fabric is a child project developed under Hyperledger, with a smart contract engine embedded in a heavy-weight runtime environment called Docker.
This might sound like an unusual statement, since Docker is normally considered to be a light weight environment. This however is only true in comparison to heavy weight virtualization technologies which simulate physical computers. Within a blockchain context, Docker has to be regarded as a heavy runtime environment. From this arises Fabric’s bottleneck problem with its TPS limited to only a few hundred transactions per second.
Due to Docker’s characteristics, smart contracts deployed on Fabric can utilize almost all functionalities of a physical computer, which makes the system highly un-deterministic. With this in mind, Fabric requires developers to avoid using un-deterministic functionalities when coding, and plans to provide a specialized deterministic function library. However, because of the very design of its bottom-layer, it would be wishful thinking to solely rely on developers abiding by good practice. The un-deterministic ghost may remain invisible until it pops up to cause complications and malfunctions in corner cases.
Halting Problem and Resource Control
The Halting Problem is a computability problem in the field of mathematical logic. In short, the halting problem describes the fundamental inability to determine whether or not a given program can complete in a finite timeframe. This problem can also be expressed as the following question: Is there a program P that can determine whether or not a given input program will complete or enter into an endless loop within a finite timeframe?
In 1936, Alan Turing proved, using Cantor’s Diagonal Argument, that such a program P cannot be formulated, meaning that there’s no universal algorithmic solution to the halting problem.
However, blockchain-based smart contracts must be guaranteed to complete in a finite timeframe, otherwise they will consume infinite time and resources and bring the system to a halt. From Turing’s proof cited above we know however that the halting problem is unsolvable. We cannot pre-determine whether or not a program will end without running it. Hence, the designers of blockchains had to presume that all smart contracts may enter into endless loops, and hence prepare a mechanism for the external abortion of contracts in endless loops. The generally used measures to install such mechanisms are listed below:
Turing-Incomplete blockchain systems provide limited instruction sets with no jump and loop instruction and the like. Smart contracts based on such a system cannot, by definition, enter into endless loops and will eventually come to a halt in a finite timeframe. Bitcoin is one such example. It is worth mentioning that BIP12 proposed to include the OP_EVAL order in the bitcoin script language, which can load scripts in the stacks and dynamically execute them, solving the multi-signature algorithm problem. This proposal was dropped since it would in-directly make the Bitcoin system Turing-Complete and restore the smart contract halting problem.
2)Step and Fee Meter
Since the halting of a contract cannot be foreseen before it is actually executed, we can instead monitor the number of steps it performs, with +1 step for every new instruction executed. When the step meter read passes a certain pre-determent limit, the contract is considered to be in a dead loop, thus a mandatory termination can be initiated. This method requires a blockchain to exercise strong controls over smart contract execution in order to be able to accurately calculate the steps needed for execution, while keeping consistency among nodes.
Another way to achieve the same result is the installation of a Fee Meter, which is technically identical to a Step Meter, but employs economic incentives to reach similar goals.
As the name suggests, a Fee Meter charges a fee for every order execution. In this framework contracts are deployed carrying a pre-paid fee. If the contract is not brought to completion as the contract’s fee deposit is drained, it will be forced to end. This Fee Meter model is the halting mechanism employed by Ethereum, which charges an Ether-based token called Gas to calculate execution fees. Once a contract’s Gas runs out, it will immediately stop, while the Gas invested by its deployer is confiscated.
The Timer halting mechanism uses a measure of execution-time to determine whether or not a contract is in dead loop: if a contract did not complete execution after its set deadline, it is considered to be in a dead loop and will forcefully be brought to an end.
Since the Docker runtime environment is not able to calculate steps or fee charges, the Timer method is Fabric’s halting mechanism of choice.
Although this method partially solves the halting problem, the contract execution time span on different nodes in a distributed system may differ. Nodes have different computational capacities and thus may vary in their judgement regarding the question whether or not a contract has passed its deadline. This poses a huge risk for the consensus process and renders this method highly problematic.
The above mentioned solutions are essentially a resource control method with the aim of setting an upper limit on lines of code, computation, and running time, to limit the resources used by smart contracts within a reasonable scope.
Apart from resource control, virtualized execution environments also serve as a means to isolate resources in order to ensure system security. On a public blockchain, any participant may write and upload smart contracts, which on a Turing-Complete platform might of course include viruses and malware contracts. If smart contracts were to run directly on the hosting OS of the blockchain nodes, a virus could achieve self-reproduction, causing malware contracts to sabotage the host’s own data. Thus, smart contracts must be confined to isolated sandboxes, i.e. virtual machines or Dockers.
Within a sandbox running environment, effective resource isolation is achieved between one contract and another, as well as between contracts and the nodes hosting them. This limits the influence of potentially malicious or malfunctioning contracts on their environment. However, in terms of the degree of isolation, namespace-relying Dockers are not as good as Virtual Machines. So much so that on public clouds, running images of different users on the same host system is explicitly discouraged. For this reason, Docker-based solutions are weaker in terms of security compared to their Virtual Machine counterparts.
Analyzing determinism, terminality, resource control and resource isolation, we can come to conclude that blockchain smart contracts should be deterministic, terminable, and subjected to accurate resource control and isolation capacities. In this regard, blockchain-tailored virtual machine solutions are obviously more advantageous than Docker solutions. Docker solutions, however, have the advantage of coding language flexibility, and do not require the learning of a new language and thus can be easily integrated into current development ecosystems. This of course begs the question: is there a solution combining the advantages of the both – Docker and VM environments? We intend to address this in the final article of this series, Reconstructing Smart Contracts Part III. Compatibility and Ecosystem.
Before that, in our upcoming article: Reconstructing Smart Contracts Part II. Parallel Universes and Infinite Scaling, we look at the reason behind the under-performing of public and consortium blockchains.
About the Writers
The writers of this articles series are the founders of the Antshares Blockchain project (www.antshares.org). Antshares Blockchain is an open-source public blockchain, exploring the frontiers of a programmable smart economy. The birth of the Antshares project dates back to 2014, making it the first blockchain project in China. In 2017, the accumulation of technological experience from Antshares’ early days will come to its blossoming. Technological breakthroughs are to be expected in the field of smart contracts, cross-chain interoperability, new consensus mechanisms and cutting-edge cryptography.
If you liked this article, follow us on Twitter @themerklenews and make sure to subscribe to our newsletter to receive the latest bitcoin, cryptocurrency, and technology news.