BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage Articles Deterministic Execution on the JVM

Deterministic Execution on the JVM

Key Takeaways

  • Cryptocurrency as it currently stands is a bad fit for a general purpose payment network
  • Distributed shared ledgers with cryptographic verification seem to be a potentially useful tool for a reasonable number of technical use cases
  • There seems to be promise in bundling a shared ledger with a programming framework for writing "smart contracts" that act upon the shared ledger state
  • Constructing this smart contract language runs into fundamental computer science problems almost straightaway
  • The JVM and classloading provides a sound basis for circumventing these problems and providing provably deterministic execution of smart contracts

Many developers have now heard of Bitcoin and the broader field of cryptocurrency. Lurid tales of illicit transactions and criminal activity have appeared across the media, and Bitcoin has been at the heart of many of these stories.

It is now increasingly clear that Bitcoin’s primary attributes (a public pseudonymous ledger of transactions, irreversible transactions and a trustless network of accounts) are a very bad fit for a payment network for day-to-day legal transactions.

However, from a purely technical standpoint, the development of cryptocurrency has contained several interesting and potentially novel aspects. Legitimate use cases for these aspects are only just starting to be developed. As the technical aspects of Bitcoin and other cryptocurrencies are being broken apart and disentangled, some very interesting technical work is coming in to view.

These types of systems show promise in industries such as supply chain management, financial technology (including clearing systems) and ownership registries (especially for physical assets in jurisdictions that may have problems with record-keeping or corruption). The "blockchain" buzz of 2016 is already fading, but this is allowing real use cases to emerge for the technology, without the accompanying hype.

Of particular interest is the Hyperledger project run under the auspices of the Linux Foundation, bringing together some 80 organizations with a shared interest in distributed ledgers, blockchains and related cryptocurrency technology.

In this article, we want to focus on one particular technical aspect of this emerging area, so let’s consider the case where all participants in a shared ledger are known to each other (perhaps by having some central trusted third party distribute known key pairs to participants). This removes trustlessness as a feature of the ledger, and means that public mining (and the associated incredibly wasteful proof-of-work aspects) can also be discarded.

Even in this simplified case, several significant problems remain. We’re going to focus on just one of these - the problem of every participant in the network being sure that if they execute a smart contract, that it will produce the same effects on the ledger (assuming all participants start from the same ledger state).

Put another way, for a robust smart contract framework, we need to ensure that any contract written in the framework will execute deterministically and will terminate. This is a restatement of a problem that has been well studied in theoretical computer science for almost as long as the discipline has existed.

As every CS undergraduate knows, the Turing machine is the usual theoretical basis for modeling computer program execution. The normal approach to the theory is to show that a correspondence exists between a specific Turing machine and an equivalent program running on a physically realized digital computer.

Programming languages can thus be categorized into Turing complete languages, which can simulate all possible Turing machines (with the standard assumption that memory can be treated as infinite) and everything else. Non-turing complete languages are obviously not as powerful as Turing complete languages, and so are of considerably less interest to computer scientists.

This categorisation is compelling and useful, although it immediately exposes one of the fundamental problems of computer science - the Halting Problem. Loosely, this is a proof, originally due to Alan Turing, that it is not possible to construct a general algorithm to determine whether a Turing machine will terminate or run forever, given an initial state.

This presents, at first sight, a serious barrier to the concept of deterministic execution - how are we to be sure that all runs of a program will yield the same result when even something as basic as the halting behaviour cannot be established in general? Fortunately there are various techniques that we can employ to sidestep the halting problem and its consequences.

Firstly, we should note that the definition of a Turing machine specifically refers to an infinite storage tape (which is modeled as infinite memory in the simple equivalence proofs). Real digital computers are, of course, finite in extent. This should give us some hope that we could evade the halting problem by restricting program size or computation somehow. A further clue comes from functional programming.

If we consider a program as being represented by a single transformation of finite state from X to Y (the state could, for example, be considered to be the state of a finite Turing machine’s storage tape), then we can represent this as:

f: X -> Y

Now if we consider the space of all possible programs (which we take to be finite), and we add in a special state to the target space for the case where the program does not terminate within some time limit, then we can build a finite (but very large) map.

