Photo By : Zach Copley used under creative commons

“Bitcoin and Cryptocurrency Technologies” Online Course Summery (Lecture 1)

Ahmed Rashwan

17 min readFeb 3, 2016

This is my notes & summery for this course “Bitcoin and Cryptocurrency Technologies” on coursera , the course material is very useful to gain a more technical understanding of Bitcoin and Cryptocurrency in general.
This is just a summery of the course content and PDF it dosen’t compensate for watching the videos and i posted it so that future students of this course may benefit from it.
All images are courtesy of the instructors’ PDF published in the course resources .

Segment 1.1 (Cryptographic Hash Functions) :

Cryptographic hash function :

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, we will assume a 256-bit output size.
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).
For a hash function to be cryptographically secure we need to add the following properties :
Collision-free.
Hiding.
Puzzle-friendly.

What we mean by “Collision-free” ? :

A collision occurs when two distinct inputs produce the same output. A hash function H(.) is collision-free if nobody can find a collision.

Notice that we said nobody can find a collision, but we did not say that no collisions exist. Actually, we know for a fact that collisions do exist, and we can prove this by a simple counting argument. 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 (256 bit). Because the input space is larger than the output space , there must be input strings that map to the same output string.

To find a collision in a (256 bit output string) we can randomly choose just ²¹³⁰ + 1 inputs, it turns out there’s a 99.8% chance that at least two of them are going to collide. However it’s impractical as it takes a huge amount of time.
A practical way to find collisions depends on the hash function itself some are easy to find collisions and some are not. Yet for the latter hash functions we don’t know if such methods exist. We suspect that they are collision-free. However, there are no hash functions proven to be collision-free. 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.
The usefulness of the collision-free attribute is that we can use the hash as a way to know if 2 inputs (x,y) are equal then they will have the same hash otherwise they are not equal. so if the 2 inputs are 2 big files and we want to make sure if they are the same file we can compare their hashes and if they are different then it’s safe to assume that x and y are different without having to compare the whole file, so the hash is used as a “message digest”.

What we mean by “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.
The problem is that this property can’t be true in the stated form. for example: we’re going to do an experiment where we flip a coin. If the result of the coin flip was heads, we’re going to announce the hash of the string “heads”. If the result was tails, we’re going to announce the hash of the string “tails”. We then ask someone, an adversary, who didn’t see the coin flip, but only saw this hash output, to figure out what the string was that was hashed. In response, they would simply compute both the hash of the string “heads” and the hash of the string “tails”, and they could see which one they were given. And so, in just a couple steps, they can figure out what the input was.
The adversary was able to guess what the string was because there were only two possible values of x, and it was easy for the adversary to just try both of them. 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.
We can hide even an input that’s not spread out by concatenating it with another input that is spread out. We can now be slightly more precise about what we mean by hiding : 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.

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.

Commitment scheme :

A commitment scheme consists of two algorithms:
com := commit(msg, key) The commit function takes a message and secret key as input and returns a commitment.
commit(msg) := (H(key ‖ msg), key) where key is a random 256-bit value

isValid:= verify(com, key, msg) The verify function takes a commitment, key, and message as input. It returns true if the com is a valid commitment to msg under the key, key. It returns false otherwise.
verify(com, key, msg) := true if H(key ‖ msg) = com; false otherwise.
We require that the following two security properties hold:
Hiding: Given com, it is infeasible to find msg
Hiding: Given H(key ‖ msg), infeasible to find msg
Binding: For any value of key, it is infeasible to find two messages, msg and msg’ such that msg ≠ msg’ and verify(commit(msg, key), key, msg’) == true
Binding: For any value of key, it is infeasible to find two messages, msg and msg’ such that msg ≠ msg’ and H(key ‖ msg) = H(key ‖ msg’)

What we mean “Puzzle Friendless”?

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 .
what this means is that 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.

Application “Search puzzle” :

 A search puzzle consists of :
a hash function (H), a value id (which we call the puzzle-ID), chosen from a high min-entropy distribution and a target set (Y) A solution to this puzzle is a value (x), such that H(id ‖ x) ∈ Y .
If a search puzzle is puzzle-friendly, this implies that there’s no solving strategy for this puzzle which is much better than just trying random values of x. And so, if we want to pose a puzzle that’s difficult to solve, we can do it this way as long as we can generate puzzle-IDs in a suitably random way.

One application of the three properties of hash functions is SHA-256 and it’s the one that Bitcoin uses.

Segment 1.2 (Hash pointers and data structures) :

hash pointer :

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.

Block Chain :

A linked list built using hash pointers . 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.

Application “tamper-evident log” :

