Introduction to authenticated data structures & cryptocurrency
Welcome to COMP90088!
● Why study cryptocurrency?
Copyright By PowCoder代写 加微信 powcoder
● About the course
● About me
● Crypto background
○ digital signatures
○ hash functions
○ … and applications
● Intro to cryptocurrencies
○ basic digital cash
Why study cryptocurrency?
Economically significant (here to stay?)
Political and philosophical questions
Interesting new applications
Most importantly: so much computer science to learn!
● Cryptography
● Distributed systems
● P2P networking
● Security & privacy
● Game theory
● Formal verification
● Consensus protocols
● Hardware design
About this course
● 2 hours weekly lecture, 1 hour tutorials ○ Hybrid mode, should be available online or off
● 4 problem sets (complete by yourself)
● 2 programming assignments (can partner)
● 1 free-choice research project (up to 3 per team)
○ Proposals due March 31
Course readings
● Reading is important. I will not cover every topic in detail in lecture
● Textbook can be read freely online
● Other readings will be assigned (topic moves fast!)
What this class is not about
● Cryptocurrency economics
● Whether to invest
● What to buy
● Where to buy
● How much to buy
● Trading strategies
● Taxes of regulation
● Who Satoshi is or was
About your instructor
● BS MS Stanford
● PhD Cambridge (cryptography)
● Working in cryptography since 2006
● First cryptocurrency paper: 2014
● Published cryptocurrency papers: 19
● 8th term teaching this class (4 universities)
● Helped launch 4 cryptocurrencies as advisor::
Outside of work
What is cryptocurrency?
Cryptocurrency = crypto + currency
Currency: payment technology for general-purpose use
1. Means of exchange
2. Store of value
3. Unit of account
Crypto: transfer of value is controlled by cryptography
Crypto ≠ cryptocurrency
Cryptography is an ancient science
● Encryption/decryption
● Data integrity
● Digital signatures
● Zero-knowledge proofs
● Multiparty computation
● Cryptocurrency
Traditional currency relies on difficult-to-copy objects
● Precious metal
● Protected dies
Banknotes:
● Special material, watermarks
● EURion constellation
Both: heavy criminal penalties
Digital currency is harder because copying is easy Currencies
Digital currencies Physical currencies
Cryptocurrencies
Many types of cryptocurrency: centralized/decentralized, payments/smart contracts, private
In the digital space, anything can be copied easily
Cheques provide a better analogy (though still a bit off)
● Signatures authorize transfer
● Clearinghouse detects copies
Cryptocurrencies use crypto for both cheque properties
Signatures replaced by digital signatures on transactions
Clearinghouse replaced by an append-only ledger ● Often, but not always, a decentralized ledger
Digital Signatures
What we want from signatures
Only legitimate party can sign, but anyone can verify
Signature commits to a particular transaction
● can’t be cut-and-pasted to another transaction
● can’t modify to a signature on something else
● more like a traditional seal than a signature
API for digital signatures
(sk, pk) := GenKey(security λ) sk: private/signing key
pk: public/verification key
σ := Sign(sk, message m)
isValid := Verify(pk, m, σ)
can be randomized algorithms
Signatures must be correct and secure
Correctness ⇔ “valid signatures verify” sk, pk = GenKey(λ)
Verify(pk, m, Sign(sk, m)) == True
Security ⇔ “can’t forge signatures” (existential unforgeability)
adversary knows pk and can learn signatures on messages of his choice can’t produce a verifiable signature on another message
Forgery “game”
challenger
Verify(pk, m*, σ*)
m0 sign(sk, m0)
m1 sign(sk, m1)
. .. m*, σ*
if true, attacker wins
Claim: no plausible* attacker can win this game
m* not in { m0, m1, … }
The fine print on signature security
● Attacker (and honest party) run in polynomial time
○ Polynomial in λ
○ Can be non-deterministic
● Attacker has a negligible chance of winning
○ Probability is O(2-λ)
● Is it a problem to output a different signature on a known message? ○ Signature malleability
Many applications of digital signatures
● Web certificates and TLS
● Email authenticity (e.g. PGP)
● Software updates
Common signature schemes:
● DSA/ECDSA
● Schnorr, EC-Schnorr
Bitcoin, Ethereum use ECDSA
Elliptic Curve Digital Signature Algorithm
GenKey() →x, gx (points on an elliptic curve, sometimes written as x, xG)
Sign(x, m) →[r = gk, s = k-1(m+xr)] (k must be random and never used again) Verify(y=gx, m, (r, s)) →r ≟ (gmyr)s^-1 (correctness ensure algebraically)
Why is this secure? Take a course on cryptography! Short answer: discrete-log problem
Parameter sizes for ECDSA signatures
Size (bits)
Private key
Public key
512 (257 compressed)
Signatures
Signature verification is fast. About 10,000/second on my laptop
Advanced properties of signature schemes
With ECDSA:
● Deterministic signing (avoid randomness bugs!)
● Hierarchical key derivation
● Secret sharing: split a key into parts
With better schemes:
● Threshold signing: sign using subset of partial keys (BLS, RSA, Schnorr)
● Aggregation: combine many signatures into one (BLS)
● Ring signatures: sign with a group of keys for anonymity
From signatures to basic cryptocurrency
Signatures can be seen as authoritative statements
Given σ such that Verify(pk, m, σ) → True, read it as: pk says: “m”
Public key functions as an identity:
All messages signed by that key are from the same source
Key generation produces limitless pseudorandom addresses
Addresses not bound to real-world names. Does that mean they are anonymous? To be discussed…
A first attempt at cryptocurrency
Goofy alone can create new coins
New coins belong to me.
signed by pkGoofy
CreateCoin [unique id X]
A coin’s owner signs it to spend
Alice owns it now.
signed by pkGoofy
Pay to pkAlice : X
signed by pkGoofy
CreateCoin [unique id X]
Coins can be repeatedly transferred
signed by pk to pkBob : X
Bob owns it now.
signed by pkGoofy
Pay to pkAlice : X
signed by pkGoofy
CreateCoin [unique id X]
Problem: double-spending attacks ☹
signed by pk to pkBob : X
signed by pk to pkChuck : X
signed by pkGoofy
Pay to pkAlice : X
signed by pkGoofy
CreateCoin [unique id X]
Cryptocurrencies prevent double-spending via a public log
signed by pkGoofy
CreateCoin [unique ID X]
signed by pkGoofy
Pay to pkAlice : X
signed by pk to pkBob : X
signed by pk to pkChuck : X
This transaction is clearly not valid…
The log should satisfy several properties
● Append-only
○ Data can never be removed
● Total ordering
○ Can observe which transaction came first
● Global consensus
○ Everybody needs to agree on contents
● Global availability
○ No censorship
signed by pkGoofy
CreateCoin [unique ID X]
signed by pkGoofy
Pay to pkAlice : X
signed by pk to pkBob : X
signed by pk to pkChuck : X
A ledger is a log which only publishes “valid” transactions Validity rules are system-dependent:
● No double spending
● Signatures validate
● Designated parties can create coins ● …
signed by pkGoofy
CreateCoin [unique ID X]
signed by pkGoofy
Pay to pkAlice : X
signed by pk to pkBob : X
Much cheaper not to distribute and re-validate invalid data
A ledger is a log which only publishes “valid” transactions Validity rules are system-dependent:
● No double spending
● Signatures validate
● Designated parties can create coins ● …
signed by pkGoofy
CreateCoin [unique ID X]
signed by pkGoofy
Pay to pkAlice : X
signed by pk to pkBob : X
Much cheaper not to distribute and re-validate invalid data
Cryptographic Hash Functions
Cryptographic hash functions Function H: {0,1}* →{0,1}t
● Takes any string as input
● Always produces t bits of output
● Deterministic, efficient
Security properties:
● collision-resistant ● hiding
● “puzzle-friendly”
Collision resistance
Nobody can find x and y such that x ≠ y and H(x)=H(y)
H(x) = H(y)
Collisions do exist, but they cannot be found efficiently
possible outputs
possible inputs
Finding a collision by brute-force
def find_collision(H):
x = random()
y = random()
if H(x) == H(y):
return (x, y)
Takes an average of 2t iterations to stop
Finding a collision by birthday attack
def find_collision(H):
x = random()
if H(x) in seen:
return x, seen[H(x)]
seen[H(x)] = x
Takes O(2t/2) iterations to stop
Collision resistance is a cryptographic assumption
● Assumption: no shortcut to finding collisions
● Established by years of trial and failure by cryptographers
● Shortcut found ⇔ hash function is “broken”
● Collision found ⇔ 🤦
Hash function graveyard:
● MD5 (collisions found 1996)
● SHA1 (collision found 2019)
SHA-256 hash function
Padding (10* | length)
Message (block 1)
Message (block 2)
256 bits IV
256 bits Hash
Theorem: If c is collision-free, then SHA-256 is collision-free.
Message (block n)
Assuming collision-res., hash functions are commitments We can say that the value H(x) is a commitment to x
● Analogy: like putting x into an envelope ✉
Commitments are binding: “open” commitment by revealing x ● Any other valid opening would be a collision for H
Application: sub-resource integrity
Web pages often include resources from third-party servers
SRI allows specifying the expected hash of the resource
● Server cannot change the value
● Network attacks prevented as well
Application: software distribution
Application: software distribution
Application: untrusted file storage
Given a large file F, store y = H(F) and upload F to the cloud
Later, can verify if download F’ is correct by checking if y = H(F’)
Natural question: what if you have n files?
Application: untrusted file storage with n files
Client has n files: F1, F2, … Fn
Wants to upload all of them to untrusted storage, verify later
Trivial solution #1: Store y1 = H(F1), y2 = H(F2), …yn = H(Fn) ● Requires O(n) storage
Trivial solution #2: Store y = H(F1 || F2 || … || Fn)
● Requires downloading every file to verify just one
Committing to a set: Merkle trees
● Leaf nodes are data values
● Each internal node value is
computed as h= H(hleft || hright)
● Root commits to the entire set
F1 F2 F3 F4 F5 F6 F7 F8
Proving inclusion in a set
How can we convince a verifier who only knows the root that F3 is in the set?
Nodes in proof
Proving inclusion in a set
Nodes in proof
Proving inclusion in a set
root Recomputed nodes
Proof size is O(lg n) Concretely: ⌈log2 n⌉
Merkle proof security from collision resistance
Theorem: if two proofs exist for F3 ≠ F’3 for the same root, then one node in the path is a hash collision in H
Generalized hash pointer authenticated data structures
The Merkle tree concept extends to other data structures
A Merkle tree is just a tree with hash pointers
● Traditional pointer: where the data is stored
● Hash pointer: commitment to what the data is
With a hash pointer plus a lookup service, we can:
● Uniquely identify data and request it
● Verify that it hasn’t changed
Hash pointer notation consistent with information flow
Hash pointer notation consistent with memory pointers
will draw hash pointers like this
Hash pointers are a powerful tool (Merklization)
can use hash pointers in any acyclic pointer-based data structure:
● Linked list (blockchain)
● Binary tree ( )
● Prefix tree/Radix tree ( Tree)
● Skip list
Linked list with hash pointers ⇔ blockchain
prev: H( )
prev: H( )
prev: H( )
Any change to old blocks will change head
prev: H( )
prev: H( )
prev: H( )
use case: tamper-evident log
Generally trees are better than chains!
Merkle tree performance:
● O(lg n) inclusion proofs
● O(lg n) non-inclusion proofs (if leaves sorted)
● O(lg n) proof of appension
Blockchain performance:
● O(n) inclusion proofs
● O(n) non-inclusion proofs (if leaves sorted)
● O(1) proof of appension
Blockchains use Merkle trees to batch transactions
H() H() H() H()
H() H() H() H() H() H() H() H()
F1 F2 F3 F4 F5 F6 F7 F8
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com