Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction by Arvind Narayanan

CHAPTER 1
Introduction to Cryptography and
Cryptocurrencies
All currencies need some way to control supply and enforce various
security properties to prevent cheating. In fiat currencies,
organizations like central banks control the money supply and add
anticounterfeiting features to physical currency. These security
features raise the bar for an attacker, but they don’t make money
impossible to counterfeit. Ultimately, law enforcement is necessary
for stopping people from breaking the rules of the system.
Cryptocurrencies too must have security measures that prevent
people from tampering with the state of the system and from
equivocating (that is, making mutually inconsistent statements to
different people). If Alice convinces Bob that she paid him a digital
coin, for example, she should not be able to convince Carol that she
paid her that same coin. But unlike fiat currencies, the security rules
of cryptocurrencies need to be enforced purely technologically and
without relying on a central authority.
As the word suggests, cryptocurrencies make heavy use of
cryptography. Cryptography provides a mechanism for securely
encoding the rules of a cryptocurrency system in the system itself.
We can use it to prevent tampering and equivocation, as well as to
encode, in a mathematical protocol, the rules for creation of new
units of the currency. Thus, before we can properly understand
cryptocurrencies, we need to delve into the cryptographic
foundations that they rely on.
Cryptography is a deep academic research field using many
advanced mathematical techniques that are notoriously subtle and
complicated. Fortunately, Bitcoin relies on only a handful of
relatively simple and well-known cryptographic constructions. In this
chapter, we specifically study cryptographic hashes and digital
signatures, two primitives that prove to be useful for building
cryptocurrencies. Later chapters introduce more complicated
cryptographic schemes, such as zero-knowledge proofs, that are used
in proposed extensions and modifications to Bitcoin.
Once the necessary cryptographic primitives have been
introduced, we’ll discuss some of the ways in which they are used to
build cryptocurrencies. We’ll complete this chapter with examples of
simple cryptocurrencies that illustrate some of the design challenges
that need to be dealt with.
1.1. CRYPTOGRAPHIC HASH FUNCTIONS
The first cryptographic primitive that we need to understand is a
cryptographic hash function. A hash function is a mathematical
function with the following three properties:
•  Its input can be any string of any size.
•  It produces a fixed-sized output. For the purpose of making
the discussion in this chapter concrete, we will assume a 256-
bit output size. However, our discussion holds true for any
output size, as long as it is sufficiently large.
•  It is efficiently computable. Intuitively this means that for a
given input string, you can figure out what the output of the
hash function is in a reasonable amount of time. More
technically, computing the hash of an n-bit string should have
a running time that is O(n).
These properties define a general hash function, one that could be
used to build a data structure, such as a hash table. We’re going to
focus exclusively on cryptographic hash functions. For a hash function
to be cryptographically secure, we require that it has the following
three additional properties: (1) collision resistance, (2) hiding, and
(3) puzzle friendliness.

Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction by Arvind Narayanan