Photo By : Zach Copley used under creative commons

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

• 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 3.1 (Bitcoin transactions) :

• We’re going to use a simplified model of a ledger for the moment. Instead of blocks, let’s suppose individual transactions are added to the ledger one at a time.

How can we build a currency on top of such a ledger?

• The first model you might think of is that you have an account-based system. You can add some transactions that create new coins and credit them to somebody. And then later you can transfer them. A transaction would say something like “we’re moving 17 coins from Alice to Bob”, and it will be signed by Alice.

• The downside to this way of doing things is that anyone who wants to determine if a transaction is valid will have to keep track of these account balances. Does Alice have the 15 coins that she’s trying to transfer to David? To figure this out, you’d have to look backwards in time forever to see every transaction affecting Alice, and whether or not her net balance at the time that she tries to transfer 15 coins to David is greater than 15 coins.
• Bitcoin doesn’t use an account-based model. Instead, Bitcoin uses a ledger that just keeps track of transactions. Transactions specify a number of inputs and a number of outputs. you can think of the inputs as coins being consumed and the outputs as coins being created. For transactions in which new currency is being minted, there are no coins being consumed . Each transaction has a unique identifier. Outputs are indexed beginning with 0, so we will refer to the first output as “output 0”.

Change addresses: ​

• Why does Alice have to send money to herself in this example? in Bitcoin, the entirety of a transaction output must be consumed by another transaction, or none of it. Alice only wants to pay 17 bitcoins to Bob, but the output that she owns is worth 25 bitcoins. So she needs to create a new output where 8 bitcoins are sent back to herself. It could be a different address from the one that owned the 25 bitcoins, but it would have to be owned by her. This is called a change address​.

Efficient verification: ​

• When a new transaction is added to the ledger, how easy is it to check if it is valid? In this example, we need to look up the transaction output that Alice referenced, make sure that it has a value of 25 bitcoins, and that it hasn’t already been spent, We don’t need to go all the way back to the beginning of the block chain.

Consolidating funds:

• since transactions can have many inputs and many outputs, splitting and merging value is easy. For example, say Bob received money in two different transactions , I’d like to have one transaction I can spend later where I have all the bitcoins. That’s easy — he creates a transaction with the two inputs and one output, with the output address being one that he owns. That lets him consolidate those two transactions.

Joint payments:

• ​Say Carol and Bob both want to pay David. They can create a transaction with two inputs and one output, but with the two inputs owned by two different people. And the only difference from the previous example is that since the two outputs from prior transactions that are being claimed here are from different addresses, the transaction will need two separate signatures — one by Carol and one by Bob.

Transaction syntax :

• Metadata​: There’s some housekeeping information — the size of the transaction, the number of inputs, and the number of outputs. There’s the hash of the entire transaction which serves as a unique ID for the transaction.
• Inputs: ​The transaction inputs form an array, and each input has the same form. An input specifies a previous transaction, so it contains a hash of that transaction, which acts as a hash pointer to it. The input also contains the index of the previous transaction’s outputs that’s being claimed, And then there’s a signature.
• Outputs: ​The outputs are an array. Each output has just two fields. They each have a value, and the sum of all the output values has to be less than or equal to the sum of all the input values. If the sum of the output values is less than the sum of the input values, the difference is a transaction fee to the miner who publishes this transaction.

Segment 3.2 (Bitcoin Scripts) :

• Each transaction output doesn’t just specify a public key. It actually specifies a script. The most common type of transaction in Bitcoin is to redeem a previous transaction output by signing with the correct key. In this case, we want the transaction output to say,”this can be redeemed by a public key that hashes to X, along with a signature from the owner of that public key.”
• The inputs also contain scripts instead of signatures. To validate that a transaction redeems a previous transaction output correctly, we combine the new transaction’s input script and the earlier transaction’s output script. We simply concatenate them, and the resulting script must run successfully in order for the transaction to be valid. These two scripts are called (scriptPubKey​) and (scriptSig) ​because in the simplest case, the output script just specifies a public key (or an address to which the public key hashes), and the input script specifies a signature with that public key.

Bitcoin scripting language:

