Cryptography

Cryptography is the practice of secure communications by encoding and decoding.

from special lecture by Prof Veneris

encryption — transmit a message without being intercepted define:

• $S(C)$: decryption of encrypted message $C$
• $P(M)$: encryption of message $M$ to $C$

symmetric encryption

• both parties agree on a single key
• sender has plaintext message $M$, and uses key to encrypt. then transmits
• receiver uses the same key to decrypt the message
• problem: you don’t really solve the problem. what if sender/receiver never meet?

asymmetric encryption

• public, private key, like PGP; sender receiver both have set of public, private keys
• secret key — only you possess. you get original back by doing maths with secret key
• sender signs the message with the public key of receiver, encrypts and sends message
• receiver decrypts with secret key

digital signature

• $M$ plaintext
• $T$ signature (or tag)
• $T=\text{Sign}(M,S)⟹\text{Check}(T,M,P)=1$
• i.e., you can verify sender was the actual sender

how to generate key pairs?

• relies on cryptography, essentially number theory. relies on idea that Prime factorisation is very difficult

RSA:

• select two very large primes $p,q$ (over 1000 bits; RSA with ~700 bits has been cracked already)
• compute $n=pq$
• compute $\phi (n)=(p-1)(q-1)$
• select small odd integer $e$, relative prime to $\phi (n)$
• compute $d$ such that $de\mathrm{mod}\phi (n)=1$, i.e., modulo fn == 1
• keys
  • public key $P=(e,n)$
  • secret key $S=(d,n)$
• basically: $n$ too large. so very hard to invert operation
• but RSA no longer really used, use elliptic curve cryptography

cryptographic Hash function $h(M)$

• must be deterministic given same message $M$
• $h(M)\ne h(M^{\prime })$ even if $M$ and $M^{\prime }$ very similar
• $h$ is intractable to invert, i.e., find $h^{-1}$ (trapdoors)
• $h$ collision resistant, i.e., intractable to find messages $M,M^{\prime }$ such that $M\ne M^{\prime }$ and $h(M)=h(M^{\prime })$, i.e., different messages that that produce same hash

Bitcoin

• UTXO model — unspent transaction output
  • suppose sender has 10 B, wants to send 6 B to receiver
  • she sends 6 to receiver, 4 to herself
  • let $⟨T_i,O_j⟩$ be the $j$th output of the $i$th transaction
• transaction — consists of two nodes
  • has both sender and receiver’s signature
  • has receiver’s public key, so only receiver can decrypt with private key
  • non-repudiation: receiver is the only one that can decrypt the message
• bitcoin block
  • Merkle tree — binary tree for cryptographic messages
    • leaves are cryptographic messages
  • blocks have a header: hash of previous block, hash of transactions (root of Merkle tree), and a number used once (nonce)
• miner
  • crazy amount of computation to find nonce such that hash of previous block, nonce, and transaction hash is smaller than difficulty of network
  • i.e., $h(p,n,t)<{\text{diff}}_{\text{net}}$
  • difficulty target chosen st block discovered every 10 minutes
  • difficulty of network self adjusts every ~2 weeks (maybe more miners one week)
  • NP-complete problem — finding problem tough, verifying is easy
  • if block is confirmed by multiple miners, each person gets a bit of B
    • forks the chain. then next block will resolve on a single path to longer path
  • by 2140, B will stop mining
• mining rewards
  • block rewards
  • transaction fees
  • block reward will halve every 4 years until being rounded to 0
• proof of work
  • for example, how can we prevent spam email? by charging the sender
  • creates economic incentive to compete and agree to use the canonical chain
  • Game theory - described by shelling point
  • prohibitively expensive to make a non canonical fork the canonical fork
  • basically more computational power than you get back
• value of Bitcoin
  • for fiat currency, value is backed by the government/central bank etc
    • how do paypal, visa, etc work? they have their own private money, they issue dollar tokens, which is what we get. so it’s not real money. from fractional reserve system
    • M0 money, much less than real money is — 8 T dollars
    • derivatives - insurance of insurance of … in excess of 900 trillion - money that DNE
    • ”in my view, voodoo economics” - Veneris
    • why everything collapsed in 2008
  • bitcoin: able to transfer value without central authority
  • very stable - no downtime since inception

Ethereum

• vs Bitcoin
  • bitcoin has no programmability, based on a simple stack language
  • Ethereum written in Solidity, based on JavaScript
• Smart contract
  • Ethereum guarantees execution of the contract
  • as a Finite state machine
  • idea: charge per computation
  • trustless computer, all miners have to agree on state transitions

criticisms

• power: Bitcoin consumes a shit ton of power, more than the country of Austria consumes. Ethereum also has same problem
• proof of stake — stake down your own ether, verify transactions? idk
• scalability
  • per network
    • bitcoin: 3-7 trans/sec
    • eth: ~20
    • visa: 2000, can hit 20k at peak
    • paypal: 200
  • L1 network: Ethereum, bitcoin
  • L2 network: slightly separate, aggregate transactions, register back to L1 network
    • but not necessarily secure or decentralised

decentralised finance v centralised finance

• DeFi vs CeFi
• centralised: what we have now. idea: allows middlemen fees (ex with foreign currency exchanges), has delays (foreign transfers)
• decentralised: transparent, on chain. assets can be traded with absolute transparency

central bank digital currencies

• or just digital currencies
• like in China
• most govts studying them