Photo By : Zach Copley used under creative commons

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

19 min readFeb 7, 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 2.1 (Centralization vs Decentralization) :

Decentralization is not all or nothing; almost no system is purely decentralized or purely centralized. For example, email is fundamentally a decentralized system based on a standardized protocol (SMTP) Yet, what has happened in the market is that a small number of centralized webmail providers have become dominant. Similarly, while the Bitcoin protocol is decentralized, services like Bitcoin exchanges and wallet software, or software that allows people to manage their bitcoins may be centralized or decentralized to varying degrees.

We can break down the question of how the Bitcoin protocol achieves decentralization into five more specific questions:

1. Who maintains the ledger of transactions?
2. Who has authority over which transactions are valid?
3. Who creates new bitcoins?
4. Who determines how the rules of the system change?
5. How do bitcoins acquire exchange value?

The peer-to-peer network is close to purely decentralized since anybody can run a Bitcoin node and there’s a fairly low barrier to entry.
Bitcoin mining is technically also open to anyone, but it requires a very high capital cost. Because of this there has been a high degree of centralization, or a concentration of power, in the Bitcoin mining ecosystem. Many in the Bitcoin community see this as quite undesirable.
Updates to the software that Bitcoin nodes run has a bearing on how and when the rules of the system change. One can imagine that there are numerous interoperable implementations of the protocol, as with email. But in practice, most nodes run the reference implementation, and its developers are trusted by the community and have a lot of power.

Segment 2.2 (Distributed consensus) :

Distributed consensus has been studied for decades in computer science. The traditional motivating application is reliability in distributed system.

Distributed consensus protocol :

There are (n) nodes that each have an input value. Some of these nodes are faulty or malicious.

A distributed consensus protocol has the following two properties:

It must terminate with all honest nodes in agreement on the value.
The value must have been generated by an honest node.
To understand how distributed consensus could work in Bitcoin, remember that Bitcoin is a peer-to-peer system. When Alice wants to pay Bob, what she actually does is broadcast a transaction to all of the Bitcoin nodes that comprise the peer-to-peer network . It’s possible that Bob is running one of the nodes in the peer-to-peer network. In fact, if he wants to be notified that this transaction did in fact happen and that he got paid, running a node might be a good idea. Nevertheless, there is no requirement that Bob be listening on the network; running a node is not necessary for Bob to receive the funds. The bitcoins will be his whether or not he’s operating a node on the network.

Given that a variety of users are broadcasting these transactions to the network, the nodes must agree on exactly which transactions were broadcast and the order in which these transactions happened. This will result in a single, global ledger for the system.
At any given point, all the nodes in the peer-to-peer network have a ledger consisting of a sequence of blocks, each containing a list of transactions, that they’ve reached consensus on. Additionally, each node has a pool of outstanding transactions that it has heard about but have not yet been included on the block chain. For these transactions, consensus has not yet happened, and so by definition, each node might have a slightly different version of the outstanding transaction pool. In practice, this occurs because the peer-to-peer network is not perfect, so some nodes may have heard about a transaction that other nodes have not heard about.
at regular intervals, say every 10 minutes, every node in the system proposes its own outstanding transaction pool to be the next block. Then the nodes execute some consensus protocol, where each node’s input is its own proposed block. Now, some nodes may be malicious and put invalid transactions into their blocks, but we might assume that other nodes will be honest. If the consensus protocol succeeds, a valid block will be selected as the output.If some transaction somehow didn’t make it into this particular block, it could just wait and get into the next block.

There are a number of technical problems with this approach :

Consensus in general is a hard problem since nodes might crash or be outright malicious.
Specifically in the Bitcoin context, the network is highly imperfect. It’s a peer-to-peer system, and not all pairs of nodes are connected to each other. There could be faults in the network because of poor Internet connectivity for example, and thus running a consensus protocol in which all nodes must participate is not really possible.
There’s a lot of latency in the system because it’s distributed all over the Internet.
One particular consequence of this high latency is that there is no notion of global time. What this means is that not all nodes can agree to a common ordering of events simply based on observing timestamps. So the consensus protocol cannot contain instructions of the form, “The node that sent the first message in step 1 must do X in step 2.” This simply will not work because not all nodes will agree on which message was sent first in the step 1 of the protocol.
Because of these constraints, much of the literature on distributed consensus is somewhat pessimistic, and many impossibility results have been proven.
these impossibility results were intended to study distributed databases.

