IS3101 Cryptocurrency & Blockchain
Course Introduction Terminology & Jargon Building Blocks of Blockchain
– Hash functions
Copyright By PowCoder代写 加微信 powcoder
– Digital signatures – Applications
Intro to cryptocurrencies – Basic digital cash
Tutorial Exercise
Get to Know Your Lecture Instructor
Room: LAU-5-236
Email: Phone: 3442-8523
Office Hour: Wednesday 2:00 – 4:00pm or by appointment
Course Introduction
Course Intended Learning Outcomes
Explain the concepts related with cryptocurrency, blockchain, and distributed ledger technologies.
the application and impact of blockchain technology in the financial domain and other markets.
Evaluate security issues related with cryptocurrency and blockchain.
Develop applications related with cryptocurrency and blockchain.
In this course, you’ll learn something related to…
Course Topics Highlights
Smart Contracts
Cryptography
Cryptocurrency
Blockchains
Recommended Textbooks
• Narayanan, Arvind; Bonneau, Joseph; Felten, Edward; Miller, Andrew; Goldfeder, Steven (2016) “Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction”. Princeton University Press.
• Antonopoulos, . and Wood, Gavin (2020). “Mastering Ethereum: Building Smart Contracts and DApps”. O’Reiley.
• Bal, Aleksandra. Taxation, Virtual Currency and Blockchain. Kluwer Law International BV, 2018.
• Kumar, Ashwani (2020). “Hyperledger Fabric In-Depth: Learn, Build and Deploy Blockchain Applications Using Hyperledger Fabric”. BPB Publications.
• Lee, Chuen, and Low, Linda (2018). “Inclusive fintech: blockchain, cryptocurrency and ICO”. World Scientific.
• Building Blockchain Apps, 1st edition,
Course Assessments
5% bonus peer- assist Participation
20 % Tutorial Exercises, Quiz & Participation
40% Final Exam
10% Individual Assignment
30% Group Project
CityU Code of Conduct
Code of Student Conduct
http://www6.cityu.edu.hk/arro/content.asp?cid =74
Avoid plagiarism
http://www.cityu.edu.hk/edge/LASSI/student0 5.htm
Class Notifications
Announcements will be made for important events / updates of the course schedule / assessment items, etc.
Announcements will also be sent to your CityU email account
Terminology for Lecture 1
Cryptography Example
Video: https://www.youtube.com/watch?v=aOdxWtqibCI&feature=emb_logo Image source: https://searchsecurity.techtarget.com/definition/cryptography
Cryptocurrency Example
Cryptocurrency Example
Source: https://www.statista.com/chart/13520/the-top-ten-cryptocurrencies/
Blockchain Example
Source: https://www.sc.com/en/explore-our-world/blockchain/
Smart Contracts Example
Source: https://hyperledger-fabric.readthedocs.io/en/latest/smartcontract/smartcontract.html
Dapp/dApp Example
• Briefly:
1. O(1) means in constant time – independent of the
number of items.
2. O(N) means in proportion to the number of items.
3. O(log N) means a time proportional to log(N)
• Basically any ‘O’ notation means an operation will take time up to a maximum of k*f(N)
– k is a constant multiplier
– f() is a function that depends on N
O Notation
O(n), O(1) O(Log(n)), O(
Number of items
Graphs of functions commonly used in the analysis of algorithms, showing the number of operations N versus input size n for each function
2) (n)), O(n
https://www.geeksforgeeks.org/analysis-of-algorithems-little-o-and-little-omega-notations/
Terminology and Jargon
1. Hash function
2. The output is a hashes = hash values = hash codes = hash sums = checksums = message digest = digital fingerprint
3. Protocol
Cryptographic Hash Functions
Hash Function Hash function attributes:
○ takes any string as input
○ fixed-size output (we’ll use 256 bits)
○ efficiently computable
Security properties: ○ collision-free
○ puzzle-friendly
Hash (or digest)
A hash is made by taking a data
of any size, and running it through a hash function, which always returns an equal in size (256 bit for SHA256), unique in output value, every time.
Hash property 1: Collision-free Nobody can find x and y such that
x != y and H(x)=H(y)
H(x) = H(y)
Hash property 1: Collision-free Collisions do exist …
possible outputs
possible inputs
… but can anyone find them?
Hash property 1: Collision-free How to find a collision
try 2130 randomly chosen inputs
99.8% chance that two of them will collide
This works no matter what H is … … but it takes too long to matter
Hash property 1: Collision-free
Is there a faster way to find collisions? For some possible H’s, yes.
For others, we don’t know of one.
No H has been proven collision-free.
Hash property 1: Collision-free Application: Hash as message digest
If we know H(x) = H(y),
it’s safe to assume that x = y.
To recognize a file that we saw before, just remember its hash.
Useful because the hash is small.
Hash property 2: Hiding We want something like this:
Given H(x), it is infeasible to find x.
H(“heads”) H(“tails”)
easy to find x!
Hash property 2: Hiding Hiding property:
If r is chosen from a probability distribution that has high min- entropy, then given H(r | x), it is infeasible to find x.
High min-entropy means that the distribution is “very spread out”, so that no particular value is chosen with more than negligible probability.
Hash property 2: Hiding Application: Commitment
Want to “seal a value in an envelope”, and “open the envelope” later.
Commit to a value, reveal it later.
Hash property 2: Hiding Commitment API
(com, key) := commit(msg) match := verify(com, key, msg)
To seal msg in envelope:
(com, key) := commit(msg) — then publish com
To open envelope: publish key, msg
anyone can use verify() to check validity
Hash property 2: Hiding Commitment API
(com, key) := commit(msg) match := verify(com, key, msg)
Security properties:
Hiding: Given com, infeasible to find msg. Binding: Infeasible to find msg != msg’ such that
verify(commit(msg), msg’) == true
Hash property 2: Hiding Commitment API
commit(msg) := ( H(key | msg), H(key) )
where key is a random 256-bit value
verify(com, key, msg) := ( H(key | msg) == com )
Security properties:
Hiding: Given H(key | msg), infeasible to find msg. Binding: Infeasible to find msg != msg’ such that
H(key | msg) == H(key | msg’)
Hash property 3: Puzzle-friendly
Puzzle-friendly:
For every possible output value y,
if k is chosen from a distribution with high min-entropy, then it is infeasible to find x such that H(k | x) = y.
Hash property 3: Puzzle-friendly
Application: Search puzzle
Given a “puzzle ID” id (from high min-entropy distrib.), and a target set Y:
Try to find a “solution” x such that H(id|x) ∈Y.
Puzzle-friendly property implies that no solving strategy is much better than trying random values of x.
SHA-256 hash function
Padding (10* | length)
Message (block n)
Message (block 1)
Message (block 2)
256 c bits
Theorem: If c is collision-free, then SHA-256 is collision-free.
Try this tool: SHA create hash online
http://www.unit-conversion.info/texttools/sha/#data
Hash Pointers and Data Structures
hash pointer is:
* pointer to where some info is stored, and * (cryptographic) hash of the info
if we have a hash pointer, we can
* ask to get the info back, and * verify that it hasn’t changed
will draw hash pointers like this
build data structures with hash pointers
Linked list with hash pointers = “block chain”
prev: H( )
prev: H( )
prev: H( )
use case: tamper-evident log
Detecting tampering
prev: H( )
prev: H( )
prev: H( )
use case: tamper-evident log
Binary tree with hash pointers = “Merkle tree”
H() H() H() H()
H() H() H() H()
Proving membership in a Merkle tree
show O(log n) items
2 H( ) H( )
Advantages of Merkle trees
Tree holds many items
but just need to remember the root hash
Can verify membership in O(log n) time/space
Variant: sorted Merkle tree
can verify non-membership in O(log n)
(show items before, after the missing one)
More generally …
can use hash pointers in any pointer-based data structure that has no cycles
Digital Signatures
What we want from signatures
Only you can sign, but anyone can verify
Signature is tied to a particular document can’t be cut-and-pasted to another doc
API for digital signatures
(sk, pk) := generateKeys(keysize)
sk: secret signing key
pk: public verification key
sig := sign(sk, message)
isValid := verify(pk, message, sig)
can be randomized algorithms
Requirements for signatures
“valid signatures verify” verify(pk, message, sign(sk, message)) == true
“can’t forge signatures”
adversary who:
gets to see signatures on messages of his choice can’t produce a verifiable signature on another message
challenger
(sk, pk) 2 3
m0 sign(sk, m0)
sign(sk, m1) …
verify(pk, M, sig)
M not in { m0, m1, … }
if true, attacker wins
Practical stuff…
algorithms are randomized
need good source of randomness
limit on message size
fix: use Hash(message) rather than message
fun trick: sign a hash pointer
signature “covers” the whole structure
Bitcoin uses ECDSA standard
Elliptic Curve Digital Signature Algorithm
relies on hairy math
will skip the details here — look it up if you care
good randomness is essential
foul this up in generateKeys() or sign() ? probably leaked your private key
Public Keys as Identities
Useful trick: public key == an identity
if you see sig such that verify(pk, msg, sig)==true, think of it as
pk says, “[msg]”.
to “speak for” pk, you must know matching secret key sk
How to make a new identity
create a new, random key-pair (sk, pk)
pk is the public “name” you can use
[usually better to use Hash(pk)] sk lets you “speak for” the identity
you control the identity, because only you know sk
if pk “looks random”, nobody needs to know who you are
Decentralized identity management
anybody can make a new identity at any time make as many as you want!
no central point of coordination
These identities are called “addresses” in Bitcoin.
Addresses not directly connected to real-world identity.
But observer can link together an address’s activity over time, make inferences.
Later: a whole lecture on privacy in Bitcoin …
Simple Cryptocurrencies
Goofy can create new coins
New coins belong to me.
signed by pkGoofy
CreateCoin [uniqueCoinID]
A coin’s owner can spend it.
Alice owns it now.
signed by pkGoofy
Pay to pkAlice : H( )
signed by pkGoofy
CreateCoin [uniqueCoinID]
The recipient can pass on the coin again.
signed by pk to pkBob : H( )
Bob owns it now.
signed by pkGoofy
Pay to pkAlice : H( )
signed by pkGoofy
CreateCoin [uniqueCoinID]
double-spending attack
signed by pk to pkBob : H( )
signed by pk to pkChuck : H( )
signed by pkGoofy
Pay to pkAlice : H( )
signed by pkGoofy
CreateCoin [uniqueCoinID]
double-spending attack
the main design challenge in digital currency
ScroogeCoin
Scrooge publishes a history of all transactions (a block chain, signed by Scrooge)
prev: H( )
transID: 71
prev: H( )
transID: 72
prev: H( )
transID: 73
optimization: put multiple transactions in the
same block
CreateCoins transaction creates new coins
Valid, because I said so.
coinID 73(0)
coinID 73(1) coinID 73(2)
transID: 73 type:CreateCoins
coins created
PayCoins transaction consumes (and destroys) some coins, and creates new coins of the same total value
transID: 73 type:PayCoins
consumed coinIDs: 68(1), 42(0), 72(3)
coins created
signatures
— consumed coins valid, — not already consumed,
— total value out = total value in, and
— signed by owners of all consumed coins
Immutable coins
Coins can’t be transferred, subdivided, or combined.
But: you can get the same effect by using transactions to subdivide: create new trans
consume your coin
pay out two new coins to yourself
Don’t worry, I’m honest.
Crucial question:
Can we descroogify the currency, and operate without any central, trusted party?
References
• Building blocks of blockchains
– Internetnetworking&TCP/IP – Databases
• Narayanan et al. Ch 1
– Hashingalgorithms(1.1)
– Merkletrees(1.2)
– Digitalsignatures(1.3)
– Asymmetrickeycryptography(publicandprivatekeys)(1.4) – Ledgers&distributedledgers(1.5)
• Blockchain Infrastructure Landscape: A First Principles Framing, Conaghy
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com