Breathing Life Into Old Math

by | Jan 29, 2019

If you’ve been studying the Casanova paper, you’ll notice that we built up Casanova in four steps. At each of these steps, we wrote an algorithm that gets progressively more powerful, efficient, and compliant with our standards of safety, liveness, finality, and compatibility with a general purpose blockchain.

The first two steps establish the DAG structure (as opposed to the standard chain structure) and emphasize how the algorithm primarily functions to attest or record transactions as validators see them. In the third step, we acknowledge that there will be conflicts we have to resolve, so the network attests to a conflict, uses a protocol on the side to form consensus, and then attests to the result.

In the fourth step, we embed that side protocol from step three natively into the attestation protocol, so all of the messages and voting go in block headers and consensus happens concurrently with attestation. It also includes some optimizations that forego consensus when the result can be determined beforehand.

The side algorithm we chose was a pre-blockchain consensus algorithm, one that defines a clear network model and has precise definitions and proofs of safety and liveness. Casanova’s proofs of safety and liveness follow along the same lines–in fact, if you read the proofs carefully you will see that Casanova’s proofs reduce the problem of safety and liveness to that of the corresponding side algorithm. So, we reduce and use the proofs that came with that side algorithm originally.

From the paper itself, it might not be straightforward to see, but the side algorithm from step three need not necessarily be the one we have in the paper. There is a whole wealth of pre-blockchain consensus protocols that meet the same standards of rigorous mathematics as the one we chose. So what’s going on here?

We recently wrote a follow-up paper to Casanova that gives a thorough treatment of what exactly went on, mathematically speaking, with Casanova. The punch line of this paper is that you can choose from an entire class of classical (pre-blockchain) consensus algorithms to stick into that side-protocol slot from step three and it will still work just fine—you’ll just have to make some changes to go from step three to step four as we did in the Casanova paper.

The great thing about this is that it gives us access to the theory of consensus that came before the blockchain, with all of its rigorous theory, solid proofs, and well-thought definitions. In other words, we inherit years of theory and progress in consensus that the blockchain world simply wasn’t taking advantage of previously.

The thing that makes this possible is that Casanova drastically speeds up these classical algorithms. The main reason that has kept those older algorithms from dominating blockchain consensus is that they require too many messages to be scalable. Yes, they have amazing proofs and theory grounding them; yes, they are safe and live and reliable. But, in practice, we simply could never hope to make a scalable blockchain if we use them out of the box.

Casanova provides a highly scalable framework that can use those older algorithms. We’re breathing blockchain-type life into these older algorithms by making them not only easily compatible with the blockchain but also scalable. The great advantage of this is that we can draw on the solid mathematical theory of pre-blockchain consensus systems, which took decades to build up. Using this work as the basis for modern blockchain systems provided a very powerful starting point for our work.