blockchain-advanced-cryptography-2023.pdf

Introduction to Distributed Systems
and Blockchain Technology
ADVANCED CRYPTOGRAPHY
K . KHOSRAVANI
1

introduction
2

Centralized Systems
Client / server architecture
Master / Slave architecture
A central unit serves/coordinates all the other nodes in the system.
Server
Client 1 Client 2 Client 3
3

Advantages of Centralized systems
Easy to physically secure
Dedicated resources (memory, CPU cores, etc)
Quick updates are possible
Easy detachment of a node from the system.
Centralized control: In a centralized system, the central authority has complete control
over the system, which can lead to better coordination and decision-making.
Easier to manage
Lower latency
Simpler implementation
4

Problems Of Centralization
Single Point of Failure
Control over Data/Money :Dropbox has access to your data
, Banks happen to not return your money
Prone to Intimidation & Pressure : Authorities can ask for
data , Problems with Swift , Gmail FBI investigation
Unjustified Cost : Swift
Power of decision making lies with the top management :
Governments and traditional big companies
Distrust :We have to rely on them
5

Disadvantages of Centralized System
Difficult server maintenance
Single point of failure
Lack of transparency: Centralized systems lack transparency
as the central authority has complete control over the system,
which can lead to issues like censorship and bias.
Limited scalability: Centralized systems have limited scalability
as the central node can only handle a limited number of clients
at a time.
Limited innovation
6

Distributed Systems
Adistributed systemis a collection of individual computers
that utilize computational resources across multiple, separate
computation nodes to achieve a common, shared goal
7

8

DECENTRALIZED SYSTEMS
In decentralized systems, every node makes its own decision.
The final behavior of the system is the aggregate of the
decisions of the individual nodes.
9

10

Characteristics of Decentralized System
Lack of a global clock
Multiple central units (Computers/Nodes/Servers)
Dependent failure of components:one central node failure
causes a part of the system to fail; not the whole system ,ex :
ISP
11

Advantages of Decentralized System
Minimal problem of performance bottlenecks occurring –The
entire load gets balanced on all the nodes;
High availability
Improved More autonomy and control over resources –As
each node controls its own behavior, it has better autonomy
leading to more control over resources.
fault tolerance
12

Advantages of Decentralized System
Increased transparency (ex : torrent)
Greater security: Decentralized systems can be more secure
than centralized systems because there is no single point of
failure or vulnerability that can be exploited by attackers. Data
is distributed across multiple nodes, making it more difficultto
hack or compromise.
Improved scalability
13

Disadvantages of Decentralized System
Difficult to achieve global big tasks –No chain of command to command
others to perform certain tasks
Difficult to know which node failed
Security challenges: Decentralized systems can be vulnerable to security
threats such as DDoSattacks, and 51% attacks.
Inefficient resource utilization: others may be overloaded. This can lead
to a waste of resources and decreased performance.Decentralized
systems can suffer from inefficient resource utilization as some nodes
may have spare computing resources while
14

Disadvantages of Decentralized System
Lack of standardization: Decentralized systems lack standardization,
which can make it difficult to integrate with other systems and can lead
to interoperability issues. This can be a major challenge for organizations
that need to work with multiple decentralized systems.(ex : internet
protocols like BGP)
Slow transaction processing: Decentralized systems can be slower in
processing transactions compared to centralized systems. This is because
each transaction needs to be validated by multiple nodes, which can take
time.
Difficult to achieveconsensus
15

Advantages of Distributed System
Low latency than a centralized system
Fault tolerance
Increased reliability
Cost-effective
Improved performance
Autonomy: Each site is able to retain a degree of control
over data stored locally.
16

Disadvantages of Distributed System
The conventional way of logging events by absolute time they
occur is not possible here.
Network complexity: Distributed systems require a complex
network infrastructure to operate, which can be difficult to set
up and maintain. Network outages and bottlenecks can cause
system failures and data loss.
17

Disadvantages of Distributed System
Security challenges: Distributed systems can be vulnerable to
security threats such as cyber-attacks, data breaches, and
unauthorized access.
Synchronization issues: Data consistency and synchronization
across all nodes can be a challenge, especially when multiple
users are accessing the system concurrently. (ex : keep track
of stocks in different stores)
High development and maintenance costs
18

consensus
19

Distributed Consensus
An algorithm achieves consensus if it satisfies the following
conditions:
Agreement: All correct nodes decide on the sameoutput value.
Termination: All correct nodes terminate in finite time and decide
on some output values.
Validity: The decision value must be the input value of a node.
20

Distributed Consensus
Generate a random number
◦In centralized : run PRNG algorithm
◦In decentralized : consensus. how?
Decide who make a data (leader Election)
21