• ​The scripting language was built specifically for Bitcoin, and is just called ‘Script’ or the Bitcoin scripting language. It has many similarities to a language called Forth, which is an old, simple, stack-based, programming language. The key design goals for Script were to have something simple and compact, yet with native support for cryptographic operations. So, for example, there are special-purpose instructions to compute hash functions and to compute and verify signature.
• The scripting language is stack-based. This means that every instruction is executed exactly once, in a linear manner.there are no loops ,So the number of instructions in the script gives us an upper bound on how long it might take to run and how much memory it could use. The language is not Turing-complete, which means that it doesn’t have the ability to compute arbitrarily powerful functions. because miners have to run these scripts, which are submitted by arbitrary participants in the network. We don’t want to give them the power to submit a script that might have an infinite loop.
• There are only two possible outcomes when a Bitcoin script is executed. It either executes successfully with no errors, in which case the transaction is valid. Or, if there’s any error while the script is executing, the whole transaction will be invalid and shouldn’t be accepted into the block chain. The Bitcoin scripting language has only room for 256 instructions, because each one is represented by one byte. Of those 256, 15 are currently disabled, and 75 are reserved. The reserved instruction codes haven’t been assigned any specific meaning yet, but might be instructions that are added later in time.

Executing a script: ​

• To execute a script in a stack-based programming language, all we’ll need is a stack that we can push data to and pop data from. There are two types of instructions: data instructions and opcodes. When a data instruction appears in a script, that data is simply pushed onto the top of the stack. Opcodes, on the other hand, perform some function, often taking as input data that is on top of the stack.

• The first two instructions in this script are data instructions — the signature and the public key used to generate that signature. These were specified by the recipient in the (scriptSig) component.when we see a data instruction, we just push it onto the stack. The rest of the script is the part that was specified by the sender — the (scriptPubKey) component.
• We have the duplicate instruction (OP_DUP) so we just push a copy of the public key onto the top of the stack. The next instruction is (OP_HASH160) which tells us to pop the top value, compute its cryptographic hash, and push the result onto the top of the stack. When this instruction finishes executing, we will have replaced the public key on the top of the stack with its hash.
• Next, we’re going to do one more push of data onto the stack. Recall that this data was specified by the sender of the coins. It is the hash of the public key that the sender specified had to be used to generate the signature to redeem these coins. At this point, there are two values at the top of the stack. There is the hash of the public key, as specified by the sender, and the hash of the public key that was used by the recipient when trying to claim the coins.
• At this point we’ll run the (EQUALVERIFY) command, which checks that the two values at the top of the stack are equal. If they aren’t, an error will be thrown, and the script will stop executing. we’ll assume that they’re equal, that is, that the recipient of the coins used the correct public key. That instruction will consume those two data items that are at the top of the stack, And the stack now contains two items.
• Now we have to check if the signature is valid. we use ء(OP_CHECKSIG) instruction. This single instruction pops the two values, the public key and signature, off the stack, and verifies that is a valid signature for the entire transaction using that public key.

What’s used in practice :

• ​If we look at the scripts that have actually been used in the history of Bitcoin so far, the vast majority, 99.9 percent, are exactly the same script, which is in fact the script that we used in our example. This is because Bitcoin nodes, by default, have a whitelist of standard scripts, and they refuse to accept scripts that are not on the list.

Proof of burn:

• ​A proof-of-burn is a script that can never be redeemed. Sending coins to a proof-of-burn script establishes that they have been destroyed since there’s no possible way for them to be spent. One use of proof-of-burn is to bootstrap an alternative to Bitcoin by forcing people to destroy Bitcoin in order to gain coins in the new system. Proof-of-burn is quite simple to implement: the (OP_RETURN) opcode throws an error if it’s ever reached. No matter what values you put before OP_RETURN, that instruction will get executed eventually, in which case this script will return false.
• Because the error is thrown, the data in the script that comes after (OP_RETURN) will not be processed. So this is an opportunity for people to put arbitrary data in a script, and hence into the block chain. If you want to write your name, or if you want to timestamp and prove that you knew some data at a specific time, you can create a very low value Bitcoin transaction. You can destroy a very small amount of currency, but you get to write whatever you want into the block chain, which should be kept around forever.

