Bitcoin

Agenda
• Introduction
• Cryptographic ingredients
• Bitcoin components
• Bitcoin security
Bitcoin: where everything started
A caveat on the paper
• A white paper briefly describing the underlying ideas of the Bitcoin
system and why it should work
• Many details about the protocol are missing and are left to the
implementation of the system
• It is intended for a specialist audience
• No background, no preliminaries
Satoshi's goal

"An electronic payment system based on

cryptographic proof instead of trust, allowing
any two willing parties to transact directly
with each other without the need for a
trusted third party"
Satoshi's Proposal

"A peer-to-peer distributed timestamp server

to generate computational proof of the
chronological order of transactions."
Cryptographic Ingredients
Hash Functions
A mathematical function

H: Data -> Hashes

that maps data of arbitrary size onto data of

a fixed size (usually a natural number or
a string of bits)

Properties
• Efficiently computable
• Every hash value should be generated with
roughly the same probability
Cryptographic Hash Functions
A special class of hash functions that enjoy further properties
making them suitable for cryptography applications

In this talk, we focus on

1. Collision free
2. Hiding (one-way function)
3. Puzzle-friendly (only for our discussion on Bitcoin)
Property 1: Collision free
It is infeasible* to find two different input X and Y with the same hash
value, i.e., H(X) = H(Y)

X H

H(X) = H(Y)

Y H

*Infeasible means impossible to achieve in practice, in theory

collisions exist
How to find a collision? (1)
Consider a hash function H that produces a digest of 256 bits

Take 2256 + 1 inputs elements and compute H(X)

Result: At least two elements are mapped on the same output since H
is not injective by Pigeonhole Principle

H Output
Input space space
How to find a collision? (2)
Consider a hash function H that produces a digest of 256 bits

Repeatedly take a random input and compute H(X)

Result: If we choose just 2128 + 1 inputs we find a collision with high

probability like the birthday problem
Collision attacks (1)
Goal: Find two inputs X and Y having the same hash value H(X) = H(Y)

Every hash function is vulnerable to brute force collision attacks: the

attacker need to tries 2n/2 + 1 inputs to find a collision, where n is the
size of the output space

Defense (necessary condition): Take l big enough to make the attack

infeasible in practice, e.g., when n = 256, 2128 + 1 tries are needed
Collision attacks (2)
Observation: if we know how H is defined, we can exploit its
weaknesses (if any) to build a collision

Example
H(X) = X mod 2256
Take X = 3 and Y = 3 + 2256
Collision attacks: final thoughts
In practice:
- We adopt standard hash functions that should not be easy to attack
- No proof of collision resistant but an heuristic approach (nobody has
found collision for a long time)

- We can assume that X and Y are different then so are their hashes
- We can use the hash as message digest
H(X) = H(Y) ⇒ X = Y
Applications: Hashes as Digest
When H(X) = H(Y) it is safe to
assume X = Y

Integrity verification of messages

and files
Comparing hashes calculated
before, and after, transmission we
can determine whether any
changes have been made to a
message or a file
Property 2: Hiding
The desiderata
Given H(X) is infeasible to invert H and to compute X.

What happens when X is chosen from a small set?

Example
I = {head, tail} H(head) = 0x25FA H(tail) = 0x35B1

The attacker can pre-compute all possible hashes and use them to
invert H
Property 2: Hiding
The idea (simplification)
Concatenating our input X with a value R taken from a sparse set where
each element has the same probability to be chosen.

The actual property

Let R a secret value, a hash function H is hiding when it is infeasible to
invert H(R | X) in order to find X
Application: commitments (1)
A commitment scheme consists of two algorithms:
1. commit(msg, nonce) ⇒ create a commitment from a msg and a
secret random value
2. verify(com, msg, nonce) ⇒ it returns true if the com is the
commitment of msg and nonce
com == commit(msg, nonce)

They are useful to create claim that can be revealed after a while, e.g.,
in lotteries.
Application: commitments (2)
We want commitments enjoys two properties:
1. Hiding: Given com, it is infeasible to find msg
2. Binding: It is infeasible to find two pairs (m,n) and (m’,n’) such that
m != m’ and commit(m,n) == commit(m’, n’)

In practise:
- Nobody can read the message from the commit
- We cannot produce lie after we committed on a value m
Commitment: implementation
commit(msg, nonce) = H(msg | nonce)
verify(com, msg, nonce) = com == H(msg, nonce)

The hiding and the binding properties are ensured by the property of
the hash function H

Note: every time you commit to a value, choice a new random nonce
Property 3: Game Friendly
The idea
• We use our hash function to generate mathematical problems that
are difficult to solve
• These problems consists in finding a value X that satisfies a given
property
• Difficult because the only way to solve the problem is to enumerate
all possible values for X (the search space is very big)
Property 3: Game Friendly
Given
• a hash function H,
• Y a hash value and
• R a value randomly chosen from a sparse set,
H is game friendly if it is infeasible to find X such that H(R | X) = Y