leader Election
We have network of processes.
Want to distinguish exactly one, as the leader.
Eventually, exactly one process should output “leader”
Motivation: Leader can take charge of:
◦Communication
◦Coordinating data processing
◦Allocating resources
◦Scheduling tasks
◦Coordinating consensus protocols
22

LCR [LeLann-Chang-Roberts]
Most simplest, easy to implement algorithm.
It works in a ringpattern topology in a synchronous fashion, i.e., they
only move forward when they receive an incoming message for moving
forward.
Every node in the distributed network topology is assigned
withUNIQUE UID.
23

LCR [LeLann-Chang-Roberts]
I.Each process sends its UID in a message, to be relayed step-by-step
around the ring.
II.When process receives a UID, it compares it with its own.
III.If the incoming UID is:
Bigger, pass it on.
Smaller, discard.
Equal, the process declares itself the leader.
This algorithm elects the process with the largest UID
24

25

Bully [Garcia-Molina]
Process with the highest UID is elected as a leader
is based on complete topology network(each process can
reach any other process in the same group in one message
hop)
26

Bully [Garcia-Molina]
I.Process P starts a leader election if it suspects the failure of existing
leader.
II.P sends inquiry message to nodes (processes) with higher UID
III.If any response then, P gives up the election and waits for higher
priority node to elect itself leader
IV.If no response then P becomes a leader.
27

leader Election
What about :
Arbitrary topologies
Synchronous nodes
Link failure
Process failure
Malicious nodes
Each algorithm is good for one scenario
28

blockchain
A blockchain is a decentralized database that stores
information. as it’s name suggests its made of blocks which are
chained to each other.
Each block contains the Hash of previous Block , so once a
block added into blockchain , we can no longer remove or
tamper it (
why?
)
29

miners
Decentralized individuals who don’t trust each other and want to
generate next block
Why should they waste their resources to generate next block?
Reward
We will explain more about them in the next chapter
30

Client
Client
Client
Client
Database
Validation Rules
Client
Client
Client
Client
Database
Validator
Validator
Validator
central access control
replaced with distributed
consensus
Database state dependent
upon agreement of majority
How to reach consensus
(vote)?
31

32

Proof of Work
An Algorithm for consensus in blockchain
The idea first introduced by Cynthia Dworkand Moni Naor(1993)
in “Pricing via Processing, Or, Combatting Junk Mail, Advances in
Cryptology”
A leader election algorithm to determines which node have the
right to record data and enables them to swiftly agree on the
information included in a block (leader makes the next block)
33

Proof of Work
Achieve consensus by solving a complex computational
puzzle the first node who solves the puzzle and publish it
becomes the leader.
How hard the puzzle should be?
34

computational puzzle
A computational puzzle is a moderately hard problem, the answer of
which can be computed within a reasonable time and verified efficiently.
DDOS mitigation
POW
Examples
make a block B which n least significant bits of Hash(B) are all 0, Hardness of
puzzle increases with n
Find
?
∗
which
?
,hardness of puzzle increases with P
35

SHA 256
∗ 69:
Cryptographic hash functions:
Preimage resistance : given y hard to find x which
Second preimage resistance : given
5
hard to find
6
which
5 6
Collision resistance : find any
56
which
5 6
36

SHA 256
In April 2021, Bitcoin was computing170000 quadrillion SHA-256
hashes per second.
That's
5=
hashes per second.
Based on birthday paradox we need to search

of space to find
collision
Which means
69:

56<

6
-.4
5;∗54
-5
∗:4∗:4∗68∗7:9.69
54
( it has two unrealistic
assumptions )
37

How blockchain works
Secure basedonSecond
preimage resistance
Image source: https://pplware.sapo.pt/informacao/monero-xmr-uma-moeda-segura-privada-e-sem-rasto/
38

fork
What if multiple miners mine a new block at nearly the same
time?
the entire network may not agree on the choice of the new
block
Vote on new blocks
What should they vote with?
Fork with longest chainwins
39

562 563
564 565
564 565 566 567
40

51% attack
Adversary wants to tamper block B in block chain:
Find block which . Impossible (2
nd
preimage
resistance)
(what if he finds it?)
Make a forkin blockchain, Start generating next blocks and
becomes the longest chain. need to have more computational
power than the rest of the network which means 51% of the
network.
(really?)
41

https://learnmeabitcoin.com/technical/51-attack
42

51% attack
Assumptions :
Power is a good way to vote
Adversary against honest parties together
Both assumptions are wrong (why?)
43

bitcoin
Average time to mine each block in bitcoin is 10 minutes.
The mining difficulty changes every 2016 blocks (2 weeks)
(645: ∗ 54 ???????)
(???? ?? ???? ???? 645: ??????)

44