A 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 can detect it.
How can we detect tamper ? : If an adversary changes the data of some block (k). Since the data has been changed, the hash in block (k + 1), which is a hash of the entire block (k), is not going to match up. And so we will detect the inconsistency between the new data in block (k) and the hash pointer in block (k + 1). Of course the adversary can continue to try and cover up this change by changing the next block’s hash as well. The adversary can continue doing this, but this strategy will fail when he reaches the head of the list. Specifically, as long as we store the hash pointer at the head of the list in a place where the adversary cannot change it, the adversary will be unable to change any block without being detected.
So by just remembering the head 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”.

Application “Merkle trees” :

A binary tree built with hash pointers , 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.

Also “tamper-protected” like the blockchain but has also these attributes :
Proof of membership : unlike the blockcahin ,”Merkle tree” 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. If there are (n) nodes in the tree, only about log(n) items need to be shown. And since each step just requires computing the hash of the child block, it takes about log(n) time for us to verify it. And so even if the Merkle tree contains a very large number of blocks, we can still prove membership, in a relatively short time.
Proof of non-membership : With a sorted Merkle tree (take the data block at the bottom and sort them using any sorting function) it becomes possible to verify non-membership in a log(n) time . That is, we can prove that a particular block is not in the Merkle tree by showing a path to the item that’s just before where the item in question would be and showing the path to the item that is just after where it would be. If these two items are consecutive in the tree, then this serves as a proof that the item in question is not included.

Segment 1.3 (Digital Signatures) :

A digital signature is supposed to be the digital analog to a handwritten signature on paper.

Digital Signature Scheme :

(sk, pk) := generateKeys(keysize) The generateKeys method takes a (key size) and generates a key pair. The secret key (sk) is kept privately and used to sign messages. (pk) is the public verification key that you give to everybody. Anyone with this key can verify your signature.
sig := sign(sk, message) The sign method takes a message (msg), and a secret key (sk), as input and outputs a signature for the (msg) under (sk).
isValid := verify(pk, message, sig) The verify method takes a message, a signature, and a public key as input. It returns a boolean value, isValid, that will be true if (sig) is a valid signature for (message) under public key (pk), and false otherwise.

Digital Signatures have two properties :

Valid signatures must verify : If I sign a message with (sk), my secret key, and someone later tries to validate that signature over that same message using my public key (pk), the signature must validate correctly.
Signatures are existentially unforgeable: it’s computationally infeasible to forge signatures. That is, 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
We say that the signature scheme is unforgeable if and only if, no matter what algorithm the adversary is using, his chance of successfully forging a message is extremely small — so small that we can assume it will never happen in practice.

Practical concerns for using digital signatures :

we need a good source of randomness in the algorithm of (generateKeys) and (sign) .The importance of this really can’t be underestimated as bad randomness will make your otherwise-secure algorithm insecure.
there’s a limit on the message size that you’re able to sign because real schemes are going to operate on bit strings of limited length. There’s an easy way around this limitation: sign the hash of the message, rather than the message itself.
Another trick that we will use later is that you can sign a hash pointer. If you sign a hash pointer, then the signature covers, or protects, the whole structure — not just the hash pointer itself, but everything the chain of hash pointers points to.
Bitcoin uses (ECDSA)_Elliptic Curve Digital Signature Algorithm_ for digital signatures , With (ECDSA) a good source of randomness is essential because a bad source of randomness will likely leak your key. It makes intuitive sense that if you use bad randomness in generating a key, then the key you generate will likely not be secure. But it’s a quirk of (ECDSA) that, even if you use bad randomness just in making a signature, using your perfectly good key, that also will leak your private key.

Segment 1.4 (Public keys as identities) :

We can take a public key 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. From this viewpoint, the public key is an identity. In order for someone to speak for the identity pk, they must know the corresponding secret key (sk).
You simply create a new key pair (sk) and (pk), via the (generateKeysoperation) in our digital signature scheme. (pk) is the new public identity that you can use, and (sk) is the corresponding secret key that only you know and lets you speak for on behalf of the identity pk. In practice, you may use the hash of (pk) as your identity since public keys are large.

Application : “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. If you want a new identity, you can just generate one at any time, and you can make as many as you want.
this is the way Bitcoin does identity. These identities are called addresses, in Bitcoin jargon. You’ll frequently hear the term address used in the context of Bitcoin and cryptocurrencies, and that’s really just a hash of a public key.
The probability of someone else generating the same 256-bit key as you is so small that we don’t have to worry about it in practice. We are for all intents and purposes guaranteed that it will never happen, so it is crucial to use a good source of randomness when generating keys to ensure that practical guarantees match the theoretical ones.
you can create a random-looking identity all by yourself without telling anyone your real-world identity. But it’s not that simple. Over time, the identity that you create makes a series of statements. People see these statements and thus know that whoever owns this identity has done a certain series of actions. They can start to connect the dots, using this series of actions to infer things about your real-world identity.