This map represents all possible program executions. Its keys are pairs of (start_state, program_code) and the values are the terminal states that are obtained by applying the program to the start_state. This is the functional programming technique known as memoization, as in a language with no side effects, we can just replace the action of applying a function with a precomputed result. This also shows that for finite state spaces and finite programs, halting can be evaded.

Not only that, but this detour into functional thinking also suggests a useful formal definition for deterministic execution:

Deterministic execution means that given a state X and a function f, then any application of f to X will produce the same state Y in finite time, regardless of who applies the function (assuming conformant semantics of the execution platform)

Note that for deterministic execution to be useful, we will also need some programmatic method to determine whether a given function is deterministic, without executing the code.

With the basic theory established, we now turn to a practical example in distributed ledgers - the deterministic classloader from the Corda project (recently donated to the Hyperledger project). This provides a JVM framework for writing deterministic smart contracts that operate on the state of a distributed, cryptographically signed ledger.

The code can be found in the experimental section of the Corda repository on Github . Participation, discussion and pull requests are all very welcome.

At first sight, the JVM could seem like a potentially strange choice for a deterministic execution platform. Many aspects of the JVM are highly dynamic - for example the inherent multithreading of all Java programs, non-deterministic garbage collection, race conditions in the JIT compilation leading to different sets of compiled methods on different runs, etc.

However, the JVM has a number of advantages:

  • JVM bytecode semantics is very well understood and tractable
  • The Java security model has been examined and attacked in detail, and is robust
  • The tooling space for JVM bytecode is very mature
  • Classloading provides a convenient platform and opportunity for analysing code for determinism

The approach taken by the Corda sandbox is to use both classloading and runtime components to achieve the following:

  • Reject any obviously non deterministic programs
  • Insert resource tracking code into the candidate program at class loading time
  • Provide a simple system for killing any program (and rolling back any transactions) that attempts to violate resource limits

The WhitelistClassLoader is a class loader that performs the class loading pieces of the deterministic framework. For example, it will reject any code that directly or indirectly creates new threads, as all multithreaded programs are essentially non-deterministic.

The classloader contains a whitelist (hence the name) that holds a list of methods that are known to be safe such as Object::getClass() which are allowed to be called (even if they would otherwise be ruled out, such as if they contain native code).

The whitelisting loader also injects runtime tracking code into classes as it loads them, to allow the runtime system to detect classes that may be too resource intensive.

The classloading system is also aware of which methods in the base JRE libraries are deterministic, and these methods can be freely called by user code. With these components, it is plausible to construct a system for deterministic execution of smart contract code.

Users of the class loader call the loadClass() method in the usual way when loading a class. This method attempts to locate the class in a cache, and if not found allows the parent classloader to attempt to load it. If both of those fail, the classloader delegates to findClass().

NOTE

This is just following the standard pattern of Java classloading. Custom classloaders typically override the findClass() method to implement their custom loading functionality.

This means that the real meat of custom classloading takes place within findClass(). In the case of the whitelisting classloader, the core of this method is a scan to see whether the class is deterministic. The method uses ASM to handle the class reading and a visitor pattern to examine the class. The scanning code (slightly simplified) looks like this:

public boolean scan() throws IOException {
  try (final InputStream in = Files.newInputStream(
               classDir.resolve(classInternalName + ".class"))) {
    try {
      // Create an ASM class reader from the stream
      final ClassReader classReader = new ClassReader(in);

      // Make a class visitor to analyse the class and
      // ensure determinism
      // We use a CandidacyStatus object to keep track of methods
      // we encounter when scanning the class, and to mark them
      // as deterministic or not.
      ClassVisitor whitelistCheckingClassVisitor
        = new WhitelistCheckingClassVisitor(classInternalName, 
                                            candidacyStatus);

      // Use ASM's reader / visitor architecture
      // to visit the class we're trying to load
      classReader.accept(whitelistCheckingClassVisitor, 
                         ClassReader.SKIP_DEBUG);
    } catch (Exception ex) {
      // ... Exception handling omitted
    }
  }

  return candidacyStatus.isLoadable();
}

 The key to the classloading process is the class visitor. This is responsible for imposing certain constraints on the code.

For example, the strictfp modifier is a little-known and rarely-used corner of the Java language, and it enforces strict adherence to the IEEE 754 floating-point standard. As a rule, very few classes set this, but without the strictfp keyword, the JVM will typically compute floating point maths in hardware, with a precision that will depend upon whatever hardware is available.

