CHAPTER 2
Fundamentals

The goal of blockchain technology is to create a shared, decentralized digital ledger. In this system, no centralized authority exists to dictate what the official version of the digital ledger is.

Blockchain technology transfers trust in the digital ledger away from a centralized authority to a set of protocols designed to provide the same guarantees as a centralized ledger. These protocols are created using smaller building blocks with certain properties that can provide these desired guarantees.

This chapter explores the fundamentals of blockchain security. This includes the cryptographic primitives and the data structures that are used to build blockchain protocols and make the decentralized digital ledger possible.

Cryptographic Primitives

Financial institutions maintain an internal accounts ledger, enabling value to be transferred from one party to another by simply updating the relevant values in this ledger. Each financial institution is responsible for maintaining the accuracy of its ledger, and customers must trust the financial institution to properly track their financial transactions.

Blockchain is designed to transfer this trust from these centralized authorities to cryptographic algorithms and protocols. The cryptographic algorithms are relied upon to ensure the authenticity and integrity of the transactions recorded on the blockchain's ledger.

Blockchain technology began with Bitcoin, and since then, many different blockchains have emerged, each with its own tweaks on the underlying protocols and methods of implementing them. However, all of these protocols are reliant on the same set of cryptographic building blocks.

The design of the blockchain makes data integrity and authenticity protections vital for the system to work. To provide these protections, blockchain technology uses public key cryptography and hash functions.

Public Key Cryptography

Cryptographic algorithms are divided into two main categories based on how they use encryption keys. Symmetric algorithms use a single key for both encryption and decryption. This symmetry means that the algorithms are generally more efficient, making them better suited for bulk data transfer. However, they require the shared secret key to be distributed to all participants via a secure channel.

Asymmetric, or public key, cryptography uses a public key for encryption and a private key for decryption. This makes it possible to send a secret message to anyone without setting up a shared secret key. However, these algorithms are generally less efficient than their symmetric counterparts.

Blockchain technology is heavily dependent on public key cryptography. Its use of two related keys and the ability to create and validate digital signatures using them provides the invaluable ability to authenticate the sender of a message.

Introducing "Hard" Mathematical Problems

Public key cryptography is built using "hard" mathematical problems. These mathematical functions are defined by an asymmetric relationship between how hard they are to perform versus how hard they are to reverse. For these problems, F(x) has polynomial complexity, while F-1(x) has exponential complexity.

This relationship makes it possible to develop cryptographic algorithms that are both usable and secure. The algorithms are designed so that a legitimate user only has to perform the easy operation, F(x), while any attacker must solve the harder problem, F-1(x).

Several of these mathematically "hard" problems exist. The two most commonly used in "classical" (i.e., not post-quantum) cryptography are the factoring problem, which is the basis for RSA, and the discrete logarithm problem, which is the basis for the Digital Signature Algorithm (DSA). Algorithms based on these problems can also be implemented more efficiently using elliptic curve cryptography (ECC).

The Factoring Problem

In the factoring problem, the easier operation is multiplying two prime numbers. The complexity of doing so is polynomial in the length of the two numbers. This means that an increase in the length of the two primes, such as switching from 128 to 129 bits, has a relatively small impact on the overall complexity.

Factoring inverts multiplication, and factoring has exponential complexity in the length of the factors. The reason for this is that the best-known way to factor two numbers on a non-quantum computer has exponential complexity.

While one of the factors is guaranteed to be less than the square root of the quotient, this is a large space that grows rapidly. Adding a single bit to the length of the primes (i.e., from 128 to 129 bits) doubles the number of potential factors that an attacker needs to search.

The difficulty of factoring grows much faster than the difficulty of multiplying. As a result, it is possible to find a length of these factors where multiplication is possible but factoring is not.

The Discrete Logarithm Problem

The discrete logarithm problem is another asymmetric problem commonly used in public key cryptography. It is based on the "easy" problem of exponentiation and the "hard" problem of logarithms.

As with the factoring problem, the discrete logarithm problem is designed to ensure that legitimate operations are easy compared to malicious ones. Increasing the size of the exponent has a minimal impact on a legitimate user-but a significant impact on an attacker. As with the factoring problem, the best way to solve the discrete logarithm is by guessing possible values for the exponent, so a user can achieve an arbitrary level of security by increasing the key length.

Elliptic Curve Cryptography

Elliptic curve cryptography (ECC) is a type of public key cryptography that uses points on an elliptic curve instead of integers as the basis for computation. An elliptic curve is a mathematical function of the form y2 = x3 + ax + b.

Using points on these curves as public keys, it's possible to create a public key cryptosystem that uses the same principles as the discrete logarithm problem. On an elliptic curve, an operation called point addition is equivalent to multiplication over the integers, and point multiplication is equivalent to exponentiation.

In elliptic curve cryptography, public keys are derived from private keys by multiplying a random integer (the private key) with a publicly known point on the curve (the generator). As with the factoring and discrete logarithm problems, point addition and multiplication (the equivalents of multiplication and exponentiation) are "easy" for legitimate users, while point subtraction and division (the equivalents of factoring and logarithms) are "hard" for an attacker.

Elliptic curve cryptography has two main advantages over integer-based public key cryptography: key length and energy consumption. Elliptic curve cryptography accomplishes the same level of security as cryptosystems using the discrete logarithm problem with much shorter keys. For example, a 2048-bit RSA key has equivalent security to a 160-bit ECC curve. ECC is also better than algorithms like RSA in low-power environments because the operations used in ECC-based cryptography (point addition and multiplication) consume less power than the equivalent operations over the integers (multiplication and exponentiation).

Building Cryptography with "Hard" Problems

Public key cryptography uses these "hard" problems to build algorithms that are both usable and secure. The design of these algorithms is intended to allow a legitimate user to only perform "easy" operations, while attackers are forced to complete "hard" ones.

A critical part of this process is the derivation of the public/private keypair. While a private key is a random number, the public key is derived from it to have certain properties. The intent is for one key to undo what the other does for a particular algorithm.

For example, the RSA encryption operation is c = me (mod n), where c is the ciphertext, m is the message, e is the public key, and n is a public modulus value. Substituting some values in, 25 (mod 14) = 4.

RSA uses the same operation for decryption, so the private key is selected to undo the effects of encryption. A private key of 11 produces 411 (mod 14) = 2.

In the case of RSA, the public and private keys, e and d, are selected so that md*e = 1 (mod 14) for any message m, since this is equivalent to the two-stage process that we performed due to the properties of exponents. With a random private key of 11, d had to be 5, according to Euler's totient function.

Since the recipient of the message knows the private key, they can undo the encryption with an exponentiation operation. However, an attacker lacking knowledge of this key would need to calculate a logarithm, which is much harder.

How the Blockchain Uses Public Key Cryptography

Public key cryptographic algorithms can provide confidentiality, integrity, and authentication protections. They are a fundamental part of how the blockchain...