Coursera Intro to Crypto and Cryptocurrencies
Notes from Coursera’s Introduction to Crypto and Cryptocurrencies - Princeton University - Course.
Hashes
Hash must be:
- Collision resistent
- Application - Hash as Message Digest
- Hiding - Given H(r | x), r is chosen with high entropy. Hard to find H(y) = H(r | x)
- Ie Given Hash hard to find input
- Puzzle friendly - H(k | x) = y, hard to find x
- I.e. Hard to get Hash output to be a particular value
Commitment API
(com, sk) := commit(msg)
match := verify(com, sk, msg)
`
Think of com
as envelope and sk
to unlock envelope.
To seal: commit and then publish com
To open: publish sk and msg. Anyone can verify.
Properties:
- Hiding: Given com, infeasible to find msg.
- Binding: Infeasible to find msg != msg’ such that verify(commit(msg), msg’) == true
Hash pointer
Where something is and what its value was
- Can use in any pointer-based Data Structure
- tamper evident
- linked list = tamper evident log
- Block chain
- Merkle tree - Binary tree w/ Hash Pointers
- Can verify membership in O(log n)
- If sorted, can verify non-membership
Digital Signature
sig := sign(sk, message)
isValid := verify(pk, message, sig)
Decentralized ID management
- random public key - addresses in Bitcoin
Nodes don’t have Identities - no central authority to grant IDs, makes things harder
Sybil Attack - copy nodes to look like many
Double-spending attack
- include Transaction history to avoid
Node Latency - No notion of global time.
Explore: Byzantine generals problem and Fischer-Lynch-Peterson Impossibility Result
Consistency Protocols
Paxos
- Never produces inconsistent result
- Can rarely get stuck
Bitcoin violates theory to make work. Things done differently:
- Introduces incentives - possibly only b/c it’s a currency.
- Embraces randomness - consensus happens over long time scales
Consensus Algorithm (Simplified)
- New transactions are broadcast to all nodes.
- Each node collects new transactions into a block.
- In each round, a random node gets to broadcast its block.
- Other nodes accept the block only if all transactions in it are valid (unspent and valid signature)
- Nodes express their acceptance of block by including its hash in the next block they create.
Alice pays Bob. Block of transactions has pointer to previous block. Transaction has hash pointer to originating transaction.
Confirmation when block pointer added:
Recap
- Protection against invalid transactions is cryptographic, but enforced by consensus.
- Protection against double spending is purely consensus.
- Probabilistic guarantee of transaction is in consensus branch. Common heuristic is 6 confirmations
Incentives
- Block reward - special coin-creation transaction in the block
- Transaction Fee - creator of transaction can choose to make output value less than input value. Remainder goes to block creator (like tip).
Proof of Work
-
approximate selecting a random node by selecting nodes in proportion to a resource that no can monopolized (computing power)
- Nodes compete for right to create block
- Make it moderately hard to create new identities (protect against Sybil attack)
- Hash Puzzles - block must contain nonce (solution to puzzle)
- Currently about 10^20 hashes/block
- Recalculate target every 2 weeks w/ goal of average 10 minutes per block (Block Latency)
- Bernoulli trial is a random experiment with exactly two possible outcomes, “success” and “failure”, in which the probability of success is the same every time the experiment is conducted.
- Currently about 10^20 hashes/block
51% attacker could suppress transactions from blockchain, put not P2P network **
** would estroy confidence in Bitcoin**
Bitcoin Transaction
- Change address - send left over bitcoins back to self
Bitcoin Scripts
- Input (scriptSig) and output (scriptPubKey) addresses are really scripts
-
OP_DUP OP_HASH160 OP_EQUALITY OP_CHECKSIG
-
- to verify: concatenate script must execute w/o errors
- Inspired by Forth — stacked based language (no loops)
- Not Turing-complete — no halting problem
- Proof-of-burn - put something arbitrary in blockchain OP_RETURN
- Hash of Redemption Script
- Pay to Script Hash
Escrow Transactions - 2 of 3 multisig
Green Addresses - Bank agrees to pay Bob
Micro Payments w/ Micro-sig
- Send transaction every minute signed by buyer
- At the end seller only signs last transaction
- lock_time used— don’t publish transaction until some time in future
Bitcoin Network
- P2P Network
- Adhoc protocol - runs on TCP port 8333
- Random topology
- All nodes equal
- New nodes can join at any time - non-responding nodes are dropped after ~3hrs
Transactions across network
- Flooding algorithm
- Gossip Protocol - if you have news, try to tell as many people as you can
- Nodes propagate only if valid transaction
- script matches whitelist
- haven’t seen before
- coins haven’t been spent already
- Blocks similar
- Meets hash target
- Has all valid transactions
- Build on current longest chain — Avoids forks
- Chooses decentralized/openness to efficiently (takes on average 30s for block to propagate)
Fully validated node vs Thin/SVP client (don’t store entire blockchain, request transactions as needed, trust FVN)
Limitations
- 10 minute time per block
- 1 MB block size
- 20K signature operations per block
- 100M satoshi per bitcoin (divisibility)
- Total # of bitcoins in existence fixed
- Mining reward Fixed
- 7 transactions/sec
- Crypographic algos fixed (ECDSA/P256)
Soft Fork
Add new features that only limit set of valid transactions
- Need majority of nodes to enforce new rules
- e.g. Pay to Script Hash
Storing Secret Key
- Availabiltiy
- Security
- Convenience
Wallet Software
- Many keys— seperate key for each coin
Hot and Cold Storage
- Cold storage not online
- separate secret keys/addresses
Hierarchical Wallet - hierarchical key generation
Splitting and Sharing Keys
- Secret sharing -
- split secret into N pieces
- need at least K pieces to reconstruct secret, don’t know anything if have < K pieces
- K = 2 line (S + RX) mod P
- K = 3 quadratic
- need at least K pieces to reconstruct secret, don’t know anything if have < K pieces
- Problem have to recombine to get secret key
- Multi-sig safer atlernative
- split secret into N pieces
Proof of Reserve
- Prove how much reserve you’re holding (X)
- publish valid pay-to-self amount and sign challenge string w/ same private key
- Prove how many demand deposits you hold (Y)
- Merkle tree w/ subtree total
- Reserve fraction = X/Y
transaction fee = value of inputs - value of outputs, fee goes to miner
Goodput = throughput x success rate
FPGA - Field Programmable Gate Arrays
Landauer’s Principle - Any non-reversible computation must consume a minimum amount of energy
Mining shares - can prove how much work done when participating in mining pool
Checkpointing
-
guard against forking attack
-
In bitcoin code, prevents forking from a certain point
Block-withholding attack - find 2 blocks in a row. Will orphan next proposed valid block by another node.
Anonymity
Anonymity = pseudonymity + unlinkability
Blind Signature - first anonymous e-cash
- Always receive at new address
- Problems: Shared spending is evidence of joint control
- Addresses can be linked transitively
- Idioms of use - change address
- Problems: Shared spending is evidence of joint control
Mixing - use intermediary (proxy) to mix coin input/outputs
-
Promise: won’t keep records, no need for identity
-
online wallets can somewhat function like one
Principles:
- Use a series of mixes (currently, not the case)
- Uniform transaction value, “chunk,” size
- Must be automated (built into online wallet software) to avoid other attacks like timing
- Fees must be all or nothing
Decentralized Mixing, e.g. Coinjoin
- Find peers who want to mix
- Exchange input/output addresses
- Construct transaction
- Send it around to collect signatures
- Broadcast transaction
Problems:
- How to find peers
- Peers know you input-output mapping
- Solution: decryption mixmaps
- DoS
- Solution: Proof of work/burn (fidelity bonds)
Merge avoidance - multiple input/output addresses
Zerocoin
- Mixing backed in
- Mint and put _com (keyed hash of serial number) _on blockchain
- Burn a “Basecoin”
- Reveal SN to spend
- Can pick arbitrary zero coin in blockchain (leads to anyominity)