Bitcoin and Cryptocurrency

Technologies
 History of Blockchain
• The very primitive form of the blockchain was the
hash tree, (Merkle tree).
• This data structure was patented by Ralph Merkle in
1979
• functioned by verifying and handling data between
computer systems.
• In a peer-to-peer network of computers, validating
data was important to make sure nothing was altered
or changed during transfer.
• It also helped to ensure that false data was not sent.
• In essence, it is used to maintain and prove the
integrity of data being shared.
• In 1991, the Merkle tree was used to create a “secured
chain of blocks” — a series of data records, each connected
to the one before it.
• The newest record in this chain would contain the history
of the entire chain. Thus, the blockchain was created.
• In 2008, Satoshi Nakamato conceptualized the
distributed blockchain.
• It would contain a secure history of data exchanges,
utilize a peer-to-peer network to time stamp and verify
each exchange, and could be managed autonomously
without a central authority.
• This became the backbone of Bitcoin.
• And thus, the blockchain as well as the world of
cryptocurrencies was born.
Homework for 31.11.19
• Get a picture of Satoshi Nakamato.
 Key Features of Blockchain
1. Blockchain keeps a record of all data exchanges,
referred to as a “ledger” in the cryptocurrency world.
• Each data exchange is a “transaction”.
• Every verified transaction is added to the ledger as a
“block”
2. It utilizes a distributed system to verify each
transaction
• a peer-to-peer network of nodes
3. Once signed and verified, the new transaction is
added to the blockchain and can not be altered.
• The (Private , Public) Key pairs are combined for a digital
signature.
• Your public key is how others are able to identify you.
• Your private key gives you the power to digitally sign and
authorize different actions on behalf of this digital identity
when used with your public key.
• In the cryptocurrency concept, this represents your wallet
address (public key)
• Your private key is what let’s you authorize transfers,
withdrawals, and other actions with your digital property like
cryptocurrencies.
• A cryptocurrency (or crypto currency) is a digital asset
designed to work as a medium of exchange using
cryptography to secure the transactions and to control the
creation of additional units of the currency.
Homework 31.11.19
• Differentiate Conventional vs Digital Currency
Why use Cryptocurrency?
 Risks Involved
• Hackers: Targets for highly sophisticated hackers, who have
been able to breach advanced security systems.
• Fewer protections: If you trust someone else to hold your
cryptocurrencies and something goes wrong, that company
may not offer you the kind of help you expect from a bank or
debit or creditcard provider.
• Cost: Cryptocurrencies can cost consumers much more to use
than credit cards or even regular cash, often due to price
volatility.
• Scams: Fraudsters are taking advantage of the hype
surrounding virtual currencies to cheat people with fake
opportunities.
• Lack of Transparency. The anonymous nature of
cryptocurrencies make transparency and accountability
difficult for consumers seeking to ensure the safety of their
investments.
Types of Cryptocurrency
 Bitcoin
• Both a cryptocurrency and an electronic payment
system
• Satoshi Nakamoto in 2008
• First decentralised payment network
• System is peer-to-peer
• 21 million bitcoins
• Completely Open source
• 1BTC = $1258.48
 A Simple Cryptocurrency
