Cryptoprimitives and beyond

The nodes in cryptoeconomic systems communicate with each other using special sets of rules called cryptographic protocols. Cryptographic techniques use various math tricks to achieve communication security in the presence of adversary. In the next longread, we will talk about how security of such cryptographic techniques is proved, that is, how their invulnerability to adversary is assessed. You will see that in practice security is proved, to put it mildly, not easy. That is why atomic elements, invulnerability of which is more or less clear, are of particular importance. Such atomic elements make up a kind of cryptographic Lego. By combining elements with each other, you can build more complex structures — in fact, cryptographic protocols. And the atomic details of the Lego are called cryptoprimitives. There is no generally accepted list of "official" cryptoprimitives. In this longread, we will talk about several components that are widely used in cryptoeconomic systems.

One-way functions were known long ago prior to the first mentioning in Wilkes (1968), which, in turn, referred to Needham. Robert Needham, researcher from Cambridge, proposed to use such functions to protect user passwords in computer networks (apparently, the paper based on the idea was published much later). The idea was simple — I briefly described it in the opening longread: input string of some arbitrary (even very large) length is mapped in some unique way to much shorter output string with fixed length.

One-way functions are usually doing several jobs in cryptoeconomic systems. First, a subset of one-way functions — hash functions — can be used to obtain succinct cryptographic digest of the data, which then could be verified by third party. Second, one-way functions could be used in asymmetric cryptography (it will be discussed later). And third, one-way functions help to digitally sign data by users.

Whitfield Diffie and Martin Hellman were the first to recognize potential of one-way functions for cryptographic protocols seeing it as one of components of a digital signature scheme. Following Diffie & Hellmann (1976), Rabin (1978) and Rabin (1979) developed cryptosystem with effective 64-bit hash-function based on DES cipher. Yuval (1979) pointed on vulnerability (hash collision attack) in Rabin's scheme; using birthday paradox (see, for example, Girault et al. (1988) for the explanation of birthday paradox in cryptosystem context) he showed that a collision for n-bit hash function could be found in 2n/2 time. Merkle (1979) proposed collision resistance and preimage resistance properties of hash-function.

Later these ideas were further developed in Damgård (1987) and Merkle (1989), and become known as Merkle–Damgård construction. Naor & Yung (1995) introduced Universal One-Way Hash Functions (UOWHFs), which was second-preimage-resistant. Almost any significant name in cryptography of the late 20th-the early 21st century — Rogaway, Bellare, Fiat, Shamir, and many others — contributed to hash-functions.

It was developed by Ralph Merkle in 1979 and patented in 1979 and 1987. Initially it was designed to enhance Lamport one-time signature scheme (which, in turn, was designed to work with one-way functions), by allowing it to use one key to sign several messages. The idea is straightforward: in binary tree data is structured into some arbitrary blocks, each part gets its own hash, then on higher level hashes are joined in pairs and hashed again, and so forth. In general case Merkle tree could have more than two hashes on each node. It is widely used in torrents, version control systems, and, of course, blockchains. Several properties make it ideal choice for distributed storage of collectively maintained data with verifiable immutability in untrusted environment:

There is a good introduction to Merkle trees in Bitcoin and Ethereum in this post by Vitalik Buterin. Version of Merkle tree, which is used in Bitcoin, is described in Haber & Stornetta (1991) and Haber & Stornetta (1997). History of their contribution is described here — we will discuss it in more details later.

But Merkle trees are used not only in public blockchains. Examples of Merkle trees in enterprise blockchains are Corda platform and here, and Hyperledger.

Strictly speaking, linked timestamping is rarely seen on a typical list of cryptoprimitives. But this idea, like the idea of secure meaningful names, is related to hash-functions and is important for understanding how blockchains work. In the 90s of the 20th century, Stuart Haber, Scott Stornetta and Dave Bayer, as well as (independently) Josh Benaloh and Michael de Mare wrote a number of articles on this subject. The developer or developers of the Bitcoin blockchain have read these works (they are quoted by Satoshi Nakamoto). Now, the ideas similar to those presented in the articles of these authors are ubiquitous across various blockchains.

Symmetric encryption has been known to humankind from ancient times. The key idea is natural: there is a key to "lock" some data, and this key is used to "unlock" data as well. Symmetric encryption algorithms often supported by blockchain platforms are 3DES, AES, and Blowfish.

Asymmetric encryption, or public-key cryptography (which is the same), use two keys: one — to encrypt, and other (which is internally linked to the first one) — to decrypt. It was proposed in Diffie & Hellman (1976) mentioned earlier. Diffie–Hellman key exchange scheme was major advance in cryptography, which greatly influenced the field. Simple explanation of how public-key cryptography works, and what is the difference between symmetric and asymmetric encryption, could be found here. More advanced information is set out here. Probably one of the most widespread asymmetric cryptography system nowadays is RSA. But Bitcoin and Ethereum use other protocol — ECDSA. Digital signatures are often mentioned in the context of asymmetric cryptography, but in fact it is somewhat different idea. Here you may read several usages of digital signatures in blockchains.

Elliptic curve cryptography is widely used in blockchains, so here is a couple of videos to understand the idea behind it.

Elliptic curves is fascinating and quite complex idea, so here are several links to videos and texts of varying complexity for better understanding of the idea:

Blind signature is another important idea from cryptogtaphy, developed especially for digital cash schemes. Here are the couple of videos, explaining basic idea.

Let's talk about different types of products — exclusive/non-exclusive, competitive/non-competitive. Difficulties arise because information is a non-exclusive and non-competitive product. Zero-knowledge proof helps to solve part of the problem. But how to prove it without presenting it?

The idea of zero-knowledge proof was introduced by Goldwasser, Micali and Rackoff in Goldwasser et al. (1982). The concept had huge impact on cryptography foundations, far behind original context, for which it was developed; for example, Goldreich, et al. (1991), among other things, shows that zero-knowledge proof could be used to cope with malicious parties to achieve Byzantine fault tolerance; it also coerced certain momentum to fields like interactive proof systems and multi-prover proof systems.

In the next long read we will elaborate more on the topic of cryptoanalysis; for now, let's state, that in cryptography there is no such thing as 100% guaranteed security; instead, modern cryptography is concentrating on efficiency of protocols, for which violating security is unfeasible under certain assumptions about computation power of an adversary and user. Usually, both an adversary and a user are believed to "be polynomial", i.e. to possess computational power capable of making calculations in polynomial time. Having said this, let's define:

So, as you might see, game-theoretic approach is ubiquitous in cryptoeconomic systems: not only it is at the core of mechanism design, it is also applicable to cryptography and security sphere. Very basic introduction to zero-knowledge proofs is in Quisquater & Joullou (1998). Video introduction could be found here. There is even informal Halloween-style description. Lots of links to more serious must-reads are on Ethereum research site.

Zero-knowledge proof is a class of protocols; it is not "automatically" present for all tasks and contexts, instead, it should be created and proved on ad hoc basis. So, there are zk-snarks for scaling of Ethereum. Basic Block is also about it (rus). There are also several podcasts:

The topic of cryptography is inexhaustible; those in the need of additional knowledge are welcomed to this awesome cryptography site.