Pay-to-script-hash:

• ​One consequence of the way that Bitcoin scripts works is that the sender of coins has to specify the script exactly. But this can sometimes be quite a strange way of doing things as normal users may not be able to write complex scripts.
• So Instead of having the sender specify the entire script, the sender can specify just a hash of the script that is going to be needed to redeem those coins. So the sender just needs to specify a very simple script which just hashes the top value on the stack, and checks to see if it’s equal to the required redemption script. The receiver of those coins needs to specify as a data value, the value of the script whose hash the sender specified. After this happens, a special second step of validation is going to occur. That top data value from the stack is going to be reinterpreted as instructions, and then it’s going to be executed a second time as a script.
• Getting support for (P2SH) was quite complicated since it wasn’t part of Bitcoin’s initial design specification. It was added after the fact. This is probably the most notable feature that’s been added to Bitcoin that wasn’t there in the original specification. And it removes complexity from the sender, so the recipient can just specify a hash that the sender sends money to.

Segment 3.3 (Applications of Bitcoin scripts) :

Escrow transactions: ​

• Say Alice wants to pay Bob in Bitcoin for Bob to send some physical goods to Alice. The problem though is that Alice doesn’t want to pay until after she’s received the goods, but Bob doesn’t want to send the goods until after he has been paid. What can we do about that? A nice solution in Bitcoin is to introduce a third party and do an escrow transaction. Escrow transactions can be implemented quite simply using (MULTISIG). Alice doesn’t send the money directly to Bob, but instead creates a MULTISIG transaction that requires two of three people to sign in order to redeem the coins. And those three people are going to be Alice, Bob, and some third party arbitrator, Judy, who will come into play in case there’s any dispute.
• In the normal case, Alice and Bob are both honest. So, Alice and Bob both sign a transaction redeeming the funds from escrow, and sending them to Bob. Notice that in this case Judy never had to get involved at all.
• Alice now doesn’t want to pay Bob because she thinks that she got cheated, and she wants to get her money back. So Alice is definitely not going to sign a transaction that releases the money to Bob. But Bob also may deny any wrongdoing and refuse to sign a transaction that releases the money back to Alice. This is where Judy needs to get involved. Judy’s going to have to decide which of these two people deserves the money.

Green addresses:

• Say Alice wants to pay Bob, and Bob’s offline. Since he’s offline, Bob can’t go and look at the block chain . It’s also possible that Bob is online, but doesn’t have the time to go and look at the block chain and wait for the transactions to be confirmed. Remember that normally we want a transaction to be in the block chain and be confirmed by six blocks, which takes up to an hour, before we trust that it’s really in the block chain.
• To solve this problem we have to introduce another third party, which we’ll call the bank (in practice it could be an exchange or any other financial intermediary). Alice is going to talk to her bank, and say, “Hey, it’s me, Alice.Here’s my card or my identification. And I’d really like to pay Bob here?” And the bank will say, “Sure. I’m going to deduct some money out of your account. And draw up a transaction from one of my green addresses over to Bob.” So essentially, the bank is paying Bob here from a bank-controlled address, which we call a green address. Moreover, the bank guarantees that it will not double-spend this money. So as soon as Bob sees that this transaction is signed by the bank, if he trusts the bank’s guarantee not to double-spend the money, he can accept that that money will eventually be his when it’s confirmed in the block chain.
• If the bank ever does double-spend, people will stop trusting its green address(es). In fact, the two most prominent online services that implemented green addresses were (Instawallet) and (Mt. Gox), and both ended up collapsing, Today green addresses aren’t used very much.

Efficient micro-payments:

• Say Bob may be Alice’s wireless service provider, and requires her to pay a small fee for every minute that she talks on her phone.
• Creating a Bitcoin transaction for every minute that Alice speaks on the phone won’t work. That will create too many transactions, and the transaction fees add up,
  So instead we start with a (MULTISIG) transaction that pays the maximum amount Alice would ever need to spend to an output requiring both Alice and Bob to sign to release the coins. Now, after the first minute that Alice has used the service, she signs a transaction spending those coins that were sent to the (MULTISIG) address, sending one unit of payment to Bob and returning the rest to Alice. After the next minute of using the service, Alice signs another transaction, this time paying two units to Bob and sending the rest to herself. Notice these are signed only by Alice, and haven’t been signed by Bob yet, nor are they being published to the block chain. Alice will keep sending these transactions to Bob every minute that she uses the service. Eventually, Alice will finish using the service, At this point Alice will stop signing additional transactions. and Bob will take that last transaction that she sent him, sign it, and publish that to the block chain. All those transactions that Alice signed along the way won’t make it to the block chain. Bob doesn’t have to sign them. They’ll just get discarded.

• we’re actually generating a huge amount of potential double-spends. In practice, however, if both parties are operating normally, Bob will never sign any transaction but the last one, in which case the block chain won’t actually see any attempt at a double-spend.
• What if Bob never signs the last transaction? He may just say, “I’m happy to let the coins sit there in escrow forever,” in which case, maybe the coins won’t move, but Alice will lose the full value that she paid at the beginning.

Lock time: ​

• To avoid this problem, before the micro-payment protocol can even start, Alice and Bob will both sign a transaction which refunds all of Alice’s money back to her, but the refund is “locked” until some time in the future. So after Alice signs, but before she broadcasts, the first MULTISIG transaction that puts her funds into escrow, she’ll want to get this refund transaction from Bob and hold on to it. That guarantees that if she makes it to time t and Bob hasn’t signed any of the small transactions that Alice has sent, Alice can publish this transaction which refunds all of the money directly to her.
• The way it works is that if you specify any value other than zero for the lock time, it tells miners not to publish the transaction until the specified lock time. The transaction will be invalid before either a specific block number, or a specific point in time, based on the timestamps that are put into blocks.

Smart contracts:

• ​The general term for contracts like the ones we saw in this section is ​smart contracts. These are contracts for which we have some degree of technical enforcement in Bitcoin, whereas traditionally they are enforced through laws or courts of arbitration.

Segment 3.4 (Bitcoin Blocks) :

Why transactions are grouped together into blocks? :

• If miners had to come to consensus on each transaction individually, the rate at which new transactions could be accepted by the system would be much lower. Also, a hash chain of blocks is much shorter than a hash chain of transactions would be.This will make it much more efficient to verify the block chain data structure.
• The block chain is a clever combination of two different hash-based data structures. The first is a hash chain of blocks. Each block has a block header, a hash pointer to some transaction data, and a hash pointer to the previous block in the sequence. The second data structure is a per-block tree of all of the transactions that are included in that block. This is a Merkle tree and allows us to have a digest of all the transactions in the block in an efficient way.

• Blocks have a special transaction in the Merkle tree called the “coinbase” transaction. This is analogous to (CreateCoins) in Scroogecoin. So this is where the creation of new coins in Bitcoin happens. It mostly looks like a normal transaction but with several differences:

1- it always has a single input and a single output.

2- the input doesn’t redeem a previous output and thus contains a null hash pointer, since it is minting new bitcoins and not spending existing coins.

3- The output value is the miner’s revenue from the block. It consists of two components: a flat mining reward and the transaction fees collected from every transaction included in the block.

4- There is a special “coinbase” parameter, which is completely arbitrary — miners can put whatever they want in there.

Segment 3.5 (The Bitcoin network) :

In the Bitcoin network, all nodes are equal.

• There is no hierarchy, and there are no special nodes or master nodes. It runs over TCP and has a random topology, where each node peers with other random nodes. New nodes can join at any time, if a node hasn’t been heard from in a while — three hours is the duration that’s hardcoded into the common clients — other nodes start to forget it. In this way, the network gracefully handles nodes going offline.
• Now say you launch a new node and want to join the network. You start with a simple message to one node that you know about. This is usually called your seed node​. You send a special message, saying, “Tell me the addresses of all the other nodes in the network that you know about.” You can repeat the process with the new nodes you learn about as many times as you want. Then you can choose which ones to peer with.

Flooding ​algorithm (gossip protocol):