GoofyCoin
• The simplest cryptocurrency.
• There are just two rules of GoofyCoin.
1. A designated entity, Goofy, can create new coins
whenever he wants and these newly created coins belong
to him.
2. 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.
• To create a coin, Goofy generates a uniqueCoinID that he’s
never generated before and constructs the string
“CreateCoin [ uniqueCoinID ]”.
• He then computes the digital signature of 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.
Transaction
Eg: Goofy wants to pay money to Alice, he will:
a. Take a hash pointer to that coin
b. Make a statement that he wants to pay the coin to
Alice. He refers to Alice through her public key
c. The statement is signed by Goofy.
d. Now Alice owns the coin and can prove it. She can
present the following data structure, which is validly
signed by Goofy and points to a coin that Goofy
owned.
e. Alice can go on and use the coin however she wants,
for example can make a payment to Bob using the
same datastructure, and so on.
• To summarize, the rules of GoofyCoin are:
1. Goofy can create new coins by simply signing a
statement that he’s making a new coin with a unique
coin ID.
2. 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)
3. 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.
Double spending problem
• This a big security problem with GoofyCoin
Goofy makes a transaction to pay Alice
Alice makes a transaction to pay Bob
Then, Alice makes another transaction to Chuck, sending the
same coin
• Both the last transactions are signed by Alice.
• If Chuck doesn't know that Alice has already sent the money
to Bob, he will think that he's the owner.
• Both the claims of Bob and Chuck to be the owner are equally
valid, since they can follow the chain till Goofy.
• That's a problem because coins are not supposed to work that
way.
• This is called double-spending attack, because Alice is
spending the same coin twice.
ScroogeCoin
Concepts are like GoofyCoin, except it will solve the
double-spending problem in a particular way.
The key idea is that Scrooge is going to publish the history
of all the transactions in a blockchain, that will be
digitally signed by Scrooge.
So anyone can check the data blocks.
Each block will have one transaction in it and a hash
pointer to the previous block in the history.
• Scrooge will take the hash pointer, which represents this
entire structure, digitally sign it and publish it.
• Now anybody can verify that Scrooge really signed this
hash pointer.
• they can follow this chain all the way back and see the
entire history of all the transactions of ScroogeCoin.
Solution to double-spending problem
• The history allows us to detect double-spending.
• Assume Alice owns a coin, and she tries to pay that coin
both to Bob and to Charlie.
• Charlie will notice that something is wrong, because he can
look into the history and see that Alice already paid that
coin to Bob.
• then everyone can see that that's a double spending and
they'll be able to reject it.
Transactions types
• In ScroogeCoin there are two kinds of transactions:
1. CreateCoins transaction
2. PayCoins transaction
CreateCoins transaction: it is possible to create multiple
coins in one transaction.
• Every coin will have a serial number, a value and an owner
(a public key of the initial owner).
• So this transaction type creates a bunch of new coins and
assigns them to people as initial owners.
• Each coin will have a unique ID
• A CreateCoins transaction is always valid, because Scrooge
said so.
• If Scrooge puts this into the history, which he signs, then it's
valid by definition.
PayCoins transaction: consumes some coins and
destroys them, and creates new coins of the same total
value, but which might belong to different people.
• So, we will have a list of the coins that are going to be
destroyed.
• Then there's a creation of a bunch of new coins, whose
total value must add up to the total of destroyed coins.
• Just like before in the CreationCoins transaction each
one has an Id, a value and a owner.
• This transaction must be signed with all signatures of
the owner of one of the destroyed coins.
• The rules of ScroogeCoin say that PayCoins transaction is
valid if four things are true:
1. the consumed coins are valid: they were really created in
previous transactions
2. double-spending check: the consumed coins were not
already been spent in previous transactions
3. the total value of the newly created coins is equal to the
total value of the destroyed coins
4. all the digital signature of previous owners are valid
• In this case Scrooge will accept it and insert this block into
the blockchain, so everyone can check it.
• In this scheme the coins are immutable, they are just created
with a specific owner and then destroyed.
• But every operation is still possible.
Eg: To subdivide a coin, is enough to create a new transaction
that consumes a coin and produces two new coins of the same
total value.
Centralization Problem
Scrooge can be a problem. Scrooge says don't worry, I'm honest.
• But if Scrooge starts misbehaving, then we're going to have a
problem. Or if Scrooge just gets bored of the whole ScroogeCoin
scheme and stops doing the things that he is supposed to do, then
the system won't operate anymore.
• The problem we have here is Centralization: although Scrooge
is happy with the system, the users of it might not be.
• In order to improve on ScroogeCoin is necessary to
decentralize the system.
• In order to do that, we need to figure out how to provide the
same services of Scrooge, but in a decentralized way, in which
no particular party is the only trusted one.
Decentralization
• An important concept, not just for Bitcoin.
• Plays an important role for different digital technologies.
• Almost no system is purely decentralized or purely
centralized.
Eg: email.
oIt is a decentralized system, fundamentally.
oIt's based on a standard spaced protocol, SMTP.
oBut, at the same time, there is a dominance of a few
different web mail providers, which are a sort of
centralized service providers.
Bitcoin decentralization
1. Who maintains the transactions ledger?
2. What is the authority that decides 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?
• Bitcoin decentralization, refers to first three aspects.
• There are other things beyond the protocol such as Bitcoin
exchanges (conversion of Bitcoins to other currencies), wallet
softwares and a variety of other services provided by specific
companies.
• So, even if the underlying protocol is decentralized, these
services, developed on top of it, may be centralized or
decentralized.
Bitcoin network
• The Bitcoin protocol works on a peer-to-peer network,
where all the users are network nodes.
• To become part of the network , download a Bitcoin
client that can run on every laptop or PC with enough
disk space.
• Currently there are several thousand of Bitcoin nodes.
• this really resembles a peer to peer decentralized system.
• Bitcoin has more components.
Bitcoin mining, that requires a very high capital cost.
It's a consequence of how the system evolved.
• So, now there's a high concentration of power in the
Bitcoin mining ecosystem, and the community
frequently sees this as quite undesirable.
• Finally there's a third aspect: updates to the software.
• While one can conceptually imagine that every Bitcoin
node will look at the Bitcoin specification, it differes in
practice.
• In fact, the community trusts the core developers.
• So they have a lot of power when it comes to
determining what Bitcoin software each of these nodes
will run on their computer.
Distributed consensus
• Key to the operation of any distributed database is a
mechanism to ensure that the nodes on the network verify
the transactions, and agree with their order and existence on
the ledger — a mechanism called consensus.

• The key technical problem to solve in building a distributed

e‐cash system is achieving distributed consensus.
Distributed consensus applications
• Consider a distributed consensus protocol and we are able to
use it to build a massive distributed key-value store, that
maps arbitrary keys or names to arbitrary values. Then we
could use it for many applications, like:
distributed domain name system: a mapping between human
understandable domain names to IP addresses
public key directory: a mapping between user email
addresses to their public keys
stock trades: the distributed database would keep track of
who's transferred goods of which stock to whom.
• There are n nodes that each have an input value. Some of
these nodes can be faulty or malicious.
• A distributed consensus protocol has the following two
properties:
1. the protocol should terminate with all honest nodes in
agreement on the value.
2. the output value cannot be arbitrary, but must match
with one of the input values proposed by at least one of
the correct nodes.
Bitcoin transaction
• Bitcoin is a peer-to-peer system.
• So, when Alice wants to pay Bob, she's broadcasting the
transaction to all of the Bitcoin nodes belonging to the peer-
to-peer network.

The transaction is going to have:

• Alice's signature used by other nodes to check the message origin
• Bob's public key, which also accesses the address at which he wants
to receive bitcoins
• a hash of the previous transaction. This is a way for Alice to link this
transaction to her receipt of this coin from someone else previously
• When Alice broadcastes the transaction to all of the Bitcoin peer-to-
peer nodes:
• It is not necessary that Bob listens the network to receive
the funds.
• The bitcoins will be his, whether or not he's running a
node on the network.
• The network nodes wants to reach consensus on which
transactions were broadcasted, and the order in which
these transactions happened.
How distributed consensus could work in Bitcoin
At any given time:
• All the nodes in the peer-to-peer network would have a
sequence of transactions blocks that they've reached
consensus on.
• In fact, for optimization purposes the transactions are
organized into blocks and linked together to form a
blockchain.
• Each node would have a set of outstanding transactions that it has
heard about.
• The consensus has not happened to them, yet.
• So each node might have a slightly different version of these
outstanding transactions.
• suppose three nodes in the system, each of whom has an input:
the set of outstanding transactions that it heard about.

• They execute together some consensus protocol, when it

succeeds, it is possible to select any valid block and add it to the
blockchain, even if it's a block proposed by only one node.
Problems with this kind of system
• Taking the traditional theory of distributive consensus and
applying that to cryptocurrency, we will get above kind of
systems.
• This has some similarities wth how Bitcoin works, but it's not
exactly the same.
Some hard technical problems, above systems can face:
 Nodes might crash or might be malicious
 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 due to poor Internet
connectivity
 There will be a lot of latency in the system, because
everything happens over the Internet and there's no single
data center.
 One particular consequence of this high latency, is that there is
no notion of global time.
 This means that not all nodes can agree to a common ordering
of events, simply based on observing timestamps.
Constraints in distributed algorithm
• Especially the last problem, puts serious constraints on what
sorts of algorithms can run into a consensus protocol.
• Byzantine generals problem: under some conditions, which
include the nodes acting in a deterministic manner,
consensus is impossible, even with a single faulty process.
• Paxos problem: under certain conditions, even if rare ones,
the protocol can get stuck and fail to make any progress
• Bitcoin violates a lot of the assumptions of the previous
impossibilities problems.
• Because of that, consensus in Bitcoin, ironically, works better
in practice than in theory:
Bitcoin introduces the idea of incentives.
• Because Bitcoin is a currency, it is possible to use it to give
incentives to the participants for acting honestly.
it embraces the notion of randomness: consensus happens
over a long period of time, about an hour in the practical
system.
• As time goes on, the probability that a transaction is valid
goes up higher and higher. And the probability that you're
wrong in making an assumption about a transaction goes
down exponentially.
• That's why Bitcoin is able to get around these traditional
impossibility results on distributed consensus protocols.
• How it is possible to reach consensus without identity
through the blockchain?
Nodes and identities
Nodes without persistent identity
• Bitcoin nodes don't have any persistent long term identities.
• This is another difference from how traditional distributive
consensus algorithms operate.
• If nodes had identities, it would make things a lot easier:
• it would be possible to include in the protocol specific
references to nodes IDs.
• the system would be more secure. If nodes were identified
and weren't able to create new identities, we could make
assumption on malicious nodes and try to eliminate them
from the network, to be sure that at least 50% of them are
not malicious
Why Bitcoin nodes don't have identities?
• Reasons:
1. Bitcoin protocol is a peer-to-peer decentralized system.
So there is no central authority that assignes identities to nodes
and verify that they're not creating new nodes.
Sybils attack: malicious nodes could create a lot of copies of
nodes all controlled by them to look like there are a lot of
different participants. When in fact, all those pseudo
participants are really controlled by the same adversary.
2. Pseudo-anonimity is a goal of Bitcoin, so it doesn't
assign an immutable identity even if it could be possible
also in a decentralized system.
So an adversary could trace the transactions and connect them
to an "address", but it would be harder to understand who is
really making that transactions.
Consensus algorithm
• A simplified version of consensus algorithm for Bitcoin:
• When Alice wants to pay Bob, she creates a transaction and
broadcasts it to all of the nodes.
• Each node is constantly listening to the network and
collecting a list of transactions not yet inserted into the
blockchain.
• at some point, one of these nodes is chosen randomly to
propose the next block.
• It will put in the new block a bunch of transaction and add it to the
blockchain. This node can be honest, or malicious and try to insert
some invalid transactions. For example it could insert transaction
with non-valid signature or with coins already spent.
• the other nodes will accept this block or reject it, by either
including the hash of this latest block in their next block or
ignoring it.
• The block is accepted only if all the transaction in it are valid.
Why the consensus algorithm works?
• See how can a malicious adversary try to subvert this
process. If Alice is a malicious attacker, she could try to:
1. steal Bitcoins belonging to another user. She is not able
to do this, because she cannot forge someone else's
signature.
2. act against another user Bob.
• Eg: Alice could try not to insert any Bob's transactions into new
blocks. But there will be other honest nodes that will gather
Bob's transaction into a new block.
3. try to spend some coins twice (double-spending attack).
 Bitcoin transactions
