1

Introduction to Cryptography & Cryptocurrencies

Blockchain Technologies

Lecture # 01

Adopted from “Bitcoin and Cryptocurrency Technologies”, Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Steven Goldfeder

Introduction

• All currencies need some way to control supply and enforce various security properties to prevent cheating.
• Cryptocurrencies too must have security measures that prevent people from tampering with the state of the system
• But unlike fiat currencies, the security rules of cryptocurrencies need to be enforced purely technologically and without relying on a central authority

Cryptography

• 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 the rules for creation of new units of the currency into a mathematical protocol.

Cryptographic Hash Functions

• A hash functionis a mathematical function with the following three properties:
• Its input can be any string of any size.
• It produces a fixed size 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).

Properties of hash functions

• For a hash function to be cryptographically secure, we’re going to require that it has the following three additional properties:
• (1) collision‐resistance,
• (2) hiding,
• (3) puzzle‐friendliness

1. Collision‐resistance

• A collision occurs when two distinct inputs produce the same output.
• A hash function H is collision‐resistant if nobody can find a collision
• A hash function H is said to be collision resistant if it is infeasible to find two values, x and y, such that x ≠ y, yet H(x)=H(y).

Collision resistnce

• Notice that we said nobody can find a collision, but we did not say that no collisions exist
• This collision‐detection algorithm works for every hash function.
• But, of course, the problem with it is that this takes a very, very long time to do
• There are no hash functions proven to be collision‐resistant

• The cryptographic hash functions that we rely on in practice are just functions for which people have tried really, really hard to find collisions and haven’t yet succeeded.
• In some cases, such as the old MD5 hash function, collisions were eventually found after years of work, leading the function to be deprecated and phased out of practical use.
• And so we choose to believe that those are collision resistant

Message digest

• Consider SecureBox, an authenticated online file storage system that allows users to upload files and ensure their integrity when they download them
• Alice just needs to remember the hash of the original file. When she later downloads the file from SecureBox, she computes the hash of the downloaded file and compares it to the one she stored.
• If the hashes are the same, then she can conclude that the file is indeed the one she uploaded, but if they are different, then Alice can conclude that the file has been tampered with

2. Hiding

• The hiding property asserts that if we’re given the output of the hash function y = H(x), there’s no feasible way to figure out what the input, x, was
• In order to be able to achieve the hiding property, it needs to be the case that there’s no value of x which is particularly likely.
• That is, x has to be chosen from a set that’s, in some sense, very spread out.
• If x is chosen from such a set, this method of trying a few values of x that are especially likely will not work

Commitments

• Now let’s look at an application of the hiding property.
• In particular, what we want to do is something called a commitment.
• A commitment is the digital analog of taking a value, sealing it in an envelope, and putting that envelope out on the table where everyone can see it
• When you do that, you’ve committed yourself to what’s inside the envelope.
• But you haven’t opened it, so even though you’ve committed to a value, the value remains a secret from everyone else.
• Later, you can open the envelope and reveal the value that you committed to earlier

Commitment scheme

• To use a commitment scheme, we first need to generate a random nonce.
• We then apply the commit function to this nonce together with msg, the value being committed to, and we publish the commitment com.
• This stage is analogous to putting the sealed envelope on the table.
• At a later point, if we want to reveal the value that they committed to earlier, we publish the random nonce that we used to create this commitment, and the message, msg.
• Now, anybody can verify that msg was indeed the message committed to earlier

3. Puzzle friendliness

• A hash function H is said to be puzzle‐friendly if for every possible n‐bit output value y, if k is chosen from a distribution with high min‐entropy, then it is infeasible to find x such that H(k ‖ x) = y in time significantly less than 2ⁿ .

Search puzzle

• In this application, we’re going to build a search puzzle, a mathematical problem which requires searching a very large space in order to find the solution.
• In particular, a search puzzle has no shortcuts.
• That is, there’s no way to find a valid solution other than searching that large space.

​

Search puzzle