This model doesn’t carry over very well to the Bitcoin setting because Bitcoin violates many of the assumptions built into the models:

Bitcoin introduces the idea of incentives, which is novel for a distributed consensus protocol. This is only possible in Bitcoin because it is a currency and therefore has a natural mechanism to incentivize participants to act honestly.
Bitcoin embraces the notion of randomness, Bitcoin’s consensus algorithm relies heavily on randomization. Also, it does away with the notion of a specific starting point and ending point for consensus. Instead, consensus happens over a long period of time. nodes can’t be certain that any particular transaction or a block has made it into the ledger. Instead, as time goes on, the probability that your view of any block will match the eventual consensus view increases, and the probability that the views will diverge goes down exponentially.

Segment 2.3(Consensus without identity:using block chain) :

Bitcoin nodes do not have persistent, long-term identities. This is another difference from traditional distributed consensus algorithms. One reason for this lack of identities is that in a peer-to-peer system, there is no central authority to assign identities to participants and verify that they’re not creating new nodes at will. The technical term for this is a Sybil attack. Sybils are just copies of nodes that a malicious adversary can create to look like there are a lot of different participants, when in fact all those pseudo-participants are really controlled by the same adversary. The other reason is that pseudonymity is inherently a goal of Bitcoin. Even if it were possible or easy to establish identities for all nodes or all participants, we wouldn’t necessarily want to do that, nobody is forced to reveal their real-life identity, like their name or IP address, in order to participate. And that’s a central feature of Bitcoin’s design.
If nodes did have identities, the design would be easier. For starters, identities would allow us to put in the protocol instructions of the form, “Now the node with the lowest numerical ID should take some step.”. also If nodes were identified and it weren’t trivial to create new node identities, then we could make assumptions on the number of nodes that are malicious, and we could derive security properties out of that.
Suppose there is somehow an ability to pick a random node in the system. A good motivating analogy for this is a lottery or a raffle, Further assume, for the moment, that this token generation and distribution algorithm is sufficiently smart so that if the adversary is going to try to create a lot of Sybil nodes, all of those Sybils together will get only one token. This means the adversary is not able to multiply his power by creating new nodes.

This assumption of random node selection makes possible something called implicit consensus.

There are multiple rounds in our protocol, each corresponding to a different block in the block chain. In each round, a random node is somehow selected, and this node gets to propose the next block in the chain.
if that node is malicious Other nodes will implicitly accept or reject that block by choosing whether or not to build on top of it. If they accept that block, they will signal their acceptance by extending the block chain including the accepted block. By contrast, if they reject that block, they will extend the chain by ignoring that block, and building on top of whichever is the previous block that they accepted.

Bitcoin consensus algorithm (simplified) :

This algorithm is simplified in that it assumes the ability to select a random node
New transactions are broadcast to all nodes.
Each node collects new transactions into a block.
In each round a random node gets to broadcast its block.
Other nodes accept the block only if all transactions in it are valid (unspent, valid signatures).
Nodes express their acceptance of the block by including its hash in the next block they create.

To understand why this consensus algorithm works consider how a malicious adversary — who we’ll call Alice — may be able to subvert this process :