• Transactions are Bitcoin’s fundamental building block.
• 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.
• transaction would say something like “we’re moving 17
coins from Alice to Bob”, and it will be signed by Alice.
That’s all the information about the transaction that’s
contained in the ledger.
• The downside : 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?
• The downside : 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
• Because of these downsides, Bitcoin doesn’t use an account-
based model. Instead, Bitcoin uses a ledger that just keeps
track of transactions similar to ScroogeCoin.
• Bitcoin uses a ledger that just keeps track of transactions.
• In this model the transactions explicitly specify a number of
inputs and a number of outputs (two arrays).
• In addition, each transaction has a unique identifier.
• the first transaction has no input, because it corresponds to
new currency being created. It has an output of 25 Bitcoins
going to Alice. It's a creation transaction, so no signature is
needed. It's identified uniquely by Id 1.
• then Alice wants to send some money to Bob. She refers
explicitly to the transaction 1 where these coins comes from.
So the input of this transaction will be the output index 0 of
the first transaction. Then this transaction has two outputs:
17 Bitcoin going to Bob, 8 Bitcoin going back to Alice. The
idea is to fully consume the output of the previous
transaction, sending the exceeding money back to herself,
this operation is called change address.
• then Bob does transaction 3 towards Carol and himself
referring to the output index 0 of transaction 2. And Alice
tries to make transaction 4 using the money of transaction 2
index 1.
Check transaction validity
• In this case it's easier to check the validity of last
transaction: it is enough to check transaction 2, output 1,
and verify that there's enough money there and that this
money wasn't used already.
• Now it enough to follow just one hash pointer to a previous
transaction to figure out whether or not there is enough
money to cover the desired outputs in the new transaction.
Transaction has three parts:
• metadata: there are some housekeeping information.
size of the transaction -dimension in bytes
number of inputs and outputs.
hash of the transaction- a unique ID for using hash pointers.
lock_time parameter.
• inputs: array of inputs of the same form. Every input refers
to a specific previous transaction, or specifically to its hash
and the index of output from the previous transaction the
current is referring to. Then there's the signature, which is
necessary to prove to be the owner of the previous
transaction output.
• outputs: array of outputs of the same form. The sum of all
output has to be less than or equal to the sum of all inputs.
Each output must go to a specific public key.
Bitcoin Scripts
• What is Bitcoin scripting language and Bitcoin scripts.
• Why a script is used in the transaction output instead of a
single 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.
The main properties of this language:
1. Stack-based: it is based on a stack.
• There are no variables, no conditional statements.
• So all the operations are always executed exactly once in linear
manner.
• operations are applied to the member on the top of the stack
following the schema FIFO (First in First Out).
2. Non Turing complete: It doesn’t have the ability to compute
arbitrarily powerful functions.
• There are no conditional statements and no loops.
• Just looking at a script, it is possible to understand how long it
might take based on the number of instructions.
• This because the miners have to run the scripts submitted by users
directly in the transactions. So they must not have the ability to
submit scripts that might have an infinite loop and might run
forever.
• There are only two possible outcomes when a Bitcoin
script is executed.
1. It either executes successfully with no errors, in which
case the transaction is valid.
2. 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 is very small.
• There’s only room for 256 instructions, because each oneis
represented by one byte.
• Of those 256, 15 are currently disabled, and 75 are reserved.
• Two types of instructions:
1. Data instructions
2. OP_CODE.
• The data instruction are simply containing some value and
are surrounded by angular brackets (i.e. <data>).
• The OP_CODE are specific operations belonging to Bitcoin
Scripting language that acts on the value on the top of the
stack and put their result also on the top of the stack.
• The most common OP instructions are the following:
1. OP_DUP: duplicates the data on the top of the stack
2. OP_HASH160: computes the hash of the data on the top of
the stack and replace it with the result
3. OP_EQUALVERIFY: verifies if the first two data on the
top of the stack are equals. If so, these two data are
removed
4. OP_CHECKSGN: controls the digital signature using the
public key and returns true or false whether the signature
verifies or not
The most common script: transaction validation
• The most common script in Bitcoin: the one used to
redeem a transaction.
• This script is formed concatenating the scriptSig in the
transaction input, with the scriptPubKey in the transaction
output.
• When a transaction has to be validated, the two scripts get
concatenated together.
• This script checks the reference to the previous transaction to
see if it can be used to transfer the money of the current
transaction.
• If the resulting script runs without any errors, the transaction
is considered valid.

The first two instructions in this script are

