A Brief Note on Provable Security in Cryptocurrencies

This post tries to give a short overview of provable security in cryptocurrencies.

For example, the paper "New Directions in Cryptography" by Whitfield Diffie and Martin Hellman, which is considered by most the beginning of modern cryptography (at least the public and civilian one), does not provide such rigorous analysis.

The publications from the cryptographic research community of today illustrate a startling difference from that era. In almost every relevant conference or journal, it is required from the authors a security analysis. With special care when the work proposes a new cryptographic scheme or claim improvements. Today, a new scheme or protocol without a proof of security in its original publication will hardly be accepted.

In the context of cryptocurrencies such evolution can be observed too. However, before going to that topic, it is convenient to review briefly what we mean by "adversary power and capabilities" mentioned earlier.

A more systematic, and therefore more preferable, approach is to design a formal model of the adversary capabilities. The goal of such a design is to construct a model attack as inclusive as possible. That is, a model which would capture as much concrete attacks as possible. Thereby giving us, in fact, a class of attacks.

The construction of such a model is not the end. What we actually want is to show (and prove) an upper bound in the probability of success of the adversary in that class of attacks. Needless to say, that the proof should show that such bound is small (more theoretical people should argue about what "small" means, but let skip this discussion in this post).

The way of computing such a bound is in fact what has been developed for the past decades for numerous cryptographic schemes and it involves computation assumptions, primitive models information theory and etc (and it is better drop it here, because it deserves a post on its own right). Needless to say that in this process some degree of generalization and simplification takes place. In the end the result is often called "the model."

The model is what ultimately is going to be analyzed not the system. Therefore, the construction of the model and the assurance that it is reasonable, i.e., is based as close as possible on reality, is of prime importance in provable security.

As an example, in the case of the public-key encryption schemes, one classic attack model is named CPA, which stands for Chosen-Plaintext Attack. This class of attacks embraces all the attacks that the adversary can obtain, somehow, ciphertexts from any plaintexts of its (finite) choices. By the end of that interaction, the adversary is assumed to output some value under a certain probability. For example, the correct secret-key or a valid ciphertext.

The reader should keep in mind that CPA is only one class. Other models can be devised and indeed have been proposed already, i.e., when the adversary has access to encrypted texts (instead of the plaintexts) given its choice of plaintext, as happens in the CCA (Chosen-Ciphertext Attack) a more powerful class of attacks. And there are several others.

The comparison between protocols and primitives brings us a couple of differences, which should be taken into account. For example, a protocol requires the participants to exchange messages over the network, hence it is necessary to take a closer look on how the adversary behaves in the presence of these messages. The adversary can see the contents of the message? Can it block them for some time or indefinitely? All these particular cases translate into different constrained scenarios which ultimately gives us different capabilities of the protocol.

Good examples of these research variants are The Bitcoin Backbone Protocol: Analysis and Applications and Analysis of the Blockchain Protocol in Asynchronous Networks. They respectively study proof-of-work in the synchronous (the messages cannot be blocked) and asynchronous (can be blocked for some time) settings. A more recent work is about the formalization of the proof-of-stake based protocol A Provably Secure Proof-of-Stake Blockchain Protocol in synchronous.

For further reading on models and provable security, we refer the reader to a few more papers with a heavy load of cryptography theory.

Random Oracles in Constantinople: Pratical Asynchronous Byzantine Agreement Using Cryptography

Zero Knowledge in the Random Oracle model, Revisited