Stealing Bitcoins? : No. Even if it is Alice’s turn to propose the next block in the chain, she cannot steal other users’ bitcoins. Doing so would require Alice to create a valid transaction that spends that coin. This would require Alice to forge the owners’ signatures which she cannot do.
Denial of service attack : Say Alice really dislikes some other user Bob. Alice can then decide that she will not include any transactions originating from Bob’s address in any block that she proposes to get onto the block chain, it’s nothing more than a minor annoyance. If Bob’s transaction doesn’t make it into the next block that Alice proposes, he will just wait until an honest node gets the chance to propose a block and then his transaction will get into that block.
Double-spend attack : Alice adds an item to her shopping cart on Bob’s website and the server requests payment. Then Alice creates a Bitcoin transaction from her address to Bob’s and broadcasts it to the network. Let’s say that some honest node creates the next block, and includes this transaction in that block. So there is now a block that was created by an honest node that contains a transaction that represents a payment from Alice to the merchant Bob. Recall that a transaction is a data structure that contains Alice’s signature, an instruction to pay to Bob’s public key, and a hash. This hash represents a pointer to a previous transaction output that Alice received and is now spending. That pointer must reference a transaction that was included in some previous block in the consensus chain.
Upon seeing this transaction included in the block chain, Bob concludes that Alice has paid him and allows Alice to download the software. Suppose the next random node that is selected in the next round happens to be controlled by Alice. Now since Alice gets to propose the next block, she could propose a block that ignores the block that contains the payment to Bob and instead contains a pointer to the previous block. Furthermore, in the block that she proposes, Alice includes a transaction that transfers the very coins that she was sending to Bob to a different address that she herself controls. This is a classic double-spend pattern. Since the two transactions spend the same coins, only one of them can be included in the block chain.

And how do we know if this double spend attempt is going to succeed or not? Well, that depends on which block will ultimately end up on the long-term consensus chain, What determines which block will be included? Honest nodes follow the policy of extending the longest valid branch, so which branch will they extend? There is no right answer! At this point, the two branches are the same length — they only differ in the last block and both of these blocks are valid. The node that chooses the next block then may decide to build upon either one of them.
If the next node does build on the double-spend block for whatever reason, then this chain will now be longer than the one that includes the transaction to Bob. At this point, the next honest node is much more likely to continue to build on this chain since it is longer. This process will continue, and it will become increasingly likely that the block containing the double-spend will be part of the long-term consensus chain. The block containing the transaction to Bob, on the other hand, gets completely ignored by the network, and this is now called an orphan block.
Let’s now reconsider this whole situation from Bob-the-merchant’s point of view. When Alice broadcasts the transaction that represents her payment to Bob, Bob is listening on the network and hears about this transaction even before the next block is created. Bob can complete the checkout process on the website and allow Alice to download the software right at that moment. That’s called a zero-confirmation transaction, This leads to an even more basic double spend attack than the one described before.
On the other hand, a cautious merchant would not release the software to Alice even after the transaction was included in one block, and would continue to wait. In fact, the double-spend probability decreases exponentially with the number of confirmations. So, if the transaction that you’re interested in has received (k) confirmations, then the probability that a double-spend transaction will end up on the long-term consensus chain goes down exponentially as a function of (k). The most common heuristic that’s used in the Bitcoin ecosystem is to wait for six confirmations. you’re never 100 percent sure that a transaction you’re interested in is on the consensus branch. But, this exponential probability guarantee is rather good. After about six transactions, there’s virtually no chance that you’re going to go wrong.

Segment 2.4 (Incentives and proof of work) :

