Stateless & Stateful Smart Contracts: Lessons in flexibility, scale, and security from digital circuit design

Modern computing systems have digital circuits at their core. There are two types of digital circuits:

• Stateless (combinational) digital logic. Has if/then, and/or/inverter/etc, blocks. Has no internal state; though it can combine with larger systems that do have internal state.
• Stateful (sequential) digital logic. Does have internal state: in addition to if/then/and etc blocks, it has loops which feed back into the circuit.

These two types of digital logic have radically different verifiability properties. It’s easy to verify large combinational digital logic circuits, and therefore to build large verified / secure systems. In contrast, sequential logic is more flexible because it supports loops and recursion, but has limited scale for trustworthy verification.

Smart Contracts

“Smart contracts” systems are a block in the decentralized stack. They process business logic in a decentralized fashion. They sit side-by-side with file storage, databases, etc.

Similar to digital logic, we can have two types of smart contracts:

• Stateless (combinational) smart contract. No internal state.
• Stateful (sequential) smart contract. Has internal state, therefore loops & recursion.

The difference between the two is just like for digital logic. It’s easy to verify large stateless smart contracts, and therefore to build large verified / secure systems. Stateful smart contracts are more flexible, but have limited scale for trustworthy verification.

Most business contracts don’t have loops or recursion. Therefore they can be handled by the more scalable & easier to verify stateless smart contracts systems. There’s still room for stateful smart contracts; and as we shall see we can simplify their architecture via client-side processing (e.g. in the browser).

Let’s drill deeper.

Background: Digital Circuits

Electronics has powered every step of the computer revolution, from the 50s until today, from mainframes to the cloud. Electronics have two types of circuits: analog and digital.

Analog circuits are typically “bare metal” on the physics themselves, operating on continuous values of voltage and current, doing things like amplifying signals or filtering out target frequencies.

Digital circuits abstract away analog in two ways: the signals are binary rather than continuous, and time is clocked rather than continuous. Which means we can simplify how we think about the circuit dynamics: digital circuits do logic processing.

Let’s look at the digital circuit below. It’s a half-adder. It has two inputs: A, B. It has two outputs: S, C. The top gate is a NOR (inverted OR). The bottom gate is a simple AND. S is computed as S = A NOR B. C is computed as A AND B. Written more compactly: S=!(A|B); C=A*B.

You can also write this circuit’s functionality as a truth table: for each combination of values of A={0,1} and B={0,1}, you can write the corresponding output value for S and for C.

A simple digital circuit (half-adder)

The digital circuit below is a “full adder”. It has three inputs (A, B, Cin) and two outputs (S, Cout). The outputs are computed as: S = !( !(A|B) | Cin). Cout = (!(A|B)*C) |(A*B).

A full adder digital circuit

The two circuits I just showed are combinational; they don’t have internal state. The signals simply flow left to right, from inputs to outputs. There are also sequential circuits (not shown) where one of the wires loops from the right to the left providing feedback; and “flip flop” building blocks to preserve state.

Modern chips (ASICs) are composed of digital, memory, and analog/RF building blocks. The memory and analog/RF blocks are designed with the help of dynamical systems simulators that are continuous in time and in value (e.g. SPICE).

It’s tremendous effort to design a memory or analog/RF building block that has even 10 or 100 transistors, because the signals must be sliced so fine-grained.

With digital, it’s significantly easier, because you can abstract signals to just be binary, and time to clocked sequences. Then — significantly — you can write code which specifies the behavior of the digital circuit. This code is automatically compiled into gates, then compiled into instructions on how to physically manufacture the circuit. This abstraction has been key to designing chips with massive complexity. For example, a modern GPU has more than ten billion logic gates.

Digital circuit design is a well-established discipline, going back several decades within the broader field of electrical engineering (EE). There are tens of thousands of digital engineers who spend their days designing the next generations of digital circuits for smartphones, PCs, and the like. There are a couple hundred companies making tools for circuit design; this industry (EDA) is a multi-billion dollar industry also stretching back decades. I spent much of my career here: training as an electrical engineer; and more than a decade in EDA, designing AI algorithms for circuit verification & design tools.

Now that we have context from a circuits perspective, let’s talk about smart contracts.

Stateless (Combinational) Smart Contracts

A stateless smart contract processes any arbitrary logic that does not retain state internally. In electrical engineering terms, it can be framed as a combinational digital logic circuit. Such circuits have Boolean inputs, Boolean operators, and Boolean outputs.

The logic itself is can be represented in one of many canonical framings:

• an arbitrary combination of AND/OR/NOT gates
• simply NAND gates (cool!)
• IF/THEN/ELSE/NOT statements
• a table having one row for each unique input vector and the corresponding output(s)
• and more.

There can be one or more output variables. The number of possible outputs is simply 2^(number of input variables). Any introductory digital circuit design textbook elaborates. Beyond, there is plenty of literature for simplifying logic circuits (e.g. Karnaugh Maps), and plenty of tools for designing and analyzing them.