Note:
It easy to verify that X is a solution
Application: Search puzzle
Puzzle: Find a X such that H(R | X) in Y

• A value R randomly chosen

• A subset Y of Hashes (target set)

Note:
• The size of the target set determines the difficulty of the game
• No shortcut, only enumerate all possible X
Application: Proof-of-work
It was initially proposed by Cynthia Dwork and Moni Nao to control the
access to a shared resource (and to combat junk emails)
Real Hash functions: SHA-2 family
SHA-2 is a family of cryptographic hash functions designed by NSA

It consists of six hash functions with digests (hash values) that are 224,
256, 384 or 512 bits

It is built using the Merkle–Damgård construction

Merkle–Damgård construction
It is a method of building collision-resistant cryptographic hash
functions from collision-resistant one-way compression functions*

(*) a function that transforms two fixed-length inputs into a fixed-length output.
Hash pointers
A data structure made of two
pieces of information

1. A location where some data is

stored
2. A Cryptographic hash of the
information

We can verify that the information

hasn't changed
 Block chain: a linked list built on hash
pointers

The hash stored in the hash pointer is the hash of the whole data of the
previous block
 Tamper evident property

• An attacker cannot change any block without being detected

• Tampering can be detected by traversing the blocks backwards and

verifying the hashes one by one
Merkle tree
A balanced binary tree built from a
set of data (leaves of the tree)

Properties
• Tamper evident as blockchain
• Easy to verify if a piece of data is
in the tree: you just need to
provide a path from the root to
the corresponding leaf

Exercise
Can you verify the absence of a
data from the tree?
Digital signature
A mathematical scheme for verifying
the authenticity of digital messages or
documents

Properties
• Valid signature must verify
• It is impossible to forge signature

we need to bind the signature to a

specific document
Digital signature
A mathematical scheme for verifying the authenticity of digital
messages or documents

Ingredients:
1. (sk,pk) := generateKey(key_size)
• sk -> the private key used to sign your messages/documents
• pk -> the public key used by others to verify your signature
2. sign(sk, message) --- a signing algorithm
3. verify(pk, message, sign) --- a signature verifying algorithm
Unforgeability
An attacker knows
- public key
- signature on some previous messages

The goal: It must be feasible to forge the signature on a new message

Unforgeability game:
The chance of the attacker to successfully
forge a message is so small, it never happen
in practise
Practical concerns
the generateKey function often relies on some randomness, so we
need to have access to a good randomness source

Usually, we sign the hash of the document not the document itself: this
is for efficiency and security reasons
ECDSA (1)
Bitcoin uses a particular digital signature scheme called Elliptic Curve
Digital Signature Algorithm (ECDSA) that elliptic curves math

An elliptic curve which consists of the points satisfying the equation

+ a point at infinity
Bitcoin uses a specific curve called secp256k1
ECDSA (2)

- The private key is a scalar value of 256 bits

- The public key is a point (x,y) of the curve (512 bits in total)
- We can only sign messages 256 bits long (no problem we use SHA-256)
An example of signatures
ECDSA private key
8bf65c723b8d2040109cea97d828c88457f6ffcd6add2b9a4e0c43c66b0b2146

ECDSA public key

040d6eaabf1bd520e66530591989ae63823ea792469f15284e9155171f688fa
98b789ff640a558be592e1402f01dc7ed5325bb9912145af539e0aaec82c9f81
5fd

Signature output
3ec850a9f720f4c83272e6cc0de1b8cb621bd3cb214f0d7516cd36c697177261
2cc1e7fa7400f64de92c624c117c729a427ef72c451b35c87de5ea1ede0d469f
Application: digital signature as identities
The idea
• Consider a public key pk as an actor/identity of the system
• If you see a message that verify the signature of pk, you know that
pk is sending the message (assumption: only pk knows the
corresponding sk)

Note
You may generate how many identities you want (just generate a new
pair of keys)
 Users as digital signatures
- Bitcoin addresses are simply hashes of public keys
- A user may have multiple addresses
- Bitcoin ensures a certain level of anonymity for users but not full
anonymity and privacy (complex and deep topic!)

A cryptographic hash function

An encoding function from binary

data to text
Application: decentralized identity
management
- No need of having a central
authority for registering users
in a systems

- You can register by yourself

just by picking a pair of key
Bitcoin components
How do we represent a currency?
Account-based model (Not in Bitcoin): Each participant has a balance of currency

Transactions are claims that creates and transfers money between user

