May 27, 2020
By: Silvio Micali
This post focuses on the off-chain component of Algorand’s smart contract architecture, developed by Jing Chen, Maurice Herlihy, Victor Luchangco, Silvio Micali, and Liuba Shrira. The full technical paper will be published in the near future.
Smart contracts make blockchains programmable. Like a vending machine, a smart contract establishes a clearly defined procedure for transferring assets. For example, Alice wants to buy tokens issued by Bob, so she sends coins to Bob’s smart contract. The contract's code counts the coins, perhaps checks that Alice is in the contract's database of qualified investors, and then transfers the correct number of tokens to Alice's account. The exchange is transparent: Alice can inspect the contract’s code, and the code runs without Bob’s participation.
This post describes Algorand's smart contract architecture, and why it departs in significant ways from prior approaches. In particular, Algorand's smart contract architecture includes several kinds of tools because Algorand’s users need to solve several kinds of problems.
First, for everyday needs, Algorand provides Layer-1 smart contracts, a secure fast-path for common, everyday transactions. (We shall recall such smart contracts in a moment.) Second, Algorand provides (Layer-2) off-chain contracts for the “long tail” of smart contracts that require more customization. These are the smart contracts we introduce in this blog.
The Ethereum blockchain was the first to demonstrate the power of smart contracts, so Ethereum smart contracts are the natural starting point for analyzing successor technologies. Their pros and cons have been extensively discussed in the blockchain community, and the discussions have triggered a variety of new designs for smart contract languages. Here, we focus on two issues of particular importance to the Algorand blockchain.
Suppose Alice and Bob agree that if Alice sends 100 “DollarCoins” to Bob, then Bob will transfer 100 “BobTokens” to Alice. Alice wants to be sure that if she transfers the coins, she gets the tokens, and Bob wants similar reassurances. This kind of transaction, where transfers controlled by mutually suspicious parties either both happen or both do not happen, is called an atomic swap. Programming an atomic swap using Ethereum’s smart contracts requires a hashed timelock contract (or something similar) - a delicate, timed, multi-phase protocol, where any programming error can be disastrous. By contrast, as discussed in an earlier post, Algorand Layer-1 smart contracts provide a simple and safe solution to atomic swaps and related problems.
Consider a charming provincial French cheese shop. Here, customers are not allowed to make their own selections. Instead, all the cheese is kept behind a counter, presided over by a shopkeeper. The customers queue up before the counter. The customer at the head of the line is looking for a goat cheese from a particular region. The shopkeeper explains that he has three such cheeses, one mild, one medium, and one sharp, but the medium one is a little salty. After judiciously discussing the relative merits of those cheeses, the customer makes a selection. The shopkeeper slices and weighs the cheese, wraps it in paper and string, and computes a price. The customer fumbles for change, pays, takes her parcel, and leaves, satisfied with her purchase. Bonjour, may I help the next customer?
As in the traditional French cheese shop, every smart Ethereum smart contract execution blocks the progress of the blockchain as a whole. Even worse, every miner must re-execute every contract call, and every new miner must re-execute every contract call that ever happened. Ethereum’s traditional “cheese shop” architecture is a scalability hazard, severely limiting the rate at which new blocks can be produced.
We will see that Algorand’s off-chain contracts are structured more like a modern supermarket. Here, customers make their own selections without asking a shopkeeper. Once a customer has decided what to buy, she queues up briefly at the register to pay. An indecisive shopper hesitating between different kinds of goat cheese will not delay other shoppers, and will not by herself limit the rate at which customers can be serviced.
NOTE: Algorand off-chain contracts should not be confused with Layer-2 payment networks such as the Lightning Network. Payment networks are specialized: they exist only to send payments from one party to another. By contrast, Algorand off-chain contracts are flexible, general-purpose programs.
Algorand Layer-1 smart contracts execute many common, simple transactions directly in the blockchain itself. For example, Algorand Layer-1 smart contracts make the atomic swap transaction mentioned earlier almost trivial. Layer-1 contracts provide atomic transfers, a built-in mechanism that ensures that multiple transactions authorized by mutually suspicious parties are executed as a single atomic unit: either all succeed, or none do. In our example, Alice creates an atomic transfer containing both her payment to Bob and Bob’s payment to her. She signs her payment, Bob signs his, and the doubly-signed atomic transfer containing both payments is then sent to the blockchain.
As another example, suppose Alice wants to issue her own tokens, where each token represents, say, a share in her restaurant's future profits. Ethereum’s smart contracts provide built-in support for its own Ether currency, but clients who wish to create their own currency-like token are left to their own devices. Although standards and conventions have evolved for user-defined tokens in Ethereum, writing such code can still be risky, and there is a long and colorful history of successful attacks on user-defined tokens in Ethereum.
The Algorand smart contract architecture, by contrast, provides built-in support for user-defined Algorand Standard Assets, at the same level as Algorand’s native Algo currency. The Algorand blockchain provides built-in protection against inadvertently creating or discarding tokens, along with direct support for optionally freezing, clawing back, minting, and burning tokens.
As described in an earlier post, Algorand Layer-1 contracts also provide direct support for common kinds of “post-and-sale” transactions, securitized loans, crowdfunding, accredited-only transactions, multi-sig wallets, and other simple, recurring transaction types.
Layer-1 smart contracts are written in TEAL, an assembly-like stack machine language. TEAL provides programmers the expressive power to implement the kinds of common transactions mentioned earlier. Forthcoming extensions to TEAL, ready by summer 2020, will allow programs to store states in Layer-1, and inspect account balances and other blockchain states for even more expressive power. TEAL will also provide enhanced security guarantees for off-chain contracts. In fact, it provides a powerful base for the off-chain contracts described below.
While many simple blockchain transactions are appropriate for the Layer-1 fast path, there is also a “long tail” of applications that require more specialized tools. For example:
Recall that in the Algorand blockchain, new blocks are selected by a consensus committee chosen securely and at random by Algorand’s cryptographic self-selection algorithm. When a user calls an off-chain contract, the call is not directly executed by the consensus committee. Instead, the call is executed and validated by a parallel committee, called the contract execution committee. Each validator on that committee executes the contract call and generates a sequence of effects: the sequence of blockchain transactions generated by the contract call. The contract execution committee then produces a signed certificate endorsing the call's effects. The simple list of effects, together with the signed certificate and other validation conditions, are then submitted to the consensus committee. For efficiency, multiple contract calls can be executed in a batch, so they can all be endorsed with a single certificate. Consensus committee validators never execute user-defined contract code, as in an on-chain contract architecture. Instead, consensus committee validators need only check the certificate and the validation conditions before applying the transaction’s effects.
A blockchain that requires on-chain contracts is like a bank that requires that all financial transactions be carried out by cashier's check. Before spending money, a customer must wait in line, along with all the other customers, at a bank office with only one teller, to escrow the amount of the check. By contrast, a blockchain that uses off-chain contracts is like using a regular checking account: customers write their own checks without queuing at the bank, and funds are transferred later when the check clears.
Figure 1 shows a normal Algorand execution, where a 5000-transaction block is selected every 5 seconds. (The 5000 transactions in a block may indeed include Algorand’s Layer-1 smart contracts without slowing down block production.) Figure 2 shows the effects of adding 10-second contract calls to each block: clearly it is impossible to maintain a 5-second block time if each contract call takes an additional 10 seconds. Figure 3 shows the benefit of executing contract calls off-chain: the contract call can be executed in parallel with regular transactions, without jeopardizing the blockchain’s throughput.
The contract execution committee is chosen by Algorand’s secure, randomized, self-selection algorithm, just like the main consensus committee. Because contract execution, unlike block consensus, is deterministic, the contract execution committee can achieve the same level of security with substantially fewer validators (about 150 validators instead of thousands).
Off-chain contract code is written in a high-level language and is executed by a virtual machine (VM). An off-chain contract has its own long-lived state, called contract storage. For privacy, the contract storage itself does not appear on the blockchain. For security, however, each contract call publishes a commitment to the latest contract storage. Off-chain contracts can read account balances and other on-chain information, and they can issue transactions, such as payments, that modify the blockchain state. Unlike in conventional Ethereum-style contracts, these “effects transactions” are not executed directly. Instead, the call's effects are validated by a quorum of contract execution committee validators. The call’s effects transactions are packaged into a Layer-1 “all-or-nothing” batch of transactions guaranteed to succeed or fail together. The contract execution committee also tracks each call's dependencies. For example, a contract call that transfers 100 tokens from Alice to Bob depends on Alice having a token balance of at least 100. The committee generates a list of dependencies to be checked by the consensus committee before executing the effects. (These checks are fast, simple, scalar comparisons.) Each atomic transaction, together with its certificate and dependencies, is submitted, much like any other sequence of transactions, to the consensus committee, which checks the atomic transaction’s certificate and dependencies, and includes that atomic transaction in a future block.
What could possibly go wrong? Well, off-chain contract calls are “speculative” in the sense that on-chain state, say, an account balance, might change in the interval between when a contract call is validated and when that call's effects reach the blockchain. Even so, correctness is guaranteed. The off-chain contract implementation keeps track of contract call dependencies, ensuring that the effects of a call whose dependencies have been violated will never be included on the blockchain.
What about progress? What if a contract call repeatedly passes contract execution committee validation but never makes it onto the chain because its on-chain dependencies are repeatedly violated? Returning to the checking analogy, regular checks are faster and more convenient than cashier's checks, but a check might still bounce even if there was enough money in the account when it was signed. Nevertheless, even though checks do sometimes bounce, they are more widely used than cashier's checks because most check-writers do not overdraw their accounts. In the same way, off-chain contracts may sometimes fail, but we expect them to succeed most of the time, because their dependencies are mostly under the user's control, and users will refrain from violating their own dependencies.
We are excited about Algorand off-chain contracts because users can write contracts that may be big, computationally demanding, idiosyncratic, and/or complex without clogging up the blockchain for everyone else. Unlike most blockchains, where the smart contract architecture is intimately intertwined with the blockchain architecture, Algorand’s smart contract architecture isolates off-chain contract execution from the blockchain consensus committee. Algorand's smart contract architecture is flexible, and in the future may enable multiple contract execution committees, each with a different service level guarantee, and each with its own contract language and virtual machine. A contract execution committee that validates computationally demanding high-privacy tokens should perhaps be distinct from one that validates highly regulated, data-intensive financial applications. Whatever your specialized smart contract needs, the Algorand smart contract architecture can support a matching language and VM.
The effort of finding a viable language and VM is going to be important for the wide adoption of our off-chain contracts, but it is a separate effort. And we plan to collaborate with others in this effort. Stay tuned!
Jing is an Assistant Professor in the Computer Science Department at Stony Brook University. She is also an Affiliated Assistant Professor in the Economics Department and an Affiliated Member of the Stony Brook Center for Game Theory. Her main research interests are distributed ledgers, game theory, and algorithms. Jing received her Bachelor and Master degrees in Computer Science from Tsinghua University, and her PhD in Computer Science from MIT. She did a one-year postdoc at the Institute for Advanced Study, Princeton. Jing received the NSF CAREER Award in 2016.
Professor Herlihy is a world expert in Distributed Computation. He is the recipient of the 2003 Dijkstra Prize in Distributed Computing, the 2004 Gödel Prize in theoretical computer science, the 2008 ISCA influential paper award, the 2012 Edsger W. Dijkstra Prize, and the 2013 Wallace McDowell award. He is fellow of the ACM, a fellow of the National Academy of Inventors, the National Academy of Engineering, and the National Academy of Arts and Sciences.
Professor Herlihy holds a Ph.D. in Computer Science from M.I.T.
Victor Luchangco is a Senior Algorithms Researcher at Algorand, where he works on protocols and languages for blockchains. Before that, he worked at Oracle Labs and Sun Labs, where he worked on concurrent algorithms and data structures for shared-memory multiprocessors and the Fortress programming language. He received an Sc.D. in Computer Science from the Massachusetts Institute of Technology, with a dissertation on models for weakly consistent memories. He has authored over 50 papers and holds more than 40 patents.
Silvio Micali has been on the faculty at MIT, Electrical Engineering and Computer Science Department, since 1983. Silvio’s research interests are cryptography, zero knowledge, pseudorandom generation, secure protocols, and mechanism design and blockchain. In particular, Silvio is the co-inventor of probabilistic encryption, Zero-Knowledge Proofs, Verifiable Random Functions and many of the protocols that are the foundations of modern cryptography.
In 2017, Silvio founded Algorand, a fully decentralized, secure, and scalable blockchain which provides a common platform for building products and services for a borderless economy. At Algorand, Silvio oversees all research, including theory, security and crypto finance.
Silvio is the recipient of the Turing Award (in computer science), of the Gödel Prize (in theoretical computer science) and the RSA prize (in cryptography). He is a member of the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences and Accademia dei Lincei.
Silvio has received his Laurea in Mathematics from the University of Rome, and his PhD in Computer Science from the University of California at Berkeley.
Liuba Shrira is a Professor in the Computer Science Department at Brandeis University, a Research Affiliate at the Laboratory for Computer Science and Artificial Inteligence at MIT. She received her PhD from Technion (Israel) in 1986. From 1986 to 1997 she was a Research Scientist in the MIT Programming Methodology Group. She joined Brandeis in 1997. In 2004-2005 she was a visiting researcher at Microsoft Research, Cambridge, UK, in 2010-2011 she was a visiting researcher at Microsoft Research Asia and a visiting Professor in the Computer Science Department, Technion. She is currently a visiting Research Fellow at Algorand.
Liuba Shrira’s research interests span aspects of design and implementation of distributed systems and especially storage systems. This includes fault-tolerance, availability and performance issues. Her recent focus is on time travel (in storage), byzantine fault-tolerance, fast transactions, and blockchain computing.
Liuba Shrira has been recognized as a Distinguished Scientist by ACM for "significant accomplishments in, and impact on, the computing field."
In her free time Liuba Shrira dances tango, gardens, reads and cooks.