Segment 1.5 (Simple Cryptocurrencies) :

GoofyCoin :

The first and simplest example of a cryptocurrency , it has three rules :
Goofy, can create new coins whenever he wants and these newly created coins belong to him. To create a coin, (Goofy) generates a unique coin ID (uniqueCoinID) that he’s never generated before and constructs the string “CreateCoin [uniqueCoinID]”. He then signs this string with his secret signing key. The string, together with Goofy’s signature, is a coin. Anyone can verify that the coin contains Goofy’s valid signature of a (CreateCoin) statement, and is therefore a valid coin.
Whoever owns a coin can transfer it on to someone else, if (Goofy) wants to transfer a coin that he created to (Alice). To do this he creates a new statement that says “Pay this to Alice” where “this” is a hash pointer that references the coin in question And “Alice” refers to Alice’s public key. Finally, (Goofy) signs the string representing the statement. Since (Goofy) is the one who originally owned that coin, he has to sign any transaction that spends the coin. Once this data structure representing Goofy’s transaction signed by him exists, Alice owns the coin. She can prove to anyone that she owns the coin, because she can present the data structure with Goofy’s valid signature.
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.

There’s a fundamental security problem with GoofyCoin. Let’s say (Alice) passed her coin on to (Bob) by sending her signed statement to (Bob) but didn’t tell anyone else. She could create another signed statement that pays the very same coin to (Chuck). To (Chuck), it would appear that it is perfectly valid transaction, and now he’s the owner of the coin. (Bob) and (Chuck) would both have valid-looking claims to be the owner of this coin. This is called a double-spending attack as (Alice) is spending the same coin twice.

Scroogecoin :

The second cryptocurrency example that solves Goofycoin’s double spending problem :
(Scrooge) publishes an append-only ledger (Block chain) containing the history of all the transactions that have happened. The append-only property ensures that any data written to this ledger will remain forever. so we can use it to defend against double-spending by requiring all transactions to be written the ledger before they are accepted. That way, it will be publicly visible if coins were previously sent to a different owner.
In the block chain each block has one transaction in it (in practice, as an optimization, we’d put multiple transactions into the same block, as Bitcoin does.) 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.

there are two kinds of transactions. The first kind is (CreateCoins) which creates multiple coins. Each coin has a serial number within the transaction. Each coin also has a value; it’s worth a certain number of ScroogeCoins. Finally, each coin has a recipient, which is a public key that gets the coin when it’s created. So (CreateCoins) creates a bunch of new coins with different values and assigns them to people as initial owners. We refer to coins by CoinIDs. A (CoinID) is a combination of a transaction ID and the coin’s serial number within that transaction.

The second kind of transaction is (PayCoins). It consumes some coins, that is, destroys them, and creates new coins of the same total value. The new coins might belong to different people (public keys). This transaction has to be signed by everyone who’s paying in a coin. So if you’re the owner of one of the coins that’s going to be consumed in this transaction, then you need to digitally sign the transaction to say that you’re really okay with spending this coin.

(PayCoins) transaction is valid if four things are true:
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.
If all of those conditions are met, then this PayCoins transaction is valid and Scrooge will accept it. He’ll write it into the history by appending it to the block chain, after which everyone can see that this transaction has happened.
Coins in this system are immutable — they are never changed, subdivided, or combined. Each coin is created, once, in one transaction and later consumed in some other transaction. But we can get the same effect as being able to subdivide or combine coins by using transactions. For example, to subdivide a coin, Alice create a new transaction that consumes that one coin, and then produces two new coins of the same total value. Those two new coins could be assigned back to her. So although coins are immutable in this system, it has all the flexibility of a system that didn’t have immutable coins.
The core problem with ScroogeCoin is (Scrooge) himself , he has too much influence .he could stop endorsing transactions from some users, denying them service and making their coins unspendable, he could refuse to publish transactions unless they transfer some mandated transaction fee to him. Scrooge can also of course create as many new coins for himself as he wants. Or Scrooge could get bored of the whole system and stop updating the block chain completely.

So the biggest challenge in cryptocurrency is how to decentralize the system?

To do that, we need to figure out how all users can agree upon a single published (block chain) as the history of which transactions have happened. They must all agree on which transactions are valid, and which transactions have actually occurred. They also need to be able to assign IDs to things in a decentralized way.

End of lecture 1.

You can find the summary of Lecture 2 here .
If you find this content useful please recommend it so others may see it.