We need to store the information about users balances and for each transaction we
need to check that the user has enough money (overhead)
Unspent Transaction Output (UTXO) Model
- UTXO model treats each transaction output as a separate entity that
can be spent in future transactions
- The outputs are created by transactions and can be used in
subsequent transactions.
- Each UTXO is identified by a unique transaction ID and index.
- Only the owner of a UTXO can spend it, ensuring security.
- When a UTXO is spent, it gets consumed and cannot be used again.
- The sum of UTXOs associated with a user represents their available
balance.
How UTXOs Work
- Inputs are references to previous UTXOs that are being spent.
- Outputs specify the new UTXOs that will be created for receiving
addresses.
- Each transaction must have a valid set of inputs to be confirmed.
Bitcoin transactions
Transactions have
• an ID (its hash)
• Several input specifying the coins of previous transactions are
consumed by this transaction
• Transactions that only create coins do not have input
• Several output specifying the coins to be created
Bitcoin transactions: example
How a transaction looks like?
How to spend an output? (1)
How do we identify the owner of a transaction and let some input to spend that
transaction?

Bitcoin provides Script is a mini programming language used as a locking

mechanism for outputs in bitcoin transactions:
- A locking script is placed on every transaction output.
- An unlocking script must be provided to unlock an output (i.e. when used as an
input to a transaction).

If a full script (unlocking + locking) is valid, the output is "unlocked" and can be
spent.
How to spend an output? (2)
- Script is a non-turing stack-based scripting language with primitive for
cryptography operations
- It has 256 opcodes and can be used to express several unlocking conditions
- However, there are some well-known patterns of unlocking conditions:
- Pay To Public Key Hash (P2PKH) used for locking an output to someone's
public key (legacy)
- Pay To Witness Public Key Hash (P2WPKH) locks an output to a public key
hash (modern variant of P2PKH)
P2PKH — Pay To Public Key Hash

We copy the signature and the public key on the data stack and run the
script. [Animation]
Bitcoin as peer-to-peer system
• All system is fully decentralized, there is no central authority
• A node in the network can operates as miners or as normal client
• Miners validate transactions, run the consensus algorithm to decide
which block to happen to the blockchain
• Every node can be a miner
• The nodes of the network maintain a copy of the blockchain
• Miners extend the longest blockchain
Steps to run the network
1. New transactions are broadcasted to all nodes
2. Each node collects all the new transactions it is aware and store
them in a mempool
3. From the mempool selects a set of transaction and form a block
4. The nodes run a consensus protocol to establish which the next
block is (see later)
5. Nodes accept a block if it is valid and by using its hash for creating
the next block of the blockchain
Blockchain: a block
Blockchain
Consensus protocol (in general)
There are N nodes in a network each with an input value. Some node
are faulty or malicious. A distributed consensus protocol must have the
following properties
1. It must terminate with all honest node in agreement on a value
2. The chosen value must have been chosen by an honest node

Impossibility result: in general it is impossible to achieve consensus in

a distributed system
Bitcoin Consensus
The impossibility result does not apply in Bitcoin, because Bitcoin
represents a very specific model (different from those used to derived
the impossibility results)

Two ingredients:
1. Economic incentives "force" nodes to behave honestly
2. The Bitcoin protocol relies on a sort of randomness
Bitcoin consensus (simplified)
• When a transaction is broadcast to the network, the receiving nodes
put it in a block
• In each round of the protocol a random node gets to broadcast its
block that becomes the next block of the block chain (simplification)

Question: how is this random node selected?

We approximate the selection of a random node using the
proof-of-work mechanism
The assumption is that nobody can monopolizes the computational
power required for it
Proof-of-work
The miner who wants to append its block must find a nonce that
satisfies
H(nonce | prev_hash | tx1 | … | txn) < target

Since the hash function used in Bitcoin is puzzle friendly, the only way
to find the nonce is to try a lot of nonces

The difficulty of the puzzle (target) is automatically adjusted in a way

that a new block is appended every 10 minutes in average
Incentives
Two kind of incentives to make miners behave honestly
1. Block reward: the miner which creates a block can put inside it a
special transaction that creates new coins (25 bitcoin currently) for
an address chosen by the miner
2. Transaction fee: usually the creator of a transaction makes the
output smaller than the input. The difference between output and
input becomes the fee for the miner which appends the block to
the blockchain
Blockchain fork
• It may happen that at the same time there are two versions of the
blockchain
• This is not a problem, because the network of miners select and
append the new block to the longest version of the blockchain
• The transactions which were in the discarded branch are not lost, but
they need to be "re-inserted" in a new block
Bitcoin limitations
1. Limits in the programmability
2. Solve the cryptographic puzzle requires too much
resources
3. Transaction requires a certain amount of time before
they are inserted (finalized in the blockchain) and this
may hinder scalability
4. Privacy
Other proposals
Smart contracts

