Smart contracts might encode legal contracts written in natural language to represent the contracting parties' shared understandings and intentions. The issues and research challenges involved in the validation and verification of smart contracts, particularly those running over blockchains and distributed ledgers, are explored. T he world of commercial computing and IT has been abuzz recently regarding a new technology, called variously blockchains, distributed ledgers, or shared ledgers. The underlying blockchain technology was invented in 2008 to support the creation and exchange of the Bitcoin cryptocurrency without the need for a controlling central authority. 1 The Blockchain platform and associated cryptocurrency were implemented and launched in 2009. In the years since, people have seen many potential applications for such technology, particularly in finance and government. For instance, in the financial sector, more than 80 global financial institutions have partnered in the R3 consortium, which recently released a conceptual framework, Corda, for smart contracts in finance. 2 To any participant old enough, the level of excitement is only matched by that for the emerging World Wide Web in the mid-1990s. A distributed ledger is a shared database, fully replicated at multiple autonomous sites or nodes, and without any node having central or privileged control. Updates to the database require execution of an agreed multinode decision protocol; normally, data can only be appended to but not erased from the shared database. A blockchain is a special type of distributed ledger in which the data is collated into "blocks" before being added to the shared database, and the blocks are linked together to form a single sequential chain. Cryptographic methods can be used to encrypt data, authorize data for upload, and chain blocks together. The Bitcoin blockchain was invented for issuing, executing, and recording transactions of a cryptocurrency, Bitcoin. A distributed ledger can also use or support an electronic currency, even if the database is intended for other purposes.  We can answer this question by comparing blockchain technology to the web. The web made it relatively easy to share information between one person or organization and others, either by placing the information directly onto a webpage, or by enabling access to the information via a webpage (for example, when stored in a database). A webpage, therefore, is akin to a blackboard, where one person-the controller of the server-has the power to write contents onto the board, as well as to erase contents from it. If the webpage is public, then anyone can read the board's current contents. If the webpage requires access permission (as, for example, subscription newspaper sites do), then the ability to read the contents might be limited to a private group. Under this metaphor, distributedledger technologies (DLTs) provide blackboard readers with some extra powers, at the possible expense of the writer's powers. Distributed ledgers only allow content to be written to the blackboard if the readers first agree, according to some prespecified voting rules. For example, for content to be added, all readers, a majority of readers, or a particular nominated reader might have to agree. Board contents are added in a manner that links them cryptographically to past board contents, forming the "chain" in blockchain. In addition, board contents are impossible to erase. Indeed, "erasure" might only be possible by starting a new board that is the same as the original blackboard up to the point just prior to where the contents are to be erased. Because this action creates two parallel chains that are identical to the point where they diverge, the process is called forking the blockchain. These additional rights for readers create some interesting consequences, which explain much of the excitement about blockchain technology. The first consequence is that anyone writing onto the board knows that the other participants (the readers) have seen the content: they had to have read it to vote on it before it was uploaded to the board. So everyone party to the distributed ledger knows the same content (that is, the participants have "shared state" for the variables on the ledger) and everyone knows that everyone knows this, and so on. In the language of game theory, 3 the participants have common knowledge, which makes it impossible for a participant to plausibly repudiate a shared ledger's content at a subsequent time. Second, the chaining of content means that any change to past contents requires changes to all the later contents. Such changes could not happen surreptitiously, and, like all proposed writing to the board, would require prior participant approval. Hence, the past records are effectively immutable. Third, the shared ledger is not stored on only one machine, but, rather, copies are stored locally on each of the participants' machines. Every reader has a copy of the board, and these copies stay in sync with one another. This creates significant challenges for anyone wishing to corrupt or alter the contents, because every participant machine would need to be hacked. These properties are the origin for the statement that DLTs eliminate the need for trust. Two or more parties engaging in a transaction online need to be sure that commitments will be honored and that individual actions of multistep transactions will not be reversed. Traditionally, parties who did not know one another would use a mutually trusted third party, often a law firm, bank, or other regulated entity, to assist with this by, for example, acting as a witness to promises and by holding funds in escrow until other steps of a transaction were completed. DLT ensures that all promises and actions are witnessed by all the participants in the shared ledger, not only the parties to the transaction, and makes it difficult or impossible for any party to subsequently repudiate, corrupt, or reverse the actions undertaken. Of course, the participants might not need a trusted third party to witness their individual transactions, but they will still need to trust the software being used. Anything expressible in digital form can be written on an electronic blackboard. In addition to transaction data, a distributed ledger can also hold computer programs. Such programs could use data from blockchain records as inputs and then generate outputs which are, in turn, written to that same or another blockchain. If stored on a blockchain and executed, their execution will occur locally at each participant node connected to the blockchain. Because many of the applications envisioned for distributed ledgers involve coordination between distinct people or organizations, an obvious application of such computer programs is the automatic execution of business workflows across multiple organizations. For example, the legal movement of physical goods from one country to another typically requires export and import permissions from the countries involved. Associated with these permissions might be taxes or duties, evidence of payment of which is required for the relevant permissions to be granted. The vendors and buyers of these goods might require bridging finance to cover delays in receipt of payments or goods, and they might purchase insurances of various forms along the chain. There may be multiple parties: vendors and buyers of the goods, transporters, banks providing trade finance, insurance companies, different countries' customs departments, and so on. The workflow could-at least, in theory-be managed by a sequence of computer programs that execute automatically as successive intermediate milestones in the physical goods' journey are reached. Such programs are examples of smart contracts, a term invented by Nick Szabo before Blockchain's development. According to Szabo, a smart contract is "a set of promises, specified in digital form, including protocols within which the parties perform on these promises." 4 To the extent that such programs embody agreements between two or more organizations, distributed ledgers are a natural home for these programs. The advantage of putting the records of these events and the controlling programs onto a distributed ledger is that the various parties can all see these programs and monitor the trade flow progress as it happens. Moreover, the ledger tracks the chain of custody for the assets involved and records their provenance. In addition, smart contracts on distributed ledgers of assets often have the capacity to do real-time settlement for the assets embedded or represented in the ledger. Whereas a blockchain is a record of who owns what amounts of, for example, a cryptocurrency, smart contracts on that blockchain can effectively settle transfer of that cryptocurrency in its native form. Whereas assets are dematerialized and then recorded onto a blockchain, smart contracts can perform the same function. These smart contracts have a feature that they would not have had they been recorded on a medium other than the medium in which those assets exist. This feature is a key reason for the disruptive nature of distributed ledger and smart contract technologies in finance. Because smart contracts embody and execute workflows, they could potentially be used for automation of regulatory workflows, for example, reporting and monitoring of required data, checking of compliance, approval (or not) by a regulator, and even levying and payment of fines for noncompliance. Such applications, which Philip Treleaven termed RegTech, have significant potential for the application of AI to governmental and regulatory activities. As with distributed ledgers themselves, because the technology is still emerging, smart contracts' nature and form are diverse. For instance, the design of smart contracts might differ significantly according to whether or not the distributed ledger on which they execute is permissioned (because this influences the ability to identify participants), and whether or not the ledger has an internal cryptocurrency. Sean Murphy and Charley Cooper have proposed a spectrum of smart contract definitions according to the extent to which the contract embodies computer code versus natural language (see Figure 1) .  there is a role for documents written in natural language. The document might duplicate the code, or it might complement it. Even at the far left, where there is no natural language document, the code will execute some intentions of the relevant parties based on some shared understandings, both of which might be implicit. From this spectrum, we can identify three components: electronic program code, a natural language contract, and the shared understandings and intentions of the parties. Any particular smart contract might involve any combination of the three components, and each component's role might vary, as indicated in Figure 1 . To ensure that smart contract programs execute correctly, we have identified several classes of questions-listed below-corresponding to the relationships between the different components. Figure 2 further illustrates these components and relationships. These questions show why we can dismiss smart contracts that lack a natural language component: if the only natural language intention is to execute the code, then questions 1-5 become trivial and all possible outcomes are validated. This would leave the smart contract owners in a situation in which they seemingly desired things they had no prior knowledge of. For instance, if there was a bug in the code (which is very plausible), no developer or participant would know about the bug, but the execution of that bug would now become intended by the smart contract owners without their foreknowledge. Because it is not possible to intend something unwittingly, we see that a smart contract without at least a small natural language underpinning is not sensible. In terminology adopted by IEEE, 6 questions 1 and 2 are about validation-respectively, validation of a natural language contract and validation of an individual computer program. Questions 3 and 4 are about verification of the properties of a program. Question 5 concerns verification of the properties of a collection or a system of programs. An example might illustrate these issues. The recent experience of the DAO, a decentralized autonomous organization, is probably well-known to readers. 7 This open source computer program was created to run over the Ethereum distributed ledger with the aim of pooling crowdsourced funds for investment in start-ups. Throughout May 2016, some 11,000 investors gave cryptocurrency then-valued at more than $150 million. Although the code did what it was intended to do (question 3), it was also used to do something that was not intended (question 4): a recursive calling vulnerability was exploited by a malicious person (or team) to transfer many of the invested funds to an account he or she (or they) controlled. So, the program code ran correctly but in a manner unintended by the developers. Because of inbuilt delays in funds transfers, the participant community was able to reverse this, but only by creating a fork of the Ethereum blockchain, that is, another blackboard forked prior to the point of the hack event. Each of these five validation and verification questions could be answered for any particular smart contract by means of human analysis and discussion between the relevant parties. The human expertise required for Most smart contract applications being considered in industry are intended to automate or semiautomate business processes, which are combinations of sequential, parallel, or interleaved actions undertaken over time by multiple participants. For this reason, action sequences and message sequence charts are obvious specification and design tools for the interactions and communications between participants in distributed ledgers, and deterministic finite automata (DFA) are an obvious computational model of their operation. DFA present an external view of the actions of a participant or a smart contract across a ledger, without modeling their internal states. We can formally model the internal states of entities (participants or smart contracts), and how these change over time as they interact with one another, using modal logics with temporal and epistemic operators. For example, public announcement logics (such as that described by Jan Plaza 10 ) represent updates in the knowledge of hearers when speakers make announcements to a group. With such logics, we can reason about the participants' knowledge over time and understand, for instance, the extent to which malicious coalitions of nodes control other participants' knowledge. A key research challenge will be formally specifying the properties of interest in the modal logic so that these properties can be verified. Trace alignment will be an important technique for verification of these programs when considered as part of a larger business process. 11 In this approach, we use formal models (DFA and/or modal logics) to create expected execution runs, or traces, and then another formal representation, such as linear temporal logic, to undertake the verification. Techniques from AI planning might then be used to automatically fix any misalignments identified. To apply formal verification methods to the five questions, we need to have certain tools and methodologies in place. For questions 2-5, we need a formal (machine-readable) representation of a smart contract program and its effects on the world in which it exists. If we view a smart contract as just a computer program operating on some real or virtual machine, ignoring (for the moment) that it operates in a distributed fashion across separate nodes, then this is straightforward, at least in principle. Program language semantics theory distinguishes several different types of formal representations of programs. The first type, axiomatic semantics, defines each program in terms of the preconditions that must exist before the program can be executed, and the postconditions that apply following its execution utterance. A second type of semantics, an operational semantics, considers the smart contract as computational instructions that operate successively on some abstract or virtual machine's states. The program commands are thus seen as state-transition operators, and the operational semantics defines these transitions precisely. Finally, in denotational semantics, each language syntax element is assigned a relationship to an abstract mathematical entity, or its denotation. We then seek to reason about the program's properties by reasoning about the denoted mathematical entities, and vice versa. Each of these types of semantics can apply to particular classes of smart contracts when viewed simply as programs (that is, ignoring the blockchain platform). For most smart contracts, creating both an axiomatic and an operational semantics should be straightforward. An operational semantics will be of most value when we are exploring the properties of collections of smart contracts (that is, in trying to answer question 5), because this semantics should facilitate the analysis of effects due to concurrency and interaction. It might be that verifying desirable properties of these programs requires an assumption that the machines running the contracts all have some common implementation environment, possibly a virtual environment. Thus, proving low-level S E P T E M B E R 2 0 1 7 55
Magazzeni et al. REF claim that it is essential to validate and verify the smart contract before deploying it to the blockchain due to security and integrity concerns.
Validation and Verification of Smart Contracts: A Research Agenda
Computer
Computer
Computer Science