simply data instructions:
• the signature of the sender
• the public key used to generate that
signature
• This data are just pushed on the stack without doing any
operations.
• OP_DUP: we duplicate the public key on top of the stack
• OP_HASH160: computes the cryptographic hash of the
public key and puts it on the top of the stack
• Now there's a new value pushed onto the stack:
• the hash of the public key specified by the sender
• There the last two operations are applied:
• OP_EQUALVERIFY: verifies if the two hashes on the top of
the stack are equals. If so they are removed. If not, an error is
returned and the transaction is not valid.
• OP_CHECKSIG: now we have the public key and the
signature left on the stack. This last operation checks if the
public key corresponds to the signature, so if the signature is
valid. It returns true if the signature is valid, false otherwise.
Script Properties
• The main properties of Bitcoin language and scripts:
• Every Bitcoin script can only produce two outcomes.
• It can either execute successfully or return an error.
• In the Transaction validation, if there's any error while the
script is executing, the whole transaction will be invalid and
shouldn't be accepted into the blockchain
• Bitcoin scripting language is very small, there's only room
for 256 instructions, since each one is given by one byte.
• 15 of them are currently disabled and 75 are reserved, so
actually they don't have any meaning and could be assigned
later on.
• Bitcoin scripting language includes instructions to manage
basic arithmetic, basic logic, throwing errors and
cryptography management such as hash functions, signature
verification.
Sophisticated Bitcoin Scripts
1. Checking Multiple Signatures :
• CHECKMULTISIG: to check multiple signatures with one
instruction.
• In this case it is necessary to specify n public keys and a
threshold t.
• This instruction will execute without errors if there are at least t
valid signatures belonging to these n public keys.
2. Proof-of-burn
• It is actually a script that can never be redeemed.
• If you have a proof-of-burn, it's provable that those coins have
been destroyed, there's no possible way for them to be spent.
• To implement a proof-of-burn it's necessary to insert an
OP_RETURN instruction, which throws as soon as it is reached,
no matter what instructions preeceded it.
• The data that comes after OP_RETURN are ignored, so this
is an opportunity to specify arbitrary data in a script that will
remain in the blockchain.
• This kind of script has mainly two purposes:
1. insert arbitrary data into blockchain,
Eg: timespamp a document and prove that you knew some
data at a specific time.
• In this case it is possibile to create a very low value Bitcoin
transaction that's proof-of-burn. So you can destroy a very
small amount of currency, and in exchange write something
into the blockchain, which should be kept forever.
2. some alternate coins systems, can promote their new
currencies forcing people to destroy Bitcoin in order to gain
coins in the new system.
3. Pay-to-script-hash
• To use Bitcoin, a sender must specify a script exactly.
• A common consumer, wouldn't be able to specify it, if for
example he is ordering something online and a MULTISIG
script is required. As a consumer, he just want to send the
money using a simple address.
• In response to this problem, there's a feature in Bitcoin
that lets the sender specify just a hash of the script that is
needed to redeem the coins.
The script acts as follows:
1. The sender specifies the hash of the script and it is put
on the top of the stack
2. The receiver specifies as a data value, the value of the
script corresponding to the previous hash
3. The algorithm checks if the hash of this data
corresponds to the one specified by the sender
4. If the two hashes match, the top data value from the
stack is reinterpreted as instructions, so it's executed a
second time as a script.
• This pay-to-script-hash is an alternative to make Bitcoin
payments to the standard way, which is called pay-to-public-
key.

• This is a useful feature that was not available in the first

version of the protocol.

• It removes complexity from the sender, and has an additional

efficiency gain since the output scripts are as small as
possible with pay-to-script-hash: they just specify a hash,
and all of the complexity is pushed to the input scripts.
 Applications of Bitcoin scripts
1. Escrow transactions
• The one advantage of having a scripting language, since it's
more complicated than just using public keys.
Consider:
• Alice wants to buy some things from Bob
• she wants to pay with Bitcoins and Bob has to send physical
goods to Alice
• Alice doesn't want to pay until she receives it. And Bob
doesn't want to send it, until he has received the payment
• Solution to this problem in Bitcoin system:
Alice creates a MULTISIG transaction that requires two or
three people to sign in order to redeem the coins.
• Alice, Bob and Judy - a judge, who will come into play only if
there's any dispute
Alice signs the transaction redeeming some coins that she
owns. At this point these coins are held in escrow between
Alice, Bob, and Judy and any two of them can specify where
the coin should go.
At this point Bob can safely send the goods to Alice and sign
the transaction that releases money to him.
If the goods arrive and corresponds to what Alice expected,
she can release the money towards Bob signing the
transaction. The money will be sent to Bob without the need
of Judy's intervention.
This happens if both are honest.
Otherwise Alice could ask for her money back. And maybe
Bob doesn't agree to sign the transactions that releases the
money towards Alice.
• Then it's Judy's turn to decide who's right and sign the
transaction that releases money either towards Alice or Bob.
In both cases, since only two signatures are required, the
money will be sent towards one of them.
2. Green addresses
• Imagine that Alice wants to pay Bob, who's offline. Bob can't
check the blockchain to see if the transaction that Alice is
sending is valid.
• This can happen for any reason.
• Normally a transaction is valid when its block is followed by
other six blocks.
• This can take up to an hour.
• To solve the problem of the recipient not being able to access the
blockchain, it is necessary to introduce a third party: the bank.
• Alice can ask her bank to transfer money to Bob. They will
deduct some money from Alice account and make a transaction
to Bob from one of their green addresses.
• The money to Bob will come directly from a bank controlled
address, with a guarantee of no double spending.
• If Bob trusts the bank, he can accept the transaction as soon as
he receives it. The money will eventually be his when it's
confirmed in the blockchain.
3. Efficient micro-payments
• Alice is a customer who wants to pay Bob a low amount of
money for some service.
• It would be very inefficient to create a Bitcoin transaction
for every minute of conversation, there will be too many
transactions with low value and too many fees.
• A solution is to combine all these small payments into one
big payment at the end. To do this we can:
start with a MULTISIG transaction that pays the maximum
amount Alice would ever need to spend, that requires both
Alice and Bob signatures to release the coins
after the first minute of conversation, Alice signs the
transaction sending one coin to Bob and returning the rest to
herself.
after another minute, Alice signs another transaction, paying
two coins to Bob and the rest to herself. At this point Bob
hasn't signed anything, yet.
Alice repeats this procedure every minutes of usage. These
transactions aren't published on the blockchain, since Bob
signature is missing.
When Bob wants to get his money, he can sign the last
transaction and publish it on the blockchain. He will receive
the money he deserves, and the remaining will be sent back
to Alice. The other transactions will never be inserted into
the blockchain.
It is impossible to redeem two different transactions
generated by Alice, since they are all technically double
spends of the same beginning transaction. If both parties are
operating normally, Bob will never sign any transaction but
the last one, so the blockchain won't actually see any attempt
of double-spending.
4. Lock time
• A problem of the micro-payments protocol :
Bob will never signs any of the transactions, so all the
money that Alice first sent to the multisign address remains
blocked.
• Alice can have her money back using another feature called
Lock Time.
Before the micro-payment protocol starts, Alice and Bob
will both sign a transaction which refunds all of Alice's
money back to her, but is locked until some time in the
future.
So before Alice signs the first transaction for the first minute
of service, she requires this refund transaction from Bob.
If a certain time T is reached and Bob hasn't signed any of
the small transactions that Alice sent, she can publish this
transaction which refunds all of the money directly to her.
 Bitcoin blocks