• The intuition is this: if H has an n‐bit output, then it can take any of 2 n values. Solving the puzzle requires finding an input so that the output falls within the set Y, which is typically much smaller than the set of all outputs.
• The size of Y determines how hard the puzzle is.
• If Y is the set of all n‐bit strings the puzzle is trivial, whereas if Y has only 1 element the puzzle is maximally hard.
• We’re going to use this idea later when we talk about Bitcoin mining, which is a sort of computational puzzle

Merkle‐Damgard transform

• Say the compression function takes inputs of length m and produces an output of a smaller length n.
• The input to the hash function, which can be of any size, is divided into blocksof length m‐n.
• The construction works as follows: pass each block together with the output of the previous block into the compression function.

• Notice that input length will then be (m‐n) + n = m, which is the input length to the compression function.
• For the first block, to which there is no previous block output, we instead use an Initialization Vector (IV).
• This number is reused for every call to the hash function, and in practice you can just look it up in a standards document.
• The last block’s output is the result that you return.

• SHA‐256 uses the Merkle‐Damgard transform to turn a fixed‐length collision‐resistant compression function into a hash function that accepts arbitrary‐length inputs.
• The input is “padded” so that its length is a multiple of 512 bits.

Hash Pointers and Data Structures

• A hash pointer is a data structure that turns out to be useful in many of the systems that we will talk about.
• A hash pointer is simply a pointer to where some information is stored together with a cryptographic hash of the information.
• Whereas a regular pointer gives you a way to retrieve the information, a hash pointer also gives you a way to verify that the information hasn’t changed.

Blockchain

• Whereas as in a regular linked list where you have a series of blocks, each block has data as well as a pointer to the previous block in the list, in a block chain the previous block pointer will be replaced with a hash pointer.
• So each block not only tells us where the value of the previous block was, but it also contains a digest of that value that allows us to verify that the value hasn’t changed.
• We store the head of the list, which is just a regular hash‐pointer that points to the most recent data block.

• A use case for a block chain is a tamper‐evident log.
• That is, we want to build a log data structure that stores a bunch of data, and allows us to append data onto the end of the log.
• But if somebody alters data that is earlier in the log, we’re going to detect it
• Genesis block

Merkle Trees

• A binary tree with hash pointers is known as a Merkle tree, after its inventor Ralph Merkle.
• Suppose we have a number of blocks containing data.
• These blocks comprise the leaves of our tree.
• We group these data blocks into pairs of two, and then for each pair, we build a data structure that has two hash pointers, one to each of these blocks.
• These data structures make the next level up of the tree.
• We in turn group these into groups of two, and for each pair, create a new data structure that contains the hash of each.
• We continue doing this until we reach a single block, the root of the tree.

Proof of membership

• Another nice feature of Merkle trees is that, unlike the block chain that we built before, it allows a concise proof of membership.
• Say that someone wants to prove that a certain data block is a member of the Merkle Tree. As usual, we remember just the root.
• Then they need to show us this data block, and the blocks on the path from the data block to the root.
• We can ignore the rest of the tree, as the blocks on this path are enough to allow us to verify the hashes all the way up to the root of the tree

Digital Signatures

• A digital signature is supposed to be the digital analog to a handwritten signature on paper
• We desire two properties from digital signatures that correspond well to the handwritten signature analogy.
• Firstly, only you can make your signature, but anyone who sees it can verify that it’s valid.
• Secondly, we want the signature to be tied to a particular document so that the signature cannot be used to indicate your agreement or endorsement of a different document

Public key as identity

• The idea is to take a public key, one of those public verification keys from a digital signature scheme, and equate that to an identity of a person or an actor in a system.
• If you see a message with a signature that verifies correctly under a public key, pk, then you can think of this as pk is saying the message

Decentralized identity management

• Rather than having a central authority that you have to go to in order to register as a user in a system, you can register as a user all by yourself.
• You don’t need to be issued a username nor do you need to inform someone that you’re going to be using a particular name.
• If you want a new identity, you can just generate one at any time, and you can make as many as you want
• All of these things are possible with decentralized identity management, and this is the way Bitcoin, in fact, does identity. These identities are called addresses, in Bitcoin jargon