A concurrent perspective on smart contracts Sergey & Hobor, Workshop on Trusted Smart Contracts, 2017
Maurice Herlihy gave a keynote on ‘Blockchains and the future of distributed computing‘ at PODC’17. In his slides (I wasn’t there to hear the talk in person), he recommends reading ‘A concurrent perspective on smart contracts.’ And here we are!
In this paper, we explore remarkable similarities between multi-transactional behaviors of smart contracts in cryptocurrencies such as Ethereum and classical problems of shared-memory concurrency.
If you need a quick refresher on smart contracts in Ethereum and some of their vulnerabilities (including the infamous attack on The DAO) check out ‘Making smart contracts smarter‘ which we looked at back in February. Today’s paper choice covers some of the same ground, but gives us a fresh perspective. The central insight is that, like it or not, smart contracts need to deal with concurrent execution. By making an analogy to concurrent objects and threads, we can begin to see how existing tools and techniques can help us to reason about contracts.
Accounts using smart contracts in a blockchain are like threads using concurrent objects in shared memory.
Let’s unpack that mapping a little bit:
- The blockchain is like shared memory, holding state that is accessible by many parties. Shared memory holds the state for concurrent objects, the blockchain holds the state for smart contracts.
- A smart contract is like a concurrent object. Accessing concurrent objects without appropriate synchronisation can lead to data races and the loss of data or data integrity. Likewise concurrent execution of smart contracts can lead to unintended consequences!
- An account is like a thread – concurrent objects are invoked by threads, smart contracts are invoked by accounts (users or other contracts).
Unlike traditional concurrent objects, a smart contract’s methods are atomic due to the transactional model of computation. That is, a single call to a contract (or a chain of calls to a series of contracts calling each other) is executed sequentially – without interrupts – and either terminates after successfully updating the blockchain or aborts and rolls back to its previous configuration before the call. The notion of “atomicity for free” is deceptive, however, as concurrent behavior can still be observed at the level of the blockchain.
Here are four ways concurrent behaviour can be observed:
- The order of transactions included in a block is not determined at the moment of transaction execution. Outcomes may depend on transaction ordering.
- Contract logic may be spread across several blockchain transactions (e.g., when contracts ‘communicate’ with the world outside of the blockchain).
- A contract that calls another contract exhibits a form of cooperative multi-tasking, a yield. But the called contract may run code unanticipated by the caller (the source of re-entrancy bugs for example).
- A contract could be used as a service managing access to a shared resource (a bit like a concurrent library). “As multi-contract transactions are becoming more ubiquitous, various interference patterns can be observed and, thus, should be accounted for.“
Concurrent smart contract behaviour in the wild
The best known example (because it had financial consequences to the tune of about 30-50M USD) is probably the attack on The DAO, which was a reentrancy bug. The authors of ‘Making smart contracts smarter‘ found 340 contracts on the Ethereum blockchain with reentrancy bugs as part of their analysis.
Previous analyses of this bug have indicated that the problem is due to recursion or unintended reentrancy. In a narrow sense this is true, but in a wider sense what is going on is that sequential code is running in what is in many senses a concurrent environment.
Another example is the BlockKing contract, implementing a simple gambling game. BlockKing relies on the Oraclize service to call Wolfram Alpha as an external number generator. After invoking Wolfram Alpha, Oraclize makes a fresh call into the originating contract at a designated callback.
Between the event and its callback, many things can occur, in the sense that the blockchain can advance several blocks during the call to oraclize_query and the resumption of control at the callback. During this time the state of the blockchain, and even of the BlockKing contract itself, can have changed drastically. In other words, this is true concurrent behavior on the blockchain.
In the BlockKing case, the last caller to invoke the contract has their details stored as the reward recipient, and when callbacks occur, all payouts go to this gambler even if they were initiated by earlier players.
It’s all a bit like watching slow-motion replays of concurrent object bugs!
Do other concurrency issues with shared objects pop up in a blockchain context? Of course they do! The authors show a nice counter based example. Consider the following Java code:
The Counter class on its own (left-hand side of the figure above) is perfectly thread-safe. And yet it is totally useless for implementing even a simple increment operation. In the example on the right hand side, concurrent execution of
incr can invalidate the assertion. (To fix the issue, the Counter class itself needs to provide an atomic implementation of
…given the only two methods, get and set, the implementation of Counter has synchronization properties of an atomic register whose consensus number (i.e., the number of concurrent threads that can unambiguously agree on the outcome of get and set) is exactly 1… Perhaps a bit surprisingly, even though the implementation of Counter is not flawed by itself, its weak atomicity properties renders it quite useless in the presence of an unbounded number of threads…
Here’s an equivalent smart contract.
… it is not difficult to observe that as an implementation of the simplest possible storage (e.g., for some id-related funds), used by multiple different parties to update it’s balance, the Counter contract is as useless as its Java counterpart.
If both get and set calls are made in a single transaction then the execution would indeed be sequential, but there are several scenarios in which they will be made from different transactions.
In both cases, the root of the problem is a lack of strong synchronization primitives. If we add a
testAndSet function (acting like a compare-and-swap) the problem goes away.
The consensus number of testAndSet (and some other similar Read-Modify-Write primitives) is known to be
&inf;, hence it is strong enough to allow an arbitrary number of concurrent parties to agree on the outcome of the operation.
These analogies suggest that we may be able to use existing formal approaches for runtime concurrency verification and atomicity violation detection if we can translate a contract into an equivalent shared-memory concurrent object.
Another model for managing concurrency is exclusive ownership. In Ethereum this is typically seen in contracts that forbid anyone but a dedicated owner to mutate contract state. Solidity’s
modifiers allow for dynamically checked pre- and post-conditions. For example:
If we use the notion that accounts are threads though, we might end up at an equivalent of a read/write lock. The essential fragments of this idea for contracts might look as follows:
… accounts-as-threads is a rather powerful analogy, suggesting a number of solutions to possible synchronization problems that can be taken verbatim from the concurrency literature.
Thinking this way also leads us towards formal reasoning using e.g. Concurrent Separation Logic or Fractional/Counting permissions.
Discussion and direction
The contracts as concurrent objects analogy can further help us to think about multi-contract interactions, and problems of progress and liveness.
The idea of compositional reasoning and verification of mutually-dependent and higher-order concurrent objects using concurrency logics has been a subject of a large research body in the past decade… we believe, that by leveraging our analogy, we will be able to develop a method for modular verification of multi-contract interactions.
The ‘The DAO’ bug sparked a lot of interest in the Ethereum community on preventing similar errors. Section 6 of the paper has a nice round-up of some of the work in this space:
- Solidity contracts with pre/post-conditions can be translated to OCaml code and verified using the Why3 tool.
- A subset of Solidity can be translated into F* (a programming language and framework based on dependent types), and EVM bytecode can also be translated to F*. This enables use of F* to verify contract properties.
- The Ethereum VM has been specified in Lem, with extraction to the Isabelle/HOL proof assistant.
In contrast with these lines of work, which focus predominantly on low-level safety properties and invariant preservation, our observations hint at a more high-level formalism for capturing the properties of a contract behavior and its communication patterns with the outside world. In particular, we consider communicating state-transition systems (STSs) with abstract state as a suitable formalism for proving, e.g., trace and liveness properties of contract executions using a toolset of established tools, such TLA+.
Now wouldn’t that be cool!