Op Ed: A Cryptographic Design Perspective of Blockchains: From Bitcoin to Ouroboros

How does one design a blockchain protocol? Back in 2013, while in Athens, I set out to design a non-proof-of-work-based blockchain protocol motivated by the debt crisis in Greece, looming bank liquidity problems and the increasing discussions about the possibility of having a parallel currency. The new protocol had to be based on proof of stake to make sure that it can run even on cellphones and be secure independent of any computational power existing that is external to it.

Very soon it became clear that the problem was going to need much more than a few months’ work. Fast-forward three years to 2016: I was at the University of Edinburgh and had joined forces with IOHK whose CEO, Charles Hoskinson, was poised to solve the same problem. The protocol, “Ouroboros” as it would be eventually named, was there but the core of the security proof was still elusive when my good friend Alexander Russell visited me.

Together, we tackled the problem of proving the security of the system. Whiteboards were filled over and over again until we felt we mined a true gem: a clean combinatorial argument that enabled us to argue mathematically the security of the scheme. 

Diving Into the Mindset of a Cryptographer

Security is an elusive concept. Take a system that is able to withstand a given set of adverse operational conditions. When can we call it secure? What if it collapses in the next moment when it is subjected to a slightly different set of conditions? Or when it is given inputs different from any that have been tried before?

Security cannot be demonstrated via experiment alone since attacker ingenuity can rarely be completely enumerated within any reasonable timeframe. Cryptographic design, thus, has to somehow scale this “universal quantifier”: the system should be called secure only if it withstands all possible attacks.

In response to this fundamental problem, “provable security” emerged as a rigorous discipline within cryptography that promotes the co-development of algorithms and (so-called) proofs of security. Such proofs come in the form of theorems that, under certain assumptions and threat models that describe what the attacker can and cannot do, establish the security of cryptographic algorithms. In this fashion, modern cryptographic design pushes the “burden of proof” to the proposer of an algorithm.

In the world of academic cryptography, gone are the days when someone could propose a protocol or algorithm and proclaim it secure because it was able to withstand a handful of known attacks. Instead, modern cryptographic design requires due diligence by the designers to ensure that no attack exists within a convincing and well-defined threat model.

This approach has been a tremendously powerful and inspiring paradigm within cryptography. For instance, the notion of a secure channel has been studied for more than 40 years. This is the fundamental cryptographic primitive that allows the proverbial Alice and Bob to send messages to each other safely in the presence (and possibly active interference) of an attacker. Today’s provable security analysis, even using automated tools, has unearthed attacks against secure channel protocols like TLS that were unanticipated by the security community.

Back in 2009 though, the blockchain was a concept that was presented outside regular academic cryptographic discourse. A brief white paper and a software implementation were sufficient to fuel its initial adoption that expanded rapidly. In retrospect, this was perhaps the only way for this fringe idea to ripple the waters of scientific discourse sufficiently and force a paradigm shift (in the sense of Thomas S. Kuhn’s “Structure of Scientific Revolutions”) in terms of how the consensus problem was to be studied henceforth.

As the shift settled though, a principled approach became direly needed. The newly discovered design space appears to be vast and the avenues of exploring it too numerous. The “burden of proof” needs to return to the designer.

Blockchain protocols need to become systematized, as they have gradually become one of the dominant themes in distributed consensus literature. The blockchain is not the problem; it is the solution. But in this case, one may wonder, what was the problem?

In 2014, jointly with Juan Garay and Nikos Leonardos, we put forth a first description of “the problem” in the form of what we called a “robust transaction ledger.” Such a ledger is implemented by a number of unauthenticated nodes and provides two properties, called persistence and liveness. Persistence mandates that nodes never disagree about the placement of transactions once they become stable, while liveness requires that all (honestly generated) transactions eventually become stable. Using this model, we provided a proof of security for the core of the Bitcoin protocol (a suitably simplified version of the protocol that we nicknamed the “bitcoin backbone”).

Given this proof, a natural question a cryptographer will ask is whether this protocol is really the best possible solution to the problem. “Best” here is typically interpreted in two ways: first, in terms of the efficiency of the solution; and second, in terms of the relevance and applicability of the threat model and the assumptions used in the security proof.

Efficiency is a particular concern for the Bitcoin blockchain. With all its virtues, the protocol is not particularly efficient in terms of processing time or resource consumption. This is exactly where “proof of stake” emerged as a possible alternative and a more efficient primitive for building blockchain protocols.

So, is it possible to use proof of stake to provably implement a robust transaction ledger? By 2016, with our Bitcoin backbone work already presented, this was a well-defined question; and the answer came with Ouroboros: our proof-of-stake-based blockchain protocol.

Ouroboros

The unique characteristic of Ouroboros is that the protocol was developed in tandem with a proof of security that aims to communicate in a succinct way that the proposed blockchain protocol satisfies the properties of a robust transaction ledger. Central to the proof is a combinatorial analysis of a class of strings that admit a certain discrete structure that maps to a blockchain fork. We called “forkable” those strings that admit a non-trivial such structure, and our proof shows that their density becomes minutely small as the length of the string grows.

With this argument, we showed how there is an opportunity for the nodes running the protocol to converge to a unique history. The protocol then dictates how to take advantage of this opportunity by running a cryptographic protocol that enables the nodes to produce a random seed, which, in turn, is used to sample the next sequence of parties to become active. As a result, the protocol facilitates the next convergence step to take place; in this way, it can continue ad infinitum following a cyclical process that was also the inspiration for its name. Ouroboros is the Greek word for the snake that eats its tail, an ancient Greek symbol for re-creation.

Having the protocol and its proof in hand gave us the unique opportunity for peer review, i.e., asking fellow cryptographers to evaluate the construction and its associated security proof as part of the formal submission process to a major cryptology conference.

Peer reviewing at the top cryptology venues is a painstakingly rigorous process that goes on for months. Papers are first reviewed independently by at least three experts, and afterward a discussion for each paper rages on as the three reviewers, as well as other members of the scientific committee, get involved and try to converge on the intellectual merits of each submission.

As a result of successfully passing this rigorous peer review process, Ouroboros was accepted and included in the program of Crypto 2017, the 37th annual cryptology conference. Crypto is one of the flagship conferences of the International Association for Cryptologic Research (IACR) and is one of the most exciting places for a cryptographer to be, as the program always contains research on the cutting edge of the discipline.

Furthermore, Ouroboros will be the settlement layer of the Cardano blockchain to be rolled out by IOHK in 2017, making it one of the swiftest technology transfer cases from a basic research publication to a system to be used by many thousands in just one year.

While all this may seem like a happy conclusion to the quest for a proof-of-stake blockchain, we are far from being done. On the contrary, we are still, as a community, at the very beginning of this expedition that will delve deep into blockchain design space. There are still too many open questions to solve, and new systems will be built on the foundations of the research that our community is laying out today.

The views expressed in this op ed are those of its author, Aggelos Kiayias , and do not necessarily reflect those of Bitcoin Magazine or BTC Media.

Ouroboros image courtesy of Wikimedia Commons.