bitcoin
Foundry mined 4 blocks in 4 minutes, 828,838 to 828,842 and earlier got 6 in a row ,
828,822 to 828,827
Viabtcmined 4 blocks in a row but they have barely 10% of the hashrate.
45

bitcoin mining distribution
46

https://www.blockchain.com/explorer/charts/pools
47

48

49

pools
Small miners share their resources to increase chance of mining a block
and share rewards according to their shared hashing power
Reason : difficulty for mining increased to the point where it could take
years for small miners to generate a block.
Pros : receive constant reward
Cons : Centralization
50

Drawbacks of POW
Bitcoin alone is estimated to consume143 terawatt-hours (TWh) a year
more than many countries, including Norway.
Computational puzzles energy and expensive processors
energy and expensive processors more costs
More costs higher fee for using Blockchain
51

Drawbacks of POW
Proof-of-Work encourages centralization of mining.
Centralized mining, as a direct result of economies of scale,
to reduce cost of maintenance
to variance of expected reward
The only cost the attacker incur, in the case of a failed attack, is energy
cost.
If protocol detects a malicious party, it can not do anything about it.
52

Proof of stake
Under proof-of-stake (POS), validators are chosen based on
the number of staked coins they have.
The next block writer on the blockchain is selected at
random, with higher odds being assigned to nodes with larger
stake positions.
the more money you stack , the higher the chance of
becoming leader
53

Proof of stake
Miners lock their money (stake it) on blockchain instead of buying
mining hardware.
They lose their authority on spending their money for a amount of
time, which incur them a cost similar to cost of energy and
maintenance.
Each miner get the chance to produce a new block proportional to
the ratio of its staked money to total staked money.
54

POW Vs POS
PROS CONS
POW Strong security through computational
hardness
High energy usage
Higher txfees
Slow block generation speed
POS Fastblock generation speed
Energy efficient
Security through risk of losing money
coin hoarding
55

Consensus in POS
We need a random number generator to select next leader
This random number generation must be decentralizedand attack
resistant.
We need to use a good DRNG
56

Features of DRNG
Availability: Successful completion despite participation of malicious
nodes.
Unpredictability : no one can predict output before completion
Unbiased: Output distributed uniformly at random despite participation
of malicious nodes.
Verifiable: Output correctness can be checked by third parties. It means,
Scalable
57

Examples of DRNG
Every one generates a random string and submit it, DRNG is
xorof all those numbers , if someone didn’t submit its number
ignore its string (issues?)
Every one generates a random string and first send its hash
as commitment and later send its string DRNG is xorof all
those numbers , if someone didn’t submit its number ignore its
string(issues?)
Any ideas?
Verifiable secret sharing
58

blockchain
A blockchain is a decentralized databasethat stores
information. Nodes in blockchain don’t trust each other.
Data protection
No central authority and Government censorship
Shared economy
59

Healthcare
Image Credit: Billion Photos / Shutterstock.com
60

VANET
DO -10.1155/2021/6679882
61

cryptocurrency
We will discuss them in details in next slide
62

references
https://www.geeksforgeeks.org/comparison-centralized-decentralized-and-distributed-
systems/
https://medium.com/nerd-for-tech/leader-election-algorithms-in-distributed-systems-
f513d41ad0d9
distributed algorithms nancy lynch
https://krchowdhary.com/dist-algo/dist-algo.html
M.A.Maddah-Ali blockchain 2019 lecture notes
https://101blockchains.com/consensus-algorithms-blockchain/
https://krchowdhary.com/dist-algo/ledrelct.pdf
https://www.blockchain.com/explorer/charts/pools
63

64

bitcoin
Address
Transactions
blocks
Rewards for miners
Halving
Attacks
Anonymity
65

Public key
Each bitcoin account is associated with a pair of keys
A private key
A public key
It is based on Elliptic Curve Cryptography.
Others use your address (function of public key) to send you
Bitcoin.
You use your private key to spend your Bitcoin
66

Eliptic curve
It is called Secp256k1
Prime Number
69:76=<;:8
The curve:
6 7
Generator: G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB
2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8
FD17B448 A6855419 9C47D08F FB10D4B8
Public key = G*secret key
67

https://www.oreilly.com/library/view/mastering-bitcoin-2nd/9781491954379/ch04.html
68

https://www.oreilly.com/library/view/mastering-bitcoin-2nd/9781491954379/ch04.html
69

Address
Why not use the public key instead?
One more layer of security
You can’t find the public key from the bitcoin address
Prevent burning bitcoin (how?)
Do you need a TTP to generate or confirm your account?
70

71

Transaction
72

Transaction
Meta data
◦Hash of the transaction as txID
◦#inputs
◦#outputs
◦…Inputs
◦It has to be UTXO
◦ID of the input tx
◦Which UTXO of that txdo you want to use (unspent transaction output)
◦Solution to the puzzle of that UTXO
Outputs
◦Amount
◦Puzzle for spender (ScriptPubKey)
73