• If Alice wants to pay Bob some money, her client creates and her node sends this transaction to all the nodes it’s peered with. Each of those nodes executes a series of checks to determine whether or not to accept and relay the transaction. If the checks pass, the node in turn sends it to all of its peer nodes. Nodes that hear about a transaction put it in a pool of transactions which they’ve heard about but that aren’t on the block chain yet. If a node hears about a transaction that’s already in its pool, it doesn’t further broadcast it. This ensures that the flooding protocol terminates and transactions don’t loop around the network forever.

How nodes decide whether or not they should propagate a transaction? :

• The transaction must be valid with the current block chain. Nodes run the script for each previous output being redeemed and ensure that the scripts return true.
• They check that the outputs being redeemed here haven’t already been spent.
• They won’t relay an already-seen transaction, as mentioned earlier.
• By default, nodes will only accept and relay “standard” scripts based on a small whitelist of scripts.
• All these checks are just sanity checks. Well-behaving nodes all implement these to try to keep the network healthy and running properly, but there’s no rule that says that nodes have to follow these specific steps.

It’s possible that nodes will end up with a different view of the pending transaction pool.

• This becomes interesting when there is an attempted double-spend. Let’s say Alice attempts to pay the same bitcoin to both Bob and Charlie, and sends out two transactions at roughly the same time. Some nodes will hear about the Alice → Bob transaction first while others will hear about the Alice → Charlie transaction first. When a node hears either of these transactions, it will add it to its transaction pool, and if it hears about the other one later it will look like a double-spend. The node will drop the latter transaction and won’t relay it or add it to its transaction pool. As a result, the nodes will temporarily disagree on which transactions should be put into the next block. This is called a race condition.this is perfectly okay. Whoever mines the next block will essentially break the tie and decide which of those two pending transactions should end up being put permanently into a block.
• The logic for announcing new blocks, whenever miners find a new block, is almost exactly the same as propagating a new transaction. Validating a block is more complex than validating transactions. In addition to validating the header and making sure that the hash value is in the acceptable range, nodes must validate every transaction included in the block. Finally, a node will forward a block only if it builds on the longest branch, based on its perspective of what the block chain (which is really a tree of blocks) looks like. This avoids forks building up.

Size of the network: ​

• On the high end, some say that over a million IP addresses in a given month will, at some point, act, at least temporarily, as a Bitcoin node. On the other hand, there seem to be only about 5,000 to 10,000 nodes that are permanently connected and fully validate every transaction they hear. This may seem like a surprisingly low number, there is no evidence that the number of fully validating nodes is going up, and it may in fact be dropping.

Storage requirements: ​

• Fully validating nodes must stay permanently connected so as to hear about all the data. The longer a node is offline, the more catching up it will have to do when it rejoins the network. Such nodes also have to store the entire block chain and need a good network connection to be able to hear every new transaction and forward it to peers. The storage requirement is currently in the low tens of gigabytes.fully validating nodes must also maintain the entire set of unspent transaction outputs, which are the coins available to be spent. Ideally this should be stored in RAM, so that upon hearing a new proposed transaction on the network, the node can quickly look up the transaction outputs that it’s attempting to claim, run the scripts, see if the signatures are valid, and add the transaction to the transaction pool. As of mid-2014, there are over 44 million transactions on the block chain of which 12 million are unspent. Fortunately, that’s still small enough to fit in less than a gigabyte of RAM in an efficient data structure.

Lightweight nodes:

• ​In contrast to fully validating nodes, there are lightweight nodes, also called thin clients or Simple Payment Verification (SPV) clients. In fact, the vast majority of nodes on the Bitcoin network are lightweight nodes. These differ from fully validating nodes in that they don’t store the entire block chain. They only store the pieces that they need to verify specific transactions that they care about. If you use a wallet program, it would typically incorporate an SPV node. The node downloads the block headers and transactions that represent payments to your addresses. SPV nodes can only validate the transactions that actually affect them. So they’re essentially trusting the fully validating nodes to have validated all the other transactions that are out there.
• The cost savings of being an SPV node are huge. The block headers are only about 1/1,000 the size of the block chain. So instead of storing a few tens of gigabytes, it’s only a few tens of megabytes. Even a smartphone can easily act as an SPV node in the Bitcoin network.