Assuming that we’re able to pick a random node and, perhaps more problematically, that at least 50 percent of the time, this process will pick an honest node. This assumption of honesty is particularly problematic if there are financial incentives for participants to subvert the process, in which case we can’t really assume that a node will be honest. The question then becomes: can we give nodes an incentive for behaving honestly? We’re going to use bitcoins to incentivize the nodes that created the blocks that did end up on the long-term consensus chain.
The block reward: According to the rules of Bitcoin, the node that creates a block gets to include a special transaction in that block. This transaction is a coin-creation transaction, and the node can also choose the recipient address of this transaction. Of course that node will typically choose an address belonging to itself. You can think of this as a payment to the node in exchange for the service of creating a block on the consensus chain. At the time of this writing, the value of the block reward is now fixed at 25 Bitcoins.
It may appear that this node gets the block reward regardless of whether it proposes a valid block or behaves maliciously. But this is not true! how will this node “collect” its reward? That will only happen if the block in question ends up on the long-term consensus branch because just like every other transaction, the coin-creation transaction will only be accepted by other nodes if it ends up on the consensus chain. That’s the key idea behind this incentive mechanism. It incentivizes nodes to behave in whatever way they believe will get other nodes to extend their blocks.
The block reward is cut in half every four years limiting the total supply of bitcoins to 21 million. It is important to note that this is the only way in which new bitcoins are allowed to be created. There is no other coin generation mechanism, and that’s why 21 million is a final and total number (as the rules stand now, at least) for how many bitcoins there can ever be.
Transaction fee: The creator of any transaction can choose to make the total value of the transaction outputs less than the total value of its inputs. Whoever creates the block that first puts that transaction into the block chain gets to collect the difference.
So if you’re a node that’s creating a block that contains, say, 200 transactions, then the sum of all those 200 transaction fees is paid to the address that you put into that block. The transaction fee is purely voluntary, but we expect, based on our understanding of the system, that as the block reward starts to run out, it will become more and more important, almost mandatory, for users to include transaction fees in order to get a reasonable quality of service.
There are still a few problems remaining with the consensus mechanism as we described it. The first major one is how we can pick a random node? Second, The system can become unstable as the incentives cause a free-for-all where everybody wants to run a Bitcoin node in the hope of capturing some of these rewards. And a third one is an even trickier version of this problem, which is that an adversary might create a large number of Sybil nodes to try and subvert the consensus process.
It turns out that all of these problems are related, and all of them have the same solution, which is called proof-of-work. The key idea behind proof-of-work is that we approximate the selection of a random node by instead selecting nodes in proportion to a resource that we hope that nobody can monopolize, that resource is computing power. Another way of understanding this is that we’re allowing nodes to compete with each other by using their computing power, and that will result in nodes automatically being picked in that proportion. Yet another view of proof-of-work is that we’re making it moderately hard to create new identities. It’s sort of a tax on identity creation and therefore on the Sybil attack.
Bitcoin achieves proof-of-work using hash puzzles. In order to create a block, the node that proposes that block is required to find a number, or nonce, such that when you concatenate the nonce, the previous hash, and the list of transactions that comprise that block and take the hash of this whole string, then that hash output should be a number that falls into a target space that is quite small in relation to the much larger output space of that hash function. We can define such a target space as any value falling below a certain target value. In this case, the nonce will have to satisfy the following inequality: H(nonce || prev_hash || tx || tx || … || tx) < target.
As of the end of 2014, the difficulty level is about 10²⁰ hashes per block. In other words the size of the target space is only 1/10²⁰ of the size of the output space of the hash function. This is a lot of computation — it’s out of the realm of possibility for a commodity laptop, for example. Because of this, only some nodes even bother to compete in this block creation process. This process of repeatedly trying and solving these hash puzzles is known as Bitcoin mining, and we call the participating nodes miners. Even though technically anybody can be a miner, there’s been a lot of concentration of power in the mining ecosystem due to the high cost of mining.
Parameterizable cost: we want the cost to be parameterizable, not a fixed cost for all time. The way that’s accomplished is that all the nodes in the Bitcoin peer-to-peer network will automatically recalculate the target, that is the size of the target space as a fraction of the output space, every (2016) blocks. They recalculate the target in such a way that the average time between successive blocks produced in the Bitcoin network is about 10 minutes. With a 10-minute average time between blocks the recalculation of the target happens roughly every two weeks.
that means that each two week nodes will automatically readjust the target, and the amount of work that you have to do to be able to find a block is going to change. So if you put in a fixed amount of hardware investment, the rate at which you find blocks is actually dependent upon what other miners are doing. There’s a very nice formula to capture this, which is that the probability that any given miner, Alice, is going to win the next block is equivalent to the fraction of global hash power that she controls. This means that if Alice has mining hardware that’s about 0.1 percent of total hash power, she will find roughly one in every 1,000 blocks.
If blocks were to come very close together, then there would be a lot of inefficiency, and we would lose the optimization benefits of being able to put a lot of transactions in a single block. despite some disagreements about the ideal latency, everybody agrees that it should be a fixed amount. It cannot be allowed to go down without limit. That’s why we have the automatic target recalculation feature.
we can now state crisply, that a lot of attacks on Bitcoin are infeasible if the majority of miners, weighted by hash power, are following the protocol — or, are honest. This is true because if a majority of miners, weighted by hash power, are honest, the competition for proposing the next block will automatically ensure that there is at least a 50 percent chance that the next block to be proposed at any point is coming from an honest node.
Trivial to verify: it is trivial to verify that a node has computed proof of work correctly. Even if it takes a node, on average, 10²⁰ tries to find a nonce that makes the block hash fall below the target, that nonce must be published as part of the block. It is thus trivial for any other node to look at the block contents, hash them all together, and verify that the output is less than the target. This is quite an important property because, once again, it allows us to get rid of centralization.