Bitcoin and Cryptocurrency Technologies Princeton University Press
74

UTXO
UTXO : output of a transaction that hasn’t been used as input
of other transactions yet
Single use: An UTXO must be entirely spent. And only as input of one
transaction.
What if:
◦UTXO has 5 bitcoin and you only want to spend 2 bitcoin?
◦Someone try to double spendan UTXO
75

76

Transaction fee
The difference between sum of transaction of inputs and
outputs.
the MINER of that block gets that money as Transaction fee.
Why Transaction fee?
Avoid flooding the network with transactions.
Motivation for miners
77

Script
The bitcoin transaction script language: Script.
a stack-base language
limited in scope
can be executed on a range of hardwares.
is Turing Incomplete
no loops or complex flow control capability
halting problem: to enforce operations in blockchain halts after finite steps
and doesn’t stuck in infinite loops.
2 3 OP_ADD 6 OP_EQUAL
78

Script
Last in first out
scriptSig: given by spender of UTXO as input of his transaction
(unlocking script)
scriptPubkey: sender lock UTXO with this cryptographic puzzle
79

Bitcoin script execution example
<sig> <pubKey> OP_DUP OP_HASH160 <pubKeyHash?> OP_EQUALVERIFY OP_CHECKSIG
<sig>
<pubKey>
<pubKey>
<pubKeyHash?>
<pubKeyHash>
true
Slide from :Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Princeton University

script
Cant program advanced models with script
no loops or complex flow control capability
halting problem: to enforce operations in blockchain halts after
finite steps and doesn’t stuck in infinite loops.
Limited cases
Ethereum uses smart contract, what about infinite loops?(gas fee)

Bitcoin block
82

Miner
Chose some of the transactions
Validate them
Put them in their block
Change nonce till the block satisfies the puzzle
Nonce is 32 bits what if none of
76
blocks solve the puzzle?
83

Reward for miner
I.Summation of all transaction fees
II.Base reward for mining the block
Miner send this money to himself in a special type of
transaction called the coinbasetransaction
This is the first transaction in each block
This transaction does not consume UTXO
84

halving
When Bitcoin was first mined in 2009, mining one block had
50 BTC as reward.
This reward halves every 210000 blocks (about 4 years)
Its 6.25 right now
Limits number of bitcoins to
94
5?
-
.
85

86

Double Spending
Eve want to use a UTXO twice:
If she spend it in block 1467 that txis no longer an UTXO so
she can’t use it on blocks after 1467 (invalid tx)
If she submit one txand make another txand try to fork the
system ( can’t due to 51% attack)
87

Double Spending
If she submit request for both txson one period (block)
Miners wont add both txsin one block
In worst case a fork happens between miners that has tx1
and miner that has tx2 only one winner so one tx
88

562 563
564 565
564 565 566 567
89

Anonymity
what is anonymity?
pseudonymity
unlinkability
Pseudonymitymeans no need to use real name and identity
unlinkabilitymeans your interactions in blockchain can’t be
linked together
90

Anonymity in bitcoin
Bitcoin has pseudonymity(address isn’t your real name and
no need to verify)
Bitcoin’s transactions are clear and everybody can see and
trace it so they are linkable.
91

How to bring linkabilityto bitcoin?
Use different address for each tx
What if more than one input in tx?
Shared spending means same person or close relations
Any idea?
92

Mix transactions
mixer
UTXO
from
many
users
UTXO to
different
addresses
of those
users
93

Do you need block chain?
Blockchain has some disadvantages:
Scalability
Additional protocol and communication for consensus
Block rate
Complexity
Storage problems
Inefficient mining process
94

Who can join?
Public Blockchain
every one can join the blockchain system
Private Blockchain
there are some rules and requirements to join the
blockchain system
95

Who can be validator?
Permissioned blockchain
there are some rules and requirements to be a validator
Permissionlessblockchain
Everyone can be a validator
96

97

summery
Distributed systems
Consensus
Blockchain
POW
POS
Attacks
Bitcoin
When to use blockchain
98

references
https://www.oreilly.com/library/view/mastering-bitcoin-
2nd/9781491954379/ch04.html
Bitcoin and Cryptocurrency Technologies Princeton University Press (book)
Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Princeton
University (slides)
K. Wüstand A. Gervais, "Do you Need a Blockchain?,"2018 Crypto Valley
Conference on Blockchain Technology (CVCBT), Zug, Switzerland, 2018, pp. 45-
54, doi: 10.1109/CVCBT.2018.00011.
99

100

blockchain-advanced-cryptography-2023.pdf

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

blockchain-advanced-cryptography-2023.pdf

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77