Segment 3.6 (Limitations and improvements) :

There are many constraints hard-coded into the Bitcoin protocol,

• they were chosen when Bitcoin was proposed in 2009, before anyone really had any idea that it might grow into a globally-important currency. Among them are the limits on the average time per block, the size of blocks, the number of signature operations in a block, and the divisibility of the currency, the total number of Bitcoins, and the block reward structure. The limitations on the total number of Bitcoins in existence, as well as the structure of the mining rewards are very likely to never be changed because the economic implications of changing them are too great.
• Some initial design choices don’t seem quite right with the benefit of hindsight. Chief among these are limits that affect the throughput of the system. How many transactions can the Bitcoin network process per second? This limitation comes from the hard coded limit on the size of blocks. Each block is limited to a megabyte which means we’re left with about 7 transactions per second, which is all that the Bitcoin network can handle. So how does seven transactions per second compare?Visa’s network is said to handle 10,000 transactions per second during busy periods. Even Paypal, can handle 100 transactions per second at peak times.
• Another limitation that people are worried about in the long term is that the choices of cryptographic algorithms in Bitcoin are fixed. There are only a couple of hash algorithms available, and only one signature algorithm (ECDSA) over a specific elliptic curve called (secp256k1). There’s some concern that over the lifetime of Bitcoin this algorithm might be broken. Cryptographers might come up with a clever new attack that we haven’t foreseen which makes the algorithm insecure. The same is true of the hash functions.

Changing the protocol:

• In practice, it’s impossible to assume that every node would upgrade. Some nodes in the network would fail to get the new software or fail to get it in time. The implications of having most nodes upgrade while some nodes are running the old version depends very much on the nature of the changes in the software.

Hard forks:

• ​One type of change that we can make introduces new features that were previously considered invalid.What happens when most nodes have upgraded, but some have not? soon the longest branch will contain blocks that are considered invalid by the old nodes. So the old nodes will go off and work on a branch of the block chain that excludes blocks with the new feature. This type of change is called a hard forking change because it makes the block chain split. Every node in the network will be on one or the other side of it based on which version of the protocol it’s running.

Soft forks: ​

• A second type of change that we can make to Bitcoin is adding features that make validation rules stricter. That is, they restrict the set of valid transactions or the set of valid blocks such that the old version would accept all of the blocks, whereas the new version would reject some. this can avoid the permanent split that a hard fork introduces. Consider what happens when we introduce a new version of the software with a soft forking change. The nodes running the new software will be enforcing some new, tighter, set of rules. Provided that the majority of nodes switch over to the new software, these nodes will be able to enforce the new rules. There is a risk that old miners might mine invalid blocks because they include some transactions that are invalid under the new, stricter, rules. But the old nodes will at least figure out that some of their blocks are being rejected, even if they don’t understand the reason.Furthermore, if their branch gets overtaken by the new miners, the old miners switch to it. That’s because blocks considered valid by new miners are also considered valid by old miners.
• (Pay-to-script-hash) was not present in the first version of the Bitcoin protocol. This is a soft fork because from the view of the old nodes, a valid pay-to-script-hash transaction would still verify correctly. As interpreted by the old nodes, the script is simple — it hashes one data value and checks if the hash matches the value specified in the output script. Old nodes don’t know to do the (now required) additional step of running that value itself to see if it is a valid script. We rely on new nodes to enforce the new rules, i.e. that the script actually redeems this transaction.
• It’s also possible that new cryptographic schemes could be added by a soft fork. We could also add some extra metadata in the coinbase parameter that had some meaning. Today, any value is accepted in the coinbase parameter. But we could, in the future, say that the coinbase has to have some specific format.
• Adding new opcodes to Bitcoin, changing the limits on block or transactions size, or various bug fixes like Fixing the bug where the (MULTISIG) instruction pops an extra value off the stack, would actually require a hard fork. That explains why, even though it’s an annoying bug, it’s much easier to leave it in the protocol and have people work around it rather than have a hard fork change to Bitcoin.

End of lecture 3.

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