Segment 2.5 (Putting it all together) :

Cost of mining : At the current difficulty level, finding a single block takes computing about 10²⁰ hashes and the block reward is about 25 Bitcoins, which is a sizable amount of money at the current exchange rate.
If (block reward + tx fees) > (hardware cost + operating costs) then miner profits.
the costs that the miner incurs are typically denominated in dollars or some other traditional currency, but their reward is denominated in bitcoin. So this equation has a hidden dependence on Bitcoin’s exchange rate at any given time.
The smallest possible value is 0.00000001 BTC (bitcoins), which is called 1 Satoshi.
bootstrapping : There is a tricky interplay between three different ideas in Bitcoin: the security of the block chain, the health of the mining ecosystem, and the value of the currency.
We want the block chain to be secure for Bitcoin to be a viable currency. For the block chain to be secure, an adversary cannot create a lot of mining nodes and take over 50 percent or more of the new block creation.
A prerequisite is having a healthy mining ecosystem made up of largely honest, protocol-following nodes. But what’s a prerequisite for that — when can we be sure that a lot of miners will put a lot of computing power into participating in this hash puzzle solving competition? Well, they’re only going to do that if the exchange rate of Bitcoin is pretty high because the rewards that they receive are denominated in Bitcoins whereas their expenditure is in dollars.
But what ensures a high and stable value of the currency? That can only happen if users in general have trust in the security of the block chain. If they believe that the network could be overwhelmed at any moment by an attacker, then Bitcoin is not going to have a lot of value as a currency. So you have this interlocking interdependence between the security of the block chain, a healthy mining ecosystem and the exchange rate.
51-percent attack : Let’s consider what would happen if consensus failed and there was in fact a 51-percent attacker who controls 51 percent or more of the mining power in the Bitcoin network.
Can this attacker steal coins from an existing address? No, because stealing from an existing address is not possible unless you subvert the cryptography.
Let’s say the 51 percent attacker creates an invalid block that contains an invalid transaction that represents stealing Bitcoins from an existing address that the attacker doesn’t control and transferring them to his own address. The attacker can pretend that it’s a valid transaction and keep building upon this block. The attacker can even succeed in making that the longest branch. But the other honest nodes are simply not going to accept this block with an invalid transaction and are going to keep mining based on the last valid block that they found in the network.
Can the 51-percent attacker suppress some transactions? Let’s say there is some user, Carol, whom the attacker really doesn’t like. The attacker knows some of Carol’s addresses, and wants to make sure that no coins belonging to any of those addresses can possibly be spent. Is that possible? Since he controls the consensus process of the block chain, the attacker can simply refuse to create any new blocks that contain transactions from one of Carol’s addresses. The attacker can further refuse to build upon blocks that contain such transactions. However, he can’t prevent these transactions from being broadcast to the peer-to-peer network because the network doesn’t depend on the block chain, or on consensus, The attacker cannot stop the transactions from reaching the majority of nodes, so even if the attack succeeds, it will at least be apparent that the attack is happening.
Can the attacker change the block reward? This is a change to the rules of the system, and because the attacker doesn’t control the copies of the Bitcoin software that all of the honest nodes are running, this is also not possible. Other nodes will simply not recognize the increase in the block reward, and the attacker will thus be unable to spend them.
Can the attacker somehow destroy confidence in Bitcoin? Well, let’s imagine what would happen. If there were a variety of double-spend attempts, situations in which nodes did not extend the longest valid branch, and other attempted attacks, then people are going to likely decide that Bitcoin is no longer acting as a decentralized ledger that they can trust and the exchange rate of Bitcoin will plummet. In fact, if it is known that there is a party that controls 51 percent of the hash power, then it’s possible that people will lose confidence in Bitcoin even if the attacker is not necessarily trying to launch any attacks. Indeed, this is the main practical threat if a 51 percent attack were ever to materialize.

End of lecture 2 .

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