This document provides an introduction to block chain technologies. It discusses cryptographic hash functions, their properties including collision resistance, hiding, and puzzle friendliness. It describes applications such as message digests, commitments, and search puzzles. The document also discusses hash pointers and data structures such as linked lists using hash pointers instead of regular pointers. Cryptographic hash functions like SHA-256 are explained along with how they are used in block chains.
This document provides an introduction to block chain technologies. It discusses cryptographic hash functions, their properties including collision resistance, hiding, and puzzle friendliness. It describes applications such as message digests, commitments, and search puzzles. The document also discusses hash pointers and data structures such as linked lists using hash pointers instead of regular pointers. Cryptographic hash functions like SHA-256 are explained along with how they are used in block chains.
This document provides an introduction to block chain technologies. It discusses cryptographic hash functions, their properties including collision resistance, hiding, and puzzle friendliness. It describes applications such as message digests, commitments, and search puzzles. The document also discusses hash pointers and data structures such as linked lists using hash pointers instead of regular pointers. Cryptographic hash functions like SHA-256 are explained along with how they are used in block chains.
This document provides an introduction to block chain technologies. It discusses cryptographic hash functions, their properties including collision resistance, hiding, and puzzle friendliness. It describes applications such as message digests, commitments, and search puzzles. The document also discusses hash pointers and data structures such as linked lists using hash pointers instead of regular pointers. Cryptographic hash functions like SHA-256 are explained along with how they are used in block chains.
Unit 2- Introduction to Cryptography and Cryptocurrencies
Dr.Ramya R S Department of Computer Science and Engineering Dayananda Sagar College of Engineering VTU October 2021
Dr.Ramya R S Block Chain Technologies 1 / 31
Table of Contents
Introduction Cryptographic Hash Functions Hash Pointers and Data Structures Digital Signatures Public Keys as Identifies A simple Cryptocurrency
Dr.Ramya R S Block Chain Technologies 2 / 31
Introduction
Cryptocurrencies too must have security measures that prevent people
from tampering with the state of the system. 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.
Dr.Ramya R S Block Chain Technologies 3 / 31
Cryptographic Hash Functions
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 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. 3 additional properties: (1) collision-resistance, (2) hiding, (3) puzzle-friendliness.
Dr.Ramya R S Block Chain Technologies 4 / 31
Property 1: Collision-resistance
The first property that we need from a cryptographic hash function is
that it’s collision-resistant. A collision occurs when two distinct inputs produce the same output. A hash function H(.) is collision-resistant if nobody can find a collision. Collision-resistance: 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).
Dr.Ramya R S Block Chain Technologies 5 / 31
Collision Resistance Nobody can find collision, but collision exists. The input space to the hash function contains all strings of all lengths, yet the output space contains only strings of a specific fixed length. To find Collission: Consider the following simple method for finding a collision for a hash function with a 256-bit output size: pick 2 256 + 1 distinct values, compute the hashes of each of them, and check if there are any two outputs are equal. Since we picked more inputs than possible outputs, some pair of them must collide when you apply the hash function.
Dr.Ramya R S Block Chain Technologies 6 / 31
Collision Resistance
If we pick random inputs and compute the hash values, we’ll find a collision with high probability long before examining. In fact, if we randomly choose just inputs, it turns out there’s a 99.8 percent chance that at least two of them are going to collide. The fact that we can find a collision by only examining roughly the square root of the number of possible outputs results from a phenomenon in probability known as the birthday paradox
Dr.Ramya R S Block Chain Technologies 7 / 31
Application: Message Digests
Consider SecureBox, an authenticated online file storage system that
allows users to upload files and ensure their integrity when they download them. Suppose that Alice uploads really large file, and wants to be able to verify later that the file she downloads is the same as the one she uploads. One way to do that would be to save the whole big file locally, and directly compare it to the file she downloads. While this works, it largely defeats the purpose of uploading it in the first place; If Alice needs to have access to a local copy of the file to ensure its integrity, she can just use the local copy directly
Dr.Ramya R S Block Chain Technologies 8 / 31
Message Digests Contd.. 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. Remembering the hash thus allows her to detect accidental corruption of the file during transmission or on SecureBox’s servers, but also intentional modification of the file by the server. The hash serves as a fixed length digest. This gives us a very efficient way to remember things we’ve seen before and recognize them again. Whereas the entire file might have been gigabytes long, the hash is of fixed length, 256-bits for the hash function in our example. This greatly reduces our storage requirement. Dr.Ramya R S Block Chain Technologies 9 / 31 Property 2: Hiding The second property that we want from our hash functions is that it’s 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. Example: When we flip a coin, result of the coin flip is heads or tails. We then ask someone, an adversary, who didn’t see the coin flip. The adversary was able to guess what the string was because there were only two possible values. A hash function H is hiding if: when a secret value r is chosen from a probability distribution that has high min-entropy, then given H(r x) it is infeasible to find x. Min-entropyis a measure of how predictable an outcome is, and high min-entropy captures the intuitive idea that the distribution is very spread out. What that means specifically is that when we sample from the Dr.Ramya R S Block Chain Technologies 10 / 31 Application: Commitments. 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.
Dr.Ramya R S Block Chain Technologies 11 / 31
Property 3: Puzzle friendliness
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 n.
Meaning If someone wants to target the hash function to come out to some particular output value y, that if there’s part of the input that is chosen in a suitably randomized way, it’s very difficult to find another value that hits exactly that target.
Dr.Ramya R S Block Chain Technologies 12 / 31
Application: Search puzzle
Dr.Ramya R S Block Chain Technologies 13 / 31
SHA-256
Bitcoin uses primarily SHA 256.
a hash function that works on fixed-length inputs, there’s a generic method to convert it into a hash function that works on arbitrary-length inputs. It’s called the Merkle-Damgard transform. SHA-256 is one of a number of commonly used hash functions that make use of this method.
Dr.Ramya R S Block Chain Technologies 14 / 31
SHA 256 Simplified
The input to the hash function, which can be of any size, is divided into blocks of 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.
Dr.Ramya R S Block Chain Technologies 15 / 31
SHA 256 Simplified
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.
Dr.Ramya R S Block Chain Technologies 16 / 31
Hash Pointers and Data Structures
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.
Dr.Ramya R S Block Chain Technologies 17 / 31
Linked List 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.
Dr.Ramya R S Block Chain Technologies 18 / 31
Tamper Evident Block
If the adversary wants to tamper with data anywhere in this entire
chain, He will have to tamper with the hash pointers all the way back to the beginning. Road Block- He won’t be able to tamper with the head of the list. Just remembering this single hash pointer, we’ve essentially remembered a tamper evident hash of the entire list. So we can build a block chain like this containing as many blocks as we want, going back to some special block at the beginning of the list, which we will call the genesis block.
Dr.Ramya R S Block Chain Technologies 19 / 31
Dr.Ramya R S Block Chain Technologies 20 / 31 Merklee Tree
Dr.Ramya R S Block Chain Technologies 21 / 31
Merkle Tree
A binary tree with hash pointers is known as a Merkle tree, after its inventor Ralph Merkle. We have a number of blocks containing data. 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. In turn group these into groups of two, and for each pair, create a new data structure that contains the hash of each. Continue doing this until we reach a single block, the root of the tree.
Dr.Ramya R S Block Chain Technologies 22 / 31
Proof of Membership If 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.
Dr.Ramya R S Block Chain Technologies 23 / 31
Digital Signature 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.
Dr.Ramya R S Block Chain Technologies 24 / 31
Unforgeability If an adversary who knows your public key and gets to see your signatures on some other messages can’t forge your signature on some message for which he has not seen your signature. This unforgeability property is generally formalized in terms of a game that we play with an adversary
Dr.Ramya R S Block Chain Technologies 25 / 31
A simple Cryptocurrency
There are 2 coins:
Goofy Coin The first rule is that a designated entity, Goofy, can create new coins whenever he wants and these newly created coins belong to him. The second rule of GoofyCoin is that whoever owns a coin can transfer it on to someone else. Transferring a coin is not simply a matter of sending the coin data structure to the recipient — it’s done using cryptographic operations.
ScroogeCoin: To solve the double-spending problem
Dr.Ramya R S Block Chain Technologies 26 / 31
GoofyCoin
Each block has the ID of a transaction, the transaction’s contents,
and a hash pointer to the previous block. Scrooge digitally signs the final hash pointer, which binds all of the data in this entire structure, and publishes the signature along with the block chain.
Dr.Ramya R S Block Chain Technologies 27 / 31
Goofy can create new coins by simply signing a statement that he’s making a new coin with a unique coin ID.
Whoever owns a coin can pass it on to someone else by signing a
statement that saying, “Pass on this coin to X” (where X is specified as a public key)
Anyone can verify the validity of a coin by following the chain of hash pointers back to its creation by Goofy, verifying all of the signatures along the way. valid coin. Dr.Ramya R S Block Chain Technologies 28 / 31 Scrooge Coin
Each block has the ID of a transaction, the transaction’s contents,
and a hash pointer to the previous block. Scrooge digitally signs the final hash pointer, which binds all of the data in this entire structure, and publishes the signature along with the block chain.
Dr.Ramya R S Block Chain Technologies 28 / 31
Rules Scrooge Coin The consumed coins are valid, that is, they really were created in previous transactions. The consumed coins were not already consumed in some previous transaction. That is, that this is not a double-spend. The total value of the coins that come out of this transaction is equal to the total value of the coins that went in. That is, only Scrooge can create new value. The transaction is validly signed by the owners of all of the consumed coins.