On modern CPUs, the JVM will often give much more precise results than IEEE 754 requires, but of course it means that different implementations could produce different results depending on the hardware. This is a potential source of non-determinism, so must be addressed.

The deterministic classloader could simply reject any program that does not include strictfp as a specifier, but as so few programmers use it, this would just be frustrating. Instead, the whitelisting classloader simply silently switches on strictfp for all classes as they are loaded, guaranteeing consistent behavior.

The class visitor implementation takes care of strictfp and various other determinism corner cases (such as disallowing any class with finalizers), before turning to the main part of the analysis. This is to visit each method in turn, using a WhitelistCheckingMethodVisitor per method.

Throughout the scan, the classloader makes use of a type called CandidacyStatus that represents what is known about the deterministic status of a particular set of methods (usually the methods of a single class, along with its dependencies). The method set is considered a "candidate" for being loadable within a deterministic context, hence the name.

The primary job of the WhitelistCheckingMethodVisitor is to build a call graph of which methods are called from a method in the candidate class. The basic rule is that if a candidate method calls only deterministic methods, then it is going to be deterministic, and the call graph we build will help us to decide whether the overall class is deterministic, once we’ve scanned the entire class.

In code, this is done relatively simply by overriding the visitMethodInsn() method in the ASM Visitor API.

 

public void visitMethodInsn(int opcode, String owner, String name, 
                            String desc, boolean itf) {

  CandidateMethod candidateMethod = 
              candidacyStatus.getCandidateMethod(currentMethodName);
  String internalName = owner + "." + name + ":" + desc;
  if (candidacyStatus.putIfAbsent(internalName)) {
    candidacyStatus.addToBacklog(internalName);
  }
  CandidateMethod referencedCandidateMethod = 
              candidacyStatus.getCandidateMethod(internalName);
  candidateMethod.addReferencedCandidateMethod(referencedCandidateMethod);
      // ...
}

The method visitor also has some corner cases and housekeeping to take care of as well. For example, the runtime uses the ThreadDeath error to kill any thread that exceeds runtime processing limits. Code which attempts to catch ThreadDeath could therefore try to circumvent deterministic checking.

The simplest solution is for the method visitor to simply disallow any class that catches ThreadDeath or its superclasses (Error or Throwable). The code that implements this should be called whenever a try-catch block is visited:

public void visitTryCatchBlock(Label start, Label end, 
                               Label handler, String type) {
  if (type == null)
    throw new IllegalArgumentException("Exception type must " + 
            "not be null in try/catch block in " + currentMethodName);

    // Forcible disallow attempts to catch ThreadDeath or any 
    //  throwable superclass - preserve determinism
    if (type.equals(Utils.THREAD_DEATH) || type.equals(Utils.ERROR)
                    || type.equals(Utils.THROWABLE)) {
      CandidateMethod candidateMethod = 
             candidacyStatus.getCandidateMethod(currentMethodName);
      candidateMethod.disallowed("Method " + currentMethodName + 
             " attempts to catch ThreadDeath, Error or Throwable");
    }
  }
}

With the call graph of a single method determined, then a simple analysis shows that if a method:

  • is not explicitly non-deterministic
  • only calls deterministic methods

then the method is deterministic.

With the scan of a single method complete, control returns to the class visitor. If all methods have been scanned, it checks to see if all methods in the class have been marked as deterministic. If so, the class is marked as loadable and is then instrumented with runtime resource checks before being loaded.

The whitelisting framework is very new, but early testing is encouraging, and it seems to offer an approach to deterministic execution that is not only suitable for newcomers, but also a sound basis for building production systems that require solid guarantees of determinism.

About the Author

Ben Evans is co-founder of jClarity, a startup which delivers performance tools & services to help development & ops teams. He is an organizer for the LJC (London's JUG) and a member of the JCP Executive Committee, helping define standards for the Java ecosystem. He is a Java Champion; 3-time JavaOne Rockstar Speaker; co-author of "The Well-Grounded Java Developer" & the new edition of "Java in a Nutshell" and a regular speaker on the Java platform, performance, concurrency, and related topics. Ben is available for speaking, teaching, writing and consultancy engagements - please contact for details.

Rate this Article

Adoption
Style

BT