Simplifying circuits for fun and profit with Karnaugh Maps

We can translate digital logic circuits directly to crypto circuits: Boolean inputs can be signature, time, or facts. OR gates become 1/2 multisig, AND gates 2/2 multisig, and NOT gates remain inverters. The latter only works for inputs that are time and facts, not for inputs that are signatures.

Bitcoin’s scripting supports combinational business logic. So does Ethereum’s Virtual Machine (a subset of EVM functionality). So does Bitshares. And more.

The Interledger Protocol (ILP) has a subset protocol called crypto-conditions(CC) to cleanly specifies these combinational circuits. CC is good to know of because it’s becoming an internet standard via the IETF. It’s basically a schema on JSON. CC has standalone implementations in JavaScript, Python, and more. BigchainDB, Ripple, and other systems directly support crypto-conditions. Therefore, BigchainDB, Ripple, and others support combinational business logic / smart contracts.

The mathematical foundations and technology infrastructure developed for digital logic over the decades can be used for designing crypto circuits. At BigchainDB, several of us are electrical engineers (EEs), so when we help customers with use cases, we sit down and draw out logic circuits with AND/OR/NOT blocks. Once we’re satisfied with the design, we simply implement the circuit in crypto conditions in BigchainDB transactions. It typically takes just a few minutes, perhaps hours at worst.

Stateful (Sequential) Business Logic

This is any arbitrary logic that does retain state internally. That is, it has memory. Or, it’s a combinational logic circuit with at least one feedback loop; and (to be easier to work with) a clock and flip flop(s) to store state. For example, a microprocessor has an internal register (set of flip flops) gets updated according to machine-code instructions that are sent to it. More generally, sequential business logic is a Turing machine that takes in a sequence of inputs, and returns a sequence of outputs. Systems that manifest (a practical approximation of) this are called Turing-complete systems.

The reason to use sequential logic instead of combinational is if you want loops or recursion. In business contracts this is not so common, so I’d be skeptical about resorting to sequential logic for that. (Do you really want a loop in a real contract?) However, it’s a wickedly cool paradigm for deploying software: your software can just “live” out there on the cloud, rather than on some particular servers somewhere. Like a computer virus, but with more control (and a wallet).

Once you have internal state, then verification becomes much harder. The number of possible outputs is not 2^(number of inputs), but rather number of internal states, e.g. 2^(number of internal state variables) if your internal variables are all Boolean. For example, if you have a 3-input combinational circuit, it would have ²³ =8 possible states to verify. But if it’s a sequential circuit with a 32-bit register, then to fully verify you have to check ²³²=4.2 billion states. Formal verification is the practice of thoroughly verifying stateful logic. It’s matured over the decades, especially in the wake of the Pentium integer multiplication bug of the late 90s, but there are still clear limits on the size of the state space that it’s feasible to verify.

Ethereum is the best-known blockchain system that manifests sequential business logic / smart contracts running directly on-chain. Lisk, Rchain, Tezos, and many more also implement it.

In many cases, you only need client-side processing. In this case the client itself — the browser or mobile OS — can do the computation. This is super-cool because it leads to wickedly simple architectures. You can simply write a single-page webapp (using say JavaScript) or mobile app (using say Swift on IoS), and plug into a decentralized database for the backend.

Tools, and Hiring

We’re in the early stages of smart contract design tools. Formal verification has been mature for more than a decade in circuit design, and we’re starting to see its benefits in smart contract design. That’s just a first example. If EDA is any indicator, then we will see many more tools to capture target behavior and compile it to smart contract code; to simulate it and visualize it; to do sensitivity analysis; and more, for both combinational and sequential smart contracts. And, it will all scale.

Also, a thought on hiring. With blockchain all the buzz, there is great demand for smart contract developers. However, most have a couple years experience if you’re lucky. However, there are thousands of digital circuit designers with decades of experience. They have a structured approach to circuit design; and know what tools to wield. To them it will be obvious how to port that knowledge to smart contract design.

Parting Thoughts

There’s a huge difference between stateless and stateful smart contracts. If you know when to use which, you have a new superpower, from which to make appropriate choices of flexibility versus scale.

Wanna get better at it yourself? Pick up a book on digital circuit design. I like the ones by Wakerly and by Rabaey.

Finally: we at BigchainDB wrote about this a year ago, with a slightly different framing. Back then we used the term simple contracts. Since then, we’ve seen people deploying many stateless contracts and calling them “smart contracts”. So be it. That’s fine; we just want to make a distinction somewhere!

Acknowledgements

Many of the thoughts here are based on conversations with my colleague Dimi de Jonghe (an EE like me). Dimi has been spearheading our EE-based smart contract practice. Also, thanks to all my professors and colleagues from the electrical engineering world, for everything you’ve taught me:)