• Reasons for transactions grouped together into blocks:
1. a block creates a single unit of work for miners, that is
bigger than the individual transaction size. Doing hash and
add metadata for every transaction would me too much
expensive.
2. the presence of blocks makes the hash_chain shorter, since
we only need one block for a large number of transactions.
• So it will also be easier to verify the block chain data
structure.
Blockchain data structure
• The blockchain is the combination of two different hash-
based data structures:
hash pointers between one block and the previous one
inside every block the transactions are organised with a
Merkle tree (hash tree). To prove that a transaction is inside
one block will be enough to provide the path inside the tree.
Block structure
• A block consists of:
1. block header: contains all metadata for the block.
• The header is the most important part for the mining puzzle.
• The header also contains the nonce that the miners can
change to solve the puzzle and an indication of how difficult
was to find the block.
• Finally there's a reference to the block body, namely the hash
of Merkle tree root.
• So the header contains all the information that are hashed
during mining.
2. Merkle Tree of transactions: a long list of transactions
organised inside this tree.
• Inside this tree there's a special transaction: the coinbase
transaction.
• This is where the creation of new coins and Bitcoin
happens.
• It almost looks like a normal transaction, with a value
corresponding with the current Bitcoin reward, plus all the
block transactions fees.
• The difference is that there's no reference to an output of a
previous transaction, since it's a creation of new coins.
• There's also a special coinbase parameter, that can be
populated with some arbitrary data.
• There's no actual limits on what miners can put in there.
Block display
• To understand blocks structure :
check the graph of transactions
see which transactions redeem which other transactions
look for transactions with complicated scripts
check block structure and the link between blocks
• Available on websites that provide this feature
Eg: blockchain.info and many others
Bitcoin Network
• It's a peer-to-peer network, where all nodes are equal.
There's no hierarchy, centralization, special nodes or master
nodes.
• It runs over TCP and has a random topology: nodes peered
randomly with other nodes.
• New nodes can come at any time.
• It is possible to download the Bitcoin client today, and start a
new Bitcoin node with the same rights and capabilities as
every other existing node.
• The network is very dynamic, nodes are coming and going
all the time.
• Although there's no explicit way to leave the network, if a
node doesn't communicate for three hours, other nodes start
to forget it.
• If a new node wants to join the network, it sends a message
one existing node that's already on the network, called
its seed node.
• The message will say “tell me all the peers that you have”.
• Then the new node proceeds asking the same to the nodes
connected to the first one, and so on.
• At the end of the iteration it will have a list of peers to make
connections with.
• The new node chooses a number of peers to connect to from
the list and become a full operating node.
Network purposes
• The network maintains the blockchain, and to publish a
transaction the entire network needs to hear about it.
• There's a simple flooding algorithm to make this happen,
sometimes called gossip protocol.
• Suppose that node 4 hears about new transaction. To spread
gossip, someone tries to tell the news to many people as he
can.
• Node 4 will do the same, notifying the transaction to all the
nodes it is connected to (nodes 2 and 3).
• Each node maintains a list of all transactions he’s heard
about that haven't been put into the blockchain, yet.
• if a node receives a notification of a transaction he’s already
heard about, he won’t spread the transaction again. So, when
all the nodes know the transaction, the spread process stops.
• Besides checking double heard transactions, a node can
decide not to propagate new transactions he’s never heard
about before.
• Node checks if a transaction is valid or not running the
validation script we’ve seen before.
• He will refuse transactions that tries to redeem coins already
spent or nonstandard transaction formats.
• The double spending attempt can be identified even before
one of the transaction is inserted into blockchain.
• If a node receives two unconfirmed transactions that try to
spend the same money, he won’t spread the second one.
Full nodes and Lightweight nodes
• To be a fully-validating node, it’s necessary to stay
permanently connected and hear about all data.
• The longer one is offline, the more catch up it will be
necessary to do to hear about all the missed transactions.
• In addition, it’s important a good network connection and a
huge storage (over 100GB).
• Being a full node also requires to store the unspent
transactions in RAM to be able to run scripts on them.
• This requires around 1GB of RAM.
• Instead of being a fully validating node, there are lightweight
nodes (thin clients or simple payment verification clients).
• This is the vast majority of nodes on the Bitcoin network.
• The difference is that these nodes aren't attempting to store
the entire blockchain.
• They only store the pieces they need to verify some specific
transactions they care about.
How to store and use Bitcoins
• In order to spend a Bitcoin it is necessary to know two main
kinds of things:
1. Some information stored on the public blockchain: the identity
of the coins.
• It is not necessary to store this information locally, since it is
always possible to retrieve it from the blockchain.
2. The secret key of the owner of the Bitcoin.
• It is really important to store and manage the keys, since they
cannot be retrieved in any way from the network. So the
money would be lost.
• When figuring out how to store and manage keys, there are 3
goals to keep in mind:
Availability: be able to spend your own money when you want to
Security: nobody else can spend your money
convenience: the process must be relatively simple and don't cost
too much
Possible approaches
• One of the simplest way of storing the keys could be
put them on a local device, such as a computer, a
phone or something similar.
• convenience: the money could be accessible just pushing
a button
• availability: if the device crashes or you lose it, the
money is lost with it
• security: if someone manages to break into the device the
security is broken. It's just as safe as carrying money in
the pocket.
• To avoid these problems, we would typically use a
wallet software.
Hot and Cold Storage
• Hot storage is online: examples of hot storage is using a
local device or an online wallet to store the keys.
• There's a high availability and convenience, but the
security is not so strong.
• Cold storage is offline: it is not connected to the Internet
and it's more secure.
• It's similar to keep the money in a safe, instead that in a
wallet.
• The security is higher but both the availability and
convenience are lower.
• It wouldn't be possible to manage Bitcoins only with a cold
storage.
• But it can be used together with a hot one to store the
majority of Bitcoins.
• So if we want to use them both, we will need to have
separate keys and addresses for the coins.
• In this way, the coins in the cold storage would be safe if the
hot storage is compromised.
Moving Bitcoins between hot and cold storage
• To move coins back and forth between the two sides, both
must know the address the other one is using.
• So each side knows its own secret key and the receiving
address of the other side.
• Even if the cold storage is offline most of the time, it
sometimes needs to connect to transfer money and to check
if its balance is changed.
• How do we manage the hot and cold storage addresses?
• For privacy and security reasons we would like to change
receive address every time.
• So, whenever there's a transfer of coins from the hot side to
the cold side, we would like to use a fresh cold address.
• How can the hot wallet know the new address even if the
cold side is not online?
• A simple solution could be to have the cold side generate a
whole bunch of addresses all at once.
• The hot wallet could use one of them per transaction. When
the cold side reconnect could send new addresses if
necessary.
• But there could still be problems, for example the hot wallet
could run out of addresses.
Hierarchical key generation
• A more complicated, but also better solution is to use
a hierarchical wallet.
• To generate keys the operation normally used is the
generateKeys function.
• This operation generates a public and a secret key.
• The public key corresponds to an address that can receive
coins.
• The private key allows to control and spend the money sent to
the address.
• The hierarchical key generation is a little more complex, that
generates two things:
1. address generation info
2. private key generation info
• These information can be used to generate multiple keys:
• given the address generation info, we can
apply genAddr operation to the address generation info and
and integer i, obtaining the ith address.
• Since we can do this for every integer i, we can obtain a full
sequence of addresses.
• This operation can be done on the public side.
• the same can be applied for private keys.
• So on the private side we can generate a sequence of private
keys using genKey
• The useful property about hierachical generation :
• is that the ith address and the ith key match as they were
generated in the old-fashioned way.
• So a coin transferred to the ith address can be controlled and
spent by somebody that knows the ith key.
• This system is secure.
• So the algorithm to generate addresses can be provided to
anyone, without affecting the key generation security.
Hierarchical wallet application
• This is useful for hot and cold storage, since we can split up
these two operations between the hot and the cold side.
• The address generation is done on the hot side, while the key
generation on the cold side.
• So, at the beginning the cold side does
the generateKeysHier operation obtaining both the address
and key generation info.
• Then it pass the address generation info to the hot side.
• So, now they're connected and the two sides can generate
addresses or keys when needed.
• In this way there's only one exchange of information needed
at the beginning.
How to store cold storage information
• The information of the cold side (a key or a key generation
info) must be stored offline. Some possibilities on how to
store them:
1. save the information on a device supposing that it's secure
(i.e. phone or tablet). The information must be offline, so
the device must be switched off. If the device is stolen or
broken, the keys get lost
2. brain wallet: we can encrypt the information with a
password that we must remember. The security depends on
the password chosen. This is subject to all possible attacks
against passwords.
3. paper wallet: we can print the information and lock it up in
a safe.
• Of course even in this case the wallet can be stolen.
• Paper wallet can come in different shapes and sizes,
Eg: 2D barcode, QR code
Split and share keys
• To be able to split and share keys, we will introduce a trick
called Secret Sharing.
• The idea is to split the key in N pieces such that, given
any K of those pieces, is possible to reconstruct the key.
• While having fewer than K pieces, we'll not be able to know
anything about the original key.
Example with N=2, K=2
• Choose:
• a large prime number P
• S is the secret and has to be in the range [0..P-1]
• R a random value, which is also in the range [0….P-1]
• Split the secret S in the following way:
• X1 = (S+R) mod P
• X2= (S+2R) mod P
• If we own both X1 and X2, we can reconstruct S:
• (2X1 - X2) mod P = (2S+2R-S-2R) mod P = S mod P = S
• With only one of the two pieces it's impossible to retrieve S.
• In addition, we can't get any useful information using one of
the two pieces.
• (S+R) mod P can take any value in [0…P-1] equally likely.
• The same is valid for (S+2R) mod P.
• So X1 and X2 look totally random.
• Increasing N, with K=2
• The idea to increase the number of shares is to use a line:
• take the 2D plane with X and Y axis
• choose a random value R
• draw a line with slope R and passing through the point (0,S)
• the shares will be the points on the line (1, S+R), (2,
S+2R), (3, S+3R), ...
• It is possible to choose as many shares as wanted, since
there's an infinite number of points on the line.
Online wallets and exchanges
Online wallets
• An online wallet is similar to a local wallet that you might
manage yourself.
• But the information is stored in the cloud with a website or
a smartphone app to manage it.
• This application will store the keys, encrypted with a
password that only the owner knows.
• But it is necessary to trust the security of the website.
Advantages: it is not necessary to install software to use a web
based wallet, or a simple app on the phone
• it works across multiple devices. Even if a device is lost, the
wallet will still be available
Disadvantages: if the website or app is malicious or gets
compromised somehow, the Bitcoins can be lost. It is necessary
to trust the website as more secure than oneself.
Cryptocurrency exchanges
• Another approach instead of an online wallet, is something
that functions more like a bank.
• Bitcoin exchanges are businesses that, at least from a user
interface point of view, are similar to banks:
1. accept deposits of Bitcoins and fiat currency (es. $, €, ...)
2. enable to send and receive Bitcoins
3. buy and sell Bitcoins for fiat currency.
• Typically they try to match Bitcoin buyers and sellers.
• So they find some customer who wants to buy bitcoins with
dollars/euros and some other customer who wants to sell
bitcoins for dollars/euros and try to match them up.
Exchange risks
• It is easy to trade back and forth from fiat currency and
Bitcoins using an Exchange.
• The risky aspect is that it behaves such as a bank, so:
1. risk of bank run : Even if the bank is solvent on paper, it
is possible that when you show up and you want your
money back, the bank might be unable to produce it
2. the exchange could try to base itself on a Ponzi scheme:
So it gets people to give money promising wonderful
profits in the future. But the money of new member is
necessary to pay the profits to people who bought
previously. So this scheme at the end is always insolvent.
3. risk of a cyber attack: If someone is able to break the
security of the exchange can retrieve keys information that
control large numers of Bitcoins.
• So the money could be stolen from the exchange.
• The statistics on exchanges are not encouraging.
• In fact, until now, around 45% of Bitcoin exchanges
closed due to some failure.
• The most famous example il Mt.Gox.
• At some point it was the largest Bitcoin exchange, but at the
end it was insolvent.
• So it ended up declaring banckrupcy, leaving a lot of people
without their money.
Proof of reserve
• To increase the customers' amount of comfort, the exchange
can do some cryptographic trick called Proof of Reserve.
• The goal is that a Bitcoin exchange can prove that it owns a
fractional reserve.
Eg: it could have the 25% of the deposits, that people made,
available for withdrawal.
• The Proof of Reserve is made of two pieces:
prove how much reserve it's holding.
prove how many demand deposits the group holds.
• With these two things, it enough to divide those to numbers
to obtain the amount of fractional reserve.
Payment services
• Consider a merchant, who is an online seller of some kind of
goods or services and he wants to be able to accept payments
in Bitcoins. The reason he wants to accept Bitcoins is that the
customers would like to be able to pay in Bitcoins.
• The merchant's requirements are:
• at the end of the day he wants to receive fiat currency.
• have a way of receiving payments in Bitcoins which is easy
to deploy.
• So he doesnt't have to worry about technology changing on its
website or build new infrastructure.
• have low risk.
• The merchant wants to avoid problems coming from a technology
change,
• e:g: website problems or collapse. In addition he wants to avoid
risks that someone breaks into his hot wallet.
Payment process
1. the merchant delivers a page that contains the "Pay with
Bitcoin" button. The button will contain a transaction
ID, an identifier meaningful to the merchant in its own
accounting system, along with an amount to be paid.
2. The information that the button has been clicked will be
sent to the payment service, along with the transaction id,
the amount and merchant's identity.
3. The payments service knows that the customer wants to
pay with Bitcoins, so will start an interaction with the user
to give information about how to pay.
4. When the user confirms the payment, there will be a
redirect that goes back to user's browser. This will also
send a message to the merchant, saying that for the
payment service everything is ok until then.
5. Later, the payment service will directly send a
confirmation to the merchant, when it's fully confirmed by
the blockchain.
6. The merchant can now send the product to the customer.
• The end result of this process is that the customer pays in
Bitcoins and the merchant gets dollars.
Transaction fees
• The transaction fee is the difference between the transaction total
inputs and total outputs.
• The inputs have to be always at least as big as the outputs for the
transaction to be valid.
• But if the inputs are a little bigger, the difference is deemed to be
a transaction fee.
• This fee goes to the miner who inserts this transaction into a
block.
• Why transaction fees exist?
• There are some costs that someone incur in order to check the
transactions and insert them into the blockchain.
• The idea of the transaction fee is to compensate people for those
costs, that exist due to the existance of the transaction.
• Generally every user is free to set the transaction fee as he wants.
Since the transaction fee is a reward for miners, if the fee is
higher the transaction as a higher probability to be recorded
quickly.
Current consensus fee
• no fee if:
• the transaction is less than 1000bytes in total size
• all the outputs of the transaction are at least 0.01 BTC
• the priority of the transaction is large enough, where Priority
= (input_age1 * input_value1 + input_age2 * input_value2 + ... +
input_ageN * input_valueN) / transaction_size
• a fee of 0.0001 Bitcoins every 1000 Bytes of the transaction.
• The transaction size is approximately 148 bytes per each
input plus about 34 bytes per each output plus about 10 bytes
for other information
Currency exchange markets
• The currency exchange markets are places where it is
possible to trade Bitcoins against fiat currency.
• There are websites such as Bitcoincharts, which show
exchanges that trade dollars against BitCoins.
• There's a list of different exchanges prices. It is possible to
see latest prices, the average, the highest and lower values
ever reached.
Directly meet people who want to buy or sell Bitcoins
• There are other websites that help you meet people to trade
Bitcoins in real life,
Eg: localbitcoins.com.
• It is possible to set the fiat currency to exchange in Bitcoins,
the area (i.e. Princeton, New Jersey, United States).