•Popularized by Ethereum
•It is a computer program localized on
the blockchain executed by validators
of the network
•Such a program is executed when
certain conditions arise
Permissioned blockchain
•Blockchains with permissions, use an access control layer to
control who accesses the network and what data can be read
and written
•Block validators are controlled by network owners

Example
Overview on Bitcoin & Security
What are possible attacks?
•51% attack
•Double spending
•Finney Attack
•Brute force attack
•Selfish attacks
•DDoS
Recap: Bitcoin main features
•A fully decentralized system, there is no central authority
•Data stored on the blockchain cannot be modified
(anti-tampering)
•The public leader provides a consistent and unique view of
the state of the system
•Users are provided with a certain degree of anonymity
Is Bitcoin secure?
Actual question: What does "secure" mean?

Typical worries:
•Can I lose my bitcoins? Can someone steal them?
•Is it possible that I receive a payment and then it vanishes?
•Can a malicious miner earn more than it deserves?

Attack: a slightly deviation from the normal behavior of the

protocol that provides some advantages to the attacker
Attack surface
•Wallet attacks (malware stealing keys, client-side security)
•Network attacks (DDoS, sybil, eclipse, etc.)
•Mining attacks (bribery, 51%, etc.)

Many attacks are still theoretical

51 Percent Attacks
•Question: what happens if there is attacker who control the
majority of the mining power in the network?

•What can this attacker do?

Can he steal coin from an address?
•No, because he cannot subvert cryptography to steal coin.

•Without attacking the cryptography, the transaction

generated by the attacker will be invalid and the honest
miners simply do not accept as valid the blockchain containing
it
Can the attacker suppress the transactions of
a specific address A?
•Yes, since the attacker can control the consensus protocol:

•Refuse to create any new block containing a transaction from A

•Refuse to extend a blockchain containing a transaction from A

Can the attacker change the block reward?
•No, because this could cause the transaction creating new
coin to be considered invalid by other peers; also, she needs to
change the protocol.
Can the attacker destroy the confidence in
the coin?

•Yes, users may feel that the system is not fair and
decentralized enough and may want to abandon it
Double Spending
•A participant performs a double spend if
she spends simultaneously the same bitcoin in two different
transactions

•A client C broadcasts a transaction Tv for transferring to V some

bitcoin B at time t
•The client C broadcasts another transaction Tc sending B to itself at
time t' (t and t' are very close)
•The attack succeeds if C tricks V to accept Tv but V will not redeem Tv
afterwards
 Successfully double spending
•The following must be meet to trick a vendor with double spending:
1. Part of the miners accept Tv and the vendor receives the
confirmation from these miners and sends the product to C
2. Other miners accept Tc, thus, the blockchain forks
3. Most miners works on top of the blockchain containing Tc, thus, it
becomes the actual blockchain
Finney attack
• The client pre-mines a block containing Tc and keeps it
privately
• The client creates and broadcasts the transaction Tv
• Once the vendor sees Tv on the blockchain, she sends the
product
• The client tries to fork the blockchain using the pre-mined
transaction Tc, trying to invalidate Tv
Brute-force attack
•An evolution of the Finney attack
•The vendor waits until m confirmations before delivering the
product
•The attacker controls n nodes in the network that work to create
a private copy of the blockchain to be released for double spend
Graphically
Mining pools
•Group of miners cooperating to mine blocks and split
rewards
•Pools are managed by a pool manager that forwards undone
work to pool members
•Each member submits either PPoW or FPoW to the manager
as shares
•When a solution is found the manager split the rewards
among miners depending on their shares
Attack on mining pools
•Dishonest miners can join a mining pool to perform an
internal attacks (selfish mining)
•Obtaining an unfair rewards with respect to the work done by
dishonest miners
•Sabotaging the pool by wasting computational resources
Bitcoin network attacks
•Denial of Service attacks targets exchange, mining pools and
eWallets
•Malicious miners perform a DDoS against competing mining
pools in order to make them perform useless work or to
disconnect them from the network
Other attacks 1

Table from "A Survey on Security and Privacy

Issues of Bitcoin" by M. Conti et al.
Other attacks 2

Table from "A Survey on Security and Privacy

Issues of Bitcoin" by M. Conti et al.
References
• Sathoshi Nakamoto. Bitcoin: A Peer-to-Peer Eletronic Cash System
• Narayanan A., Bonneau J., Felten E., Miller A., Goldfeder S., Bitcoin
and Cryptocurrency Technologies, Princeton University Press, (2016)
• M. Conti, E. Sandeep Kumar, C. Lal and S. Ruj, "A Survey on Security
and Privacy Issues of Bitcoin," in IEEE Communications Surveys &
Tutorials, vol. 20, no. 4, pp. 3416-3452, Fourthquarter 2018.