Coursera Intro to Crypto and Cryptocurrencies

Notes from Coursera’s Introduction to Crypto and Cryptocurrencies - Princeton University - Course.

Hashes

Hash must be:

  1. Collision resistent
    1. Application - Hash as Message Digest
  2. Hiding - Given H(r | x), r is chosen with high entropy. Hard to find H(y) = H(r | x)
    1. Ie Given Hash hard to find input
  3. Puzzle friendly - H(k | x) = y, hard to find x
    1. 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:

  1. Hiding: Given com, infeasible to find msg.
  2. Binding: Infeasible to find msg != msg’ such that verify(commit(msg), msg’) == true

Hash pointer

Where something is and what its value was

Digital Signature

sig := sign(sk, message)

isValid := verify(pk, message, sig)

Decentralized ID management

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

Node Latency - No notion of global time.

Explore: Byzantine generals problem and Fischer-Lynch-Peterson Impossibility Result

Consistency Protocols

Paxos

Bitcoin violates theory to make work. Things done differently:

  1. Introduces incentives - possibly only b/c it’s a currency.
  2. Embraces randomness - consensus happens over long time scales

Consensus Algorithm (Simplified)

  1. New transactions are broadcast to all nodes.
  2. Each node collects new transactions into a block.
  3. In each round, a random node gets to broadcast its block.
  4. Other nodes accept the block only if all transactions in it are valid (unspent and valid signature)
  5. Nodes express their acceptance of block by including its hash in the next block they create.

Screen_Shot_2017-11-27_at_1-18-26_PM.png

Alice pays Bob. Block of transactions has pointer to previous block. Transaction has hash pointer to originating transaction.

Confirmation when block pointer added:

Screen_Shot_2017-11-27_at_1-35-31_PM.png

Recap

  1. Protection against invalid transactions is cryptographic, but enforced by consensus.
  2. Protection against double spending is purely consensus.
  3. Probabilistic guarantee of transaction is in consensus branch. Common heuristic is 6 confirmations

Incentives

  1. Block reward - special coin-creation transaction in the block
  2. 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

51% attacker could suppress transactions from blockchain, put not P2P network **

** would estroy confidence in Bitcoin**

Bitcoin Transaction

Bitcoin Scripts

Escrow Transactions  - 2 of 3 multisig

Green Addresses - Bank agrees to pay Bob

Micro Payments w/ Micro-sig

Bitcoin Network

Transactions across network

Fully validated node vs Thin/SVP client (don’t store entire blockchain, request transactions as needed, trust FVN)

Limitations

Soft Fork

Add new features that only limit set of valid transactions

Storing Secret Key

  1. Availabiltiy
  2. Security
  3. Convenience

Wallet Software

Hot and Cold Storage

Hierarchical Wallet - hierarchical key generation

Splitting and Sharing Keys

Proof of Reserve

  1. Prove how much reserve you’re holding (X)
    1. publish valid pay-to-self amount and sign challenge string w/ same private key
  2. Prove how many demand deposits you hold (Y)
    1. Merkle tree w/ subtree total
  3. 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

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

Mixing - use intermediary (proxy) to mix coin input/outputs

Principles:

  1. Use a series of mixes (currently, not the case)
  2. Uniform transaction value, “chunk,” size 
  3. Must be automated (built into online wallet software) to avoid other attacks like timing
  4. Fees must be all or nothing

Decentralized Mixing, e.g. Coinjoin

  1. Find peers who want to mix
  2. Exchange input/output addresses
  3. Construct transaction
  4. Send it around to collect signatures
  5. Broadcast transaction

Problems:

  1. How to find peers
  2. Peers know you input-output mapping
    1. Solution: decryption mixmaps
  3. DoS
    1. Solution: Proof of work/burn (fidelity bonds)

Merge avoidance - multiple input/output addresses

Zerocoin

Screen_Shot_2018-02-06_at_11-03-51_AM.png